|
111
|
1 /* Loop splitting.
|
|
145
|
2 Copyright (C) 2015-2020 Free Software Foundation, Inc.
|
|
111
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify it
|
|
|
7 under the terms of the GNU General Public License as published by the
|
|
|
8 Free Software Foundation; either version 3, or (at your option) any
|
|
|
9 later version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful, but WITHOUT
|
|
|
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 #include "config.h"
|
|
|
21 #include "system.h"
|
|
|
22 #include "coretypes.h"
|
|
|
23 #include "backend.h"
|
|
|
24 #include "tree.h"
|
|
|
25 #include "gimple.h"
|
|
|
26 #include "tree-pass.h"
|
|
|
27 #include "ssa.h"
|
|
|
28 #include "fold-const.h"
|
|
|
29 #include "tree-cfg.h"
|
|
|
30 #include "tree-ssa.h"
|
|
|
31 #include "tree-ssa-loop-niter.h"
|
|
|
32 #include "tree-ssa-loop.h"
|
|
|
33 #include "tree-ssa-loop-manip.h"
|
|
|
34 #include "tree-into-ssa.h"
|
|
145
|
35 #include "tree-inline.h"
|
|
|
36 #include "tree-cfgcleanup.h"
|
|
111
|
37 #include "cfgloop.h"
|
|
|
38 #include "tree-scalar-evolution.h"
|
|
|
39 #include "gimple-iterator.h"
|
|
|
40 #include "gimple-pretty-print.h"
|
|
|
41 #include "cfghooks.h"
|
|
|
42 #include "gimple-fold.h"
|
|
|
43 #include "gimplify-me.h"
|
|
|
44
|
|
145
|
45 /* This file implements two kinds of loop splitting.
|
|
|
46
|
|
|
47 One transformation of loops like:
|
|
111
|
48
|
|
|
49 for (i = 0; i < 100; i++)
|
|
|
50 {
|
|
|
51 if (i < 50)
|
|
|
52 A;
|
|
|
53 else
|
|
|
54 B;
|
|
|
55 }
|
|
|
56
|
|
|
57 into:
|
|
|
58
|
|
|
59 for (i = 0; i < 50; i++)
|
|
|
60 {
|
|
|
61 A;
|
|
|
62 }
|
|
|
63 for (; i < 100; i++)
|
|
|
64 {
|
|
|
65 B;
|
|
|
66 }
|
|
|
67
|
|
|
68 */
|
|
|
69
|
|
|
70 /* Return true when BB inside LOOP is a potential iteration space
|
|
|
71 split point, i.e. ends with a condition like "IV < comp", which
|
|
|
72 is true on one side of the iteration space and false on the other,
|
|
|
73 and the split point can be computed. If so, also return the border
|
|
|
74 point in *BORDER and the comparison induction variable in IV. */
|
|
|
75
|
|
|
76 static tree
|
|
145
|
77 split_at_bb_p (class loop *loop, basic_block bb, tree *border, affine_iv *iv)
|
|
111
|
78 {
|
|
|
79 gimple *last;
|
|
|
80 gcond *stmt;
|
|
|
81 affine_iv iv2;
|
|
|
82
|
|
|
83 /* BB must end in a simple conditional jump. */
|
|
|
84 last = last_stmt (bb);
|
|
|
85 if (!last || gimple_code (last) != GIMPLE_COND)
|
|
|
86 return NULL_TREE;
|
|
|
87 stmt = as_a <gcond *> (last);
|
|
|
88
|
|
|
89 enum tree_code code = gimple_cond_code (stmt);
|
|
|
90
|
|
|
91 /* Only handle relational comparisons, for equality and non-equality
|
|
|
92 we'd have to split the loop into two loops and a middle statement. */
|
|
|
93 switch (code)
|
|
|
94 {
|
|
|
95 case LT_EXPR:
|
|
|
96 case LE_EXPR:
|
|
|
97 case GT_EXPR:
|
|
|
98 case GE_EXPR:
|
|
|
99 break;
|
|
|
100 default:
|
|
|
101 return NULL_TREE;
|
|
|
102 }
|
|
|
103
|
|
|
104 if (loop_exits_from_bb_p (loop, bb))
|
|
|
105 return NULL_TREE;
|
|
|
106
|
|
|
107 tree op0 = gimple_cond_lhs (stmt);
|
|
|
108 tree op1 = gimple_cond_rhs (stmt);
|
|
145
|
109 class loop *useloop = loop_containing_stmt (stmt);
|
|
111
|
110
|
|
|
111 if (!simple_iv (loop, useloop, op0, iv, false))
|
|
|
112 return NULL_TREE;
|
|
|
113 if (!simple_iv (loop, useloop, op1, &iv2, false))
|
|
|
114 return NULL_TREE;
|
|
|
115
|
|
|
116 /* Make it so that the first argument of the condition is
|
|
|
117 the looping one. */
|
|
|
118 if (!integer_zerop (iv2.step))
|
|
|
119 {
|
|
|
120 std::swap (op0, op1);
|
|
|
121 std::swap (*iv, iv2);
|
|
|
122 code = swap_tree_comparison (code);
|
|
|
123 gimple_cond_set_condition (stmt, code, op0, op1);
|
|
|
124 update_stmt (stmt);
|
|
|
125 }
|
|
|
126 else if (integer_zerop (iv->step))
|
|
|
127 return NULL_TREE;
|
|
|
128 if (!integer_zerop (iv2.step))
|
|
|
129 return NULL_TREE;
|
|
|
130 if (!iv->no_overflow)
|
|
|
131 return NULL_TREE;
|
|
|
132
|
|
|
133 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
134 {
|
|
|
135 fprintf (dump_file, "Found potential split point: ");
|
|
|
136 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
|
137 fprintf (dump_file, " { ");
|
|
|
138 print_generic_expr (dump_file, iv->base, TDF_SLIM);
|
|
|
139 fprintf (dump_file, " + I*");
|
|
|
140 print_generic_expr (dump_file, iv->step, TDF_SLIM);
|
|
|
141 fprintf (dump_file, " } %s ", get_tree_code_name (code));
|
|
|
142 print_generic_expr (dump_file, iv2.base, TDF_SLIM);
|
|
|
143 fprintf (dump_file, "\n");
|
|
|
144 }
|
|
|
145
|
|
|
146 *border = iv2.base;
|
|
|
147 return op0;
|
|
|
148 }
|
|
|
149
|
|
|
150 /* Given a GUARD conditional stmt inside LOOP, which we want to make always
|
|
|
151 true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL
|
|
|
152 (a post-increment IV) and NEWBOUND (the comparator) adjust the loop
|
|
|
153 exit test statement to loop back only if the GUARD statement will
|
|
|
154 also be true/false in the next iteration. */
|
|
|
155
|
|
|
156 static void
|
|
145
|
157 patch_loop_exit (class loop *loop, gcond *guard, tree nextval, tree newbound,
|
|
111
|
158 bool initial_true)
|
|
|
159 {
|
|
|
160 edge exit = single_exit (loop);
|
|
|
161 gcond *stmt = as_a <gcond *> (last_stmt (exit->src));
|
|
|
162 gimple_cond_set_condition (stmt, gimple_cond_code (guard),
|
|
|
163 nextval, newbound);
|
|
|
164 update_stmt (stmt);
|
|
|
165
|
|
|
166 edge stay = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
|
|
|
167
|
|
|
168 exit->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
|
|
|
169 stay->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
|
|
|
170
|
|
|
171 if (initial_true)
|
|
|
172 {
|
|
|
173 exit->flags |= EDGE_FALSE_VALUE;
|
|
|
174 stay->flags |= EDGE_TRUE_VALUE;
|
|
|
175 }
|
|
|
176 else
|
|
|
177 {
|
|
|
178 exit->flags |= EDGE_TRUE_VALUE;
|
|
|
179 stay->flags |= EDGE_FALSE_VALUE;
|
|
|
180 }
|
|
|
181 }
|
|
|
182
|
|
|
183 /* Give an induction variable GUARD_IV, and its affine descriptor IV,
|
|
|
184 find the loop phi node in LOOP defining it directly, or create
|
|
|
185 such phi node. Return that phi node. */
|
|
|
186
|
|
|
187 static gphi *
|
|
145
|
188 find_or_create_guard_phi (class loop *loop, tree guard_iv, affine_iv * /*iv*/)
|
|
111
|
189 {
|
|
|
190 gimple *def = SSA_NAME_DEF_STMT (guard_iv);
|
|
|
191 gphi *phi;
|
|
|
192 if ((phi = dyn_cast <gphi *> (def))
|
|
|
193 && gimple_bb (phi) == loop->header)
|
|
|
194 return phi;
|
|
|
195
|
|
|
196 /* XXX Create the PHI instead. */
|
|
|
197 return NULL;
|
|
|
198 }
|
|
|
199
|
|
|
200 /* Returns true if the exit values of all loop phi nodes can be
|
|
|
201 determined easily (i.e. that connect_loop_phis can determine them). */
|
|
|
202
|
|
|
203 static bool
|
|
145
|
204 easy_exit_values (class loop *loop)
|
|
111
|
205 {
|
|
|
206 edge exit = single_exit (loop);
|
|
|
207 edge latch = loop_latch_edge (loop);
|
|
|
208 gphi_iterator psi;
|
|
|
209
|
|
|
210 /* Currently we regard the exit values as easy if they are the same
|
|
|
211 as the value over the backedge. Which is the case if the definition
|
|
|
212 of the backedge value dominates the exit edge. */
|
|
|
213 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
|
|
|
214 {
|
|
|
215 gphi *phi = psi.phi ();
|
|
|
216 tree next = PHI_ARG_DEF_FROM_EDGE (phi, latch);
|
|
|
217 basic_block bb;
|
|
|
218 if (TREE_CODE (next) == SSA_NAME
|
|
|
219 && (bb = gimple_bb (SSA_NAME_DEF_STMT (next)))
|
|
|
220 && !dominated_by_p (CDI_DOMINATORS, exit->src, bb))
|
|
|
221 return false;
|
|
|
222 }
|
|
|
223
|
|
|
224 return true;
|
|
|
225 }
|
|
|
226
|
|
|
227 /* This function updates the SSA form after connect_loops made a new
|
|
|
228 edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate
|
|
|
229 conditional). I.e. the second loop can now be entered either
|
|
|
230 via the original entry or via NEW_E, so the entry values of LOOP2
|
|
|
231 phi nodes are either the original ones or those at the exit
|
|
|
232 of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting
|
|
|
233 this. The loops need to fulfill easy_exit_values(). */
|
|
|
234
|
|
|
235 static void
|
|
145
|
236 connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e)
|
|
111
|
237 {
|
|
|
238 basic_block rest = loop_preheader_edge (loop2)->src;
|
|
|
239 gcc_assert (new_e->dest == rest);
|
|
|
240 edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e);
|
|
|
241
|
|
|
242 edge firste = loop_preheader_edge (loop1);
|
|
|
243 edge seconde = loop_preheader_edge (loop2);
|
|
|
244 edge firstn = loop_latch_edge (loop1);
|
|
|
245 gphi_iterator psi_first, psi_second;
|
|
|
246 for (psi_first = gsi_start_phis (loop1->header),
|
|
|
247 psi_second = gsi_start_phis (loop2->header);
|
|
|
248 !gsi_end_p (psi_first);
|
|
|
249 gsi_next (&psi_first), gsi_next (&psi_second))
|
|
|
250 {
|
|
|
251 tree init, next, new_init;
|
|
|
252 use_operand_p op;
|
|
|
253 gphi *phi_first = psi_first.phi ();
|
|
|
254 gphi *phi_second = psi_second.phi ();
|
|
|
255
|
|
|
256 init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste);
|
|
|
257 next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn);
|
|
|
258 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde);
|
|
|
259 gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
|
|
|
260
|
|
|
261 /* Prefer using original variable as a base for the new ssa name.
|
|
|
262 This is necessary for virtual ops, and useful in order to avoid
|
|
|
263 losing debug info for real ops. */
|
|
|
264 if (TREE_CODE (next) == SSA_NAME
|
|
|
265 && useless_type_conversion_p (TREE_TYPE (next),
|
|
|
266 TREE_TYPE (init)))
|
|
|
267 new_init = copy_ssa_name (next);
|
|
|
268 else if (TREE_CODE (init) == SSA_NAME
|
|
|
269 && useless_type_conversion_p (TREE_TYPE (init),
|
|
|
270 TREE_TYPE (next)))
|
|
|
271 new_init = copy_ssa_name (init);
|
|
|
272 else if (useless_type_conversion_p (TREE_TYPE (next),
|
|
|
273 TREE_TYPE (init)))
|
|
|
274 new_init = make_temp_ssa_name (TREE_TYPE (next), NULL,
|
|
|
275 "unrinittmp");
|
|
|
276 else
|
|
|
277 new_init = make_temp_ssa_name (TREE_TYPE (init), NULL,
|
|
|
278 "unrinittmp");
|
|
|
279
|
|
|
280 gphi * newphi = create_phi_node (new_init, rest);
|
|
|
281 add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION);
|
|
|
282 add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION);
|
|
|
283 SET_USE (op, new_init);
|
|
|
284 }
|
|
|
285 }
|
|
|
286
|
|
|
287 /* The two loops LOOP1 and LOOP2 were just created by loop versioning,
|
|
|
288 they are still equivalent and placed in two arms of a diamond, like so:
|
|
|
289
|
|
|
290 .------if (cond)------.
|
|
|
291 v v
|
|
|
292 pre1 pre2
|
|
|
293 | |
|
|
|
294 .--->h1 h2<----.
|
|
|
295 | | | |
|
|
|
296 | ex1---. .---ex2 |
|
|
|
297 | / | | \ |
|
|
|
298 '---l1 X | l2---'
|
|
|
299 | |
|
|
|
300 | |
|
|
|
301 '--->join<---'
|
|
|
302
|
|
|
303 This function transforms the program such that LOOP1 is conditionally
|
|
|
304 falling through to LOOP2, or skipping it. This is done by splitting
|
|
|
305 the ex1->join edge at X in the diagram above, and inserting a condition
|
|
|
306 whose one arm goes to pre2, resulting in this situation:
|
|
|
307
|
|
|
308 .------if (cond)------.
|
|
|
309 v v
|
|
|
310 pre1 .---------->pre2
|
|
|
311 | | |
|
|
|
312 .--->h1 | h2<----.
|
|
|
313 | | | | |
|
|
|
314 | ex1---. | .---ex2 |
|
|
|
315 | / v | | \ |
|
|
|
316 '---l1 skip---' | l2---'
|
|
|
317 | |
|
|
|
318 | |
|
|
|
319 '--->join<---'
|
|
|
320
|
|
|
321
|
|
|
322 The condition used is the exit condition of LOOP1, which effectively means
|
|
|
323 that when the first loop exits (for whatever reason) but the real original
|
|
|
324 exit expression is still false the second loop will be entered.
|
|
|
325 The function returns the new edge cond->pre2.
|
|
|
326
|
|
|
327 This doesn't update the SSA form, see connect_loop_phis for that. */
|
|
|
328
|
|
|
329 static edge
|
|
145
|
330 connect_loops (class loop *loop1, class loop *loop2)
|
|
111
|
331 {
|
|
|
332 edge exit = single_exit (loop1);
|
|
|
333 basic_block skip_bb = split_edge (exit);
|
|
|
334 gcond *skip_stmt;
|
|
|
335 gimple_stmt_iterator gsi;
|
|
|
336 edge new_e, skip_e;
|
|
|
337
|
|
|
338 gimple *stmt = last_stmt (exit->src);
|
|
|
339 skip_stmt = gimple_build_cond (gimple_cond_code (stmt),
|
|
|
340 gimple_cond_lhs (stmt),
|
|
|
341 gimple_cond_rhs (stmt),
|
|
|
342 NULL_TREE, NULL_TREE);
|
|
|
343 gsi = gsi_last_bb (skip_bb);
|
|
|
344 gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT);
|
|
|
345
|
|
|
346 skip_e = EDGE_SUCC (skip_bb, 0);
|
|
|
347 skip_e->flags &= ~EDGE_FALLTHRU;
|
|
|
348 new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0);
|
|
|
349 if (exit->flags & EDGE_TRUE_VALUE)
|
|
|
350 {
|
|
|
351 skip_e->flags |= EDGE_TRUE_VALUE;
|
|
|
352 new_e->flags |= EDGE_FALSE_VALUE;
|
|
|
353 }
|
|
|
354 else
|
|
|
355 {
|
|
|
356 skip_e->flags |= EDGE_FALSE_VALUE;
|
|
|
357 new_e->flags |= EDGE_TRUE_VALUE;
|
|
|
358 }
|
|
|
359
|
|
|
360 new_e->probability = profile_probability::likely ();
|
|
|
361 skip_e->probability = new_e->probability.invert ();
|
|
|
362
|
|
|
363 return new_e;
|
|
|
364 }
|
|
|
365
|
|
|
366 /* This returns the new bound for iterations given the original iteration
|
|
|
367 space in NITER, an arbitrary new bound BORDER, assumed to be some
|
|
|
368 comparison value with a different IV, the initial value GUARD_INIT of
|
|
|
369 that other IV, and the comparison code GUARD_CODE that compares
|
|
|
370 that other IV with BORDER. We return an SSA name, and place any
|
|
|
371 necessary statements for that computation into *STMTS.
|
|
|
372
|
|
|
373 For example for such a loop:
|
|
|
374
|
|
|
375 for (i = beg, j = guard_init; i < end; i++, j++)
|
|
|
376 if (j < border) // this is supposed to be true/false
|
|
|
377 ...
|
|
|
378
|
|
|
379 we want to return a new bound (on j) that makes the loop iterate
|
|
|
380 as long as the condition j < border stays true. We also don't want
|
|
|
381 to iterate more often than the original loop, so we have to introduce
|
|
|
382 some cut-off as well (via min/max), effectively resulting in:
|
|
|
383
|
|
|
384 newend = min (end+guard_init-beg, border)
|
|
|
385 for (i = beg; j = guard_init; j < newend; i++, j++)
|
|
|
386 if (j < c)
|
|
|
387 ...
|
|
|
388
|
|
|
389 Depending on the direction of the IVs and if the exit tests
|
|
|
390 are strict or non-strict we need to use MIN or MAX,
|
|
|
391 and add or subtract 1. This routine computes newend above. */
|
|
|
392
|
|
|
393 static tree
|
|
145
|
394 compute_new_first_bound (gimple_seq *stmts, class tree_niter_desc *niter,
|
|
111
|
395 tree border,
|
|
|
396 enum tree_code guard_code, tree guard_init)
|
|
|
397 {
|
|
|
398 /* The niter structure contains the after-increment IV, we need
|
|
|
399 the loop-enter base, so subtract STEP once. */
|
|
|
400 tree controlbase = force_gimple_operand (niter->control.base,
|
|
|
401 stmts, true, NULL_TREE);
|
|
|
402 tree controlstep = niter->control.step;
|
|
|
403 tree enddiff;
|
|
|
404 if (POINTER_TYPE_P (TREE_TYPE (controlbase)))
|
|
|
405 {
|
|
|
406 controlstep = gimple_build (stmts, NEGATE_EXPR,
|
|
|
407 TREE_TYPE (controlstep), controlstep);
|
|
|
408 enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
|
|
|
409 TREE_TYPE (controlbase),
|
|
|
410 controlbase, controlstep);
|
|
|
411 }
|
|
|
412 else
|
|
|
413 enddiff = gimple_build (stmts, MINUS_EXPR,
|
|
|
414 TREE_TYPE (controlbase),
|
|
|
415 controlbase, controlstep);
|
|
|
416
|
|
|
417 /* Compute end-beg. */
|
|
|
418 gimple_seq stmts2;
|
|
|
419 tree end = force_gimple_operand (niter->bound, &stmts2,
|
|
|
420 true, NULL_TREE);
|
|
|
421 gimple_seq_add_seq_without_update (stmts, stmts2);
|
|
|
422 if (POINTER_TYPE_P (TREE_TYPE (enddiff)))
|
|
|
423 {
|
|
|
424 tree tem = gimple_convert (stmts, sizetype, enddiff);
|
|
|
425 tem = gimple_build (stmts, NEGATE_EXPR, sizetype, tem);
|
|
|
426 enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
|
|
|
427 TREE_TYPE (enddiff),
|
|
|
428 end, tem);
|
|
|
429 }
|
|
|
430 else
|
|
|
431 enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff),
|
|
|
432 end, enddiff);
|
|
|
433
|
|
|
434 /* Compute guard_init + (end-beg). */
|
|
|
435 tree newbound;
|
|
|
436 enddiff = gimple_convert (stmts, TREE_TYPE (guard_init), enddiff);
|
|
|
437 if (POINTER_TYPE_P (TREE_TYPE (guard_init)))
|
|
|
438 {
|
|
|
439 enddiff = gimple_convert (stmts, sizetype, enddiff);
|
|
|
440 newbound = gimple_build (stmts, POINTER_PLUS_EXPR,
|
|
|
441 TREE_TYPE (guard_init),
|
|
|
442 guard_init, enddiff);
|
|
|
443 }
|
|
|
444 else
|
|
|
445 newbound = gimple_build (stmts, PLUS_EXPR, TREE_TYPE (guard_init),
|
|
|
446 guard_init, enddiff);
|
|
|
447
|
|
|
448 /* Depending on the direction of the IVs the new bound for the first
|
|
|
449 loop is the minimum or maximum of old bound and border.
|
|
|
450 Also, if the guard condition isn't strictly less or greater,
|
|
|
451 we need to adjust the bound. */
|
|
|
452 int addbound = 0;
|
|
|
453 enum tree_code minmax;
|
|
|
454 if (niter->cmp == LT_EXPR)
|
|
|
455 {
|
|
|
456 /* GT and LE are the same, inverted. */
|
|
|
457 if (guard_code == GT_EXPR || guard_code == LE_EXPR)
|
|
|
458 addbound = -1;
|
|
|
459 minmax = MIN_EXPR;
|
|
|
460 }
|
|
|
461 else
|
|
|
462 {
|
|
|
463 gcc_assert (niter->cmp == GT_EXPR);
|
|
|
464 if (guard_code == GE_EXPR || guard_code == LT_EXPR)
|
|
|
465 addbound = 1;
|
|
|
466 minmax = MAX_EXPR;
|
|
|
467 }
|
|
|
468
|
|
|
469 if (addbound)
|
|
|
470 {
|
|
|
471 tree type2 = TREE_TYPE (newbound);
|
|
|
472 if (POINTER_TYPE_P (type2))
|
|
|
473 type2 = sizetype;
|
|
|
474 newbound = gimple_build (stmts,
|
|
|
475 POINTER_TYPE_P (TREE_TYPE (newbound))
|
|
|
476 ? POINTER_PLUS_EXPR : PLUS_EXPR,
|
|
|
477 TREE_TYPE (newbound),
|
|
|
478 newbound,
|
|
|
479 build_int_cst (type2, addbound));
|
|
|
480 }
|
|
|
481
|
|
|
482 tree newend = gimple_build (stmts, minmax, TREE_TYPE (border),
|
|
|
483 border, newbound);
|
|
|
484 return newend;
|
|
|
485 }
|
|
|
486
|
|
|
487 /* Checks if LOOP contains an conditional block whose condition
|
|
|
488 depends on which side in the iteration space it is, and if so
|
|
|
489 splits the iteration space into two loops. Returns true if the
|
|
|
490 loop was split. NITER must contain the iteration descriptor for the
|
|
|
491 single exit of LOOP. */
|
|
|
492
|
|
|
493 static bool
|
|
145
|
494 split_loop (class loop *loop1)
|
|
111
|
495 {
|
|
145
|
496 class tree_niter_desc niter;
|
|
111
|
497 basic_block *bbs;
|
|
|
498 unsigned i;
|
|
|
499 bool changed = false;
|
|
|
500 tree guard_iv;
|
|
|
501 tree border = NULL_TREE;
|
|
|
502 affine_iv iv;
|
|
|
503
|
|
145
|
504 if (!single_exit (loop1)
|
|
|
505 /* ??? We could handle non-empty latches when we split the latch edge
|
|
|
506 (not the exit edge), and put the new exit condition in the new block.
|
|
|
507 OTOH this executes some code unconditionally that might have been
|
|
|
508 skipped by the original exit before. */
|
|
|
509 || !empty_block_p (loop1->latch)
|
|
|
510 || !easy_exit_values (loop1)
|
|
|
511 || !number_of_iterations_exit (loop1, single_exit (loop1), &niter,
|
|
|
512 false, true)
|
|
|
513 || niter.cmp == ERROR_MARK
|
|
|
514 /* We can't yet handle loops controlled by a != predicate. */
|
|
|
515 || niter.cmp == NE_EXPR)
|
|
|
516 return false;
|
|
|
517
|
|
111
|
518 bbs = get_loop_body (loop1);
|
|
|
519
|
|
145
|
520 if (!can_copy_bbs_p (bbs, loop1->num_nodes))
|
|
|
521 {
|
|
|
522 free (bbs);
|
|
|
523 return false;
|
|
|
524 }
|
|
|
525
|
|
111
|
526 /* Find a splitting opportunity. */
|
|
|
527 for (i = 0; i < loop1->num_nodes; i++)
|
|
|
528 if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv)))
|
|
|
529 {
|
|
|
530 /* Handling opposite steps is not implemented yet. Neither
|
|
|
531 is handling different step sizes. */
|
|
|
532 if ((tree_int_cst_sign_bit (iv.step)
|
|
145
|
533 != tree_int_cst_sign_bit (niter.control.step))
|
|
|
534 || !tree_int_cst_equal (iv.step, niter.control.step))
|
|
111
|
535 continue;
|
|
|
536
|
|
|
537 /* Find a loop PHI node that defines guard_iv directly,
|
|
|
538 or create one doing that. */
|
|
|
539 gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv);
|
|
|
540 if (!phi)
|
|
|
541 continue;
|
|
|
542 gcond *guard_stmt = as_a<gcond *> (last_stmt (bbs[i]));
|
|
|
543 tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi,
|
|
|
544 loop_preheader_edge (loop1));
|
|
|
545 enum tree_code guard_code = gimple_cond_code (guard_stmt);
|
|
|
546
|
|
|
547 /* Loop splitting is implemented by versioning the loop, placing
|
|
|
548 the new loop after the old loop, make the first loop iterate
|
|
|
549 as long as the conditional stays true (or false) and let the
|
|
|
550 second (new) loop handle the rest of the iterations.
|
|
|
551
|
|
|
552 First we need to determine if the condition will start being true
|
|
|
553 or false in the first loop. */
|
|
|
554 bool initial_true;
|
|
|
555 switch (guard_code)
|
|
|
556 {
|
|
|
557 case LT_EXPR:
|
|
|
558 case LE_EXPR:
|
|
|
559 initial_true = !tree_int_cst_sign_bit (iv.step);
|
|
|
560 break;
|
|
|
561 case GT_EXPR:
|
|
|
562 case GE_EXPR:
|
|
|
563 initial_true = tree_int_cst_sign_bit (iv.step);
|
|
|
564 break;
|
|
|
565 default:
|
|
|
566 gcc_unreachable ();
|
|
|
567 }
|
|
|
568
|
|
|
569 /* Build a condition that will skip the first loop when the
|
|
|
570 guard condition won't ever be true (or false). */
|
|
|
571 gimple_seq stmts2;
|
|
|
572 border = force_gimple_operand (border, &stmts2, true, NULL_TREE);
|
|
|
573 if (stmts2)
|
|
|
574 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
|
|
|
575 stmts2);
|
|
|
576 tree cond = build2 (guard_code, boolean_type_node, guard_init, border);
|
|
|
577 if (!initial_true)
|
|
|
578 cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
|
|
|
579
|
|
|
580 /* Now version the loop, placing loop2 after loop1 connecting
|
|
|
581 them, and fix up SSA form for that. */
|
|
|
582 initialize_original_copy_tables ();
|
|
|
583 basic_block cond_bb;
|
|
|
584
|
|
145
|
585 class loop *loop2 = loop_version (loop1, cond, &cond_bb,
|
|
111
|
586 profile_probability::always (),
|
|
|
587 profile_probability::always (),
|
|
|
588 profile_probability::always (),
|
|
|
589 profile_probability::always (),
|
|
|
590 true);
|
|
|
591 gcc_assert (loop2);
|
|
|
592 update_ssa (TODO_update_ssa);
|
|
|
593
|
|
|
594 edge new_e = connect_loops (loop1, loop2);
|
|
|
595 connect_loop_phis (loop1, loop2, new_e);
|
|
|
596
|
|
|
597 /* The iterations of the second loop is now already
|
|
|
598 exactly those that the first loop didn't do, but the
|
|
|
599 iteration space of the first loop is still the original one.
|
|
|
600 Compute the new bound for the guarding IV and patch the
|
|
|
601 loop exit to use it instead of original IV and bound. */
|
|
|
602 gimple_seq stmts = NULL;
|
|
145
|
603 tree newend = compute_new_first_bound (&stmts, &niter, border,
|
|
111
|
604 guard_code, guard_init);
|
|
|
605 if (stmts)
|
|
|
606 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
|
|
|
607 stmts);
|
|
|
608 tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1));
|
|
|
609 patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true);
|
|
|
610
|
|
|
611 /* Finally patch out the two copies of the condition to be always
|
|
|
612 true/false (or opposite). */
|
|
|
613 gcond *force_true = as_a<gcond *> (last_stmt (bbs[i]));
|
|
|
614 gcond *force_false = as_a<gcond *> (last_stmt (get_bb_copy (bbs[i])));
|
|
|
615 if (!initial_true)
|
|
|
616 std::swap (force_true, force_false);
|
|
|
617 gimple_cond_make_true (force_true);
|
|
|
618 gimple_cond_make_false (force_false);
|
|
|
619 update_stmt (force_true);
|
|
|
620 update_stmt (force_false);
|
|
|
621
|
|
|
622 free_original_copy_tables ();
|
|
|
623
|
|
|
624 /* We destroyed LCSSA form above. Eventually we might be able
|
|
|
625 to fix it on the fly, for now simply punt and use the helper. */
|
|
|
626 rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1);
|
|
|
627
|
|
|
628 changed = true;
|
|
|
629 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
630 fprintf (dump_file, ";; Loop split.\n");
|
|
|
631
|
|
|
632 /* Only deal with the first opportunity. */
|
|
|
633 break;
|
|
|
634 }
|
|
|
635
|
|
|
636 free (bbs);
|
|
|
637 return changed;
|
|
|
638 }
|
|
|
639
|
|
145
|
640 /* Another transformation of loops like:
|
|
|
641
|
|
|
642 for (i = INIT (); CHECK (i); i = NEXT ())
|
|
|
643 {
|
|
|
644 if (expr (a_1, a_2, ..., a_n)) // expr is pure
|
|
|
645 a_j = ...; // change at least one a_j
|
|
|
646 else
|
|
|
647 S; // not change any a_j
|
|
|
648 }
|
|
|
649
|
|
|
650 into:
|
|
|
651
|
|
|
652 for (i = INIT (); CHECK (i); i = NEXT ())
|
|
|
653 {
|
|
|
654 if (expr (a_1, a_2, ..., a_n))
|
|
|
655 a_j = ...;
|
|
|
656 else
|
|
|
657 {
|
|
|
658 S;
|
|
|
659 i = NEXT ();
|
|
|
660 break;
|
|
|
661 }
|
|
|
662 }
|
|
|
663
|
|
|
664 for (; CHECK (i); i = NEXT ())
|
|
|
665 {
|
|
|
666 S;
|
|
|
667 }
|
|
|
668
|
|
|
669 */
|
|
|
670
|
|
|
671 /* Data structure to hold temporary information during loop split upon
|
|
|
672 semi-invariant conditional statement. */
|
|
|
673 class split_info {
|
|
|
674 public:
|
|
|
675 /* Array of all basic blocks in a loop, returned by get_loop_body(). */
|
|
|
676 basic_block *bbs;
|
|
|
677
|
|
|
678 /* All memory store/clobber statements in a loop. */
|
|
|
679 auto_vec<gimple *> memory_stores;
|
|
|
680
|
|
|
681 /* Whether above memory stores vector has been filled. */
|
|
|
682 int need_init;
|
|
|
683
|
|
|
684 /* Control dependencies of basic blocks in a loop. */
|
|
|
685 auto_vec<hash_set<basic_block> *> control_deps;
|
|
|
686
|
|
|
687 split_info () : bbs (NULL), need_init (true) { }
|
|
|
688
|
|
|
689 ~split_info ()
|
|
|
690 {
|
|
|
691 if (bbs)
|
|
|
692 free (bbs);
|
|
|
693
|
|
|
694 for (unsigned i = 0; i < control_deps.length (); i++)
|
|
|
695 delete control_deps[i];
|
|
|
696 }
|
|
|
697 };
|
|
|
698
|
|
|
699 /* Find all statements with memory-write effect in LOOP, including memory
|
|
|
700 store and non-pure function call, and keep those in a vector. This work
|
|
|
701 is only done one time, for the vector should be constant during analysis
|
|
|
702 stage of semi-invariant condition. */
|
|
|
703
|
|
|
704 static void
|
|
|
705 find_vdef_in_loop (struct loop *loop)
|
|
|
706 {
|
|
|
707 split_info *info = (split_info *) loop->aux;
|
|
|
708 gphi *vphi = get_virtual_phi (loop->header);
|
|
|
709
|
|
|
710 /* Indicate memory store vector has been filled. */
|
|
|
711 info->need_init = false;
|
|
|
712
|
|
|
713 /* If loop contains memory operation, there must be a virtual PHI node in
|
|
|
714 loop header basic block. */
|
|
|
715 if (vphi == NULL)
|
|
|
716 return;
|
|
|
717
|
|
|
718 /* All virtual SSA names inside the loop are connected to be a cyclic
|
|
|
719 graph via virtual PHI nodes. The virtual PHI node in loop header just
|
|
|
720 links the first and the last virtual SSA names, by using the last as
|
|
|
721 PHI operand to define the first. */
|
|
|
722 const edge latch = loop_latch_edge (loop);
|
|
|
723 const tree first = gimple_phi_result (vphi);
|
|
|
724 const tree last = PHI_ARG_DEF_FROM_EDGE (vphi, latch);
|
|
|
725
|
|
|
726 /* The virtual SSA cyclic graph might consist of only one SSA name, who
|
|
|
727 is defined by itself.
|
|
|
728
|
|
|
729 .MEM_1 = PHI <.MEM_2(loop entry edge), .MEM_1(latch edge)>
|
|
|
730
|
|
|
731 This means the loop contains only memory loads, so we can skip it. */
|
|
|
732 if (first == last)
|
|
|
733 return;
|
|
|
734
|
|
|
735 auto_vec<gimple *> other_stores;
|
|
|
736 auto_vec<tree> worklist;
|
|
|
737 auto_bitmap visited;
|
|
|
738
|
|
|
739 bitmap_set_bit (visited, SSA_NAME_VERSION (first));
|
|
|
740 bitmap_set_bit (visited, SSA_NAME_VERSION (last));
|
|
|
741 worklist.safe_push (last);
|
|
|
742
|
|
|
743 do
|
|
|
744 {
|
|
|
745 tree vuse = worklist.pop ();
|
|
|
746 gimple *stmt = SSA_NAME_DEF_STMT (vuse);
|
|
|
747
|
|
|
748 /* We mark the first and last SSA names as visited at the beginning,
|
|
|
749 and reversely start the process from the last SSA name towards the
|
|
|
750 first, which ensures that this do-while will not touch SSA names
|
|
|
751 defined outside the loop. */
|
|
|
752 gcc_assert (gimple_bb (stmt)
|
|
|
753 && flow_bb_inside_loop_p (loop, gimple_bb (stmt)));
|
|
|
754
|
|
|
755 if (gimple_code (stmt) == GIMPLE_PHI)
|
|
|
756 {
|
|
|
757 gphi *phi = as_a <gphi *> (stmt);
|
|
|
758
|
|
|
759 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
|
|
|
760 {
|
|
|
761 tree arg = gimple_phi_arg_def (stmt, i);
|
|
|
762
|
|
|
763 if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
|
|
|
764 worklist.safe_push (arg);
|
|
|
765 }
|
|
|
766 }
|
|
|
767 else
|
|
|
768 {
|
|
|
769 tree prev = gimple_vuse (stmt);
|
|
|
770
|
|
|
771 /* Non-pure call statement is conservatively assumed to impact all
|
|
|
772 memory locations. So place call statements ahead of other memory
|
|
|
773 stores in the vector with an idea of of using them as shortcut
|
|
|
774 terminators to memory alias analysis. */
|
|
|
775 if (gimple_code (stmt) == GIMPLE_CALL)
|
|
|
776 info->memory_stores.safe_push (stmt);
|
|
|
777 else
|
|
|
778 other_stores.safe_push (stmt);
|
|
|
779
|
|
|
780 if (bitmap_set_bit (visited, SSA_NAME_VERSION (prev)))
|
|
|
781 worklist.safe_push (prev);
|
|
|
782 }
|
|
|
783 } while (!worklist.is_empty ());
|
|
|
784
|
|
|
785 info->memory_stores.safe_splice (other_stores);
|
|
|
786 }
|
|
|
787
|
|
|
788 /* Two basic blocks have equivalent control dependency if one dominates to
|
|
|
789 the other, and it is post-dominated by the latter. Given a basic block
|
|
|
790 BB in LOOP, find farest equivalent dominating basic block. For BB, there
|
|
|
791 is a constraint that BB does not post-dominate loop header of LOOP, this
|
|
|
792 means BB is control-dependent on at least one basic block in LOOP. */
|
|
|
793
|
|
|
794 static basic_block
|
|
|
795 get_control_equiv_head_block (struct loop *loop, basic_block bb)
|
|
|
796 {
|
|
|
797 while (!bb->aux)
|
|
|
798 {
|
|
|
799 basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
|
|
|
800
|
|
|
801 gcc_checking_assert (dom_bb && flow_bb_inside_loop_p (loop, dom_bb));
|
|
|
802
|
|
|
803 if (!dominated_by_p (CDI_POST_DOMINATORS, dom_bb, bb))
|
|
|
804 break;
|
|
|
805
|
|
|
806 bb = dom_bb;
|
|
|
807 }
|
|
|
808 return bb;
|
|
|
809 }
|
|
|
810
|
|
|
811 /* Given a BB in LOOP, find out all basic blocks in LOOP that BB is control-
|
|
|
812 dependent on. */
|
|
|
813
|
|
|
814 static hash_set<basic_block> *
|
|
|
815 find_control_dep_blocks (struct loop *loop, basic_block bb)
|
|
|
816 {
|
|
|
817 /* BB has same control dependency as loop header, then it is not control-
|
|
|
818 dependent on any basic block in LOOP. */
|
|
|
819 if (dominated_by_p (CDI_POST_DOMINATORS, loop->header, bb))
|
|
|
820 return NULL;
|
|
|
821
|
|
|
822 basic_block equiv_head = get_control_equiv_head_block (loop, bb);
|
|
|
823
|
|
|
824 if (equiv_head->aux)
|
|
|
825 {
|
|
|
826 /* There is a basic block containing control dependency equivalent
|
|
|
827 to BB. No need to recompute that, and also set this information
|
|
|
828 to other equivalent basic blocks. */
|
|
|
829 for (; bb != equiv_head;
|
|
|
830 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
|
|
|
831 bb->aux = equiv_head->aux;
|
|
|
832 return (hash_set<basic_block> *) equiv_head->aux;
|
|
|
833 }
|
|
|
834
|
|
|
835 /* A basic block X is control-dependent on another Y iff there exists
|
|
|
836 a path from X to Y, in which every basic block other than X and Y
|
|
|
837 is post-dominated by Y, but X is not post-dominated by Y.
|
|
|
838
|
|
|
839 According to this rule, traverse basic blocks in the loop backwards
|
|
|
840 starting from BB, if a basic block is post-dominated by BB, extend
|
|
|
841 current post-dominating path to this block, otherwise it is another
|
|
|
842 one that BB is control-dependent on. */
|
|
|
843
|
|
|
844 auto_vec<basic_block> pdom_worklist;
|
|
|
845 hash_set<basic_block> pdom_visited;
|
|
|
846 hash_set<basic_block> *dep_bbs = new hash_set<basic_block>;
|
|
|
847
|
|
|
848 pdom_worklist.safe_push (equiv_head);
|
|
|
849
|
|
|
850 do
|
|
|
851 {
|
|
|
852 basic_block pdom_bb = pdom_worklist.pop ();
|
|
|
853 edge_iterator ei;
|
|
|
854 edge e;
|
|
|
855
|
|
|
856 if (pdom_visited.add (pdom_bb))
|
|
|
857 continue;
|
|
|
858
|
|
|
859 FOR_EACH_EDGE (e, ei, pdom_bb->preds)
|
|
|
860 {
|
|
|
861 basic_block pred_bb = e->src;
|
|
|
862
|
|
|
863 if (!dominated_by_p (CDI_POST_DOMINATORS, pred_bb, bb))
|
|
|
864 {
|
|
|
865 dep_bbs->add (pred_bb);
|
|
|
866 continue;
|
|
|
867 }
|
|
|
868
|
|
|
869 pred_bb = get_control_equiv_head_block (loop, pred_bb);
|
|
|
870
|
|
|
871 if (pdom_visited.contains (pred_bb))
|
|
|
872 continue;
|
|
|
873
|
|
|
874 if (!pred_bb->aux)
|
|
|
875 {
|
|
|
876 pdom_worklist.safe_push (pred_bb);
|
|
|
877 continue;
|
|
|
878 }
|
|
|
879
|
|
|
880 /* If control dependency of basic block is available, fast extend
|
|
|
881 post-dominating path using the information instead of advancing
|
|
|
882 forward step-by-step. */
|
|
|
883 hash_set<basic_block> *pred_dep_bbs
|
|
|
884 = (hash_set<basic_block> *) pred_bb->aux;
|
|
|
885
|
|
|
886 for (hash_set<basic_block>::iterator iter = pred_dep_bbs->begin ();
|
|
|
887 iter != pred_dep_bbs->end (); ++iter)
|
|
|
888 {
|
|
|
889 basic_block pred_dep_bb = *iter;
|
|
|
890
|
|
|
891 /* Basic blocks can either be in control dependency of BB, or
|
|
|
892 must be post-dominated by BB, if so, extend the path from
|
|
|
893 these basic blocks. */
|
|
|
894 if (!dominated_by_p (CDI_POST_DOMINATORS, pred_dep_bb, bb))
|
|
|
895 dep_bbs->add (pred_dep_bb);
|
|
|
896 else if (!pdom_visited.contains (pred_dep_bb))
|
|
|
897 pdom_worklist.safe_push (pred_dep_bb);
|
|
|
898 }
|
|
|
899 }
|
|
|
900 } while (!pdom_worklist.is_empty ());
|
|
|
901
|
|
|
902 /* Record computed control dependencies in loop so that we can reach them
|
|
|
903 when reclaiming resources. */
|
|
|
904 ((split_info *) loop->aux)->control_deps.safe_push (dep_bbs);
|
|
|
905
|
|
|
906 /* Associate control dependence with related equivalent basic blocks. */
|
|
|
907 for (equiv_head->aux = dep_bbs; bb != equiv_head;
|
|
|
908 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
|
|
|
909 bb->aux = dep_bbs;
|
|
|
910
|
|
|
911 return dep_bbs;
|
|
|
912 }
|
|
|
913
|
|
|
914 /* Forward declaration */
|
|
|
915
|
|
|
916 static bool
|
|
|
917 stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
|
|
|
918 const_basic_block skip_head,
|
|
|
919 hash_map<gimple *, bool> &stmt_stat);
|
|
|
920
|
|
|
921 /* Given STMT, memory load or pure call statement, check whether it is impacted
|
|
|
922 by some memory store in LOOP, excluding trace starting from SKIP_HEAD (the
|
|
|
923 trace is composed of SKIP_HEAD and those basic block dominated by it, always
|
|
|
924 corresponds to one branch of a conditional statement). If SKIP_HEAD is
|
|
|
925 NULL, all basic blocks of LOOP are checked. */
|
|
|
926
|
|
|
927 static bool
|
|
|
928 vuse_semi_invariant_p (struct loop *loop, gimple *stmt,
|
|
|
929 const_basic_block skip_head)
|
|
|
930 {
|
|
|
931 split_info *info = (split_info *) loop->aux;
|
|
|
932 tree rhs = NULL_TREE;
|
|
|
933 ao_ref ref;
|
|
|
934 gimple *store;
|
|
|
935 unsigned i;
|
|
|
936
|
|
|
937 /* Collect memory store/clobber statements if haven't done that. */
|
|
|
938 if (info->need_init)
|
|
|
939 find_vdef_in_loop (loop);
|
|
|
940
|
|
|
941 if (is_gimple_assign (stmt))
|
|
|
942 rhs = gimple_assign_rhs1 (stmt);
|
|
|
943
|
|
|
944 ao_ref_init (&ref, rhs);
|
|
|
945
|
|
|
946 FOR_EACH_VEC_ELT (info->memory_stores, i, store)
|
|
|
947 {
|
|
|
948 /* Skip basic blocks dominated by SKIP_HEAD, if non-NULL. */
|
|
|
949 if (skip_head
|
|
|
950 && dominated_by_p (CDI_DOMINATORS, gimple_bb (store), skip_head))
|
|
|
951 continue;
|
|
|
952
|
|
|
953 if (!ref.ref || stmt_may_clobber_ref_p_1 (store, &ref))
|
|
|
954 return false;
|
|
|
955 }
|
|
|
956
|
|
|
957 return true;
|
|
|
958 }
|
|
|
959
|
|
|
960 /* Suppose one condition branch, led by SKIP_HEAD, is not executed since
|
|
|
961 certain iteration of LOOP, check whether an SSA name (NAME) remains
|
|
|
962 unchanged in next iteration. We call this characteristic semi-
|
|
|
963 invariantness. SKIP_HEAD might be NULL, if so, nothing excluded, all basic
|
|
|
964 blocks and control flows in the loop will be considered. Semi-invariant
|
|
|
965 state of checked statement is cached in hash map STMT_STAT to avoid
|
|
|
966 redundant computation in possible following re-check. */
|
|
|
967
|
|
|
968 static inline bool
|
|
|
969 ssa_semi_invariant_p (struct loop *loop, tree name,
|
|
|
970 const_basic_block skip_head,
|
|
|
971 hash_map<gimple *, bool> &stmt_stat)
|
|
|
972 {
|
|
|
973 gimple *def = SSA_NAME_DEF_STMT (name);
|
|
|
974 const_basic_block def_bb = gimple_bb (def);
|
|
|
975
|
|
|
976 /* An SSA name defined outside loop is definitely semi-invariant. */
|
|
|
977 if (!def_bb || !flow_bb_inside_loop_p (loop, def_bb))
|
|
|
978 return true;
|
|
|
979
|
|
|
980 return stmt_semi_invariant_p_1 (loop, def, skip_head, stmt_stat);
|
|
|
981 }
|
|
|
982
|
|
|
983 /* Check whether a loop iteration PHI node (LOOP_PHI) defines a value that is
|
|
|
984 semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
|
|
|
985 are excluded from LOOP. */
|
|
|
986
|
|
|
987 static bool
|
|
|
988 loop_iter_phi_semi_invariant_p (struct loop *loop, gphi *loop_phi,
|
|
|
989 const_basic_block skip_head)
|
|
|
990 {
|
|
|
991 const_edge latch = loop_latch_edge (loop);
|
|
|
992 tree name = gimple_phi_result (loop_phi);
|
|
|
993 tree from = PHI_ARG_DEF_FROM_EDGE (loop_phi, latch);
|
|
|
994
|
|
|
995 gcc_checking_assert (from);
|
|
|
996
|
|
|
997 /* Loop iteration PHI node locates in loop header, and it has two source
|
|
|
998 operands, one is an initial value coming from outside the loop, the other
|
|
|
999 is a value through latch of the loop, which is derived in last iteration,
|
|
|
1000 we call the latter latch value. From the PHI node to definition of latch
|
|
|
1001 value, if excluding branch trace starting from SKIP_HEAD, except copy-
|
|
|
1002 assignment or likewise, there is no other kind of value redefinition, SSA
|
|
|
1003 name defined by the PHI node is semi-invariant.
|
|
|
1004
|
|
|
1005 loop entry
|
|
|
1006 | .--- latch ---.
|
|
|
1007 | | |
|
|
|
1008 v v |
|
|
|
1009 x_1 = PHI <x_0, x_3> |
|
|
|
1010 | |
|
|
|
1011 v |
|
|
|
1012 .------- if (cond) -------. |
|
|
|
1013 | | |
|
|
|
1014 | [ SKIP ] |
|
|
|
1015 | | |
|
|
|
1016 | x_2 = ... |
|
|
|
1017 | | |
|
|
|
1018 '---- T ---->.<---- F ----' |
|
|
|
1019 | |
|
|
|
1020 v |
|
|
|
1021 x_3 = PHI <x_1, x_2> |
|
|
|
1022 | |
|
|
|
1023 '----------------------'
|
|
|
1024
|
|
|
1025 Suppose in certain iteration, execution flow in above graph goes through
|
|
|
1026 true branch, which means that one source value to define x_3 in false
|
|
|
1027 branch (x_2) is skipped, x_3 only comes from x_1, and x_1 in next
|
|
|
1028 iterations is defined by x_3, we know that x_1 will never changed if COND
|
|
|
1029 always chooses true branch from then on. */
|
|
|
1030
|
|
|
1031 while (from != name)
|
|
|
1032 {
|
|
|
1033 /* A new value comes from a CONSTANT. */
|
|
|
1034 if (TREE_CODE (from) != SSA_NAME)
|
|
|
1035 return false;
|
|
|
1036
|
|
|
1037 gimple *stmt = SSA_NAME_DEF_STMT (from);
|
|
|
1038 const_basic_block bb = gimple_bb (stmt);
|
|
|
1039
|
|
|
1040 /* A new value comes from outside the loop. */
|
|
|
1041 if (!bb || !flow_bb_inside_loop_p (loop, bb))
|
|
|
1042 return false;
|
|
|
1043
|
|
|
1044 from = NULL_TREE;
|
|
|
1045
|
|
|
1046 if (gimple_code (stmt) == GIMPLE_PHI)
|
|
|
1047 {
|
|
|
1048 gphi *phi = as_a <gphi *> (stmt);
|
|
|
1049
|
|
|
1050 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
|
|
|
1051 {
|
|
|
1052 if (skip_head)
|
|
|
1053 {
|
|
|
1054 const_edge e = gimple_phi_arg_edge (phi, i);
|
|
|
1055
|
|
|
1056 /* Don't consider redefinitions in excluded basic blocks. */
|
|
|
1057 if (dominated_by_p (CDI_DOMINATORS, e->src, skip_head))
|
|
|
1058 continue;
|
|
|
1059 }
|
|
|
1060
|
|
|
1061 tree arg = gimple_phi_arg_def (phi, i);
|
|
|
1062
|
|
|
1063 if (!from)
|
|
|
1064 from = arg;
|
|
|
1065 else if (!operand_equal_p (from, arg, 0))
|
|
|
1066 /* There are more than one source operands that provide
|
|
|
1067 different values to the SSA name, it is variant. */
|
|
|
1068 return false;
|
|
|
1069 }
|
|
|
1070 }
|
|
|
1071 else if (gimple_code (stmt) == GIMPLE_ASSIGN)
|
|
|
1072 {
|
|
|
1073 /* For simple value copy, check its rhs instead. */
|
|
|
1074 if (gimple_assign_ssa_name_copy_p (stmt))
|
|
|
1075 from = gimple_assign_rhs1 (stmt);
|
|
|
1076 }
|
|
|
1077
|
|
|
1078 /* Any other kind of definition is deemed to introduce a new value
|
|
|
1079 to the SSA name. */
|
|
|
1080 if (!from)
|
|
|
1081 return false;
|
|
|
1082 }
|
|
|
1083 return true;
|
|
|
1084 }
|
|
|
1085
|
|
|
1086 /* Check whether conditional predicates that BB is control-dependent on, are
|
|
|
1087 semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL),
|
|
|
1088 are excluded from LOOP. Semi-invariant state of checked statement is cached
|
|
|
1089 in hash map STMT_STAT. */
|
|
|
1090
|
|
|
1091 static bool
|
|
|
1092 control_dep_semi_invariant_p (struct loop *loop, basic_block bb,
|
|
|
1093 const_basic_block skip_head,
|
|
|
1094 hash_map<gimple *, bool> &stmt_stat)
|
|
|
1095 {
|
|
|
1096 hash_set<basic_block> *dep_bbs = find_control_dep_blocks (loop, bb);
|
|
|
1097
|
|
|
1098 if (!dep_bbs)
|
|
|
1099 return true;
|
|
|
1100
|
|
|
1101 for (hash_set<basic_block>::iterator iter = dep_bbs->begin ();
|
|
|
1102 iter != dep_bbs->end (); ++iter)
|
|
|
1103 {
|
|
|
1104 gimple *last = last_stmt (*iter);
|
|
|
1105
|
|
|
1106 if (!last)
|
|
|
1107 return false;
|
|
|
1108
|
|
|
1109 /* Only check condition predicates. */
|
|
|
1110 if (gimple_code (last) != GIMPLE_COND
|
|
|
1111 && gimple_code (last) != GIMPLE_SWITCH)
|
|
|
1112 return false;
|
|
|
1113
|
|
|
1114 if (!stmt_semi_invariant_p_1 (loop, last, skip_head, stmt_stat))
|
|
|
1115 return false;
|
|
|
1116 }
|
|
|
1117
|
|
|
1118 return true;
|
|
|
1119 }
|
|
|
1120
|
|
|
1121 /* Check whether STMT is semi-invariant in LOOP, iff all its operands are
|
|
|
1122 semi-invariant, consequently, all its defined values are semi-invariant.
|
|
|
1123 Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP.
|
|
|
1124 Semi-invariant state of checked statement is cached in hash map
|
|
|
1125 STMT_STAT. */
|
|
|
1126
|
|
|
1127 static bool
|
|
|
1128 stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
|
|
|
1129 const_basic_block skip_head,
|
|
|
1130 hash_map<gimple *, bool> &stmt_stat)
|
|
|
1131 {
|
|
|
1132 bool existed;
|
|
|
1133 bool &invar = stmt_stat.get_or_insert (stmt, &existed);
|
|
|
1134
|
|
|
1135 if (existed)
|
|
|
1136 return invar;
|
|
|
1137
|
|
|
1138 /* A statement might depend on itself, which is treated as variant. So set
|
|
|
1139 state of statement under check to be variant to ensure that. */
|
|
|
1140 invar = false;
|
|
|
1141
|
|
|
1142 if (gimple_code (stmt) == GIMPLE_PHI)
|
|
|
1143 {
|
|
|
1144 gphi *phi = as_a <gphi *> (stmt);
|
|
|
1145
|
|
|
1146 if (gimple_bb (stmt) == loop->header)
|
|
|
1147 {
|
|
|
1148 invar = loop_iter_phi_semi_invariant_p (loop, phi, skip_head);
|
|
|
1149 return invar;
|
|
|
1150 }
|
|
|
1151
|
|
|
1152 /* For a loop PHI node that does not locate in loop header, it is semi-
|
|
|
1153 invariant only if two conditions are met. The first is its source
|
|
|
1154 values are derived from CONSTANT (including loop-invariant value), or
|
|
|
1155 from SSA name defined by semi-invariant loop iteration PHI node. The
|
|
|
1156 second is its source incoming edges are control-dependent on semi-
|
|
|
1157 invariant conditional predicates. */
|
|
|
1158 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
|
|
|
1159 {
|
|
|
1160 const_edge e = gimple_phi_arg_edge (phi, i);
|
|
|
1161 tree arg = gimple_phi_arg_def (phi, i);
|
|
|
1162
|
|
|
1163 if (TREE_CODE (arg) == SSA_NAME)
|
|
|
1164 {
|
|
|
1165 if (!ssa_semi_invariant_p (loop, arg, skip_head, stmt_stat))
|
|
|
1166 return false;
|
|
|
1167
|
|
|
1168 /* If source value is defined in location from where the source
|
|
|
1169 edge comes in, no need to check control dependency again
|
|
|
1170 since this has been done in above SSA name check stage. */
|
|
|
1171 if (e->src == gimple_bb (SSA_NAME_DEF_STMT (arg)))
|
|
|
1172 continue;
|
|
|
1173 }
|
|
|
1174
|
|
|
1175 if (!control_dep_semi_invariant_p (loop, e->src, skip_head,
|
|
|
1176 stmt_stat))
|
|
|
1177 return false;
|
|
|
1178 }
|
|
|
1179 }
|
|
|
1180 else
|
|
|
1181 {
|
|
|
1182 ssa_op_iter iter;
|
|
|
1183 tree use;
|
|
|
1184
|
|
|
1185 /* Volatile memory load or return of normal (non-const/non-pure) call
|
|
|
1186 should not be treated as constant in each iteration of loop. */
|
|
|
1187 if (gimple_has_side_effects (stmt))
|
|
|
1188 return false;
|
|
|
1189
|
|
|
1190 /* Check if any memory store may kill memory load at this place. */
|
|
|
1191 if (gimple_vuse (stmt) && !vuse_semi_invariant_p (loop, stmt, skip_head))
|
|
|
1192 return false;
|
|
|
1193
|
|
|
1194 /* Although operand of a statement might be SSA name, CONSTANT or
|
|
|
1195 VARDECL, here we only need to check SSA name operands. This is
|
|
|
1196 because check on VARDECL operands, which involve memory loads,
|
|
|
1197 must have been done prior to invocation of this function in
|
|
|
1198 vuse_semi_invariant_p. */
|
|
|
1199 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
|
|
|
1200 if (!ssa_semi_invariant_p (loop, use, skip_head, stmt_stat))
|
|
|
1201 return false;
|
|
|
1202 }
|
|
|
1203
|
|
|
1204 if (!control_dep_semi_invariant_p (loop, gimple_bb (stmt), skip_head,
|
|
|
1205 stmt_stat))
|
|
|
1206 return false;
|
|
|
1207
|
|
|
1208 /* Here we SHOULD NOT use invar = true, since hash map might be changed due
|
|
|
1209 to new insertion, and thus invar may point to invalid memory. */
|
|
|
1210 stmt_stat.put (stmt, true);
|
|
|
1211 return true;
|
|
|
1212 }
|
|
|
1213
|
|
|
1214 /* A helper function to check whether STMT is semi-invariant in LOOP. Basic
|
|
|
1215 blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. */
|
|
|
1216
|
|
|
1217 static bool
|
|
|
1218 stmt_semi_invariant_p (struct loop *loop, gimple *stmt,
|
|
|
1219 const_basic_block skip_head)
|
|
|
1220 {
|
|
|
1221 hash_map<gimple *, bool> stmt_stat;
|
|
|
1222 return stmt_semi_invariant_p_1 (loop, stmt, skip_head, stmt_stat);
|
|
|
1223 }
|
|
|
1224
|
|
|
1225 /* Determine when conditional statement never transfers execution to one of its
|
|
|
1226 branch, whether we can remove the branch's leading basic block (BRANCH_BB)
|
|
|
1227 and those basic blocks dominated by BRANCH_BB. */
|
|
|
1228
|
|
|
1229 static bool
|
|
|
1230 branch_removable_p (basic_block branch_bb)
|
|
|
1231 {
|
|
|
1232 edge_iterator ei;
|
|
|
1233 edge e;
|
|
|
1234
|
|
|
1235 if (single_pred_p (branch_bb))
|
|
|
1236 return true;
|
|
|
1237
|
|
|
1238 FOR_EACH_EDGE (e, ei, branch_bb->preds)
|
|
|
1239 {
|
|
|
1240 if (dominated_by_p (CDI_DOMINATORS, e->src, branch_bb))
|
|
|
1241 continue;
|
|
|
1242
|
|
|
1243 if (dominated_by_p (CDI_DOMINATORS, branch_bb, e->src))
|
|
|
1244 continue;
|
|
|
1245
|
|
|
1246 /* The branch can be reached from opposite branch, or from some
|
|
|
1247 statement not dominated by the conditional statement. */
|
|
|
1248 return false;
|
|
|
1249 }
|
|
|
1250
|
|
|
1251 return true;
|
|
|
1252 }
|
|
|
1253
|
|
|
1254 /* Find out which branch of a conditional statement (COND) is invariant in the
|
|
|
1255 execution context of LOOP. That is: once the branch is selected in certain
|
|
|
1256 iteration of the loop, any operand that contributes to computation of the
|
|
|
1257 conditional statement remains unchanged in all following iterations. */
|
|
|
1258
|
|
|
1259 static edge
|
|
|
1260 get_cond_invariant_branch (struct loop *loop, gcond *cond)
|
|
|
1261 {
|
|
|
1262 basic_block cond_bb = gimple_bb (cond);
|
|
|
1263 basic_block targ_bb[2];
|
|
|
1264 bool invar[2];
|
|
|
1265 unsigned invar_checks = 0;
|
|
|
1266
|
|
|
1267 for (unsigned i = 0; i < 2; i++)
|
|
|
1268 {
|
|
|
1269 targ_bb[i] = EDGE_SUCC (cond_bb, i)->dest;
|
|
|
1270
|
|
|
1271 /* One branch directs to loop exit, no need to perform loop split upon
|
|
|
1272 this conditional statement. Firstly, it is trivial if the exit branch
|
|
|
1273 is semi-invariant, for the statement is just to break loop. Secondly,
|
|
|
1274 if the opposite branch is semi-invariant, it means that the statement
|
|
|
1275 is real loop-invariant, which is covered by loop unswitch. */
|
|
|
1276 if (!flow_bb_inside_loop_p (loop, targ_bb[i]))
|
|
|
1277 return NULL;
|
|
|
1278 }
|
|
|
1279
|
|
|
1280 for (unsigned i = 0; i < 2; i++)
|
|
|
1281 {
|
|
|
1282 invar[!i] = false;
|
|
|
1283
|
|
|
1284 if (!branch_removable_p (targ_bb[i]))
|
|
|
1285 continue;
|
|
|
1286
|
|
|
1287 /* Given a semi-invariant branch, if its opposite branch dominates
|
|
|
1288 loop latch, it and its following trace will only be executed in
|
|
|
1289 final iteration of loop, namely it is not part of repeated body
|
|
|
1290 of the loop. Similar to the above case that the branch is loop
|
|
|
1291 exit, no need to split loop. */
|
|
|
1292 if (dominated_by_p (CDI_DOMINATORS, loop->latch, targ_bb[i]))
|
|
|
1293 continue;
|
|
|
1294
|
|
|
1295 invar[!i] = stmt_semi_invariant_p (loop, cond, targ_bb[i]);
|
|
|
1296 invar_checks++;
|
|
|
1297 }
|
|
|
1298
|
|
|
1299 /* With both branches being invariant (handled by loop unswitch) or
|
|
|
1300 variant is not what we want. */
|
|
|
1301 if (invar[0] ^ !invar[1])
|
|
|
1302 return NULL;
|
|
|
1303
|
|
|
1304 /* Found a real loop-invariant condition, do nothing. */
|
|
|
1305 if (invar_checks < 2 && stmt_semi_invariant_p (loop, cond, NULL))
|
|
|
1306 return NULL;
|
|
|
1307
|
|
|
1308 return EDGE_SUCC (cond_bb, invar[0] ? 0 : 1);
|
|
|
1309 }
|
|
|
1310
|
|
|
1311 /* Calculate increased code size measured by estimated insn number if applying
|
|
|
1312 loop split upon certain branch (BRANCH_EDGE) of a conditional statement. */
|
|
|
1313
|
|
|
1314 static int
|
|
|
1315 compute_added_num_insns (struct loop *loop, const_edge branch_edge)
|
|
|
1316 {
|
|
|
1317 basic_block cond_bb = branch_edge->src;
|
|
|
1318 unsigned branch = EDGE_SUCC (cond_bb, 1) == branch_edge;
|
|
|
1319 basic_block opposite_bb = EDGE_SUCC (cond_bb, !branch)->dest;
|
|
|
1320 basic_block *bbs = ((split_info *) loop->aux)->bbs;
|
|
|
1321 int num = 0;
|
|
|
1322
|
|
|
1323 for (unsigned i = 0; i < loop->num_nodes; i++)
|
|
|
1324 {
|
|
|
1325 /* Do no count basic blocks only in opposite branch. */
|
|
|
1326 if (dominated_by_p (CDI_DOMINATORS, bbs[i], opposite_bb))
|
|
|
1327 continue;
|
|
|
1328
|
|
|
1329 num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights);
|
|
|
1330 }
|
|
|
1331
|
|
|
1332 /* It is unnecessary to evaluate expression of the conditional statement
|
|
|
1333 in new loop that contains only invariant branch. This expression should
|
|
|
1334 be constant value (either true or false). Exclude code size of insns
|
|
|
1335 that contribute to computation of the expression. */
|
|
|
1336
|
|
|
1337 auto_vec<gimple *> worklist;
|
|
|
1338 hash_set<gimple *> removed;
|
|
|
1339 gimple *stmt = last_stmt (cond_bb);
|
|
|
1340
|
|
|
1341 worklist.safe_push (stmt);
|
|
|
1342 removed.add (stmt);
|
|
|
1343 num -= estimate_num_insns (stmt, &eni_size_weights);
|
|
|
1344
|
|
|
1345 do
|
|
|
1346 {
|
|
|
1347 ssa_op_iter opnd_iter;
|
|
|
1348 use_operand_p opnd_p;
|
|
|
1349
|
|
|
1350 stmt = worklist.pop ();
|
|
|
1351 FOR_EACH_PHI_OR_STMT_USE (opnd_p, stmt, opnd_iter, SSA_OP_USE)
|
|
|
1352 {
|
|
|
1353 tree opnd = USE_FROM_PTR (opnd_p);
|
|
|
1354
|
|
|
1355 if (TREE_CODE (opnd) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (opnd))
|
|
|
1356 continue;
|
|
|
1357
|
|
|
1358 gimple *opnd_stmt = SSA_NAME_DEF_STMT (opnd);
|
|
|
1359 use_operand_p use_p;
|
|
|
1360 imm_use_iterator use_iter;
|
|
|
1361
|
|
|
1362 if (removed.contains (opnd_stmt)
|
|
|
1363 || !flow_bb_inside_loop_p (loop, gimple_bb (opnd_stmt)))
|
|
|
1364 continue;
|
|
|
1365
|
|
|
1366 FOR_EACH_IMM_USE_FAST (use_p, use_iter, opnd)
|
|
|
1367 {
|
|
|
1368 gimple *use_stmt = USE_STMT (use_p);
|
|
|
1369
|
|
|
1370 if (!is_gimple_debug (use_stmt) && !removed.contains (use_stmt))
|
|
|
1371 {
|
|
|
1372 opnd_stmt = NULL;
|
|
|
1373 break;
|
|
|
1374 }
|
|
|
1375 }
|
|
|
1376
|
|
|
1377 if (opnd_stmt)
|
|
|
1378 {
|
|
|
1379 worklist.safe_push (opnd_stmt);
|
|
|
1380 removed.add (opnd_stmt);
|
|
|
1381 num -= estimate_num_insns (opnd_stmt, &eni_size_weights);
|
|
|
1382 }
|
|
|
1383 }
|
|
|
1384 } while (!worklist.is_empty ());
|
|
|
1385
|
|
|
1386 gcc_assert (num >= 0);
|
|
|
1387 return num;
|
|
|
1388 }
|
|
|
1389
|
|
|
1390 /* Find out loop-invariant branch of a conditional statement (COND) if it has,
|
|
|
1391 and check whether it is eligible and profitable to perform loop split upon
|
|
|
1392 this branch in LOOP. */
|
|
|
1393
|
|
|
1394 static edge
|
|
|
1395 get_cond_branch_to_split_loop (struct loop *loop, gcond *cond)
|
|
|
1396 {
|
|
|
1397 edge invar_branch = get_cond_invariant_branch (loop, cond);
|
|
|
1398 if (!invar_branch)
|
|
|
1399 return NULL;
|
|
|
1400
|
|
|
1401 /* When accurate profile information is available, and execution
|
|
|
1402 frequency of the branch is too low, just let it go. */
|
|
|
1403 profile_probability prob = invar_branch->probability;
|
|
|
1404 if (prob.reliable_p ())
|
|
|
1405 {
|
|
|
1406 int thres = param_min_loop_cond_split_prob;
|
|
|
1407
|
|
|
1408 if (prob < profile_probability::always ().apply_scale (thres, 100))
|
|
|
1409 return NULL;
|
|
|
1410 }
|
|
|
1411
|
|
|
1412 /* Add a threshold for increased code size to disable loop split. */
|
|
|
1413 if (compute_added_num_insns (loop, invar_branch) > param_max_peeled_insns)
|
|
|
1414 return NULL;
|
|
|
1415
|
|
|
1416 return invar_branch;
|
|
|
1417 }
|
|
|
1418
|
|
|
1419 /* Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of some
|
|
|
1420 conditional statement, perform loop split transformation illustrated
|
|
|
1421 as the following graph.
|
|
|
1422
|
|
|
1423 .-------T------ if (true) ------F------.
|
|
|
1424 | .---------------. |
|
|
|
1425 | | | |
|
|
|
1426 v | v v
|
|
|
1427 pre-header | pre-header
|
|
|
1428 | .------------. | | .------------.
|
|
|
1429 | | | | | | |
|
|
|
1430 | v | | | v |
|
|
|
1431 header | | header |
|
|
|
1432 | | | | |
|
|
|
1433 .--- if (cond) ---. | | .--- if (true) ---. |
|
|
|
1434 | | | | | | |
|
|
|
1435 invariant | | | invariant | |
|
|
|
1436 | | | | | | |
|
|
|
1437 '---T--->.<---F---' | | '---T--->.<---F---' |
|
|
|
1438 | | / | |
|
|
|
1439 stmts | / stmts |
|
|
|
1440 | F T | |
|
|
|
1441 / \ | / / \ |
|
|
|
1442 .-------* * [ if (cond) ] .-------* * |
|
|
|
1443 | | | | | |
|
|
|
1444 | latch | | latch |
|
|
|
1445 | | | | | |
|
|
|
1446 | '------------' | '------------'
|
|
|
1447 '------------------------. .-----------'
|
|
|
1448 loop1 | | loop2
|
|
|
1449 v v
|
|
|
1450 exits
|
|
|
1451
|
|
|
1452 In the graph, loop1 represents the part derived from original one, and
|
|
|
1453 loop2 is duplicated using loop_version (), which corresponds to the part
|
|
|
1454 of original one being splitted out. In original latch edge of loop1, we
|
|
|
1455 insert a new conditional statement duplicated from the semi-invariant cond,
|
|
|
1456 and one of its branch goes back to loop1 header as a latch edge, and the
|
|
|
1457 other branch goes to loop2 pre-header as an entry edge. And also in loop2,
|
|
|
1458 we abandon the variant branch of the conditional statement by setting a
|
|
|
1459 constant bool condition, based on which branch is semi-invariant. */
|
|
|
1460
|
|
|
1461 static bool
|
|
|
1462 do_split_loop_on_cond (struct loop *loop1, edge invar_branch)
|
|
|
1463 {
|
|
|
1464 basic_block cond_bb = invar_branch->src;
|
|
|
1465 bool true_invar = !!(invar_branch->flags & EDGE_TRUE_VALUE);
|
|
|
1466 gcond *cond = as_a <gcond *> (last_stmt (cond_bb));
|
|
|
1467
|
|
|
1468 gcc_assert (cond_bb->loop_father == loop1);
|
|
|
1469
|
|
|
1470 if (dump_enabled_p ())
|
|
|
1471 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
|
|
|
1472 "loop split on semi-invariant condition at %s branch\n",
|
|
|
1473 true_invar ? "true" : "false");
|
|
|
1474
|
|
|
1475 initialize_original_copy_tables ();
|
|
|
1476
|
|
|
1477 struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL,
|
|
|
1478 profile_probability::always (),
|
|
|
1479 profile_probability::never (),
|
|
|
1480 profile_probability::always (),
|
|
|
1481 profile_probability::always (),
|
|
|
1482 true);
|
|
|
1483 if (!loop2)
|
|
|
1484 {
|
|
|
1485 free_original_copy_tables ();
|
|
|
1486 return false;
|
|
|
1487 }
|
|
|
1488
|
|
|
1489 basic_block cond_bb_copy = get_bb_copy (cond_bb);
|
|
|
1490 gcond *cond_copy = as_a<gcond *> (last_stmt (cond_bb_copy));
|
|
|
1491
|
|
|
1492 /* Replace the condition in loop2 with a bool constant to let PassManager
|
|
|
1493 remove the variant branch after current pass completes. */
|
|
|
1494 if (true_invar)
|
|
|
1495 gimple_cond_make_true (cond_copy);
|
|
|
1496 else
|
|
|
1497 gimple_cond_make_false (cond_copy);
|
|
|
1498
|
|
|
1499 update_stmt (cond_copy);
|
|
|
1500
|
|
|
1501 /* Insert a new conditional statement on latch edge of loop1, its condition
|
|
|
1502 is duplicated from the semi-invariant. This statement acts as a switch
|
|
|
1503 to transfer execution from loop1 to loop2, when loop1 enters into
|
|
|
1504 invariant state. */
|
|
|
1505 basic_block latch_bb = split_edge (loop_latch_edge (loop1));
|
|
|
1506 basic_block break_bb = split_edge (single_pred_edge (latch_bb));
|
|
|
1507 gimple *break_cond = gimple_build_cond (gimple_cond_code(cond),
|
|
|
1508 gimple_cond_lhs (cond),
|
|
|
1509 gimple_cond_rhs (cond),
|
|
|
1510 NULL_TREE, NULL_TREE);
|
|
|
1511
|
|
|
1512 gimple_stmt_iterator gsi = gsi_last_bb (break_bb);
|
|
|
1513 gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT);
|
|
|
1514
|
|
|
1515 edge to_loop1 = single_succ_edge (break_bb);
|
|
|
1516 edge to_loop2 = make_edge (break_bb, loop_preheader_edge (loop2)->src, 0);
|
|
|
1517
|
|
|
1518 to_loop1->flags &= ~EDGE_FALLTHRU;
|
|
|
1519 to_loop1->flags |= true_invar ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE;
|
|
|
1520 to_loop2->flags |= true_invar ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE;
|
|
|
1521
|
|
|
1522 update_ssa (TODO_update_ssa);
|
|
|
1523
|
|
|
1524 /* Due to introduction of a control flow edge from loop1 latch to loop2
|
|
|
1525 pre-header, we should update PHIs in loop2 to reflect this connection
|
|
|
1526 between loop1 and loop2. */
|
|
|
1527 connect_loop_phis (loop1, loop2, to_loop2);
|
|
|
1528
|
|
|
1529 free_original_copy_tables ();
|
|
|
1530
|
|
|
1531 rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1);
|
|
|
1532
|
|
|
1533 return true;
|
|
|
1534 }
|
|
|
1535
|
|
|
1536 /* Traverse all conditional statements in LOOP, to find out a good candidate
|
|
|
1537 upon which we can do loop split. */
|
|
|
1538
|
|
|
1539 static bool
|
|
|
1540 split_loop_on_cond (struct loop *loop)
|
|
|
1541 {
|
|
|
1542 split_info *info = new split_info ();
|
|
|
1543 basic_block *bbs = info->bbs = get_loop_body (loop);
|
|
|
1544 bool do_split = false;
|
|
|
1545
|
|
|
1546 /* Allocate an area to keep temporary info, and associate its address
|
|
|
1547 with loop aux field. */
|
|
|
1548 loop->aux = info;
|
|
|
1549
|
|
|
1550 for (unsigned i = 0; i < loop->num_nodes; i++)
|
|
|
1551 bbs[i]->aux = NULL;
|
|
|
1552
|
|
|
1553 for (unsigned i = 0; i < loop->num_nodes; i++)
|
|
|
1554 {
|
|
|
1555 basic_block bb = bbs[i];
|
|
|
1556
|
|
|
1557 /* We only consider conditional statement, which be executed at most once
|
|
|
1558 in each iteration of the loop. So skip statements in inner loops. */
|
|
|
1559 if ((bb->loop_father != loop) || (bb->flags & BB_IRREDUCIBLE_LOOP))
|
|
|
1560 continue;
|
|
|
1561
|
|
|
1562 /* Actually this check is not a must constraint. With it, we can ensure
|
|
|
1563 conditional statement will always be executed in each iteration. */
|
|
|
1564 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
|
|
|
1565 continue;
|
|
|
1566
|
|
|
1567 gimple *last = last_stmt (bb);
|
|
|
1568
|
|
|
1569 if (!last || gimple_code (last) != GIMPLE_COND)
|
|
|
1570 continue;
|
|
|
1571
|
|
|
1572 gcond *cond = as_a <gcond *> (last);
|
|
|
1573 edge branch_edge = get_cond_branch_to_split_loop (loop, cond);
|
|
|
1574
|
|
|
1575 if (branch_edge)
|
|
|
1576 {
|
|
|
1577 do_split_loop_on_cond (loop, branch_edge);
|
|
|
1578 do_split = true;
|
|
|
1579 break;
|
|
|
1580 }
|
|
|
1581 }
|
|
|
1582
|
|
|
1583 delete info;
|
|
|
1584 loop->aux = NULL;
|
|
|
1585
|
|
|
1586 return do_split;
|
|
|
1587 }
|
|
|
1588
|
|
111
|
1589 /* Main entry point. Perform loop splitting on all suitable loops. */
|
|
|
1590
|
|
|
1591 static unsigned int
|
|
|
1592 tree_ssa_split_loops (void)
|
|
|
1593 {
|
|
145
|
1594 class loop *loop;
|
|
111
|
1595 bool changed = false;
|
|
|
1596
|
|
|
1597 gcc_assert (scev_initialized_p ());
|
|
145
|
1598
|
|
|
1599 calculate_dominance_info (CDI_POST_DOMINATORS);
|
|
|
1600
|
|
111
|
1601 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
|
|
|
1602 loop->aux = NULL;
|
|
|
1603
|
|
|
1604 /* Go through all loops starting from innermost. */
|
|
|
1605 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
|
|
|
1606 {
|
|
|
1607 if (loop->aux)
|
|
|
1608 {
|
|
|
1609 /* If any of our inner loops was split, don't split us,
|
|
|
1610 and mark our containing loop as having had splits as well. */
|
|
|
1611 loop_outer (loop)->aux = loop;
|
|
|
1612 continue;
|
|
|
1613 }
|
|
|
1614
|
|
145
|
1615 if (optimize_loop_for_size_p (loop))
|
|
|
1616 continue;
|
|
|
1617
|
|
|
1618 if (split_loop (loop) || split_loop_on_cond (loop))
|
|
111
|
1619 {
|
|
145
|
1620 /* Mark our containing loop as having had some split inner loops. */
|
|
|
1621 loop_outer (loop)->aux = loop;
|
|
|
1622 changed = true;
|
|
111
|
1623 }
|
|
|
1624 }
|
|
|
1625
|
|
|
1626 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
|
|
|
1627 loop->aux = NULL;
|
|
|
1628
|
|
145
|
1629 clear_aux_for_blocks ();
|
|
|
1630
|
|
|
1631 free_dominance_info (CDI_POST_DOMINATORS);
|
|
|
1632
|
|
111
|
1633 if (changed)
|
|
|
1634 return TODO_cleanup_cfg;
|
|
|
1635 return 0;
|
|
|
1636 }
|
|
|
1637
|
|
|
1638 /* Loop splitting pass. */
|
|
|
1639
|
|
|
1640 namespace {
|
|
|
1641
|
|
|
1642 const pass_data pass_data_loop_split =
|
|
|
1643 {
|
|
|
1644 GIMPLE_PASS, /* type */
|
|
|
1645 "lsplit", /* name */
|
|
|
1646 OPTGROUP_LOOP, /* optinfo_flags */
|
|
|
1647 TV_LOOP_SPLIT, /* tv_id */
|
|
|
1648 PROP_cfg, /* properties_required */
|
|
|
1649 0, /* properties_provided */
|
|
|
1650 0, /* properties_destroyed */
|
|
|
1651 0, /* todo_flags_start */
|
|
|
1652 0, /* todo_flags_finish */
|
|
|
1653 };
|
|
|
1654
|
|
|
1655 class pass_loop_split : public gimple_opt_pass
|
|
|
1656 {
|
|
|
1657 public:
|
|
|
1658 pass_loop_split (gcc::context *ctxt)
|
|
|
1659 : gimple_opt_pass (pass_data_loop_split, ctxt)
|
|
|
1660 {}
|
|
|
1661
|
|
|
1662 /* opt_pass methods: */
|
|
|
1663 virtual bool gate (function *) { return flag_split_loops != 0; }
|
|
|
1664 virtual unsigned int execute (function *);
|
|
|
1665
|
|
|
1666 }; // class pass_loop_split
|
|
|
1667
|
|
|
1668 unsigned int
|
|
|
1669 pass_loop_split::execute (function *fun)
|
|
|
1670 {
|
|
|
1671 if (number_of_loops (fun) <= 1)
|
|
|
1672 return 0;
|
|
|
1673
|
|
|
1674 return tree_ssa_split_loops ();
|
|
|
1675 }
|
|
|
1676
|
|
|
1677 } // anon namespace
|
|
|
1678
|
|
|
1679 gimple_opt_pass *
|
|
|
1680 make_pass_loop_split (gcc::context *ctxt)
|
|
|
1681 {
|
|
|
1682 return new pass_loop_split (ctxt);
|
|
|
1683 }
|
