gcc/ChangeLog:
[official-gcc.git] / gcc / gimple-loop-jam.c
blob2ecd1bb5a7c86c19f00bfea70453454296ab2bd6
1 /* Loop unroll-and-jam.
2 Copyright (C) 2017-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "params.h"
24 #include "tree-pass.h"
25 #include "backend.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "ssa.h"
29 #include "fold-const.h"
30 #include "tree-cfg.h"
31 #include "tree-ssa.h"
32 #include "tree-ssa-loop-niter.h"
33 #include "tree-ssa-loop.h"
34 #include "tree-ssa-loop-manip.h"
35 #include "cfgloop.h"
36 #include "tree-scalar-evolution.h"
37 #include "gimple-iterator.h"
38 #include "cfghooks.h"
39 #include "tree-data-ref.h"
40 #include "tree-ssa-loop-ivopts.h"
41 #include "tree-vectorizer.h"
43 /* Unroll and Jam transformation
45 This is a combination of two transformations, where the second
46 is not always valid. It's applicable if a loop nest has redundancies
47 over the iterations of an outer loop while not having that with
48 an inner loop.
50 Given this nest:
51 for (i) {
52 for (j) {
53 B(i,j)
57 first unroll:
58 for (i by 2) {
59 for (j) {
60 B(i,j)
62 for (j) {
63 B(i+1,j)
67 then fuse the two adjacent inner loops resulting from that:
68 for (i by 2) {
69 for (j) {
70 B(i,j)
71 B(i+1,j)
75 As the order of evaluations of the body B changes this is valid
76 only in certain situations: all distance vectors need to be forward.
77 Additionally if there are multiple induction variables than just
78 a counting control IV (j above) we can also deal with some situations.
80 The validity is checked by unroll_jam_possible_p, and the data-dep
81 testing below.
83 A trivial example where the fusion is wrong would be when
84 B(i,j) == x[j-1] = x[j];
85 for (i by 2) {
86 for (j) {
87 x[j-1] = x[j];
89 for (j) {
90 x[j-1] = x[j];
92 } effect: move content to front by two elements
93 -->
94 for (i by 2) {
95 for (j) {
96 x[j-1] = x[j];
97 x[j-1] = x[j];
99 } effect: move content to front by one element
102 /* Modify the loop tree for the fact that all code once belonging
103 to the OLD loop or the outer loop of OLD now is inside LOOP. */
105 static void
106 merge_loop_tree (struct loop *loop, struct loop *old)
108 basic_block *bbs;
109 int i, n;
110 struct loop *subloop;
111 edge e;
112 edge_iterator ei;
114 /* Find its nodes. */
115 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
116 n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
118 for (i = 0; i < n; i++)
120 /* If the block was direct child of OLD loop it's now part
121 of LOOP. If it was outside OLD, then it moved into LOOP
122 as well. This avoids changing the loop father for BBs
123 in inner loops of OLD. */
124 if (bbs[i]->loop_father == old
125 || loop_depth (bbs[i]->loop_father) < loop_depth (old))
127 remove_bb_from_loops (bbs[i]);
128 add_bb_to_loop (bbs[i], loop);
129 continue;
132 /* If we find a direct subloop of OLD, move it to LOOP. */
133 subloop = bbs[i]->loop_father;
134 if (loop_outer (subloop) == old && subloop->header == bbs[i])
136 flow_loop_tree_node_remove (subloop);
137 flow_loop_tree_node_add (loop, subloop);
141 /* Update the information about loop exit edges. */
142 for (i = 0; i < n; i++)
144 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
146 rescan_loop_exit (e, false, false);
150 loop->num_nodes = n;
152 free (bbs);
155 /* BB is part of the outer loop of an unroll-and-jam situation.
156 Check if any statements therein would prevent the transformation. */
158 static bool
159 bb_prevents_fusion_p (basic_block bb)
161 gimple_stmt_iterator gsi;
162 /* BB is duplicated by outer unrolling and then all N-1 first copies
163 move into the body of the fused inner loop. If BB exits the outer loop
164 the last copy still doess so, and the first N-1 copies are cancelled
165 by loop unrolling, so also after fusion it's the exit block.
166 But there might be other reasons that prevent fusion:
167 * stores or unknown side-effects prevent fusion
168 * loads don't
169 * computations into SSA names: these aren't problematic. Their
170 result will be unused on the exit edges of the first N-1 copies
171 (those aren't taken after unrolling). If they are used on the
172 other edge (the one leading to the outer latch block) they are
173 loop-carried (on the outer loop) and the Nth copy of BB will
174 compute them again (i.e. the first N-1 copies will be dead). */
175 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
177 gimple *g = gsi_stmt (gsi);
178 if (gimple_vdef (g) || gimple_has_side_effects (g))
179 return true;
181 return false;
184 /* Given an inner loop LOOP (of some OUTER loop) determine if
185 we can safely fuse copies of it (generated by outer unrolling).
186 If so return true, otherwise return false. */
188 static bool
189 unroll_jam_possible_p (struct loop *outer, struct loop *loop)
191 basic_block *bbs;
192 int i, n;
193 struct tree_niter_desc niter;
195 /* When fusing the loops we skip the latch block
196 of the first one, so it mustn't have any effects to
197 preserve. */
198 if (!empty_block_p (loop->latch))
199 return false;
201 if (!single_exit (loop))
202 return false;
204 /* We need a perfect nest. Quick check for adjacent inner loops. */
205 if (outer->inner != loop || loop->next)
206 return false;
208 /* Prevent head-controlled inner loops, that we usually have.
209 The guard block would need to be accepted
210 (invariant condition either entering or skipping the loop),
211 without also accepting arbitrary control flow. When unswitching
212 ran before us (as with -O3) this won't be a problem because its
213 outer loop unswitching will have moved out the invariant condition.
215 If we do that we need to extend fuse_loops() to cope with this
216 by threading through the (still invariant) copied condition
217 between the two loop copies. */
218 if (!dominated_by_p (CDI_DOMINATORS, outer->latch, loop->header))
219 return false;
221 /* The number of iterations of the inner loop must be loop invariant
222 with respect to the outer loop. */
223 if (!number_of_iterations_exit (loop, single_exit (loop), &niter,
224 false, true)
225 || niter.cmp == ERROR_MARK
226 || !integer_zerop (niter.may_be_zero)
227 || !expr_invariant_in_loop_p (outer, niter.niter))
228 return false;
230 /* And check blocks belonging to just outer loop. */
231 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
232 n = get_loop_body_with_size (outer, bbs, n_basic_blocks_for_fn (cfun));
234 for (i = 0; i < n; i++)
235 if (bbs[i]->loop_father == outer && bb_prevents_fusion_p (bbs[i]))
236 break;
237 free (bbs);
238 if (i != n)
239 return false;
241 /* For now we can safely fuse copies of LOOP only if all
242 loop carried variables are inductions (or the virtual op).
244 We could handle reductions as well (the initial value in the second
245 body would be the after-iter value of the first body) if it's over
246 an associative and commutative operation. We wouldn't
247 be able to handle unknown cycles. */
248 gphi_iterator psi;
249 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
251 affine_iv iv;
252 tree op = gimple_phi_result (psi.phi ());
254 if (virtual_operand_p (op))
255 continue;
256 if (!simple_iv (loop, loop, op, &iv, true))
257 return false;
258 /* The inductions must be regular, loop invariant step and initial
259 value. */
260 if (!expr_invariant_in_loop_p (outer, iv.step)
261 || !expr_invariant_in_loop_p (outer, iv.base))
262 return false;
263 /* XXX With more effort we could also be able to deal with inductions
264 where the initial value is loop variant but a simple IV in the
265 outer loop. The initial value for the second body would be
266 the original initial value plus iv.base.step. The next value
267 for the fused loop would be the original next value of the first
268 copy, _not_ the next value of the second body. */
271 return true;
274 /* Fuse LOOP with all further neighbors. The loops are expected to
275 be in appropriate form. */
277 static void
278 fuse_loops (struct loop *loop)
280 struct loop *next = loop->next;
282 while (next)
284 edge e;
286 remove_branch (single_pred_edge (loop->latch));
287 /* Make delete_basic_block not fiddle with the loop structure. */
288 basic_block oldlatch = loop->latch;
289 loop->latch = NULL;
290 delete_basic_block (oldlatch);
291 e = redirect_edge_and_branch (loop_latch_edge (next),
292 loop->header);
293 loop->latch = e->src;
294 flush_pending_stmts (e);
296 gcc_assert (EDGE_COUNT (next->header->preds) == 1);
298 /* The PHI nodes of the second body (single-argument now)
299 need adjustments to use the right values: either directly
300 the value of the corresponding PHI in the first copy or
301 the one leaving the first body which unrolling did for us.
303 See also unroll_jam_possible_p() for further possibilities. */
304 gphi_iterator psi_first, psi_second;
305 e = single_pred_edge (next->header);
306 for (psi_first = gsi_start_phis (loop->header),
307 psi_second = gsi_start_phis (next->header);
308 !gsi_end_p (psi_first);
309 gsi_next (&psi_first), gsi_next (&psi_second))
311 gphi *phi_first = psi_first.phi ();
312 gphi *phi_second = psi_second.phi ();
313 tree firstop = gimple_phi_result (phi_first);
314 /* The virtual operand is correct already as it's
315 always live at exit, hence has a LCSSA node and outer
316 loop unrolling updated SSA form. */
317 if (virtual_operand_p (firstop))
318 continue;
320 /* Due to unroll_jam_possible_p() we know that this is
321 an induction. The second body goes over the same
322 iteration space. */
323 add_phi_arg (phi_second, firstop, e,
324 gimple_location (phi_first));
326 gcc_assert (gsi_end_p (psi_second));
328 merge_loop_tree (loop, next);
329 gcc_assert (!next->num_nodes);
330 struct loop *ln = next->next;
331 delete_loop (next);
332 next = ln;
334 rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop);
337 /* Returns true if the distance in DDR can be determined and adjusts
338 the unroll factor in *UNROLL to make unrolling valid for that distance.
339 Otherwise return false.
341 If this data dep can lead to a removed memory reference, increment
342 *REMOVED and adjust *PROFIT_UNROLL to be the necessary unroll factor
343 for this to happen. */
345 static bool
346 adjust_unroll_factor (struct data_dependence_relation *ddr,
347 unsigned *unroll, unsigned *profit_unroll,
348 unsigned *removed)
350 bool ret = false;
351 if (DDR_ARE_DEPENDENT (ddr) != chrec_known)
353 if (DDR_NUM_DIST_VECTS (ddr) == 0)
354 return false;
355 unsigned i;
356 lambda_vector dist_v;
357 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
359 /* A distance (a,b) is at worst transformed into (a/N,b) by the
360 unrolling (factor N), so the transformation is valid if
361 a >= N, or b > 0, or b is zero and a > 0. Otherwise the unroll
362 factor needs to be limited so that the first condition holds.
363 That may limit the factor down to zero in the worst case. */
364 int dist = dist_v[0];
365 if (dist < 0)
366 gcc_unreachable ();
367 else if ((unsigned)dist >= *unroll)
369 else if (lambda_vector_lexico_pos (dist_v + 1, DDR_NB_LOOPS (ddr) - 1)
370 || (lambda_vector_zerop (dist_v + 1, DDR_NB_LOOPS (ddr) - 1)
371 && dist > 0))
373 else
374 *unroll = dist;
376 /* With a distance (a,0) it's always profitable to unroll-and-jam
377 (by a+1), because one memory reference will go away. With
378 (a,b) and b != 0 that's less clear. We will increase the
379 number of streams without lowering the number of mem refs.
380 So for now only handle the first situation. */
381 if (lambda_vector_zerop (dist_v + 1, DDR_NB_LOOPS (ddr) - 1))
383 *profit_unroll = MAX (*profit_unroll, (unsigned)dist + 1);
384 (*removed)++;
387 ret = true;
390 return ret;
393 /* Main entry point for the unroll-and-jam transformation
394 described above. */
396 static unsigned int
397 tree_loop_unroll_and_jam (void)
399 struct loop *loop;
400 bool changed = false;
402 gcc_assert (scev_initialized_p ());
404 /* Go through all innermost loops. */
405 FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
407 struct loop *outer = loop_outer (loop);
409 if (loop_depth (loop) < 2
410 || optimize_loop_nest_for_size_p (outer))
411 continue;
413 if (!unroll_jam_possible_p (outer, loop))
414 continue;
416 vec<data_reference_p> datarefs;
417 vec<ddr_p> dependences;
418 unsigned unroll_factor, profit_unroll, removed;
419 struct tree_niter_desc desc;
420 bool unroll = false;
422 auto_vec<loop_p, 3> loop_nest;
423 dependences.create (10);
424 datarefs.create (10);
425 if (!compute_data_dependences_for_loop (outer, true, &loop_nest,
426 &datarefs, &dependences))
428 if (dump_file && (dump_flags & TDF_DETAILS))
429 fprintf (dump_file, "Cannot analyze data dependencies\n");
430 free_data_refs (datarefs);
431 free_dependence_relations (dependences);
432 return false;
434 if (!datarefs.length ())
435 continue;
437 if (dump_file && (dump_flags & TDF_DETAILS))
438 dump_data_dependence_relations (dump_file, dependences);
440 unroll_factor = (unsigned)-1;
441 profit_unroll = 1;
442 removed = 0;
444 /* Check all dependencies. */
445 unsigned i;
446 struct data_dependence_relation *ddr;
447 FOR_EACH_VEC_ELT (dependences, i, ddr)
449 struct data_reference *dra, *drb;
451 /* If the refs are independend there's nothing to do. */
452 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
453 continue;
454 dra = DDR_A (ddr);
455 drb = DDR_B (ddr);
456 /* Nothing interesting for the self dependencies. */
457 if (dra == drb)
458 continue;
460 /* Now check the distance vector, for determining a sensible
461 outer unroll factor, and for validity of merging the inner
462 loop copies. */
463 if (!adjust_unroll_factor (ddr, &unroll_factor, &profit_unroll,
464 &removed))
466 /* Couldn't get the distance vector. For two reads that's
467 harmless (we assume we should unroll). For at least
468 one write this means we can't check the dependence direction
469 and hence can't determine safety. */
471 if (DR_IS_WRITE (dra) || DR_IS_WRITE (drb))
473 unroll_factor = 0;
474 break;
479 /* We regard a user-specified minimum percentage of zero as a request
480 to ignore all profitability concerns and apply the transformation
481 always. */
482 if (!PARAM_VALUE (PARAM_UNROLL_JAM_MIN_PERCENT))
483 profit_unroll = 2;
484 else if (removed * 100 / datarefs.length ()
485 < (unsigned)PARAM_VALUE (PARAM_UNROLL_JAM_MIN_PERCENT))
486 profit_unroll = 1;
487 if (unroll_factor > profit_unroll)
488 unroll_factor = profit_unroll;
489 if (unroll_factor > (unsigned)PARAM_VALUE (PARAM_UNROLL_JAM_MAX_UNROLL))
490 unroll_factor = PARAM_VALUE (PARAM_UNROLL_JAM_MAX_UNROLL);
491 unroll = (unroll_factor > 1
492 && can_unroll_loop_p (outer, unroll_factor, &desc));
494 if (unroll)
496 if (dump_enabled_p ())
497 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS,
498 find_loop_location (outer),
499 "applying unroll and jam with factor %d\n",
500 unroll_factor);
501 initialize_original_copy_tables ();
502 tree_unroll_loop (outer, unroll_factor, single_dom_exit (outer),
503 &desc);
504 free_original_copy_tables ();
505 fuse_loops (outer->inner);
506 changed = true;
509 loop_nest.release ();
510 free_dependence_relations (dependences);
511 free_data_refs (datarefs);
514 if (changed)
516 scev_reset ();
517 free_dominance_info (CDI_DOMINATORS);
518 return TODO_cleanup_cfg;
520 return 0;
523 /* Pass boilerplate */
525 namespace {
527 const pass_data pass_data_loop_jam =
529 GIMPLE_PASS, /* type */
530 "unrolljam", /* name */
531 OPTGROUP_LOOP, /* optinfo_flags */
532 TV_LOOP_JAM, /* tv_id */
533 PROP_cfg, /* properties_required */
534 0, /* properties_provided */
535 0, /* properties_destroyed */
536 0, /* todo_flags_start */
537 0, /* todo_flags_finish */
540 class pass_loop_jam : public gimple_opt_pass
542 public:
543 pass_loop_jam (gcc::context *ctxt)
544 : gimple_opt_pass (pass_data_loop_jam, ctxt)
547 /* opt_pass methods: */
548 virtual bool gate (function *) { return flag_unroll_jam != 0; }
549 virtual unsigned int execute (function *);
553 unsigned int
554 pass_loop_jam::execute (function *fun)
556 if (number_of_loops (fun) <= 1)
557 return 0;
559 return tree_loop_unroll_and_jam ();
564 gimple_opt_pass *
565 make_pass_loop_jam (gcc::context *ctxt)
567 return new pass_loop_jam (ctxt);