src/mesa/state_tracker/tests/test_glsl_to_tgsi_lifetime.cpp

   1 /*
   2  * Copyright © 2017 Gert Wollny
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 #include <state_tracker/st_glsl_to_tgsi_temprename.h>
  25 #include <tgsi/tgsi_ureg.h>
  26 #include <tgsi/tgsi_info.h>
  27 #include <compiler/glsl/list.h>
  28 #include <mesa/program/prog_instruction.h>
  29
  30 #include <utility>
  31 #include <gtest/gtest.h>
  32
  33 using std::vector;
  34 using std::pair;
  35 using std::make_pair;
  36
  37 /* A line to describe a TGSI instruction for building mock shaders. */
  38 struct MockCodeline {
  39    MockCodeline(unsigned _op): op(_op) {}
  40    MockCodeline(unsigned _op, const vector<int>& _dst, const vector<int>& _src, const vector<int>&_to):
  41       op(_op), dst(_dst), src(_src), tex_offsets(_to){}
  42    unsigned op;
  43    vector<int> dst;
  44    vector<int> src;
  45    vector<int> tex_offsets;
  46 };
  47
  48 /* A line to describe a TGSI instruction with swizzeling and write makss
  49  * for building mock shaders.
  50  */
  51 struct MockCodelineWithSwizzle {
  52    MockCodelineWithSwizzle(unsigned _op): op(_op) {}
  53    MockCodelineWithSwizzle(unsigned _op, const vector<pair<int,int>>& _dst,
  54                            const vector<pair<int, const char *>>& _src,
  55                            const vector<pair<int, const char *>>&_to):
  56       op(_op), dst(_dst), src(_src), tex_offsets(_to){}
  57    unsigned op;
  58    vector<pair<int,int>> dst;
  59    vector<pair<int, const char *>> src;
  60    vector<pair<int, const char *>> tex_offsets;
  61 };
  62
  63 /* A few constants that will notbe tracked as temporary registers by the
  64  * mock shader.
  65  */
  66 const int in0 = -1;
  67 const int in1 = -2;
  68 const int in2 = -3;
  69
  70 const int out0 = -1;
  71 const int out1 = -2;
  72
  73 class MockShader {
  74 public:
  75    MockShader(const vector<MockCodeline>& source);
  76    MockShader(const vector<MockCodelineWithSwizzle>& source);
  77    ~MockShader();
  78
  79    void free();
  80
  81    exec_list* get_program() const;
  82    int get_num_temps() const;
  83 private:
  84    st_src_reg create_src_register(int src_idx);
  85    st_dst_reg create_dst_register(int dst_idx);
  86    st_src_reg create_src_register(int src_idx, const char *swizzle);
  87    st_dst_reg create_dst_register(int dst_idx,int writemask);
  88    exec_list* program;
  89    int num_temps;
  90    void *mem_ctx;
  91 };
  92
  93 using expectation = vector<vector<int>>;
  94
  95 class MesaTestWithMemCtx : public testing::Test {
  96    void SetUp();
  97    void TearDown();
  98 protected:
  99    void *mem_ctx;
 100 };
 101
 102 class LifetimeEvaluatorTest : public MesaTestWithMemCtx {
 103 protected:
 104    void run(const vector<MockCodeline>& code, const expectation& e);
 105    void run(const vector<MockCodelineWithSwizzle>& code, const expectation& e);
 106 private:
 107    virtual void check(const vector<lifetime>& result, const expectation& e) = 0;
 108 };
 109
 110 /* This is a test class to check the exact life times of
 111  * registers. */
 112 class LifetimeEvaluatorExactTest : public LifetimeEvaluatorTest {
 113 protected:
 114    void check(const vector<lifetime>& result, const expectation& e);
 115 };
 116
 117 /* This test class checks that the life time covers at least
 118  * in the expected range. It is used for cases where we know that
 119  * a the implementation could be improved on estimating the minimal
 120  * life time.
 121  */
 122 class LifetimeEvaluatorAtLeastTest : public LifetimeEvaluatorTest {
 123 protected:
 124    void check(const vector<lifetime>& result, const expectation& e);
 125 };
 126
 127 TEST_F(LifetimeEvaluatorExactTest, SimpleMoveAdd)
 128 {
 129    const vector<MockCodeline> code = {
 130       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 131       { TGSI_OPCODE_UADD, {out0}, {1,in0}, {}},
 132       { TGSI_OPCODE_END}
 133    };
 134    run(code, expectation({{-1,-1}, {0,1}}));
 135 }
 136
 137 TEST_F(LifetimeEvaluatorExactTest, SimpleMoveAddMove)
 138 {
 139    const vector<MockCodeline> code = {
 140       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 141       { TGSI_OPCODE_UADD, {2}, {1,in0}, {}},
 142       { TGSI_OPCODE_MOV, {out0}, {2}, {}},
 143       { TGSI_OPCODE_END}
 144    };
 145    run(code, expectation({{-1, -1}, {0,1}, {1,2}}));
 146 }
 147
 148 /* Test whether the texoffst are actually visited by the
 149  * merge algorithm. Note that it is of no importance
 150  * what instruction is actually used, the MockShader class
 151  * does not consider the details of the operation, only
 152  * the number of arguments is of importance.
 153  */
 154 TEST_F(LifetimeEvaluatorExactTest, SimpleOpWithTexoffset)
 155 {
 156    const vector<MockCodeline> code = {
 157       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 158       { TGSI_OPCODE_MOV, {2}, {in1}, {}},
 159       { TGSI_OPCODE_TEX, {out0}, {in0}, {1,2}},
 160       { TGSI_OPCODE_END}
 161    };
 162    run(code, expectation({{-1, -1}, {0,2}, {1,2}}));
 163 }
 164
 165 /* Simple register access involving a loop
 166  * 1: must life up to then end of the loop
 167  * 2: only needs to life from write to read
 168  * 3: only needs to life from write to read outside the loop
 169  */
 170 TEST_F(LifetimeEvaluatorExactTest, SimpleMoveInLoop)
 171 {
 172    const vector<MockCodeline> code = {
 173       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 174       { TGSI_OPCODE_BGNLOOP },
 175       {   TGSI_OPCODE_UADD, {2}, {1,in0}, {}},
 176       {   TGSI_OPCODE_UADD, {3}, {1,2}, {}},
 177       {   TGSI_OPCODE_UADD, {3}, {3,in1}, {}},
 178       { TGSI_OPCODE_ENDLOOP },
 179       { TGSI_OPCODE_MOV, {out0}, {3}, {}},
 180       { TGSI_OPCODE_END}
 181    };
 182    run (code, expectation({{-1,-1}, {0,5}, {2,3}, {3,6}}));
 183 }
 184
 185 /* In loop if/else value written only in one path, and read later
 186  * - value must survive the whole loop.
 187  */
 188 TEST_F(LifetimeEvaluatorExactTest, MoveInIfInLoop)
 189 {
 190    const vector<MockCodeline> code = {
 191       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 192       { TGSI_OPCODE_BGNLOOP },
 193       {   TGSI_OPCODE_IF, {}, {in1}, {}},
 194       {     TGSI_OPCODE_UADD, {2}, {1,in0}, {}},
 195       {   TGSI_OPCODE_ENDIF},
 196       {   TGSI_OPCODE_UADD, {3}, {1,2}, {}},
 197       {   TGSI_OPCODE_UADD, {3}, {3,in1}, {}},
 198       { TGSI_OPCODE_ENDLOOP },
 199       { TGSI_OPCODE_MOV, {out0}, {3}, {}},
 200       { TGSI_OPCODE_END}
 201    };
 202    run (code, expectation({{-1,-1}, {0,7}, {1,7}, {5,8}}));
 203 }
 204
 205 /* A non-dominant write within an IF can be ignored (if it is read
 206  * later)
 207  */
 208 TEST_F(LifetimeEvaluatorExactTest, NonDominantWriteinIfInLoop)
 209 {
 210    const vector<MockCodeline> code = {
 211       { TGSI_OPCODE_BGNLOOP },
 212       {   TGSI_OPCODE_MOV, {1}, {in0}, {}},
 213       {   TGSI_OPCODE_IF, {}, {in1}, {}},
 214       {     TGSI_OPCODE_MOV, {1}, {in1}, {}},
 215       {   TGSI_OPCODE_ENDIF},
 216       {   TGSI_OPCODE_UADD, {2}, {1,in1}, {}},
 217       {   TGSI_OPCODE_IF, {}, {2}, {}},
 218       {     TGSI_OPCODE_BRK},
 219       {   TGSI_OPCODE_ENDIF},
 220       { TGSI_OPCODE_ENDLOOP },
 221       { TGSI_OPCODE_MOV, {out0}, {2}, {}},
 222       { TGSI_OPCODE_END}
 223    };
 224    run (code, expectation({{-1,-1}, {1,5}, {5,10}}));
 225 }
 226
 227 /* In Nested loop if/else value written only in one path, and read later
 228  * - value must survive the outer loop.
 229  */
 230 TEST_F(LifetimeEvaluatorExactTest, MoveInIfInNestedLoop)
 231 {
 232    const vector<MockCodeline> code = {
 233       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 234       { TGSI_OPCODE_BGNLOOP },
 235       {   TGSI_OPCODE_BGNLOOP },
 236       {     TGSI_OPCODE_IF, {}, {in1}, {} },
 237       {       TGSI_OPCODE_UADD, {2}, {1,in0}, {}},
 238       {     TGSI_OPCODE_ENDIF},
 239       {     TGSI_OPCODE_UADD, {3}, {1,2}, {}},
 240       {   TGSI_OPCODE_ENDLOOP },
 241       { TGSI_OPCODE_ENDLOOP },
 242       { TGSI_OPCODE_MOV, {out0}, {3}, {}},
 243       { TGSI_OPCODE_END}
 244    };
 245    run (code, expectation({{-1,-1}, {0,8}, {1,8}, {6,9}}));
 246 }
 247
 248 /* In loop if/else value written in both path, and read later
 249  * - value must survive from first write to last read in loop
 250  * for now we only check that the minimum life time is correct.
 251  */
 252 TEST_F(LifetimeEvaluatorAtLeastTest, WriteInIfAndElseInLoop)
 253 {
 254    const vector<MockCodeline> code = {
 255       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 256       { TGSI_OPCODE_BGNLOOP },
 257       {   TGSI_OPCODE_IF, {}, {1}, {}},
 258       {     TGSI_OPCODE_UADD, {2}, {1,in0}, {}},
 259       {   TGSI_OPCODE_ELSE },
 260       {     TGSI_OPCODE_MOV, {2}, {1}, {}},
 261       {   TGSI_OPCODE_ENDIF},
 262       {   TGSI_OPCODE_UADD, {3}, {1,2}, {}},
 263       {   TGSI_OPCODE_UADD, {3}, {3,in1}, {}},
 264       { TGSI_OPCODE_ENDLOOP },
 265       { TGSI_OPCODE_MOV, {out0}, {3}, {}},
 266       { TGSI_OPCODE_END}
 267    };
 268    run (code, expectation({{-1,-1}, {0,9}, {3,7}, {7,10}}));
 269 }
 270
 271 /* In loop if/else value written in both path, read in else path
 272  * before write and also read later
 273  * - value must survive the whole loop
 274  */
 275 TEST_F(LifetimeEvaluatorExactTest, WriteInIfAndElseReadInElseInLoop)
 276 {
 277    const vector<MockCodeline> code = {
 278       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 279       { TGSI_OPCODE_BGNLOOP },
 280       {   TGSI_OPCODE_IF, {}, {1}, {}},
 281       {     TGSI_OPCODE_UADD, {2}, {1,in0}, {}},
 282       {   TGSI_OPCODE_ELSE },
 283       {     TGSI_OPCODE_ADD, {2}, {1,2}, {}},
 284       {   TGSI_OPCODE_ENDIF},
 285       {   TGSI_OPCODE_UADD, {3}, {1,2}, {}},
 286       {   TGSI_OPCODE_UADD, {3}, {3,in1}, {}},
 287       { TGSI_OPCODE_ENDLOOP },
 288       { TGSI_OPCODE_MOV, {out0}, {3}, {}},
 289       { TGSI_OPCODE_END}
 290    };
 291    run (code, expectation({{-1,-1}, {0,9}, {1,9}, {7,10}}));
 292 }
 293
 294 /* In loop if/else read in one path before written in the same loop
 295  * - value must survive the whole loop
 296  */
 297 TEST_F(LifetimeEvaluatorExactTest, ReadInIfInLoopBeforeWrite)
 298 {
 299    const vector<MockCodeline> code = {
 300       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 301       { TGSI_OPCODE_BGNLOOP },
 302       {   TGSI_OPCODE_IF, {}, {in0}, {}},
 303       {     TGSI_OPCODE_UADD, {2}, {1,3}, {}},
 304       {   TGSI_OPCODE_ENDIF},
 305       {   TGSI_OPCODE_UADD, {3}, {1,2}, {}},
 306       {   TGSI_OPCODE_UADD, {3}, {3,in1}, {}},
 307       { TGSI_OPCODE_ENDLOOP },
 308       { TGSI_OPCODE_MOV, {out0}, {3}, {}},
 309       { TGSI_OPCODE_END}
 310    };
 311    run (code, expectation({{-1,-1}, {0,7}, {1,7}, {1,8}}));
 312 }
 313
 314 /* In loop if/else read in one path before written in the same loop
 315  * read after the loop, value must survivethe whole loop and
 316  * to the read.
 317  */
 318 TEST_F(LifetimeEvaluatorExactTest, ReadInLoopInIfBeforeWriteAndLifeToTheEnd)
 319 {
 320    const vector<MockCodeline> code = {
 321       { TGSI_OPCODE_BGNLOOP },
 322       {   TGSI_OPCODE_IF, {}, {in0}, {}},
 323       {     TGSI_OPCODE_MUL, {1}, {1,in1}, {}},
 324       {   TGSI_OPCODE_ENDIF},
 325       {   TGSI_OPCODE_UADD, {1}, {1,in1}, {}},
 326       { TGSI_OPCODE_ENDLOOP },
 327       { TGSI_OPCODE_MOV, {out0}, {1}, {}},
 328       { TGSI_OPCODE_END}
 329    };
 330    run (code, expectation({{-1,-1}, {0,6}}));
 331 }
 332
 333 /* In loop if/else read in one path before written in the same loop
 334  * read after the loop, value must survivethe whole loop and
 335  * to the read.
 336  */
 337 TEST_F(LifetimeEvaluatorExactTest, ReadInLoopBeforeWriteAndLifeToTheEnd)
 338 {
 339    const vector<MockCodeline> code = {
 340       { TGSI_OPCODE_BGNLOOP },
 341       {   TGSI_OPCODE_MUL, {1}, {1,in1}, {}},
 342       {   TGSI_OPCODE_UADD, {1}, {1,in1}, {}},
 343       { TGSI_OPCODE_ENDLOOP },
 344       { TGSI_OPCODE_MOV, {out0}, {1}, {}},
 345       { TGSI_OPCODE_END}
 346    };
 347    run (code, expectation({{-1,-1}, {0,4}}));
 348 }
 349
 350
 351 /* Write in nested ifs in loop, for now we do test whether the
 352  * life time is at least what is required, but we know that the
 353  * implementation doesn't do a full check and sets larger boundaries
 354  */
 355 TEST_F(LifetimeEvaluatorAtLeastTest, NestedIfInLoopAlwaysWriteButNotPropagated)
 356 {
 357    const vector<MockCodeline> code = {
 358       { TGSI_OPCODE_BGNLOOP },
 359       {   TGSI_OPCODE_IF, {}, {in0}, {}},
 360       {     TGSI_OPCODE_IF, {}, {in0}, {}},
 361       {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
 362       {     TGSI_OPCODE_ELSE},
 363       {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
 364       {     TGSI_OPCODE_ENDIF},
 365       {   TGSI_OPCODE_ELSE},
 366       {     TGSI_OPCODE_IF, {}, {in0}, {}},
 367       {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
 368       {     TGSI_OPCODE_ELSE},
 369       {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
 370       {     TGSI_OPCODE_ENDIF},
 371       {   TGSI_OPCODE_ENDIF},
 372       {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
 373       { TGSI_OPCODE_ENDLOOP },
 374       { TGSI_OPCODE_END}
 375    };
 376    run (code, expectation({{-1,-1}, {3,14}}));
 377 }
 378
 379 /* The value is written in a loop and in a nested if, but
 380  * not in all code paths, hence the value must survive the loop.
 381  */
 382 TEST_F(LifetimeEvaluatorExactTest, NestedIfInLoopWriteNotAlways)
 383 {
 384    const vector<MockCodeline> code = {
 385       { TGSI_OPCODE_BGNLOOP },
 386       {   TGSI_OPCODE_IF, {}, {in0}, {}},
 387       {     TGSI_OPCODE_IF, {}, {in0}, {}},
 388       {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
 389       {     TGSI_OPCODE_ELSE},
 390       {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
 391       {     TGSI_OPCODE_ENDIF},
 392       {   TGSI_OPCODE_ELSE},
 393       {     TGSI_OPCODE_IF, {}, {in0}, {}},
 394       {       TGSI_OPCODE_MOV, {1}, {in0}, {}},
 395       {     TGSI_OPCODE_ENDIF},
 396       {   TGSI_OPCODE_ENDIF},
 397       {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
 398       { TGSI_OPCODE_ENDLOOP },
 399       { TGSI_OPCODE_END}
 400    };
 401    run (code, expectation({{-1,-1}, {0,13}}));
 402 }
 403
 404 /* A continue in the loop is not relevant */
 405 TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteAfterContinue)
 406 {
 407    const vector<MockCodeline> code = {
 408       { TGSI_OPCODE_BGNLOOP },
 409       {   TGSI_OPCODE_IF, {}, {in0}, {}},
 410       {     TGSI_OPCODE_CONT},
 411       {   TGSI_OPCODE_ENDIF},
 412       {   TGSI_OPCODE_MOV, {1}, {in0}, {}},
 413       { TGSI_OPCODE_ENDLOOP },
 414       { TGSI_OPCODE_MOV, {out0}, {1}, {}},
 415       { TGSI_OPCODE_END}
 416    };
 417    run (code, expectation({{-1,-1}, {4,6}}));
 418 }
 419
 420 /* Temporary used to in case must live up to the case
 421  * statement where it is used, the switch we only keep
 422  * for the actual SWITCH opcode like it is in tgsi_exec.c, the
 423  * only current use case.
 424  */
 425 TEST_F(LifetimeEvaluatorExactTest, UseSwitchCase)
 426 {
 427    const vector<MockCodeline> code = {
 428       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 429       { TGSI_OPCODE_MOV, {2}, {in1}, {}},
 430       { TGSI_OPCODE_MOV, {3}, {in2}, {}},
 431       { TGSI_OPCODE_SWITCH, {}, {3}, {}},
 432       {   TGSI_OPCODE_CASE, {}, {2}, {}},
 433       {   TGSI_OPCODE_CASE, {}, {1}, {}},
 434       {   TGSI_OPCODE_BRK},
 435       {   TGSI_OPCODE_DEFAULT},
 436       { TGSI_OPCODE_ENDSWITCH},
 437       { TGSI_OPCODE_END}
 438    };
 439    run (code, expectation({{-1,-1}, {0,5}, {1,4}, {2,3}}));
 440 }
 441
 442 /* With two destinations, if one result is thrown away, the
 443  * register must be kept past the writing instructions.
 444  */
 445 TEST_F(LifetimeEvaluatorExactTest, WriteTwoOnlyUseOne)
 446 {
 447    const vector<MockCodeline> code = {
 448       { TGSI_OPCODE_DFRACEXP , {1,2}, {in0}, {}},
 449       { TGSI_OPCODE_ADD , {3}, {2,in0}, {}},
 450       { TGSI_OPCODE_MOV, {out1}, {3}, {}},
 451       { TGSI_OPCODE_END},
 452
 453    };
 454    run (code, expectation({{-1,-1}, {0,1}, {0,1}, {1,2}}));
 455 }
 456
 457 /* If a break is in the loop, all variables written after the
 458  * break and used outside the loop must be maintained for the
 459  * whole loop
 460  */
 461 TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteAfterBreak)
 462 {
 463    const vector<MockCodeline> code = {
 464       { TGSI_OPCODE_BGNLOOP },
 465       {   TGSI_OPCODE_IF, {}, {in0}, {}},
 466       {     TGSI_OPCODE_BRK},
 467       {   TGSI_OPCODE_ENDIF},
 468       {   TGSI_OPCODE_MOV, {1}, {in0}, {}},
 469       { TGSI_OPCODE_ENDLOOP },
 470       { TGSI_OPCODE_MOV, {out0}, {1}, {}},
 471       { TGSI_OPCODE_END}
 472    };
 473    run (code, expectation({{-1,-1}, {0,6}}));
 474 }
 475
 476 /* If a break is in the loop, all variables written after the
 477  * break and used outside the loop must be maintained for the
 478  * whole loop. The first break in the loop is the defining one.
 479  */
 480 TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteAfterBreak2Breaks)
 481 {
 482    const vector<MockCodeline> code = {
 483       { TGSI_OPCODE_BGNLOOP },
 484       {   TGSI_OPCODE_IF, {}, {in0}, {}},
 485       {     TGSI_OPCODE_BRK},
 486       {   TGSI_OPCODE_ENDIF},
 487       {   TGSI_OPCODE_MOV, {1}, {in0}, {}},
 488       {   TGSI_OPCODE_BRK},
 489       { TGSI_OPCODE_ENDLOOP },
 490       { TGSI_OPCODE_MOV, {out0}, {1}, {}},
 491       { TGSI_OPCODE_END}
 492    };
 493    run (code, expectation({{-1,-1}, {0,7}}));
 494 }
 495
 496 /* Loop with a break at the beginning and read/write in the post
 497  * break loop scope. The value written and read within the loop
 498  * can be limited to [write, read], but the value read outside the
 499  * loop must survive the whole loop. This is the typical code for
 500  * while and for loops, where the breaking condition is tested at
 501  * the beginning.
 502  */
 503 TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteAndReadAfterBreak)
 504 {
 505    const vector<MockCodeline> code = {
 506       { TGSI_OPCODE_BGNLOOP },
 507       {   TGSI_OPCODE_IF, {}, {in0}, {}},
 508       {     TGSI_OPCODE_BRK},
 509       {   TGSI_OPCODE_ENDIF},
 510       {   TGSI_OPCODE_MOV, {1}, {in0}, {}},
 511       {   TGSI_OPCODE_MOV, {2}, {1}, {}},
 512       { TGSI_OPCODE_ENDLOOP },
 513       { TGSI_OPCODE_MOV, {out0}, {2}, {}},
 514       { TGSI_OPCODE_END}
 515    };
 516    run (code, expectation({{-1,-1}, {4,5}, {0,7}}));
 517 }
 518
 519 /* Same as above, just make sure that the life time of the local variable
 520  * in the outer loop (3) is not accidently promoted to the whole loop.
 521  */
 522 TEST_F(LifetimeEvaluatorExactTest, NestedLoopWithWriteAndReadAfterBreak)
 523 {
 524    const vector<MockCodeline> code = {
 525       { TGSI_OPCODE_BGNLOOP },
 526       {   TGSI_OPCODE_IF, {}, {in1}, {}},
 527       {     TGSI_OPCODE_BRK},
 528       {   TGSI_OPCODE_ENDIF},
 529       {   TGSI_OPCODE_BGNLOOP},
 530       {     TGSI_OPCODE_IF, {}, {in0}, {}},
 531       {       TGSI_OPCODE_BRK},
 532       {     TGSI_OPCODE_ENDIF},
 533       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
 534       {     TGSI_OPCODE_MOV, {2}, {1}, {}},
 535       {   TGSI_OPCODE_ENDLOOP },
 536       {   TGSI_OPCODE_ADD, {3}, {2,in0}, {}},
 537       {   TGSI_OPCODE_ADD, {4}, {3,in2}, {}},
 538       { TGSI_OPCODE_ENDLOOP },
 539       { TGSI_OPCODE_MOV, {out0}, {4}, {}},
 540       { TGSI_OPCODE_END}
 541    };
 542    run (code, expectation({{-1,-1}, {8,9}, {0,13}, {11,12}, {0,14}}));
 543 }
 544
 545 /* If a break is in the loop inside a switch case, make sure it is
 546  * interpreted as breaking that inner loop, i.e. the variable has to
 547  * survive the loop.
 548  */
 549 TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteAfterBreakInSwitchInLoop)
 550 {
 551    const vector<MockCodeline> code = {
 552       { TGSI_OPCODE_SWITCH, {}, {in1}, {}},
 553       {  TGSI_OPCODE_CASE, {}, {in1}, {}},
 554       {   TGSI_OPCODE_BGNLOOP },
 555       {    TGSI_OPCODE_IF, {}, {in0}, {}},
 556       {     TGSI_OPCODE_BRK},
 557       {    TGSI_OPCODE_ENDIF},
 558       {    TGSI_OPCODE_MOV, {1}, {in0}, {}},
 559       {   TGSI_OPCODE_ENDLOOP },
 560       {  TGSI_OPCODE_DEFAULT, {}, {}, {}},
 561       { TGSI_OPCODE_ENDSWITCH, {}, {}, {}},
 562       { TGSI_OPCODE_MOV, {out0}, {1}, {}},
 563       { TGSI_OPCODE_END}
 564    };
 565    run (code, expectation({{-1,-1}, {2,10}}));
 566 }
 567
 568 /* Value written conditionally in one loop and read in another loop,
 569  * and both of these loops are within yet another loop. Here the value
 570  * has to survive the outer loop.
 571  */
 572 TEST_F(LifetimeEvaluatorExactTest, LoopsWithDifferntScopesConditionalWrite)
 573 {
 574    const vector<MockCodeline> code = {
 575       { TGSI_OPCODE_BGNLOOP },
 576       {  TGSI_OPCODE_IF, {}, {in0}, {}},
 577       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
 578       {   TGSI_OPCODE_ENDIF},
 579       { TGSI_OPCODE_ENDLOOP },
 580       { TGSI_OPCODE_BGNLOOP },
 581       {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
 582       { TGSI_OPCODE_ENDLOOP },
 583       { TGSI_OPCODE_END}
 584    };
 585    run (code, expectation({{-1,-1}, {0,7}}));
 586 }
 587
 588 /* Value written and read in one loop and last read in another loop,
 589  * Here the value has to survive both loops.
 590  */
 591 TEST_F(LifetimeEvaluatorExactTest, LoopsWithDifferntScopesFirstReadBeforeWrite)
 592 {
 593    const vector<MockCodeline> code = {
 594       { TGSI_OPCODE_BGNLOOP },
 595       {   TGSI_OPCODE_MUL, {1}, {1,in0}, {}},
 596       { TGSI_OPCODE_ENDLOOP },
 597       { TGSI_OPCODE_BGNLOOP },
 598       {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
 599       { TGSI_OPCODE_ENDLOOP },
 600       { TGSI_OPCODE_END}
 601    };
 602    run (code, expectation({{-1,-1}, {0,5}}));
 603 }
 604
 605
 606 /* Value is written in one switch code path within a loop
 607  * must survive the full loop.
 608  */
 609 TEST_F(LifetimeEvaluatorExactTest, LoopWithWriteInSwitch)
 610 {
 611    const vector<MockCodeline> code = {
 612       { TGSI_OPCODE_BGNLOOP },
 613       {   TGSI_OPCODE_SWITCH, {}, {in0}, {} },
 614       {    TGSI_OPCODE_CASE, {}, {in0}, {} },
 615       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
 616       {    TGSI_OPCODE_BRK },
 617       {   TGSI_OPCODE_DEFAULT },
 618       {   TGSI_OPCODE_BRK },
 619       {   TGSI_OPCODE_ENDSWITCH },
 620       {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
 621       { TGSI_OPCODE_ENDLOOP },
 622       { TGSI_OPCODE_END}
 623    };
 624    run (code, expectation({{-1,-1}, {0,9}}));
 625 }
 626
 627 /* Value written in one case, and read in other,in loop
 628  * - must survive the loop.
 629  */
 630 TEST_F(LifetimeEvaluatorExactTest, LoopWithReadWriteInSwitchDifferentCase)
 631 {
 632    const vector<MockCodeline> code = {
 633       { TGSI_OPCODE_BGNLOOP },
 634       {   TGSI_OPCODE_SWITCH, {}, {in0}, {} },
 635       {    TGSI_OPCODE_CASE, {}, {in0}, {} },
 636       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
 637       {    TGSI_OPCODE_BRK },
 638       {   TGSI_OPCODE_DEFAULT },
 639       {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
 640       {   TGSI_OPCODE_BRK },
 641       {   TGSI_OPCODE_ENDSWITCH },
 642       { TGSI_OPCODE_ENDLOOP },
 643       { TGSI_OPCODE_END}
 644    };
 645    run (code, expectation({{-1,-1}, {0,9}}));
 646 }
 647
 648 /* Value written in one case, and read in other,in loop
 649  * - must survive the loop, even if the write case falls through.
 650  */
 651 TEST_F(LifetimeEvaluatorExactTest, LoopWithReadWriteInSwitchDifferentCaseFallThrough)
 652 {
 653    const vector<MockCodeline> code = {
 654       { TGSI_OPCODE_BGNLOOP },
 655       {   TGSI_OPCODE_SWITCH, {}, {in0}, {} },
 656       {    TGSI_OPCODE_CASE, {}, {in0}, {} },
 657       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
 658       {   TGSI_OPCODE_DEFAULT },
 659       {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
 660       {   TGSI_OPCODE_BRK },
 661       {   TGSI_OPCODE_ENDSWITCH },
 662       { TGSI_OPCODE_ENDLOOP },
 663       { TGSI_OPCODE_END}
 664    };
 665    run (code, expectation({{-1,-1}, {0,8}}));
 666 }
 667
 668
 669 /* Here we read and write from an to the same temp in the same instruction,
 670  * but the read is conditional (select operation), hence the lifetime must
 671  * start with the first write.
 672  */
 673 TEST_F(LifetimeEvaluatorExactTest, WriteSelectFromSelf)
 674 {
 675    const vector<MockCodeline> code = {
 676       {TGSI_OPCODE_USEQ, {5}, {in0,in1}, {}},
 677       {TGSI_OPCODE_UCMP, {1}, {5,in1,1}, {}},
 678       {TGSI_OPCODE_UCMP, {1}, {5,in1,1}, {}},
 679       {TGSI_OPCODE_UCMP, {1}, {5,in1,1}, {}},
 680       {TGSI_OPCODE_UCMP, {1}, {5,in1,1}, {}},
 681       {TGSI_OPCODE_FSLT, {2}, {1,in1}, {}},
 682       {TGSI_OPCODE_UIF, {}, {2}, {}},
 683       {  TGSI_OPCODE_MOV, {3}, {in1}, {}},
 684       {TGSI_OPCODE_ELSE},
 685       {  TGSI_OPCODE_MOV, {4}, {in1}, {}},
 686       {  TGSI_OPCODE_MOV, {4}, {4}, {}},
 687       {  TGSI_OPCODE_MOV, {3}, {4}, {}},
 688       {TGSI_OPCODE_ENDIF},
 689       {TGSI_OPCODE_MOV, {out1}, {3}, {}},
 690       {TGSI_OPCODE_END}
 691    };
 692    run (code, expectation({{-1,-1}, {1,5}, {5,6}, {7,13}, {9,11}, {0,4}}));
 693 }
 694
 695 /* This test checks wheter the ENDSWITCH is handled properly if the
 696  * last switch case/default doesn't stop with a BRK.
 697  */
 698 TEST_F(LifetimeEvaluatorExactTest, LoopRWInSwitchCaseLastCaseWithoutBreak)
 699 {
 700    const vector<MockCodeline> code = {
 701       { TGSI_OPCODE_BGNLOOP },
 702       {   TGSI_OPCODE_SWITCH, {}, {in0}, {} },
 703       {    TGSI_OPCODE_CASE, {}, {in0}, {} },
 704       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
 705       {    TGSI_OPCODE_BRK },
 706       {   TGSI_OPCODE_DEFAULT },
 707       {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
 708       {   TGSI_OPCODE_ENDSWITCH },
 709       { TGSI_OPCODE_ENDLOOP },
 710       { TGSI_OPCODE_END}
 711    };
 712    run (code, expectation({{-1,-1}, {0,8}}));
 713 }
 714
 715 /* Value read/write in same case, stays there */
 716 TEST_F(LifetimeEvaluatorExactTest, LoopWithReadWriteInSwitchSameCase)
 717 {
 718    const vector<MockCodeline> code = {
 719       { TGSI_OPCODE_BGNLOOP },
 720       {   TGSI_OPCODE_SWITCH, {}, {in0}, {} },
 721       {    TGSI_OPCODE_CASE, {}, {in0}, {} },
 722       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
 723       {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
 724       {    TGSI_OPCODE_BRK },
 725       {   TGSI_OPCODE_DEFAULT },
 726       {   TGSI_OPCODE_BRK },
 727       {   TGSI_OPCODE_ENDSWITCH },
 728       { TGSI_OPCODE_ENDLOOP },
 729       { TGSI_OPCODE_END}
 730    };
 731    run (code, expectation({{-1,-1}, {3,4}}));
 732 }
 733
 734 /* Value read/write in all cases, should only live from first
 735  * write to last read, but currently the whole loop is used.
 736  */
 737 TEST_F(LifetimeEvaluatorAtLeastTest, LoopWithReadWriteInSwitchSameCase)
 738 {
 739    const vector<MockCodeline> code = {
 740       { TGSI_OPCODE_BGNLOOP },
 741       {   TGSI_OPCODE_SWITCH, {}, {in0}, {}},
 742       {    TGSI_OPCODE_CASE, {}, {in0}, {} },
 743       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
 744       {    TGSI_OPCODE_BRK },
 745       {   TGSI_OPCODE_DEFAULT },
 746       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
 747       {   TGSI_OPCODE_BRK },
 748       {   TGSI_OPCODE_ENDSWITCH },
 749       {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
 750       { TGSI_OPCODE_ENDLOOP },
 751       { TGSI_OPCODE_END}
 752    };
 753    run (code, expectation({{-1,-1}, {3,9}}));
 754 }
 755
 756 /* First read before first write with nested loops */
 757 TEST_F(LifetimeEvaluatorExactTest, LoopsWithDifferentScopesCondReadBeforeWrite)
 758 {
 759    const vector<MockCodeline> code = {
 760       { TGSI_OPCODE_BGNLOOP },
 761       {   TGSI_OPCODE_BGNLOOP },
 762       {    TGSI_OPCODE_IF, {}, {in0}, {}},
 763       {     TGSI_OPCODE_MOV, {out0}, {1}, {}},
 764       {    TGSI_OPCODE_ENDIF},
 765       {   TGSI_OPCODE_ENDLOOP },
 766       {   TGSI_OPCODE_BGNLOOP },
 767       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
 768       {   TGSI_OPCODE_ENDLOOP },
 769       { TGSI_OPCODE_ENDLOOP },
 770       { TGSI_OPCODE_END}
 771    };
 772    run (code, expectation({{-1,-1}, {0,9}}));
 773 }
 774
 775 /* First read before first write wiredness with nested loops.
 776  * Here the first read of 2 is logically before the first, dominant
 777  * write, therfore, the 2 has to survive both loops.
 778  */
 779 TEST_F(LifetimeEvaluatorExactTest, FirstWriteAtferReadInNestedLoop)
 780 {
 781    const vector<MockCodeline> code = {
 782       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 783       { TGSI_OPCODE_BGNLOOP },
 784       {   TGSI_OPCODE_BGNLOOP },
 785       {     TGSI_OPCODE_MUL, {2}, {2,1}, {}},
 786       {     TGSI_OPCODE_MOV, {3}, {2}, {}},
 787       {   TGSI_OPCODE_ENDLOOP },
 788       { TGSI_OPCODE_ADD, {1}, {1,in1}, {}},
 789       { TGSI_OPCODE_ENDLOOP },
 790       { TGSI_OPCODE_MOV, {out0}, {3}, {}},
 791       { TGSI_OPCODE_END}
 792    };
 793    run (code, expectation({{-1,-1}, {0,7}, {1,7}, {4,8}}));
 794 }
 795
 796
 797 #define DST(X, W) vector<pair<int,int>>(1, make_pair(X, W))
 798 #define SRC(X, S) vector<pair<int, const char *>>(1, make_pair(X, S))
 799 #define SRC2(X, S, Y, T) vector<pair<int, const char *>>({make_pair(X, S), make_pair(Y, T)})
 800
 801 /* Partial write to components: one component was written unconditionally
 802  * but another conditionally, temporary must survive the whole loop.
 803  * Test series for all components.
 804  */
 805 TEST_F(LifetimeEvaluatorExactTest, LoopWithConditionalComponentWrite_X)
 806 {
 807    const vector<MockCodelineWithSwizzle> code = {
 808       MockCodelineWithSwizzle(TGSI_OPCODE_BGNLOOP),
 809       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(1, WRITEMASK_Y), SRC(in1, "x"), {}),
 810       MockCodelineWithSwizzle(TGSI_OPCODE_IF, {}, SRC(in0, "xxxx"), {}),
 811       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(1, WRITEMASK_X), SRC(in1, "y"), {}),
 812       MockCodelineWithSwizzle(TGSI_OPCODE_ENDIF),
 813       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(2, WRITEMASK_XY), SRC(1, "xy"), {}),
 814       MockCodelineWithSwizzle(TGSI_OPCODE_ENDLOOP),
 815       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(out0, WRITEMASK_XYZW), SRC(2, "xyxy"), {}),
 816       MockCodelineWithSwizzle(TGSI_OPCODE_END)
 817    };
 818    run (code, expectation({{-1,-1}, {0,6}, {5,7}}));
 819 }
 820
 821 TEST_F(LifetimeEvaluatorExactTest, LoopWithConditionalComponentWrite_Y)
 822 {
 823    const vector<MockCodelineWithSwizzle> code = {
 824       MockCodelineWithSwizzle(TGSI_OPCODE_BGNLOOP),
 825       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(1, WRITEMASK_X), SRC(in1, "x"), {}),
 826       MockCodelineWithSwizzle(TGSI_OPCODE_IF, {}, SRC(in0, "xxxx"), {}),
 827       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(1, WRITEMASK_Y), SRC(in1, "y"), {}),
 828       MockCodelineWithSwizzle(TGSI_OPCODE_ENDIF),
 829       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(2, WRITEMASK_XY), SRC(1, "xy"), {}),
 830       MockCodelineWithSwizzle(TGSI_OPCODE_ENDLOOP),
 831       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(out0, WRITEMASK_XYZW), SRC(2, "xyxy"), {}),
 832       MockCodelineWithSwizzle(TGSI_OPCODE_END)
 833    };
 834    run (code, expectation({{-1,-1}, {0,6}, {5,7}}));
 835 }
 836
 837 TEST_F(LifetimeEvaluatorExactTest, LoopWithConditionalComponentWrite_Z)
 838 {
 839    const vector<MockCodelineWithSwizzle> code = {
 840       MockCodelineWithSwizzle(TGSI_OPCODE_BGNLOOP),
 841       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(1, WRITEMASK_X), SRC(in1, "x"), {}),
 842       MockCodelineWithSwizzle(TGSI_OPCODE_IF, {}, SRC(in0, "xxxx"), {}),
 843       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(1, WRITEMASK_Z), SRC(in1, "y"), {}),
 844       MockCodelineWithSwizzle(TGSI_OPCODE_ENDIF),
 845       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(2, WRITEMASK_XY), SRC(1, "xz"), {}),
 846       MockCodelineWithSwizzle(TGSI_OPCODE_ENDLOOP),
 847       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(out0, WRITEMASK_XYZW), SRC(2, "xyxy"), {}),
 848       MockCodelineWithSwizzle(TGSI_OPCODE_END)
 849    };
 850    run (code, expectation({{-1,-1}, {0,6}, {5,7}}));
 851 }
 852
 853 TEST_F(LifetimeEvaluatorExactTest, LoopWithConditionalComponentWrite_W)
 854 {
 855    const vector<MockCodelineWithSwizzle> code = {
 856       MockCodelineWithSwizzle(TGSI_OPCODE_BGNLOOP),
 857       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(1, WRITEMASK_X), SRC(in1, "x"), {}),
 858       MockCodelineWithSwizzle(TGSI_OPCODE_IF, {}, SRC(in0, "xxxx"), {}),
 859       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(1, WRITEMASK_W), SRC(in1, "y"), {}),
 860       MockCodelineWithSwizzle(TGSI_OPCODE_ENDIF),
 861       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(2, WRITEMASK_XY), SRC(1, "xw"), {}),
 862       MockCodelineWithSwizzle(TGSI_OPCODE_ENDLOOP),
 863       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(out0, WRITEMASK_XYZW), SRC(2, "xyxy"), {}),
 864       MockCodelineWithSwizzle(TGSI_OPCODE_END)
 865    };
 866    run (code, expectation({{-1,-1}, {0,6}, {5,7}}));
 867 }
 868
 869 TEST_F(LifetimeEvaluatorExactTest, LoopWithConditionalComponentWrite_X_Read_Y_Before)
 870 {
 871    const vector<MockCodelineWithSwizzle> code = {
 872       MockCodelineWithSwizzle(TGSI_OPCODE_BGNLOOP),
 873       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(1, WRITEMASK_X), SRC(in1, "x"), {}),
 874       MockCodelineWithSwizzle(TGSI_OPCODE_IF, {}, SRC(in0, "xxxx"), {}),
 875       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(2, WRITEMASK_XYZW), SRC(1, "yyyy"), {}),
 876       MockCodelineWithSwizzle(TGSI_OPCODE_ENDIF),
 877       MockCodelineWithSwizzle(TGSI_OPCODE_MOV, DST(1, WRITEMASK_YZW), SRC(2, "yyzw"), {}),
 878       MockCodelineWithSwizzle(TGSI_OPCODE_ENDLOOP),
 879       MockCodelineWithSwizzle(TGSI_OPCODE_ADD, DST(out0, WRITEMASK_XYZW), SRC2(2, "yyzw", 1, "xyxy"), {}),
 880       MockCodelineWithSwizzle(TGSI_OPCODE_END)
 881    };
 882    run (code, expectation({{-1,-1}, {0,7}, {0,7}}));
 883 }
 884
 885 /* The variable is conditionally read before first written, so
 886  * it has to surive all the loops.
 887  */
 888 TEST_F(LifetimeEvaluatorExactTest, FRaWSameInstructionInLoopAndCondition)
 889 {
 890    const vector<MockCodeline> code = {
 891       { TGSI_OPCODE_BGNLOOP },
 892       {   TGSI_OPCODE_BGNLOOP },
 893       {     TGSI_OPCODE_IF, {0}, {in0}, {} },
 894       {       TGSI_OPCODE_ADD, {1}, {1,in0}, {}},
 895       {     TGSI_OPCODE_ENDIF},
 896       {     TGSI_OPCODE_MOV, {1}, {in1}, {}},
 897       {  TGSI_OPCODE_ENDLOOP },
 898       { TGSI_OPCODE_ENDLOOP },
 899       { TGSI_OPCODE_END},
 900
 901    };
 902    run (code, expectation({{-1,-1}, {0,7}}));
 903 }
 904
 905 /* If unconditionally first written and read in the same
 906  * instruction, then the register must be kept for the
 907  * one write, but not more (undefined behaviour)
 908  */
 909 TEST_F(LifetimeEvaluatorExactTest, FRaWSameInstruction)
 910 {
 911    const vector<MockCodeline> code = {
 912       { TGSI_OPCODE_ADD, {1}, {1,in0}, {}},
 913       { TGSI_OPCODE_END},
 914
 915    };
 916    run (code, expectation({{-1,-1}, {0,1}}));
 917 }
 918
 919 /* If unconditionally written and read in the same
 920  * instruction, various times then the register must be
 921  * kept past the last write, but not longer (undefined behaviour)
 922  */
 923 TEST_F(LifetimeEvaluatorExactTest, FRaWSameInstructionMoreThenOnce)
 924 {
 925    const vector<MockCodeline> code = {
 926       { TGSI_OPCODE_ADD, {1}, {1,in0}, {}},
 927       { TGSI_OPCODE_ADD, {1}, {1,in0}, {}},
 928       { TGSI_OPCODE_MOV, {out0}, {in0}, {}},
 929       { TGSI_OPCODE_END},
 930
 931    };
 932    run (code, expectation({{-1,-1}, {0,2}}));
 933 }
 934
 935 /* Register is only written. This should not happen,
 936  * but to handle the case we want the register to life
 937  * at least one instruction
 938  */
 939 TEST_F(LifetimeEvaluatorExactTest, WriteOnly)
 940 {
 941    const vector<MockCodeline> code = {
 942       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 943       { TGSI_OPCODE_END}
 944    };
 945    run (code, expectation({{-1,-1}, {0,1}}));
 946 }
 947
 948 /* Register is read in IF.
 949  */
 950 TEST_F(LifetimeEvaluatorExactTest, SimpleReadForIf)
 951 {
 952    const vector<MockCodeline> code = {
 953       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 954       { TGSI_OPCODE_ADD, {out0}, {in0,in1}, {}},
 955       { TGSI_OPCODE_IF, {}, {1}, {}},
 956       { TGSI_OPCODE_ENDIF}
 957    };
 958    run (code, expectation({{-1,-1}, {0,2}}));
 959 }
 960
 961 TEST_F(LifetimeEvaluatorExactTest, WriteTwoReadOne)
 962 {
 963    const vector<MockCodeline> code = {
 964       { TGSI_OPCODE_DFRACEXP , {1,2}, {in0}, {}},
 965       { TGSI_OPCODE_ADD , {3}, {2,in0}, {}},
 966       { TGSI_OPCODE_MOV, {out1}, {3}, {}},
 967       { TGSI_OPCODE_END},
 968    };
 969    run (code, expectation({{-1,-1}, {0,1}, {0,1}, {1,2}}));
 970 }
 971
 972 TEST_F(LifetimeEvaluatorExactTest, ReadOnly)
 973 {
 974    const vector<MockCodeline> code = {
 975       { TGSI_OPCODE_MOV, {out0}, {1}, {}},
 976       { TGSI_OPCODE_END},
 977    };
 978    run (code, expectation({{-1,-1}, {-1,-1}}));
 979 }
 980
 981
 982 /* Test handling of missing END marker
 983 */
 984 TEST_F(LifetimeEvaluatorExactTest, SomeScopesAndNoEndProgramId)
 985 {
 986    const vector<MockCodeline> code = {
 987       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
 988       { TGSI_OPCODE_IF, {}, {1}, {}},
 989       { TGSI_OPCODE_MOV, {2}, {1}, {}},
 990       { TGSI_OPCODE_ENDIF},
 991       { TGSI_OPCODE_IF, {}, {1}, {}},
 992       { TGSI_OPCODE_MOV, {out0}, {2}, {}},
 993       { TGSI_OPCODE_ENDIF},
 994    };
 995    run (code, expectation({{-1,-1}, {0,4}, {2,5}}));
 996 }
 997
 998 TEST_F(LifetimeEvaluatorExactTest, SerialReadWrite)
 999 {
1000    const vector<MockCodeline> code = {
1001       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
1002       { TGSI_OPCODE_MOV, {2}, {1}, {}},
1003       { TGSI_OPCODE_MOV, {3}, {2}, {}},
1004       { TGSI_OPCODE_MOV, {out0}, {3}, {}},
1005       { TGSI_OPCODE_END},
1006    };
1007    run (code, expectation({{-1,-1}, {0,1}, {1,2}, {2,3}}));
1008 }
1009
1010 /* Check that two destination registers are used */
1011 TEST_F(LifetimeEvaluatorExactTest, TwoDestRegisters)
1012 {
1013    const vector<MockCodeline> code = {
1014       { TGSI_OPCODE_DFRACEXP , {1,2}, {in0}, {}},
1015       { TGSI_OPCODE_ADD, {out0}, {1,2}, {}},
1016       { TGSI_OPCODE_END}
1017    };
1018    run (code, expectation({{-1,-1}, {0,1}, {0,1}}));
1019 }
1020
1021 /* Check that writing within a loop in a conditional is propagated
1022  * to the outer loop.
1023  */
1024 TEST_F(LifetimeEvaluatorExactTest, WriteInLoopInConditionalReadOutside)
1025 {
1026    const vector<MockCodeline> code = {
1027       { TGSI_OPCODE_BGNLOOP},
1028       {   TGSI_OPCODE_IF, {}, {in0}, {}},
1029       {     TGSI_OPCODE_BGNLOOP},
1030       {       TGSI_OPCODE_MOV, {1}, {in1}, {}},
1031       {     TGSI_OPCODE_ENDLOOP},
1032       {   TGSI_OPCODE_ENDIF},
1033       {   TGSI_OPCODE_ADD, {2}, {1,in1}, {}},
1034       { TGSI_OPCODE_ENDLOOP},
1035       { TGSI_OPCODE_MOV, {out0}, {2}, {}},
1036       { TGSI_OPCODE_END}
1037    };
1038    run (code, expectation({{-1,-1}, {0,7}, {6,8}}));
1039 }
1040
1041 /* Check that a register written in a loop that is inside a conditional
1042  * is not propagated past that loop if last read is also within the
1043  * conditional
1044 */
1045 TEST_F(LifetimeEvaluatorExactTest, WriteInLoopInCondReadInCondOutsideLoop)
1046 {
1047    const vector<MockCodeline> code = {
1048       { TGSI_OPCODE_BGNLOOP},
1049       {   TGSI_OPCODE_IF, {}, {in0}, {}},
1050       {     TGSI_OPCODE_BGNLOOP},
1051       {       TGSI_OPCODE_MUL, {1}, {in2,in1}, {}},
1052       {     TGSI_OPCODE_ENDLOOP},
1053       {     TGSI_OPCODE_ADD, {2}, {1,in1}, {}},
1054       {   TGSI_OPCODE_ENDIF},
1055       { TGSI_OPCODE_ENDLOOP},
1056       { TGSI_OPCODE_MOV, {out0}, {2}, {}},
1057       { TGSI_OPCODE_END}
1058    };
1059    run (code, expectation({{-1,-1}, {3,5}, {0,8}}));
1060 }
1061
1062 /* Check that a register read before written in a loop that is
1063  * inside a conditional is propagated to the outer loop.
1064  */
1065 TEST_F(LifetimeEvaluatorExactTest, ReadWriteInLoopInCondReadInCondOutsideLoop)
1066 {
1067    const vector<MockCodeline> code = {
1068       { TGSI_OPCODE_BGNLOOP},
1069       {   TGSI_OPCODE_IF, {}, {in0}, {}},
1070       {     TGSI_OPCODE_BGNLOOP},
1071       {       TGSI_OPCODE_MUL, {1}, {1,in1}, {}},
1072       {     TGSI_OPCODE_ENDLOOP},
1073       {     TGSI_OPCODE_ADD, {2}, {1,in1}, {}},
1074       {   TGSI_OPCODE_ENDIF},
1075       { TGSI_OPCODE_ENDLOOP},
1076       { TGSI_OPCODE_MOV, {out0}, {2}, {}},
1077       { TGSI_OPCODE_END}
1078    };
1079    run (code, expectation({{-1,-1}, {0,7}, {0,8}}));
1080 }
1081
1082 /* With two destinations if one value is thrown away, we must
1083  * ensure that the two output registers don't merge. In this test
1084  * case the last access for 2 and 3 is in line 4, but 4 can only
1085  * be merged with 3 because it is read,2 on the other hand is written
1086  * to, and merging it with 4 would result in a bug.
1087  */
1088 TEST_F(LifetimeEvaluatorExactTest, WritePastLastRead2)
1089 {
1090    const vector<MockCodeline> code = {
1091       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
1092       { TGSI_OPCODE_MOV, {2}, {in0}, {}},
1093       { TGSI_OPCODE_ADD, {3}, {1,2}, {}},
1094       { TGSI_OPCODE_DFRACEXP , {2,4}, {3}, {}},
1095       { TGSI_OPCODE_MOV, {out1}, {4}, {}},
1096       { TGSI_OPCODE_END}
1097    };
1098    run (code, expectation({{-1,-1}, {0,2}, {1,4}, {2,3}, {3,4}}));
1099 }
1100
1101 /* Check that three source registers are used */
1102 TEST_F(LifetimeEvaluatorExactTest, ThreeSourceRegisters)
1103 {
1104    const vector<MockCodeline> code = {
1105       { TGSI_OPCODE_DFRACEXP , {1,2}, {in0}, {}},
1106       { TGSI_OPCODE_ADD , {3}, {in0,in1}, {}},
1107       { TGSI_OPCODE_MAD, {out0}, {1,2,3}, {}},
1108       { TGSI_OPCODE_END}
1109    };
1110    run (code, expectation({{-1,-1}, {0,2}, {0,2}, {1,2}}));
1111 }
1112
1113 /* Check minimal lifetime for registers only written to */
1114 TEST_F(LifetimeEvaluatorExactTest, OverwriteWrittenOnlyTemps)
1115 {
1116    const vector<MockCodeline> code = {
1117       { TGSI_OPCODE_MOV , {1}, {in0}, {}},
1118       { TGSI_OPCODE_MOV , {2}, {in1}, {}},
1119       { TGSI_OPCODE_END}
1120    };
1121    run (code, expectation({{-1,-1}, {0,1}, {1,2}}));
1122 }
1123
1124 /* Same register is only written twice. This should not happen,
1125  * but to handle the case we want the register to life
1126  * at least past the last write instruction
1127  */
1128 TEST_F(LifetimeEvaluatorExactTest, WriteOnlyTwiceSame)
1129 {
1130    const vector<MockCodeline> code = {
1131       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
1132       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
1133       { TGSI_OPCODE_END}
1134    };
1135    run (code, expectation({{-1,-1}, {0,2}}));
1136 }
1137
1138 /* Dead code elimination should catch and remove the case
1139  * when a variable is written after its last read, but
1140  * we want the code to be aware of this case.
1141  * The life time of this uselessly written variable is set
1142  * to the instruction after the write, because
1143  * otherwise it could be re-used too early.
1144  */
1145 TEST_F(LifetimeEvaluatorExactTest, WritePastLastRead)
1146 {
1147    const vector<MockCodeline> code = {
1148       { TGSI_OPCODE_MOV, {1}, {in0}, {}},
1149       { TGSI_OPCODE_MOV, {2}, {1}, {}},
1150       { TGSI_OPCODE_MOV, {1}, {2}, {}},
1151       { TGSI_OPCODE_END},
1152
1153    };
1154    run (code, expectation({{-1,-1}, {0,3}, {1,2}}));
1155 }
1156
1157 /* If a break is in the loop, all variables written after the
1158  * break and used outside the loop the variable must survive the
1159  * outer loop
1160  */
1161 TEST_F(LifetimeEvaluatorExactTest, NestedLoopWithWriteAfterBreak)
1162 {
1163    const vector<MockCodeline> code = {
1164       { TGSI_OPCODE_BGNLOOP },
1165       {   TGSI_OPCODE_BGNLOOP },
1166       {     TGSI_OPCODE_IF, {}, {in0}, {}},
1167       {       TGSI_OPCODE_BRK},
1168       {     TGSI_OPCODE_ENDIF},
1169       {     TGSI_OPCODE_MOV, {1}, {in0}, {}},
1170       {   TGSI_OPCODE_ENDLOOP },
1171       {   TGSI_OPCODE_MOV, {out0}, {1}, {}},
1172       { TGSI_OPCODE_ENDLOOP },
1173       { TGSI_OPCODE_END}
1174    };
1175    run (code, expectation({{-1,-1}, {0,8}}));
1176 }
1177
1178 /* Implementation of helper and test classes */
1179 MockShader::~MockShader()
1180 {
1181    free();
1182    ralloc_free(mem_ctx);
1183 }
1184
1185 MockShader::MockShader(const vector<MockCodelineWithSwizzle>& source):
1186    num_temps(0)
1187 {
1188    mem_ctx = ralloc_context(NULL);
1189
1190    program = new(mem_ctx) exec_list();
1191
1192    for (MockCodelineWithSwizzle i: source) {
1193       glsl_to_tgsi_instruction *next_instr = new(mem_ctx) glsl_to_tgsi_instruction();
1194       next_instr->op = i.op;
1195       next_instr->info = tgsi_get_opcode_info(i.op);
1196
1197       assert(i.src.size() < 4);
1198       assert(i.dst.size() < 3);
1199       assert(i.tex_offsets.size() < 3);
1200
1201       for (unsigned k = 0; k < i.src.size(); ++k) {
1202          next_instr->src[k] = create_src_register(i.src[k].first, i.src[k].second);
1203       }
1204       for (unsigned k = 0; k < i.dst.size(); ++k) {
1205          next_instr->dst[k] = create_dst_register(i.dst[k].first, i.dst[k].second);
1206       }
1207       next_instr->tex_offset_num_offset = i.tex_offsets.size();
1208       next_instr->tex_offsets = new st_src_reg[i.tex_offsets.size()];
1209       for (unsigned k = 0; k < i.tex_offsets.size(); ++k) {
1210          next_instr->tex_offsets[k] = create_src_register(i.tex_offsets[k].first,
1211                                                           i.tex_offsets[k].second);
1212       }
1213       program->push_tail(next_instr);
1214    }
1215    ++num_temps;
1216 }
1217
1218 MockShader::MockShader(const vector<MockCodeline>& source):
1219    num_temps(0)
1220 {
1221    mem_ctx = ralloc_context(NULL);
1222
1223    program = new(mem_ctx) exec_list();
1224
1225    for (MockCodeline i: source) {
1226       glsl_to_tgsi_instruction *next_instr = new(mem_ctx) glsl_to_tgsi_instruction();
1227       next_instr->op = i.op;
1228       next_instr->info = tgsi_get_opcode_info(i.op);
1229
1230       assert(i.src.size() < 4);
1231       assert(i.dst.size() < 3);
1232       assert(i.tex_offsets.size() < 3);
1233
1234       for (unsigned k = 0; k < i.src.size(); ++k) {
1235          next_instr->src[k] = create_src_register(i.src[k]);
1236       }
1237       for (unsigned k = 0; k < i.dst.size(); ++k) {
1238          next_instr->dst[k] = create_dst_register(i.dst[k]);
1239       }
1240       next_instr->tex_offset_num_offset = i.tex_offsets.size();
1241       next_instr->tex_offsets = new st_src_reg[i.tex_offsets.size()];
1242       for (unsigned k = 0; k < i.tex_offsets.size(); ++k) {
1243          next_instr->tex_offsets[k] = create_src_register(i.tex_offsets[k]);
1244       }
1245       program->push_tail(next_instr);
1246    }
1247    ++num_temps;
1248 }
1249
1250 int MockShader::get_num_temps() const
1251 {
1252    return num_temps;
1253 }
1254
1255
1256 exec_list* MockShader::get_program() const
1257 {
1258    return program;
1259 }
1260
1261 void MockShader::free()
1262 {
1263    /* The list is not fully initialized, so
1264     * tearing it down also must be done manually. */
1265    exec_node *p;
1266    while ((p = program->pop_head())) {
1267       glsl_to_tgsi_instruction * instr = static_cast<glsl_to_tgsi_instruction *>(p);
1268       if (instr->tex_offset_num_offset > 0)
1269          delete[] instr->tex_offsets;
1270       delete p;
1271    }
1272    program = 0;
1273    num_temps = 0;
1274 }
1275
1276 st_src_reg MockShader::create_src_register(int src_idx)
1277 {
1278    gl_register_file file;
1279    int idx = 0;
1280    if (src_idx >= 0) {
1281       file = PROGRAM_TEMPORARY;
1282       idx = src_idx;
1283       if (num_temps < idx)
1284          num_temps = idx;
1285    } else {
1286       file = PROGRAM_INPUT;
1287       idx = 1 - src_idx;
1288    }
1289    return st_src_reg(file, idx, GLSL_TYPE_INT);
1290 }
1291
1292 st_src_reg MockShader::create_src_register(int src_idx, const char *sw)
1293 {
1294    uint16_t swizzle = 0;
1295    for (int i = 0; i < 4; ++i) {
1296       switch (sw[i]) {
1297       case 'x': break; /* is zero */
1298       case 'y': swizzle |= SWIZZLE_Y << 3 * i; break;
1299       case 'z': swizzle |= SWIZZLE_Z << 3 * i; break;
1300       case 'w': swizzle |= SWIZZLE_W << 3 * i; break;
1301       }
1302    }
1303
1304    gl_register_file file;
1305    int idx = 0;
1306    if (src_idx >= 0) {
1307       file = PROGRAM_TEMPORARY;
1308       idx = src_idx;
1309       if (num_temps < idx)
1310          num_temps = idx;
1311    } else {
1312       file = PROGRAM_INPUT;
1313       idx = 1 - src_idx;
1314    }
1315    st_src_reg result(file, idx, GLSL_TYPE_INT);
1316    result.swizzle = swizzle;
1317    return result;
1318 }
1319
1320 st_dst_reg MockShader::create_dst_register(int dst_idx,int writemask)
1321 {
1322    gl_register_file file;
1323    int idx = 0;
1324    if (dst_idx >= 0) {
1325       file = PROGRAM_TEMPORARY;
1326       idx = dst_idx;
1327       if (num_temps < idx)
1328          num_temps = idx;
1329    } else {
1330       file = PROGRAM_OUTPUT;
1331       idx = 1 - dst_idx;
1332    }
1333    return st_dst_reg(file, writemask, GLSL_TYPE_INT, idx);
1334 }
1335
1336 st_dst_reg MockShader::create_dst_register(int dst_idx)
1337 {
1338    gl_register_file file;
1339    int idx = 0;
1340    if (dst_idx >= 0) {
1341       file = PROGRAM_TEMPORARY;
1342       idx = dst_idx;
1343       if (num_temps < idx)
1344          num_temps = idx;
1345    } else {
1346       file = PROGRAM_OUTPUT;
1347       idx = 1 - dst_idx;
1348    }
1349    return st_dst_reg(file,0xF, GLSL_TYPE_INT, idx);
1350 }
1351
1352
1353 void MesaTestWithMemCtx::SetUp()
1354 {
1355    mem_ctx = ralloc_context(nullptr);
1356 }
1357
1358 void MesaTestWithMemCtx::TearDown()
1359 {
1360    ralloc_free(mem_ctx);
1361    mem_ctx = nullptr;
1362 }
1363
1364 void LifetimeEvaluatorTest::run(const vector<MockCodeline>& code, const expectation& e)
1365 {
1366    MockShader shader(code);
1367    std::vector<lifetime> result(shader.get_num_temps());
1368
1369    bool success =
1370          get_temp_registers_required_lifetimes(mem_ctx, shader.get_program(),
1371                                                shader.get_num_temps(), &result[0]);
1372
1373    ASSERT_TRUE(success);
1374    ASSERT_EQ(result.size(), e.size());
1375    check(result, e);
1376 }
1377
1378 void LifetimeEvaluatorTest::run(const vector<MockCodelineWithSwizzle>& code,
1379                                 const expectation& e)
1380 {
1381    MockShader shader(code);
1382    std::vector<lifetime> result(shader.get_num_temps());
1383
1384    bool success =
1385          get_temp_registers_required_lifetimes(mem_ctx, shader.get_program(),
1386                                                shader.get_num_temps(), &result[0]);
1387    ASSERT_TRUE(success);
1388    ASSERT_EQ(result.size(), e.size());
1389    check(result, e);
1390 }
1391
1392 void LifetimeEvaluatorExactTest::check( const vector<lifetime>& lifetimes,
1393                                         const expectation& e)
1394 {
1395    for (unsigned i = 1; i < lifetimes.size(); ++i) {
1396       EXPECT_EQ(lifetimes[i].begin, e[i][0]);
1397       EXPECT_EQ(lifetimes[i].end, e[i][1]);
1398    }
1399 }
1400
1401 void LifetimeEvaluatorAtLeastTest::check( const vector<lifetime>& lifetimes,
1402                                           const expectation& e)
1403 {
1404    for (unsigned i = 1; i < lifetimes.size(); ++i) {
1405       EXPECT_LE(lifetimes[i].begin, e[i][0]);
1406       EXPECT_GE(lifetimes[i].end, e[i][1]);
1407    }
1408 }
1409
1410 void RegisterRemappingTest::run(const vector<lifetime>& lt,
1411                             const vector<int>& expect)
1412 {
1413    rename_reg_pair proto{false,0};
1414    vector<rename_reg_pair> result(lt.size(), proto);
1415
1416    get_temp_registers_remapping(mem_ctx, lt.size(), &lt[0], &result[0]);
1417
1418    vector<int> remap(lt.size());
1419    for (unsigned i = 0; i < lt.size(); ++i) {
1420       remap[i] = result[i].valid ? result[i].new_reg : i;
1421    }
1422
1423    std::transform(remap.begin(), remap.end(), result.begin(), remap.begin(),
1424                   [](int x, const rename_reg_pair& rn) {
1425                      return rn.valid ? rn.new_reg : x;
1426                   });
1427
1428    for(unsigned i = 1; i < remap.size(); ++i) {
1429       EXPECT_EQ(remap[i], expect[i]);
1430    }
1431 }