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