60
60
#include <string.h>
64
* Enum recording the result of analyzing how control flow might exit
67
* Each possible value of jump_strength indicates a strictly stronger
68
* guarantee on control flow than the previous value.
70
* The ordering of strengths roughly reflects the way jumps are
71
* lowered: jumps with higher strength tend to be lowered to jumps of
72
* lower strength. Accordingly, strength is used as a heuristic to
73
* determine which lowering to perform first.
75
* This enum is also used by get_jump_strength() to categorize
76
* instructions as either break, continue, return, or other. When
77
* used in this fashion, strength_always_clears_execute_flag is not
80
* The control flow analysis made by this optimization pass makes two
81
* simplifying assumptions:
83
* - It ignores discard instructions, since they are lowered by a
84
* separate pass (lower_discard.cpp).
86
* - It assumes it is always possible for control to flow from a loop
87
* to the instruction immediately following it. Technically, this
88
* is not true (since all execution paths through the loop might
89
* jump back to the top, or return from the function).
91
* Both of these simplifying assumtions are safe, since they can never
92
* cause reachable code to be incorrectly classified as unreachable;
93
* they can only do the opposite.
98
* Analysis has produced no guarantee on how control flow might
99
* exit this IR node. It might fall out the bottom (with or
100
* without clearing the execute flag, if present), or it might
101
* continue to the top of the innermost enclosing loop, break out
102
* of it, or return from the function.
107
* The only way control can fall out the bottom of this node is
108
* through a code path that clears the execute flag. It might also
109
* continue to the top of the innermost enclosing loop, break out
110
* of it, or return from the function.
66
112
strength_always_clears_execute_flag,
115
* Control cannot fall out the bottom of this node. It might
116
* continue to the top of the innermost enclosing loop, break out
117
* of it, or return from the function.
67
119
strength_continue,
122
* Control cannot fall out the bottom of this node, or continue the
123
* top of the innermost enclosing loop. It can only break out of
124
* it or return from the function.
129
* Control cannot fall out the bottom of this node, continue to the
130
* top of the innermost enclosing loop, or break out of it. It can
131
* only return from the function.
182
247
struct ir_lower_jumps_visitor : public ir_control_flow_visitor {
248
/* Postconditions: on exit of any visit() function:
250
* ANALYSIS: this->block.min_strength,
251
* this->block.may_clear_execute_flag, and
252
* this->loop.may_set_return_flag are updated to reflect the
253
* characteristics of the visited statement.
255
* DEAD_CODE_ELIMINATION: If this->block.min_strength is not
256
* strength_none, the visited node is at the end of its exec_list.
257
* In other words, any unreachable statements that follow the
258
* visited statement in its exec_list have been removed.
260
* CONTAINED_JUMPS_LOWERED: If the visited statement contains other
261
* statements, then should_lower_jump() is false for all of the
262
* return, break, or continue statements it contains.
264
* Note that visiting a jump does not lower it. That is the
265
* responsibility of the statement (or function signature) that
185
271
struct function_record function;
308
* Insert the instructions necessary to lower a return statement,
309
* before the given return instruction.
311
void insert_lowered_return(ir_return *ir)
313
ir_variable* return_flag = this->function.get_return_flag();
314
if(!this->function.signature->return_type->is_void()) {
315
ir_variable* return_value = this->function.get_return_value();
317
new(ir) ir_assignment(
318
new (ir) ir_dereference_variable(return_value),
322
new(ir) ir_assignment(
323
new (ir) ir_dereference_variable(return_flag),
324
new (ir) ir_constant(true)));
325
this->loop.may_set_return_flag = true;
329
* If the given instruction is a return, lower it to instructions
330
* that store the return value (if there is one), set the return
331
* flag, and then break.
333
* It is safe to pass NULL to this function.
335
void lower_return_unconditionally(ir_instruction *ir)
337
if (get_jump_strength(ir) != strength_return) {
340
insert_lowered_return((ir_return*)ir);
341
ir->replace_with(new(ir) ir_loop_jump(ir_loop_jump::jump_break));
345
* Create the necessary instruction to replace a break instruction.
347
ir_instruction *create_lowered_break()
349
void *ctx = this->function.signature;
350
return new(ctx) ir_assignment(
351
new(ctx) ir_dereference_variable(this->loop.get_break_flag()),
352
new(ctx) ir_constant(true),
357
* If the given instruction is a break, lower it to an instruction
358
* that sets the break flag, without consulting
359
* should_lower_jump().
361
* It is safe to pass NULL to this function.
363
void lower_break_unconditionally(ir_instruction *ir)
365
if (get_jump_strength(ir) != strength_break) {
368
ir->replace_with(create_lowered_break());
372
* If the block ends in a conditional or unconditional break, lower
373
* it, even though should_lower_jump() says it needn't be lowered.
375
void lower_final_breaks(exec_list *block)
377
ir_instruction *ir = (ir_instruction *) block->get_tail();
378
lower_break_unconditionally(ir);
379
ir_if *ir_if = ir->as_if();
381
lower_break_unconditionally(
382
(ir_instruction *) ir_if->then_instructions.get_tail());
383
lower_break_unconditionally(
384
(ir_instruction *) ir_if->else_instructions.get_tail());
221
388
virtual void visit(class ir_loop_jump * ir)
390
/* Eliminate all instructions after each one, since they are
391
* unreachable. This satisfies the DEAD_CODE_ELIMINATION
223
394
truncate_after_instruction(ir);
396
/* Set this->block.min_strength based on this instruction. This
397
* satisfies the ANALYSIS postcondition. It is not necessary to
398
* update this->block.may_clear_execute_flag or
399
* this->loop.may_set_return_flag, because an unlowered jump
400
* instruction can't change any flags.
224
402
this->block.min_strength = ir->is_break() ? strength_break : strength_continue;
404
/* The CONTAINED_JUMPS_LOWERED postcondition is already
405
* satisfied, because jump statements can't contain other
227
410
virtual void visit(class ir_return * ir)
412
/* Eliminate all instructions after each one, since they are
413
* unreachable. This satisfies the DEAD_CODE_ELIMINATION
229
416
truncate_after_instruction(ir);
418
/* Set this->block.min_strength based on this instruction. This
419
* satisfies the ANALYSIS postcondition. It is not necessary to
420
* update this->block.may_clear_execute_flag or
421
* this->loop.may_set_return_flag, because an unlowered return
422
* instruction can't change any flags.
230
424
this->block.min_strength = strength_return;
426
/* The CONTAINED_JUMPS_LOWERED postcondition is already
427
* satisfied, because jump statements can't contain other
233
432
virtual void visit(class ir_discard * ir)
434
/* Nothing needs to be done. The ANALYSIS and
435
* DEAD_CODE_ELIMINATION postconditions are already satisfied,
436
* because discard statements are ignored by this optimization
437
* pass. The CONTAINED_JUMPS_LOWERED postcondition is already
438
* satisfied, because discard statements can't contain other
237
444
enum jump_strength get_jump_strength(ir_instruction* ir)
286
491
block_record visit_block(exec_list* list)
493
/* Note: since visiting a node may change that node's next
494
* pointer, we can't use visit_exec_list(), because
495
* visit_exec_list() caches the node's next pointer before
496
* visiting it. So we use foreach_list() instead.
498
* foreach_list() isn't safe if the node being visited gets
499
* removed, but fortunately this visitor doesn't do that.
288
502
block_record saved_block = this->block;
289
503
this->block = block_record();
290
visit_exec_list(list, this);
504
foreach_list(node, list) {
505
((ir_instruction *) node)->accept(this);
291
507
block_record ret = this->block;
292
508
this->block = saved_block;
304
520
block_record block_records[2];
305
521
ir_jump* jumps[2];
523
/* Recursively lower nested jumps. This satisfies the
524
* CONTAINED_JUMPS_LOWERED postcondition, except in the case of
525
* unconditional jumps at the end of ir->then_instructions and
526
* ir->else_instructions, which are handled below.
307
528
block_records[0] = visit_block(&ir->then_instructions);
308
529
block_records[1] = visit_block(&ir->else_instructions);
310
531
retry: /* we get here if we put code after the if inside a branch */
311
for(unsigned i = 0; i < 2; ++i) {
312
exec_list& list = i ? ir->else_instructions : ir->then_instructions;
314
if(!list.is_empty() && get_jump_strength((ir_instruction*)list.get_tail()))
315
jumps[i] = (ir_jump*)list.get_tail();
533
/* Determine which of ir->then_instructions and
534
* ir->else_instructions end with an unconditional jump.
536
for(unsigned i = 0; i < 2; ++i) {
537
exec_list& list = i ? ir->else_instructions : ir->then_instructions;
539
if(!list.is_empty() && get_jump_strength((ir_instruction*)list.get_tail()))
540
jumps[i] = (ir_jump*)list.get_tail();
543
/* Loop until we have satisfied the CONTAINED_JUMPS_LOWERED
544
* postcondition by lowering jumps in both then_instructions and
548
/* Determine the types of the jumps that terminate
549
* ir->then_instructions and ir->else_instructions.
319
551
jump_strength jump_strengths[2];
321
553
for(unsigned i = 0; i < 2; ++i) {
367
613
else if(should_lower[1])
616
/* Neither code path ends in a jump that needs to be
617
* lowered, so the CONTAINED_JUMPS_LOWERED postcondition
618
* is satisfied and we can break out of the loop.
372
622
if(jump_strengths[lower] == strength_return) {
373
ir_variable* return_flag = this->function.get_return_flag();
374
if(!this->function.signature->return_type->is_void()) {
375
ir_variable* return_value = this->function.get_return_value();
376
jumps[lower]->insert_before(new(ir) ir_assignment(new (ir) ir_dereference_variable(return_value), ((ir_return*)jumps[lower])->value, NULL));
378
jumps[lower]->insert_before(new(ir) ir_assignment(new (ir) ir_dereference_variable(return_flag), new (ir) ir_constant(true), NULL));
379
this->loop.may_set_return_flag = true;
623
/* To lower a return, we create a return flag (if the
624
* function doesn't have one already) and add instructions
625
* that: 1. store the return value (if this function has a
626
* non-void return) and 2. set the return flag
628
insert_lowered_return((ir_return*)jumps[lower]);
380
629
if(this->loop.loop) {
630
/* If we are in a loop, replace the return instruction
631
* with a break instruction, and then loop so that the
632
* break instruction can be lowered if necessary.
381
634
ir_loop_jump* lowered = 0;
382
635
lowered = new(ir) ir_loop_jump(ir_loop_jump::jump_break);
636
/* Note: we must update block_records and jumps to
637
* reflect the fact that the control path has been
638
* altered from a return to a break.
383
640
block_records[lower].min_strength = strength_break;
384
641
jumps[lower]->replace_with(lowered);
385
642
jumps[lower] = lowered;
644
/* If we are not in a loop, we then proceed as we would
645
* for a continue statement (set the execute flag to
646
* false to prevent the rest of the function from
387
649
goto lower_continue;
388
651
this->progress = true;
389
652
} else if(jump_strengths[lower] == strength_break) {
390
/* We can't lower to an actual continue because that would execute the increment.
392
* In the lowered code, we instead put the break check between the this->loop body and the increment,
393
* which is impossible with a real continue as defined by the GLSL IR currently.
395
* Smarter options (such as undoing the increment) are possible but it's not worth implementing them,
396
* because if break is lowered, continue is almost surely lowered too.
653
/* To lower a break, we create a break flag (if the loop
654
* doesn't have one already) and add an instruction that
657
* Then we proceed as we would for a continue statement
658
* (set the execute flag to false to prevent the rest of
659
* the loop body from executing).
661
* The visit() function for the loop will ensure that the
662
* break flag is checked after executing the loop body.
398
jumps[lower]->insert_before(new(ir) ir_assignment(new (ir) ir_dereference_variable(this->loop.get_break_flag()), new (ir) ir_constant(true), 0));
664
jumps[lower]->insert_before(create_lowered_break());
399
665
goto lower_continue;
400
666
} else if(jump_strengths[lower] == strength_continue) {
668
/* To lower a continue, we create an execute flag (if the
669
* loop doesn't have one already) and replace the continue
670
* with an instruction that clears it.
672
* Note that this code path gets exercised when lowering
673
* return statements that are not inside a loop, so
674
* this->loop must be initialized even outside of loops.
402
676
ir_variable* execute_flag = this->loop.get_execute_flag();
403
677
jumps[lower]->replace_with(new(ir) ir_assignment(new (ir) ir_dereference_variable(execute_flag), new (ir) ir_constant(false), 0));
678
/* Note: we must update block_records and jumps to reflect
679
* the fact that the control path has been altered to an
680
* instruction that clears the execute flag.
404
682
jumps[lower] = 0;
405
683
block_records[lower].min_strength = strength_always_clears_execute_flag;
406
684
block_records[lower].may_clear_execute_flag = true;
407
685
this->progress = true;
687
/* Let the loop run again, in case the other branch of the
688
* if needs to be lowered too.
412
693
/* move out a jump out if possible */
413
694
if(pull_out_jumps) {
695
/* If one of the branches ends in a jump, and control cannot
696
* fall out the bottom of the other branch, then we can move
697
* the jump after the if.
699
* Set move_out to the branch we are moving a jump out of.
414
701
int move_out = -1;
415
702
if(jumps[0] && block_records[1].min_strength >= strength_continue)
422
709
jumps[move_out]->remove();
423
710
ir->insert_after(jumps[move_out]);
711
/* Note: we must update block_records and jumps to reflect
712
* the fact that the jump has been moved out of the if.
424
714
jumps[move_out] = 0;
425
715
block_records[move_out].min_strength = strength_none;
426
716
this->progress = true;
720
/* Now satisfy the ANALYSIS postcondition by setting
721
* this->block.min_strength and
722
* this->block.may_clear_execute_flag based on the
723
* characteristics of the two branches.
430
725
if(block_records[0].min_strength < block_records[1].min_strength)
431
726
this->block.min_strength = block_records[0].min_strength;
433
728
this->block.min_strength = block_records[1].min_strength;
434
729
this->block.may_clear_execute_flag = this->block.may_clear_execute_flag || block_records[0].may_clear_execute_flag || block_records[1].may_clear_execute_flag;
731
/* Now we need to clean up the instructions that follow the
734
* If those instructions are unreachable, then satisfy the
735
* DEAD_CODE_ELIMINATION postcondition by eliminating them.
736
* Otherwise that postcondition is already satisfied.
436
738
if(this->block.min_strength)
437
739
truncate_after_instruction(ir);
438
740
else if(this->block.may_clear_execute_flag)
742
/* If the "if" instruction might clear the execute flag, then
743
* we need to guard any instructions that follow so that they
744
* are only executed if the execute flag is set.
746
* If one of the branches of the "if" always clears the
747
* execute flag, and the other branch never clears it, then
748
* this is easy: just move all the instructions following the
749
* "if" into the branch that never clears it.
440
751
int move_into = -1;
441
752
if(block_records[0].min_strength && !block_records[1].may_clear_execute_flag)
451
762
if(!next->is_tail_sentinel()) {
452
763
move_outer_block_inside(ir, list);
765
/* If any instructions moved, then we need to visit
766
* them (since they are now inside the "if"). Since
767
* block_records[move_into] is in its default state
768
* (see assertion above), we can safely replace
769
* block_records[move_into] with the result of this
455
773
list.head = next;
456
774
block_records[move_into] = visit_block(&list);
777
* Then we need to re-start our jump lowering, since one
778
* of the instructions we moved might be a jump that
779
* needs to be lowered.
458
781
this->progress = true;
785
/* If we get here, then the simple case didn't apply; we
786
* need to actually guard the instructions that follow.
788
* To avoid creating unnecessarily-deep nesting, first
789
* look through the instructions that follow and unwrap
790
* any instructions that that are already wrapped in the
462
793
ir_instruction* ir_after;
463
794
for(ir_after = (ir_instruction*)ir->get_next(); !ir_after->is_tail_sentinel();)
494
828
virtual void visit(ir_loop *ir)
830
/* Visit the body of the loop, with a fresh data structure in
831
* this->loop so that the analysis we do here won't bleed into
834
* We assume that all code after a loop is reachable from the
835
* loop (see comments on enum jump_strength), so the
836
* DEAD_CODE_ELIMINATION postcondition is automatically
837
* satisfied, as is the block.min_strength portion of the
838
* ANALYSIS postcondition.
840
* The block.may_clear_execute_flag portion of the ANALYSIS
841
* postcondition is automatically satisfied because execute
842
* flags do not propagate outside of loops.
844
* The loop.may_set_return_flag portion of the ANALYSIS
845
* postcondition is handled below.
496
847
++this->function.nesting_depth;
497
848
loop_record saved_loop = this->loop;
498
849
this->loop = loop_record(this->function.signature, ir);
851
/* Recursively lower nested jumps. This satisfies the
852
* CONTAINED_JUMPS_LOWERED postcondition, except in the case of
853
* an unconditional continue or return at the bottom of the
854
* loop, which are handled below.
500
856
block_record body = visit_block(&ir->body_instructions);
858
/* If the loop ends in an unconditional continue, eliminate it
859
* because it is redundant.
861
ir_instruction *ir_last
862
= (ir_instruction *) ir->body_instructions.get_tail();
863
if (get_jump_strength(ir_last) == strength_continue) {
867
/* If the loop ends in an unconditional return, and we are
868
* lowering returns, lower it.
870
if (this->function.lower_return)
871
lower_return_unconditionally(ir_last);
502
873
if(body.min_strength >= strength_break) {
503
/* FINISHME: turn the this->loop into an if, or replace it with its body */
874
/* FINISHME: If the min_strength of the loop body is
875
* strength_break or strength_return, that means that it
876
* isn't a loop at all, since control flow always leaves the
877
* body of the loop via break or return. In principle the
878
* loop could be eliminated in this case. This optimization
879
* is not implemented yet.
506
883
if(this->loop.break_flag) {
884
/* We only get here if we are lowering breaks */
885
assert (lower_break);
887
/* If a break flag was generated while visiting the body of
888
* the loop, then at least one break was lowered, so we need
889
* to generate an if statement at the end of the loop that
890
* does a "break" if the break flag is set. The break we
891
* generate won't violate the CONTAINED_JUMPS_LOWERED
892
* postcondition, because should_lower_jump() always returns
893
* false for a break that happens at the end of a loop.
895
* However, if the loop already ends in a conditional or
896
* unconditional break, then we need to lower that break,
897
* because it won't be at the end of the loop anymore.
899
lower_final_breaks(&ir->body_instructions);
507
901
ir_if* break_if = new(ir) ir_if(new(ir) ir_dereference_variable(this->loop.break_flag));
508
902
break_if->then_instructions.push_tail(new(ir) ir_loop_jump(ir_loop_jump::jump_break));
509
903
ir->body_instructions.push_tail(break_if);
906
/* If the body of the loop may set the return flag, then at
907
* least one return was lowered to a break, so we need to ensure
908
* that the return flag is checked after the body of the loop is
512
911
if(this->loop.may_set_return_flag) {
513
912
assert(this->function.return_flag);
913
/* Generate the if statement to check the return flag */
514
914
ir_if* return_if = new(ir) ir_if(new(ir) ir_dereference_variable(this->function.return_flag));
915
/* Note: we also need to propagate the knowledge that the
916
* return flag may get set to the outer context. This
917
* satisfies the loop.may_set_return_flag part of the
918
* ANALYSIS postcondition.
515
920
saved_loop.may_set_return_flag = true;
516
921
if(saved_loop.loop)
922
/* If this loop is nested inside another one, then the if
923
* statement that we generated should break out of that
924
* loop if the return flag is set. Caller will lower that
925
* break statement if necessary.
517
927
return_if->then_instructions.push_tail(new(ir) ir_loop_jump(ir_loop_jump::jump_break));
929
/* Otherwise, all we need to do is ensure that the
930
* instructions that follow are only executed if the
931
* return flag is clear. We can do that by moving those
932
* instructions into the else clause of the generated if
519
935
move_outer_block_inside(ir, &return_if->else_instructions);
520
936
ir->insert_after(return_if);
530
946
assert(!this->function.signature);
531
947
assert(!this->loop.loop);
950
if (strcmp(ir->function_name(), "main") == 0)
951
lower_return = lower_main_return;
953
lower_return = lower_sub_return;
533
955
function_record saved_function = this->function;
534
956
loop_record saved_loop = this->loop;
535
this->function = function_record(ir);
957
this->function = function_record(ir, lower_return);
536
958
this->loop = loop_record(ir);
538
960
assert(!this->loop.loop);
962
/* Visit the body of the function to lower any jumps that occur
963
* in it, except possibly an unconditional return statement at
539
966
visit_block(&ir->body);
968
/* If the body ended in an unconditional return of non-void,
969
* then we don't need to lower it because it's the one canonical
972
* If the body ended in a return of void, eliminate it because
975
if (ir->return_type->is_void() &&
976
get_jump_strength((ir_instruction *) ir->body.get_tail())) {
977
ir_jump *jump = (ir_jump *) ir->body.get_tail();
978
assert (jump->ir_type == ir_type_return);
541
982
if(this->function.return_value)
542
983
ir->body.push_tail(new(ir) ir_return(new (ir) ir_dereference_variable(this->function.return_value)));
added
removed
src/glsl/lower_jumps.cpp
