annotate gcc/tree-ssa-loop-ivcanon.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
16
kono
parents: 14
diff changeset
1 /* Induction variable canonicalization and loop peeling.
kono
parents: 14
diff changeset
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
3
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 This file is part of GCC.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
5
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 GCC is free software; you can redistribute it and/or modify it
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 under the terms of the GNU General Public License as published by the
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 Free Software Foundation; either version 3, or (at your option) any
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 later version.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
10
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 GCC is distributed in the hope that it will be useful, but WITHOUT
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 for more details.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
15
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 You should have received a copy of the GNU General Public License
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 along with GCC; see the file COPYING3. If not see
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 <http://www.gnu.org/licenses/>. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 /* This pass detects the loops that iterate a constant number of times,
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
21 adds a canonical induction variable (step -1, tested against 0)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 and replaces the exit test. This enables the less powerful rtl
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 level analysis to use this information.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 This might spoil the code in some cases (by increasing register pressure).
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 Note that in the case the new variable is not needed, ivopts will get rid
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 of it, so it might only be a problem when there are no other linear induction
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 variables. In that case the created optimization possibilities are likely
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 to pay up.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
16
kono
parents: 14
diff changeset
31 We also perform
kono
parents: 14
diff changeset
32 - complete unrolling (or peeling) when the loops is rolling few enough
kono
parents: 14
diff changeset
33 times
kono
parents: 14
diff changeset
34 - simple peeling (i.e. copying few initial iterations prior the loop)
kono
parents: 14
diff changeset
35 when number of iteration estimate is known (typically by the profile
kono
parents: 14
diff changeset
36 info). */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 #include "config.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 #include "system.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 #include "coretypes.h"
16
kono
parents: 14
diff changeset
41 #include "backend.h"
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 #include "tree.h"
16
kono
parents: 14
diff changeset
43 #include "gimple.h"
kono
parents: 14
diff changeset
44 #include "cfghooks.h"
kono
parents: 14
diff changeset
45 #include "tree-pass.h"
kono
parents: 14
diff changeset
46 #include "ssa.h"
kono
parents: 14
diff changeset
47 #include "cgraph.h"
11
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
48 #include "gimple-pretty-print.h"
16
kono
parents: 14
diff changeset
49 #include "fold-const.h"
kono
parents: 14
diff changeset
50 #include "profile.h"
kono
parents: 14
diff changeset
51 #include "gimple-fold.h"
kono
parents: 14
diff changeset
52 #include "tree-eh.h"
kono
parents: 14
diff changeset
53 #include "gimple-iterator.h"
kono
parents: 14
diff changeset
54 #include "tree-cfg.h"
kono
parents: 14
diff changeset
55 #include "tree-ssa-loop-manip.h"
kono
parents: 14
diff changeset
56 #include "tree-ssa-loop-niter.h"
kono
parents: 14
diff changeset
57 #include "tree-ssa-loop.h"
kono
parents: 14
diff changeset
58 #include "tree-into-ssa.h"
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 #include "cfgloop.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 #include "tree-chrec.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 #include "tree-scalar-evolution.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 #include "params.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 #include "tree-inline.h"
16
kono
parents: 14
diff changeset
64 #include "tree-cfgcleanup.h"
kono
parents: 14
diff changeset
65 #include "builtins.h"
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
66
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 /* Specifies types of loops that may be unrolled. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 enum unroll_level
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 UL_SINGLE_ITER, /* Only loops that exit immediately in the first
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 iteration. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 of code size. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 UL_ALL /* All suitable loops. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 };
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 is the exit edge whose condition is replaced. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
80
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 static void
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 create_canonical_iv (struct loop *loop, edge exit, tree niter)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 edge in;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 tree type, var;
16
kono
parents: 14
diff changeset
86 gcond *cond;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 gimple_stmt_iterator incr_at;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 enum tree_code cmp;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 if (dump_file && (dump_flags & TDF_DETAILS))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 print_generic_expr (dump_file, niter, TDF_SLIM);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 fprintf (dump_file, " iterations.\n");
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
96
16
kono
parents: 14
diff changeset
97 cond = as_a <gcond *> (last_stmt (exit->src));
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 in = EDGE_SUCC (exit->src, 0);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 if (in == exit)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 in = EDGE_SUCC (exit->src, 1);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
101
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 /* Note that we do not need to worry about overflows, since
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 type of niter is always unsigned and all comparisons are
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 just for equality/nonequality -- i.e. everything works
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 with a modulo arithmetics. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
106
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 type = TREE_TYPE (niter);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 niter = fold_build2 (PLUS_EXPR, type,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 niter,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 build_int_cst (type, 1));
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
111 incr_at = gsi_last_bb (in->src);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 create_iv (niter,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 build_int_cst (type, -1),
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 NULL_TREE, loop,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 &incr_at, false, NULL, &var);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
116
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 gimple_cond_set_code (cond, cmp);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 gimple_cond_set_lhs (cond, var);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 gimple_cond_set_rhs (cond, build_int_cst (type, 0));
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 update_stmt (cond);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
123
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
124 /* Describe size of loop as detected by tree_estimate_loop_size. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
125 struct loop_size
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
126 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
127 /* Number of instructions in the loop. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
128 int overall;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
129
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
130 /* Number of instructions that will be likely optimized out in
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
131 peeled iterations of loop (i.e. computation based on induction
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
132 variable where induction variable starts at known constant.) */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
133 int eliminated_by_peeling;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
134
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
135 /* Same statistics for last iteration of loop: it is smaller because
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
136 instructions after exit are not executed. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
137 int last_iteration;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
138 int last_iteration_eliminated_by_peeling;
16
kono
parents: 14
diff changeset
139
kono
parents: 14
diff changeset
140 /* If some IV computation will become constant. */
kono
parents: 14
diff changeset
141 bool constant_iv;
kono
parents: 14
diff changeset
142
kono
parents: 14
diff changeset
143 /* Number of call stmts that are not a builtin and are pure or const
kono
parents: 14
diff changeset
144 present on the hot path. */
kono
parents: 14
diff changeset
145 int num_pure_calls_on_hot_path;
kono
parents: 14
diff changeset
146 /* Number of call stmts that are not a builtin and are not pure nor const
kono
parents: 14
diff changeset
147 present on the hot path. */
kono
parents: 14
diff changeset
148 int num_non_pure_calls_on_hot_path;
kono
parents: 14
diff changeset
149 /* Number of statements other than calls in the loop. */
kono
parents: 14
diff changeset
150 int non_call_stmts_on_hot_path;
kono
parents: 14
diff changeset
151 /* Number of branches seen on the hot path. */
kono
parents: 14
diff changeset
152 int num_branches_on_hot_path;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
153 };
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
154
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
155 /* Return true if OP in STMT will be constant after peeling LOOP. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
156
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
157 static bool
16
kono
parents: 14
diff changeset
158 constant_after_peeling (tree op, gimple *stmt, struct loop *loop)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
159 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
160 if (is_gimple_min_invariant (op))
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
161 return true;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
162
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
163 /* We can still fold accesses to constant arrays when index is known. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
164 if (TREE_CODE (op) != SSA_NAME)
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
165 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
166 tree base = op;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
167
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
168 /* First make fast look if we see constant array inside. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
169 while (handled_component_p (base))
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
170 base = TREE_OPERAND (base, 0);
16
kono
parents: 14
diff changeset
171 if ((DECL_P (base)
kono
parents: 14
diff changeset
172 && ctor_for_folding (base) != error_mark_node)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
173 || CONSTANT_CLASS_P (base))
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
174 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
175 /* If so, see if we understand all the indices. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
176 base = op;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
177 while (handled_component_p (base))
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
178 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
179 if (TREE_CODE (base) == ARRAY_REF
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
180 && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
181 return false;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
182 base = TREE_OPERAND (base, 0);
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
183 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
184 return true;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
185 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
186 return false;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
187 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
188
16
kono
parents: 14
diff changeset
189 /* Induction variables are constants when defined in loop. */
kono
parents: 14
diff changeset
190 if (loop_containing_stmt (stmt) != loop)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
191 return false;
16
kono
parents: 14
diff changeset
192 tree ev = analyze_scalar_evolution (loop, op);
kono
parents: 14
diff changeset
193 if (chrec_contains_undetermined (ev)
kono
parents: 14
diff changeset
194 || chrec_contains_symbols (ev))
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
195 return false;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
196 return true;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
197 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
198
16
kono
parents: 14
diff changeset
199 /* Computes an estimated number of insns in LOOP.
kono
parents: 14
diff changeset
200 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
kono
parents: 14
diff changeset
201 iteration of the loop.
kono
parents: 14
diff changeset
202 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
kono
parents: 14
diff changeset
203 of loop.
kono
parents: 14
diff changeset
204 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
kono
parents: 14
diff changeset
205 Stop estimating after UPPER_BOUND is met. Return true in this case. */
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
206
16
kono
parents: 14
diff changeset
207 static bool
kono
parents: 14
diff changeset
208 tree_estimate_loop_size (struct loop *loop, edge exit, edge edge_to_cancel,
kono
parents: 14
diff changeset
209 struct loop_size *size, int upper_bound)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
210 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
211 basic_block *body = get_loop_body (loop);
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
212 gimple_stmt_iterator gsi;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
213 unsigned int i;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
214 bool after_exit;
16
kono
parents: 14
diff changeset
215 vec<basic_block> path = get_loop_hot_path (loop);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
216
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
217 size->overall = 0;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
218 size->eliminated_by_peeling = 0;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
219 size->last_iteration = 0;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
220 size->last_iteration_eliminated_by_peeling = 0;
16
kono
parents: 14
diff changeset
221 size->num_pure_calls_on_hot_path = 0;
kono
parents: 14
diff changeset
222 size->num_non_pure_calls_on_hot_path = 0;
kono
parents: 14
diff changeset
223 size->non_call_stmts_on_hot_path = 0;
kono
parents: 14
diff changeset
224 size->num_branches_on_hot_path = 0;
kono
parents: 14
diff changeset
225 size->constant_iv = 0;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
226
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
227 if (dump_file && (dump_flags & TDF_DETAILS))
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
228 fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num);
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
229 for (i = 0; i < loop->num_nodes; i++)
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
230 {
16
kono
parents: 14
diff changeset
231 if (edge_to_cancel && body[i] != edge_to_cancel->src
kono
parents: 14
diff changeset
232 && dominated_by_p (CDI_DOMINATORS, body[i], edge_to_cancel->src))
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
233 after_exit = true;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
234 else
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
235 after_exit = false;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
236 if (dump_file && (dump_flags & TDF_DETAILS))
16
kono
parents: 14
diff changeset
237 fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index,
kono
parents: 14
diff changeset
238 after_exit);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
239
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
240 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
241 {
16
kono
parents: 14
diff changeset
242 gimple *stmt = gsi_stmt (gsi);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
243 int num = estimate_num_insns (stmt, &eni_size_weights);
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
244 bool likely_eliminated = false;
16
kono
parents: 14
diff changeset
245 bool likely_eliminated_last = false;
kono
parents: 14
diff changeset
246 bool likely_eliminated_peeled = false;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
247
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
248 if (dump_file && (dump_flags & TDF_DETAILS))
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
249 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
250 fprintf (dump_file, " size: %3i ", num);
16
kono
parents: 14
diff changeset
251 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
252 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
253
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
254 /* Look for reasons why we might optimize this stmt away. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
255
16
kono
parents: 14
diff changeset
256 if (!gimple_has_side_effects (stmt))
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
257 {
16
kono
parents: 14
diff changeset
258 /* Exit conditional. */
kono
parents: 14
diff changeset
259 if (exit && body[i] == exit->src
kono
parents: 14
diff changeset
260 && stmt == last_stmt (exit->src))
kono
parents: 14
diff changeset
261 {
kono
parents: 14
diff changeset
262 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
263 fprintf (dump_file, " Exit condition will be eliminated "
kono
parents: 14
diff changeset
264 "in peeled copies.\n");
kono
parents: 14
diff changeset
265 likely_eliminated_peeled = true;
kono
parents: 14
diff changeset
266 }
kono
parents: 14
diff changeset
267 if (edge_to_cancel && body[i] == edge_to_cancel->src
kono
parents: 14
diff changeset
268 && stmt == last_stmt (edge_to_cancel->src))
kono
parents: 14
diff changeset
269 {
kono
parents: 14
diff changeset
270 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
271 fprintf (dump_file, " Exit condition will be eliminated "
kono
parents: 14
diff changeset
272 "in last copy.\n");
kono
parents: 14
diff changeset
273 likely_eliminated_last = true;
kono
parents: 14
diff changeset
274 }
kono
parents: 14
diff changeset
275 /* Sets of IV variables */
kono
parents: 14
diff changeset
276 if (gimple_code (stmt) == GIMPLE_ASSIGN
kono
parents: 14
diff changeset
277 && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
kono
parents: 14
diff changeset
278 {
kono
parents: 14
diff changeset
279 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
280 fprintf (dump_file, " Induction variable computation will"
kono
parents: 14
diff changeset
281 " be folded away.\n");
kono
parents: 14
diff changeset
282 likely_eliminated = true;
kono
parents: 14
diff changeset
283 }
kono
parents: 14
diff changeset
284 /* Assignments of IV variables. */
kono
parents: 14
diff changeset
285 else if (gimple_code (stmt) == GIMPLE_ASSIGN
kono
parents: 14
diff changeset
286 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
kono
parents: 14
diff changeset
287 && constant_after_peeling (gimple_assign_rhs1 (stmt),
kono
parents: 14
diff changeset
288 stmt, loop)
kono
parents: 14
diff changeset
289 && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS
kono
parents: 14
diff changeset
290 || constant_after_peeling (gimple_assign_rhs2 (stmt),
kono
parents: 14
diff changeset
291 stmt, loop)))
kono
parents: 14
diff changeset
292 {
kono
parents: 14
diff changeset
293 size->constant_iv = true;
kono
parents: 14
diff changeset
294 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
295 fprintf (dump_file,
kono
parents: 14
diff changeset
296 " Constant expression will be folded away.\n");
kono
parents: 14
diff changeset
297 likely_eliminated = true;
kono
parents: 14
diff changeset
298 }
kono
parents: 14
diff changeset
299 /* Conditionals. */
kono
parents: 14
diff changeset
300 else if ((gimple_code (stmt) == GIMPLE_COND
kono
parents: 14
diff changeset
301 && constant_after_peeling (gimple_cond_lhs (stmt), stmt,
kono
parents: 14
diff changeset
302 loop)
kono
parents: 14
diff changeset
303 && constant_after_peeling (gimple_cond_rhs (stmt), stmt,
kono
parents: 14
diff changeset
304 loop)
kono
parents: 14
diff changeset
305 /* We don't simplify all constant compares so make sure
kono
parents: 14
diff changeset
306 they are not both constant already. See PR70288. */
kono
parents: 14
diff changeset
307 && (! is_gimple_min_invariant (gimple_cond_lhs (stmt))
kono
parents: 14
diff changeset
308 || ! is_gimple_min_invariant
kono
parents: 14
diff changeset
309 (gimple_cond_rhs (stmt))))
kono
parents: 14
diff changeset
310 || (gimple_code (stmt) == GIMPLE_SWITCH
kono
parents: 14
diff changeset
311 && constant_after_peeling (gimple_switch_index (
kono
parents: 14
diff changeset
312 as_a <gswitch *>
kono
parents: 14
diff changeset
313 (stmt)),
kono
parents: 14
diff changeset
314 stmt, loop)
kono
parents: 14
diff changeset
315 && ! is_gimple_min_invariant
kono
parents: 14
diff changeset
316 (gimple_switch_index
kono
parents: 14
diff changeset
317 (as_a <gswitch *> (stmt)))))
kono
parents: 14
diff changeset
318 {
kono
parents: 14
diff changeset
319 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
320 fprintf (dump_file, " Constant conditional.\n");
kono
parents: 14
diff changeset
321 likely_eliminated = true;
kono
parents: 14
diff changeset
322 }
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
323 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
324
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
325 size->overall += num;
16
kono
parents: 14
diff changeset
326 if (likely_eliminated || likely_eliminated_peeled)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
327 size->eliminated_by_peeling += num;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
328 if (!after_exit)
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
329 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
330 size->last_iteration += num;
16
kono
parents: 14
diff changeset
331 if (likely_eliminated || likely_eliminated_last)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
332 size->last_iteration_eliminated_by_peeling += num;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
333 }
16
kono
parents: 14
diff changeset
334 if ((size->overall * 3 / 2 - size->eliminated_by_peeling
kono
parents: 14
diff changeset
335 - size->last_iteration_eliminated_by_peeling) > upper_bound)
kono
parents: 14
diff changeset
336 {
kono
parents: 14
diff changeset
337 free (body);
kono
parents: 14
diff changeset
338 path.release ();
kono
parents: 14
diff changeset
339 return true;
kono
parents: 14
diff changeset
340 }
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
341 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
342 }
16
kono
parents: 14
diff changeset
343 while (path.length ())
kono
parents: 14
diff changeset
344 {
kono
parents: 14
diff changeset
345 basic_block bb = path.pop ();
kono
parents: 14
diff changeset
346 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
kono
parents: 14
diff changeset
347 {
kono
parents: 14
diff changeset
348 gimple *stmt = gsi_stmt (gsi);
kono
parents: 14
diff changeset
349 if (gimple_code (stmt) == GIMPLE_CALL
kono
parents: 14
diff changeset
350 && !gimple_inexpensive_call_p (as_a <gcall *> (stmt)))
kono
parents: 14
diff changeset
351 {
kono
parents: 14
diff changeset
352 int flags = gimple_call_flags (stmt);
kono
parents: 14
diff changeset
353 if (flags & (ECF_PURE | ECF_CONST))
kono
parents: 14
diff changeset
354 size->num_pure_calls_on_hot_path++;
kono
parents: 14
diff changeset
355 else
kono
parents: 14
diff changeset
356 size->num_non_pure_calls_on_hot_path++;
kono
parents: 14
diff changeset
357 size->num_branches_on_hot_path ++;
kono
parents: 14
diff changeset
358 }
kono
parents: 14
diff changeset
359 /* Count inexpensive calls as non-calls, because they will likely
kono
parents: 14
diff changeset
360 expand inline. */
kono
parents: 14
diff changeset
361 else if (gimple_code (stmt) != GIMPLE_DEBUG)
kono
parents: 14
diff changeset
362 size->non_call_stmts_on_hot_path++;
kono
parents: 14
diff changeset
363 if (((gimple_code (stmt) == GIMPLE_COND
kono
parents: 14
diff changeset
364 && (!constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
kono
parents: 14
diff changeset
365 || constant_after_peeling (gimple_cond_rhs (stmt), stmt,
kono
parents: 14
diff changeset
366 loop)))
kono
parents: 14
diff changeset
367 || (gimple_code (stmt) == GIMPLE_SWITCH
kono
parents: 14
diff changeset
368 && !constant_after_peeling (gimple_switch_index (
kono
parents: 14
diff changeset
369 as_a <gswitch *> (stmt)),
kono
parents: 14
diff changeset
370 stmt, loop)))
kono
parents: 14
diff changeset
371 && (!exit || bb != exit->src))
kono
parents: 14
diff changeset
372 size->num_branches_on_hot_path++;
kono
parents: 14
diff changeset
373 }
kono
parents: 14
diff changeset
374 }
kono
parents: 14
diff changeset
375 path.release ();
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
376 if (dump_file && (dump_flags & TDF_DETAILS))
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
377 fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall,
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
378 size->eliminated_by_peeling, size->last_iteration,
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
379 size->last_iteration_eliminated_by_peeling);
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
380
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
381 free (body);
16
kono
parents: 14
diff changeset
382 return false;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
383 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
384
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
385 /* Estimate number of insns of completely unrolled loop.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
386 It is (NUNROLL + 1) * size of loop body with taking into account
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
387 the fact that in last copy everything after exit conditional
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
388 is dead and that some instructions will be eliminated after
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
389 peeling.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
390
16
kono
parents: 14
diff changeset
391 Loop body is likely going to simplify further, this is difficult
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
392 to guess, we just decrease the result by 1/3. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
393
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
394 static unsigned HOST_WIDE_INT
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
395 estimated_unrolled_size (struct loop_size *size,
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
396 unsigned HOST_WIDE_INT nunroll)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
397 {
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
398 HOST_WIDE_INT unr_insns = ((nunroll)
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
399 * (HOST_WIDE_INT) (size->overall
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
400 - size->eliminated_by_peeling));
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
401 if (!nunroll)
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
402 unr_insns = 0;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
403 unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
404
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
405 unr_insns = unr_insns * 2 / 3;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
406 if (unr_insns <= 0)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
407 unr_insns = 1;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
408
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
409 return unr_insns;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
410 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
411
16
kono
parents: 14
diff changeset
412 /* Loop LOOP is known to not loop. See if there is an edge in the loop
kono
parents: 14
diff changeset
413 body that can be remove to make the loop to always exit and at
kono
parents: 14
diff changeset
414 the same time it does not make any code potentially executed
kono
parents: 14
diff changeset
415 during the last iteration dead.
kono
parents: 14
diff changeset
416
kono
parents: 14
diff changeset
417 After complete unrolling we still may get rid of the conditional
kono
parents: 14
diff changeset
418 on the exit in the last copy even if we have no idea what it does.
kono
parents: 14
diff changeset
419 This is quite common case for loops of form
kono
parents: 14
diff changeset
420
kono
parents: 14
diff changeset
421 int a[5];
kono
parents: 14
diff changeset
422 for (i=0;i<b;i++)
kono
parents: 14
diff changeset
423 a[i]=0;
kono
parents: 14
diff changeset
424
kono
parents: 14
diff changeset
425 Here we prove the loop to iterate 5 times but we do not know
kono
parents: 14
diff changeset
426 it from induction variable.
kono
parents: 14
diff changeset
427
kono
parents: 14
diff changeset
428 For now we handle only simple case where there is exit condition
kono
parents: 14
diff changeset
429 just before the latch block and the latch block contains no statements
kono
parents: 14
diff changeset
430 with side effect that may otherwise terminate the execution of loop
kono
parents: 14
diff changeset
431 (such as by EH or by terminating the program or longjmp).
kono
parents: 14
diff changeset
432
kono
parents: 14
diff changeset
433 In the general case we may want to cancel the paths leading to statements
kono
parents: 14
diff changeset
434 loop-niter identified as having undefined effect in the last iteration.
kono
parents: 14
diff changeset
435 The other cases are hopefully rare and will be cleaned up later. */
kono
parents: 14
diff changeset
436
kono
parents: 14
diff changeset
437 static edge
kono
parents: 14
diff changeset
438 loop_edge_to_cancel (struct loop *loop)
kono
parents: 14
diff changeset
439 {
kono
parents: 14
diff changeset
440 vec<edge> exits;
kono
parents: 14
diff changeset
441 unsigned i;
kono
parents: 14
diff changeset
442 edge edge_to_cancel;
kono
parents: 14
diff changeset
443 gimple_stmt_iterator gsi;
kono
parents: 14
diff changeset
444
kono
parents: 14
diff changeset
445 /* We want only one predecestor of the loop. */
kono
parents: 14
diff changeset
446 if (EDGE_COUNT (loop->latch->preds) > 1)
kono
parents: 14
diff changeset
447 return NULL;
kono
parents: 14
diff changeset
448
kono
parents: 14
diff changeset
449 exits = get_loop_exit_edges (loop);
kono
parents: 14
diff changeset
450
kono
parents: 14
diff changeset
451 FOR_EACH_VEC_ELT (exits, i, edge_to_cancel)
kono
parents: 14
diff changeset
452 {
kono
parents: 14
diff changeset
453 /* Find the other edge than the loop exit
kono
parents: 14
diff changeset
454 leaving the conditoinal. */
kono
parents: 14
diff changeset
455 if (EDGE_COUNT (edge_to_cancel->src->succs) != 2)
kono
parents: 14
diff changeset
456 continue;
kono
parents: 14
diff changeset
457 if (EDGE_SUCC (edge_to_cancel->src, 0) == edge_to_cancel)
kono
parents: 14
diff changeset
458 edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 1);
kono
parents: 14
diff changeset
459 else
kono
parents: 14
diff changeset
460 edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 0);
kono
parents: 14
diff changeset
461
kono
parents: 14
diff changeset
462 /* We only can handle conditionals. */
kono
parents: 14
diff changeset
463 if (!(edge_to_cancel->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
kono
parents: 14
diff changeset
464 continue;
kono
parents: 14
diff changeset
465
kono
parents: 14
diff changeset
466 /* We should never have conditionals in the loop latch. */
kono
parents: 14
diff changeset
467 gcc_assert (edge_to_cancel->dest != loop->header);
kono
parents: 14
diff changeset
468
kono
parents: 14
diff changeset
469 /* Check that it leads to loop latch. */
kono
parents: 14
diff changeset
470 if (edge_to_cancel->dest != loop->latch)
kono
parents: 14
diff changeset
471 continue;
kono
parents: 14
diff changeset
472
kono
parents: 14
diff changeset
473 exits.release ();
kono
parents: 14
diff changeset
474
kono
parents: 14
diff changeset
475 /* Verify that the code in loop latch does nothing that may end program
kono
parents: 14
diff changeset
476 execution without really reaching the exit. This may include
kono
parents: 14
diff changeset
477 non-pure/const function calls, EH statements, volatile ASMs etc. */
kono
parents: 14
diff changeset
478 for (gsi = gsi_start_bb (loop->latch); !gsi_end_p (gsi); gsi_next (&gsi))
kono
parents: 14
diff changeset
479 if (gimple_has_side_effects (gsi_stmt (gsi)))
kono
parents: 14
diff changeset
480 return NULL;
kono
parents: 14
diff changeset
481 return edge_to_cancel;
kono
parents: 14
diff changeset
482 }
kono
parents: 14
diff changeset
483 exits.release ();
kono
parents: 14
diff changeset
484 return NULL;
kono
parents: 14
diff changeset
485 }
kono
parents: 14
diff changeset
486
kono
parents: 14
diff changeset
487 /* Remove all tests for exits that are known to be taken after LOOP was
kono
parents: 14
diff changeset
488 peeled NPEELED times. Put gcc_unreachable before every statement
kono
parents: 14
diff changeset
489 known to not be executed. */
kono
parents: 14
diff changeset
490
kono
parents: 14
diff changeset
491 static bool
kono
parents: 14
diff changeset
492 remove_exits_and_undefined_stmts (struct loop *loop, unsigned int npeeled)
kono
parents: 14
diff changeset
493 {
kono
parents: 14
diff changeset
494 struct nb_iter_bound *elt;
kono
parents: 14
diff changeset
495 bool changed = false;
kono
parents: 14
diff changeset
496
kono
parents: 14
diff changeset
497 for (elt = loop->bounds; elt; elt = elt->next)
kono
parents: 14
diff changeset
498 {
kono
parents: 14
diff changeset
499 /* If statement is known to be undefined after peeling, turn it
kono
parents: 14
diff changeset
500 into unreachable (or trap when debugging experience is supposed
kono
parents: 14
diff changeset
501 to be good). */
kono
parents: 14
diff changeset
502 if (!elt->is_exit
kono
parents: 14
diff changeset
503 && wi::ltu_p (elt->bound, npeeled))
kono
parents: 14
diff changeset
504 {
kono
parents: 14
diff changeset
505 gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt);
kono
parents: 14
diff changeset
506 gcall *stmt = gimple_build_call
kono
parents: 14
diff changeset
507 (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
kono
parents: 14
diff changeset
508 gimple_set_location (stmt, gimple_location (elt->stmt));
kono
parents: 14
diff changeset
509 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
kono
parents: 14
diff changeset
510 split_block (gimple_bb (stmt), stmt);
kono
parents: 14
diff changeset
511 changed = true;
kono
parents: 14
diff changeset
512 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
513 {
kono
parents: 14
diff changeset
514 fprintf (dump_file, "Forced statement unreachable: ");
kono
parents: 14
diff changeset
515 print_gimple_stmt (dump_file, elt->stmt, 0);
kono
parents: 14
diff changeset
516 }
kono
parents: 14
diff changeset
517 }
kono
parents: 14
diff changeset
518 /* If we know the exit will be taken after peeling, update. */
kono
parents: 14
diff changeset
519 else if (elt->is_exit
kono
parents: 14
diff changeset
520 && wi::leu_p (elt->bound, npeeled))
kono
parents: 14
diff changeset
521 {
kono
parents: 14
diff changeset
522 basic_block bb = gimple_bb (elt->stmt);
kono
parents: 14
diff changeset
523 edge exit_edge = EDGE_SUCC (bb, 0);
kono
parents: 14
diff changeset
524
kono
parents: 14
diff changeset
525 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
526 {
kono
parents: 14
diff changeset
527 fprintf (dump_file, "Forced exit to be taken: ");
kono
parents: 14
diff changeset
528 print_gimple_stmt (dump_file, elt->stmt, 0);
kono
parents: 14
diff changeset
529 }
kono
parents: 14
diff changeset
530 if (!loop_exit_edge_p (loop, exit_edge))
kono
parents: 14
diff changeset
531 exit_edge = EDGE_SUCC (bb, 1);
kono
parents: 14
diff changeset
532 exit_edge->probability = profile_probability::always ();
kono
parents: 14
diff changeset
533 gcc_checking_assert (loop_exit_edge_p (loop, exit_edge));
kono
parents: 14
diff changeset
534 gcond *cond_stmt = as_a <gcond *> (elt->stmt);
kono
parents: 14
diff changeset
535 if (exit_edge->flags & EDGE_TRUE_VALUE)
kono
parents: 14
diff changeset
536 gimple_cond_make_true (cond_stmt);
kono
parents: 14
diff changeset
537 else
kono
parents: 14
diff changeset
538 gimple_cond_make_false (cond_stmt);
kono
parents: 14
diff changeset
539 update_stmt (cond_stmt);
kono
parents: 14
diff changeset
540 changed = true;
kono
parents: 14
diff changeset
541 }
kono
parents: 14
diff changeset
542 }
kono
parents: 14
diff changeset
543 return changed;
kono
parents: 14
diff changeset
544 }
kono
parents: 14
diff changeset
545
kono
parents: 14
diff changeset
546 /* Remove all exits that are known to be never taken because of the loop bound
kono
parents: 14
diff changeset
547 discovered. */
kono
parents: 14
diff changeset
548
kono
parents: 14
diff changeset
549 static bool
kono
parents: 14
diff changeset
550 remove_redundant_iv_tests (struct loop *loop)
kono
parents: 14
diff changeset
551 {
kono
parents: 14
diff changeset
552 struct nb_iter_bound *elt;
kono
parents: 14
diff changeset
553 bool changed = false;
kono
parents: 14
diff changeset
554
kono
parents: 14
diff changeset
555 if (!loop->any_upper_bound)
kono
parents: 14
diff changeset
556 return false;
kono
parents: 14
diff changeset
557 for (elt = loop->bounds; elt; elt = elt->next)
kono
parents: 14
diff changeset
558 {
kono
parents: 14
diff changeset
559 /* Exit is pointless if it won't be taken before loop reaches
kono
parents: 14
diff changeset
560 upper bound. */
kono
parents: 14
diff changeset
561 if (elt->is_exit && loop->any_upper_bound
kono
parents: 14
diff changeset
562 && wi::ltu_p (loop->nb_iterations_upper_bound, elt->bound))
kono
parents: 14
diff changeset
563 {
kono
parents: 14
diff changeset
564 basic_block bb = gimple_bb (elt->stmt);
kono
parents: 14
diff changeset
565 edge exit_edge = EDGE_SUCC (bb, 0);
kono
parents: 14
diff changeset
566 struct tree_niter_desc niter;
kono
parents: 14
diff changeset
567
kono
parents: 14
diff changeset
568 if (!loop_exit_edge_p (loop, exit_edge))
kono
parents: 14
diff changeset
569 exit_edge = EDGE_SUCC (bb, 1);
kono
parents: 14
diff changeset
570
kono
parents: 14
diff changeset
571 /* Only when we know the actual number of iterations, not
kono
parents: 14
diff changeset
572 just a bound, we can remove the exit. */
kono
parents: 14
diff changeset
573 if (!number_of_iterations_exit (loop, exit_edge,
kono
parents: 14
diff changeset
574 &niter, false, false)
kono
parents: 14
diff changeset
575 || !integer_onep (niter.assumptions)
kono
parents: 14
diff changeset
576 || !integer_zerop (niter.may_be_zero)
kono
parents: 14
diff changeset
577 || !niter.niter
kono
parents: 14
diff changeset
578 || TREE_CODE (niter.niter) != INTEGER_CST
kono
parents: 14
diff changeset
579 || !wi::ltu_p (loop->nb_iterations_upper_bound,
kono
parents: 14
diff changeset
580 wi::to_widest (niter.niter)))
kono
parents: 14
diff changeset
581 continue;
kono
parents: 14
diff changeset
582
kono
parents: 14
diff changeset
583 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
584 {
kono
parents: 14
diff changeset
585 fprintf (dump_file, "Removed pointless exit: ");
kono
parents: 14
diff changeset
586 print_gimple_stmt (dump_file, elt->stmt, 0);
kono
parents: 14
diff changeset
587 }
kono
parents: 14
diff changeset
588 gcond *cond_stmt = as_a <gcond *> (elt->stmt);
kono
parents: 14
diff changeset
589 if (exit_edge->flags & EDGE_TRUE_VALUE)
kono
parents: 14
diff changeset
590 gimple_cond_make_false (cond_stmt);
kono
parents: 14
diff changeset
591 else
kono
parents: 14
diff changeset
592 gimple_cond_make_true (cond_stmt);
kono
parents: 14
diff changeset
593 update_stmt (cond_stmt);
kono
parents: 14
diff changeset
594 changed = true;
kono
parents: 14
diff changeset
595 }
kono
parents: 14
diff changeset
596 }
kono
parents: 14
diff changeset
597 return changed;
kono
parents: 14
diff changeset
598 }
kono
parents: 14
diff changeset
599
kono
parents: 14
diff changeset
600 /* Stores loops that will be unlooped and edges that will be removed
kono
parents: 14
diff changeset
601 after we process whole loop tree. */
kono
parents: 14
diff changeset
602 static vec<loop_p> loops_to_unloop;
kono
parents: 14
diff changeset
603 static vec<int> loops_to_unloop_nunroll;
kono
parents: 14
diff changeset
604 static vec<edge> edges_to_remove;
kono
parents: 14
diff changeset
605 /* Stores loops that has been peeled. */
kono
parents: 14
diff changeset
606 static bitmap peeled_loops;
kono
parents: 14
diff changeset
607
kono
parents: 14
diff changeset
608 /* Cancel all fully unrolled loops by putting __builtin_unreachable
kono
parents: 14
diff changeset
609 on the latch edge.
kono
parents: 14
diff changeset
610 We do it after all unrolling since unlooping moves basic blocks
kono
parents: 14
diff changeset
611 across loop boundaries trashing loop closed SSA form as well
kono
parents: 14
diff changeset
612 as SCEV info needed to be intact during unrolling.
kono
parents: 14
diff changeset
613
kono
parents: 14
diff changeset
614 IRRED_INVALIDATED is used to bookkeep if information about
kono
parents: 14
diff changeset
615 irreducible regions may become invalid as a result
kono
parents: 14
diff changeset
616 of the transformation.
kono
parents: 14
diff changeset
617 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
kono
parents: 14
diff changeset
618 when we need to go into loop closed SSA form. */
kono
parents: 14
diff changeset
619
kono
parents: 14
diff changeset
620 static void
kono
parents: 14
diff changeset
621 unloop_loops (bitmap loop_closed_ssa_invalidated,
kono
parents: 14
diff changeset
622 bool *irred_invalidated)
kono
parents: 14
diff changeset
623 {
kono
parents: 14
diff changeset
624 while (loops_to_unloop.length ())
kono
parents: 14
diff changeset
625 {
kono
parents: 14
diff changeset
626 struct loop *loop = loops_to_unloop.pop ();
kono
parents: 14
diff changeset
627 int n_unroll = loops_to_unloop_nunroll.pop ();
kono
parents: 14
diff changeset
628 basic_block latch = loop->latch;
kono
parents: 14
diff changeset
629 edge latch_edge = loop_latch_edge (loop);
kono
parents: 14
diff changeset
630 int flags = latch_edge->flags;
kono
parents: 14
diff changeset
631 location_t locus = latch_edge->goto_locus;
kono
parents: 14
diff changeset
632 gcall *stmt;
kono
parents: 14
diff changeset
633 gimple_stmt_iterator gsi;
kono
parents: 14
diff changeset
634
kono
parents: 14
diff changeset
635 remove_exits_and_undefined_stmts (loop, n_unroll);
kono
parents: 14
diff changeset
636
kono
parents: 14
diff changeset
637 /* Unloop destroys the latch edge. */
kono
parents: 14
diff changeset
638 unloop (loop, irred_invalidated, loop_closed_ssa_invalidated);
kono
parents: 14
diff changeset
639
kono
parents: 14
diff changeset
640 /* Create new basic block for the latch edge destination and wire
kono
parents: 14
diff changeset
641 it in. */
kono
parents: 14
diff changeset
642 stmt = gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
kono
parents: 14
diff changeset
643 latch_edge = make_edge (latch, create_basic_block (NULL, NULL, latch), flags);
kono
parents: 14
diff changeset
644 latch_edge->probability = profile_probability::never ();
kono
parents: 14
diff changeset
645 latch_edge->flags |= flags;
kono
parents: 14
diff changeset
646 latch_edge->goto_locus = locus;
kono
parents: 14
diff changeset
647
kono
parents: 14
diff changeset
648 add_bb_to_loop (latch_edge->dest, current_loops->tree_root);
kono
parents: 14
diff changeset
649 latch_edge->dest->count = profile_count::zero ();
kono
parents: 14
diff changeset
650 latch_edge->dest->frequency = 0;
kono
parents: 14
diff changeset
651 set_immediate_dominator (CDI_DOMINATORS, latch_edge->dest, latch_edge->src);
kono
parents: 14
diff changeset
652
kono
parents: 14
diff changeset
653 gsi = gsi_start_bb (latch_edge->dest);
kono
parents: 14
diff changeset
654 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
kono
parents: 14
diff changeset
655 }
kono
parents: 14
diff changeset
656 loops_to_unloop.release ();
kono
parents: 14
diff changeset
657 loops_to_unloop_nunroll.release ();
kono
parents: 14
diff changeset
658
kono
parents: 14
diff changeset
659 /* Remove edges in peeled copies. */
kono
parents: 14
diff changeset
660 unsigned i;
kono
parents: 14
diff changeset
661 edge e;
kono
parents: 14
diff changeset
662 FOR_EACH_VEC_ELT (edges_to_remove, i, e)
kono
parents: 14
diff changeset
663 {
kono
parents: 14
diff changeset
664 bool ok = remove_path (e, irred_invalidated, loop_closed_ssa_invalidated);
kono
parents: 14
diff changeset
665 gcc_assert (ok);
kono
parents: 14
diff changeset
666 }
kono
parents: 14
diff changeset
667 edges_to_remove.release ();
kono
parents: 14
diff changeset
668 }
kono
parents: 14
diff changeset
669
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
670 /* Tries to unroll LOOP completely, i.e. NITER times.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
671 UL determines which loops we are allowed to unroll.
16
kono
parents: 14
diff changeset
672 EXIT is the exit of the loop that should be eliminated.
kono
parents: 14
diff changeset
673 MAXITER specfy bound on number of iterations, -1 if it is
kono
parents: 14
diff changeset
674 not known or too large for HOST_WIDE_INT. The location
kono
parents: 14
diff changeset
675 LOCUS corresponding to the loop is used when emitting
kono
parents: 14
diff changeset
676 a summary of the unroll to the dump file. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
677
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
678 static bool
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
679 try_unroll_loop_completely (struct loop *loop,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
680 edge exit, tree niter,
16
kono
parents: 14
diff changeset
681 enum unroll_level ul,
kono
parents: 14
diff changeset
682 HOST_WIDE_INT maxiter,
kono
parents: 14
diff changeset
683 location_t locus)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
684 {
16
kono
parents: 14
diff changeset
685 unsigned HOST_WIDE_INT n_unroll = 0, ninsns, unr_insns;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
686 struct loop_size size;
16
kono
parents: 14
diff changeset
687 bool n_unroll_found = false;
kono
parents: 14
diff changeset
688 edge edge_to_cancel = NULL;
kono
parents: 14
diff changeset
689 dump_flags_t report_flags = MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
690
16
kono
parents: 14
diff changeset
691 /* See if we proved number of iterations to be low constant.
kono
parents: 14
diff changeset
692
kono
parents: 14
diff changeset
693 EXIT is an edge that will be removed in all but last iteration of
kono
parents: 14
diff changeset
694 the loop.
kono
parents: 14
diff changeset
695
kono
parents: 14
diff changeset
696 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
kono
parents: 14
diff changeset
697 of the unrolled sequence and is expected to make the final loop not
kono
parents: 14
diff changeset
698 rolling.
kono
parents: 14
diff changeset
699
kono
parents: 14
diff changeset
700 If the number of execution of loop is determined by standard induction
kono
parents: 14
diff changeset
701 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
kono
parents: 14
diff changeset
702 from the iv test. */
kono
parents: 14
diff changeset
703 if (tree_fits_uhwi_p (niter))
kono
parents: 14
diff changeset
704 {
kono
parents: 14
diff changeset
705 n_unroll = tree_to_uhwi (niter);
kono
parents: 14
diff changeset
706 n_unroll_found = true;
kono
parents: 14
diff changeset
707 edge_to_cancel = EDGE_SUCC (exit->src, 0);
kono
parents: 14
diff changeset
708 if (edge_to_cancel == exit)
kono
parents: 14
diff changeset
709 edge_to_cancel = EDGE_SUCC (exit->src, 1);
kono
parents: 14
diff changeset
710 }
kono
parents: 14
diff changeset
711 /* We do not know the number of iterations and thus we can not eliminate
kono
parents: 14
diff changeset
712 the EXIT edge. */
kono
parents: 14
diff changeset
713 else
kono
parents: 14
diff changeset
714 exit = NULL;
kono
parents: 14
diff changeset
715
kono
parents: 14
diff changeset
716 /* See if we can improve our estimate by using recorded loop bounds. */
kono
parents: 14
diff changeset
717 if (maxiter >= 0
kono
parents: 14
diff changeset
718 && (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
kono
parents: 14
diff changeset
719 {
kono
parents: 14
diff changeset
720 n_unroll = maxiter;
kono
parents: 14
diff changeset
721 n_unroll_found = true;
kono
parents: 14
diff changeset
722 /* Loop terminates before the IV variable test, so we can not
kono
parents: 14
diff changeset
723 remove it in the last iteration. */
kono
parents: 14
diff changeset
724 edge_to_cancel = NULL;
kono
parents: 14
diff changeset
725 }
kono
parents: 14
diff changeset
726
kono
parents: 14
diff changeset
727 if (!n_unroll_found)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
728 return false;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
729
16
kono
parents: 14
diff changeset
730 if (n_unroll > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES))
kono
parents: 14
diff changeset
731 {
kono
parents: 14
diff changeset
732 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
733 fprintf (dump_file, "Not unrolling loop %d "
kono
parents: 14
diff changeset
734 "(--param max-completely-peel-times limit reached).\n",
kono
parents: 14
diff changeset
735 loop->num);
kono
parents: 14
diff changeset
736 return false;
kono
parents: 14
diff changeset
737 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
738
16
kono
parents: 14
diff changeset
739 if (!edge_to_cancel)
kono
parents: 14
diff changeset
740 edge_to_cancel = loop_edge_to_cancel (loop);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
741
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
742 if (n_unroll)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
743 {
16
kono
parents: 14
diff changeset
744 bool large;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
745 if (ul == UL_SINGLE_ITER)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
746 return false;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
747
16
kono
parents: 14
diff changeset
748 /* EXIT can be removed only if we are sure it passes first N_UNROLL
kono
parents: 14
diff changeset
749 iterations. */
kono
parents: 14
diff changeset
750 bool remove_exit = (exit && niter
kono
parents: 14
diff changeset
751 && TREE_CODE (niter) == INTEGER_CST
kono
parents: 14
diff changeset
752 && wi::leu_p (n_unroll, wi::to_widest (niter)));
kono
parents: 14
diff changeset
753
kono
parents: 14
diff changeset
754 large = tree_estimate_loop_size
kono
parents: 14
diff changeset
755 (loop, remove_exit ? exit : NULL, edge_to_cancel, &size,
kono
parents: 14
diff changeset
756 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS));
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
757 ninsns = size.overall;
16
kono
parents: 14
diff changeset
758 if (large)
kono
parents: 14
diff changeset
759 {
kono
parents: 14
diff changeset
760 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
761 fprintf (dump_file, "Not unrolling loop %d: it is too large.\n",
kono
parents: 14
diff changeset
762 loop->num);
kono
parents: 14
diff changeset
763 return false;
kono
parents: 14
diff changeset
764 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
765
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
766 unr_insns = estimated_unrolled_size (&size, n_unroll);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
767 if (dump_file && (dump_flags & TDF_DETAILS))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
768 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
769 fprintf (dump_file, " Loop size: %d\n", (int) ninsns);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
770 fprintf (dump_file, " Estimated size after unrolling: %d\n",
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
771 (int) unr_insns);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
772 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
773
16
kono
parents: 14
diff changeset
774 /* If the code is going to shrink, we don't need to be extra cautious
kono
parents: 14
diff changeset
775 on guessing if the unrolling is going to be profitable. */
kono
parents: 14
diff changeset
776 if (unr_insns
kono
parents: 14
diff changeset
777 /* If there is IV variable that will become constant, we save
kono
parents: 14
diff changeset
778 one instruction in the loop prologue we do not account
kono
parents: 14
diff changeset
779 otherwise. */
kono
parents: 14
diff changeset
780 <= ninsns + (size.constant_iv != false))
kono
parents: 14
diff changeset
781 ;
kono
parents: 14
diff changeset
782 /* We unroll only inner loops, because we do not consider it profitable
kono
parents: 14
diff changeset
783 otheriwse. We still can cancel loopback edge of not rolling loop;
kono
parents: 14
diff changeset
784 this is always a good idea. */
kono
parents: 14
diff changeset
785 else if (ul == UL_NO_GROWTH)
kono
parents: 14
diff changeset
786 {
kono
parents: 14
diff changeset
787 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
788 fprintf (dump_file, "Not unrolling loop %d: size would grow.\n",
kono
parents: 14
diff changeset
789 loop->num);
kono
parents: 14
diff changeset
790 return false;
kono
parents: 14
diff changeset
791 }
kono
parents: 14
diff changeset
792 /* Outer loops tend to be less interesting candidates for complete
kono
parents: 14
diff changeset
793 unrolling unless we can do a lot of propagation into the inner loop
kono
parents: 14
diff changeset
794 body. For now we disable outer loop unrolling when the code would
kono
parents: 14
diff changeset
795 grow. */
kono
parents: 14
diff changeset
796 else if (loop->inner)
kono
parents: 14
diff changeset
797 {
kono
parents: 14
diff changeset
798 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
799 fprintf (dump_file, "Not unrolling loop %d: "
kono
parents: 14
diff changeset
800 "it is not innermost and code would grow.\n",
kono
parents: 14
diff changeset
801 loop->num);
kono
parents: 14
diff changeset
802 return false;
kono
parents: 14
diff changeset
803 }
kono
parents: 14
diff changeset
804 /* If there is call on a hot path through the loop, then
kono
parents: 14
diff changeset
805 there is most probably not much to optimize. */
kono
parents: 14
diff changeset
806 else if (size.num_non_pure_calls_on_hot_path)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
807 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
808 if (dump_file && (dump_flags & TDF_DETAILS))
16
kono
parents: 14
diff changeset
809 fprintf (dump_file, "Not unrolling loop %d: "
kono
parents: 14
diff changeset
810 "contains call and code would grow.\n",
kono
parents: 14
diff changeset
811 loop->num);
kono
parents: 14
diff changeset
812 return false;
kono
parents: 14
diff changeset
813 }
kono
parents: 14
diff changeset
814 /* If there is pure/const call in the function, then we
kono
parents: 14
diff changeset
815 can still optimize the unrolled loop body if it contains
kono
parents: 14
diff changeset
816 some other interesting code than the calls and code
kono
parents: 14
diff changeset
817 storing or cumulating the return value. */
kono
parents: 14
diff changeset
818 else if (size.num_pure_calls_on_hot_path
kono
parents: 14
diff changeset
819 /* One IV increment, one test, one ivtmp store
kono
parents: 14
diff changeset
820 and one useful stmt. That is about minimal loop
kono
parents: 14
diff changeset
821 doing pure call. */
kono
parents: 14
diff changeset
822 && (size.non_call_stmts_on_hot_path
kono
parents: 14
diff changeset
823 <= 3 + size.num_pure_calls_on_hot_path))
kono
parents: 14
diff changeset
824 {
kono
parents: 14
diff changeset
825 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
826 fprintf (dump_file, "Not unrolling loop %d: "
kono
parents: 14
diff changeset
827 "contains just pure calls and code would grow.\n",
kono
parents: 14
diff changeset
828 loop->num);
kono
parents: 14
diff changeset
829 return false;
kono
parents: 14
diff changeset
830 }
kono
parents: 14
diff changeset
831 /* Complete unrolling is a major win when control flow is removed and
kono
parents: 14
diff changeset
832 one big basic block is created. If the loop contains control flow
kono
parents: 14
diff changeset
833 the optimization may still be a win because of eliminating the loop
kono
parents: 14
diff changeset
834 overhead but it also may blow the branch predictor tables.
kono
parents: 14
diff changeset
835 Limit number of branches on the hot path through the peeled
kono
parents: 14
diff changeset
836 sequence. */
kono
parents: 14
diff changeset
837 else if (size.num_branches_on_hot_path * (int)n_unroll
kono
parents: 14
diff changeset
838 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES))
kono
parents: 14
diff changeset
839 {
kono
parents: 14
diff changeset
840 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
841 fprintf (dump_file, "Not unrolling loop %d: "
kono
parents: 14
diff changeset
842 " number of branches on hot path in the unrolled sequence"
kono
parents: 14
diff changeset
843 " reach --param max-peel-branches limit.\n",
kono
parents: 14
diff changeset
844 loop->num);
kono
parents: 14
diff changeset
845 return false;
kono
parents: 14
diff changeset
846 }
kono
parents: 14
diff changeset
847 else if (unr_insns
kono
parents: 14
diff changeset
848 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
kono
parents: 14
diff changeset
849 {
kono
parents: 14
diff changeset
850 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
851 fprintf (dump_file, "Not unrolling loop %d: "
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
852 "(--param max-completely-peeled-insns limit reached).\n",
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
853 loop->num);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
854 return false;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
855 }
16
kono
parents: 14
diff changeset
856 if (!n_unroll)
kono
parents: 14
diff changeset
857 dump_printf_loc (report_flags, locus,
kono
parents: 14
diff changeset
858 "loop turned into non-loop; it never loops.\n");
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
859
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
860 initialize_original_copy_tables ();
16
kono
parents: 14
diff changeset
861 auto_sbitmap wont_exit (n_unroll + 1);
kono
parents: 14
diff changeset
862 if (exit && niter
kono
parents: 14
diff changeset
863 && TREE_CODE (niter) == INTEGER_CST
kono
parents: 14
diff changeset
864 && wi::leu_p (n_unroll, wi::to_widest (niter)))
kono
parents: 14
diff changeset
865 {
kono
parents: 14
diff changeset
866 bitmap_ones (wont_exit);
kono
parents: 14
diff changeset
867 if (wi::eq_p (wi::to_widest (niter), n_unroll)
kono
parents: 14
diff changeset
868 || edge_to_cancel)
kono
parents: 14
diff changeset
869 bitmap_clear_bit (wont_exit, 0);
kono
parents: 14
diff changeset
870 }
kono
parents: 14
diff changeset
871 else
kono
parents: 14
diff changeset
872 {
kono
parents: 14
diff changeset
873 exit = NULL;
kono
parents: 14
diff changeset
874 bitmap_clear (wont_exit);
kono
parents: 14
diff changeset
875 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
876
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
877 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
878 n_unroll, wont_exit,
16
kono
parents: 14
diff changeset
879 exit, &edges_to_remove,
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
880 DLTHE_FLAG_UPDATE_FREQ
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
881 | DLTHE_FLAG_COMPLETTE_PEEL))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
882 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
883 free_original_copy_tables ();
16
kono
parents: 14
diff changeset
884 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
885 fprintf (dump_file, "Failed to duplicate the loop\n");
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
886 return false;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
887 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
888
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
889 free_original_copy_tables ();
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
890 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
891
16
kono
parents: 14
diff changeset
892 /* Remove the conditional from the last copy of the loop. */
kono
parents: 14
diff changeset
893 if (edge_to_cancel)
kono
parents: 14
diff changeset
894 {
kono
parents: 14
diff changeset
895 gcond *cond = as_a <gcond *> (last_stmt (edge_to_cancel->src));
kono
parents: 14
diff changeset
896 force_edge_cold (edge_to_cancel, true);
kono
parents: 14
diff changeset
897 if (edge_to_cancel->flags & EDGE_TRUE_VALUE)
kono
parents: 14
diff changeset
898 gimple_cond_make_false (cond);
kono
parents: 14
diff changeset
899 else
kono
parents: 14
diff changeset
900 gimple_cond_make_true (cond);
kono
parents: 14
diff changeset
901 update_stmt (cond);
kono
parents: 14
diff changeset
902 /* Do not remove the path. Doing so may remove outer loop
kono
parents: 14
diff changeset
903 and confuse bookkeeping code in tree_unroll_loops_completelly. */
kono
parents: 14
diff changeset
904 }
kono
parents: 14
diff changeset
905
kono
parents: 14
diff changeset
906 /* Store the loop for later unlooping and exit removal. */
kono
parents: 14
diff changeset
907 loops_to_unloop.safe_push (loop);
kono
parents: 14
diff changeset
908 loops_to_unloop_nunroll.safe_push (n_unroll);
kono
parents: 14
diff changeset
909
kono
parents: 14
diff changeset
910 if (dump_enabled_p ())
kono
parents: 14
diff changeset
911 {
kono
parents: 14
diff changeset
912 if (!n_unroll)
kono
parents: 14
diff changeset
913 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
kono
parents: 14
diff changeset
914 "loop turned into non-loop; it never loops\n");
kono
parents: 14
diff changeset
915 else
kono
parents: 14
diff changeset
916 {
kono
parents: 14
diff changeset
917 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
kono
parents: 14
diff changeset
918 "loop with %d iterations completely unrolled",
kono
parents: 14
diff changeset
919 (int) (n_unroll + 1));
kono
parents: 14
diff changeset
920 if (loop->header->count.initialized_p ())
kono
parents: 14
diff changeset
921 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS,
kono
parents: 14
diff changeset
922 " (header execution count %d)",
kono
parents: 14
diff changeset
923 (int)loop->header->count.to_gcov_type ());
kono
parents: 14
diff changeset
924 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, "\n");
kono
parents: 14
diff changeset
925 }
kono
parents: 14
diff changeset
926 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
927
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
928 if (dump_file && (dump_flags & TDF_DETAILS))
16
kono
parents: 14
diff changeset
929 {
kono
parents: 14
diff changeset
930 if (exit)
kono
parents: 14
diff changeset
931 fprintf (dump_file, "Exit condition of peeled iterations was "
kono
parents: 14
diff changeset
932 "eliminated.\n");
kono
parents: 14
diff changeset
933 if (edge_to_cancel)
kono
parents: 14
diff changeset
934 fprintf (dump_file, "Last iteration exit edge was proved true.\n");
kono
parents: 14
diff changeset
935 else
kono
parents: 14
diff changeset
936 fprintf (dump_file, "Latch of last iteration was marked by "
kono
parents: 14
diff changeset
937 "__builtin_unreachable ().\n");
kono
parents: 14
diff changeset
938 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
939
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
940 return true;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
941 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
942
16
kono
parents: 14
diff changeset
943 /* Return number of instructions after peeling. */
kono
parents: 14
diff changeset
944 static unsigned HOST_WIDE_INT
kono
parents: 14
diff changeset
945 estimated_peeled_sequence_size (struct loop_size *size,
kono
parents: 14
diff changeset
946 unsigned HOST_WIDE_INT npeel)
kono
parents: 14
diff changeset
947 {
kono
parents: 14
diff changeset
948 return MAX (npeel * (HOST_WIDE_INT) (size->overall
kono
parents: 14
diff changeset
949 - size->eliminated_by_peeling), 1);
kono
parents: 14
diff changeset
950 }
kono
parents: 14
diff changeset
951
kono
parents: 14
diff changeset
952 /* If the loop is expected to iterate N times and is
kono
parents: 14
diff changeset
953 small enough, duplicate the loop body N+1 times before
kono
parents: 14
diff changeset
954 the loop itself. This way the hot path will never
kono
parents: 14
diff changeset
955 enter the loop.
kono
parents: 14
diff changeset
956 Parameters are the same as for try_unroll_loops_completely */
kono
parents: 14
diff changeset
957
kono
parents: 14
diff changeset
958 static bool
kono
parents: 14
diff changeset
959 try_peel_loop (struct loop *loop,
kono
parents: 14
diff changeset
960 edge exit, tree niter,
kono
parents: 14
diff changeset
961 HOST_WIDE_INT maxiter)
kono
parents: 14
diff changeset
962 {
kono
parents: 14
diff changeset
963 HOST_WIDE_INT npeel;
kono
parents: 14
diff changeset
964 struct loop_size size;
kono
parents: 14
diff changeset
965 int peeled_size;
kono
parents: 14
diff changeset
966
kono
parents: 14
diff changeset
967 if (!flag_peel_loops || PARAM_VALUE (PARAM_MAX_PEEL_TIMES) <= 0
kono
parents: 14
diff changeset
968 || !peeled_loops)
kono
parents: 14
diff changeset
969 return false;
kono
parents: 14
diff changeset
970
kono
parents: 14
diff changeset
971 if (bitmap_bit_p (peeled_loops, loop->num))
kono
parents: 14
diff changeset
972 {
kono
parents: 14
diff changeset
973 if (dump_file)
kono
parents: 14
diff changeset
974 fprintf (dump_file, "Not peeling: loop is already peeled\n");
kono
parents: 14
diff changeset
975 return false;
kono
parents: 14
diff changeset
976 }
kono
parents: 14
diff changeset
977
kono
parents: 14
diff changeset
978 /* Peel only innermost loops.
kono
parents: 14
diff changeset
979 While the code is perfectly capable of peeling non-innermost loops,
kono
parents: 14
diff changeset
980 the heuristics would probably need some improvements. */
kono
parents: 14
diff changeset
981 if (loop->inner)
kono
parents: 14
diff changeset
982 {
kono
parents: 14
diff changeset
983 if (dump_file)
kono
parents: 14
diff changeset
984 fprintf (dump_file, "Not peeling: outer loop\n");
kono
parents: 14
diff changeset
985 return false;
kono
parents: 14
diff changeset
986 }
kono
parents: 14
diff changeset
987
kono
parents: 14
diff changeset
988 if (!optimize_loop_for_speed_p (loop))
kono
parents: 14
diff changeset
989 {
kono
parents: 14
diff changeset
990 if (dump_file)
kono
parents: 14
diff changeset
991 fprintf (dump_file, "Not peeling: cold loop\n");
kono
parents: 14
diff changeset
992 return false;
kono
parents: 14
diff changeset
993 }
kono
parents: 14
diff changeset
994
kono
parents: 14
diff changeset
995 /* Check if there is an estimate on the number of iterations. */
kono
parents: 14
diff changeset
996 npeel = estimated_loop_iterations_int (loop);
kono
parents: 14
diff changeset
997 if (npeel < 0)
kono
parents: 14
diff changeset
998 npeel = likely_max_loop_iterations_int (loop);
kono
parents: 14
diff changeset
999 if (npeel < 0)
kono
parents: 14
diff changeset
1000 {
kono
parents: 14
diff changeset
1001 if (dump_file)
kono
parents: 14
diff changeset
1002 fprintf (dump_file, "Not peeling: number of iterations is not "
kono
parents: 14
diff changeset
1003 "estimated\n");
kono
parents: 14
diff changeset
1004 return false;
kono
parents: 14
diff changeset
1005 }
kono
parents: 14
diff changeset
1006 if (maxiter >= 0 && maxiter <= npeel)
kono
parents: 14
diff changeset
1007 {
kono
parents: 14
diff changeset
1008 if (dump_file)
kono
parents: 14
diff changeset
1009 fprintf (dump_file, "Not peeling: upper bound is known so can "
kono
parents: 14
diff changeset
1010 "unroll completely\n");
kono
parents: 14
diff changeset
1011 return false;
kono
parents: 14
diff changeset
1012 }
kono
parents: 14
diff changeset
1013
kono
parents: 14
diff changeset
1014 /* We want to peel estimated number of iterations + 1 (so we never
kono
parents: 14
diff changeset
1015 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
kono
parents: 14
diff changeset
1016 and be sure to avoid overflows. */
kono
parents: 14
diff changeset
1017 if (npeel > PARAM_VALUE (PARAM_MAX_PEEL_TIMES) - 1)
kono
parents: 14
diff changeset
1018 {
kono
parents: 14
diff changeset
1019 if (dump_file)
kono
parents: 14
diff changeset
1020 fprintf (dump_file, "Not peeling: rolls too much "
kono
parents: 14
diff changeset
1021 "(%i + 1 > --param max-peel-times)\n", (int) npeel);
kono
parents: 14
diff changeset
1022 return false;
kono
parents: 14
diff changeset
1023 }
kono
parents: 14
diff changeset
1024 npeel++;
kono
parents: 14
diff changeset
1025
kono
parents: 14
diff changeset
1026 /* Check peeled loops size. */
kono
parents: 14
diff changeset
1027 tree_estimate_loop_size (loop, exit, NULL, &size,
kono
parents: 14
diff changeset
1028 PARAM_VALUE (PARAM_MAX_PEELED_INSNS));
kono
parents: 14
diff changeset
1029 if ((peeled_size = estimated_peeled_sequence_size (&size, (int) npeel))
kono
parents: 14
diff changeset
1030 > PARAM_VALUE (PARAM_MAX_PEELED_INSNS))
kono
parents: 14
diff changeset
1031 {
kono
parents: 14
diff changeset
1032 if (dump_file)
kono
parents: 14
diff changeset
1033 fprintf (dump_file, "Not peeling: peeled sequence size is too large "
kono
parents: 14
diff changeset
1034 "(%i insns > --param max-peel-insns)", peeled_size);
kono
parents: 14
diff changeset
1035 return false;
kono
parents: 14
diff changeset
1036 }
kono
parents: 14
diff changeset
1037
kono
parents: 14
diff changeset
1038 /* Duplicate possibly eliminating the exits. */
kono
parents: 14
diff changeset
1039 initialize_original_copy_tables ();
kono
parents: 14
diff changeset
1040 auto_sbitmap wont_exit (npeel + 1);
kono
parents: 14
diff changeset
1041 if (exit && niter
kono
parents: 14
diff changeset
1042 && TREE_CODE (niter) == INTEGER_CST
kono
parents: 14
diff changeset
1043 && wi::leu_p (npeel, wi::to_widest (niter)))
kono
parents: 14
diff changeset
1044 {
kono
parents: 14
diff changeset
1045 bitmap_ones (wont_exit);
kono
parents: 14
diff changeset
1046 bitmap_clear_bit (wont_exit, 0);
kono
parents: 14
diff changeset
1047 }
kono
parents: 14
diff changeset
1048 else
kono
parents: 14
diff changeset
1049 {
kono
parents: 14
diff changeset
1050 exit = NULL;
kono
parents: 14
diff changeset
1051 bitmap_clear (wont_exit);
kono
parents: 14
diff changeset
1052 }
kono
parents: 14
diff changeset
1053 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
kono
parents: 14
diff changeset
1054 npeel, wont_exit,
kono
parents: 14
diff changeset
1055 exit, &edges_to_remove,
kono
parents: 14
diff changeset
1056 DLTHE_FLAG_UPDATE_FREQ))
kono
parents: 14
diff changeset
1057 {
kono
parents: 14
diff changeset
1058 free_original_copy_tables ();
kono
parents: 14
diff changeset
1059 return false;
kono
parents: 14
diff changeset
1060 }
kono
parents: 14
diff changeset
1061 free_original_copy_tables ();
kono
parents: 14
diff changeset
1062 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
1063 {
kono
parents: 14
diff changeset
1064 fprintf (dump_file, "Peeled loop %d, %i times.\n",
kono
parents: 14
diff changeset
1065 loop->num, (int) npeel);
kono
parents: 14
diff changeset
1066 }
kono
parents: 14
diff changeset
1067 if (loop->any_estimate)
kono
parents: 14
diff changeset
1068 {
kono
parents: 14
diff changeset
1069 if (wi::ltu_p (npeel, loop->nb_iterations_estimate))
kono
parents: 14
diff changeset
1070 loop->nb_iterations_estimate -= npeel;
kono
parents: 14
diff changeset
1071 else
kono
parents: 14
diff changeset
1072 loop->nb_iterations_estimate = 0;
kono
parents: 14
diff changeset
1073 }
kono
parents: 14
diff changeset
1074 if (loop->any_upper_bound)
kono
parents: 14
diff changeset
1075 {
kono
parents: 14
diff changeset
1076 if (wi::ltu_p (npeel, loop->nb_iterations_upper_bound))
kono
parents: 14
diff changeset
1077 loop->nb_iterations_upper_bound -= npeel;
kono
parents: 14
diff changeset
1078 else
kono
parents: 14
diff changeset
1079 loop->nb_iterations_upper_bound = 0;
kono
parents: 14
diff changeset
1080 }
kono
parents: 14
diff changeset
1081 if (loop->any_likely_upper_bound)
kono
parents: 14
diff changeset
1082 {
kono
parents: 14
diff changeset
1083 if (wi::ltu_p (npeel, loop->nb_iterations_likely_upper_bound))
kono
parents: 14
diff changeset
1084 loop->nb_iterations_likely_upper_bound -= npeel;
kono
parents: 14
diff changeset
1085 else
kono
parents: 14
diff changeset
1086 {
kono
parents: 14
diff changeset
1087 loop->any_estimate = true;
kono
parents: 14
diff changeset
1088 loop->nb_iterations_estimate = 0;
kono
parents: 14
diff changeset
1089 loop->nb_iterations_likely_upper_bound = 0;
kono
parents: 14
diff changeset
1090 }
kono
parents: 14
diff changeset
1091 }
kono
parents: 14
diff changeset
1092 profile_count entry_count = profile_count::zero ();
kono
parents: 14
diff changeset
1093 int entry_freq = 0;
kono
parents: 14
diff changeset
1094
kono
parents: 14
diff changeset
1095 edge e;
kono
parents: 14
diff changeset
1096 edge_iterator ei;
kono
parents: 14
diff changeset
1097 FOR_EACH_EDGE (e, ei, loop->header->preds)
kono
parents: 14
diff changeset
1098 if (e->src != loop->latch)
kono
parents: 14
diff changeset
1099 {
kono
parents: 14
diff changeset
1100 if (e->src->count.initialized_p ())
kono
parents: 14
diff changeset
1101 entry_count = e->src->count + e->src->count;
kono
parents: 14
diff changeset
1102 entry_freq += e->src->frequency;
kono
parents: 14
diff changeset
1103 gcc_assert (!flow_bb_inside_loop_p (loop, e->src));
kono
parents: 14
diff changeset
1104 }
kono
parents: 14
diff changeset
1105 profile_probability p = profile_probability::very_unlikely ();
kono
parents: 14
diff changeset
1106 if (loop->header->count > 0)
kono
parents: 14
diff changeset
1107 p = entry_count.probability_in (loop->header->count);
kono
parents: 14
diff changeset
1108 else if (loop->header->frequency)
kono
parents: 14
diff changeset
1109 p = profile_probability::probability_in_gcov_type
kono
parents: 14
diff changeset
1110 (entry_freq, loop->header->frequency);
kono
parents: 14
diff changeset
1111 scale_loop_profile (loop, p, 0);
kono
parents: 14
diff changeset
1112 bitmap_set_bit (peeled_loops, loop->num);
kono
parents: 14
diff changeset
1113 return true;
kono
parents: 14
diff changeset
1114 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1115 /* Adds a canonical induction variable to LOOP if suitable.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
1116 CREATE_IV is true if we may create a new iv. UL determines
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1117 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
1118 to determine the number of iterations of a loop by direct evaluation.
16
kono
parents: 14
diff changeset
1119 Returns true if cfg is changed. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1120
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1121 static bool
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1122 canonicalize_loop_induction_variables (struct loop *loop,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1123 bool create_iv, enum unroll_level ul,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1124 bool try_eval)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1125 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1126 edge exit = NULL;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1127 tree niter;
16
kono
parents: 14
diff changeset
1128 HOST_WIDE_INT maxiter;
kono
parents: 14
diff changeset
1129 bool modified = false;
kono
parents: 14
diff changeset
1130 location_t locus = UNKNOWN_LOCATION;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1131
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1132 niter = number_of_latch_executions (loop);
16
kono
parents: 14
diff changeset
1133 exit = single_exit (loop);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1134 if (TREE_CODE (niter) == INTEGER_CST)
16
kono
parents: 14
diff changeset
1135 locus = gimple_location (last_stmt (exit->src));
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1136 else
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1137 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1138 /* If the loop has more than one exit, try checking all of them
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1139 for # of iterations determinable through scev. */
16
kono
parents: 14
diff changeset
1140 if (!exit)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1141 niter = find_loop_niter (loop, &exit);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1142
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1143 /* Finally if everything else fails, try brute force evaluation. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1144 if (try_eval
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1145 && (chrec_contains_undetermined (niter)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1146 || TREE_CODE (niter) != INTEGER_CST))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1147 niter = find_loop_niter_by_eval (loop, &exit);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1148
16
kono
parents: 14
diff changeset
1149 if (exit)
kono
parents: 14
diff changeset
1150 locus = gimple_location (last_stmt (exit->src));
kono
parents: 14
diff changeset
1151
kono
parents: 14
diff changeset
1152 if (TREE_CODE (niter) != INTEGER_CST)
kono
parents: 14
diff changeset
1153 exit = NULL;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1154 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1155
16
kono
parents: 14
diff changeset
1156 /* We work exceptionally hard here to estimate the bound
kono
parents: 14
diff changeset
1157 by find_loop_niter_by_eval. Be sure to keep it for future. */
kono
parents: 14
diff changeset
1158 if (niter && TREE_CODE (niter) == INTEGER_CST)
kono
parents: 14
diff changeset
1159 {
kono
parents: 14
diff changeset
1160 record_niter_bound (loop, wi::to_widest (niter),
kono
parents: 14
diff changeset
1161 exit == single_likely_exit (loop), true);
kono
parents: 14
diff changeset
1162 }
kono
parents: 14
diff changeset
1163
kono
parents: 14
diff changeset
1164 /* Force re-computation of loop bounds so we can remove redundant exits. */
kono
parents: 14
diff changeset
1165 maxiter = max_loop_iterations_int (loop);
kono
parents: 14
diff changeset
1166
kono
parents: 14
diff changeset
1167 if (dump_file && (dump_flags & TDF_DETAILS)
kono
parents: 14
diff changeset
1168 && TREE_CODE (niter) == INTEGER_CST)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1169 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1170 fprintf (dump_file, "Loop %d iterates ", loop->num);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1171 print_generic_expr (dump_file, niter, TDF_SLIM);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1172 fprintf (dump_file, " times.\n");
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1173 }
16
kono
parents: 14
diff changeset
1174 if (dump_file && (dump_flags & TDF_DETAILS)
kono
parents: 14
diff changeset
1175 && maxiter >= 0)
kono
parents: 14
diff changeset
1176 {
kono
parents: 14
diff changeset
1177 fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
kono
parents: 14
diff changeset
1178 (int)maxiter);
kono
parents: 14
diff changeset
1179 }
kono
parents: 14
diff changeset
1180 if (dump_file && (dump_flags & TDF_DETAILS)
kono
parents: 14
diff changeset
1181 && likely_max_loop_iterations_int (loop) >= 0)
kono
parents: 14
diff changeset
1182 {
kono
parents: 14
diff changeset
1183 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
kono
parents: 14
diff changeset
1184 loop->num, (int)likely_max_loop_iterations_int (loop));
kono
parents: 14
diff changeset
1185 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1186
16
kono
parents: 14
diff changeset
1187 /* Remove exits that are known to be never taken based on loop bound.
kono
parents: 14
diff changeset
1188 Needs to be called after compilation of max_loop_iterations_int that
kono
parents: 14
diff changeset
1189 populates the loop bounds. */
kono
parents: 14
diff changeset
1190 modified |= remove_redundant_iv_tests (loop);
kono
parents: 14
diff changeset
1191
kono
parents: 14
diff changeset
1192 if (try_unroll_loop_completely (loop, exit, niter, ul, maxiter, locus))
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1193 return true;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1194
16
kono
parents: 14
diff changeset
1195 if (create_iv
kono
parents: 14
diff changeset
1196 && niter && !chrec_contains_undetermined (niter)
kono
parents: 14
diff changeset
1197 && exit && just_once_each_iteration_p (loop, exit->src))
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1198 create_canonical_iv (loop, exit, niter);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1199
16
kono
parents: 14
diff changeset
1200 if (ul == UL_ALL)
kono
parents: 14
diff changeset
1201 modified |= try_peel_loop (loop, exit, niter, maxiter);
kono
parents: 14
diff changeset
1202
kono
parents: 14
diff changeset
1203 return modified;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1204 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1205
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1206 /* The main entry point of the pass. Adds canonical induction variables
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1207 to the suitable loops. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1208
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1209 unsigned int
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1210 canonicalize_induction_variables (void)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1211 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1212 struct loop *loop;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1213 bool changed = false;
16
kono
parents: 14
diff changeset
1214 bool irred_invalidated = false;
kono
parents: 14
diff changeset
1215 bitmap loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
1216
16
kono
parents: 14
diff changeset
1217 estimate_numbers_of_iterations (cfun);
kono
parents: 14
diff changeset
1218
kono
parents: 14
diff changeset
1219 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1220 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1221 changed |= canonicalize_loop_induction_variables (loop,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1222 true, UL_SINGLE_ITER,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1223 true);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1224 }
16
kono
parents: 14
diff changeset
1225 gcc_assert (!need_ssa_update_p (cfun));
kono
parents: 14
diff changeset
1226
kono
parents: 14
diff changeset
1227 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
kono
parents: 14
diff changeset
1228 if (irred_invalidated
kono
parents: 14
diff changeset
1229 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
kono
parents: 14
diff changeset
1230 mark_irreducible_loops ();
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1231
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1232 /* Clean up the information about numbers of iterations, since brute force
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1233 evaluation could reveal new information. */
16
kono
parents: 14
diff changeset
1234 free_numbers_of_iterations_estimates (cfun);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1235 scev_reset ();
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1236
16
kono
parents: 14
diff changeset
1237 if (!bitmap_empty_p (loop_closed_ssa_invalidated))
kono
parents: 14
diff changeset
1238 {
kono
parents: 14
diff changeset
1239 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA));
kono
parents: 14
diff changeset
1240 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
kono
parents: 14
diff changeset
1241 }
kono
parents: 14
diff changeset
1242 BITMAP_FREE (loop_closed_ssa_invalidated);
kono
parents: 14
diff changeset
1243
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1244 if (changed)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1245 return TODO_cleanup_cfg;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1246 return 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1247 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1248
16
kono
parents: 14
diff changeset
1249 /* Propagate constant SSA_NAMEs defined in basic block BB. */
kono
parents: 14
diff changeset
1250
kono
parents: 14
diff changeset
1251 static void
kono
parents: 14
diff changeset
1252 propagate_constants_for_unrolling (basic_block bb)
kono
parents: 14
diff changeset
1253 {
kono
parents: 14
diff changeset
1254 /* Look for degenerate PHI nodes with constant argument. */
kono
parents: 14
diff changeset
1255 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
kono
parents: 14
diff changeset
1256 {
kono
parents: 14
diff changeset
1257 gphi *phi = gsi.phi ();
kono
parents: 14
diff changeset
1258 tree result = gimple_phi_result (phi);
kono
parents: 14
diff changeset
1259 tree arg = gimple_phi_arg_def (phi, 0);
kono
parents: 14
diff changeset
1260
kono
parents: 14
diff changeset
1261 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (result)
kono
parents: 14
diff changeset
1262 && gimple_phi_num_args (phi) == 1
kono
parents: 14
diff changeset
1263 && CONSTANT_CLASS_P (arg))
kono
parents: 14
diff changeset
1264 {
kono
parents: 14
diff changeset
1265 replace_uses_by (result, arg);
kono
parents: 14
diff changeset
1266 gsi_remove (&gsi, true);
kono
parents: 14
diff changeset
1267 release_ssa_name (result);
kono
parents: 14
diff changeset
1268 }
kono
parents: 14
diff changeset
1269 else
kono
parents: 14
diff changeset
1270 gsi_next (&gsi);
kono
parents: 14
diff changeset
1271 }
kono
parents: 14
diff changeset
1272
kono
parents: 14
diff changeset
1273 /* Look for assignments to SSA names with constant RHS. */
kono
parents: 14
diff changeset
1274 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
kono
parents: 14
diff changeset
1275 {
kono
parents: 14
diff changeset
1276 gimple *stmt = gsi_stmt (gsi);
kono
parents: 14
diff changeset
1277 tree lhs;
kono
parents: 14
diff changeset
1278
kono
parents: 14
diff changeset
1279 if (is_gimple_assign (stmt)
kono
parents: 14
diff changeset
1280 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_constant
kono
parents: 14
diff changeset
1281 && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)
kono
parents: 14
diff changeset
1282 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
kono
parents: 14
diff changeset
1283 {
kono
parents: 14
diff changeset
1284 replace_uses_by (lhs, gimple_assign_rhs1 (stmt));
kono
parents: 14
diff changeset
1285 gsi_remove (&gsi, true);
kono
parents: 14
diff changeset
1286 release_ssa_name (lhs);
kono
parents: 14
diff changeset
1287 }
kono
parents: 14
diff changeset
1288 else
kono
parents: 14
diff changeset
1289 gsi_next (&gsi);
kono
parents: 14
diff changeset
1290 }
kono
parents: 14
diff changeset
1291 }
kono
parents: 14
diff changeset
1292
kono
parents: 14
diff changeset
1293 /* Process loops from innermost to outer, stopping at the innermost
kono
parents: 14
diff changeset
1294 loop we unrolled. */
kono
parents: 14
diff changeset
1295
kono
parents: 14
diff changeset
1296 static bool
kono
parents: 14
diff changeset
1297 tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
kono
parents: 14
diff changeset
1298 bitmap father_bbs, struct loop *loop)
kono
parents: 14
diff changeset
1299 {
kono
parents: 14
diff changeset
1300 struct loop *loop_father;
kono
parents: 14
diff changeset
1301 bool changed = false;
kono
parents: 14
diff changeset
1302 struct loop *inner;
kono
parents: 14
diff changeset
1303 enum unroll_level ul;
kono
parents: 14
diff changeset
1304
kono
parents: 14
diff changeset
1305 /* Process inner loops first. */
kono
parents: 14
diff changeset
1306 for (inner = loop->inner; inner != NULL; inner = inner->next)
kono
parents: 14
diff changeset
1307 changed |= tree_unroll_loops_completely_1 (may_increase_size,
kono
parents: 14
diff changeset
1308 unroll_outer, father_bbs,
kono
parents: 14
diff changeset
1309 inner);
kono
parents: 14
diff changeset
1310
kono
parents: 14
diff changeset
1311 /* If we changed an inner loop we cannot process outer loops in this
kono
parents: 14
diff changeset
1312 iteration because SSA form is not up-to-date. Continue with
kono
parents: 14
diff changeset
1313 siblings of outer loops instead. */
kono
parents: 14
diff changeset
1314 if (changed)
kono
parents: 14
diff changeset
1315 return true;
kono
parents: 14
diff changeset
1316
kono
parents: 14
diff changeset
1317 /* Don't unroll #pragma omp simd loops until the vectorizer
kono
parents: 14
diff changeset
1318 attempts to vectorize those. */
kono
parents: 14
diff changeset
1319 if (loop->force_vectorize)
kono
parents: 14
diff changeset
1320 return false;
kono
parents: 14
diff changeset
1321
kono
parents: 14
diff changeset
1322 /* Try to unroll this loop. */
kono
parents: 14
diff changeset
1323 loop_father = loop_outer (loop);
kono
parents: 14
diff changeset
1324 if (!loop_father)
kono
parents: 14
diff changeset
1325 return false;
kono
parents: 14
diff changeset
1326
kono
parents: 14
diff changeset
1327 if (may_increase_size && optimize_loop_nest_for_speed_p (loop)
kono
parents: 14
diff changeset
1328 /* Unroll outermost loops only if asked to do so or they do
kono
parents: 14
diff changeset
1329 not cause code growth. */
kono
parents: 14
diff changeset
1330 && (unroll_outer || loop_outer (loop_father)))
kono
parents: 14
diff changeset
1331 ul = UL_ALL;
kono
parents: 14
diff changeset
1332 else
kono
parents: 14
diff changeset
1333 ul = UL_NO_GROWTH;
kono
parents: 14
diff changeset
1334
kono
parents: 14
diff changeset
1335 if (canonicalize_loop_induction_variables
kono
parents: 14
diff changeset
1336 (loop, false, ul, !flag_tree_loop_ivcanon))
kono
parents: 14
diff changeset
1337 {
kono
parents: 14
diff changeset
1338 /* If we'll continue unrolling, we need to propagate constants
kono
parents: 14
diff changeset
1339 within the new basic blocks to fold away induction variable
kono
parents: 14
diff changeset
1340 computations; otherwise, the size might blow up before the
kono
parents: 14
diff changeset
1341 iteration is complete and the IR eventually cleaned up. */
kono
parents: 14
diff changeset
1342 if (loop_outer (loop_father))
kono
parents: 14
diff changeset
1343 bitmap_set_bit (father_bbs, loop_father->header->index);
kono
parents: 14
diff changeset
1344
kono
parents: 14
diff changeset
1345 return true;
kono
parents: 14
diff changeset
1346 }
kono
parents: 14
diff changeset
1347
kono
parents: 14
diff changeset
1348 return false;
kono
parents: 14
diff changeset
1349 }
kono
parents: 14
diff changeset
1350
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1351 /* Unroll LOOPS completely if they iterate just few times. Unless
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1352 MAY_INCREASE_SIZE is true, perform the unrolling only if the
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1353 size of the code does not increase. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1354
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1355 unsigned int
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1356 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1357 {
16
kono
parents: 14
diff changeset
1358 bitmap father_bbs = BITMAP_ALLOC (NULL);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1359 bool changed;
11
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
1360 int iteration = 0;
16
kono
parents: 14
diff changeset
1361 bool irred_invalidated = false;
kono
parents: 14
diff changeset
1362
kono
parents: 14
diff changeset
1363 estimate_numbers_of_iterations (cfun);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1364
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1365 do
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1366 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1367 changed = false;
16
kono
parents: 14
diff changeset
1368 bitmap loop_closed_ssa_invalidated = NULL;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1369
16
kono
parents: 14
diff changeset
1370 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
kono
parents: 14
diff changeset
1371 loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1372
16
kono
parents: 14
diff changeset
1373 free_numbers_of_iterations_estimates (cfun);
kono
parents: 14
diff changeset
1374 estimate_numbers_of_iterations (cfun);
kono
parents: 14
diff changeset
1375
kono
parents: 14
diff changeset
1376 changed = tree_unroll_loops_completely_1 (may_increase_size,
kono
parents: 14
diff changeset
1377 unroll_outer, father_bbs,
kono
parents: 14
diff changeset
1378 current_loops->tree_root);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1379 if (changed)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1380 {
16
kono
parents: 14
diff changeset
1381 unsigned i;
kono
parents: 14
diff changeset
1382
kono
parents: 14
diff changeset
1383 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
kono
parents: 14
diff changeset
1384
kono
parents: 14
diff changeset
1385 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
kono
parents: 14
diff changeset
1386 if (loop_closed_ssa_invalidated
kono
parents: 14
diff changeset
1387 && !bitmap_empty_p (loop_closed_ssa_invalidated))
kono
parents: 14
diff changeset
1388 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated,
kono
parents: 14
diff changeset
1389 TODO_update_ssa);
kono
parents: 14
diff changeset
1390 else
kono
parents: 14
diff changeset
1391 update_ssa (TODO_update_ssa);
kono
parents: 14
diff changeset
1392
kono
parents: 14
diff changeset
1393 /* father_bbs is a bitmap of loop father header BB indices.
kono
parents: 14
diff changeset
1394 Translate that to what non-root loops these BBs belong to now. */
kono
parents: 14
diff changeset
1395 bitmap_iterator bi;
kono
parents: 14
diff changeset
1396 bitmap fathers = BITMAP_ALLOC (NULL);
kono
parents: 14
diff changeset
1397 EXECUTE_IF_SET_IN_BITMAP (father_bbs, 0, i, bi)
kono
parents: 14
diff changeset
1398 {
kono
parents: 14
diff changeset
1399 basic_block unrolled_loop_bb = BASIC_BLOCK_FOR_FN (cfun, i);
kono
parents: 14
diff changeset
1400 if (! unrolled_loop_bb)
kono
parents: 14
diff changeset
1401 continue;
kono
parents: 14
diff changeset
1402 if (loop_outer (unrolled_loop_bb->loop_father))
kono
parents: 14
diff changeset
1403 bitmap_set_bit (fathers,
kono
parents: 14
diff changeset
1404 unrolled_loop_bb->loop_father->num);
kono
parents: 14
diff changeset
1405 }
kono
parents: 14
diff changeset
1406 bitmap_clear (father_bbs);
kono
parents: 14
diff changeset
1407 /* Propagate the constants within the new basic blocks. */
kono
parents: 14
diff changeset
1408 EXECUTE_IF_SET_IN_BITMAP (fathers, 0, i, bi)
kono
parents: 14
diff changeset
1409 {
kono
parents: 14
diff changeset
1410 loop_p father = get_loop (cfun, i);
kono
parents: 14
diff changeset
1411 basic_block *body = get_loop_body_in_dom_order (father);
kono
parents: 14
diff changeset
1412 for (unsigned j = 0; j < father->num_nodes; j++)
kono
parents: 14
diff changeset
1413 propagate_constants_for_unrolling (body[j]);
kono
parents: 14
diff changeset
1414 free (body);
kono
parents: 14
diff changeset
1415 }
kono
parents: 14
diff changeset
1416 BITMAP_FREE (fathers);
kono
parents: 14
diff changeset
1417
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1418 /* This will take care of removing completely unrolled loops
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1419 from the loop structures so we can continue unrolling now
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1420 innermost loops. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1421 if (cleanup_tree_cfg ())
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1422 update_ssa (TODO_update_ssa_only_virtuals);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1423
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1424 /* Clean up the information about numbers of iterations, since
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1425 complete unrolling might have invalidated it. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1426 scev_reset ();
16
kono
parents: 14
diff changeset
1427 if (flag_checking && loops_state_satisfies_p (LOOP_CLOSED_SSA))
kono
parents: 14
diff changeset
1428 verify_loop_closed_ssa (true);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1429 }
16
kono
parents: 14
diff changeset
1430 if (loop_closed_ssa_invalidated)
kono
parents: 14
diff changeset
1431 BITMAP_FREE (loop_closed_ssa_invalidated);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1432 }
11
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
1433 while (changed
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
1434 && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1435
16
kono
parents: 14
diff changeset
1436 BITMAP_FREE (father_bbs);
kono
parents: 14
diff changeset
1437
kono
parents: 14
diff changeset
1438 if (irred_invalidated
kono
parents: 14
diff changeset
1439 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
kono
parents: 14
diff changeset
1440 mark_irreducible_loops ();
kono
parents: 14
diff changeset
1441
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1442 return 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1443 }
16
kono
parents: 14
diff changeset
1444
kono
parents: 14
diff changeset
1445 /* Canonical induction variable creation pass. */
kono
parents: 14
diff changeset
1446
kono
parents: 14
diff changeset
1447 namespace {
kono
parents: 14
diff changeset
1448
kono
parents: 14
diff changeset
1449 const pass_data pass_data_iv_canon =
kono
parents: 14
diff changeset
1450 {
kono
parents: 14
diff changeset
1451 GIMPLE_PASS, /* type */
kono
parents: 14
diff changeset
1452 "ivcanon", /* name */
kono
parents: 14
diff changeset
1453 OPTGROUP_LOOP, /* optinfo_flags */
kono
parents: 14
diff changeset
1454 TV_TREE_LOOP_IVCANON, /* tv_id */
kono
parents: 14
diff changeset
1455 ( PROP_cfg | PROP_ssa ), /* properties_required */
kono
parents: 14
diff changeset
1456 0, /* properties_provided */
kono
parents: 14
diff changeset
1457 0, /* properties_destroyed */
kono
parents: 14
diff changeset
1458 0, /* todo_flags_start */
kono
parents: 14
diff changeset
1459 0, /* todo_flags_finish */
kono
parents: 14
diff changeset
1460 };
kono
parents: 14
diff changeset
1461
kono
parents: 14
diff changeset
1462 class pass_iv_canon : public gimple_opt_pass
kono
parents: 14
diff changeset
1463 {
kono
parents: 14
diff changeset
1464 public:
kono
parents: 14
diff changeset
1465 pass_iv_canon (gcc::context *ctxt)
kono
parents: 14
diff changeset
1466 : gimple_opt_pass (pass_data_iv_canon, ctxt)
kono
parents: 14
diff changeset
1467 {}
kono
parents: 14
diff changeset
1468
kono
parents: 14
diff changeset
1469 /* opt_pass methods: */
kono
parents: 14
diff changeset
1470 virtual bool gate (function *) { return flag_tree_loop_ivcanon != 0; }
kono
parents: 14
diff changeset
1471 virtual unsigned int execute (function *fun);
kono
parents: 14
diff changeset
1472
kono
parents: 14
diff changeset
1473 }; // class pass_iv_canon
kono
parents: 14
diff changeset
1474
kono
parents: 14
diff changeset
1475 unsigned int
kono
parents: 14
diff changeset
1476 pass_iv_canon::execute (function *fun)
kono
parents: 14
diff changeset
1477 {
kono
parents: 14
diff changeset
1478 if (number_of_loops (fun) <= 1)
kono
parents: 14
diff changeset
1479 return 0;
kono
parents: 14
diff changeset
1480
kono
parents: 14
diff changeset
1481 return canonicalize_induction_variables ();
kono
parents: 14
diff changeset
1482 }
kono
parents: 14
diff changeset
1483
kono
parents: 14
diff changeset
1484 } // anon namespace
kono
parents: 14
diff changeset
1485
kono
parents: 14
diff changeset
1486 gimple_opt_pass *
kono
parents: 14
diff changeset
1487 make_pass_iv_canon (gcc::context *ctxt)
kono
parents: 14
diff changeset
1488 {
kono
parents: 14
diff changeset
1489 return new pass_iv_canon (ctxt);
kono
parents: 14
diff changeset
1490 }
kono
parents: 14
diff changeset
1491
kono
parents: 14
diff changeset
1492 /* Complete unrolling of loops. */
kono
parents: 14
diff changeset
1493
kono
parents: 14
diff changeset
1494 namespace {
kono
parents: 14
diff changeset
1495
kono
parents: 14
diff changeset
1496 const pass_data pass_data_complete_unroll =
kono
parents: 14
diff changeset
1497 {
kono
parents: 14
diff changeset
1498 GIMPLE_PASS, /* type */
kono
parents: 14
diff changeset
1499 "cunroll", /* name */
kono
parents: 14
diff changeset
1500 OPTGROUP_LOOP, /* optinfo_flags */
kono
parents: 14
diff changeset
1501 TV_COMPLETE_UNROLL, /* tv_id */
kono
parents: 14
diff changeset
1502 ( PROP_cfg | PROP_ssa ), /* properties_required */
kono
parents: 14
diff changeset
1503 0, /* properties_provided */
kono
parents: 14
diff changeset
1504 0, /* properties_destroyed */
kono
parents: 14
diff changeset
1505 0, /* todo_flags_start */
kono
parents: 14
diff changeset
1506 0, /* todo_flags_finish */
kono
parents: 14
diff changeset
1507 };
kono
parents: 14
diff changeset
1508
kono
parents: 14
diff changeset
1509 class pass_complete_unroll : public gimple_opt_pass
kono
parents: 14
diff changeset
1510 {
kono
parents: 14
diff changeset
1511 public:
kono
parents: 14
diff changeset
1512 pass_complete_unroll (gcc::context *ctxt)
kono
parents: 14
diff changeset
1513 : gimple_opt_pass (pass_data_complete_unroll, ctxt)
kono
parents: 14
diff changeset
1514 {}
kono
parents: 14
diff changeset
1515
kono
parents: 14
diff changeset
1516 /* opt_pass methods: */
kono
parents: 14
diff changeset
1517 virtual unsigned int execute (function *);
kono
parents: 14
diff changeset
1518
kono
parents: 14
diff changeset
1519 }; // class pass_complete_unroll
kono
parents: 14
diff changeset
1520
kono
parents: 14
diff changeset
1521 unsigned int
kono
parents: 14
diff changeset
1522 pass_complete_unroll::execute (function *fun)
kono
parents: 14
diff changeset
1523 {
kono
parents: 14
diff changeset
1524 if (number_of_loops (fun) <= 1)
kono
parents: 14
diff changeset
1525 return 0;
kono
parents: 14
diff changeset
1526
kono
parents: 14
diff changeset
1527 /* If we ever decide to run loop peeling more than once, we will need to
kono
parents: 14
diff changeset
1528 track loops already peeled in loop structures themselves to avoid
kono
parents: 14
diff changeset
1529 re-peeling the same loop multiple times. */
kono
parents: 14
diff changeset
1530 if (flag_peel_loops)
kono
parents: 14
diff changeset
1531 peeled_loops = BITMAP_ALLOC (NULL);
kono
parents: 14
diff changeset
1532 int val = tree_unroll_loops_completely (flag_unroll_loops
kono
parents: 14
diff changeset
1533 || flag_peel_loops
kono
parents: 14
diff changeset
1534 || optimize >= 3, true);
kono
parents: 14
diff changeset
1535 if (peeled_loops)
kono
parents: 14
diff changeset
1536 {
kono
parents: 14
diff changeset
1537 BITMAP_FREE (peeled_loops);
kono
parents: 14
diff changeset
1538 peeled_loops = NULL;
kono
parents: 14
diff changeset
1539 }
kono
parents: 14
diff changeset
1540 return val;
kon&