1 /*
2 * Copyright © 2022 Intel Corporation
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 #include "util/hash_table.h"
24 #include <gtest/gtest.h>
25 #include "nir.h"
26 #include "nir_builder.h"
27
28 class nir_loop_analyze_test : public ::testing::Test {
29 protected:
30 nir_loop_analyze_test();
31 ~nir_loop_analyze_test();
32
33 nir_builder b;
34 };
35
nir_loop_analyze_test()36 nir_loop_analyze_test::nir_loop_analyze_test()
37 {
38 glsl_type_singleton_init_or_ref();
39
40 static nir_shader_compiler_options options = { };
41
42 options.max_unroll_iterations = 32;
43
44 b = nir_builder_init_simple_shader(MESA_SHADER_VERTEX, &options,
45 "loop analyze");
46 }
47
~nir_loop_analyze_test()48 nir_loop_analyze_test::~nir_loop_analyze_test()
49 {
50 ralloc_free(b.shader);
51 glsl_type_singleton_decref();
52 }
53
54 struct loop_builder_param {
55 uint32_t init_value;
56 uint32_t cond_value;
57 uint32_t incr_value;
58 nir_def *(*cond_instr)(nir_builder *,
59 nir_def *,
60 nir_def *);
61 nir_def *(*incr_instr)(nir_builder *,
62 nir_def *,
63 nir_def *);
64 bool use_unknown_init_value;
65 bool invert_exit_condition_and_continue_branch;
66 };
67
68 static nir_loop *
loop_builder(nir_builder * b,loop_builder_param p)69 loop_builder(nir_builder *b, loop_builder_param p)
70 {
71 /* Create IR:
72 *
73 * auto i = init_value;
74 * while (true) {
75 * if (cond_instr(i, cond_value))
76 * break;
77 *
78 * i = incr_instr(i, incr_value);
79 * }
80 */
81 nir_def *ssa_0;
82 if (p.use_unknown_init_value) {
83 nir_def *one = nir_imm_int(b, 1);
84 nir_def *twelve = nir_imm_int(b, 12);
85 ssa_0 = nir_load_ubo(b, 1, 32, one, twelve, (gl_access_qualifier)0, 0, 0, 0, 16);
86 } else
87 ssa_0 = nir_imm_int(b, p.init_value);
88
89 nir_def *ssa_1 = nir_imm_int(b, p.cond_value);
90 nir_def *ssa_2 = nir_imm_int(b, p.incr_value);
91
92 nir_phi_instr *const phi = nir_phi_instr_create(b->shader);
93
94 nir_loop *loop = nir_push_loop(b);
95 {
96 nir_def_init(&phi->instr, &phi->def, ssa_0->num_components,
97 ssa_0->bit_size);
98
99 nir_phi_instr_add_src(phi, ssa_0->parent_instr->block, ssa_0);
100
101 nir_def *ssa_5 = &phi->def;
102 nir_def *ssa_3 = p.cond_instr(b, ssa_5, ssa_1);
103
104 if (p.invert_exit_condition_and_continue_branch)
105 ssa_3 = nir_inot(b, ssa_3);
106
107 nir_if *nif = nir_push_if(b, ssa_3);
108 {
109 if (p.invert_exit_condition_and_continue_branch)
110 nir_push_else(b, NULL);
111
112 nir_jump_instr *jump = nir_jump_instr_create(b->shader, nir_jump_break);
113 nir_builder_instr_insert(b, &jump->instr);
114 }
115 nir_pop_if(b, nif);
116
117 nir_def *ssa_4 = p.incr_instr(b, ssa_5, ssa_2);
118
119 nir_phi_instr_add_src(phi, ssa_4->parent_instr->block, ssa_4);
120 }
121 nir_pop_loop(b, loop);
122
123 b->cursor = nir_before_block(nir_loop_first_block(loop));
124 nir_builder_instr_insert(b, &phi->instr);
125
126 return loop;
127 }
128
129 struct loop_builder_invert_param {
130 uint32_t init_value;
131 uint32_t incr_value;
132 uint32_t cond_value;
133 nir_def *(*cond_instr)(nir_builder *,
134 nir_def *,
135 nir_def *);
136 nir_def *(*incr_instr)(nir_builder *,
137 nir_def *,
138 nir_def *);
139 };
140
141 /**
142 * Build an "inverted" loop.
143 *
144 * Like \c loop_builder, but the exit condition for the loop is at the bottom
145 * of the loop instead of the top. In compiler literature, the optimization
146 * that moves the exit condition from the top to the bottom is called "loop
147 * inversion," hence the name of this function.
148 */
149 static nir_loop *
loop_builder_invert(nir_builder * b,loop_builder_invert_param p)150 loop_builder_invert(nir_builder *b, loop_builder_invert_param p)
151 {
152 /* Create IR:
153 *
154 * auto i = init_value;
155 * while (true) {
156 * i = incr_instr(i, incr_value);
157 *
158 * if (cond_instr(i, cond_value))
159 * break;
160 * }
161 */
162 nir_def *ssa_0 = nir_imm_int(b, p.init_value);
163 nir_def *ssa_1 = nir_imm_int(b, p.incr_value);
164 nir_def *ssa_2 = nir_imm_int(b, p.cond_value);
165
166 nir_phi_instr *const phi = nir_phi_instr_create(b->shader);
167
168 nir_loop *loop = nir_push_loop(b);
169 {
170 nir_def_init(&phi->instr, &phi->def, ssa_0->num_components,
171 ssa_0->bit_size);
172
173 nir_phi_instr_add_src(phi, ssa_0->parent_instr->block, ssa_0);
174
175 nir_def *ssa_5 = &phi->def;
176
177 nir_def *ssa_3 = p.incr_instr(b, ssa_5, ssa_1);
178
179 nir_def *ssa_4 = p.cond_instr(b, ssa_3, ssa_2);
180
181 nir_if *nif = nir_push_if(b, ssa_4);
182 {
183 nir_jump_instr *jump = nir_jump_instr_create(b->shader, nir_jump_break);
184 nir_builder_instr_insert(b, &jump->instr);
185 }
186 nir_pop_if(b, nif);
187
188 nir_phi_instr_add_src(phi, nir_cursor_current_block(b->cursor), ssa_3);
189 }
190 nir_pop_loop(b, loop);
191
192 b->cursor = nir_before_block(nir_loop_first_block(loop));
193 nir_builder_instr_insert(b, &phi->instr);
194
195 return loop;
196 }
197
TEST_F(nir_loop_analyze_test,one_iteration_fneu)198 TEST_F(nir_loop_analyze_test, one_iteration_fneu)
199 {
200 /* Create IR:
201 *
202 * float i = uintBitsToFloat(0xe7000000);
203 * while (true) {
204 * if (i != uintBitsToFloat(0xe7000000))
205 * break;
206 *
207 * i = i + uintBitsToFloat(0x5b000000);
208 * }
209 *
210 * Going towards smaller magnitude (i.e., adding a small positive value to
211 * a large negative value) requires a smaller delta to make a difference
212 * than going towards a larger magnitude. For this reason, ssa_0 + ssa_1 !=
213 * ssa_0, but ssa_0 - ssa_1 == ssa_0. Math class is tough.
214 */
215 nir_loop *loop =
216 loop_builder(&b, {.init_value = 0xe7000000, .cond_value = 0xe7000000,
217 .incr_value = 0x5b000000,
218 .cond_instr = nir_fneu, .incr_instr = nir_fadd,
219 .use_unknown_init_value = false,
220 .invert_exit_condition_and_continue_branch = false});
221
222 /* At this point, we should have:
223 *
224 * impl main {
225 * block block_0:
226 * // preds:
227 * vec1 32 ssa_0 = load_const (0xe7000000 = -604462909807314587353088.0)
228 * vec1 32 ssa_1 = load_const (0xe7000000 = -604462909807314587353088.0)
229 * vec1 32 ssa_2 = load_const (0x5b000000 = 36028797018963968.0)
230 * // succs: block_1
231 * loop {
232 * block block_1:
233 * // preds: block_0 block_4
234 * vec1 32 ssa_5 = phi block_0: ssa_0, block_4: ssa_4
235 * vec1 1 ssa_3 = fneu ssa_5, ssa_1
236 * // succs: block_2 block_3
237 * if ssa_3 {
238 * block block_2:
239 * // preds: block_1
240 * break
241 * // succs: block_5
242 * } else {
243 * block block_3:
244 * // preds: block_1
245 * // succs: block_4
246 * }
247 * block block_4:
248 * // preds: block_3
249 * vec1 32 ssa_4 = fadd ssa_5, ssa_2
250 * // succs: block_1
251 * }
252 * block block_5:
253 * // preds: block_2
254 * // succs: block_6
255 * block block_6:
256 * }
257 */
258 nir_validate_shader(b.shader, "input");
259
260 nir_loop_analyze_impl(b.impl, nir_var_all, false);
261
262 ASSERT_NE((void *)0, loop->info);
263 EXPECT_EQ(1, loop->info->max_trip_count);
264 EXPECT_TRUE(loop->info->exact_trip_count_known);
265
266 /* Loop should have an induction variable for ssa_5 and ssa_4. */
267 ASSERT_NE((void *)0, loop->info->induction_vars);
268 EXPECT_EQ(2, _mesa_hash_table_num_entries(loop->info->induction_vars));
269
270 /* The basis and def fields should not be NULL. The init_src field should
271 * point to a load_const. The update_src field should point to a load_const.
272 */
273 hash_table_foreach(loop->info->induction_vars, entry) {
274 nir_loop_induction_variable *ivar = (nir_loop_induction_variable *)entry->data;
275 EXPECT_NE((void *)0, ivar->basis);
276 EXPECT_NE((void *)0, ivar->def);
277 ASSERT_NE((void *)0, ivar->init_src);
278 EXPECT_TRUE(nir_src_is_const(*ivar->init_src));
279 ASSERT_NE((void *)0, ivar->update_src);
280 EXPECT_TRUE(nir_src_is_const(ivar->update_src->src));
281 }
282 }
283
284 #define COMPARE_REVERSE(comp) \
285 static nir_def * \
286 nir_ ## comp ## _rev(nir_builder *b, nir_def *x, nir_def *y) \
287 { \
288 return nir_ ## comp (b, y, x); \
289 }
290
291 COMPARE_REVERSE(ilt)
292 COMPARE_REVERSE(ige)
293 COMPARE_REVERSE(ult)
294 COMPARE_REVERSE(uge)
295 COMPARE_REVERSE(ishl)
296
297 #define INOT_COMPARE(comp) \
298 static nir_def * \
299 nir_inot_ ## comp (nir_builder *b, nir_def *x, nir_def *y) \
300 { \
301 return nir_inot(b, nir_ ## comp (b, x, y)); \
302 }
303
304 INOT_COMPARE(ilt_rev)
305 INOT_COMPARE(ine)
306 INOT_COMPARE(uge_rev)
307
308 #define CMP_MIN(cmp, min) \
309 static nir_def *nir_##cmp##_##min(nir_builder *b, nir_def *counter, nir_def *limit) \
310 { \
311 nir_def *unk = nir_load_vertex_id(b); \
312 return nir_##cmp(b, counter, nir_##min(b, limit, unk)); \
313 }
314
315 #define CMP_MIN_REV(cmp, min) \
316 static nir_def *nir_##cmp##_##min##_rev(nir_builder *b, nir_def *counter, nir_def *limit) \
317 { \
318 nir_def *unk = nir_load_vertex_id(b); \
319 return nir_##cmp(b, nir_##min(b, limit, unk), counter); \
320 }
321
322 CMP_MIN(ige, imin)
323 CMP_MIN_REV(ige, imin)
324 CMP_MIN(uge, umin)
325 CMP_MIN(ige, fmin)
326 CMP_MIN(uge, imin)
327 CMP_MIN(ilt, imin)
328 CMP_MIN(ilt, imax)
329 CMP_MIN_REV(ilt, imin)
330 INOT_COMPARE(ilt_imin_rev)
331
332 #define KNOWN_COUNT_TEST(_init_value, _cond_value, _incr_value, cond, incr, count) \
333 TEST_F(nir_loop_analyze_test, incr##_##cond##_known_count_##count) \
334 { \
335 nir_loop *loop = \
336 loop_builder(&b, { .init_value = _init_value, \
337 .cond_value = _cond_value, \
338 .incr_value = _incr_value, \
339 .cond_instr = nir_##cond, \
340 .incr_instr = nir_##incr, \
341 .use_unknown_init_value = false, \
342 .invert_exit_condition_and_continue_branch = false }); \
343 \
344 nir_validate_shader(b.shader, "input"); \
345 \
346 nir_loop_analyze_impl(b.impl, nir_var_all, false); \
347 \
348 ASSERT_NE((void *)0, loop->info); \
349 EXPECT_NE((void *)0, loop->info->limiting_terminator); \
350 EXPECT_EQ(count, loop->info->max_trip_count); \
351 EXPECT_TRUE(loop->info->exact_trip_count_known); \
352 \
353 ASSERT_NE((void *)0, loop->info->induction_vars); \
354 EXPECT_EQ(2, _mesa_hash_table_num_entries(loop->info->induction_vars)); \
355 \
356 hash_table_foreach(loop->info->induction_vars, entry) { \
357 nir_loop_induction_variable *ivar = (nir_loop_induction_variable *)entry->data; \
358 EXPECT_NE((void *)0, ivar->basis); \
359 EXPECT_NE((void *)0, ivar->def); \
360 ASSERT_NE((void *)0, ivar->init_src); \
361 EXPECT_TRUE(nir_src_is_const(*ivar->init_src)); \
362 ASSERT_NE((void *)0, ivar->update_src); \
363 EXPECT_TRUE(nir_src_is_const(ivar->update_src->src)); \
364 } \
365 }
366
367 #define INEXACT_COUNT_TEST_UNKNOWN_INIT(_cond_value, _incr_value, cond, incr, count, invert) \
368 TEST_F(nir_loop_analyze_test, incr##_##cond##_inexact_count_##count##_invert_##invert) \
369 { \
370 nir_loop *loop = \
371 loop_builder(&b, { .init_value = 0, \
372 .cond_value = _cond_value, \
373 .incr_value = _incr_value, \
374 .cond_instr = nir_##cond, \
375 .incr_instr = nir_##incr, \
376 .use_unknown_init_value = true, \
377 .invert_exit_condition_and_continue_branch = invert }); \
378 \
379 nir_validate_shader(b.shader, "input"); \
380 \
381 nir_loop_analyze_impl(b.impl, nir_var_all, false); \
382 \
383 ASSERT_NE((void *)0, loop->info); \
384 EXPECT_NE((void *)0, loop->info->limiting_terminator); \
385 EXPECT_EQ(count, loop->info->max_trip_count); \
386 EXPECT_FALSE(loop->info->exact_trip_count_known); \
387 \
388 ASSERT_NE((void *)0, loop->info->induction_vars); \
389 EXPECT_EQ(2, _mesa_hash_table_num_entries(loop->info->induction_vars)); \
390 \
391 hash_table_foreach(loop->info->induction_vars, entry) { \
392 nir_loop_induction_variable *ivar = (nir_loop_induction_variable *)entry->data; \
393 EXPECT_NE((void *)0, ivar->basis); \
394 EXPECT_NE((void *)0, ivar->def); \
395 ASSERT_NE((void *)0, ivar->init_src); \
396 EXPECT_FALSE(nir_src_is_const(*ivar->init_src)); \
397 ASSERT_NE((void *)0, ivar->update_src); \
398 EXPECT_TRUE(nir_src_is_const(ivar->update_src->src)); \
399 } \
400 }
401
402 #define INEXACT_COUNT_TEST(_init_value, _cond_value, _incr_value, cond, incr, count) \
403 TEST_F(nir_loop_analyze_test, incr##_##cond##_inexact_count_##count) \
404 { \
405 nir_loop *loop = \
406 loop_builder(&b, { .init_value = _init_value, \
407 .cond_value = _cond_value, \
408 .incr_value = _incr_value, \
409 .cond_instr = nir_##cond, \
410 .incr_instr = nir_##incr, \
411 .use_unknown_init_value = false, \
412 .invert_exit_condition_and_continue_branch = false }); \
413 \
414 nir_validate_shader(b.shader, "input"); \
415 \
416 nir_loop_analyze_impl(b.impl, nir_var_all, false); \
417 \
418 ASSERT_NE((void *)0, loop->info); \
419 EXPECT_NE((void *)0, loop->info->limiting_terminator); \
420 EXPECT_EQ(count, loop->info->max_trip_count); \
421 EXPECT_FALSE(loop->info->exact_trip_count_known); \
422 \
423 ASSERT_NE((void *)0, loop->info->induction_vars); \
424 EXPECT_EQ(2, _mesa_hash_table_num_entries(loop->info->induction_vars)); \
425 \
426 hash_table_foreach(loop->info->induction_vars, entry) { \
427 nir_loop_induction_variable *ivar = (nir_loop_induction_variable *)entry->data; \
428 EXPECT_NE((void *)0, ivar->basis); \
429 EXPECT_NE((void *)0, ivar->def); \
430 ASSERT_NE((void *)0, ivar->init_src); \
431 EXPECT_TRUE(nir_src_is_const(*ivar->init_src)); \
432 ASSERT_NE((void *)0, ivar->update_src); \
433 EXPECT_TRUE(nir_src_is_const(ivar->update_src->src)); \
434 } \
435 }
436
437 #define UNKNOWN_COUNT_TEST(_init_value, _cond_value, _incr_value, cond, incr) \
438 TEST_F(nir_loop_analyze_test, incr ## _ ## cond ## _unknown_count) \
439 { \
440 nir_loop *loop = \
441 loop_builder(&b, {.init_value = _init_value, \
442 .cond_value = _cond_value, \
443 .incr_value = _incr_value, \
444 .cond_instr = nir_ ## cond, \
445 .incr_instr = nir_ ## incr, \
446 .use_unknown_init_value = false, \
447 .invert_exit_condition_and_continue_branch = false}); \
448 \
449 nir_validate_shader(b.shader, "input"); \
450 \
451 nir_loop_analyze_impl(b.impl, nir_var_all, false); \
452 \
453 ASSERT_NE((void *)0, loop->info); \
454 EXPECT_EQ((void *)0, loop->info->limiting_terminator); \
455 EXPECT_EQ(0, loop->info->max_trip_count); \
456 EXPECT_FALSE(loop->info->exact_trip_count_known); \
457 }
458
459 #define INFINITE_LOOP_UNKNOWN_COUNT_TEST(_init_value, _cond_value, _incr_value, cond, incr) \
460 TEST_F(nir_loop_analyze_test, incr ## _ ## cond ## _infinite_loop_unknown_count) \
461 { \
462 nir_loop *loop = \
463 loop_builder(&b, {.init_value = _init_value, \
464 .cond_value = _cond_value, \
465 .incr_value = _incr_value, \
466 .cond_instr = nir_ ## cond, \
467 .incr_instr = nir_ ## incr, \
468 .use_unknown_init_value = false, \
469 .invert_exit_condition_and_continue_branch = false}); \
470 \
471 nir_validate_shader(b.shader, "input"); \
472 \
473 nir_loop_analyze_impl(b.impl, nir_var_all, false); \
474 \
475 ASSERT_NE((void *)0, loop->info); \
476 EXPECT_EQ((void *)0, loop->info->limiting_terminator); \
477 EXPECT_EQ(0, loop->info->max_trip_count); \
478 EXPECT_FALSE(loop->info->exact_trip_count_known); \
479 }
480
481 #define KNOWN_COUNT_TEST_INVERT(_init_value, _incr_value, _cond_value, cond, incr, count) \
482 TEST_F(nir_loop_analyze_test, incr##_##cond##_known_count_invert_##count) \
483 { \
484 nir_loop *loop = \
485 loop_builder_invert(&b, { .init_value = _init_value, \
486 .incr_value = _incr_value, \
487 .cond_value = _cond_value, \
488 .cond_instr = nir_##cond, \
489 .incr_instr = nir_##incr }); \
490 \
491 nir_validate_shader(b.shader, "input"); \
492 \
493 nir_loop_analyze_impl(b.impl, nir_var_all, false); \
494 \
495 ASSERT_NE((void *)0, loop->info); \
496 EXPECT_NE((void *)0, loop->info->limiting_terminator); \
497 EXPECT_EQ(count, loop->info->max_trip_count); \
498 EXPECT_TRUE(loop->info->exact_trip_count_known); \
499 \
500 ASSERT_NE((void *)0, loop->info->induction_vars); \
501 EXPECT_EQ(2, _mesa_hash_table_num_entries(loop->info->induction_vars)); \
502 \
503 hash_table_foreach(loop->info->induction_vars, entry) { \
504 nir_loop_induction_variable *ivar = (nir_loop_induction_variable *)entry->data; \
505 EXPECT_NE((void *)0, ivar->basis); \
506 EXPECT_NE((void *)0, ivar->def); \
507 ASSERT_NE((void *)0, ivar->init_src); \
508 EXPECT_TRUE(nir_src_is_const(*ivar->init_src)); \
509 ASSERT_NE((void *)0, ivar->update_src); \
510 EXPECT_TRUE(nir_src_is_const(ivar->update_src->src)); \
511 } \
512 }
513
514 #define UNKNOWN_COUNT_TEST_INVERT(_init_value, _incr_value, _cond_value, cond, incr) \
515 TEST_F(nir_loop_analyze_test, incr ## _ ## cond ## _unknown_count_invert) \
516 { \
517 nir_loop *loop = \
518 loop_builder_invert(&b, {.init_value = _init_value, \
519 .incr_value = _incr_value, \
520 .cond_value = _cond_value, \
521 .cond_instr = nir_ ## cond, \
522 .incr_instr = nir_ ## incr}); \
523 \
524 nir_validate_shader(b.shader, "input"); \
525 \
526 nir_loop_analyze_impl(b.impl, nir_var_all, false); \
527 \
528 ASSERT_NE((void *)0, loop->info); \
529 EXPECT_EQ((void *)0, loop->info->limiting_terminator); \
530 EXPECT_EQ(0, loop->info->max_trip_count); \
531 EXPECT_FALSE(loop->info->exact_trip_count_known); \
532 }
533
534 #define INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(_init_value, _incr_value, _cond_value, cond, incr) \
535 TEST_F(nir_loop_analyze_test, incr ## _ ## cond ## _infinite_loop_unknown_count_invert) \
536 { \
537 nir_loop *loop = \
538 loop_builder_invert(&b, {.init_value = _init_value, \
539 .incr_value = _incr_value, \
540 .cond_value = _cond_value, \
541 .cond_instr = nir_ ## cond, \
542 .incr_instr = nir_ ## incr}); \
543 \
544 nir_validate_shader(b.shader, "input"); \
545 \
546 nir_loop_analyze_impl(b.impl, nir_var_all, false); \
547 \
548 ASSERT_NE((void *)0, loop->info); \
549 EXPECT_EQ((void *)0, loop->info->limiting_terminator); \
550 EXPECT_EQ(0, loop->info->max_trip_count); \
551 EXPECT_FALSE(loop->info->exact_trip_count_known); \
552 }
553
554 /* float i = 0.0;
555 * while (true) {
556 * if (i == 0.9)
557 * break;
558 *
559 * i = i + 0.2;
560 * }
561 */
562 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000000, 0x3e4ccccd, 0x3f666666, feq, fadd)
563
564 /* uint i = 1;
565 * while (true) {
566 * if (i != 0)
567 * break;
568 *
569 * i++;
570 * }
571 *
572 * This loop should have an iteration count of zero. See also
573 * https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/19732#note_1648999
574 */
575 KNOWN_COUNT_TEST(0x00000001, 0x00000000, 0x00000001, ine, iadd, 0)
576
577 /* uint i = 0;
578 * while (true) {
579 * if (i >= 1)
580 * break;
581 *
582 * i++;
583 * }
584 */
585 KNOWN_COUNT_TEST(0x00000000, 0x00000001, 0x00000001, uge, iadd, 1)
586
587 /* uint i = 0;
588 * while (true) {
589 * if (i != 0)
590 * break;
591 *
592 * i++;
593 * }
594 */
595 KNOWN_COUNT_TEST(0x00000000, 0x00000000, 0x00000001, ine, iadd, 1)
596
597 /* uint i = 0;
598 * while (true) {
599 * if (!(i != 6))
600 * break;
601 *
602 * i++;
603 * }
604 */
605 KNOWN_COUNT_TEST(0x00000000, 0x00000006, 0x00000001, inot_ine, iadd, 6)
606
607 /* uint i = 0;
608 * while (true) {
609 * i++;
610 *
611 * if (!(i != 8))
612 * break;
613 * }
614 */
615 KNOWN_COUNT_TEST_INVERT(0x00000000, 0x00000001, 0x00000008, inot_ine, iadd, 7)
616
617 /* uint i = 0;
618 * while (true) {
619 * if (i == 1)
620 * break;
621 *
622 * i++;
623 * }
624 */
625 KNOWN_COUNT_TEST(0x00000000, 0x00000001, 0x00000001, ieq, iadd, 1)
626
627 /* uint i = 0;
628 * while (true) {
629 * if (i == 6)
630 * break;
631 *
632 * i++;
633 * }
634 */
635 KNOWN_COUNT_TEST(0x00000000, 0x00000006, 0x00000001, ieq, iadd, 6)
636
637 /* uint i = 0;
638 * while (true) {
639 * i++;
640 *
641 * if (i == 6)
642 * break;
643 * }
644 */
645 KNOWN_COUNT_TEST_INVERT(0x00000000, 0x00000001, 0x00000006, ieq, iadd, 5)
646
647 /* float i = 0.0;
648 * while (true) {
649 * if (i != 0.0)
650 * break;
651 *
652 * i = i + 1.0;
653 * }
654 */
655 KNOWN_COUNT_TEST(0x00000000, 0x00000000, 0x3f800000, fneu, fadd, 1)
656
657 /* uint i = 0;
658 * while (true) {
659 * i++;
660 *
661 * if (i != 0)
662 * break;
663 * }
664 */
665 KNOWN_COUNT_TEST_INVERT(0x00000000, 0x00000001, 0x00000000, ine, iadd, 0)
666
667 /* int i = 0;
668 * while (true) {
669 * i++;
670 *
671 * if (i >= 6)
672 * break;
673 * }
674 */
675 KNOWN_COUNT_TEST_INVERT(0x00000000, 0x00000001, 0x00000006, ige, iadd, 5)
676
677 /* uint i = 10;
678 * while (true) {
679 * if (!(5 < i))
680 * break;
681 *
682 * i += -1;
683 * }
684 */
685 KNOWN_COUNT_TEST(0x0000000a, 0x00000005, 0xffffffff, inot_ilt_rev, iadd, 5)
686
687 /* int i = 10;
688 * while (true) {
689 * if (!(imin(vertex_id, 5) < i))
690 * break;
691 *
692 * i += -1;
693 * }
694 */
695 UNKNOWN_COUNT_TEST(0x0000000a, 0x00000005, 0xffffffff, inot_ilt_imin_rev, iadd)
696
697 /* uint i = 0;
698 * while (true) {
699 * if (!(0 >= i))
700 * break;
701 *
702 * i += 1;
703 * }
704 */
705 KNOWN_COUNT_TEST(0x00000000, 0x00000000, 0x00000001, inot_uge_rev, iadd, 1)
706
707 /* uint i = 0;
708 * while (true) {
709 * if (i != 0)
710 * break;
711 *
712 * i >>= 1;
713 * }
714 */
715 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000000, 0x00000000, 0x00000001, ine, ushr)
716
717 /* uint i = 0x80000000;
718 * while (true) {
719 * if (i == 0xDEADBEEF)
720 * break;
721 *
722 * i >>= 1;
723 * }
724 */
725 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x80000000, 0xDEADBEEF, 0x00000001, ieq, ushr)
726
727 /* There is no ult / ushr infinite loop test because, aside from the
728 * contradiction ult(x, 0), there isn't a way to construct such a loop with
729 * the loop induction variable on the left side of the comparison.
730 */
731 /* INFINITE_LOOP_UNKNOWN_COUNT_TEST(0xBADDC0DE, 0xBADDC0DE, 0xBADDC0DE, ult, ushr) */
732
733 /* uint i = 0x40000000;
734 * while (true) {
735 * if (0x43210000 < i)
736 * break;
737 *
738 * i >>= 1;
739 * }
740 */
741 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x40000000, 0x43210000, 0x00000001, ult_rev, ushr)
742
743 /* uint i = 0x40000000;
744 * while (true) {
745 * if (i >= 0x80000000)
746 * break;
747 *
748 * i >>= 1;
749 * }
750 */
751 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x40000000, 0x80000000, 0x00000001, uge, ushr)
752
753 /* There is no uge_rev / ushr infinite loop test because I could not think of
754 * a way to construct one.
755 */
756 /* INFINITE_LOOP_UNKNOWN_COUNT_TEST(0xBADDC0DE, 0xBADDC0DE, 0xBADDC0DE, uge_rev, ushr) */
757
758 /* uint i = 0x00001234;
759 * while (true) {
760 * i >>= 16;
761 *
762 * if (i != 0)
763 * break;
764 * }
765 */
766 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x00001234, 0x00000010, 0x00000000, ine, ushr)
767
768 /* uint i = 0x12345678;
769 * while (true) {
770 * i >>= 3;
771 *
772 * if (i == 0x048d159e)
773 * break;
774 * }
775 */
776 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x12345678, 0x00000003, 0x048d159e, ieq, ushr)
777
778 /* There is no ult / ushr infinite inverted loop test because, aside from the
779 * contradiction ult(x, 0), there isn't a way to construct such a loop with
780 * the loop induction variable on the left side of the comparison.
781 */
782 /* INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0xBADDC0DE, 0xBADDC0DE, 0xBADDC0DE, ult, ushr) */
783
784 /* uint i = 0x87654321;
785 * while (true) {
786 * i >>= 2;
787 *
788 * if (0x77777777 < i)
789 * break;
790 * }
791 */
792 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x87654321, 0x00000002, 0x77777777, ult_rev, ushr)
793
794 /* uint i = 0x80000000;
795 * while (true) {
796 * i >>= 3;
797 *
798 * if (i >= 0x40000000)
799 * break;
800 * }
801 */
802 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000003, 0x40000000, uge, ushr)
803
804 /* There is no uge_rev / ushr infinite loop test because I could not think of
805 * a way to construct one.
806 */
807 /* INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0xBADDC0DE, 0xBADDC0DE, 0xBADDC0DE, uge_rev, ushr) */
808
809 /* uint i = 0x80000000;
810 * while (true) {
811 * if (i != 0x80000000)
812 * break;
813 *
814 * i >>= 1;
815 * }
816 */
817 KNOWN_COUNT_TEST(0x80000000, 0x80000000, 0x00000001, ine, ushr, 1)
818
819 /* uint i = 0x80000000;
820 * while (true) {
821 * if (i == 0)
822 * break;
823 *
824 * i >>= 1;
825 * }
826 */
827 KNOWN_COUNT_TEST(0x80000000, 0x00000000, 0x00000001, ieq, ushr, 32)
828
829 /* uint i = 0x80000000;
830 * while (true) {
831 * if (i < 2)
832 * break;
833 *
834 * i >>= 1;
835 * }
836 */
837 KNOWN_COUNT_TEST(0x80000000, 0x00000002, 0x00000001, ult, ushr, 31)
838
839 /* uint i = 0x80000000;
840 * while (true) {
841 * if (2 < i)
842 * break;
843 *
844 * i >>= 1;
845 * }
846 */
847 KNOWN_COUNT_TEST(0x80000000, 0x00000002, 0x00000001, ult_rev, ushr, 0)
848
849 /* uint i = 0x80000000;
850 * while (true) {
851 * if (i >= 0x80000000)
852 * break;
853 *
854 * i >>= 1;
855 * }
856 */
857 KNOWN_COUNT_TEST(0x80000000, 0x80000000, 0x00000001, uge, ushr, 0)
858
859 /* uint i = 0x80000000;
860 * while (true) {
861 * if (0x00008000 >= i)
862 * break;
863 *
864 * i >>= 1;
865 * }
866 */
867 KNOWN_COUNT_TEST(0x80000000, 0x00008000, 0x00000001, uge_rev, ushr, 16)
868
869 /* uint i = 0x80000000;
870 * while (true) {
871 * i >>= 1;
872 *
873 * if (i != 0x80000000)
874 * break;
875 * }
876 */
877 KNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000001, 0x80000000, ine, ushr, 0)
878
879 /* uint i = 0x80000000;
880 * while (true) {
881 * i >>= 1;
882 *
883 * if (i == 0x00000000)
884 * break;
885 * }
886 */
887 KNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000001, 0x00000000, ieq, ushr, 31)
888
889 /* uint i = 0x80000000;
890 * while (true) {
891 * i >>= 1;
892 *
893 * if (i < 0x80000000)
894 * break;
895 * }
896 */
897 KNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000001, 0x80000000, ult, ushr, 0)
898
899 /* uint i = 0xAAAAAAAA;
900 * while (true) {
901 * i >>= 1;
902 *
903 * if (0x08000000 < i)
904 * break;
905 * }
906 */
907 KNOWN_COUNT_TEST_INVERT(0xAAAAAAAA, 0x00000001, 0x08000000, ult_rev, ushr, 0)
908
909 /* uint i = 0x80000000;
910 * while (true) {
911 * i >>= 1;
912 *
913 * if (i >= 0x00000000)
914 * break;
915 * }
916 */
917 KNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000001, 0x00000000, uge, ushr, 0)
918
919 /* uint i = 0x80000000;
920 * while (true) {
921 * i >>= 1;
922 *
923 * if (0x00000008 >= i)
924 * break;
925 * }
926 */
927 KNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000001, 0x00000008, uge_rev, ushr, 27)
928
929 /* int i = 0xffffffff;
930 * while (true) {
931 * if (i != 0xffffffff)
932 * break;
933 *
934 * i >>= 1;
935 * }
936 */
937 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0xffffffff, 0xffffffff, 0x00000001, ine, ishr)
938
939 /* int i = 0x80000000;
940 * while (true) {
941 * if (i == 0)
942 * break;
943 *
944 * i >>= 1;
945 * }
946 */
947 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x80000000, 0x00000000, 0x00000001, ieq, ishr)
948
949 /* int i = 0x7fffffff;
950 * while (true) {
951 * if (i < 0)
952 * break;
953 *
954 * i >>= 1;
955 * }
956 */
957 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x7fffffff, 0x00000000, 0x00000001, ilt, ishr)
958
959 /* int i = 0x80000000;
960 * while (true) {
961 * if (0 < i)
962 * break;
963 *
964 * i >>= 1;
965 * }
966 */
967 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x80000000, 0x00000000, 0x00000001, ilt_rev, ishr)
968
969 /* int i = 0x80000000;
970 * while (true) {
971 * if (i >= 0)
972 * break;
973 *
974 * i >>= 1;
975 * }
976 */
977 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x80000000, 0x00000000, 0x00000001, ige, ishr)
978
979 /* int i = 0x76543210;
980 * while (true) {
981 * if (-1 >= i)
982 * break;
983 *
984 * i >>= 1;
985 * }
986 */
987 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x76543210, 0xffffffff, 0x00000001, ige_rev, ishr)
988
989 /* int i = 0xffffffff;
990 * while (true) {
991 * i >>= 1;
992 *
993 * if (i != 0xffffffff)
994 * break;
995 * }
996 */
997 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0xffffffff, 0x00000001, 0xffffffff, ine, ishr)
998
999 /* int i = 0xffffffff;
1000 * while (true) {
1001 * i >>= 1;
1002 *
1003 * if (i == 0)
1004 * break;
1005 * }
1006 */
1007 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0xffffffff, 0x00000001, 0x00000000, ieq, ishr)
1008
1009 /* int i = 0x7fffffff;
1010 * while (true) {
1011 * i >>= 1;
1012 *
1013 * if (i < 0)
1014 * break;
1015 * }
1016 */
1017 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x7fffffff, 0x00000001, 0x00000000, ilt, ishr)
1018
1019 /* int i = 0x80000000;
1020 * while (true) {
1021 * i >>= 1;
1022 *
1023 * if (1 < i)
1024 * break;
1025 * }
1026 */
1027 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000001, 0x00000001, ilt_rev, ishr)
1028
1029 /* int i = 0x80000000;
1030 * while (true) {
1031 * i >>= 1;
1032 *
1033 * if (i >= 0)
1034 * break;
1035 * }
1036 */
1037 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000001, 0x00000000, ige, ishr)
1038
1039 /* int i = 0x76543210;
1040 * while (true) {
1041 * i >>= 7;
1042 *
1043 * if (-1 >= i)
1044 * break;
1045 * }
1046 */
1047 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x76543210, 0x00000007, 0xffffffff, ige_rev, ishr)
1048
1049 /* int i = 0x7fffffff;
1050 * while (true) {
1051 * if (i != 0)
1052 * break;
1053 *
1054 * i >>= 1;
1055 * }
1056 */
1057 KNOWN_COUNT_TEST(0x7fffffff, 0x00000000, 0x00000001, ine, ishr, 0)
1058
1059 /* int i = 0x40000000;
1060 * while (true) {
1061 * if (i == 1)
1062 * break;
1063 *
1064 * i >>= 1;
1065 * }
1066 */
1067 KNOWN_COUNT_TEST(0x40000000, 0x00000001, 0x00000001, ieq, ishr, 30)
1068
1069 /* int i = 0x7fffffff;
1070 * while (true) {
1071 * if (i < 1)
1072 * break;
1073 *
1074 * i >>= 1;
1075 * }
1076 */
1077 KNOWN_COUNT_TEST(0x7fffffff, 0x00000001, 0x00000001, ilt, ishr, 31)
1078
1079 /* int i = 0x80000000;
1080 * while (true) {
1081 * if (0xffff0000 < i)
1082 * break;
1083 *
1084 * i >>= 1;
1085 * }
1086 */
1087 KNOWN_COUNT_TEST(0x80000000, 0xffff0000, 0x00000001, ilt_rev, ishr, 16)
1088
1089 /* int i = 0x80000000;
1090 * while (true) {
1091 * if (i >= -1)
1092 * break;
1093 *
1094 * i >>= 1;
1095 * }
1096 */
1097 KNOWN_COUNT_TEST(0x80000000, 0xffffffff, 0x00000001, ige, ishr, 31)
1098
1099 /* int i = 0x12345678;
1100 * while (true) {
1101 * if (1 >= i)
1102 * break;
1103 *
1104 * i >>= 4;
1105 * }
1106 */
1107 KNOWN_COUNT_TEST(0x12345678, 0x00000001, 0x00000004, ige_rev, ishr, 7)
1108
1109 /* int i = 0x7fffffff;
1110 * while (true) {
1111 * i >>= 1;
1112 *
1113 * if (i != 0)
1114 * break;
1115 * }
1116 */
1117 KNOWN_COUNT_TEST_INVERT(0x7fffffff, 0x00000001, 0x00000000, ine, ishr, 0)
1118
1119 /* int i = 0x7fffffff;
1120 * while (true) {
1121 * i >>= 1;
1122 *
1123 * if (i == 0)
1124 * break;
1125 * }
1126 */
1127 KNOWN_COUNT_TEST_INVERT(0x7fffffff, 0x00000001, 0x00000000, ieq, ishr, 30)
1128
1129 /* int i = 0x7fffffff;
1130 * while (true) {
1131 * i >>= 1;
1132 *
1133 * if (i < 1)
1134 * break;
1135 * }
1136 */
1137 KNOWN_COUNT_TEST_INVERT(0x7fffffff, 0x00000001, 0x00000001, ilt, ishr, 30)
1138
1139 /* int i = 0x80000000;
1140 * while (true) {
1141 * i >>= 1;
1142 *
1143 * if (-2 < i)
1144 * break;
1145 * }
1146 */
1147 KNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000001, 0xfffffffe, ilt_rev, ishr, 30)
1148
1149 /* int i = 0xbfffffff;
1150 * while (true) {
1151 * i >>= 1;
1152 *
1153 * if (i >= -2)
1154 * break;
1155 * }
1156 */
1157 KNOWN_COUNT_TEST_INVERT(0xbfffffff, 0x00000001, 0xfffffffe, ige, ishr, 29)
1158
1159 /* int i = 0x7fffffff;
1160 * while (true) {
1161 * i >>= 1;
1162 *
1163 * if (2 >= i)
1164 * break;
1165 * }
1166 */
1167 KNOWN_COUNT_TEST_INVERT(0x7fffffff, 0x00000001, 0x00000002, ige_rev, ishr, 29)
1168
1169 /* int i = 0;
1170 * while (true) {
1171 * if (i != 0)
1172 * break;
1173 *
1174 * i <<= 1;
1175 * }
1176 */
1177 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000000, 0x00000000, 0x00000001, ine, ishl)
1178
1179 /* int i = 1;
1180 * while (true) {
1181 * if (i == 3)
1182 * break;
1183 *
1184 * i <<= 1;
1185 * }
1186 */
1187 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000001, 0x00000003, 0x00000001, ieq, ishl)
1188
1189 /* int i = 1;
1190 * while (true) {
1191 * if (i < 0x80000001)
1192 * break;
1193 *
1194 * i <<= 2;
1195 * }
1196 */
1197 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000001, 0x80000001, 0x00000002, ilt, ishl)
1198
1199 /* int i = 0xffff0000;
1200 * while (true) {
1201 * if (1 < i)
1202 * break;
1203 *
1204 * i <<= 2;
1205 * }
1206 */
1207 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0xffff0000, 0x00000001, 0x00000002, ilt_rev, ishl)
1208
1209 /* int i = 1;
1210 * while (true) {
1211 * if (i >= 0x70000000)
1212 * break;
1213 *
1214 * i <<= 1;
1215 * }
1216 */
1217 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000001, 0x70000000, 0x00000001, ige, ishl)
1218
1219 /* int i = 1;
1220 * while (true) {
1221 * if (0xf0000000 >= i)
1222 * break;
1223 *
1224 * i <<= 2;
1225 * }
1226 */
1227 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000001, 0xf0000000, 0x00000002, ige_rev, ishl)
1228
1229 /* int i = 0x80000000;
1230 * while (true) {
1231 * i <<= 1;
1232 *
1233 * if (i != 0)
1234 * break;
1235 * }
1236 */
1237 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000001, 0x00000000, ine, ishl)
1238
1239 /* int i = 0xf0f0f0f0;
1240 * while (true) {
1241 * i <<= 2;
1242 *
1243 * if (i == 0xe1e1e1e0)
1244 * break;
1245 * }
1246 */
1247 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0xf0f0f0f0, 0x00000002, 0xe1e1e1e0, ieq, ishl)
1248
1249 /* int i = 1;
1250 * while (true) {
1251 * i <<= 2;
1252 *
1253 * if (i < 0)
1254 * break;
1255 * }
1256 */
1257 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x00000001, 0x00000002, 0x00000000, ilt, ishl)
1258
1259 /* int i = 0xffffffff;
1260 * while (true) {
1261 * i <<= 2;
1262 *
1263 * if (0 < i)
1264 * break;
1265 * }
1266 */
1267 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0xffffffff, 0x00000002, 0x00000000, ilt_rev, ishl)
1268
1269 /* int i = 0x88888888;
1270 * while (true) {
1271 * i <<= 4;
1272 *
1273 * if (i >= 1)
1274 * break;
1275 * }
1276 */
1277 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x88888888, 0x00000004, 0x00000001, ige, ishl)
1278
1279 /* int i = 0x77777777;
1280 * while (true) {
1281 * i <<= 4;
1282 *
1283 * if (-1 >= i)
1284 * break;
1285 * }
1286 */
1287 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x77777777, 0x00000004, 0xffffffff, ige_rev, ishl)
1288
1289 /* int i = 1;
1290 * while (true) {
1291 * if (i != 1)
1292 * break;
1293 *
1294 * i <<= 1;
1295 * }
1296 */
1297 KNOWN_COUNT_TEST(0x00000001, 0x00000001, 0x00000001, ine, ishl, 1)
1298
1299 /* int i = 1;
1300 * while (true) {
1301 * if (i == 0x1000)
1302 * break;
1303 *
1304 * i <<= 4;
1305 * }
1306 */
1307 KNOWN_COUNT_TEST(0x00000001, 0x00001000, 0x00000004, ieq, ishl, 3)
1308
1309 /* uint i = 1;
1310 * while (true) {
1311 * if (i < 1)
1312 * break;
1313 *
1314 * i <<= 1;
1315 * }
1316 */
1317 KNOWN_COUNT_TEST(0x00000001, 0x00000001, 0x00000001, ult, ishl, 32)
1318
1319 /* int i = 1;
1320 * while (true) {
1321 * if (i < 1)
1322 * break;
1323 *
1324 * i <<= 1;
1325 * }
1326 */
1327 KNOWN_COUNT_TEST(0x00000001, 0x00000001, 0x00000001, ilt, ishl, 31)
1328
1329 /* int i = 0xffff0000;
1330 * while (true) {
1331 * if (-1 < i)
1332 * break;
1333 *
1334 * i <<= 2;
1335 * }
1336 */
1337 KNOWN_COUNT_TEST(0xffff0000, 0xffffffff, 0x00000002, ilt_rev, ishl, 8)
1338
1339 /* int i = 0xf;
1340 * while (true) {
1341 * if (i >= 0x0000ffff)
1342 * break;
1343 *
1344 * i <<= 3;
1345 * }
1346 */
1347 KNOWN_COUNT_TEST(0x0000000f, 0x0000ffff, 0x00000003, ige, ishl, 5)
1348
1349 /* int i = 0x0000000f;
1350 * while (true) {
1351 * if (-196608 >= i)
1352 * break;
1353 *
1354 * i <<= 4;
1355 * }
1356 */
1357 KNOWN_COUNT_TEST(0x0000000f, 0xfffd0000, 0x00000004, ige_rev, ishl, 7)
1358
1359 /* int i = 1;
1360 * while (true) {
1361 * i <<= 1;
1362 *
1363 * if (i != 2)
1364 * break;
1365 * }
1366 */
1367 KNOWN_COUNT_TEST_INVERT(0x00000001, 0x00000001, 0x00000002, ine, ishl, 1)
1368
1369 /* int i = 1;
1370 * while (true) {
1371 * i <<= 8;
1372 *
1373 * if (i == 0x01000000)
1374 * break;
1375 * }
1376 */
1377 KNOWN_COUNT_TEST_INVERT(0x00000001, 0x00000008, 0x01000000, ieq, ishl, 2)
1378
1379 /* int i = 0x7fffffff;
1380 * while (true) {
1381 * i <<= 1;
1382 *
1383 * if (i < 1)
1384 * break;
1385 * }
1386 */
1387 KNOWN_COUNT_TEST_INVERT(0x7fffffff, 0x00000001, 0x00000001, ilt, ishl, 0)
1388
1389 /* int i = 0x7fff;
1390 * while (true) {
1391 * i <<= 2;
1392 *
1393 * if (0x1fffffff < i)
1394 * break;
1395 * }
1396 */
1397 KNOWN_COUNT_TEST_INVERT(0x00007fff, 0x00000002, 0x1fffffff, ilt_rev, ishl, 7)
1398
1399 /* int i = 0xffff7fff;
1400 * while (true) {
1401 * i <<= 4;
1402 *
1403 * if (i >= -2)
1404 * break;
1405 * }
1406 */
1407 KNOWN_COUNT_TEST_INVERT(0xffff7fff, 0x00000004, 0xfffffffe, ige, ishl, 3)
1408
1409 /* int i = 0x0000f0f0;
1410 * while (true) {
1411 * i <<= 4;
1412 *
1413 * if (-2 >= i)
1414 * break;
1415 * }
1416 */
1417 KNOWN_COUNT_TEST_INVERT(0x0000f0f0, 0x00000004, 0xfffffffe, ige_rev, ishl, 3)
1418
1419 /* This infinite loop makes no sense, but it's a good test to make sure the
1420 * loop analysis code doesn't incorrectly treat left-shift as a commutative
1421 * operation.
1422 *
1423 * int i = 1;
1424 * while (true) {
1425 * if (i == 0)
1426 * break;
1427 *
1428 * i = 1 << i;
1429 * }
1430 */
1431 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000001, 0x00000000, 0x00000001, ieq, ishl_rev)
1432
1433 /* int i = 0;
1434 * while (true) {
1435 * if (i != 0)
1436 * break;
1437 *
1438 * i = i * 7;
1439 * }
1440 */
1441 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000000, 0x00000000, 0x00000007, ine, imul)
1442
1443 /* int i = 1;
1444 * while (true) {
1445 * if (i == 4)
1446 * break;
1447 *
1448 * i = i * 3;
1449 * }
1450 */
1451 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000001, 0x00000004, 0x00000003, ieq, imul)
1452
1453 /* int i = 1;
1454 * while (true) {
1455 * // The only value less than 0x80000001 is 0x80000000, but the result
1456 * // of the multiply can never be even.
1457 * if (i < 0x80000001)
1458 * break;
1459 *
1460 * i = i * 5;
1461 * }
1462 */
1463 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000001, 0x80000001, 0x00000005, ilt, imul)
1464
1465 /* int i = 2;
1466 * while (true) {
1467 * if (i >= 0x7f000000)
1468 * break;
1469 *
1470 * i = i * 6;
1471 * }
1472 */
1473 INFINITE_LOOP_UNKNOWN_COUNT_TEST(0x00000002, 0x7f000000, 0x00000006, ige, imul)
1474
1475 /* int i = 0x80000000;
1476 * while (true) {
1477 * i = i * 6;
1478 *
1479 * if (i != 0)
1480 * break;
1481 * }
1482 */
1483 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x80000000, 0x00000006, 0x00000000, ine, imul)
1484
1485 /* int i = 0xf0f0f0f0;
1486 * while (true) {
1487 * i = i * 6;
1488 *
1489 * if (i == 0xe1e1e1e1)
1490 * break;
1491 * }
1492 */
1493 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0xf0f0f0f0, 0x00000006, 0xe1e1e1e1, ieq, imul)
1494
1495 /* int i = 3;
1496 * while (true) {
1497 * i = i * 3;
1498 *
1499 * // The only value less than 0x80000001 is 0x80000000, but the result
1500 * // of the multiply can never be even.
1501 * if (i < 0x80000001)
1502 * break;
1503 * }
1504 */
1505 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x00000003, 0x00000003, 0x80000001, ilt, imul)
1506
1507 /* int i = 0x88888888;
1508 * while (true) {
1509 * i = i * 16;
1510 *
1511 * if (i >= 1)
1512 * break;
1513 * }
1514 *
1515 * I'm not fond of this test because (i * 16) is the same as (i << 4), but I
1516 * could not think of another way.
1517 */
1518 INFINITE_LOOP_UNKNOWN_COUNT_TEST_INVERT(0x88888888, 0x00000010, 0x00000001, ige, imul)
1519
1520 /* int i = 1;
1521 * while (true) {
1522 * if (i != 1)
1523 * break;
1524 *
1525 * i = i * 7;
1526 * }
1527 */
1528 KNOWN_COUNT_TEST(0x00000001, 0x00000001, 0x00000007, ine, imul, 1)
1529
1530 /* int i = 2;
1531 * while (true) {
1532 * if (i == 54)
1533 * break;
1534 *
1535 * i = i * 3;
1536 * }
1537 */
1538 KNOWN_COUNT_TEST(0x00000002, 0x00000036, 0x00000003, ieq, imul, 3)
1539
1540 /* int i = 5;
1541 * while (true) {
1542 * if (i < 1)
1543 * break;
1544 *
1545 * i = i * -3;
1546 * }
1547 */
1548 KNOWN_COUNT_TEST(0x00000005, 0x00000001, 0xfffffffd, ilt, imul, 1)
1549
1550 /* int i = 0xf;
1551 * while (true) {
1552 * if (i >= 0x0000ffff)
1553 * break;
1554 *
1555 * i = i * 11;
1556 * }
1557 */
1558 KNOWN_COUNT_TEST(0x0000000f, 0x0000ffff, 0x0000000b, ige, imul, 4)
1559
1560 /* int i = 3;
1561 * while (true) {
1562 * i = i * -5;
1563 *
1564 * if (i != -15)
1565 * break;
1566 * }
1567 */
1568 KNOWN_COUNT_TEST_INVERT(0x00000003, 0xfffffffb, 0xfffffff1, ine, imul, 1)
1569
1570 /* int i = 3;
1571 * while (true) {
1572 * i = i * -7;
1573 *
1574 * if (i == 0x562b3)
1575 * break;
1576 * }
1577 */
1578 KNOWN_COUNT_TEST_INVERT(0x00000003, 0xfffffff9, 0x000562b3, ieq, imul, 5)
1579
1580 /* int i = 0x7f;
1581 * while (true) {
1582 * i = i * 3;
1583 *
1584 * if (i < 1)
1585 * break;
1586 * }
1587 */
1588 KNOWN_COUNT_TEST_INVERT(0x0000007f, 0x00000003, 0x00000001, ilt, imul, 16)
1589
1590 /* int i = 0xffff7fff;
1591 * while (true) {
1592 * i = i * 15;
1593 *
1594 * if (i >= 0x34cce9b0)
1595 * break;
1596 * }
1597 */
1598 KNOWN_COUNT_TEST_INVERT(0xffff7fff, 0x0000000f, 0x34cce9b0, ige, imul, 4)
1599
1600 /* int i = 0;
1601 * while (true) {
1602 * if (i >= imin(vertex_id, 4))
1603 * break;
1604 *
1605 * i++;
1606 * }
1607 */
1608 INEXACT_COUNT_TEST(0x00000000, 0x00000004, 0x00000001, ige_imin, iadd, 4)
1609
1610 /* This fmin is the wrong type to be useful.
1611 *
1612 * int i = 0;
1613 * while (true) {
1614 * if (i >= fmin(vertex_id, 4))
1615 * break;
1616 *
1617 * i++;
1618 * }
1619 */
1620 UNKNOWN_COUNT_TEST(0x00000000, 0x00000004, 0x00000001, ige_fmin, iadd)
1621
1622 /* The comparison is unsigned, so this isn't safe if vertex_id is negative.
1623 *
1624 * uint i = 0;
1625 * while (true) {
1626 * if (i >= imin(vertex_id, 4))
1627 * break;
1628 *
1629 * i++;
1630 * }
1631 */
1632 UNKNOWN_COUNT_TEST(0x00000000, 0x00000004, 0x00000001, uge_imin, iadd)
1633
1634 /* int i = 8;
1635 * while (true) {
1636 * if (4 >= i)
1637 * break;
1638 *
1639 * i += -1;
1640 * }
1641 */
1642 KNOWN_COUNT_TEST(0x00000008, 0x00000004, 0xffffffff, ige_rev, iadd, 4)
1643
1644 /* int i = 8;
1645 * while (true) {
1646 * if (i < 4)
1647 * break;
1648 *
1649 * i += -1;
1650 * }
1651 */
1652 KNOWN_COUNT_TEST(0x00000008, 0x00000004, 0xffffffff, ilt, iadd, 5)
1653
1654 /* This imin can increase the iteration count, not limit it.
1655 *
1656 * int i = 8;
1657 * while (true) {
1658 * if (imin(vertex_id, 4) >= i)
1659 * break;
1660 *
1661 * i += -1;
1662 * }
1663 */
1664 UNKNOWN_COUNT_TEST(0x00000008, 0x00000004, 0xffffffff, ige_imin_rev, iadd)
1665
1666 /* This imin can increase the iteration count, not limit it.
1667 *
1668 * int i = 8;
1669 * while (true) {
1670 * if (i < imin(vertex_id, 4))
1671 * break;
1672 *
1673 * i += -1;
1674 * }
1675 */
1676 UNKNOWN_COUNT_TEST(0x00000008, 0x00000004, 0xffffffff, ilt_imin, iadd)
1677
1678 /* int i = 8;
1679 * while (true) {
1680 * if (i < imax(vertex_id, 4))
1681 * break;
1682 *
1683 * i--;
1684 * }
1685 */
1686 INEXACT_COUNT_TEST(0x00000008, 0x00000004, 0xffffffff, ilt_imax, iadd, 5)
1687
1688 /* uint i = 0x00000001;
1689 * while (true) {
1690 * if (i >= umin(vertex_id, 0x00000100))
1691 * break;
1692 *
1693 * i <<= 1;
1694 * }
1695 */
1696 INEXACT_COUNT_TEST(0x00000001, 0x00000100, 0x00000001, uge_umin, ishl, 8)
1697
1698 /* uniform uint x;
1699 * uint i = x;
1700 * while (true) {
1701 * if (i >= 4)
1702 * break;
1703 *
1704 * i += 6;
1705 * }
1706 */
1707 INEXACT_COUNT_TEST_UNKNOWN_INIT(0x00000004, 0x00000006, uge, iadd, 1, 0)
1708
1709 /* uniform uint x;
1710 * uint i = x;
1711 * while (true) {
1712 * if (!(i >= 4))
1713 * continue;
1714 * else
1715 * break;
1716 *
1717 * i += 6;
1718 * }
1719 */
1720 INEXACT_COUNT_TEST_UNKNOWN_INIT(0x00000004, 0x00000006, uge, iadd, 1, 1)
1721