Mercurial > hg > CbC > CbC_gcc
comparison gcc/tree-ssa-loop-split.c @ 145:1830386684a0
gcc-9.2.0
author | anatofuz |
---|---|
date | Thu, 13 Feb 2020 11:34:05 +0900 |
parents | 84e7813d76e9 |
children |
comparison
equal
deleted
inserted
replaced
131:84e7813d76e9 | 145:1830386684a0 |
---|---|
1 /* Loop splitting. | 1 /* Loop splitting. |
2 Copyright (C) 2015-2018 Free Software Foundation, Inc. | 2 Copyright (C) 2015-2020 Free Software Foundation, Inc. |
3 | 3 |
4 This file is part of GCC. | 4 This file is part of GCC. |
5 | 5 |
6 GCC is free software; you can redistribute it and/or modify it | 6 GCC is free software; you can redistribute it and/or modify it |
7 under the terms of the GNU General Public License as published by the | 7 under the terms of the GNU General Public License as published by the |
30 #include "tree-ssa.h" | 30 #include "tree-ssa.h" |
31 #include "tree-ssa-loop-niter.h" | 31 #include "tree-ssa-loop-niter.h" |
32 #include "tree-ssa-loop.h" | 32 #include "tree-ssa-loop.h" |
33 #include "tree-ssa-loop-manip.h" | 33 #include "tree-ssa-loop-manip.h" |
34 #include "tree-into-ssa.h" | 34 #include "tree-into-ssa.h" |
35 #include "tree-inline.h" | |
36 #include "tree-cfgcleanup.h" | |
35 #include "cfgloop.h" | 37 #include "cfgloop.h" |
36 #include "tree-scalar-evolution.h" | 38 #include "tree-scalar-evolution.h" |
37 #include "gimple-iterator.h" | 39 #include "gimple-iterator.h" |
38 #include "gimple-pretty-print.h" | 40 #include "gimple-pretty-print.h" |
39 #include "cfghooks.h" | 41 #include "cfghooks.h" |
40 #include "gimple-fold.h" | 42 #include "gimple-fold.h" |
41 #include "gimplify-me.h" | 43 #include "gimplify-me.h" |
42 | 44 |
43 /* This file implements loop splitting, i.e. transformation of loops like | 45 /* This file implements two kinds of loop splitting. |
46 | |
47 One transformation of loops like: | |
44 | 48 |
45 for (i = 0; i < 100; i++) | 49 for (i = 0; i < 100; i++) |
46 { | 50 { |
47 if (i < 50) | 51 if (i < 50) |
48 A; | 52 A; |
68 is true on one side of the iteration space and false on the other, | 72 is true on one side of the iteration space and false on the other, |
69 and the split point can be computed. If so, also return the border | 73 and the split point can be computed. If so, also return the border |
70 point in *BORDER and the comparison induction variable in IV. */ | 74 point in *BORDER and the comparison induction variable in IV. */ |
71 | 75 |
72 static tree | 76 static tree |
73 split_at_bb_p (struct loop *loop, basic_block bb, tree *border, affine_iv *iv) | 77 split_at_bb_p (class loop *loop, basic_block bb, tree *border, affine_iv *iv) |
74 { | 78 { |
75 gimple *last; | 79 gimple *last; |
76 gcond *stmt; | 80 gcond *stmt; |
77 affine_iv iv2; | 81 affine_iv iv2; |
78 | 82 |
100 if (loop_exits_from_bb_p (loop, bb)) | 104 if (loop_exits_from_bb_p (loop, bb)) |
101 return NULL_TREE; | 105 return NULL_TREE; |
102 | 106 |
103 tree op0 = gimple_cond_lhs (stmt); | 107 tree op0 = gimple_cond_lhs (stmt); |
104 tree op1 = gimple_cond_rhs (stmt); | 108 tree op1 = gimple_cond_rhs (stmt); |
105 struct loop *useloop = loop_containing_stmt (stmt); | 109 class loop *useloop = loop_containing_stmt (stmt); |
106 | 110 |
107 if (!simple_iv (loop, useloop, op0, iv, false)) | 111 if (!simple_iv (loop, useloop, op0, iv, false)) |
108 return NULL_TREE; | 112 return NULL_TREE; |
109 if (!simple_iv (loop, useloop, op1, &iv2, false)) | 113 if (!simple_iv (loop, useloop, op1, &iv2, false)) |
110 return NULL_TREE; | 114 return NULL_TREE; |
148 (a post-increment IV) and NEWBOUND (the comparator) adjust the loop | 152 (a post-increment IV) and NEWBOUND (the comparator) adjust the loop |
149 exit test statement to loop back only if the GUARD statement will | 153 exit test statement to loop back only if the GUARD statement will |
150 also be true/false in the next iteration. */ | 154 also be true/false in the next iteration. */ |
151 | 155 |
152 static void | 156 static void |
153 patch_loop_exit (struct loop *loop, gcond *guard, tree nextval, tree newbound, | 157 patch_loop_exit (class loop *loop, gcond *guard, tree nextval, tree newbound, |
154 bool initial_true) | 158 bool initial_true) |
155 { | 159 { |
156 edge exit = single_exit (loop); | 160 edge exit = single_exit (loop); |
157 gcond *stmt = as_a <gcond *> (last_stmt (exit->src)); | 161 gcond *stmt = as_a <gcond *> (last_stmt (exit->src)); |
158 gimple_cond_set_condition (stmt, gimple_cond_code (guard), | 162 gimple_cond_set_condition (stmt, gimple_cond_code (guard), |
179 /* Give an induction variable GUARD_IV, and its affine descriptor IV, | 183 /* Give an induction variable GUARD_IV, and its affine descriptor IV, |
180 find the loop phi node in LOOP defining it directly, or create | 184 find the loop phi node in LOOP defining it directly, or create |
181 such phi node. Return that phi node. */ | 185 such phi node. Return that phi node. */ |
182 | 186 |
183 static gphi * | 187 static gphi * |
184 find_or_create_guard_phi (struct loop *loop, tree guard_iv, affine_iv * /*iv*/) | 188 find_or_create_guard_phi (class loop *loop, tree guard_iv, affine_iv * /*iv*/) |
185 { | 189 { |
186 gimple *def = SSA_NAME_DEF_STMT (guard_iv); | 190 gimple *def = SSA_NAME_DEF_STMT (guard_iv); |
187 gphi *phi; | 191 gphi *phi; |
188 if ((phi = dyn_cast <gphi *> (def)) | 192 if ((phi = dyn_cast <gphi *> (def)) |
189 && gimple_bb (phi) == loop->header) | 193 && gimple_bb (phi) == loop->header) |
195 | 199 |
196 /* Returns true if the exit values of all loop phi nodes can be | 200 /* Returns true if the exit values of all loop phi nodes can be |
197 determined easily (i.e. that connect_loop_phis can determine them). */ | 201 determined easily (i.e. that connect_loop_phis can determine them). */ |
198 | 202 |
199 static bool | 203 static bool |
200 easy_exit_values (struct loop *loop) | 204 easy_exit_values (class loop *loop) |
201 { | 205 { |
202 edge exit = single_exit (loop); | 206 edge exit = single_exit (loop); |
203 edge latch = loop_latch_edge (loop); | 207 edge latch = loop_latch_edge (loop); |
204 gphi_iterator psi; | 208 gphi_iterator psi; |
205 | 209 |
227 phi nodes are either the original ones or those at the exit | 231 phi nodes are either the original ones or those at the exit |
228 of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting | 232 of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting |
229 this. The loops need to fulfill easy_exit_values(). */ | 233 this. The loops need to fulfill easy_exit_values(). */ |
230 | 234 |
231 static void | 235 static void |
232 connect_loop_phis (struct loop *loop1, struct loop *loop2, edge new_e) | 236 connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e) |
233 { | 237 { |
234 basic_block rest = loop_preheader_edge (loop2)->src; | 238 basic_block rest = loop_preheader_edge (loop2)->src; |
235 gcc_assert (new_e->dest == rest); | 239 gcc_assert (new_e->dest == rest); |
236 edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e); | 240 edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e); |
237 | 241 |
321 The function returns the new edge cond->pre2. | 325 The function returns the new edge cond->pre2. |
322 | 326 |
323 This doesn't update the SSA form, see connect_loop_phis for that. */ | 327 This doesn't update the SSA form, see connect_loop_phis for that. */ |
324 | 328 |
325 static edge | 329 static edge |
326 connect_loops (struct loop *loop1, struct loop *loop2) | 330 connect_loops (class loop *loop1, class loop *loop2) |
327 { | 331 { |
328 edge exit = single_exit (loop1); | 332 edge exit = single_exit (loop1); |
329 basic_block skip_bb = split_edge (exit); | 333 basic_block skip_bb = split_edge (exit); |
330 gcond *skip_stmt; | 334 gcond *skip_stmt; |
331 gimple_stmt_iterator gsi; | 335 gimple_stmt_iterator gsi; |
385 Depending on the direction of the IVs and if the exit tests | 389 Depending on the direction of the IVs and if the exit tests |
386 are strict or non-strict we need to use MIN or MAX, | 390 are strict or non-strict we need to use MIN or MAX, |
387 and add or subtract 1. This routine computes newend above. */ | 391 and add or subtract 1. This routine computes newend above. */ |
388 | 392 |
389 static tree | 393 static tree |
390 compute_new_first_bound (gimple_seq *stmts, struct tree_niter_desc *niter, | 394 compute_new_first_bound (gimple_seq *stmts, class tree_niter_desc *niter, |
391 tree border, | 395 tree border, |
392 enum tree_code guard_code, tree guard_init) | 396 enum tree_code guard_code, tree guard_init) |
393 { | 397 { |
394 /* The niter structure contains the after-increment IV, we need | 398 /* The niter structure contains the after-increment IV, we need |
395 the loop-enter base, so subtract STEP once. */ | 399 the loop-enter base, so subtract STEP once. */ |
485 splits the iteration space into two loops. Returns true if the | 489 splits the iteration space into two loops. Returns true if the |
486 loop was split. NITER must contain the iteration descriptor for the | 490 loop was split. NITER must contain the iteration descriptor for the |
487 single exit of LOOP. */ | 491 single exit of LOOP. */ |
488 | 492 |
489 static bool | 493 static bool |
490 split_loop (struct loop *loop1, struct tree_niter_desc *niter) | 494 split_loop (class loop *loop1) |
491 { | 495 { |
496 class tree_niter_desc niter; | |
492 basic_block *bbs; | 497 basic_block *bbs; |
493 unsigned i; | 498 unsigned i; |
494 bool changed = false; | 499 bool changed = false; |
495 tree guard_iv; | 500 tree guard_iv; |
496 tree border = NULL_TREE; | 501 tree border = NULL_TREE; |
497 affine_iv iv; | 502 affine_iv iv; |
498 | 503 |
504 if (!single_exit (loop1) | |
505 /* ??? We could handle non-empty latches when we split the latch edge | |
506 (not the exit edge), and put the new exit condition in the new block. | |
507 OTOH this executes some code unconditionally that might have been | |
508 skipped by the original exit before. */ | |
509 || !empty_block_p (loop1->latch) | |
510 || !easy_exit_values (loop1) | |
511 || !number_of_iterations_exit (loop1, single_exit (loop1), &niter, | |
512 false, true) | |
513 || niter.cmp == ERROR_MARK | |
514 /* We can't yet handle loops controlled by a != predicate. */ | |
515 || niter.cmp == NE_EXPR) | |
516 return false; | |
517 | |
499 bbs = get_loop_body (loop1); | 518 bbs = get_loop_body (loop1); |
519 | |
520 if (!can_copy_bbs_p (bbs, loop1->num_nodes)) | |
521 { | |
522 free (bbs); | |
523 return false; | |
524 } | |
500 | 525 |
501 /* Find a splitting opportunity. */ | 526 /* Find a splitting opportunity. */ |
502 for (i = 0; i < loop1->num_nodes; i++) | 527 for (i = 0; i < loop1->num_nodes; i++) |
503 if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv))) | 528 if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv))) |
504 { | 529 { |
505 /* Handling opposite steps is not implemented yet. Neither | 530 /* Handling opposite steps is not implemented yet. Neither |
506 is handling different step sizes. */ | 531 is handling different step sizes. */ |
507 if ((tree_int_cst_sign_bit (iv.step) | 532 if ((tree_int_cst_sign_bit (iv.step) |
508 != tree_int_cst_sign_bit (niter->control.step)) | 533 != tree_int_cst_sign_bit (niter.control.step)) |
509 || !tree_int_cst_equal (iv.step, niter->control.step)) | 534 || !tree_int_cst_equal (iv.step, niter.control.step)) |
510 continue; | 535 continue; |
511 | 536 |
512 /* Find a loop PHI node that defines guard_iv directly, | 537 /* Find a loop PHI node that defines guard_iv directly, |
513 or create one doing that. */ | 538 or create one doing that. */ |
514 gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv); | 539 gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv); |
555 /* Now version the loop, placing loop2 after loop1 connecting | 580 /* Now version the loop, placing loop2 after loop1 connecting |
556 them, and fix up SSA form for that. */ | 581 them, and fix up SSA form for that. */ |
557 initialize_original_copy_tables (); | 582 initialize_original_copy_tables (); |
558 basic_block cond_bb; | 583 basic_block cond_bb; |
559 | 584 |
560 struct loop *loop2 = loop_version (loop1, cond, &cond_bb, | 585 class loop *loop2 = loop_version (loop1, cond, &cond_bb, |
561 profile_probability::always (), | 586 profile_probability::always (), |
562 profile_probability::always (), | 587 profile_probability::always (), |
563 profile_probability::always (), | 588 profile_probability::always (), |
564 profile_probability::always (), | 589 profile_probability::always (), |
565 true); | 590 true); |
573 exactly those that the first loop didn't do, but the | 598 exactly those that the first loop didn't do, but the |
574 iteration space of the first loop is still the original one. | 599 iteration space of the first loop is still the original one. |
575 Compute the new bound for the guarding IV and patch the | 600 Compute the new bound for the guarding IV and patch the |
576 loop exit to use it instead of original IV and bound. */ | 601 loop exit to use it instead of original IV and bound. */ |
577 gimple_seq stmts = NULL; | 602 gimple_seq stmts = NULL; |
578 tree newend = compute_new_first_bound (&stmts, niter, border, | 603 tree newend = compute_new_first_bound (&stmts, &niter, border, |
579 guard_code, guard_init); | 604 guard_code, guard_init); |
580 if (stmts) | 605 if (stmts) |
581 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1), | 606 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1), |
582 stmts); | 607 stmts); |
583 tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1)); | 608 tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1)); |
610 | 635 |
611 free (bbs); | 636 free (bbs); |
612 return changed; | 637 return changed; |
613 } | 638 } |
614 | 639 |
640 /* Another transformation of loops like: | |
641 | |
642 for (i = INIT (); CHECK (i); i = NEXT ()) | |
643 { | |
644 if (expr (a_1, a_2, ..., a_n)) // expr is pure | |
645 a_j = ...; // change at least one a_j | |
646 else | |
647 S; // not change any a_j | |
648 } | |
649 | |
650 into: | |
651 | |
652 for (i = INIT (); CHECK (i); i = NEXT ()) | |
653 { | |
654 if (expr (a_1, a_2, ..., a_n)) | |
655 a_j = ...; | |
656 else | |
657 { | |
658 S; | |
659 i = NEXT (); | |
660 break; | |
661 } | |
662 } | |
663 | |
664 for (; CHECK (i); i = NEXT ()) | |
665 { | |
666 S; | |
667 } | |
668 | |
669 */ | |
670 | |
671 /* Data structure to hold temporary information during loop split upon | |
672 semi-invariant conditional statement. */ | |
673 class split_info { | |
674 public: | |
675 /* Array of all basic blocks in a loop, returned by get_loop_body(). */ | |
676 basic_block *bbs; | |
677 | |
678 /* All memory store/clobber statements in a loop. */ | |
679 auto_vec<gimple *> memory_stores; | |
680 | |
681 /* Whether above memory stores vector has been filled. */ | |
682 int need_init; | |
683 | |
684 /* Control dependencies of basic blocks in a loop. */ | |
685 auto_vec<hash_set<basic_block> *> control_deps; | |
686 | |
687 split_info () : bbs (NULL), need_init (true) { } | |
688 | |
689 ~split_info () | |
690 { | |
691 if (bbs) | |
692 free (bbs); | |
693 | |
694 for (unsigned i = 0; i < control_deps.length (); i++) | |
695 delete control_deps[i]; | |
696 } | |
697 }; | |
698 | |
699 /* Find all statements with memory-write effect in LOOP, including memory | |
700 store and non-pure function call, and keep those in a vector. This work | |
701 is only done one time, for the vector should be constant during analysis | |
702 stage of semi-invariant condition. */ | |
703 | |
704 static void | |
705 find_vdef_in_loop (struct loop *loop) | |
706 { | |
707 split_info *info = (split_info *) loop->aux; | |
708 gphi *vphi = get_virtual_phi (loop->header); | |
709 | |
710 /* Indicate memory store vector has been filled. */ | |
711 info->need_init = false; | |
712 | |
713 /* If loop contains memory operation, there must be a virtual PHI node in | |
714 loop header basic block. */ | |
715 if (vphi == NULL) | |
716 return; | |
717 | |
718 /* All virtual SSA names inside the loop are connected to be a cyclic | |
719 graph via virtual PHI nodes. The virtual PHI node in loop header just | |
720 links the first and the last virtual SSA names, by using the last as | |
721 PHI operand to define the first. */ | |
722 const edge latch = loop_latch_edge (loop); | |
723 const tree first = gimple_phi_result (vphi); | |
724 const tree last = PHI_ARG_DEF_FROM_EDGE (vphi, latch); | |
725 | |
726 /* The virtual SSA cyclic graph might consist of only one SSA name, who | |
727 is defined by itself. | |
728 | |
729 .MEM_1 = PHI <.MEM_2(loop entry edge), .MEM_1(latch edge)> | |
730 | |
731 This means the loop contains only memory loads, so we can skip it. */ | |
732 if (first == last) | |
733 return; | |
734 | |
735 auto_vec<gimple *> other_stores; | |
736 auto_vec<tree> worklist; | |
737 auto_bitmap visited; | |
738 | |
739 bitmap_set_bit (visited, SSA_NAME_VERSION (first)); | |
740 bitmap_set_bit (visited, SSA_NAME_VERSION (last)); | |
741 worklist.safe_push (last); | |
742 | |
743 do | |
744 { | |
745 tree vuse = worklist.pop (); | |
746 gimple *stmt = SSA_NAME_DEF_STMT (vuse); | |
747 | |
748 /* We mark the first and last SSA names as visited at the beginning, | |
749 and reversely start the process from the last SSA name towards the | |
750 first, which ensures that this do-while will not touch SSA names | |
751 defined outside the loop. */ | |
752 gcc_assert (gimple_bb (stmt) | |
753 && flow_bb_inside_loop_p (loop, gimple_bb (stmt))); | |
754 | |
755 if (gimple_code (stmt) == GIMPLE_PHI) | |
756 { | |
757 gphi *phi = as_a <gphi *> (stmt); | |
758 | |
759 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) | |
760 { | |
761 tree arg = gimple_phi_arg_def (stmt, i); | |
762 | |
763 if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg))) | |
764 worklist.safe_push (arg); | |
765 } | |
766 } | |
767 else | |
768 { | |
769 tree prev = gimple_vuse (stmt); | |
770 | |
771 /* Non-pure call statement is conservatively assumed to impact all | |
772 memory locations. So place call statements ahead of other memory | |
773 stores in the vector with an idea of of using them as shortcut | |
774 terminators to memory alias analysis. */ | |
775 if (gimple_code (stmt) == GIMPLE_CALL) | |
776 info->memory_stores.safe_push (stmt); | |
777 else | |
778 other_stores.safe_push (stmt); | |
779 | |
780 if (bitmap_set_bit (visited, SSA_NAME_VERSION (prev))) | |
781 worklist.safe_push (prev); | |
782 } | |
783 } while (!worklist.is_empty ()); | |
784 | |
785 info->memory_stores.safe_splice (other_stores); | |
786 } | |
787 | |
788 /* Two basic blocks have equivalent control dependency if one dominates to | |
789 the other, and it is post-dominated by the latter. Given a basic block | |
790 BB in LOOP, find farest equivalent dominating basic block. For BB, there | |
791 is a constraint that BB does not post-dominate loop header of LOOP, this | |
792 means BB is control-dependent on at least one basic block in LOOP. */ | |
793 | |
794 static basic_block | |
795 get_control_equiv_head_block (struct loop *loop, basic_block bb) | |
796 { | |
797 while (!bb->aux) | |
798 { | |
799 basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); | |
800 | |
801 gcc_checking_assert (dom_bb && flow_bb_inside_loop_p (loop, dom_bb)); | |
802 | |
803 if (!dominated_by_p (CDI_POST_DOMINATORS, dom_bb, bb)) | |
804 break; | |
805 | |
806 bb = dom_bb; | |
807 } | |
808 return bb; | |
809 } | |
810 | |
811 /* Given a BB in LOOP, find out all basic blocks in LOOP that BB is control- | |
812 dependent on. */ | |
813 | |
814 static hash_set<basic_block> * | |
815 find_control_dep_blocks (struct loop *loop, basic_block bb) | |
816 { | |
817 /* BB has same control dependency as loop header, then it is not control- | |
818 dependent on any basic block in LOOP. */ | |
819 if (dominated_by_p (CDI_POST_DOMINATORS, loop->header, bb)) | |
820 return NULL; | |
821 | |
822 basic_block equiv_head = get_control_equiv_head_block (loop, bb); | |
823 | |
824 if (equiv_head->aux) | |
825 { | |
826 /* There is a basic block containing control dependency equivalent | |
827 to BB. No need to recompute that, and also set this information | |
828 to other equivalent basic blocks. */ | |
829 for (; bb != equiv_head; | |
830 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
831 bb->aux = equiv_head->aux; | |
832 return (hash_set<basic_block> *) equiv_head->aux; | |
833 } | |
834 | |
835 /* A basic block X is control-dependent on another Y iff there exists | |
836 a path from X to Y, in which every basic block other than X and Y | |
837 is post-dominated by Y, but X is not post-dominated by Y. | |
838 | |
839 According to this rule, traverse basic blocks in the loop backwards | |
840 starting from BB, if a basic block is post-dominated by BB, extend | |
841 current post-dominating path to this block, otherwise it is another | |
842 one that BB is control-dependent on. */ | |
843 | |
844 auto_vec<basic_block> pdom_worklist; | |
845 hash_set<basic_block> pdom_visited; | |
846 hash_set<basic_block> *dep_bbs = new hash_set<basic_block>; | |
847 | |
848 pdom_worklist.safe_push (equiv_head); | |
849 | |
850 do | |
851 { | |
852 basic_block pdom_bb = pdom_worklist.pop (); | |
853 edge_iterator ei; | |
854 edge e; | |
855 | |
856 if (pdom_visited.add (pdom_bb)) | |
857 continue; | |
858 | |
859 FOR_EACH_EDGE (e, ei, pdom_bb->preds) | |
860 { | |
861 basic_block pred_bb = e->src; | |
862 | |
863 if (!dominated_by_p (CDI_POST_DOMINATORS, pred_bb, bb)) | |
864 { | |
865 dep_bbs->add (pred_bb); | |
866 continue; | |
867 } | |
868 | |
869 pred_bb = get_control_equiv_head_block (loop, pred_bb); | |
870 | |
871 if (pdom_visited.contains (pred_bb)) | |
872 continue; | |
873 | |
874 if (!pred_bb->aux) | |
875 { | |
876 pdom_worklist.safe_push (pred_bb); | |
877 continue; | |
878 } | |
879 | |
880 /* If control dependency of basic block is available, fast extend | |
881 post-dominating path using the information instead of advancing | |
882 forward step-by-step. */ | |
883 hash_set<basic_block> *pred_dep_bbs | |
884 = (hash_set<basic_block> *) pred_bb->aux; | |
885 | |
886 for (hash_set<basic_block>::iterator iter = pred_dep_bbs->begin (); | |
887 iter != pred_dep_bbs->end (); ++iter) | |
888 { | |
889 basic_block pred_dep_bb = *iter; | |
890 | |
891 /* Basic blocks can either be in control dependency of BB, or | |
892 must be post-dominated by BB, if so, extend the path from | |
893 these basic blocks. */ | |
894 if (!dominated_by_p (CDI_POST_DOMINATORS, pred_dep_bb, bb)) | |
895 dep_bbs->add (pred_dep_bb); | |
896 else if (!pdom_visited.contains (pred_dep_bb)) | |
897 pdom_worklist.safe_push (pred_dep_bb); | |
898 } | |
899 } | |
900 } while (!pdom_worklist.is_empty ()); | |
901 | |
902 /* Record computed control dependencies in loop so that we can reach them | |
903 when reclaiming resources. */ | |
904 ((split_info *) loop->aux)->control_deps.safe_push (dep_bbs); | |
905 | |
906 /* Associate control dependence with related equivalent basic blocks. */ | |
907 for (equiv_head->aux = dep_bbs; bb != equiv_head; | |
908 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
909 bb->aux = dep_bbs; | |
910 | |
911 return dep_bbs; | |
912 } | |
913 | |
914 /* Forward declaration */ | |
915 | |
916 static bool | |
917 stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt, | |
918 const_basic_block skip_head, | |
919 hash_map<gimple *, bool> &stmt_stat); | |
920 | |
921 /* Given STMT, memory load or pure call statement, check whether it is impacted | |
922 by some memory store in LOOP, excluding trace starting from SKIP_HEAD (the | |
923 trace is composed of SKIP_HEAD and those basic block dominated by it, always | |
924 corresponds to one branch of a conditional statement). If SKIP_HEAD is | |
925 NULL, all basic blocks of LOOP are checked. */ | |
926 | |
927 static bool | |
928 vuse_semi_invariant_p (struct loop *loop, gimple *stmt, | |
929 const_basic_block skip_head) | |
930 { | |
931 split_info *info = (split_info *) loop->aux; | |
932 tree rhs = NULL_TREE; | |
933 ao_ref ref; | |
934 gimple *store; | |
935 unsigned i; | |
936 | |
937 /* Collect memory store/clobber statements if haven't done that. */ | |
938 if (info->need_init) | |
939 find_vdef_in_loop (loop); | |
940 | |
941 if (is_gimple_assign (stmt)) | |
942 rhs = gimple_assign_rhs1 (stmt); | |
943 | |
944 ao_ref_init (&ref, rhs); | |
945 | |
946 FOR_EACH_VEC_ELT (info->memory_stores, i, store) | |
947 { | |
948 /* Skip basic blocks dominated by SKIP_HEAD, if non-NULL. */ | |
949 if (skip_head | |
950 && dominated_by_p (CDI_DOMINATORS, gimple_bb (store), skip_head)) | |
951 continue; | |
952 | |
953 if (!ref.ref || stmt_may_clobber_ref_p_1 (store, &ref)) | |
954 return false; | |
955 } | |
956 | |
957 return true; | |
958 } | |
959 | |
960 /* Suppose one condition branch, led by SKIP_HEAD, is not executed since | |
961 certain iteration of LOOP, check whether an SSA name (NAME) remains | |
962 unchanged in next iteration. We call this characteristic semi- | |
963 invariantness. SKIP_HEAD might be NULL, if so, nothing excluded, all basic | |
964 blocks and control flows in the loop will be considered. Semi-invariant | |
965 state of checked statement is cached in hash map STMT_STAT to avoid | |
966 redundant computation in possible following re-check. */ | |
967 | |
968 static inline bool | |
969 ssa_semi_invariant_p (struct loop *loop, tree name, | |
970 const_basic_block skip_head, | |
971 hash_map<gimple *, bool> &stmt_stat) | |
972 { | |
973 gimple *def = SSA_NAME_DEF_STMT (name); | |
974 const_basic_block def_bb = gimple_bb (def); | |
975 | |
976 /* An SSA name defined outside loop is definitely semi-invariant. */ | |
977 if (!def_bb || !flow_bb_inside_loop_p (loop, def_bb)) | |
978 return true; | |
979 | |
980 return stmt_semi_invariant_p_1 (loop, def, skip_head, stmt_stat); | |
981 } | |
982 | |
983 /* Check whether a loop iteration PHI node (LOOP_PHI) defines a value that is | |
984 semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL), | |
985 are excluded from LOOP. */ | |
986 | |
987 static bool | |
988 loop_iter_phi_semi_invariant_p (struct loop *loop, gphi *loop_phi, | |
989 const_basic_block skip_head) | |
990 { | |
991 const_edge latch = loop_latch_edge (loop); | |
992 tree name = gimple_phi_result (loop_phi); | |
993 tree from = PHI_ARG_DEF_FROM_EDGE (loop_phi, latch); | |
994 | |
995 gcc_checking_assert (from); | |
996 | |
997 /* Loop iteration PHI node locates in loop header, and it has two source | |
998 operands, one is an initial value coming from outside the loop, the other | |
999 is a value through latch of the loop, which is derived in last iteration, | |
1000 we call the latter latch value. From the PHI node to definition of latch | |
1001 value, if excluding branch trace starting from SKIP_HEAD, except copy- | |
1002 assignment or likewise, there is no other kind of value redefinition, SSA | |
1003 name defined by the PHI node is semi-invariant. | |
1004 | |
1005 loop entry | |
1006 | .--- latch ---. | |
1007 | | | | |
1008 v v | | |
1009 x_1 = PHI <x_0, x_3> | | |
1010 | | | |
1011 v | | |
1012 .------- if (cond) -------. | | |
1013 | | | | |
1014 | [ SKIP ] | | |
1015 | | | | |
1016 | x_2 = ... | | |
1017 | | | | |
1018 '---- T ---->.<---- F ----' | | |
1019 | | | |
1020 v | | |
1021 x_3 = PHI <x_1, x_2> | | |
1022 | | | |
1023 '----------------------' | |
1024 | |
1025 Suppose in certain iteration, execution flow in above graph goes through | |
1026 true branch, which means that one source value to define x_3 in false | |
1027 branch (x_2) is skipped, x_3 only comes from x_1, and x_1 in next | |
1028 iterations is defined by x_3, we know that x_1 will never changed if COND | |
1029 always chooses true branch from then on. */ | |
1030 | |
1031 while (from != name) | |
1032 { | |
1033 /* A new value comes from a CONSTANT. */ | |
1034 if (TREE_CODE (from) != SSA_NAME) | |
1035 return false; | |
1036 | |
1037 gimple *stmt = SSA_NAME_DEF_STMT (from); | |
1038 const_basic_block bb = gimple_bb (stmt); | |
1039 | |
1040 /* A new value comes from outside the loop. */ | |
1041 if (!bb || !flow_bb_inside_loop_p (loop, bb)) | |
1042 return false; | |
1043 | |
1044 from = NULL_TREE; | |
1045 | |
1046 if (gimple_code (stmt) == GIMPLE_PHI) | |
1047 { | |
1048 gphi *phi = as_a <gphi *> (stmt); | |
1049 | |
1050 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) | |
1051 { | |
1052 if (skip_head) | |
1053 { | |
1054 const_edge e = gimple_phi_arg_edge (phi, i); | |
1055 | |
1056 /* Don't consider redefinitions in excluded basic blocks. */ | |
1057 if (dominated_by_p (CDI_DOMINATORS, e->src, skip_head)) | |
1058 continue; | |
1059 } | |
1060 | |
1061 tree arg = gimple_phi_arg_def (phi, i); | |
1062 | |
1063 if (!from) | |
1064 from = arg; | |
1065 else if (!operand_equal_p (from, arg, 0)) | |
1066 /* There are more than one source operands that provide | |
1067 different values to the SSA name, it is variant. */ | |
1068 return false; | |
1069 } | |
1070 } | |
1071 else if (gimple_code (stmt) == GIMPLE_ASSIGN) | |
1072 { | |
1073 /* For simple value copy, check its rhs instead. */ | |
1074 if (gimple_assign_ssa_name_copy_p (stmt)) | |
1075 from = gimple_assign_rhs1 (stmt); | |
1076 } | |
1077 | |
1078 /* Any other kind of definition is deemed to introduce a new value | |
1079 to the SSA name. */ | |
1080 if (!from) | |
1081 return false; | |
1082 } | |
1083 return true; | |
1084 } | |
1085 | |
1086 /* Check whether conditional predicates that BB is control-dependent on, are | |
1087 semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL), | |
1088 are excluded from LOOP. Semi-invariant state of checked statement is cached | |
1089 in hash map STMT_STAT. */ | |
1090 | |
1091 static bool | |
1092 control_dep_semi_invariant_p (struct loop *loop, basic_block bb, | |
1093 const_basic_block skip_head, | |
1094 hash_map<gimple *, bool> &stmt_stat) | |
1095 { | |
1096 hash_set<basic_block> *dep_bbs = find_control_dep_blocks (loop, bb); | |
1097 | |
1098 if (!dep_bbs) | |
1099 return true; | |
1100 | |
1101 for (hash_set<basic_block>::iterator iter = dep_bbs->begin (); | |
1102 iter != dep_bbs->end (); ++iter) | |
1103 { | |
1104 gimple *last = last_stmt (*iter); | |
1105 | |
1106 if (!last) | |
1107 return false; | |
1108 | |
1109 /* Only check condition predicates. */ | |
1110 if (gimple_code (last) != GIMPLE_COND | |
1111 && gimple_code (last) != GIMPLE_SWITCH) | |
1112 return false; | |
1113 | |
1114 if (!stmt_semi_invariant_p_1 (loop, last, skip_head, stmt_stat)) | |
1115 return false; | |
1116 } | |
1117 | |
1118 return true; | |
1119 } | |
1120 | |
1121 /* Check whether STMT is semi-invariant in LOOP, iff all its operands are | |
1122 semi-invariant, consequently, all its defined values are semi-invariant. | |
1123 Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. | |
1124 Semi-invariant state of checked statement is cached in hash map | |
1125 STMT_STAT. */ | |
1126 | |
1127 static bool | |
1128 stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt, | |
1129 const_basic_block skip_head, | |
1130 hash_map<gimple *, bool> &stmt_stat) | |
1131 { | |
1132 bool existed; | |
1133 bool &invar = stmt_stat.get_or_insert (stmt, &existed); | |
1134 | |
1135 if (existed) | |
1136 return invar; | |
1137 | |
1138 /* A statement might depend on itself, which is treated as variant. So set | |
1139 state of statement under check to be variant to ensure that. */ | |
1140 invar = false; | |
1141 | |
1142 if (gimple_code (stmt) == GIMPLE_PHI) | |
1143 { | |
1144 gphi *phi = as_a <gphi *> (stmt); | |
1145 | |
1146 if (gimple_bb (stmt) == loop->header) | |
1147 { | |
1148 invar = loop_iter_phi_semi_invariant_p (loop, phi, skip_head); | |
1149 return invar; | |
1150 } | |
1151 | |
1152 /* For a loop PHI node that does not locate in loop header, it is semi- | |
1153 invariant only if two conditions are met. The first is its source | |
1154 values are derived from CONSTANT (including loop-invariant value), or | |
1155 from SSA name defined by semi-invariant loop iteration PHI node. The | |
1156 second is its source incoming edges are control-dependent on semi- | |
1157 invariant conditional predicates. */ | |
1158 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) | |
1159 { | |
1160 const_edge e = gimple_phi_arg_edge (phi, i); | |
1161 tree arg = gimple_phi_arg_def (phi, i); | |
1162 | |
1163 if (TREE_CODE (arg) == SSA_NAME) | |
1164 { | |
1165 if (!ssa_semi_invariant_p (loop, arg, skip_head, stmt_stat)) | |
1166 return false; | |
1167 | |
1168 /* If source value is defined in location from where the source | |
1169 edge comes in, no need to check control dependency again | |
1170 since this has been done in above SSA name check stage. */ | |
1171 if (e->src == gimple_bb (SSA_NAME_DEF_STMT (arg))) | |
1172 continue; | |
1173 } | |
1174 | |
1175 if (!control_dep_semi_invariant_p (loop, e->src, skip_head, | |
1176 stmt_stat)) | |
1177 return false; | |
1178 } | |
1179 } | |
1180 else | |
1181 { | |
1182 ssa_op_iter iter; | |
1183 tree use; | |
1184 | |
1185 /* Volatile memory load or return of normal (non-const/non-pure) call | |
1186 should not be treated as constant in each iteration of loop. */ | |
1187 if (gimple_has_side_effects (stmt)) | |
1188 return false; | |
1189 | |
1190 /* Check if any memory store may kill memory load at this place. */ | |
1191 if (gimple_vuse (stmt) && !vuse_semi_invariant_p (loop, stmt, skip_head)) | |
1192 return false; | |
1193 | |
1194 /* Although operand of a statement might be SSA name, CONSTANT or | |
1195 VARDECL, here we only need to check SSA name operands. This is | |
1196 because check on VARDECL operands, which involve memory loads, | |
1197 must have been done prior to invocation of this function in | |
1198 vuse_semi_invariant_p. */ | |
1199 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) | |
1200 if (!ssa_semi_invariant_p (loop, use, skip_head, stmt_stat)) | |
1201 return false; | |
1202 } | |
1203 | |
1204 if (!control_dep_semi_invariant_p (loop, gimple_bb (stmt), skip_head, | |
1205 stmt_stat)) | |
1206 return false; | |
1207 | |
1208 /* Here we SHOULD NOT use invar = true, since hash map might be changed due | |
1209 to new insertion, and thus invar may point to invalid memory. */ | |
1210 stmt_stat.put (stmt, true); | |
1211 return true; | |
1212 } | |
1213 | |
1214 /* A helper function to check whether STMT is semi-invariant in LOOP. Basic | |
1215 blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. */ | |
1216 | |
1217 static bool | |
1218 stmt_semi_invariant_p (struct loop *loop, gimple *stmt, | |
1219 const_basic_block skip_head) | |
1220 { | |
1221 hash_map<gimple *, bool> stmt_stat; | |
1222 return stmt_semi_invariant_p_1 (loop, stmt, skip_head, stmt_stat); | |
1223 } | |
1224 | |
1225 /* Determine when conditional statement never transfers execution to one of its | |
1226 branch, whether we can remove the branch's leading basic block (BRANCH_BB) | |
1227 and those basic blocks dominated by BRANCH_BB. */ | |
1228 | |
1229 static bool | |
1230 branch_removable_p (basic_block branch_bb) | |
1231 { | |
1232 edge_iterator ei; | |
1233 edge e; | |
1234 | |
1235 if (single_pred_p (branch_bb)) | |
1236 return true; | |
1237 | |
1238 FOR_EACH_EDGE (e, ei, branch_bb->preds) | |
1239 { | |
1240 if (dominated_by_p (CDI_DOMINATORS, e->src, branch_bb)) | |
1241 continue; | |
1242 | |
1243 if (dominated_by_p (CDI_DOMINATORS, branch_bb, e->src)) | |
1244 continue; | |
1245 | |
1246 /* The branch can be reached from opposite branch, or from some | |
1247 statement not dominated by the conditional statement. */ | |
1248 return false; | |
1249 } | |
1250 | |
1251 return true; | |
1252 } | |
1253 | |
1254 /* Find out which branch of a conditional statement (COND) is invariant in the | |
1255 execution context of LOOP. That is: once the branch is selected in certain | |
1256 iteration of the loop, any operand that contributes to computation of the | |
1257 conditional statement remains unchanged in all following iterations. */ | |
1258 | |
1259 static edge | |
1260 get_cond_invariant_branch (struct loop *loop, gcond *cond) | |
1261 { | |
1262 basic_block cond_bb = gimple_bb (cond); | |
1263 basic_block targ_bb[2]; | |
1264 bool invar[2]; | |
1265 unsigned invar_checks = 0; | |
1266 | |
1267 for (unsigned i = 0; i < 2; i++) | |
1268 { | |
1269 targ_bb[i] = EDGE_SUCC (cond_bb, i)->dest; | |
1270 | |
1271 /* One branch directs to loop exit, no need to perform loop split upon | |
1272 this conditional statement. Firstly, it is trivial if the exit branch | |
1273 is semi-invariant, for the statement is just to break loop. Secondly, | |
1274 if the opposite branch is semi-invariant, it means that the statement | |
1275 is real loop-invariant, which is covered by loop unswitch. */ | |
1276 if (!flow_bb_inside_loop_p (loop, targ_bb[i])) | |
1277 return NULL; | |
1278 } | |
1279 | |
1280 for (unsigned i = 0; i < 2; i++) | |
1281 { | |
1282 invar[!i] = false; | |
1283 | |
1284 if (!branch_removable_p (targ_bb[i])) | |
1285 continue; | |
1286 | |
1287 /* Given a semi-invariant branch, if its opposite branch dominates | |
1288 loop latch, it and its following trace will only be executed in | |
1289 final iteration of loop, namely it is not part of repeated body | |
1290 of the loop. Similar to the above case that the branch is loop | |
1291 exit, no need to split loop. */ | |
1292 if (dominated_by_p (CDI_DOMINATORS, loop->latch, targ_bb[i])) | |
1293 continue; | |
1294 | |
1295 invar[!i] = stmt_semi_invariant_p (loop, cond, targ_bb[i]); | |
1296 invar_checks++; | |
1297 } | |
1298 | |
1299 /* With both branches being invariant (handled by loop unswitch) or | |
1300 variant is not what we want. */ | |
1301 if (invar[0] ^ !invar[1]) | |
1302 return NULL; | |
1303 | |
1304 /* Found a real loop-invariant condition, do nothing. */ | |
1305 if (invar_checks < 2 && stmt_semi_invariant_p (loop, cond, NULL)) | |
1306 return NULL; | |
1307 | |
1308 return EDGE_SUCC (cond_bb, invar[0] ? 0 : 1); | |
1309 } | |
1310 | |
1311 /* Calculate increased code size measured by estimated insn number if applying | |
1312 loop split upon certain branch (BRANCH_EDGE) of a conditional statement. */ | |
1313 | |
1314 static int | |
1315 compute_added_num_insns (struct loop *loop, const_edge branch_edge) | |
1316 { | |
1317 basic_block cond_bb = branch_edge->src; | |
1318 unsigned branch = EDGE_SUCC (cond_bb, 1) == branch_edge; | |
1319 basic_block opposite_bb = EDGE_SUCC (cond_bb, !branch)->dest; | |
1320 basic_block *bbs = ((split_info *) loop->aux)->bbs; | |
1321 int num = 0; | |
1322 | |
1323 for (unsigned i = 0; i < loop->num_nodes; i++) | |
1324 { | |
1325 /* Do no count basic blocks only in opposite branch. */ | |
1326 if (dominated_by_p (CDI_DOMINATORS, bbs[i], opposite_bb)) | |
1327 continue; | |
1328 | |
1329 num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights); | |
1330 } | |
1331 | |
1332 /* It is unnecessary to evaluate expression of the conditional statement | |
1333 in new loop that contains only invariant branch. This expression should | |
1334 be constant value (either true or false). Exclude code size of insns | |
1335 that contribute to computation of the expression. */ | |
1336 | |
1337 auto_vec<gimple *> worklist; | |
1338 hash_set<gimple *> removed; | |
1339 gimple *stmt = last_stmt (cond_bb); | |
1340 | |
1341 worklist.safe_push (stmt); | |
1342 removed.add (stmt); | |
1343 num -= estimate_num_insns (stmt, &eni_size_weights); | |
1344 | |
1345 do | |
1346 { | |
1347 ssa_op_iter opnd_iter; | |
1348 use_operand_p opnd_p; | |
1349 | |
1350 stmt = worklist.pop (); | |
1351 FOR_EACH_PHI_OR_STMT_USE (opnd_p, stmt, opnd_iter, SSA_OP_USE) | |
1352 { | |
1353 tree opnd = USE_FROM_PTR (opnd_p); | |
1354 | |
1355 if (TREE_CODE (opnd) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (opnd)) | |
1356 continue; | |
1357 | |
1358 gimple *opnd_stmt = SSA_NAME_DEF_STMT (opnd); | |
1359 use_operand_p use_p; | |
1360 imm_use_iterator use_iter; | |
1361 | |
1362 if (removed.contains (opnd_stmt) | |
1363 || !flow_bb_inside_loop_p (loop, gimple_bb (opnd_stmt))) | |
1364 continue; | |
1365 | |
1366 FOR_EACH_IMM_USE_FAST (use_p, use_iter, opnd) | |
1367 { | |
1368 gimple *use_stmt = USE_STMT (use_p); | |
1369 | |
1370 if (!is_gimple_debug (use_stmt) && !removed.contains (use_stmt)) | |
1371 { | |
1372 opnd_stmt = NULL; | |
1373 break; | |
1374 } | |
1375 } | |
1376 | |
1377 if (opnd_stmt) | |
1378 { | |
1379 worklist.safe_push (opnd_stmt); | |
1380 removed.add (opnd_stmt); | |
1381 num -= estimate_num_insns (opnd_stmt, &eni_size_weights); | |
1382 } | |
1383 } | |
1384 } while (!worklist.is_empty ()); | |
1385 | |
1386 gcc_assert (num >= 0); | |
1387 return num; | |
1388 } | |
1389 | |
1390 /* Find out loop-invariant branch of a conditional statement (COND) if it has, | |
1391 and check whether it is eligible and profitable to perform loop split upon | |
1392 this branch in LOOP. */ | |
1393 | |
1394 static edge | |
1395 get_cond_branch_to_split_loop (struct loop *loop, gcond *cond) | |
1396 { | |
1397 edge invar_branch = get_cond_invariant_branch (loop, cond); | |
1398 if (!invar_branch) | |
1399 return NULL; | |
1400 | |
1401 /* When accurate profile information is available, and execution | |
1402 frequency of the branch is too low, just let it go. */ | |
1403 profile_probability prob = invar_branch->probability; | |
1404 if (prob.reliable_p ()) | |
1405 { | |
1406 int thres = param_min_loop_cond_split_prob; | |
1407 | |
1408 if (prob < profile_probability::always ().apply_scale (thres, 100)) | |
1409 return NULL; | |
1410 } | |
1411 | |
1412 /* Add a threshold for increased code size to disable loop split. */ | |
1413 if (compute_added_num_insns (loop, invar_branch) > param_max_peeled_insns) | |
1414 return NULL; | |
1415 | |
1416 return invar_branch; | |
1417 } | |
1418 | |
1419 /* Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of some | |
1420 conditional statement, perform loop split transformation illustrated | |
1421 as the following graph. | |
1422 | |
1423 .-------T------ if (true) ------F------. | |
1424 | .---------------. | | |
1425 | | | | | |
1426 v | v v | |
1427 pre-header | pre-header | |
1428 | .------------. | | .------------. | |
1429 | | | | | | | | |
1430 | v | | | v | | |
1431 header | | header | | |
1432 | | | | | | |
1433 .--- if (cond) ---. | | .--- if (true) ---. | | |
1434 | | | | | | | | |
1435 invariant | | | invariant | | | |
1436 | | | | | | | | |
1437 '---T--->.<---F---' | | '---T--->.<---F---' | | |
1438 | | / | | | |
1439 stmts | / stmts | | |
1440 | F T | | | |
1441 / \ | / / \ | | |
1442 .-------* * [ if (cond) ] .-------* * | | |
1443 | | | | | | | |
1444 | latch | | latch | | |
1445 | | | | | | | |
1446 | '------------' | '------------' | |
1447 '------------------------. .-----------' | |
1448 loop1 | | loop2 | |
1449 v v | |
1450 exits | |
1451 | |
1452 In the graph, loop1 represents the part derived from original one, and | |
1453 loop2 is duplicated using loop_version (), which corresponds to the part | |
1454 of original one being splitted out. In original latch edge of loop1, we | |
1455 insert a new conditional statement duplicated from the semi-invariant cond, | |
1456 and one of its branch goes back to loop1 header as a latch edge, and the | |
1457 other branch goes to loop2 pre-header as an entry edge. And also in loop2, | |
1458 we abandon the variant branch of the conditional statement by setting a | |
1459 constant bool condition, based on which branch is semi-invariant. */ | |
1460 | |
1461 static bool | |
1462 do_split_loop_on_cond (struct loop *loop1, edge invar_branch) | |
1463 { | |
1464 basic_block cond_bb = invar_branch->src; | |
1465 bool true_invar = !!(invar_branch->flags & EDGE_TRUE_VALUE); | |
1466 gcond *cond = as_a <gcond *> (last_stmt (cond_bb)); | |
1467 | |
1468 gcc_assert (cond_bb->loop_father == loop1); | |
1469 | |
1470 if (dump_enabled_p ()) | |
1471 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond, | |
1472 "loop split on semi-invariant condition at %s branch\n", | |
1473 true_invar ? "true" : "false"); | |
1474 | |
1475 initialize_original_copy_tables (); | |
1476 | |
1477 struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL, | |
1478 profile_probability::always (), | |
1479 profile_probability::never (), | |
1480 profile_probability::always (), | |
1481 profile_probability::always (), | |
1482 true); | |
1483 if (!loop2) | |
1484 { | |
1485 free_original_copy_tables (); | |
1486 return false; | |
1487 } | |
1488 | |
1489 basic_block cond_bb_copy = get_bb_copy (cond_bb); | |
1490 gcond *cond_copy = as_a<gcond *> (last_stmt (cond_bb_copy)); | |
1491 | |
1492 /* Replace the condition in loop2 with a bool constant to let PassManager | |
1493 remove the variant branch after current pass completes. */ | |
1494 if (true_invar) | |
1495 gimple_cond_make_true (cond_copy); | |
1496 else | |
1497 gimple_cond_make_false (cond_copy); | |
1498 | |
1499 update_stmt (cond_copy); | |
1500 | |
1501 /* Insert a new conditional statement on latch edge of loop1, its condition | |
1502 is duplicated from the semi-invariant. This statement acts as a switch | |
1503 to transfer execution from loop1 to loop2, when loop1 enters into | |
1504 invariant state. */ | |
1505 basic_block latch_bb = split_edge (loop_latch_edge (loop1)); | |
1506 basic_block break_bb = split_edge (single_pred_edge (latch_bb)); | |
1507 gimple *break_cond = gimple_build_cond (gimple_cond_code(cond), | |
1508 gimple_cond_lhs (cond), | |
1509 gimple_cond_rhs (cond), | |
1510 NULL_TREE, NULL_TREE); | |
1511 | |
1512 gimple_stmt_iterator gsi = gsi_last_bb (break_bb); | |
1513 gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT); | |
1514 | |
1515 edge to_loop1 = single_succ_edge (break_bb); | |
1516 edge to_loop2 = make_edge (break_bb, loop_preheader_edge (loop2)->src, 0); | |
1517 | |
1518 to_loop1->flags &= ~EDGE_FALLTHRU; | |
1519 to_loop1->flags |= true_invar ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE; | |
1520 to_loop2->flags |= true_invar ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE; | |
1521 | |
1522 update_ssa (TODO_update_ssa); | |
1523 | |
1524 /* Due to introduction of a control flow edge from loop1 latch to loop2 | |
1525 pre-header, we should update PHIs in loop2 to reflect this connection | |
1526 between loop1 and loop2. */ | |
1527 connect_loop_phis (loop1, loop2, to_loop2); | |
1528 | |
1529 free_original_copy_tables (); | |
1530 | |
1531 rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1); | |
1532 | |
1533 return true; | |
1534 } | |
1535 | |
1536 /* Traverse all conditional statements in LOOP, to find out a good candidate | |
1537 upon which we can do loop split. */ | |
1538 | |
1539 static bool | |
1540 split_loop_on_cond (struct loop *loop) | |
1541 { | |
1542 split_info *info = new split_info (); | |
1543 basic_block *bbs = info->bbs = get_loop_body (loop); | |
1544 bool do_split = false; | |
1545 | |
1546 /* Allocate an area to keep temporary info, and associate its address | |
1547 with loop aux field. */ | |
1548 loop->aux = info; | |
1549 | |
1550 for (unsigned i = 0; i < loop->num_nodes; i++) | |
1551 bbs[i]->aux = NULL; | |
1552 | |
1553 for (unsigned i = 0; i < loop->num_nodes; i++) | |
1554 { | |
1555 basic_block bb = bbs[i]; | |
1556 | |
1557 /* We only consider conditional statement, which be executed at most once | |
1558 in each iteration of the loop. So skip statements in inner loops. */ | |
1559 if ((bb->loop_father != loop) || (bb->flags & BB_IRREDUCIBLE_LOOP)) | |
1560 continue; | |
1561 | |
1562 /* Actually this check is not a must constraint. With it, we can ensure | |
1563 conditional statement will always be executed in each iteration. */ | |
1564 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) | |
1565 continue; | |
1566 | |
1567 gimple *last = last_stmt (bb); | |
1568 | |
1569 if (!last || gimple_code (last) != GIMPLE_COND) | |
1570 continue; | |
1571 | |
1572 gcond *cond = as_a <gcond *> (last); | |
1573 edge branch_edge = get_cond_branch_to_split_loop (loop, cond); | |
1574 | |
1575 if (branch_edge) | |
1576 { | |
1577 do_split_loop_on_cond (loop, branch_edge); | |
1578 do_split = true; | |
1579 break; | |
1580 } | |
1581 } | |
1582 | |
1583 delete info; | |
1584 loop->aux = NULL; | |
1585 | |
1586 return do_split; | |
1587 } | |
1588 | |
615 /* Main entry point. Perform loop splitting on all suitable loops. */ | 1589 /* Main entry point. Perform loop splitting on all suitable loops. */ |
616 | 1590 |
617 static unsigned int | 1591 static unsigned int |
618 tree_ssa_split_loops (void) | 1592 tree_ssa_split_loops (void) |
619 { | 1593 { |
620 struct loop *loop; | 1594 class loop *loop; |
621 bool changed = false; | 1595 bool changed = false; |
622 | 1596 |
623 gcc_assert (scev_initialized_p ()); | 1597 gcc_assert (scev_initialized_p ()); |
1598 | |
1599 calculate_dominance_info (CDI_POST_DOMINATORS); | |
1600 | |
624 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) | 1601 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) |
625 loop->aux = NULL; | 1602 loop->aux = NULL; |
626 | 1603 |
627 /* Go through all loops starting from innermost. */ | 1604 /* Go through all loops starting from innermost. */ |
628 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) | 1605 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) |
629 { | 1606 { |
630 struct tree_niter_desc niter; | |
631 if (loop->aux) | 1607 if (loop->aux) |
632 { | 1608 { |
633 /* If any of our inner loops was split, don't split us, | 1609 /* If any of our inner loops was split, don't split us, |
634 and mark our containing loop as having had splits as well. */ | 1610 and mark our containing loop as having had splits as well. */ |
635 loop_outer (loop)->aux = loop; | 1611 loop_outer (loop)->aux = loop; |
636 continue; | 1612 continue; |
637 } | 1613 } |
638 | 1614 |
639 if (single_exit (loop) | 1615 if (optimize_loop_for_size_p (loop)) |
640 /* ??? We could handle non-empty latches when we split | 1616 continue; |
641 the latch edge (not the exit edge), and put the new | 1617 |
642 exit condition in the new block. OTOH this executes some | 1618 if (split_loop (loop) || split_loop_on_cond (loop)) |
643 code unconditionally that might have been skipped by the | |
644 original exit before. */ | |
645 && empty_block_p (loop->latch) | |
646 && !optimize_loop_for_size_p (loop) | |
647 && easy_exit_values (loop) | |
648 && number_of_iterations_exit (loop, single_exit (loop), &niter, | |
649 false, true) | |
650 && niter.cmp != ERROR_MARK | |
651 /* We can't yet handle loops controlled by a != predicate. */ | |
652 && niter.cmp != NE_EXPR) | |
653 { | 1619 { |
654 if (split_loop (loop, &niter)) | 1620 /* Mark our containing loop as having had some split inner loops. */ |
655 { | 1621 loop_outer (loop)->aux = loop; |
656 /* Mark our containing loop as having had some split inner | 1622 changed = true; |
657 loops. */ | |
658 loop_outer (loop)->aux = loop; | |
659 changed = true; | |
660 } | |
661 } | 1623 } |
662 } | 1624 } |
663 | 1625 |
664 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) | 1626 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) |
665 loop->aux = NULL; | 1627 loop->aux = NULL; |
1628 | |
1629 clear_aux_for_blocks (); | |
1630 | |
1631 free_dominance_info (CDI_POST_DOMINATORS); | |
666 | 1632 |
667 if (changed) | 1633 if (changed) |
668 return TODO_cleanup_cfg; | 1634 return TODO_cleanup_cfg; |
669 return 0; | 1635 return 0; |
670 } | 1636 } |