Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-if-conv.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 24 May 2010 12:47:05 +0900 |
| parents | 77e2b8dfacca |
| children | f6334be47118 |
| rev | line source |
|---|---|
| 0 | 1 /* If-conversion for vectorizer. |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 Free Software Foundation, Inc. |
| 0 | 4 Contributed by Devang Patel <dpatel@apple.com> |
| 5 | |
| 6 This file is part of GCC. | |
| 7 | |
| 8 GCC is free software; you can redistribute it and/or modify it under | |
| 9 the terms of the GNU General Public License as published by the Free | |
| 10 Software Foundation; either version 3, or (at your option) any later | |
| 11 version. | |
| 12 | |
| 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
| 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 16 for more details. | |
| 17 | |
| 18 You should have received a copy of the GNU General Public License | |
| 19 along with GCC; see the file COPYING3. If not see | |
| 20 <http://www.gnu.org/licenses/>. */ | |
| 21 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
22 /* This pass implements a tree level if-conversion of loops. Its |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
23 initial goal is to help the vectorizer to vectorize loops with |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
24 conditions. |
| 0 | 25 |
| 26 A short description of if-conversion: | |
| 27 | |
| 28 o Decide if a loop is if-convertible or not. | |
| 29 o Walk all loop basic blocks in breadth first order (BFS order). | |
| 30 o Remove conditional statements (at the end of basic block) | |
| 31 and propagate condition into destination basic blocks' | |
| 32 predicate list. | |
| 33 o Replace modify expression with conditional modify expression | |
| 34 using current basic block's condition. | |
| 35 o Merge all basic blocks | |
| 36 o Replace phi nodes with conditional modify expr | |
| 37 o Merge all basic blocks into header | |
| 38 | |
| 39 Sample transformation: | |
| 40 | |
| 41 INPUT | |
| 42 ----- | |
| 43 | |
| 44 # i_23 = PHI <0(0), i_18(10)>; | |
| 45 <L0>:; | |
| 46 j_15 = A[i_23]; | |
| 47 if (j_15 > 41) goto <L1>; else goto <L17>; | |
| 48 | |
| 49 <L17>:; | |
| 50 goto <bb 3> (<L3>); | |
| 51 | |
| 52 <L1>:; | |
| 53 | |
| 54 # iftmp.2_4 = PHI <0(8), 42(2)>; | |
| 55 <L3>:; | |
| 56 A[i_23] = iftmp.2_4; | |
| 57 i_18 = i_23 + 1; | |
| 58 if (i_18 <= 15) goto <L19>; else goto <L18>; | |
| 59 | |
| 60 <L19>:; | |
| 61 goto <bb 1> (<L0>); | |
| 62 | |
| 63 <L18>:; | |
| 64 | |
| 65 OUTPUT | |
| 66 ------ | |
| 67 | |
| 68 # i_23 = PHI <0(0), i_18(10)>; | |
| 69 <L0>:; | |
| 70 j_15 = A[i_23]; | |
| 71 | |
| 72 <L3>:; | |
| 73 iftmp.2_4 = j_15 > 41 ? 42 : 0; | |
| 74 A[i_23] = iftmp.2_4; | |
| 75 i_18 = i_23 + 1; | |
| 76 if (i_18 <= 15) goto <L19>; else goto <L18>; | |
| 77 | |
| 78 <L19>:; | |
| 79 goto <bb 1> (<L0>); | |
| 80 | |
| 81 <L18>:; | |
| 82 */ | |
| 83 | |
| 84 #include "config.h" | |
| 85 #include "system.h" | |
| 86 #include "coretypes.h" | |
| 87 #include "tm.h" | |
| 88 #include "tree.h" | |
| 89 #include "flags.h" | |
| 90 #include "timevar.h" | |
| 91 #include "basic-block.h" | |
| 92 #include "diagnostic.h" | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
93 #include "tree-pretty-print.h" |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
94 #include "gimple-pretty-print.h" |
| 0 | 95 #include "tree-flow.h" |
| 96 #include "tree-dump.h" | |
| 97 #include "cfgloop.h" | |
| 98 #include "tree-chrec.h" | |
| 99 #include "tree-data-ref.h" | |
| 100 #include "tree-scalar-evolution.h" | |
| 101 #include "tree-pass.h" | |
| 102 | |
| 103 /* List of basic blocks in if-conversion-suitable order. */ | |
| 104 static basic_block *ifc_bbs; | |
| 105 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
106 /* Create a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
107 to the new variable. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
108 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
109 static gimple |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
110 ifc_temp_var (tree type, tree exp) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
111 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
112 const char *name = "_ifc_"; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
113 tree var, new_name; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
114 gimple stmt; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
115 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
116 /* Create new temporary variable. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
117 var = create_tmp_var (type, name); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
118 add_referenced_var (var); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
119 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
120 /* Build new statement to assign EXP to new variable. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
121 stmt = gimple_build_assign (var, exp); |
| 0 | 122 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
123 /* Get SSA name for the new variable and set make new statement |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
124 its definition statement. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
125 new_name = make_ssa_name (var, stmt); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
126 gimple_assign_set_lhs (stmt, new_name); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
127 SSA_NAME_DEF_STMT (new_name) = stmt; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
128 update_stmt (stmt); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
129 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
130 return stmt; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
131 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
132 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
133 /* Add condition NEW_COND to the predicate list of basic block BB. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
134 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
135 static void |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
136 add_to_predicate_list (basic_block bb, tree new_cond) |
| 0 | 137 { |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
138 tree cond = (tree) bb->aux; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
139 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
140 if (cond) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
141 cond = fold_build2_loc (EXPR_LOCATION (cond), |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
142 TRUTH_OR_EXPR, boolean_type_node, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
143 unshare_expr (cond), new_cond); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
144 else |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
145 cond = new_cond; |
| 0 | 146 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
147 bb->aux = cond; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
148 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
149 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
150 /* Add the condition COND to the previous condition PREV_COND, and add this |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
151 to the predicate list of the destination of edge E. GSI is the |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
152 place where the gimplification of the resulting condition should |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
153 output code. LOOP is the loop to be if-converted. */ |
| 0 | 154 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
155 static tree |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
156 add_to_dst_predicate_list (struct loop *loop, edge e, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
157 tree prev_cond, tree cond, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
158 gimple_stmt_iterator *gsi) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
159 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
160 tree new_cond = NULL_TREE; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
161 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
162 if (!flow_bb_inside_loop_p (loop, e->dest)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
163 return NULL_TREE; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
164 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
165 if (prev_cond == boolean_true_node || !prev_cond) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
166 new_cond = unshare_expr (cond); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
167 else |
| 0 | 168 { |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
169 tree tmp; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
170 gimple tmp_stmt = NULL; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
171 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
172 prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond), |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
173 true, NULL, true, GSI_SAME_STMT); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
174 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
175 cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
176 true, NULL, true, GSI_SAME_STMT); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
177 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
178 /* Add the condition COND to the e->aux field. In case the edge |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
179 destination is a PHI node, this condition will be added to |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
180 the block predicate to construct a complete condition. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
181 e->aux = cond; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
182 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
183 tmp = build2 (TRUTH_AND_EXPR, boolean_type_node, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
184 unshare_expr (prev_cond), cond); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
185 tmp_stmt = ifc_temp_var (boolean_type_node, tmp); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
186 gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
187 new_cond = gimple_assign_lhs (tmp_stmt); |
| 0 | 188 } |
| 189 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
190 add_to_predicate_list (e->dest, new_cond); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
191 return new_cond; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
192 } |
| 0 | 193 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
194 /* Return true if one of the successor edges of BB exits LOOP. */ |
| 0 | 195 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
196 static bool |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
197 bb_with_exit_edge_p (struct loop *loop, basic_block bb) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
198 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
199 edge e; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
200 edge_iterator ei; |
| 0 | 201 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
202 FOR_EACH_EDGE (e, ei, bb->succs) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
203 if (loop_exit_edge_p (loop, e)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
204 return true; |
| 0 | 205 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
206 return false; |
| 0 | 207 } |
| 208 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
209 /* STMT is a GIMPLE_COND. Update two destination's predicate list. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
210 Remove COND_EXPR, if it is not the exit condition of LOOP. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
211 Otherwise update the exit condition of LOOP appropriately. GSI |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
212 points to the statement STMT. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
213 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
214 static void |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
215 tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
216 gimple_stmt_iterator *gsi) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
217 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
218 tree c2; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
219 edge true_edge, false_edge; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
220 location_t loc = gimple_location (stmt); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
221 tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
222 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
223 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
224 extract_true_false_edges_from_block (gimple_bb (stmt), |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
225 &true_edge, &false_edge); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
226 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
227 /* Add new condition into destination's predicate list. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
228 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
229 /* If C is true, then TRUE_EDGE is taken. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
230 add_to_dst_predicate_list (loop, true_edge, cond, c, gsi); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
231 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
232 /* If C is false, then FALSE_EDGE is taken. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
233 c2 = invert_truthvalue_loc (loc, unshare_expr (c)); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
234 add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
235 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
236 /* Now this conditional statement is redundant. Remove it. But, do |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
237 not remove the exit condition! Update the exit condition using |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
238 the new condition. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
239 if (!bb_with_exit_edge_p (loop, gimple_bb (stmt))) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
240 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
241 gsi_remove (gsi, true); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
242 cond = NULL_TREE; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
243 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
244 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
245 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
246 /* If-convert stmt T which is part of LOOP. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
247 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
248 If T is a GIMPLE_ASSIGN then it is converted into a conditional |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
249 modify expression using COND. For conditional expressions, add |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
250 a condition in the destination basic block's predicate list and |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
251 remove the conditional expression itself. GSI points to the |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
252 statement T. */ |
| 0 | 253 |
| 254 static tree | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
255 tree_if_convert_stmt (struct loop *loop, gimple t, tree cond, |
| 0 | 256 gimple_stmt_iterator *gsi) |
| 257 { | |
| 258 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 259 { | |
| 260 fprintf (dump_file, "------if-convert stmt\n"); | |
| 261 print_gimple_stmt (dump_file, t, 0, TDF_SLIM); | |
| 262 print_generic_stmt (dump_file, cond, TDF_SLIM); | |
| 263 } | |
| 264 | |
| 265 switch (gimple_code (t)) | |
| 266 { | |
| 267 /* Labels are harmless here. */ | |
| 268 case GIMPLE_LABEL: | |
| 269 break; | |
| 270 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
271 case GIMPLE_DEBUG: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
272 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
273 if (gimple_debug_bind_p (gsi_stmt (*gsi))) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
274 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
275 gimple_debug_bind_reset_value (gsi_stmt (*gsi)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
276 update_stmt (gsi_stmt (*gsi)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
277 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
278 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
279 |
| 0 | 280 case GIMPLE_ASSIGN: |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
281 /* This GIMPLE_ASSIGN is killing previous value of LHS. Appropriate |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
282 value will be selected by PHI node based on condition. It is possible |
| 0 | 283 that before this transformation, PHI nodes was selecting default |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
284 value and now it will use this new value. This is OK because it does |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
285 not change the validity of the program. */ |
| 0 | 286 break; |
| 287 | |
| 288 case GIMPLE_COND: | |
| 289 /* Update destination blocks' predicate list and remove this | |
| 290 condition expression. */ | |
| 291 tree_if_convert_cond_stmt (loop, t, cond, gsi); | |
| 292 cond = NULL_TREE; | |
| 293 break; | |
| 294 | |
| 295 default: | |
| 296 gcc_unreachable (); | |
| 297 } | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
298 |
| 0 | 299 return cond; |
| 300 } | |
| 301 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
302 /* Return true when PHI is if-convertible. PHI is part of loop LOOP |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
303 and it belongs to basic block BB. |
| 0 | 304 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
305 PHI is not if-convertible if: |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
306 - it has more than 2 arguments, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
307 - virtual PHI is immediately used in another PHI node, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
308 - virtual PHI on BB other than header. */ |
| 0 | 309 |
| 310 static bool | |
| 311 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) | |
| 312 { | |
| 313 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 314 { | |
| 315 fprintf (dump_file, "-------------------------\n"); | |
| 316 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); | |
| 317 } | |
| 318 | |
| 319 if (bb != loop->header && gimple_phi_num_args (phi) != 2) | |
| 320 { | |
| 321 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 322 fprintf (dump_file, "More than two phi node args.\n"); | |
| 323 return false; | |
| 324 } | |
| 325 | |
| 326 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi)))) | |
| 327 { | |
| 328 imm_use_iterator imm_iter; | |
| 329 use_operand_p use_p; | |
| 330 | |
| 331 if (bb != loop->header) | |
| 332 { | |
| 333 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 334 fprintf (dump_file, "Virtual phi not on loop header.\n"); | |
| 335 return false; | |
| 336 } | |
| 337 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi)) | |
| 338 { | |
| 339 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI) | |
| 340 { | |
| 341 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 342 fprintf (dump_file, "Difficult to handle this virtual phi.\n"); | |
| 343 return false; | |
| 344 } | |
| 345 } | |
| 346 } | |
| 347 | |
| 348 return true; | |
| 349 } | |
| 350 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
351 /* Return true when STMT is if-convertible. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
352 |
| 0 | 353 GIMPLE_ASSIGN statement is not if-convertible if, |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
354 - it is not movable, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
355 - it could trap, |
| 0 | 356 - LHS is not var decl. |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
357 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
358 GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */ |
| 0 | 359 |
| 360 static bool | |
| 361 if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb, | |
| 362 gimple stmt) | |
| 363 { | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
364 tree lhs = gimple_assign_lhs (stmt); |
| 0 | 365 |
| 366 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 367 { | |
| 368 fprintf (dump_file, "-------------------------\n"); | |
| 369 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
| 370 } | |
| 371 | |
| 372 /* Some of these constrains might be too conservative. */ | |
| 373 if (stmt_ends_bb_p (stmt) | |
| 374 || gimple_has_volatile_ops (stmt) | |
| 375 || (TREE_CODE (lhs) == SSA_NAME | |
| 376 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) | |
| 377 || gimple_has_side_effects (stmt)) | |
| 378 { | |
| 379 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 380 fprintf (dump_file, "stmt not suitable for ifcvt\n"); | |
| 381 return false; | |
| 382 } | |
| 383 | |
| 384 /* See if it needs speculative loading or not. */ | |
| 385 if (bb != loop->header | |
| 386 && gimple_assign_rhs_could_trap_p (stmt)) | |
| 387 { | |
| 388 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 389 fprintf (dump_file, "tree could trap...\n"); | |
| 390 return false; | |
| 391 } | |
| 392 | |
| 393 if (TREE_CODE (lhs) != SSA_NAME | |
| 394 && bb != loop->header | |
| 395 && !bb_with_exit_edge_p (loop, bb)) | |
| 396 { | |
| 397 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 398 { | |
| 399 fprintf (dump_file, "LHS is not var\n"); | |
| 400 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
| 401 } | |
| 402 return false; | |
| 403 } | |
| 404 | |
| 405 return true; | |
| 406 } | |
| 407 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
408 /* Return true when STMT is if-convertible. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
409 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
410 A statement is if-convertible if: |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
411 - it is an if-convertible GIMPLE_ASSGIN, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
412 - it is a GIMPLE_LABEL or a GIMPLE_COND. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
413 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
414 STMT is inside BB, which is inside loop LOOP. */ |
| 0 | 415 |
| 416 static bool | |
| 417 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt) | |
| 418 { | |
| 419 switch (gimple_code (stmt)) | |
| 420 { | |
| 421 case GIMPLE_LABEL: | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
422 case GIMPLE_DEBUG: |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
423 case GIMPLE_COND: |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
424 return true; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
425 |
| 0 | 426 case GIMPLE_ASSIGN: |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
427 return if_convertible_gimple_assign_stmt_p (loop, bb, stmt); |
| 0 | 428 |
| 429 default: | |
| 430 /* Don't know what to do with 'em so don't do anything. */ | |
| 431 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 432 { | |
| 433 fprintf (dump_file, "don't know what to do\n"); | |
| 434 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
| 435 } | |
| 436 return false; | |
| 437 break; | |
| 438 } | |
| 439 | |
| 440 return true; | |
| 441 } | |
| 442 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
443 /* Return true when BB is if-convertible. This routine does not check |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
444 basic block's statements and phis. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
445 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
446 A basic block is not if-convertible if: |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
447 - it is non-empty and it is after the exit block (in BFS order), |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
448 - it is after the exit block but before the latch, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
449 - its edges are not normal. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
450 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
451 EXIT_BB is the basic block containing the exit of the LOOP. BB is |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
452 inside LOOP. */ |
| 0 | 453 |
| 454 static bool | |
| 455 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) | |
| 456 { | |
| 457 edge e; | |
| 458 edge_iterator ei; | |
| 459 | |
| 460 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 461 fprintf (dump_file, "----------[%d]-------------\n", bb->index); | |
| 462 | |
| 463 if (exit_bb) | |
| 464 { | |
| 465 if (bb != loop->latch) | |
| 466 { | |
| 467 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 468 fprintf (dump_file, "basic block after exit bb but before latch\n"); | |
| 469 return false; | |
| 470 } | |
| 471 else if (!empty_block_p (bb)) | |
| 472 { | |
| 473 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 474 fprintf (dump_file, "non empty basic block after exit bb\n"); | |
| 475 return false; | |
| 476 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
477 else if (bb == loop->latch |
| 0 | 478 && bb != exit_bb |
| 479 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) | |
| 480 { | |
| 481 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 482 fprintf (dump_file, "latch is not dominated by exit_block\n"); | |
| 483 return false; | |
| 484 } | |
| 485 } | |
| 486 | |
| 487 /* Be less adventurous and handle only normal edges. */ | |
| 488 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 489 if (e->flags & | |
| 490 (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) | |
| 491 { | |
| 492 if (dump_file && (dump_flags & TDF_DETAILS)) | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
493 fprintf (dump_file, "Difficult to handle edges\n"); |
| 0 | 494 return false; |
| 495 } | |
| 496 | |
| 497 return true; | |
| 498 } | |
| 499 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
500 /* Return true when all predecessor blocks of BB are visited. The |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
501 VISITED bitmap keeps track of the visited blocks. */ |
| 0 | 502 |
| 503 static bool | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
504 pred_blocks_visited_p (basic_block bb, bitmap *visited) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
505 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
506 edge e; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
507 edge_iterator ei; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
508 FOR_EACH_EDGE (e, ei, bb->preds) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
509 if (!bitmap_bit_p (*visited, e->src->index)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
510 return false; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
511 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
512 return true; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
513 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
514 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
515 /* Get body of a LOOP in suitable order for if-conversion. It is |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
516 caller's responsibility to deallocate basic block list. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
517 If-conversion suitable order is, breadth first sort (BFS) order |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
518 with an additional constraint: select a block only if all its |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
519 predecessors are already selected. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
520 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
521 static basic_block * |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
522 get_loop_body_in_if_conv_order (const struct loop *loop) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
523 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
524 basic_block *blocks, *blocks_in_bfs_order; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
525 basic_block bb; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
526 bitmap visited; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
527 unsigned int index = 0; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
528 unsigned int visited_count = 0; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
529 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
530 gcc_assert (loop->num_nodes); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
531 gcc_assert (loop->latch != EXIT_BLOCK_PTR); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
532 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
533 blocks = XCNEWVEC (basic_block, loop->num_nodes); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
534 visited = BITMAP_ALLOC (NULL); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
535 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
536 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
537 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
538 index = 0; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
539 while (index < loop->num_nodes) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
540 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
541 bb = blocks_in_bfs_order [index]; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
542 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
543 if (bb->flags & BB_IRREDUCIBLE_LOOP) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
544 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
545 free (blocks_in_bfs_order); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
546 BITMAP_FREE (visited); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
547 free (blocks); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
548 return NULL; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
549 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
550 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
551 if (!bitmap_bit_p (visited, bb->index)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
552 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
553 if (pred_blocks_visited_p (bb, &visited) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
554 || bb == loop->header) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
555 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
556 /* This block is now visited. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
557 bitmap_set_bit (visited, bb->index); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
558 blocks[visited_count++] = bb; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
559 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
560 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
561 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
562 index++; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
563 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
564 if (index == loop->num_nodes |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
565 && visited_count != loop->num_nodes) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
566 /* Not done yet. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
567 index = 0; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
568 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
569 free (blocks_in_bfs_order); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
570 BITMAP_FREE (visited); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
571 return blocks; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
572 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
573 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
574 /* Return true when LOOP is if-convertible. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
575 LOOP is if-convertible if: |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
576 - it is innermost, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
577 - it has two or more basic blocks, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
578 - it has only one exit, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
579 - loop header is not the exit edge, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
580 - if its basic blocks and phi nodes are if convertible. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
581 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
582 static bool |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
583 if_convertible_loop_p (struct loop *loop) |
| 0 | 584 { |
| 585 basic_block bb; | |
| 586 gimple_stmt_iterator itr; | |
| 587 unsigned int i; | |
| 588 edge e; | |
| 589 edge_iterator ei; | |
| 590 basic_block exit_bb = NULL; | |
| 591 | |
| 592 /* Handle only inner most loop. */ | |
| 593 if (!loop || loop->inner) | |
| 594 { | |
| 595 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 596 fprintf (dump_file, "not inner most loop\n"); | |
| 597 return false; | |
| 598 } | |
| 599 | |
| 600 /* If only one block, no need for if-conversion. */ | |
| 601 if (loop->num_nodes <= 2) | |
| 602 { | |
| 603 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 604 fprintf (dump_file, "less than 2 basic blocks\n"); | |
| 605 return false; | |
| 606 } | |
| 607 | |
| 608 /* More than one loop exit is too much to handle. */ | |
| 609 if (!single_exit (loop)) | |
| 610 { | |
| 611 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 612 fprintf (dump_file, "multiple exits\n"); | |
| 613 return false; | |
| 614 } | |
| 615 | |
| 616 /* ??? Check target's vector conditional operation support for vectorizer. */ | |
| 617 | |
| 618 /* If one of the loop header's edge is exit edge then do not apply | |
| 619 if-conversion. */ | |
| 620 FOR_EACH_EDGE (e, ei, loop->header->succs) | |
| 621 { | |
| 622 if (loop_exit_edge_p (loop, e)) | |
| 623 return false; | |
| 624 } | |
| 625 | |
| 626 calculate_dominance_info (CDI_DOMINATORS); | |
| 627 calculate_dominance_info (CDI_POST_DOMINATORS); | |
| 628 | |
| 629 /* Allow statements that can be handled during if-conversion. */ | |
| 630 ifc_bbs = get_loop_body_in_if_conv_order (loop); | |
| 631 if (!ifc_bbs) | |
| 632 { | |
| 633 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 634 fprintf (dump_file,"Irreducible loop\n"); | |
| 635 free_dominance_info (CDI_POST_DOMINATORS); | |
| 636 return false; | |
| 637 } | |
| 638 | |
| 639 for (i = 0; i < loop->num_nodes; i++) | |
| 640 { | |
| 641 bb = ifc_bbs[i]; | |
| 642 | |
| 643 if (!if_convertible_bb_p (loop, bb, exit_bb)) | |
| 644 return false; | |
| 645 | |
| 646 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) | |
| 647 if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr))) | |
| 648 return false; | |
| 649 | |
| 650 itr = gsi_start_phis (bb); | |
| 651 | |
| 652 if (!gsi_end_p (itr)) | |
| 653 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 654 e->aux = NULL; | |
| 655 | |
| 656 for (; !gsi_end_p (itr); gsi_next (&itr)) | |
| 657 if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr))) | |
| 658 return false; | |
| 659 | |
| 660 if (bb_with_exit_edge_p (loop, bb)) | |
| 661 exit_bb = bb; | |
| 662 } | |
| 663 | |
| 664 if (dump_file) | |
| 665 fprintf (dump_file,"Applying if-conversion\n"); | |
| 666 | |
| 667 free_dominance_info (CDI_POST_DOMINATORS); | |
| 668 return true; | |
| 669 } | |
| 670 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
671 /* During if-conversion, the bb->aux field is used to hold a predicate |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
672 list. This function cleans for all the basic blocks in the given |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
673 LOOP their predicate list. It also cleans up the e->aux field of |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
674 all the successor edges: e->aux is used to hold the true and false |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
675 conditions for conditional expressions. */ |
| 0 | 676 |
| 677 static void | |
| 678 clean_predicate_lists (struct loop *loop) | |
| 679 { | |
| 680 basic_block *bb; | |
| 681 unsigned int i; | |
| 682 edge e; | |
| 683 edge_iterator ei; | |
| 684 | |
| 685 bb = get_loop_body (loop); | |
| 686 for (i = 0; i < loop->num_nodes; i++) | |
| 687 { | |
| 688 bb[i]->aux = NULL; | |
| 689 FOR_EACH_EDGE (e, ei, bb[i]->succs) | |
| 690 e->aux = NULL; | |
| 691 } | |
| 692 free (bb); | |
| 693 } | |
| 694 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
695 /* Basic block BB has two predecessors. Using predecessor's bb->aux |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
696 field, set appropriate condition COND for the PHI node replacement. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
697 Return true block whose phi arguments are selected when cond is |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
698 true. LOOP is the loop containing the if-converted region, GSI is |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
699 the place to insert the code for the if-conversion. */ |
| 0 | 700 |
| 701 static basic_block | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
702 find_phi_replacement_condition (struct loop *loop, |
| 0 | 703 basic_block bb, tree *cond, |
| 704 gimple_stmt_iterator *gsi) | |
| 705 { | |
| 706 edge first_edge, second_edge; | |
| 707 tree tmp_cond; | |
| 708 | |
| 709 gcc_assert (EDGE_COUNT (bb->preds) == 2); | |
| 710 first_edge = EDGE_PRED (bb, 0); | |
| 711 second_edge = EDGE_PRED (bb, 1); | |
| 712 | |
| 713 /* Use condition based on following criteria: | |
| 714 1) | |
| 715 S1: x = !c ? a : b; | |
| 716 | |
| 717 S2: x = c ? b : a; | |
| 718 | |
| 719 S2 is preferred over S1. Make 'b' first_bb and use its condition. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
720 |
| 0 | 721 2) Do not make loop header first_bb. |
| 722 | |
| 723 3) | |
| 724 S1: x = !(c == d)? a : b; | |
| 725 | |
| 726 S21: t1 = c == d; | |
| 727 S22: x = t1 ? b : a; | |
| 728 | |
| 729 S3: x = (c == d) ? b : a; | |
| 730 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
731 S3 is preferred over S1 and S2*, Make 'b' first_bb and use |
| 0 | 732 its condition. |
| 733 | |
| 734 4) If pred B is dominated by pred A then use pred B's condition. | |
| 735 See PR23115. */ | |
| 736 | |
| 737 /* Select condition that is not TRUTH_NOT_EXPR. */ | |
| 738 tmp_cond = (tree) (first_edge->src)->aux; | |
| 739 gcc_assert (tmp_cond); | |
| 740 | |
| 741 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) | |
| 742 { | |
| 743 edge tmp_edge; | |
| 744 | |
| 745 tmp_edge = first_edge; | |
| 746 first_edge = second_edge; | |
| 747 second_edge = tmp_edge; | |
| 748 } | |
| 749 | |
| 750 /* Check if FIRST_BB is loop header or not and make sure that | |
| 751 FIRST_BB does not dominate SECOND_BB. */ | |
| 752 if (first_edge->src == loop->header | |
| 753 || dominated_by_p (CDI_DOMINATORS, | |
| 754 second_edge->src, first_edge->src)) | |
| 755 { | |
| 756 *cond = (tree) (second_edge->src)->aux; | |
| 757 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
758 /* If there is a condition on an incoming edge, add it to the |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
759 incoming bb predicate. */ |
| 0 | 760 if (second_edge->aux) |
| 761 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, | |
| 762 *cond, (tree) second_edge->aux); | |
| 763 | |
| 764 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR) | |
| 765 *cond = invert_truthvalue (*cond); | |
| 766 else | |
| 767 /* Select non loop header bb. */ | |
| 768 first_edge = second_edge; | |
| 769 } | |
| 770 else | |
| 771 { | |
| 772 *cond = (tree) (first_edge->src)->aux; | |
| 773 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
774 /* If there is a condition on an incoming edge, add it to the |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
775 incoming bb predicate. */ |
| 0 | 776 if (first_edge->aux) |
| 777 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, | |
| 778 *cond, (tree) first_edge->aux); | |
| 779 } | |
| 780 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
781 /* Gimplify the condition: the vectorizer prefers to have gimple |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
782 values as conditions. Various targets use different means to |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
783 communicate conditions in vector compare operations. Using a |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
784 gimple value allows the compiler to emit vector compare and |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
785 select RTL without exposing compare's result. */ |
| 0 | 786 *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond), |
| 787 false, NULL_TREE, | |
| 788 true, GSI_SAME_STMT); | |
| 789 if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond)) | |
| 790 { | |
| 791 gimple new_stmt; | |
| 792 | |
| 793 new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); | |
| 794 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); | |
| 795 *cond = gimple_assign_lhs (new_stmt); | |
| 796 } | |
| 797 | |
| 798 gcc_assert (*cond); | |
| 799 | |
| 800 return first_edge->src; | |
| 801 } | |
| 802 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
803 /* Replace PHI node with conditional modify expr using COND. This |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
804 routine does not handle PHI nodes with more than two arguments. |
| 0 | 805 |
| 806 For example, | |
| 807 S1: A = PHI <x1(1), x2(5) | |
| 808 is converted into, | |
| 809 S2: A = cond ? x1 : x2; | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
810 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
811 The generated code is inserted at GSI that points to the top of |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
812 basic block's statement list. When COND is true, phi arg from |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
813 TRUE_BB is selected. */ |
| 0 | 814 |
| 815 static void | |
| 816 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond, | |
| 817 basic_block true_bb, | |
| 818 gimple_stmt_iterator *gsi) | |
| 819 { | |
| 820 gimple new_stmt; | |
| 821 basic_block bb; | |
| 822 tree rhs; | |
| 823 tree arg_0, arg_1; | |
| 824 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
825 gcc_assert (gimple_code (phi) == GIMPLE_PHI |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
826 && gimple_phi_num_args (phi) == 2); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
827 |
| 0 | 828 bb = gimple_bb (phi); |
| 829 | |
| 830 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ | |
| 831 if (EDGE_PRED (bb, 1)->src == true_bb) | |
| 832 { | |
| 833 arg_0 = gimple_phi_arg_def (phi, 1); | |
| 834 arg_1 = gimple_phi_arg_def (phi, 0); | |
| 835 } | |
| 836 else | |
| 837 { | |
| 838 arg_0 = gimple_phi_arg_def (phi, 0); | |
| 839 arg_1 = gimple_phi_arg_def (phi, 1); | |
| 840 } | |
| 841 | |
| 842 /* Build new RHS using selected condition and arguments. */ | |
| 843 rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), | |
| 844 unshare_expr (cond), unshare_expr (arg_0), | |
| 845 unshare_expr (arg_1)); | |
| 846 | |
| 847 new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs); | |
| 848 SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt; | |
| 849 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); | |
| 850 update_stmt (new_stmt); | |
| 851 | |
| 852 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 853 { | |
| 854 fprintf (dump_file, "new phi replacement stmt\n"); | |
| 855 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); | |
| 856 } | |
| 857 } | |
| 858 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
859 /* Process phi nodes for the given LOOP. Replace phi nodes with |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
860 conditional modify expressions. */ |
| 0 | 861 |
| 862 static void | |
| 863 process_phi_nodes (struct loop *loop) | |
| 864 { | |
| 865 basic_block bb; | |
| 866 unsigned int orig_loop_num_nodes = loop->num_nodes; | |
| 867 unsigned int i; | |
| 868 | |
| 869 for (i = 1; i < orig_loop_num_nodes; i++) | |
| 870 { | |
| 871 gimple phi; | |
| 872 tree cond = NULL_TREE; | |
| 873 gimple_stmt_iterator gsi, phi_gsi; | |
| 874 basic_block true_bb = NULL; | |
| 875 bb = ifc_bbs[i]; | |
| 876 | |
| 877 if (bb == loop->header) | |
| 878 continue; | |
| 879 | |
| 880 phi_gsi = gsi_start_phis (bb); | |
| 881 gsi = gsi_after_labels (bb); | |
| 882 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
883 /* BB has two predecessors. Using predecessor's aux field, set |
| 0 | 884 appropriate condition for the PHI node replacement. */ |
| 885 if (!gsi_end_p (phi_gsi)) | |
| 886 true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi); | |
| 887 | |
| 888 while (!gsi_end_p (phi_gsi)) | |
| 889 { | |
| 890 phi = gsi_stmt (phi_gsi); | |
| 891 replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi); | |
| 892 release_phi_node (phi); | |
| 893 gsi_next (&phi_gsi); | |
| 894 } | |
| 895 set_phi_nodes (bb, NULL); | |
| 896 } | |
| 897 } | |
| 898 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
899 /* Combine all the basic blocks from LOOP into one or two super basic |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
900 blocks. Replace PHI nodes with conditional modify expressions. */ |
| 0 | 901 |
| 902 static void | |
| 903 combine_blocks (struct loop *loop) | |
| 904 { | |
| 905 basic_block bb, exit_bb, merge_target_bb; | |
| 906 unsigned int orig_loop_num_nodes = loop->num_nodes; | |
| 907 unsigned int i; | |
| 908 edge e; | |
| 909 edge_iterator ei; | |
| 910 | |
| 911 /* Process phi nodes to prepare blocks for merge. */ | |
| 912 process_phi_nodes (loop); | |
| 913 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
914 /* Merge basic blocks: first remove all the edges in the loop, |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
915 except for those from the exit block. */ |
| 0 | 916 exit_bb = NULL; |
| 917 for (i = 0; i < orig_loop_num_nodes; i++) | |
| 918 { | |
| 919 bb = ifc_bbs[i]; | |
| 920 if (bb_with_exit_edge_p (loop, bb)) | |
| 921 { | |
| 922 exit_bb = bb; | |
| 923 break; | |
| 924 } | |
| 925 } | |
| 926 gcc_assert (exit_bb != loop->latch); | |
| 927 | |
| 928 for (i = 1; i < orig_loop_num_nodes; i++) | |
| 929 { | |
| 930 bb = ifc_bbs[i]; | |
| 931 | |
| 932 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) | |
| 933 { | |
| 934 if (e->src == exit_bb) | |
| 935 ei_next (&ei); | |
| 936 else | |
| 937 remove_edge (e); | |
| 938 } | |
| 939 } | |
| 940 | |
| 941 if (exit_bb != NULL) | |
| 942 { | |
| 943 if (exit_bb != loop->header) | |
| 944 { | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
945 /* Connect this node to loop header. */ |
| 0 | 946 make_edge (loop->header, exit_bb, EDGE_FALLTHRU); |
| 947 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); | |
| 948 } | |
| 949 | |
| 950 /* Redirect non-exit edges to loop->latch. */ | |
| 951 FOR_EACH_EDGE (e, ei, exit_bb->succs) | |
| 952 { | |
| 953 if (!loop_exit_edge_p (loop, e)) | |
| 954 redirect_edge_and_branch (e, loop->latch); | |
| 955 } | |
| 956 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); | |
| 957 } | |
| 958 else | |
| 959 { | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
960 /* If the loop does not have an exit, reconnect header and latch. */ |
| 0 | 961 make_edge (loop->header, loop->latch, EDGE_FALLTHRU); |
| 962 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); | |
| 963 } | |
| 964 | |
| 965 merge_target_bb = loop->header; | |
| 966 for (i = 1; i < orig_loop_num_nodes; i++) | |
| 967 { | |
| 968 gimple_stmt_iterator gsi; | |
| 969 gimple_stmt_iterator last; | |
| 970 | |
| 971 bb = ifc_bbs[i]; | |
| 972 | |
| 973 if (bb == exit_bb || bb == loop->latch) | |
| 974 continue; | |
| 975 | |
| 976 /* Remove labels and make stmts member of loop->header. */ | |
| 977 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) | |
| 978 { | |
| 979 if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL) | |
| 980 gsi_remove (&gsi, true); | |
| 981 else | |
| 982 { | |
| 983 gimple_set_bb (gsi_stmt (gsi), merge_target_bb); | |
| 984 gsi_next (&gsi); | |
| 985 } | |
| 986 } | |
| 987 | |
| 988 /* Update stmt list. */ | |
| 989 last = gsi_last_bb (merge_target_bb); | |
| 990 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT); | |
| 991 set_bb_seq (bb, NULL); | |
| 992 | |
| 993 delete_basic_block (bb); | |
| 994 } | |
| 995 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
996 /* If possible, merge loop header to the block with the exit edge. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
997 This reduces the number of basic blocks to two, to please the |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
998 vectorizer that handles only loops with two nodes. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
999 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1000 FIXME: Call cleanup_tree_cfg. */ |
| 0 | 1001 if (exit_bb |
| 1002 && exit_bb != loop->header | |
| 1003 && can_merge_blocks_p (loop->header, exit_bb)) | |
| 1004 merge_blocks (loop->header, exit_bb); | |
| 1005 } | |
| 1006 | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1007 /* Main entry point: return true when LOOP is if-converted, otherwise |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1008 the loop remains unchanged. */ |
| 0 | 1009 |
| 1010 static bool | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1011 tree_if_conversion (struct loop *loop) |
| 0 | 1012 { |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1013 gimple_stmt_iterator itr; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1014 unsigned int i; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1015 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1016 ifc_bbs = NULL; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1017 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1018 /* If-conversion is not appropriate for all loops. First, check if |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1019 the loop is if-convertible. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1020 if (!if_convertible_loop_p (loop)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1021 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1022 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1023 fprintf (dump_file,"-------------------------\n"); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1024 if (ifc_bbs) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1025 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1026 free (ifc_bbs); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1027 ifc_bbs = NULL; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1028 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1029 free_dominance_info (CDI_POST_DOMINATORS); |
| 0 | 1030 return false; |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1031 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1032 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1033 for (i = 0; i < loop->num_nodes; i++) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1034 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1035 basic_block bb = ifc_bbs [i]; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1036 tree cond = (tree) bb->aux; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1037 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1038 /* Process all the statements in this basic block. |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1039 Remove conditional expression, if any, and annotate |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1040 destination basic block(s) appropriately. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1041 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1042 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1043 gimple t = gsi_stmt (itr); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1044 cond = tree_if_convert_stmt (loop, t, cond, &itr); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1045 if (!gsi_end_p (itr)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1046 gsi_next (&itr); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1047 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1048 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1049 /* If current bb has only one successor, then consider it as an |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1050 unconditional goto. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1051 if (single_succ_p (bb)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1052 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1053 basic_block bb_n = single_succ (bb); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1054 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1055 /* The successor bb inherits the predicate of its |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1056 predecessor. If there is no predicate in the predecessor |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1057 bb, then consider the successor bb as always executed. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1058 if (cond == NULL_TREE) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1059 cond = boolean_true_node; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1060 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1061 add_to_predicate_list (bb_n, cond); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1062 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1063 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1064 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1065 /* Now, all statements are if-converted and basic blocks are |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1066 annotated appropriately. Combine all the basic blocks into one |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1067 huge basic block. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1068 combine_blocks (loop); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1069 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1070 /* clean up */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1071 clean_predicate_lists (loop); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1072 free (ifc_bbs); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1073 ifc_bbs = NULL; |
| 0 | 1074 |
| 1075 return true; | |
| 1076 } | |
| 1077 | |
| 1078 /* Tree if-conversion pass management. */ | |
| 1079 | |
| 1080 static unsigned int | |
| 1081 main_tree_if_conversion (void) | |
| 1082 { | |
| 1083 loop_iterator li; | |
| 1084 struct loop *loop; | |
| 1085 | |
| 1086 if (number_of_loops () <= 1) | |
| 1087 return 0; | |
| 1088 | |
| 1089 FOR_EACH_LOOP (li, loop, 0) | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1090 tree_if_conversion (loop); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1091 |
| 0 | 1092 return 0; |
| 1093 } | |
| 1094 | |
| 1095 static bool | |
| 1096 gate_tree_if_conversion (void) | |
| 1097 { | |
| 1098 return flag_tree_vectorize != 0; | |
| 1099 } | |
| 1100 | |
| 1101 struct gimple_opt_pass pass_if_conversion = | |
| 1102 { | |
| 1103 { | |
| 1104 GIMPLE_PASS, | |
| 1105 "ifcvt", /* name */ | |
| 1106 gate_tree_if_conversion, /* gate */ | |
| 1107 main_tree_if_conversion, /* execute */ | |
| 1108 NULL, /* sub */ | |
| 1109 NULL, /* next */ | |
| 1110 0, /* static_pass_number */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1111 TV_NONE, /* tv_id */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1112 PROP_cfg | PROP_ssa, /* properties_required */ |
| 0 | 1113 0, /* properties_provided */ |
| 1114 0, /* properties_destroyed */ | |
| 1115 0, /* todo_flags_start */ | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1116 TODO_dump_func | TODO_verify_stmts | TODO_verify_flow |
| 0 | 1117 /* todo_flags_finish */ |
| 1118 } | |
| 1119 }; |