Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-if-conv.c @ 158:494b0b89df80 default tip
...
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 25 May 2020 18:13:55 +0900 |
parents | 1830386684a0 |
children |
rev | line source |
---|---|
0 | 1 /* If-conversion for vectorizer. |
145 | 2 Copyright (C) 2004-2020 Free Software Foundation, Inc. |
0 | 3 Contributed by Devang Patel <dpatel@apple.com> |
4 | |
5 This file is part of GCC. | |
6 | |
7 GCC is free software; you can redistribute it and/or modify it under | |
8 the terms of the GNU General Public License as published by the Free | |
9 Software Foundation; either version 3, or (at your option) any later | |
10 version. | |
11 | |
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 for more details. | |
16 | |
17 You should have received a copy of the GNU General Public License | |
18 along with GCC; see the file COPYING3. If not see | |
19 <http://www.gnu.org/licenses/>. */ | |
20 | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
21 /* 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
|
22 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
|
23 conditions. |
0 | 24 |
25 A short description of if-conversion: | |
26 | |
27 o Decide if a loop is if-convertible or not. | |
28 o Walk all loop basic blocks in breadth first order (BFS order). | |
29 o Remove conditional statements (at the end of basic block) | |
30 and propagate condition into destination basic blocks' | |
31 predicate list. | |
32 o Replace modify expression with conditional modify expression | |
33 using current basic block's condition. | |
34 o Merge all basic blocks | |
35 o Replace phi nodes with conditional modify expr | |
36 o Merge all basic blocks into header | |
37 | |
38 Sample transformation: | |
39 | |
40 INPUT | |
41 ----- | |
42 | |
43 # i_23 = PHI <0(0), i_18(10)>; | |
44 <L0>:; | |
45 j_15 = A[i_23]; | |
46 if (j_15 > 41) goto <L1>; else goto <L17>; | |
47 | |
48 <L17>:; | |
49 goto <bb 3> (<L3>); | |
50 | |
51 <L1>:; | |
52 | |
53 # iftmp.2_4 = PHI <0(8), 42(2)>; | |
54 <L3>:; | |
55 A[i_23] = iftmp.2_4; | |
56 i_18 = i_23 + 1; | |
57 if (i_18 <= 15) goto <L19>; else goto <L18>; | |
58 | |
59 <L19>:; | |
60 goto <bb 1> (<L0>); | |
61 | |
62 <L18>:; | |
63 | |
64 OUTPUT | |
65 ------ | |
66 | |
67 # i_23 = PHI <0(0), i_18(10)>; | |
68 <L0>:; | |
69 j_15 = A[i_23]; | |
70 | |
71 <L3>:; | |
72 iftmp.2_4 = j_15 > 41 ? 42 : 0; | |
73 A[i_23] = iftmp.2_4; | |
74 i_18 = i_23 + 1; | |
75 if (i_18 <= 15) goto <L19>; else goto <L18>; | |
76 | |
77 <L19>:; | |
78 goto <bb 1> (<L0>); | |
79 | |
80 <L18>:; | |
81 */ | |
82 | |
83 #include "config.h" | |
84 #include "system.h" | |
85 #include "coretypes.h" | |
111 | 86 #include "backend.h" |
87 #include "rtl.h" | |
0 | 88 #include "tree.h" |
111 | 89 #include "gimple.h" |
90 #include "cfghooks.h" | |
91 #include "tree-pass.h" | |
92 #include "ssa.h" | |
93 #include "expmed.h" | |
94 #include "optabs-query.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
|
95 #include "gimple-pretty-print.h" |
111 | 96 #include "alias.h" |
97 #include "fold-const.h" | |
98 #include "stor-layout.h" | |
99 #include "gimple-fold.h" | |
100 #include "gimplify.h" | |
101 #include "gimple-iterator.h" | |
102 #include "gimplify-me.h" | |
103 #include "tree-cfg.h" | |
104 #include "tree-into-ssa.h" | |
105 #include "tree-ssa.h" | |
0 | 106 #include "cfgloop.h" |
107 #include "tree-data-ref.h" | |
108 #include "tree-scalar-evolution.h" | |
111 | 109 #include "tree-ssa-loop.h" |
110 #include "tree-ssa-loop-niter.h" | |
111 #include "tree-ssa-loop-ivopts.h" | |
112 #include "tree-ssa-address.h" | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
113 #include "dbgcnt.h" |
111 | 114 #include "tree-hash-traits.h" |
115 #include "varasm.h" | |
116 #include "builtins.h" | |
117 #include "cfganal.h" | |
131 | 118 #include "internal-fn.h" |
119 #include "fold-const.h" | |
145 | 120 #include "tree-ssa-sccvn.h" |
121 #include "tree-cfgcleanup.h" | |
122 #include "tree-ssa-dse.h" | |
111 | 123 |
124 /* Only handle PHIs with no more arguments unless we are asked to by | |
125 simd pragma. */ | |
126 #define MAX_PHI_ARG_NUM \ | |
145 | 127 ((unsigned) param_max_tree_if_conversion_phi_args) |
111 | 128 |
131 | 129 /* True if we've converted a statement that was only executed when some |
130 condition C was true, and if for correctness we need to predicate the | |
131 statement to ensure that it is a no-op when C is false. See | |
132 predicate_statements for the kinds of predication we support. */ | |
133 static bool need_to_predicate; | |
111 | 134 |
135 /* Indicate if there are any complicated PHIs that need to be handled in | |
136 if-conversion. Complicated PHI has more than two arguments and can't | |
137 be degenerated to two arguments PHI. See more information in comment | |
138 before phi_convertible_by_degenerating_args. */ | |
139 static bool any_complicated_phi; | |
140 | |
141 /* Hash for struct innermost_loop_behavior. It depends on the user to | |
142 free the memory. */ | |
143 | |
144 struct innermost_loop_behavior_hash : nofree_ptr_hash <innermost_loop_behavior> | |
145 { | |
146 static inline hashval_t hash (const value_type &); | |
147 static inline bool equal (const value_type &, | |
148 const compare_type &); | |
149 }; | |
150 | |
151 inline hashval_t | |
152 innermost_loop_behavior_hash::hash (const value_type &e) | |
153 { | |
154 hashval_t hash; | |
155 | |
156 hash = iterative_hash_expr (e->base_address, 0); | |
157 hash = iterative_hash_expr (e->offset, hash); | |
158 hash = iterative_hash_expr (e->init, hash); | |
159 return iterative_hash_expr (e->step, hash); | |
160 } | |
161 | |
162 inline bool | |
163 innermost_loop_behavior_hash::equal (const value_type &e1, | |
164 const compare_type &e2) | |
165 { | |
166 if ((e1->base_address && !e2->base_address) | |
167 || (!e1->base_address && e2->base_address) | |
168 || (!e1->offset && e2->offset) | |
169 || (e1->offset && !e2->offset) | |
170 || (!e1->init && e2->init) | |
171 || (e1->init && !e2->init) | |
172 || (!e1->step && e2->step) | |
173 || (e1->step && !e2->step)) | |
174 return false; | |
175 | |
176 if (e1->base_address && e2->base_address | |
177 && !operand_equal_p (e1->base_address, e2->base_address, 0)) | |
178 return false; | |
179 if (e1->offset && e2->offset | |
180 && !operand_equal_p (e1->offset, e2->offset, 0)) | |
181 return false; | |
182 if (e1->init && e2->init | |
183 && !operand_equal_p (e1->init, e2->init, 0)) | |
184 return false; | |
185 if (e1->step && e2->step | |
186 && !operand_equal_p (e1->step, e2->step, 0)) | |
187 return false; | |
188 | |
189 return true; | |
190 } | |
0 | 191 |
192 /* List of basic blocks in if-conversion-suitable order. */ | |
193 static basic_block *ifc_bbs; | |
194 | |
111 | 195 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */ |
196 static hash_map<innermost_loop_behavior_hash, | |
197 data_reference_p> *innermost_DR_map; | |
198 | |
199 /* Hash table to store <base reference, DR> pairs. */ | |
200 static hash_map<tree_operand_hash, data_reference_p> *baseref_DR_map; | |
201 | |
131 | 202 /* List of redundant SSA names: the first should be replaced by the second. */ |
203 static vec< std::pair<tree, tree> > redundant_ssa_names; | |
204 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
205 /* Structure used to predicate basic blocks. This is attached to the |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
206 ->aux field of the BBs in the loop to be if-converted. */ |
111 | 207 struct bb_predicate { |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
208 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
209 /* The condition under which this basic block is executed. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
210 tree predicate; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
211 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
212 /* PREDICATE is gimplified, and the sequence of statements is |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
213 recorded here, in order to avoid the duplication of computations |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
214 that occur in previous conditions. See PR44483. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
215 gimple_seq predicate_gimplified_stmts; |
111 | 216 }; |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
217 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
218 /* Returns true when the basic block BB has a predicate. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
219 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
220 static inline bool |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
221 bb_has_predicate (basic_block bb) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
222 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
223 return bb->aux != NULL; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
224 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
225 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
226 /* Returns the gimplified predicate for basic block BB. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
227 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
228 static inline tree |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
229 bb_predicate (basic_block bb) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
230 { |
111 | 231 return ((struct bb_predicate *) bb->aux)->predicate; |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
232 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
233 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
234 /* Sets the gimplified predicate COND for basic block BB. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
235 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
236 static inline void |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
237 set_bb_predicate (basic_block bb, tree cond) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
238 { |
111 | 239 gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR |
240 && is_gimple_condexpr (TREE_OPERAND (cond, 0))) | |
241 || is_gimple_condexpr (cond)); | |
242 ((struct bb_predicate *) bb->aux)->predicate = cond; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
243 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
244 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
245 /* Returns the sequence of statements of the gimplification of the |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
246 predicate for basic block BB. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
247 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
248 static inline gimple_seq |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
249 bb_predicate_gimplified_stmts (basic_block bb) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
250 { |
111 | 251 return ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts; |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
252 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
253 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
254 /* Sets the sequence of statements STMTS of the gimplification of the |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
255 predicate for basic block BB. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
256 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
257 static inline void |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
258 set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
259 { |
111 | 260 ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts; |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
261 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
262 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
263 /* Adds the sequence of statements STMTS to the sequence of statements |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
264 of the predicate for basic block BB. */ |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
265 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
266 static inline void |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
267 add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
268 { |
131 | 269 /* We might have updated some stmts in STMTS via force_gimple_operand |
270 calling fold_stmt and that producing multiple stmts. Delink immediate | |
271 uses so update_ssa after loop versioning doesn't get confused for | |
272 the not yet inserted predicates. | |
273 ??? This should go away once we reliably avoid updating stmts | |
274 not in any BB. */ | |
275 for (gimple_stmt_iterator gsi = gsi_start (stmts); | |
276 !gsi_end_p (gsi); gsi_next (&gsi)) | |
277 { | |
278 gimple *stmt = gsi_stmt (gsi); | |
279 delink_stmt_imm_use (stmt); | |
280 gimple_set_modified (stmt, true); | |
281 } | |
111 | 282 gimple_seq_add_seq_without_update |
283 (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
284 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
285 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
286 /* Initializes to TRUE the predicate of basic block BB. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
287 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
288 static inline void |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
289 init_bb_predicate (basic_block bb) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
290 { |
111 | 291 bb->aux = XNEW (struct bb_predicate); |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
292 set_bb_predicate_gimplified_stmts (bb, NULL); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
293 set_bb_predicate (bb, boolean_true_node); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
294 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
295 |
131 | 296 /* Release the SSA_NAMEs associated with the predicate of basic block BB. */ |
111 | 297 |
298 static inline void | |
299 release_bb_predicate (basic_block bb) | |
300 { | |
301 gimple_seq stmts = bb_predicate_gimplified_stmts (bb); | |
302 if (stmts) | |
303 { | |
131 | 304 /* Ensure that these stmts haven't yet been added to a bb. */ |
111 | 305 if (flag_checking) |
306 for (gimple_stmt_iterator i = gsi_start (stmts); | |
307 !gsi_end_p (i); gsi_next (&i)) | |
131 | 308 gcc_assert (! gimple_bb (gsi_stmt (i))); |
309 | |
310 /* Discard them. */ | |
311 gimple_seq_discard (stmts); | |
111 | 312 set_bb_predicate_gimplified_stmts (bb, NULL); |
313 } | |
314 } | |
315 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
316 /* Free the predicate of basic block BB. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
317 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
318 static inline void |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
319 free_bb_predicate (basic_block bb) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
320 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
321 if (!bb_has_predicate (bb)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
322 return; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
323 |
111 | 324 release_bb_predicate (bb); |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
325 free (bb->aux); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
326 bb->aux = NULL; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
327 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
328 |
111 | 329 /* Reinitialize predicate of BB with the true predicate. */ |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
330 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
331 static inline void |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
332 reset_bb_predicate (basic_block bb) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
333 { |
111 | 334 if (!bb_has_predicate (bb)) |
335 init_bb_predicate (bb); | |
336 else | |
337 { | |
338 release_bb_predicate (bb); | |
339 set_bb_predicate (bb, boolean_true_node); | |
340 } | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
341 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
342 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
343 /* Returns a new SSA_NAME of type TYPE that is assigned the value of |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
344 the expression EXPR. Inserts the statement created for this |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
345 computation before GSI and leaves the iterator GSI at the same |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
346 statement. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
347 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
348 static tree |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
349 ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi) |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
350 { |
111 | 351 tree new_name = make_temp_ssa_name (type, NULL, "_ifc_"); |
352 gimple *stmt = gimple_build_assign (new_name, expr); | |
353 gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi))); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
354 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); |
111 | 355 return new_name; |
356 } | |
357 | |
358 /* Return true when COND is a false predicate. */ | |
359 | |
360 static inline bool | |
361 is_false_predicate (tree cond) | |
362 { | |
363 return (cond != NULL_TREE | |
364 && (cond == boolean_false_node | |
365 || integer_zerop (cond))); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
366 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
367 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
368 /* Return true when COND is a true predicate. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
369 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
370 static inline bool |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
371 is_true_predicate (tree cond) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
372 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
373 return (cond == NULL_TREE |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
374 || cond == boolean_true_node |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
375 || integer_onep (cond)); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
376 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
377 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
378 /* Returns true when BB has a predicate that is not trivial: true or |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
379 NULL_TREE. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
380 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
381 static inline bool |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
382 is_predicated (basic_block bb) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
383 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
384 return !is_true_predicate (bb_predicate (bb)); |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
385 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
386 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
387 /* Parses the predicate COND and returns its comparison code and |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
388 operands OP0 and OP1. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
389 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
390 static enum tree_code |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
391 parse_predicate (tree cond, tree *op0, tree *op1) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
392 { |
111 | 393 gimple *s; |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
394 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
395 if (TREE_CODE (cond) == SSA_NAME |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
396 && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond))) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
397 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
398 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
399 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
400 *op0 = gimple_assign_rhs1 (s); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
401 *op1 = gimple_assign_rhs2 (s); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
402 return gimple_assign_rhs_code (s); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
403 } |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
404 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
405 else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
406 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
407 tree op = gimple_assign_rhs1 (s); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
408 tree type = TREE_TYPE (op); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
409 enum tree_code code = parse_predicate (op, op0, op1); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
410 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
411 return code == ERROR_MARK ? ERROR_MARK |
111 | 412 : invert_tree_comparison (code, HONOR_NANS (type)); |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
413 } |
0 | 414 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
415 return ERROR_MARK; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
416 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
417 |
111 | 418 if (COMPARISON_CLASS_P (cond)) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
419 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
420 *op0 = TREE_OPERAND (cond, 0); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
421 *op1 = TREE_OPERAND (cond, 1); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
422 return TREE_CODE (cond); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
423 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
424 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
425 return ERROR_MARK; |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
426 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
427 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
428 /* Returns the fold of predicate C1 OR C2 at location LOC. */ |
0 | 429 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
430 static tree |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
431 fold_or_predicates (location_t loc, tree c1, tree c2) |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
432 { |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
433 tree op1a, op1b, op2a, op2b; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
434 enum tree_code code1 = parse_predicate (c1, &op1a, &op1b); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
435 enum tree_code code2 = parse_predicate (c2, &op2a, &op2b); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
436 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
437 if (code1 != ERROR_MARK && code2 != ERROR_MARK) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
438 { |
145 | 439 tree t = maybe_fold_or_comparisons (boolean_type_node, code1, op1a, op1b, |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
440 code2, op2a, op2b); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
441 if (t) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
442 return t; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
443 } |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
444 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
445 return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
446 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
447 |
111 | 448 /* Returns either a COND_EXPR or the folded expression if the folded |
449 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR, | |
450 a constant or a SSA_NAME. */ | |
451 | |
452 static tree | |
453 fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs) | |
454 { | |
455 tree rhs1, lhs1, cond_expr; | |
456 | |
457 /* If COND is comparison r != 0 and r has boolean type, convert COND | |
458 to SSA_NAME to accept by vect bool pattern. */ | |
459 if (TREE_CODE (cond) == NE_EXPR) | |
460 { | |
461 tree op0 = TREE_OPERAND (cond, 0); | |
462 tree op1 = TREE_OPERAND (cond, 1); | |
463 if (TREE_CODE (op0) == SSA_NAME | |
464 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE | |
465 && (integer_zerop (op1))) | |
466 cond = op0; | |
467 } | |
468 cond_expr = fold_ternary (COND_EXPR, type, cond, rhs, lhs); | |
469 | |
470 if (cond_expr == NULL_TREE) | |
471 return build3 (COND_EXPR, type, cond, rhs, lhs); | |
472 | |
473 STRIP_USELESS_TYPE_CONVERSION (cond_expr); | |
474 | |
475 if (is_gimple_val (cond_expr)) | |
476 return cond_expr; | |
477 | |
478 if (TREE_CODE (cond_expr) == ABS_EXPR) | |
479 { | |
480 rhs1 = TREE_OPERAND (cond_expr, 1); | |
481 STRIP_USELESS_TYPE_CONVERSION (rhs1); | |
482 if (is_gimple_val (rhs1)) | |
483 return build1 (ABS_EXPR, type, rhs1); | |
484 } | |
485 | |
486 if (TREE_CODE (cond_expr) == MIN_EXPR | |
487 || TREE_CODE (cond_expr) == MAX_EXPR) | |
488 { | |
489 lhs1 = TREE_OPERAND (cond_expr, 0); | |
490 STRIP_USELESS_TYPE_CONVERSION (lhs1); | |
491 rhs1 = TREE_OPERAND (cond_expr, 1); | |
492 STRIP_USELESS_TYPE_CONVERSION (rhs1); | |
493 if (is_gimple_val (rhs1) && is_gimple_val (lhs1)) | |
494 return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1); | |
495 } | |
496 return build3 (COND_EXPR, type, cond, rhs, lhs); | |
497 } | |
498 | |
499 /* Add condition NC to the predicate list of basic block BB. LOOP is | |
500 the loop to be if-converted. Use predicate of cd-equivalent block | |
501 for join bb if it exists: we call basic blocks bb1 and bb2 | |
502 cd-equivalent if they are executed under the same condition. */ | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
503 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
504 static inline void |
145 | 505 add_to_predicate_list (class loop *loop, basic_block bb, tree nc) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
506 { |
111 | 507 tree bc, *tp; |
508 basic_block dom_bb; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
509 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
510 if (is_true_predicate (nc)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
511 return; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
512 |
111 | 513 /* If dominance tells us this basic block is always executed, |
514 don't record any predicates for it. */ | |
515 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) | |
516 return; | |
517 | |
518 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); | |
519 /* We use notion of cd equivalence to get simpler predicate for | |
520 join block, e.g. if join block has 2 predecessors with predicates | |
521 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of | |
522 p1 & p2 | p1 & !p2. */ | |
523 if (dom_bb != loop->header | |
524 && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb) | |
525 { | |
526 gcc_assert (flow_bb_inside_loop_p (loop, dom_bb)); | |
527 bc = bb_predicate (dom_bb); | |
528 if (!is_true_predicate (bc)) | |
529 set_bb_predicate (bb, bc); | |
530 else | |
531 gcc_assert (is_true_predicate (bb_predicate (bb))); | |
532 if (dump_file && (dump_flags & TDF_DETAILS)) | |
533 fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n", | |
534 dom_bb->index, bb->index); | |
535 return; | |
536 } | |
537 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
538 if (!is_predicated (bb)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
539 bc = nc; |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
540 else |
0 | 541 { |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
542 bc = bb_predicate (bb); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
543 bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc); |
111 | 544 if (is_true_predicate (bc)) |
545 { | |
546 reset_bb_predicate (bb); | |
547 return; | |
548 } | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
549 } |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
550 |
111 | 551 /* Allow a TRUTH_NOT_EXPR around the main predicate. */ |
552 if (TREE_CODE (bc) == TRUTH_NOT_EXPR) | |
553 tp = &TREE_OPERAND (bc, 0); | |
554 else | |
555 tp = &bc; | |
556 if (!is_gimple_condexpr (*tp)) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
557 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
558 gimple_seq stmts; |
111 | 559 *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE); |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
560 add_bb_predicate_gimplified_stmts (bb, stmts); |
0 | 561 } |
111 | 562 set_bb_predicate (bb, bc); |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
563 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
564 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
565 /* Add the condition COND to the previous condition PREV_COND, and add |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
566 this to the predicate list of the destination of edge E. LOOP is |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
567 the loop to be if-converted. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
568 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
569 static void |
145 | 570 add_to_dst_predicate_list (class loop *loop, edge e, |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
571 tree prev_cond, tree cond) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
572 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
573 if (!flow_bb_inside_loop_p (loop, e->dest)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
574 return; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
575 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
576 if (!is_true_predicate (prev_cond)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
577 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
578 prev_cond, cond); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
579 |
111 | 580 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest)) |
581 add_to_predicate_list (loop, e->dest, cond); | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
582 } |
0 | 583 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
584 /* Return true if one of the successor edges of BB exits LOOP. */ |
0 | 585 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
586 static bool |
145 | 587 bb_with_exit_edge_p (class loop *loop, basic_block bb) |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
588 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
589 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
|
590 edge_iterator ei; |
0 | 591 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
592 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
|
593 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
|
594 return true; |
0 | 595 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
596 return false; |
0 | 597 } |
598 | |
111 | 599 /* Given PHI which has more than two arguments, this function checks if |
600 it's if-convertible by degenerating its arguments. Specifically, if | |
601 below two conditions are satisfied: | |
602 | |
603 1) Number of PHI arguments with different values equals to 2 and one | |
604 argument has the only occurrence. | |
605 2) The edge corresponding to the unique argument isn't critical edge. | |
606 | |
607 Such PHI can be handled as PHIs have only two arguments. For example, | |
608 below PHI: | |
609 | |
610 res = PHI <A_1(e1), A_1(e2), A_2(e3)>; | |
611 | |
612 can be transformed into: | |
613 | |
614 res = (predicate of e3) ? A_2 : A_1; | |
615 | |
616 Return TRUE if it is the case, FALSE otherwise. */ | |
0 | 617 |
618 static bool | |
111 | 619 phi_convertible_by_degenerating_args (gphi *phi) |
620 { | |
621 edge e; | |
622 tree arg, t1 = NULL, t2 = NULL; | |
623 unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0; | |
624 unsigned int num_args = gimple_phi_num_args (phi); | |
625 | |
626 gcc_assert (num_args > 2); | |
627 | |
628 for (i = 0; i < num_args; i++) | |
629 { | |
630 arg = gimple_phi_arg_def (phi, i); | |
631 if (t1 == NULL || operand_equal_p (t1, arg, 0)) | |
632 { | |
633 n1++; | |
634 i1 = i; | |
635 t1 = arg; | |
636 } | |
637 else if (t2 == NULL || operand_equal_p (t2, arg, 0)) | |
638 { | |
639 n2++; | |
640 i2 = i; | |
641 t2 = arg; | |
642 } | |
643 else | |
644 return false; | |
645 } | |
646 | |
647 if (n1 != 1 && n2 != 1) | |
648 return false; | |
649 | |
650 /* Check if the edge corresponding to the unique arg is critical. */ | |
651 e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2); | |
652 if (EDGE_COUNT (e->src->succs) > 1) | |
653 return false; | |
654 | |
655 return true; | |
656 } | |
657 | |
658 /* Return true when PHI is if-convertible. PHI is part of loop LOOP | |
659 and it belongs to basic block BB. Note at this point, it is sure | |
660 that PHI is if-convertible. This function updates global variable | |
661 ANY_COMPLICATED_PHI if PHI is complicated. */ | |
662 | |
663 static bool | |
145 | 664 if_convertible_phi_p (class loop *loop, basic_block bb, gphi *phi) |
0 | 665 { |
666 if (dump_file && (dump_flags & TDF_DETAILS)) | |
667 { | |
668 fprintf (dump_file, "-------------------------\n"); | |
669 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); | |
670 } | |
671 | |
111 | 672 if (bb != loop->header |
673 && gimple_phi_num_args (phi) > 2 | |
674 && !phi_convertible_by_degenerating_args (phi)) | |
675 any_complicated_phi = true; | |
0 | 676 |
677 return true; | |
678 } | |
679 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
680 /* Records the status of a data reference. This struct is attached to |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
681 each DR->aux field. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
682 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
683 struct ifc_dr { |
111 | 684 bool rw_unconditionally; |
685 bool w_unconditionally; | |
686 bool written_at_least_once; | |
687 | |
688 tree rw_predicate; | |
689 tree w_predicate; | |
690 tree base_w_predicate; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
691 }; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
692 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
693 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux) |
111 | 694 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
695 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally) |
111 | 696 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally) |
697 | |
698 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in | |
699 HASH tables. While storing them in HASH table, it checks if the | |
700 reference is unconditionally read or written and stores that as a flag | |
701 information. For base reference it checks if it is written atlest once | |
702 unconditionally and stores it as flag information along with DR. | |
703 In other words for every data reference A in STMT there exist other | |
704 accesses to a data reference with the same base with predicates that | |
705 add up (OR-up) to the true predicate: this ensures that the data | |
706 reference A is touched (read or written) on every iteration of the | |
707 if-converted loop. */ | |
708 static void | |
709 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a) | |
710 { | |
711 | |
712 data_reference_p *master_dr, *base_master_dr; | |
713 tree base_ref = DR_BASE_OBJECT (a); | |
714 innermost_loop_behavior *innermost = &DR_INNERMOST (a); | |
715 tree ca = bb_predicate (gimple_bb (DR_STMT (a))); | |
716 bool exist1, exist2; | |
717 | |
718 master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1); | |
719 if (!exist1) | |
720 *master_dr = a; | |
721 | |
722 if (DR_IS_WRITE (a)) | |
723 { | |
724 IFC_DR (*master_dr)->w_predicate | |
725 = fold_or_predicates (UNKNOWN_LOCATION, ca, | |
726 IFC_DR (*master_dr)->w_predicate); | |
727 if (is_true_predicate (IFC_DR (*master_dr)->w_predicate)) | |
728 DR_W_UNCONDITIONALLY (*master_dr) = true; | |
729 } | |
730 IFC_DR (*master_dr)->rw_predicate | |
731 = fold_or_predicates (UNKNOWN_LOCATION, ca, | |
732 IFC_DR (*master_dr)->rw_predicate); | |
733 if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate)) | |
734 DR_RW_UNCONDITIONALLY (*master_dr) = true; | |
735 | |
736 if (DR_IS_WRITE (a)) | |
737 { | |
738 base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2); | |
739 if (!exist2) | |
740 *base_master_dr = a; | |
741 IFC_DR (*base_master_dr)->base_w_predicate | |
742 = fold_or_predicates (UNKNOWN_LOCATION, ca, | |
743 IFC_DR (*base_master_dr)->base_w_predicate); | |
744 if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate)) | |
745 DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true; | |
746 } | |
747 } | |
748 | |
749 /* Return TRUE if can prove the index IDX of an array reference REF is | |
750 within array bound. Return false otherwise. */ | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
751 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
752 static bool |
111 | 753 idx_within_array_bound (tree ref, tree *idx, void *dta) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
754 { |
131 | 755 wi::overflow_type overflow; |
111 | 756 widest_int niter, valid_niter, delta, wi_step; |
757 tree ev, init, step; | |
758 tree low, high; | |
145 | 759 class loop *loop = (class loop*) dta; |
111 | 760 |
761 /* Only support within-bound access for array references. */ | |
762 if (TREE_CODE (ref) != ARRAY_REF) | |
763 return false; | |
764 | |
765 /* For arrays at the end of the structure, we are not guaranteed that they | |
766 do not really extend over their declared size. However, for arrays of | |
767 size greater than one, this is unlikely to be intended. */ | |
768 if (array_at_struct_end_p (ref)) | |
769 return false; | |
770 | |
771 ev = analyze_scalar_evolution (loop, *idx); | |
772 ev = instantiate_parameters (loop, ev); | |
773 init = initial_condition (ev); | |
774 step = evolution_part_in_loop_num (ev, loop->num); | |
775 | |
776 if (!init || TREE_CODE (init) != INTEGER_CST | |
777 || (step && TREE_CODE (step) != INTEGER_CST)) | |
778 return false; | |
779 | |
780 low = array_ref_low_bound (ref); | |
781 high = array_ref_up_bound (ref); | |
782 | |
783 /* The case of nonconstant bounds could be handled, but it would be | |
784 complicated. */ | |
785 if (TREE_CODE (low) != INTEGER_CST | |
786 || !high || TREE_CODE (high) != INTEGER_CST) | |
787 return false; | |
788 | |
789 /* Check if the intial idx is within bound. */ | |
790 if (wi::to_widest (init) < wi::to_widest (low) | |
791 || wi::to_widest (init) > wi::to_widest (high)) | |
792 return false; | |
793 | |
794 /* The idx is always within bound. */ | |
795 if (!step || integer_zerop (step)) | |
796 return true; | |
797 | |
798 if (!max_loop_iterations (loop, &niter)) | |
799 return false; | |
800 | |
801 if (wi::to_widest (step) < 0) | |
802 { | |
803 delta = wi::to_widest (init) - wi::to_widest (low); | |
804 wi_step = -wi::to_widest (step); | |
805 } | |
806 else | |
807 { | |
808 delta = wi::to_widest (high) - wi::to_widest (init); | |
809 wi_step = wi::to_widest (step); | |
810 } | |
811 | |
812 valid_niter = wi::div_floor (delta, wi_step, SIGNED, &overflow); | |
813 /* The iteration space of idx is within array bound. */ | |
814 if (!overflow && niter <= valid_niter) | |
815 return true; | |
816 | |
817 return false; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
818 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
819 |
111 | 820 /* Return TRUE if ref is a within bound array reference. */ |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
821 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
822 static bool |
111 | 823 ref_within_array_bound (gimple *stmt, tree ref) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
824 { |
145 | 825 class loop *loop = loop_containing_stmt (stmt); |
111 | 826 |
827 gcc_assert (loop != NULL); | |
828 return for_each_index (&ref, idx_within_array_bound, loop); | |
829 } | |
830 | |
831 | |
832 /* Given a memory reference expression T, return TRUE if base object | |
833 it refers to is writable. The base object of a memory reference | |
834 is the main object being referenced, which is returned by function | |
835 get_base_address. */ | |
836 | |
837 static bool | |
838 base_object_writable (tree ref) | |
839 { | |
840 tree base_tree = get_base_address (ref); | |
841 | |
842 return (base_tree | |
843 && DECL_P (base_tree) | |
844 && decl_binds_to_current_def_p (base_tree) | |
845 && !TREE_READONLY (base_tree)); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
846 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
847 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
848 /* Return true when the memory references of STMT won't trap in the |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
849 if-converted code. There are two things that we have to check for: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
850 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
851 - writes to memory occur to writable memory: if-conversion of |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
852 memory writes transforms the conditional memory writes into |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
853 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
854 into "A[i] = cond ? foo : A[i]", and as the write to memory may not |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
855 be executed at all in the original code, it may be a readonly |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
856 memory. To check that A is not const-qualified, we check that |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
857 there exists at least an unconditional write to A in the current |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
858 function. |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
859 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
860 - reads or writes to memory are valid memory accesses for every |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
861 iteration. To check that the memory accesses are correctly formed |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
862 and that we are allowed to read and write in these locations, we |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
863 check that the memory accesses to be if-converted occur at every |
111 | 864 iteration unconditionally. |
865 | |
866 Returns true for the memory reference in STMT, same memory reference | |
867 is read or written unconditionally atleast once and the base memory | |
868 reference is written unconditionally once. This is to check reference | |
869 will not write fault. Also retuns true if the memory reference is | |
870 unconditionally read once then we are conditionally writing to memory | |
871 which is defined as read and write and is bound to the definition | |
872 we are seeing. */ | |
873 static bool | |
874 ifcvt_memrefs_wont_trap (gimple *stmt, vec<data_reference_p> drs) | |
875 { | |
131 | 876 /* If DR didn't see a reference here we can't use it to tell |
877 whether the ref traps or not. */ | |
878 if (gimple_uid (stmt) == 0) | |
879 return false; | |
880 | |
111 | 881 data_reference_p *master_dr, *base_master_dr; |
882 data_reference_p a = drs[gimple_uid (stmt) - 1]; | |
883 | |
884 tree base = DR_BASE_OBJECT (a); | |
885 innermost_loop_behavior *innermost = &DR_INNERMOST (a); | |
886 | |
887 gcc_assert (DR_STMT (a) == stmt); | |
888 gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a) | |
889 || DR_INIT (a) || DR_STEP (a)); | |
890 | |
891 master_dr = innermost_DR_map->get (innermost); | |
892 gcc_assert (master_dr != NULL); | |
893 | |
894 base_master_dr = baseref_DR_map->get (base); | |
895 | |
896 /* If a is unconditionally written to it doesn't trap. */ | |
897 if (DR_W_UNCONDITIONALLY (*master_dr)) | |
898 return true; | |
899 | |
900 /* If a is unconditionally accessed then ... | |
901 | |
902 Even a is conditional access, we can treat it as an unconditional | |
903 one if it's an array reference and all its index are within array | |
904 bound. */ | |
905 if (DR_RW_UNCONDITIONALLY (*master_dr) | |
906 || ref_within_array_bound (stmt, DR_REF (a))) | |
907 { | |
908 /* an unconditional read won't trap. */ | |
909 if (DR_IS_READ (a)) | |
910 return true; | |
911 | |
912 /* an unconditionaly write won't trap if the base is written | |
913 to unconditionally. */ | |
914 if (base_master_dr | |
915 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr)) | |
145 | 916 return flag_store_data_races; |
111 | 917 /* or the base is known to be not readonly. */ |
918 else if (base_object_writable (DR_REF (a))) | |
145 | 919 return flag_store_data_races; |
111 | 920 } |
921 | |
922 return false; | |
923 } | |
924 | |
925 /* Return true if STMT could be converted into a masked load or store | |
926 (conditional load or store based on a mask computed from bb predicate). */ | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
927 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
928 static bool |
111 | 929 ifcvt_can_use_mask_load_store (gimple *stmt) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
930 { |
131 | 931 /* Check whether this is a load or store. */ |
932 tree lhs = gimple_assign_lhs (stmt); | |
111 | 933 bool is_load; |
131 | 934 tree ref; |
111 | 935 if (gimple_store_p (stmt)) |
936 { | |
937 if (!is_gimple_val (gimple_assign_rhs1 (stmt))) | |
938 return false; | |
939 is_load = false; | |
940 ref = lhs; | |
941 } | |
942 else if (gimple_assign_load_p (stmt)) | |
943 { | |
944 is_load = true; | |
945 ref = gimple_assign_rhs1 (stmt); | |
946 } | |
947 else | |
948 return false; | |
949 | |
950 if (may_be_nonaddressable_p (ref)) | |
951 return false; | |
952 | |
953 /* Mask should be integer mode of the same size as the load/store | |
954 mode. */ | |
131 | 955 machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); |
111 | 956 if (!int_mode_for_mode (mode).exists () || VECTOR_MODE_P (mode)) |
957 return false; | |
958 | |
959 if (can_vec_mask_load_store_p (mode, VOIDmode, is_load)) | |
960 return true; | |
961 | |
962 return false; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
963 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
964 |
131 | 965 /* Return true if STMT could be converted from an operation that is |
966 unconditional to one that is conditional on a bb predicate mask. */ | |
967 | |
968 static bool | |
969 ifcvt_can_predicate (gimple *stmt) | |
970 { | |
971 basic_block bb = gimple_bb (stmt); | |
972 | |
973 if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize) | |
974 || bb->loop_father->dont_vectorize | |
975 || gimple_has_volatile_ops (stmt)) | |
976 return false; | |
977 | |
978 if (gimple_assign_single_p (stmt)) | |
979 return ifcvt_can_use_mask_load_store (stmt); | |
980 | |
981 tree_code code = gimple_assign_rhs_code (stmt); | |
982 tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
983 tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt)); | |
984 if (!types_compatible_p (lhs_type, rhs_type)) | |
985 return false; | |
986 internal_fn cond_fn = get_conditional_internal_fn (code); | |
987 return (cond_fn != IFN_LAST | |
988 && vectorized_internal_fn_supported_p (cond_fn, lhs_type)); | |
989 } | |
990 | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
991 /* 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
|
992 |
0 | 993 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
|
994 - 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
|
995 - it could trap, |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
996 - LHS is not var decl. */ |
0 | 997 |
998 static bool | |
111 | 999 if_convertible_gimple_assign_stmt_p (gimple *stmt, |
1000 vec<data_reference_p> refs) | |
0 | 1001 { |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1002 tree lhs = gimple_assign_lhs (stmt); |
0 | 1003 |
1004 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1005 { | |
1006 fprintf (dump_file, "-------------------------\n"); | |
1007 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1008 } | |
1009 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1010 if (!is_gimple_reg_type (TREE_TYPE (lhs))) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1011 return false; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1012 |
0 | 1013 /* Some of these constrains might be too conservative. */ |
1014 if (stmt_ends_bb_p (stmt) | |
1015 || gimple_has_volatile_ops (stmt) | |
1016 || (TREE_CODE (lhs) == SSA_NAME | |
1017 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) | |
1018 || gimple_has_side_effects (stmt)) | |
1019 { | |
1020 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1021 fprintf (dump_file, "stmt not suitable for ifcvt\n"); | |
1022 return false; | |
1023 } | |
1024 | |
111 | 1025 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because |
1026 in between if_convertible_loop_p and combine_blocks | |
1027 we can perform loop versioning. */ | |
1028 gimple_set_plf (stmt, GF_PLF_2, false); | |
1029 | |
1030 if ((! gimple_vuse (stmt) | |
1031 || gimple_could_trap_p_1 (stmt, false, false) | |
1032 || ! ifcvt_memrefs_wont_trap (stmt, refs)) | |
1033 && gimple_could_trap_p (stmt)) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1034 { |
131 | 1035 if (ifcvt_can_predicate (stmt)) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1036 { |
111 | 1037 gimple_set_plf (stmt, GF_PLF_2, true); |
131 | 1038 need_to_predicate = true; |
111 | 1039 return true; |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1040 } |
0 | 1041 if (dump_file && (dump_flags & TDF_DETAILS)) |
1042 fprintf (dump_file, "tree could trap...\n"); | |
1043 return false; | |
1044 } | |
1045 | |
111 | 1046 /* When if-converting stores force versioning, likewise if we |
1047 ended up generating store data races. */ | |
1048 if (gimple_vdef (stmt)) | |
131 | 1049 need_to_predicate = true; |
0 | 1050 |
1051 return true; | |
1052 } | |
1053 | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1054 /* 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
|
1055 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1056 A statement is if-convertible if: |
111 | 1057 - it is an if-convertible GIMPLE_ASSIGN, |
1058 - it is a GIMPLE_LABEL or a GIMPLE_COND, | |
1059 - it is builtins call. */ | |
0 | 1060 |
1061 static bool | |
111 | 1062 if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs) |
0 | 1063 { |
1064 switch (gimple_code (stmt)) | |
1065 { | |
1066 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
|
1067 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
|
1068 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
|
1069 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
|
1070 |
0 | 1071 case GIMPLE_ASSIGN: |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1072 return if_convertible_gimple_assign_stmt_p (stmt, refs); |
0 | 1073 |
111 | 1074 case GIMPLE_CALL: |
1075 { | |
1076 tree fndecl = gimple_call_fndecl (stmt); | |
1077 if (fndecl) | |
1078 { | |
1079 int flags = gimple_call_flags (stmt); | |
1080 if ((flags & ECF_CONST) | |
1081 && !(flags & ECF_LOOPING_CONST_OR_PURE) | |
1082 /* We can only vectorize some builtins at the moment, | |
1083 so restrict if-conversion to those. */ | |
131 | 1084 && fndecl_built_in_p (fndecl)) |
111 | 1085 return true; |
1086 } | |
1087 return false; | |
1088 } | |
1089 | |
0 | 1090 default: |
1091 /* Don't know what to do with 'em so don't do anything. */ | |
1092 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1093 { | |
1094 fprintf (dump_file, "don't know what to do\n"); | |
1095 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1096 } | |
1097 return false; | |
1098 } | |
1099 | |
1100 return true; | |
1101 } | |
1102 | |
111 | 1103 /* Assumes that BB has more than 1 predecessors. |
1104 Returns false if at least one successor is not on critical edge | |
1105 and true otherwise. */ | |
1106 | |
1107 static inline bool | |
1108 all_preds_critical_p (basic_block bb) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1109 { |
111 | 1110 edge e; |
1111 edge_iterator ei; | |
1112 | |
1113 FOR_EACH_EDGE (e, ei, bb->preds) | |
1114 if (EDGE_COUNT (e->src->succs) == 1) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1115 return false; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1116 return true; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1117 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1118 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1119 /* 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
|
1120 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
|
1121 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1122 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
|
1123 - 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
|
1124 - 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
|
1125 - 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
|
1126 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1127 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
|
1128 inside LOOP. */ |
0 | 1129 |
1130 static bool | |
145 | 1131 if_convertible_bb_p (class loop *loop, basic_block bb, basic_block exit_bb) |
0 | 1132 { |
1133 edge e; | |
1134 edge_iterator ei; | |
1135 | |
1136 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1137 fprintf (dump_file, "----------[%d]-------------\n", bb->index); | |
1138 | |
111 | 1139 if (EDGE_COUNT (bb->succs) > 2) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1140 return false; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1141 |
0 | 1142 if (exit_bb) |
1143 { | |
1144 if (bb != loop->latch) | |
1145 { | |
1146 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1147 fprintf (dump_file, "basic block after exit bb but before latch\n"); | |
1148 return false; | |
1149 } | |
1150 else if (!empty_block_p (bb)) | |
1151 { | |
1152 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1153 fprintf (dump_file, "non empty basic block after exit bb\n"); | |
1154 return false; | |
1155 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1156 else if (bb == loop->latch |
0 | 1157 && bb != exit_bb |
1158 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) | |
1159 { | |
1160 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1161 fprintf (dump_file, "latch is not dominated by exit_block\n"); | |
1162 return false; | |
1163 } | |
1164 } | |
1165 | |
1166 /* Be less adventurous and handle only normal edges. */ | |
1167 FOR_EACH_EDGE (e, ei, bb->succs) | |
111 | 1168 if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) |
0 | 1169 { |
1170 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
|
1171 fprintf (dump_file, "Difficult to handle edges\n"); |
0 | 1172 return false; |
1173 } | |
1174 | |
1175 return true; | |
1176 } | |
1177 | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1178 /* 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
|
1179 VISITED bitmap keeps track of the visited blocks. */ |
0 | 1180 |
1181 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
|
1182 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
|
1183 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1184 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
|
1185 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
|
1186 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
|
1187 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
|
1188 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
|
1189 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1190 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
|
1191 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1192 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1193 /* 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
|
1194 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
|
1195 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
|
1196 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
|
1197 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
|
1198 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1199 static basic_block * |
145 | 1200 get_loop_body_in_if_conv_order (const class loop *loop) |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1201 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1202 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
|
1203 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
|
1204 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
|
1205 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
|
1206 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
|
1207 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1208 gcc_assert (loop->num_nodes); |
111 | 1209 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)); |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1210 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1211 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
|
1212 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
|
1213 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1214 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
|
1215 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1216 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
|
1217 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
|
1218 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1219 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
|
1220 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1221 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
|
1222 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1223 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
|
1224 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
|
1225 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
|
1226 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
|
1227 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1228 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1229 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
|
1230 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1231 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
|
1232 || 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
|
1233 { |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1234 /* 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
|
1235 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
|
1236 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
|
1237 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1238 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1239 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1240 index++; |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1241 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1242 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
|
1243 && 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
|
1244 /* 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
|
1245 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
|
1246 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1247 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
|
1248 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
|
1249 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
|
1250 } |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1251 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1252 /* Returns true when the analysis of the predicates for all the basic |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1253 blocks in LOOP succeeded. |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1254 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1255 predicate_bbs first allocates the predicates of the basic blocks. |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1256 These fields are then initialized with the tree expressions |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1257 representing the predicates under which a basic block is executed |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1258 in the LOOP. As the loop->header is executed at each iteration, it |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1259 has the "true" predicate. Other statements executed under a |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1260 condition are predicated with that condition, for example |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1261 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1262 | if (x) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1263 | S1; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1264 | else |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1265 | S2; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1266 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1267 S1 will be predicated with "x", and |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1268 S2 will be predicated with "!x". */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1269 |
111 | 1270 static void |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1271 predicate_bbs (loop_p loop) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1272 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1273 unsigned int i; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1274 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1275 for (i = 0; i < loop->num_nodes; i++) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1276 init_bb_predicate (ifc_bbs[i]); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1277 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1278 for (i = 0; i < loop->num_nodes; i++) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1279 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1280 basic_block bb = ifc_bbs[i]; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1281 tree cond; |
111 | 1282 gimple *stmt; |
1283 | |
1284 /* The loop latch and loop exit block are always executed and | |
1285 have no extra conditions to be processed: skip them. */ | |
1286 if (bb == loop->latch | |
1287 || bb_with_exit_edge_p (loop, bb)) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1288 { |
111 | 1289 reset_bb_predicate (bb); |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1290 continue; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1291 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1292 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1293 cond = bb_predicate (bb); |
111 | 1294 stmt = last_stmt (bb); |
1295 if (stmt && gimple_code (stmt) == GIMPLE_COND) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1296 { |
111 | 1297 tree c2; |
1298 edge true_edge, false_edge; | |
1299 location_t loc = gimple_location (stmt); | |
1300 tree c = build2_loc (loc, gimple_cond_code (stmt), | |
1301 boolean_type_node, | |
1302 gimple_cond_lhs (stmt), | |
1303 gimple_cond_rhs (stmt)); | |
1304 | |
1305 /* Add new condition into destination's predicate list. */ | |
1306 extract_true_false_edges_from_block (gimple_bb (stmt), | |
1307 &true_edge, &false_edge); | |
1308 | |
1309 /* If C is true, then TRUE_EDGE is taken. */ | |
1310 add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond), | |
1311 unshare_expr (c)); | |
1312 | |
1313 /* If C is false, then FALSE_EDGE is taken. */ | |
1314 c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node, | |
1315 unshare_expr (c)); | |
1316 add_to_dst_predicate_list (loop, false_edge, | |
1317 unshare_expr (cond), c2); | |
1318 | |
1319 cond = NULL_TREE; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1320 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1321 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1322 /* If current bb has only one successor, then consider it as an |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1323 unconditional goto. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1324 if (single_succ_p (bb)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1325 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1326 basic_block bb_n = single_succ (bb); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1327 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1328 /* The successor bb inherits the predicate of its |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1329 predecessor. If there is no predicate in the predecessor |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1330 bb, then consider the successor bb as always executed. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1331 if (cond == NULL_TREE) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1332 cond = boolean_true_node; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1333 |
111 | 1334 add_to_predicate_list (loop, bb_n, cond); |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1335 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1336 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1337 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1338 /* The loop header is always executed. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1339 reset_bb_predicate (loop->header); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1340 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1341 && bb_predicate_gimplified_stmts (loop->latch) == NULL); |
111 | 1342 } |
1343 | |
1344 /* Build region by adding loop pre-header and post-header blocks. */ | |
1345 | |
1346 static vec<basic_block> | |
145 | 1347 build_region (class loop *loop) |
111 | 1348 { |
1349 vec<basic_block> region = vNULL; | |
1350 basic_block exit_bb = NULL; | |
1351 | |
1352 gcc_assert (ifc_bbs); | |
1353 /* The first element is loop pre-header. */ | |
1354 region.safe_push (loop_preheader_edge (loop)->src); | |
1355 | |
1356 for (unsigned int i = 0; i < loop->num_nodes; i++) | |
1357 { | |
1358 basic_block bb = ifc_bbs[i]; | |
1359 region.safe_push (bb); | |
1360 /* Find loop postheader. */ | |
1361 edge e; | |
1362 edge_iterator ei; | |
1363 FOR_EACH_EDGE (e, ei, bb->succs) | |
1364 if (loop_exit_edge_p (loop, e)) | |
1365 { | |
1366 exit_bb = e->dest; | |
1367 break; | |
1368 } | |
1369 } | |
1370 /* The last element is loop post-header. */ | |
1371 gcc_assert (exit_bb); | |
1372 region.safe_push (exit_bb); | |
1373 return region; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1374 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1375 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1376 /* Return true when LOOP is if-convertible. This is a helper function |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1377 for if_convertible_loop_p. REFS and DDRS are initialized and freed |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1378 in if_convertible_loop_p. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1379 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1380 static bool |
145 | 1381 if_convertible_loop_p_1 (class loop *loop, vec<data_reference_p> *refs) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1382 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1383 unsigned int i; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1384 basic_block exit_bb = NULL; |
111 | 1385 vec<basic_block> region; |
1386 | |
1387 if (find_data_references_in_loop (loop, refs) == chrec_dont_know) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1388 return false; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1389 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1390 calculate_dominance_info (CDI_DOMINATORS); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1391 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1392 /* Allow statements that can be handled during if-conversion. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1393 ifc_bbs = get_loop_body_in_if_conv_order (loop); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1394 if (!ifc_bbs) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1395 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1396 if (dump_file && (dump_flags & TDF_DETAILS)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1397 fprintf (dump_file, "Irreducible loop\n"); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1398 return false; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1399 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1400 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1401 for (i = 0; i < loop->num_nodes; i++) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1402 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1403 basic_block bb = ifc_bbs[i]; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1404 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1405 if (!if_convertible_bb_p (loop, bb, exit_bb)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1406 return false; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1407 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1408 if (bb_with_exit_edge_p (loop, bb)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1409 exit_bb = bb; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1410 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1411 |
111 | 1412 for (i = 0; i < loop->num_nodes; i++) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1413 { |
111 | 1414 basic_block bb = ifc_bbs[i]; |
1415 gimple_stmt_iterator gsi; | |
1416 | |
1417 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
1418 switch (gimple_code (gsi_stmt (gsi))) | |
1419 { | |
1420 case GIMPLE_LABEL: | |
1421 case GIMPLE_ASSIGN: | |
1422 case GIMPLE_CALL: | |
1423 case GIMPLE_DEBUG: | |
1424 case GIMPLE_COND: | |
1425 gimple_set_uid (gsi_stmt (gsi), 0); | |
1426 break; | |
1427 default: | |
1428 return false; | |
1429 } | |
1430 } | |
1431 | |
1432 data_reference_p dr; | |
1433 | |
1434 innermost_DR_map | |
1435 = new hash_map<innermost_loop_behavior_hash, data_reference_p>; | |
1436 baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>; | |
1437 | |
1438 /* Compute post-dominator tree locally. */ | |
1439 region = build_region (loop); | |
1440 calculate_dominance_info_for_region (CDI_POST_DOMINATORS, region); | |
1441 | |
1442 predicate_bbs (loop); | |
1443 | |
1444 /* Free post-dominator tree since it is not used after predication. */ | |
1445 free_dominance_info_for_region (cfun, CDI_POST_DOMINATORS, region); | |
1446 region.release (); | |
1447 | |
1448 for (i = 0; refs->iterate (i, &dr); i++) | |
1449 { | |
1450 tree ref = DR_REF (dr); | |
1451 | |
1452 dr->aux = XNEW (struct ifc_dr); | |
1453 DR_BASE_W_UNCONDITIONALLY (dr) = false; | |
1454 DR_RW_UNCONDITIONALLY (dr) = false; | |
1455 DR_W_UNCONDITIONALLY (dr) = false; | |
1456 IFC_DR (dr)->rw_predicate = boolean_false_node; | |
1457 IFC_DR (dr)->w_predicate = boolean_false_node; | |
1458 IFC_DR (dr)->base_w_predicate = boolean_false_node; | |
1459 if (gimple_uid (DR_STMT (dr)) == 0) | |
1460 gimple_set_uid (DR_STMT (dr), i + 1); | |
1461 | |
1462 /* If DR doesn't have innermost loop behavior or it's a compound | |
1463 memory reference, we synthesize its innermost loop behavior | |
1464 for hashing. */ | |
1465 if (TREE_CODE (ref) == COMPONENT_REF | |
1466 || TREE_CODE (ref) == IMAGPART_EXPR | |
1467 || TREE_CODE (ref) == REALPART_EXPR | |
1468 || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr) | |
1469 || DR_INIT (dr) || DR_STEP (dr))) | |
1470 { | |
1471 while (TREE_CODE (ref) == COMPONENT_REF | |
1472 || TREE_CODE (ref) == IMAGPART_EXPR | |
1473 || TREE_CODE (ref) == REALPART_EXPR) | |
1474 ref = TREE_OPERAND (ref, 0); | |
1475 | |
1476 memset (&DR_INNERMOST (dr), 0, sizeof (DR_INNERMOST (dr))); | |
1477 DR_BASE_ADDRESS (dr) = ref; | |
1478 } | |
1479 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1480 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1481 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1482 for (i = 0; i < loop->num_nodes; i++) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1483 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1484 basic_block bb = ifc_bbs[i]; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1485 gimple_stmt_iterator itr; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1486 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1487 /* Check the if-convertibility of statements in predicated BBs. */ |
111 | 1488 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1489 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1490 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1491 return false; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1492 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1493 |
111 | 1494 /* Checking PHIs needs to be done after stmts, as the fact whether there |
1495 are any masked loads or stores affects the tests. */ | |
1496 for (i = 0; i < loop->num_nodes; i++) | |
1497 { | |
1498 basic_block bb = ifc_bbs[i]; | |
1499 gphi_iterator itr; | |
1500 | |
1501 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr)) | |
1502 if (!if_convertible_phi_p (loop, bb, itr.phi ())) | |
1503 return false; | |
1504 } | |
1505 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1506 if (dump_file) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1507 fprintf (dump_file, "Applying if-conversion\n"); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1508 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1509 return true; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1510 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1511 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1512 /* 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
|
1513 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
|
1514 - 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
|
1515 - 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
|
1516 - 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
|
1517 - 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
|
1518 - 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
|
1519 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1520 static bool |
145 | 1521 if_convertible_loop_p (class loop *loop) |
0 | 1522 { |
1523 edge e; | |
1524 edge_iterator ei; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1525 bool res = false; |
111 | 1526 vec<data_reference_p> refs; |
0 | 1527 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1528 /* Handle only innermost loop. */ |
0 | 1529 if (!loop || loop->inner) |
1530 { | |
1531 if (dump_file && (dump_flags & TDF_DETAILS)) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1532 fprintf (dump_file, "not innermost loop\n"); |
0 | 1533 return false; |
1534 } | |
1535 | |
1536 /* If only one block, no need for if-conversion. */ | |
1537 if (loop->num_nodes <= 2) | |
1538 { | |
1539 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1540 fprintf (dump_file, "less than 2 basic blocks\n"); | |
1541 return false; | |
1542 } | |
1543 | |
1544 /* More than one loop exit is too much to handle. */ | |
1545 if (!single_exit (loop)) | |
1546 { | |
1547 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1548 fprintf (dump_file, "multiple exits\n"); | |
1549 return false; | |
1550 } | |
1551 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1552 /* If one of the loop header's edge is an exit edge then do not |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1553 apply if-conversion. */ |
0 | 1554 FOR_EACH_EDGE (e, ei, loop->header->succs) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1555 if (loop_exit_edge_p (loop, e)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1556 return false; |
0 | 1557 |
111 | 1558 refs.create (5); |
1559 res = if_convertible_loop_p_1 (loop, &refs); | |
1560 | |
1561 data_reference_p dr; | |
1562 unsigned int i; | |
1563 for (i = 0; refs.iterate (i, &dr); i++) | |
1564 free (dr->aux); | |
1565 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1566 free_data_refs (refs); |
111 | 1567 |
1568 delete innermost_DR_map; | |
1569 innermost_DR_map = NULL; | |
1570 | |
1571 delete baseref_DR_map; | |
1572 baseref_DR_map = NULL; | |
1573 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1574 return res; |
0 | 1575 } |
1576 | |
111 | 1577 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement |
1578 which is in predicated basic block. | |
1579 In fact, the following PHI pattern is searching: | |
1580 loop-header: | |
1581 reduc_1 = PHI <..., reduc_2> | |
1582 ... | |
1583 if (...) | |
1584 reduc_3 = ... | |
1585 reduc_2 = PHI <reduc_1, reduc_3> | |
1586 | |
1587 ARG_0 and ARG_1 are correspondent PHI arguments. | |
1588 REDUC, OP0 and OP1 contain reduction stmt and its operands. | |
1589 EXTENDED is true if PHI has > 2 arguments. */ | |
1590 | |
1591 static bool | |
1592 is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1, | |
1593 tree *op0, tree *op1, bool extended) | |
0 | 1594 { |
111 | 1595 tree lhs, r_op1, r_op2; |
1596 gimple *stmt; | |
1597 gimple *header_phi = NULL; | |
1598 enum tree_code reduction_op; | |
1599 basic_block bb = gimple_bb (phi); | |
145 | 1600 class loop *loop = bb->loop_father; |
111 | 1601 edge latch_e = loop_latch_edge (loop); |
1602 imm_use_iterator imm_iter; | |
1603 use_operand_p use_p; | |
1604 edge e; | |
1605 edge_iterator ei; | |
1606 bool result = false; | |
1607 if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME) | |
1608 return false; | |
1609 | |
1610 if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI) | |
0 | 1611 { |
111 | 1612 lhs = arg_1; |
1613 header_phi = SSA_NAME_DEF_STMT (arg_0); | |
1614 stmt = SSA_NAME_DEF_STMT (arg_1); | |
0 | 1615 } |
111 | 1616 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI) |
0 | 1617 { |
111 | 1618 lhs = arg_0; |
1619 header_phi = SSA_NAME_DEF_STMT (arg_1); | |
1620 stmt = SSA_NAME_DEF_STMT (arg_0); | |
0 | 1621 } |
1622 else | |
111 | 1623 return false; |
1624 if (gimple_bb (header_phi) != loop->header) | |
1625 return false; | |
1626 | |
1627 if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi)) | |
1628 return false; | |
1629 | |
1630 if (gimple_code (stmt) != GIMPLE_ASSIGN | |
1631 || gimple_has_volatile_ops (stmt)) | |
1632 return false; | |
1633 | |
1634 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt))) | |
1635 return false; | |
1636 | |
1637 if (!is_predicated (gimple_bb (stmt))) | |
1638 return false; | |
1639 | |
1640 /* Check that stmt-block is predecessor of phi-block. */ | |
1641 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs) | |
1642 if (e->dest == bb) | |
1643 { | |
1644 result = true; | |
1645 break; | |
1646 } | |
1647 if (!result) | |
1648 return false; | |
1649 | |
1650 if (!has_single_use (lhs)) | |
1651 return false; | |
1652 | |
1653 reduction_op = gimple_assign_rhs_code (stmt); | |
1654 if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR) | |
1655 return false; | |
1656 r_op1 = gimple_assign_rhs1 (stmt); | |
1657 r_op2 = gimple_assign_rhs2 (stmt); | |
1658 | |
1659 /* Make R_OP1 to hold reduction variable. */ | |
1660 if (r_op2 == PHI_RESULT (header_phi) | |
1661 && reduction_op == PLUS_EXPR) | |
1662 std::swap (r_op1, r_op2); | |
1663 else if (r_op1 != PHI_RESULT (header_phi)) | |
1664 return false; | |
1665 | |
1666 /* Check that R_OP1 is used in reduction stmt or in PHI only. */ | |
1667 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1) | |
1668 { | |
1669 gimple *use_stmt = USE_STMT (use_p); | |
1670 if (is_gimple_debug (use_stmt)) | |
1671 continue; | |
1672 if (use_stmt == stmt) | |
1673 continue; | |
1674 if (gimple_code (use_stmt) != GIMPLE_PHI) | |
1675 return false; | |
1676 } | |
1677 | |
1678 *op0 = r_op1; *op1 = r_op2; | |
1679 *reduc = stmt; | |
1680 return true; | |
1681 } | |
1682 | |
1683 /* Converts conditional scalar reduction into unconditional form, e.g. | |
1684 bb_4 | |
1685 if (_5 != 0) goto bb_5 else goto bb_6 | |
1686 end_bb_4 | |
1687 bb_5 | |
1688 res_6 = res_13 + 1; | |
1689 end_bb_5 | |
1690 bb_6 | |
1691 # res_2 = PHI <res_13(4), res_6(5)> | |
1692 end_bb_6 | |
1693 | |
1694 will be converted into sequence | |
1695 _ifc__1 = _5 != 0 ? 1 : 0; | |
1696 res_2 = res_13 + _ifc__1; | |
1697 Argument SWAP tells that arguments of conditional expression should be | |
1698 swapped. | |
1699 Returns rhs of resulting PHI assignment. */ | |
1700 | |
1701 static tree | |
1702 convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi, | |
1703 tree cond, tree op0, tree op1, bool swap) | |
1704 { | |
1705 gimple_stmt_iterator stmt_it; | |
1706 gimple *new_assign; | |
1707 tree rhs; | |
1708 tree rhs1 = gimple_assign_rhs1 (reduc); | |
1709 tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_"); | |
1710 tree c; | |
1711 tree zero = build_zero_cst (TREE_TYPE (rhs1)); | |
1712 | |
1713 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1714 { | |
1715 fprintf (dump_file, "Found cond scalar reduction.\n"); | |
1716 print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM); | |
1717 } | |
1718 | |
1719 /* Build cond expression using COND and constant operand | |
1720 of reduction rhs. */ | |
1721 c = fold_build_cond_expr (TREE_TYPE (rhs1), | |
1722 unshare_expr (cond), | |
1723 swap ? zero : op1, | |
1724 swap ? op1 : zero); | |
1725 | |
1726 /* Create assignment stmt and insert it at GSI. */ | |
1727 new_assign = gimple_build_assign (tmp, c); | |
1728 gsi_insert_before (gsi, new_assign, GSI_SAME_STMT); | |
1729 /* Build rhs for unconditional increment/decrement. */ | |
1730 rhs = fold_build2 (gimple_assign_rhs_code (reduc), | |
1731 TREE_TYPE (rhs1), op0, tmp); | |
1732 | |
1733 /* Delete original reduction stmt. */ | |
1734 stmt_it = gsi_for_stmt (reduc); | |
1735 gsi_remove (&stmt_it, true); | |
1736 release_defs (reduc); | |
1737 return rhs; | |
1738 } | |
1739 | |
1740 /* Produce condition for all occurrences of ARG in PHI node. */ | |
1741 | |
1742 static tree | |
1743 gen_phi_arg_condition (gphi *phi, vec<int> *occur, | |
1744 gimple_stmt_iterator *gsi) | |
1745 { | |
1746 int len; | |
1747 int i; | |
1748 tree cond = NULL_TREE; | |
1749 tree c; | |
1750 edge e; | |
1751 | |
1752 len = occur->length (); | |
1753 gcc_assert (len > 0); | |
1754 for (i = 0; i < len; i++) | |
1755 { | |
1756 e = gimple_phi_arg_edge (phi, (*occur)[i]); | |
1757 c = bb_predicate (e->src); | |
1758 if (is_true_predicate (c)) | |
1759 { | |
1760 cond = c; | |
1761 break; | |
1762 } | |
1763 c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c), | |
1764 is_gimple_condexpr, NULL_TREE, | |
1765 true, GSI_SAME_STMT); | |
1766 if (cond != NULL_TREE) | |
1767 { | |
1768 /* Must build OR expression. */ | |
1769 cond = fold_or_predicates (EXPR_LOCATION (c), c, cond); | |
1770 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), | |
1771 is_gimple_condexpr, NULL_TREE, | |
1772 true, GSI_SAME_STMT); | |
1773 } | |
1774 else | |
1775 cond = c; | |
1776 } | |
1777 gcc_assert (cond != NULL_TREE); | |
1778 return cond; | |
1779 } | |
1780 | |
1781 /* Local valueization callback that follows all-use SSA edges. */ | |
1782 | |
1783 static tree | |
1784 ifcvt_follow_ssa_use_edges (tree val) | |
1785 { | |
1786 return val; | |
0 | 1787 } |
1788 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1789 /* Replace a scalar PHI node with a COND_EXPR using COND as condition. |
111 | 1790 This routine can handle PHI nodes with more than two arguments. |
0 | 1791 |
1792 For example, | |
111 | 1793 S1: A = PHI <x1(1), x2(5)> |
0 | 1794 is converted into, |
1795 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
|
1796 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1797 The generated code is inserted at GSI that points to the top of |
111 | 1798 basic block's statement list. |
1799 If PHI node has more than two arguments a chain of conditional | |
1800 expression is produced. */ | |
1801 | |
0 | 1802 |
1803 static void | |
111 | 1804 predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) |
0 | 1805 { |
111 | 1806 gimple *new_stmt = NULL, *reduc; |
1807 tree rhs, res, arg0, arg1, op0, op1, scev; | |
1808 tree cond; | |
1809 unsigned int index0; | |
1810 unsigned int max, args_len; | |
1811 edge e; | |
0 | 1812 basic_block bb; |
111 | 1813 unsigned int i; |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1814 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1815 res = gimple_phi_result (phi); |
111 | 1816 if (virtual_operand_p (res)) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1817 return; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1818 |
111 | 1819 if ((rhs = degenerate_phi_result (phi)) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1820 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1821 res)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1822 && !chrec_contains_undetermined (scev) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1823 && scev != res |
111 | 1824 && (rhs = gimple_phi_arg_def (phi, 0)))) |
1825 { | |
1826 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1827 { | |
1828 fprintf (dump_file, "Degenerate phi!\n"); | |
1829 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); | |
1830 } | |
1831 new_stmt = gimple_build_assign (res, rhs); | |
1832 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); | |
1833 update_stmt (new_stmt); | |
1834 return; | |
1835 } | |
1836 | |
1837 bb = gimple_bb (phi); | |
1838 if (EDGE_COUNT (bb->preds) == 2) | |
0 | 1839 { |
111 | 1840 /* Predicate ordinary PHI node with 2 arguments. */ |
1841 edge first_edge, second_edge; | |
1842 basic_block true_bb; | |
1843 first_edge = EDGE_PRED (bb, 0); | |
1844 second_edge = EDGE_PRED (bb, 1); | |
1845 cond = bb_predicate (first_edge->src); | |
1846 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) | |
1847 std::swap (first_edge, second_edge); | |
1848 if (EDGE_COUNT (first_edge->src->succs) > 1) | |
1849 { | |
1850 cond = bb_predicate (second_edge->src); | |
1851 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) | |
1852 cond = TREE_OPERAND (cond, 0); | |
1853 else | |
1854 first_edge = second_edge; | |
1855 } | |
1856 else | |
1857 cond = bb_predicate (first_edge->src); | |
1858 /* Gimplify the condition to a valid cond-expr conditonal operand. */ | |
1859 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), | |
1860 is_gimple_condexpr, NULL_TREE, | |
1861 true, GSI_SAME_STMT); | |
1862 true_bb = first_edge->src; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1863 if (EDGE_PRED (bb, 1)->src == true_bb) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1864 { |
111 | 1865 arg0 = gimple_phi_arg_def (phi, 1); |
1866 arg1 = gimple_phi_arg_def (phi, 0); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1867 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1868 else |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1869 { |
111 | 1870 arg0 = gimple_phi_arg_def (phi, 0); |
1871 arg1 = gimple_phi_arg_def (phi, 1); | |
1872 } | |
1873 if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1, | |
1874 &op0, &op1, false)) | |
1875 /* Convert reduction stmt into vectorizable form. */ | |
1876 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1, | |
1877 true_bb != gimple_bb (reduc)); | |
1878 else | |
1879 /* Build new RHS using selected condition and arguments. */ | |
1880 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond), | |
1881 arg0, arg1); | |
1882 new_stmt = gimple_build_assign (res, rhs); | |
1883 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); | |
1884 gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt); | |
1885 if (fold_stmt (&new_gsi, ifcvt_follow_ssa_use_edges)) | |
1886 { | |
1887 new_stmt = gsi_stmt (new_gsi); | |
1888 update_stmt (new_stmt); | |
1889 } | |
1890 | |
1891 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1892 { | |
1893 fprintf (dump_file, "new phi replacement stmt\n"); | |
1894 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); | |
1895 } | |
1896 return; | |
1897 } | |
1898 | |
1899 /* Create hashmap for PHI node which contain vector of argument indexes | |
1900 having the same value. */ | |
1901 bool swap = false; | |
1902 hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map; | |
1903 unsigned int num_args = gimple_phi_num_args (phi); | |
1904 int max_ind = -1; | |
1905 /* Vector of different PHI argument values. */ | |
1906 auto_vec<tree> args (num_args); | |
1907 | |
1908 /* Compute phi_arg_map. */ | |
1909 for (i = 0; i < num_args; i++) | |
1910 { | |
1911 tree arg; | |
1912 | |
1913 arg = gimple_phi_arg_def (phi, i); | |
1914 if (!phi_arg_map.get (arg)) | |
1915 args.quick_push (arg); | |
1916 phi_arg_map.get_or_insert (arg).safe_push (i); | |
1917 } | |
1918 | |
1919 /* Determine element with max number of occurrences. */ | |
1920 max_ind = -1; | |
1921 max = 1; | |
1922 args_len = args.length (); | |
1923 for (i = 0; i < args_len; i++) | |
1924 { | |
1925 unsigned int len; | |
1926 if ((len = phi_arg_map.get (args[i])->length ()) > max) | |
1927 { | |
1928 max_ind = (int) i; | |
1929 max = len; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1930 } |
0 | 1931 } |
1932 | |
111 | 1933 /* Put element with max number of occurences to the end of ARGS. */ |
1934 if (max_ind != -1 && max_ind +1 != (int) args_len) | |
1935 std::swap (args[args_len - 1], args[max_ind]); | |
1936 | |
1937 /* Handle one special case when number of arguments with different values | |
1938 is equal 2 and one argument has the only occurrence. Such PHI can be | |
1939 handled as if would have only 2 arguments. */ | |
1940 if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1) | |
1941 { | |
1942 vec<int> *indexes; | |
1943 indexes = phi_arg_map.get (args[0]); | |
1944 index0 = (*indexes)[0]; | |
1945 arg0 = args[0]; | |
1946 arg1 = args[1]; | |
1947 e = gimple_phi_arg_edge (phi, index0); | |
1948 cond = bb_predicate (e->src); | |
1949 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) | |
1950 { | |
1951 swap = true; | |
1952 cond = TREE_OPERAND (cond, 0); | |
1953 } | |
1954 /* Gimplify the condition to a valid cond-expr conditonal operand. */ | |
1955 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), | |
1956 is_gimple_condexpr, NULL_TREE, | |
1957 true, GSI_SAME_STMT); | |
1958 if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1, | |
1959 &op0, &op1, true))) | |
1960 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond), | |
1961 swap? arg1 : arg0, | |
1962 swap? arg0 : arg1); | |
1963 else | |
1964 /* Convert reduction stmt into vectorizable form. */ | |
1965 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1, | |
1966 swap); | |
1967 new_stmt = gimple_build_assign (res, rhs); | |
1968 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); | |
1969 update_stmt (new_stmt); | |
1970 } | |
1971 else | |
1972 { | |
1973 /* Common case. */ | |
1974 vec<int> *indexes; | |
1975 tree type = TREE_TYPE (gimple_phi_result (phi)); | |
1976 tree lhs; | |
1977 arg1 = args[1]; | |
1978 for (i = 0; i < args_len; i++) | |
1979 { | |
1980 arg0 = args[i]; | |
1981 indexes = phi_arg_map.get (args[i]); | |
1982 if (i != args_len - 1) | |
1983 lhs = make_temp_ssa_name (type, NULL, "_ifc_"); | |
1984 else | |
1985 lhs = res; | |
1986 cond = gen_phi_arg_condition (phi, indexes, gsi); | |
1987 rhs = fold_build_cond_expr (type, unshare_expr (cond), | |
1988 arg0, arg1); | |
1989 new_stmt = gimple_build_assign (lhs, rhs); | |
1990 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); | |
1991 update_stmt (new_stmt); | |
1992 arg1 = lhs; | |
1993 } | |
1994 } | |
0 | 1995 |
1996 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1997 { | |
111 | 1998 fprintf (dump_file, "new extended phi replacement stmt\n"); |
0 | 1999 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); |
2000 } | |
2001 } | |
2002 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2003 /* Replaces in LOOP all the scalar phi nodes other than those in the |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2004 LOOP->header block with conditional modify expressions. */ |
0 | 2005 |
2006 static void | |
145 | 2007 predicate_all_scalar_phis (class loop *loop) |
0 | 2008 { |
2009 basic_block bb; | |
2010 unsigned int orig_loop_num_nodes = loop->num_nodes; | |
2011 unsigned int i; | |
2012 | |
2013 for (i = 1; i < orig_loop_num_nodes; i++) | |
2014 { | |
111 | 2015 gphi *phi; |
2016 gimple_stmt_iterator gsi; | |
2017 gphi_iterator phi_gsi; | |
0 | 2018 bb = ifc_bbs[i]; |
2019 | |
2020 if (bb == loop->header) | |
2021 continue; | |
2022 | |
2023 phi_gsi = gsi_start_phis (bb); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2024 if (gsi_end_p (phi_gsi)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2025 continue; |
0 | 2026 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2027 gsi = gsi_after_labels (bb); |
0 | 2028 while (!gsi_end_p (phi_gsi)) |
2029 { | |
111 | 2030 phi = phi_gsi.phi (); |
2031 if (virtual_operand_p (gimple_phi_result (phi))) | |
2032 gsi_next (&phi_gsi); | |
2033 else | |
2034 { | |
2035 predicate_scalar_phi (phi, &gsi); | |
2036 remove_phi_node (&phi_gsi, false); | |
2037 } | |
0 | 2038 } |
2039 } | |
2040 } | |
2041 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2042 /* Insert in each basic block of LOOP the statements produced by the |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2043 gimplification of the predicates. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2044 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2045 static void |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2046 insert_gimplified_predicates (loop_p loop) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2047 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2048 unsigned int i; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2049 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2050 for (i = 0; i < loop->num_nodes; i++) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2051 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2052 basic_block bb = ifc_bbs[i]; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2053 gimple_seq stmts; |
111 | 2054 if (!is_predicated (bb)) |
2055 gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2056 if (!is_predicated (bb)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2057 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2058 /* Do not insert statements for a basic block that is not |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2059 predicated. Also make sure that the predicate of the |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2060 basic block is set to true. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2061 reset_bb_predicate (bb); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2062 continue; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2063 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2064 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2065 stmts = bb_predicate_gimplified_stmts (bb); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2066 if (stmts) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2067 { |
131 | 2068 if (need_to_predicate) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2069 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2070 /* Insert the predicate of the BB just after the label, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2071 as the if-conversion of memory writes will use this |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2072 predicate. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2073 gimple_stmt_iterator gsi = gsi_after_labels (bb); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2074 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2075 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2076 else |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2077 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2078 /* Insert the predicate of the BB at the end of the BB |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2079 as this would reduce the register pressure: the only |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2080 use of this predicate will be in successor BBs. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2081 gimple_stmt_iterator gsi = gsi_last_bb (bb); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2082 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2083 if (gsi_end_p (gsi) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2084 || stmt_ends_bb_p (gsi_stmt (gsi))) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2085 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2086 else |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2087 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2088 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2089 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2090 /* Once the sequence is code generated, set it to NULL. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2091 set_bb_predicate_gimplified_stmts (bb, NULL); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2092 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2093 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2094 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2095 |
131 | 2096 /* Helper function for predicate_statements. Returns index of existent |
111 | 2097 mask if it was created for given SIZE and -1 otherwise. */ |
2098 | |
2099 static int | |
2100 mask_exists (int size, vec<int> vec) | |
2101 { | |
2102 unsigned int ix; | |
2103 int v; | |
2104 FOR_EACH_VEC_ELT (vec, ix, v) | |
2105 if (v == size) | |
2106 return (int) ix; | |
2107 return -1; | |
2108 } | |
2109 | |
131 | 2110 /* Helper function for predicate_statements. STMT is a memory read or |
2111 write and it needs to be predicated by MASK. Return a statement | |
2112 that does so. */ | |
2113 | |
2114 static gimple * | |
2115 predicate_load_or_store (gimple_stmt_iterator *gsi, gassign *stmt, tree mask) | |
2116 { | |
2117 gcall *new_stmt; | |
2118 | |
2119 tree lhs = gimple_assign_lhs (stmt); | |
2120 tree rhs = gimple_assign_rhs1 (stmt); | |
2121 tree ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs; | |
2122 mark_addressable (ref); | |
2123 tree addr = force_gimple_operand_gsi (gsi, build_fold_addr_expr (ref), | |
2124 true, NULL_TREE, true, GSI_SAME_STMT); | |
2125 tree ptr = build_int_cst (reference_alias_ptr_type (ref), | |
2126 get_object_alignment (ref)); | |
2127 /* Copy points-to info if possible. */ | |
2128 if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr)) | |
2129 copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr), | |
2130 ref); | |
2131 if (TREE_CODE (lhs) == SSA_NAME) | |
2132 { | |
2133 new_stmt | |
2134 = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr, | |
2135 ptr, mask); | |
2136 gimple_call_set_lhs (new_stmt, lhs); | |
2137 gimple_set_vuse (new_stmt, gimple_vuse (stmt)); | |
2138 } | |
2139 else | |
2140 { | |
2141 new_stmt | |
2142 = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr, | |
2143 mask, rhs); | |
145 | 2144 gimple_move_vops (new_stmt, stmt); |
131 | 2145 } |
2146 gimple_call_set_nothrow (new_stmt, true); | |
2147 return new_stmt; | |
2148 } | |
2149 | |
2150 /* STMT uses OP_LHS. Check whether it is equivalent to: | |
2151 | |
2152 ... = OP_MASK ? OP_LHS : X; | |
2153 | |
2154 Return X if so, otherwise return null. OP_MASK is an SSA_NAME that is | |
2155 known to have value OP_COND. */ | |
2156 | |
2157 static tree | |
2158 check_redundant_cond_expr (gimple *stmt, tree op_mask, tree op_cond, | |
2159 tree op_lhs) | |
2160 { | |
2161 gassign *assign = dyn_cast <gassign *> (stmt); | |
2162 if (!assign || gimple_assign_rhs_code (assign) != COND_EXPR) | |
2163 return NULL_TREE; | |
2164 | |
2165 tree use_cond = gimple_assign_rhs1 (assign); | |
2166 tree if_true = gimple_assign_rhs2 (assign); | |
2167 tree if_false = gimple_assign_rhs3 (assign); | |
2168 | |
2169 if ((use_cond == op_mask || operand_equal_p (use_cond, op_cond, 0)) | |
2170 && if_true == op_lhs) | |
2171 return if_false; | |
2172 | |
2173 if (inverse_conditions_p (use_cond, op_cond) && if_false == op_lhs) | |
2174 return if_true; | |
2175 | |
2176 return NULL_TREE; | |
2177 } | |
2178 | |
2179 /* Return true if VALUE is available for use at STMT. SSA_NAMES is | |
2180 the set of SSA names defined earlier in STMT's block. */ | |
2181 | |
2182 static bool | |
2183 value_available_p (gimple *stmt, hash_set<tree_ssa_name_hash> *ssa_names, | |
2184 tree value) | |
2185 { | |
2186 if (is_gimple_min_invariant (value)) | |
2187 return true; | |
2188 | |
2189 if (TREE_CODE (value) == SSA_NAME) | |
2190 { | |
2191 if (SSA_NAME_IS_DEFAULT_DEF (value)) | |
2192 return true; | |
2193 | |
2194 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value)); | |
2195 basic_block use_bb = gimple_bb (stmt); | |
2196 return (def_bb == use_bb | |
2197 ? ssa_names->contains (value) | |
2198 : dominated_by_p (CDI_DOMINATORS, use_bb, def_bb)); | |
2199 } | |
2200 | |
2201 return false; | |
2202 } | |
2203 | |
2204 /* Helper function for predicate_statements. STMT is a potentially-trapping | |
2205 arithmetic operation that needs to be predicated by MASK, an SSA_NAME that | |
2206 has value COND. Return a statement that does so. SSA_NAMES is the set of | |
2207 SSA names defined earlier in STMT's block. */ | |
2208 | |
2209 static gimple * | |
2210 predicate_rhs_code (gassign *stmt, tree mask, tree cond, | |
2211 hash_set<tree_ssa_name_hash> *ssa_names) | |
2212 { | |
2213 tree lhs = gimple_assign_lhs (stmt); | |
2214 tree_code code = gimple_assign_rhs_code (stmt); | |
2215 unsigned int nops = gimple_num_ops (stmt); | |
2216 internal_fn cond_fn = get_conditional_internal_fn (code); | |
2217 | |
2218 /* Construct the arguments to the conditional internal function. */ | |
2219 auto_vec<tree, 8> args; | |
2220 args.safe_grow (nops + 1); | |
2221 args[0] = mask; | |
2222 for (unsigned int i = 1; i < nops; ++i) | |
2223 args[i] = gimple_op (stmt, i); | |
2224 args[nops] = NULL_TREE; | |
2225 | |
2226 /* Look for uses of the result to see whether they are COND_EXPRs that can | |
2227 be folded into the conditional call. */ | |
2228 imm_use_iterator imm_iter; | |
2229 gimple *use_stmt; | |
2230 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs) | |
2231 { | |
2232 tree new_else = check_redundant_cond_expr (use_stmt, mask, cond, lhs); | |
2233 if (new_else && value_available_p (stmt, ssa_names, new_else)) | |
2234 { | |
2235 if (!args[nops]) | |
2236 args[nops] = new_else; | |
2237 if (operand_equal_p (new_else, args[nops], 0)) | |
2238 { | |
2239 /* We have: | |
2240 | |
2241 LHS = IFN_COND (MASK, ..., ELSE); | |
2242 X = MASK ? LHS : ELSE; | |
2243 | |
2244 which makes X equivalent to LHS. */ | |
2245 tree use_lhs = gimple_assign_lhs (use_stmt); | |
2246 redundant_ssa_names.safe_push (std::make_pair (use_lhs, lhs)); | |
2247 } | |
2248 } | |
2249 } | |
2250 if (!args[nops]) | |
2251 args[nops] = targetm.preferred_else_value (cond_fn, TREE_TYPE (lhs), | |
2252 nops - 1, &args[1]); | |
2253 | |
2254 /* Create and insert the call. */ | |
2255 gcall *new_stmt = gimple_build_call_internal_vec (cond_fn, args); | |
2256 gimple_call_set_lhs (new_stmt, lhs); | |
2257 gimple_call_set_nothrow (new_stmt, true); | |
2258 | |
2259 return new_stmt; | |
2260 } | |
2261 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2262 /* Predicate each write to memory in LOOP. |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2263 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2264 This function transforms control flow constructs containing memory |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2265 writes of the form: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2266 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2267 | for (i = 0; i < N; i++) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2268 | if (cond) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2269 | A[i] = expr; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2270 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2271 into the following form that does not contain control flow: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2272 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2273 | for (i = 0; i < N; i++) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2274 | A[i] = cond ? expr : A[i]; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2275 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2276 The original CFG looks like this: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2277 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2278 | bb_0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2279 | i = 0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2280 | end_bb_0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2281 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2282 | bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2283 | if (i < N) goto bb_5 else goto bb_2 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2284 | end_bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2285 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2286 | bb_2 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2287 | cond = some_computation; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2288 | if (cond) goto bb_3 else goto bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2289 | end_bb_2 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2290 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2291 | bb_3 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2292 | A[i] = expr; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2293 | goto bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2294 | end_bb_3 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2295 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2296 | bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2297 | goto bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2298 | end_bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2299 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2300 insert_gimplified_predicates inserts the computation of the COND |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2301 expression at the beginning of the destination basic block: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2302 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2303 | bb_0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2304 | i = 0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2305 | end_bb_0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2306 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2307 | bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2308 | if (i < N) goto bb_5 else goto bb_2 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2309 | end_bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2310 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2311 | bb_2 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2312 | cond = some_computation; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2313 | if (cond) goto bb_3 else goto bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2314 | end_bb_2 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2315 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2316 | bb_3 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2317 | cond = some_computation; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2318 | A[i] = expr; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2319 | goto bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2320 | end_bb_3 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2321 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2322 | bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2323 | goto bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2324 | end_bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2325 |
131 | 2326 predicate_statements is then predicating the memory write as follows: |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2327 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2328 | bb_0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2329 | i = 0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2330 | end_bb_0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2331 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2332 | bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2333 | if (i < N) goto bb_5 else goto bb_2 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2334 | end_bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2335 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2336 | bb_2 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2337 | if (cond) goto bb_3 else goto bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2338 | end_bb_2 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2339 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2340 | bb_3 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2341 | cond = some_computation; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2342 | A[i] = cond ? expr : A[i]; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2343 | goto bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2344 | end_bb_3 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2345 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2346 | bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2347 | goto bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2348 | end_bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2349 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2350 and finally combine_blocks removes the basic block boundaries making |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2351 the loop vectorizable: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2352 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2353 | bb_0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2354 | i = 0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2355 | if (i < N) goto bb_5 else goto bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2356 | end_bb_0 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2357 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2358 | bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2359 | cond = some_computation; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2360 | A[i] = cond ? expr : A[i]; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2361 | if (i < N) goto bb_5 else goto bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2362 | end_bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2363 | |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2364 | bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2365 | goto bb_1 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2366 | end_bb_4 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2367 */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2368 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2369 static void |
131 | 2370 predicate_statements (loop_p loop) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2371 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2372 unsigned int i, orig_loop_num_nodes = loop->num_nodes; |
111 | 2373 auto_vec<int, 1> vect_sizes; |
2374 auto_vec<tree, 1> vect_masks; | |
131 | 2375 hash_set<tree_ssa_name_hash> ssa_names; |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2376 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2377 for (i = 1; i < orig_loop_num_nodes; i++) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2378 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2379 gimple_stmt_iterator gsi; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2380 basic_block bb = ifc_bbs[i]; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2381 tree cond = bb_predicate (bb); |
111 | 2382 bool swap; |
2383 int index; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2384 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2385 if (is_true_predicate (cond)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2386 continue; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2387 |
111 | 2388 swap = false; |
2389 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) | |
2390 { | |
2391 swap = true; | |
2392 cond = TREE_OPERAND (cond, 0); | |
2393 } | |
2394 | |
2395 vect_sizes.truncate (0); | |
2396 vect_masks.truncate (0); | |
2397 | |
2398 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) | |
2399 { | |
131 | 2400 gassign *stmt = dyn_cast <gassign *> (gsi_stmt (gsi)); |
2401 if (!stmt) | |
111 | 2402 ; |
2403 else if (is_false_predicate (cond) | |
2404 && gimple_vdef (stmt)) | |
2405 { | |
2406 unlink_stmt_vdef (stmt); | |
2407 gsi_remove (&gsi, true); | |
2408 release_defs (stmt); | |
2409 continue; | |
2410 } | |
2411 else if (gimple_plf (stmt, GF_PLF_2)) | |
2412 { | |
2413 tree lhs = gimple_assign_lhs (stmt); | |
131 | 2414 tree mask; |
2415 gimple *new_stmt; | |
111 | 2416 gimple_seq stmts = NULL; |
131 | 2417 machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); |
2418 /* We checked before setting GF_PLF_2 that an equivalent | |
2419 integer mode exists. */ | |
2420 int bitsize = GET_MODE_BITSIZE (mode).to_constant (); | |
111 | 2421 if (!vect_sizes.is_empty () |
2422 && (index = mask_exists (bitsize, vect_sizes)) != -1) | |
2423 /* Use created mask. */ | |
2424 mask = vect_masks[index]; | |
2425 else | |
2426 { | |
2427 if (COMPARISON_CLASS_P (cond)) | |
2428 mask = gimple_build (&stmts, TREE_CODE (cond), | |
2429 boolean_type_node, | |
2430 TREE_OPERAND (cond, 0), | |
2431 TREE_OPERAND (cond, 1)); | |
2432 else | |
131 | 2433 mask = cond; |
111 | 2434 |
2435 if (swap) | |
2436 { | |
2437 tree true_val | |
2438 = constant_boolean_node (true, TREE_TYPE (mask)); | |
2439 mask = gimple_build (&stmts, BIT_XOR_EXPR, | |
2440 TREE_TYPE (mask), mask, true_val); | |
2441 } | |
2442 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); | |
2443 | |
2444 /* Save mask and its size for further use. */ | |
2445 vect_sizes.safe_push (bitsize); | |
2446 vect_masks.safe_push (mask); | |
2447 } | |
131 | 2448 if (gimple_assign_single_p (stmt)) |
2449 new_stmt = predicate_load_or_store (&gsi, stmt, mask); | |
111 | 2450 else |
131 | 2451 new_stmt = predicate_rhs_code (stmt, mask, cond, &ssa_names); |
111 | 2452 |
2453 gsi_replace (&gsi, new_stmt, true); | |
2454 } | |
2455 else if (gimple_vdef (stmt)) | |
2456 { | |
2457 tree lhs = gimple_assign_lhs (stmt); | |
2458 tree rhs = gimple_assign_rhs1 (stmt); | |
2459 tree type = TREE_TYPE (lhs); | |
2460 | |
2461 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi); | |
2462 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi); | |
2463 if (swap) | |
2464 std::swap (lhs, rhs); | |
2465 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond), | |
2466 is_gimple_condexpr, NULL_TREE, | |
2467 true, GSI_SAME_STMT); | |
2468 rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs); | |
2469 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi)); | |
2470 update_stmt (stmt); | |
2471 } | |
131 | 2472 tree lhs = gimple_get_lhs (gsi_stmt (gsi)); |
2473 if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
2474 ssa_names.add (lhs); | |
111 | 2475 gsi_next (&gsi); |
2476 } | |
131 | 2477 ssa_names.empty (); |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2478 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2479 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2480 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2481 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2482 other than the exit and latch of the LOOP. Also resets the |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2483 GIMPLE_DEBUG information. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2484 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2485 static void |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2486 remove_conditions_and_labels (loop_p loop) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2487 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2488 gimple_stmt_iterator gsi; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2489 unsigned int i; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2490 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2491 for (i = 0; i < loop->num_nodes; i++) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2492 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2493 basic_block bb = ifc_bbs[i]; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2494 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2495 if (bb_with_exit_edge_p (loop, bb) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2496 || bb == loop->latch) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2497 continue; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2498 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2499 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2500 switch (gimple_code (gsi_stmt (gsi))) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2501 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2502 case GIMPLE_COND: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2503 case GIMPLE_LABEL: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2504 gsi_remove (&gsi, true); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2505 break; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2506 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2507 case GIMPLE_DEBUG: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2508 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2509 if (gimple_debug_bind_p (gsi_stmt (gsi))) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2510 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2511 gimple_debug_bind_reset_value (gsi_stmt (gsi)); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2512 update_stmt (gsi_stmt (gsi)); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2513 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2514 gsi_next (&gsi); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2515 break; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2516 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2517 default: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2518 gsi_next (&gsi); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2519 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2520 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2521 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2522 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2523 /* 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
|
2524 blocks. Replace PHI nodes with conditional modify expressions. */ |
0 | 2525 |
2526 static void | |
145 | 2527 combine_blocks (class loop *loop) |
0 | 2528 { |
2529 basic_block bb, exit_bb, merge_target_bb; | |
2530 unsigned int orig_loop_num_nodes = loop->num_nodes; | |
2531 unsigned int i; | |
2532 edge e; | |
2533 edge_iterator ei; | |
2534 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2535 remove_conditions_and_labels (loop); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2536 insert_gimplified_predicates (loop); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2537 predicate_all_scalar_phis (loop); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2538 |
131 | 2539 if (need_to_predicate) |
2540 predicate_statements (loop); | |
0 | 2541 |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2542 /* 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
|
2543 except for those from the exit block. */ |
0 | 2544 exit_bb = NULL; |
111 | 2545 bool *predicated = XNEWVEC (bool, orig_loop_num_nodes); |
0 | 2546 for (i = 0; i < orig_loop_num_nodes; i++) |
2547 { | |
2548 bb = ifc_bbs[i]; | |
111 | 2549 predicated[i] = !is_true_predicate (bb_predicate (bb)); |
2550 free_bb_predicate (bb); | |
0 | 2551 if (bb_with_exit_edge_p (loop, bb)) |
2552 { | |
111 | 2553 gcc_assert (exit_bb == NULL); |
0 | 2554 exit_bb = bb; |
2555 } | |
2556 } | |
2557 gcc_assert (exit_bb != loop->latch); | |
2558 | |
2559 for (i = 1; i < orig_loop_num_nodes; i++) | |
2560 { | |
2561 bb = ifc_bbs[i]; | |
2562 | |
2563 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) | |
2564 { | |
2565 if (e->src == exit_bb) | |
2566 ei_next (&ei); | |
2567 else | |
2568 remove_edge (e); | |
2569 } | |
2570 } | |
2571 | |
2572 if (exit_bb != NULL) | |
2573 { | |
2574 if (exit_bb != loop->header) | |
2575 { | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2576 /* Connect this node to loop header. */ |
111 | 2577 make_single_succ_edge (loop->header, exit_bb, EDGE_FALLTHRU); |
0 | 2578 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); |
2579 } | |
2580 | |
2581 /* Redirect non-exit edges to loop->latch. */ | |
2582 FOR_EACH_EDGE (e, ei, exit_bb->succs) | |
2583 { | |
2584 if (!loop_exit_edge_p (loop, e)) | |
2585 redirect_edge_and_branch (e, loop->latch); | |
2586 } | |
2587 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); | |
2588 } | |
2589 else | |
2590 { | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2591 /* If the loop does not have an exit, reconnect header and latch. */ |
0 | 2592 make_edge (loop->header, loop->latch, EDGE_FALLTHRU); |
2593 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); | |
2594 } | |
2595 | |
2596 merge_target_bb = loop->header; | |
111 | 2597 |
2598 /* Get at the virtual def valid for uses starting at the first block | |
2599 we merge into the header. Without a virtual PHI the loop has the | |
2600 same virtual use on all stmts. */ | |
2601 gphi *vphi = get_virtual_phi (loop->header); | |
2602 tree last_vdef = NULL_TREE; | |
2603 if (vphi) | |
2604 { | |
2605 last_vdef = gimple_phi_result (vphi); | |
2606 for (gimple_stmt_iterator gsi = gsi_start_bb (loop->header); | |
2607 ! gsi_end_p (gsi); gsi_next (&gsi)) | |
2608 if (gimple_vdef (gsi_stmt (gsi))) | |
2609 last_vdef = gimple_vdef (gsi_stmt (gsi)); | |
2610 } | |
0 | 2611 for (i = 1; i < orig_loop_num_nodes; i++) |
2612 { | |
2613 gimple_stmt_iterator gsi; | |
2614 gimple_stmt_iterator last; | |
2615 | |
2616 bb = ifc_bbs[i]; | |
2617 | |
2618 if (bb == exit_bb || bb == loop->latch) | |
2619 continue; | |
2620 | |
111 | 2621 /* We release virtual PHIs late because we have to propagate them |
2622 out using the current VUSE. The def might be the one used | |
2623 after the loop. */ | |
2624 vphi = get_virtual_phi (bb); | |
2625 if (vphi) | |
2626 { | |
145 | 2627 /* When there's just loads inside the loop a stray virtual |
2628 PHI merging the uses can appear, update last_vdef from | |
2629 it. */ | |
2630 if (!last_vdef) | |
2631 last_vdef = gimple_phi_arg_def (vphi, 0); | |
111 | 2632 imm_use_iterator iter; |
2633 use_operand_p use_p; | |
2634 gimple *use_stmt; | |
2635 FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi)) | |
2636 { | |
2637 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) | |
2638 SET_USE (use_p, last_vdef); | |
2639 } | |
145 | 2640 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi))) |
2641 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1; | |
111 | 2642 gsi = gsi_for_stmt (vphi); |
2643 remove_phi_node (&gsi, true); | |
2644 } | |
2645 | |
2646 /* Make stmts member of loop->header and clear range info from all stmts | |
2647 in BB which is now no longer executed conditional on a predicate we | |
2648 could have derived it from. */ | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2649 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
111 | 2650 { |
2651 gimple *stmt = gsi_stmt (gsi); | |
2652 gimple_set_bb (stmt, merge_target_bb); | |
2653 /* Update virtual operands. */ | |
2654 if (last_vdef) | |
2655 { | |
2656 use_operand_p use_p = ssa_vuse_operand (stmt); | |
2657 if (use_p | |
2658 && USE_FROM_PTR (use_p) != last_vdef) | |
2659 SET_USE (use_p, last_vdef); | |
2660 if (gimple_vdef (stmt)) | |
2661 last_vdef = gimple_vdef (stmt); | |
2662 } | |
145 | 2663 else |
2664 /* If this is the first load we arrive at update last_vdef | |
2665 so we handle stray PHIs correctly. */ | |
2666 last_vdef = gimple_vuse (stmt); | |
111 | 2667 if (predicated[i]) |
2668 { | |
2669 ssa_op_iter i; | |
2670 tree op; | |
2671 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF) | |
2672 reset_flow_sensitive_info (op); | |
2673 } | |
2674 } | |
0 | 2675 |
2676 /* Update stmt list. */ | |
2677 last = gsi_last_bb (merge_target_bb); | |
111 | 2678 gsi_insert_seq_after_without_update (&last, bb_seq (bb), GSI_NEW_STMT); |
0 | 2679 set_bb_seq (bb, NULL); |
2680 | |
2681 delete_basic_block (bb); | |
2682 } | |
2683 | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2684 /* 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
|
2685 This reduces the number of basic blocks to two, to please the |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2686 vectorizer that handles only loops with two nodes. */ |
0 | 2687 if (exit_bb |
111 | 2688 && exit_bb != loop->header) |
2689 { | |
2690 /* We release virtual PHIs late because we have to propagate them | |
2691 out using the current VUSE. The def might be the one used | |
2692 after the loop. */ | |
2693 vphi = get_virtual_phi (exit_bb); | |
2694 if (vphi) | |
2695 { | |
2696 imm_use_iterator iter; | |
2697 use_operand_p use_p; | |
2698 gimple *use_stmt; | |
2699 FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi)) | |
2700 { | |
2701 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) | |
2702 SET_USE (use_p, last_vdef); | |
2703 } | |
145 | 2704 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi))) |
2705 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1; | |
111 | 2706 gimple_stmt_iterator gsi = gsi_for_stmt (vphi); |
2707 remove_phi_node (&gsi, true); | |
2708 } | |
2709 | |
2710 if (can_merge_blocks_p (loop->header, exit_bb)) | |
2711 merge_blocks (loop->header, exit_bb); | |
2712 } | |
2713 | |
2714 free (ifc_bbs); | |
2715 ifc_bbs = NULL; | |
2716 free (predicated); | |
2717 } | |
2718 | |
2719 /* Version LOOP before if-converting it; the original loop | |
2720 will be if-converted, the new copy of the loop will not, | |
2721 and the LOOP_VECTORIZED internal call will be guarding which | |
2722 loop to execute. The vectorizer pass will fold this | |
2723 internal call into either true or false. | |
2724 | |
2725 Note that this function intentionally invalidates profile. Both edges | |
2726 out of LOOP_VECTORIZED must have 100% probability so the profile remains | |
2727 consistent after the condition is folded in the vectorizer. */ | |
2728 | |
145 | 2729 static class loop * |
2730 version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds) | |
111 | 2731 { |
2732 basic_block cond_bb; | |
2733 tree cond = make_ssa_name (boolean_type_node); | |
145 | 2734 class loop *new_loop; |
111 | 2735 gimple *g; |
2736 gimple_stmt_iterator gsi; | |
2737 unsigned int save_length; | |
2738 | |
2739 g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2, | |
2740 build_int_cst (integer_type_node, loop->num), | |
2741 integer_zero_node); | |
2742 gimple_call_set_lhs (g, cond); | |
2743 | |
2744 /* Save BB->aux around loop_version as that uses the same field. */ | |
2745 save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes; | |
2746 void **saved_preds = XALLOCAVEC (void *, save_length); | |
2747 for (unsigned i = 0; i < save_length; i++) | |
2748 saved_preds[i] = ifc_bbs[i]->aux; | |
2749 | |
2750 initialize_original_copy_tables (); | |
2751 /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED | |
2752 is re-merged in the vectorizer. */ | |
2753 new_loop = loop_version (loop, cond, &cond_bb, | |
2754 profile_probability::always (), | |
2755 profile_probability::always (), | |
2756 profile_probability::always (), | |
2757 profile_probability::always (), true); | |
2758 free_original_copy_tables (); | |
2759 | |
2760 for (unsigned i = 0; i < save_length; i++) | |
2761 ifc_bbs[i]->aux = saved_preds[i]; | |
2762 | |
2763 if (new_loop == NULL) | |
2764 return NULL; | |
2765 | |
2766 new_loop->dont_vectorize = true; | |
2767 new_loop->force_vectorize = false; | |
2768 gsi = gsi_last_bb (cond_bb); | |
2769 gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num)); | |
145 | 2770 if (preds) |
2771 preds->safe_push (g); | |
111 | 2772 gsi_insert_before (&gsi, g, GSI_SAME_STMT); |
2773 update_ssa (TODO_update_ssa); | |
2774 return new_loop; | |
2775 } | |
2776 | |
2777 /* Return true when LOOP satisfies the follow conditions that will | |
2778 allow it to be recognized by the vectorizer for outer-loop | |
2779 vectorization: | |
2780 - The loop is not the root node of the loop tree. | |
2781 - The loop has exactly one inner loop. | |
2782 - The loop has a single exit. | |
2783 - The loop header has a single successor, which is the inner | |
2784 loop header. | |
2785 - Each of the inner and outer loop latches have a single | |
2786 predecessor. | |
2787 - The loop exit block has a single predecessor, which is the | |
2788 inner loop's exit block. */ | |
2789 | |
2790 static bool | |
145 | 2791 versionable_outer_loop_p (class loop *loop) |
111 | 2792 { |
2793 if (!loop_outer (loop) | |
2794 || loop->dont_vectorize | |
2795 || !loop->inner | |
2796 || loop->inner->next | |
2797 || !single_exit (loop) | |
2798 || !single_succ_p (loop->header) | |
2799 || single_succ (loop->header) != loop->inner->header | |
2800 || !single_pred_p (loop->latch) | |
2801 || !single_pred_p (loop->inner->latch)) | |
2802 return false; | |
2803 | |
2804 basic_block outer_exit = single_pred (loop->latch); | |
2805 basic_block inner_exit = single_pred (loop->inner->latch); | |
2806 | |
2807 if (!single_pred_p (outer_exit) || single_pred (outer_exit) != inner_exit) | |
2808 return false; | |
2809 | |
2810 if (dump_file) | |
2811 fprintf (dump_file, "Found vectorizable outer loop for versioning\n"); | |
2812 | |
2813 return true; | |
2814 } | |
2815 | |
2816 /* Performs splitting of critical edges. Skip splitting and return false | |
2817 if LOOP will not be converted because: | |
2818 | |
2819 - LOOP is not well formed. | |
2820 - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments. | |
2821 | |
2822 Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */ | |
2823 | |
2824 static bool | |
145 | 2825 ifcvt_split_critical_edges (class loop *loop, bool aggressive_if_conv) |
111 | 2826 { |
2827 basic_block *body; | |
2828 basic_block bb; | |
2829 unsigned int num = loop->num_nodes; | |
2830 unsigned int i; | |
2831 gimple *stmt; | |
2832 edge e; | |
2833 edge_iterator ei; | |
2834 auto_vec<edge> critical_edges; | |
2835 | |
2836 /* Loop is not well formed. */ | |
2837 if (num <= 2 || loop->inner || !single_exit (loop)) | |
2838 return false; | |
2839 | |
2840 body = get_loop_body (loop); | |
2841 for (i = 0; i < num; i++) | |
2842 { | |
2843 bb = body[i]; | |
2844 if (!aggressive_if_conv | |
2845 && phi_nodes (bb) | |
2846 && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM) | |
2847 { | |
2848 if (dump_file && (dump_flags & TDF_DETAILS)) | |
2849 fprintf (dump_file, | |
2850 "BB %d has complicated PHI with more than %u args.\n", | |
2851 bb->index, MAX_PHI_ARG_NUM); | |
2852 | |
2853 free (body); | |
2854 return false; | |
2855 } | |
2856 if (bb == loop->latch || bb_with_exit_edge_p (loop, bb)) | |
2857 continue; | |
2858 | |
2859 stmt = last_stmt (bb); | |
2860 /* Skip basic blocks not ending with conditional branch. */ | |
2861 if (!stmt || gimple_code (stmt) != GIMPLE_COND) | |
2862 continue; | |
2863 | |
2864 FOR_EACH_EDGE (e, ei, bb->succs) | |
2865 if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop) | |
2866 critical_edges.safe_push (e); | |
2867 } | |
2868 free (body); | |
2869 | |
2870 while (critical_edges.length () > 0) | |
2871 { | |
2872 e = critical_edges.pop (); | |
2873 /* Don't split if bb can be predicated along non-critical edge. */ | |
2874 if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest)) | |
2875 split_edge (e); | |
2876 } | |
2877 | |
2878 return true; | |
2879 } | |
2880 | |
2881 /* Delete redundant statements produced by predication which prevents | |
2882 loop vectorization. */ | |
2883 | |
2884 static void | |
145 | 2885 ifcvt_local_dce (class loop *loop) |
111 | 2886 { |
2887 gimple *stmt; | |
2888 gimple *stmt1; | |
2889 gimple *phi; | |
2890 gimple_stmt_iterator gsi; | |
2891 auto_vec<gimple *> worklist; | |
2892 enum gimple_code code; | |
2893 use_operand_p use_p; | |
2894 imm_use_iterator imm_iter; | |
131 | 2895 std::pair <tree, tree> *name_pair; |
2896 unsigned int i; | |
2897 | |
2898 FOR_EACH_VEC_ELT (redundant_ssa_names, i, name_pair) | |
2899 replace_uses_by (name_pair->first, name_pair->second); | |
2900 redundant_ssa_names.release (); | |
111 | 2901 |
145 | 2902 /* The loop has a single BB only. */ |
2903 basic_block bb = loop->header; | |
2904 tree latch_vdef = NULL_TREE; | |
2905 | |
111 | 2906 worklist.create (64); |
2907 /* Consider all phi as live statements. */ | |
2908 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
2909 { | |
2910 phi = gsi_stmt (gsi); | |
2911 gimple_set_plf (phi, GF_PLF_2, true); | |
2912 worklist.safe_push (phi); | |
145 | 2913 if (virtual_operand_p (gimple_phi_result (phi))) |
2914 latch_vdef = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); | |
111 | 2915 } |
2916 /* Consider load/store statements, CALL and COND as live. */ | |
2917 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
2918 { | |
2919 stmt = gsi_stmt (gsi); | |
2920 if (gimple_store_p (stmt) | |
2921 || gimple_assign_load_p (stmt) | |
2922 || is_gimple_debug (stmt)) | |
2923 { | |
2924 gimple_set_plf (stmt, GF_PLF_2, true); | |
2925 worklist.safe_push (stmt); | |
2926 continue; | |
2927 } | |
2928 code = gimple_code (stmt); | |
2929 if (code == GIMPLE_COND || code == GIMPLE_CALL) | |
2930 { | |
2931 gimple_set_plf (stmt, GF_PLF_2, true); | |
2932 worklist.safe_push (stmt); | |
2933 continue; | |
2934 } | |
2935 gimple_set_plf (stmt, GF_PLF_2, false); | |
2936 | |
2937 if (code == GIMPLE_ASSIGN) | |
2938 { | |
2939 tree lhs = gimple_assign_lhs (stmt); | |
2940 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs) | |
2941 { | |
2942 stmt1 = USE_STMT (use_p); | |
2943 if (gimple_bb (stmt1) != bb) | |
2944 { | |
2945 gimple_set_plf (stmt, GF_PLF_2, true); | |
2946 worklist.safe_push (stmt); | |
2947 break; | |
2948 } | |
2949 } | |
2950 } | |
2951 } | |
2952 /* Propagate liveness through arguments of live stmt. */ | |
2953 while (worklist.length () > 0) | |
2954 { | |
2955 ssa_op_iter iter; | |
2956 use_operand_p use_p; | |
2957 tree use; | |
2958 | |
2959 stmt = worklist.pop (); | |
2960 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) | |
2961 { | |
2962 use = USE_FROM_PTR (use_p); | |
2963 if (TREE_CODE (use) != SSA_NAME) | |
2964 continue; | |
2965 stmt1 = SSA_NAME_DEF_STMT (use); | |
2966 if (gimple_bb (stmt1) != bb | |
2967 || gimple_plf (stmt1, GF_PLF_2)) | |
2968 continue; | |
2969 gimple_set_plf (stmt1, GF_PLF_2, true); | |
2970 worklist.safe_push (stmt1); | |
2971 } | |
2972 } | |
2973 /* Delete dead statements. */ | |
2974 gsi = gsi_start_bb (bb); | |
2975 while (!gsi_end_p (gsi)) | |
2976 { | |
2977 stmt = gsi_stmt (gsi); | |
145 | 2978 if (gimple_store_p (stmt)) |
2979 { | |
2980 tree lhs = gimple_get_lhs (stmt); | |
2981 ao_ref write; | |
2982 ao_ref_init (&write, lhs); | |
2983 | |
2984 if (dse_classify_store (&write, stmt, false, NULL, NULL, latch_vdef) | |
2985 == DSE_STORE_DEAD) | |
2986 delete_dead_or_redundant_assignment (&gsi, "dead"); | |
2987 else | |
2988 gsi_next (&gsi); | |
2989 continue; | |
2990 } | |
2991 | |
111 | 2992 if (gimple_plf (stmt, GF_PLF_2)) |
2993 { | |
2994 gsi_next (&gsi); | |
2995 continue; | |
2996 } | |
2997 if (dump_file && (dump_flags & TDF_DETAILS)) | |
2998 { | |
2999 fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index); | |
3000 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
3001 } | |
3002 gsi_remove (&gsi, true); | |
3003 release_defs (stmt); | |
3004 } | |
0 | 3005 } |
3006 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3007 /* If-convert LOOP when it is legal. For the moment this pass has no |
111 | 3008 profitability analysis. Returns non-zero todo flags when something |
3009 changed. */ | |
3010 | |
3011 unsigned int | |
145 | 3012 tree_if_conversion (class loop *loop, vec<gimple *> *preds) |
0 | 3013 { |
111 | 3014 unsigned int todo = 0; |
3015 bool aggressive_if_conv; | |
145 | 3016 class loop *rloop; |
3017 bitmap exit_bbs; | |
111 | 3018 |
3019 again: | |
3020 rloop = NULL; | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3021 ifc_bbs = NULL; |
131 | 3022 need_to_predicate = false; |
111 | 3023 any_complicated_phi = false; |
3024 | |
3025 /* Apply more aggressive if-conversion when loop or its outer loop were | |
3026 marked with simd pragma. When that's the case, we try to if-convert | |
3027 loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */ | |
3028 aggressive_if_conv = loop->force_vectorize; | |
3029 if (!aggressive_if_conv) | |
3030 { | |
145 | 3031 class loop *outer_loop = loop_outer (loop); |
111 | 3032 if (outer_loop && outer_loop->force_vectorize) |
3033 aggressive_if_conv = true; | |
3034 } | |
3035 | |
3036 if (!ifcvt_split_critical_edges (loop, aggressive_if_conv)) | |
3037 goto cleanup; | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3038 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3039 if (!if_convertible_loop_p (loop) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3040 || !dbg_cnt (if_conversion_tree)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3041 goto cleanup; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3042 |
131 | 3043 if ((need_to_predicate || any_complicated_phi) |
111 | 3044 && ((!flag_tree_loop_vectorize && !loop->force_vectorize) |
3045 || loop->dont_vectorize)) | |
3046 goto cleanup; | |
3047 | |
3048 /* Since we have no cost model, always version loops unless the user | |
3049 specified -ftree-loop-if-convert or unless versioning is required. | |
3050 Either version this loop, or if the pattern is right for outer-loop | |
3051 vectorization, version the outer loop. In the latter case we will | |
3052 still if-convert the original inner loop. */ | |
131 | 3053 if (need_to_predicate |
111 | 3054 || any_complicated_phi |
3055 || flag_tree_loop_if_convert != 1) | |
3056 { | |
145 | 3057 class loop *vloop |
111 | 3058 = (versionable_outer_loop_p (loop_outer (loop)) |
3059 ? loop_outer (loop) : loop); | |
145 | 3060 class loop *nloop = version_loop_for_if_conversion (vloop, preds); |
111 | 3061 if (nloop == NULL) |
3062 goto cleanup; | |
3063 if (vloop != loop) | |
3064 { | |
3065 /* If versionable_outer_loop_p decided to version the | |
3066 outer loop, version also the inner loop of the non-vectorized | |
3067 loop copy. So we transform: | |
3068 loop1 | |
3069 loop2 | |
3070 into: | |
3071 if (LOOP_VECTORIZED (1, 3)) | |
3072 { | |
3073 loop1 | |
3074 loop2 | |
3075 } | |
3076 else | |
3077 loop3 (copy of loop1) | |
3078 if (LOOP_VECTORIZED (4, 5)) | |
3079 loop4 (copy of loop2) | |
3080 else | |
3081 loop5 (copy of loop4) */ | |
3082 gcc_assert (nloop->inner && nloop->inner->next == NULL); | |
3083 rloop = nloop->inner; | |
3084 } | |
3085 } | |
3086 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3087 /* Now all statements are if-convertible. Combine all the basic |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3088 blocks into one huge basic block doing the if-conversion |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3089 on-the-fly. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3090 combine_blocks (loop); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3091 |
145 | 3092 /* Perform local CSE, this esp. helps the vectorizer analysis if loads |
3093 and stores are involved. CSE only the loop body, not the entry | |
3094 PHIs, those are to be kept in sync with the non-if-converted copy. | |
3095 ??? We'll still keep dead stores though. */ | |
3096 exit_bbs = BITMAP_ALLOC (NULL); | |
3097 bitmap_set_bit (exit_bbs, single_exit (loop)->dest->index); | |
3098 bitmap_set_bit (exit_bbs, loop->latch->index); | |
3099 todo |= do_rpo_vn (cfun, loop_preheader_edge (loop), exit_bbs); | |
3100 | |
111 | 3101 /* Delete dead predicate computations. */ |
145 | 3102 ifcvt_local_dce (loop); |
3103 BITMAP_FREE (exit_bbs); | |
111 | 3104 |
3105 todo |= TODO_cleanup_cfg; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3106 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3107 cleanup: |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3108 if (ifc_bbs) |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3109 { |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3110 unsigned int i; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3111 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3112 for (i = 0; i < loop->num_nodes; i++) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3113 free_bb_predicate (ifc_bbs[i]); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3114 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3115 free (ifc_bbs); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3116 ifc_bbs = NULL; |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3117 } |
111 | 3118 if (rloop != NULL) |
3119 { | |
3120 loop = rloop; | |
3121 goto again; | |
3122 } | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3123 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
3124 return todo; |
0 | 3125 } |
3126 | |
111 | 3127 /* Tree if-conversion pass management. */ |
3128 | |
3129 namespace { | |
3130 | |
3131 const pass_data pass_data_if_conversion = | |
0 | 3132 { |
111 | 3133 GIMPLE_PASS, /* type */ |
3134 "ifcvt", /* name */ | |
3135 OPTGROUP_NONE, /* optinfo_flags */ | |
3136 TV_TREE_LOOP_IFCVT, /* tv_id */ | |
3137 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
3138 0, /* properties_provided */ | |
3139 0, /* properties_destroyed */ | |
3140 0, /* todo_flags_start */ | |
3141 0, /* todo_flags_finish */ | |
3142 }; | |
3143 | |
3144 class pass_if_conversion : public gimple_opt_pass | |
3145 { | |
3146 public: | |
3147 pass_if_conversion (gcc::context *ctxt) | |
3148 : gimple_opt_pass (pass_data_if_conversion, ctxt) | |
3149 {} | |
3150 | |
3151 /* opt_pass methods: */ | |
3152 virtual bool gate (function *); | |
3153 virtual unsigned int execute (function *); | |
3154 | |
3155 }; // class pass_if_conversion | |
3156 | |
3157 bool | |
3158 pass_if_conversion::gate (function *fun) | |
0 | 3159 { |
111 | 3160 return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops) |
3161 && flag_tree_loop_if_convert != 0) | |
3162 || flag_tree_loop_if_convert == 1); | |
3163 } | |
3164 | |
3165 unsigned int | |
3166 pass_if_conversion::execute (function *fun) | |
3167 { | |
145 | 3168 class loop *loop; |
111 | 3169 unsigned todo = 0; |
3170 | |
3171 if (number_of_loops (fun) <= 1) | |
3172 return 0; | |
3173 | |
145 | 3174 auto_vec<gimple *> preds; |
111 | 3175 FOR_EACH_LOOP (loop, 0) |
3176 if (flag_tree_loop_if_convert == 1 | |
3177 || ((flag_tree_loop_vectorize || loop->force_vectorize) | |
3178 && !loop->dont_vectorize)) | |
145 | 3179 todo |= tree_if_conversion (loop, &preds); |
111 | 3180 |
131 | 3181 if (todo) |
3182 { | |
3183 free_numbers_of_iterations_estimates (fun); | |
3184 scev_reset (); | |
3185 } | |
3186 | |
111 | 3187 if (flag_checking) |
3188 { | |
3189 basic_block bb; | |
3190 FOR_EACH_BB_FN (bb, fun) | |
3191 gcc_assert (!bb->aux); | |
3192 } | |
3193 | |
145 | 3194 /* Perform IL update now, it might elide some loops. */ |
3195 if (todo & TODO_cleanup_cfg) | |
3196 { | |
3197 cleanup_tree_cfg (); | |
3198 if (need_ssa_update_p (fun)) | |
3199 todo |= TODO_update_ssa; | |
3200 } | |
3201 if (todo & TODO_update_ssa_any) | |
3202 update_ssa (todo & TODO_update_ssa_any); | |
3203 | |
3204 /* If if-conversion elided the loop fall back to the original one. */ | |
3205 for (unsigned i = 0; i < preds.length (); ++i) | |
3206 { | |
3207 gimple *g = preds[i]; | |
3208 if (!gimple_bb (g)) | |
3209 continue; | |
3210 unsigned ifcvt_loop = tree_to_uhwi (gimple_call_arg (g, 0)); | |
3211 if (!get_loop (fun, ifcvt_loop)) | |
3212 { | |
3213 if (dump_file) | |
3214 fprintf (dump_file, "If-converted loop vanished\n"); | |
3215 fold_loop_internal_call (g, boolean_false_node); | |
3216 } | |
3217 } | |
3218 | |
3219 return 0; | |
111 | 3220 } |
3221 | |
3222 } // anon namespace | |
3223 | |
3224 gimple_opt_pass * | |
3225 make_pass_if_conversion (gcc::context *ctxt) | |
3226 { | |
3227 return new pass_if_conversion (ctxt); | |
3228 } |