annotate gcc/tree-ssa-loop-unswitch.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
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 /* Loop unswitching.
16
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 #include "config.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 #include "system.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 #include "coretypes.h"
16
kono
parents: 14
diff changeset
23 #include "backend.h"
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 #include "tree.h"
16
kono
parents: 14
diff changeset
25 #include "gimple.h"
kono
parents: 14
diff changeset
26 #include "tree-pass.h"
kono
parents: 14
diff changeset
27 #include "ssa.h"
kono
parents: 14
diff changeset
28 #include "fold-const.h"
kono
parents: 14
diff changeset
29 #include "gimplify.h"
kono
parents: 14
diff changeset
30 #include "tree-cfg.h"
kono
parents: 14
diff changeset
31 #include "tree-ssa.h"
kono
parents: 14
diff changeset
32 #include "tree-ssa-loop-niter.h"
kono
parents: 14
diff changeset
33 #include "tree-ssa-loop.h"
kono
parents: 14
diff changeset
34 #include "tree-into-ssa.h"
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 #include "cfgloop.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 #include "params.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 #include "tree-inline.h"
16
kono
parents: 14
diff changeset
38 #include "gimple-iterator.h"
kono
parents: 14
diff changeset
39 #include "cfghooks.h"
kono
parents: 14
diff changeset
40 #include "tree-ssa-loop-manip.h"
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 /* This file implements the loop unswitching, i.e. transformation of loops like
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 while (A)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 if (inv)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 B;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 X;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 if (!inv)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 C;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 where inv is the loop invariant, into
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 if (inv)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 while (A)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 B;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 X;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 else
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 while (A)
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 X;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 C;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 Inv is considered invariant iff the values it compares are both invariant;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 tree-ssa-loop-im.c ensures that all the suitable conditions are in this
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 shape. */
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 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 static bool tree_unswitch_single_loop (struct loop *, int);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 static tree tree_may_unswitch_on (basic_block, struct loop *);
16
kono
parents: 14
diff changeset
81 static bool tree_unswitch_outer_loop (struct loop *);
kono
parents: 14
diff changeset
82 static edge find_loop_guard (struct loop *);
kono
parents: 14
diff changeset
83 static bool empty_bb_without_guard_p (struct loop *, basic_block);
kono
parents: 14
diff changeset
84 static bool used_outside_loop_p (struct loop *, tree);
kono
parents: 14
diff changeset
85 static void hoist_guard (struct loop *, edge);
kono
parents: 14
diff changeset
86 static bool check_exit_phi (struct loop *);
kono
parents: 14
diff changeset
87 static tree get_vop_from_header (struct loop *);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 /* Main entry point. Perform loop unswitching on all suitable loops. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 unsigned int
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 tree_ssa_unswitch_loops (void)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 struct loop *loop;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 bool changed = false;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
96
16
kono
parents: 14
diff changeset
97 /* Go through all loops starting from innermost. */
kono
parents: 14
diff changeset
98 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 {
16
kono
parents: 14
diff changeset
100 if (!loop->inner)
kono
parents: 14
diff changeset
101 /* Unswitch innermost loop. */
kono
parents: 14
diff changeset
102 changed |= tree_unswitch_single_loop (loop, 0);
kono
parents: 14
diff changeset
103 else
kono
parents: 14
diff changeset
104 changed |= tree_unswitch_outer_loop (loop);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 }
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 if (changed)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 return TODO_cleanup_cfg;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 return 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
111
16
kono
parents: 14
diff changeset
112 /* Return TRUE if an SSA_NAME maybe undefined and is therefore
kono
parents: 14
diff changeset
113 unsuitable for unswitching. STMT is the statement we are
kono
parents: 14
diff changeset
114 considering for unswitching and LOOP is the loop it appears in. */
kono
parents: 14
diff changeset
115
kono
parents: 14
diff changeset
116 static bool
kono
parents: 14
diff changeset
117 is_maybe_undefined (const tree name, gimple *stmt, struct loop *loop)
kono
parents: 14
diff changeset
118 {
kono
parents: 14
diff changeset
119 /* The loop header is the only block we can trivially determine that
kono
parents: 14
diff changeset
120 will always be executed. If the comparison is in the loop
kono
parents: 14
diff changeset
121 header, we know it's OK to unswitch on it. */
kono
parents: 14
diff changeset
122 if (gimple_bb (stmt) == loop->header)
kono
parents: 14
diff changeset
123 return false;
kono
parents: 14
diff changeset
124
kono
parents: 14
diff changeset
125 auto_bitmap visited_ssa;
kono
parents: 14
diff changeset
126 auto_vec<tree> worklist;
kono
parents: 14
diff changeset
127 worklist.safe_push (name);
kono
parents: 14
diff changeset
128 bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
kono
parents: 14
diff changeset
129 while (!worklist.is_empty ())
kono
parents: 14
diff changeset
130 {
kono
parents: 14
diff changeset
131 tree t = worklist.pop ();
kono
parents: 14
diff changeset
132
kono
parents: 14
diff changeset
133 /* If it's obviously undefined, avoid further computations. */
kono
parents: 14
diff changeset
134 if (ssa_undefined_value_p (t, true))
kono
parents: 14
diff changeset
135 return true;
kono
parents: 14
diff changeset
136
kono
parents: 14
diff changeset
137 if (ssa_defined_default_def_p (t))
kono
parents: 14
diff changeset
138 continue;
kono
parents: 14
diff changeset
139
kono
parents: 14
diff changeset
140 gimple *def = SSA_NAME_DEF_STMT (t);
kono
parents: 14
diff changeset
141
kono
parents: 14
diff changeset
142 /* Check that all the PHI args are fully defined. */
kono
parents: 14
diff changeset
143 if (gphi *phi = dyn_cast <gphi *> (def))
kono
parents: 14
diff changeset
144 {
kono
parents: 14
diff changeset
145 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
kono
parents: 14
diff changeset
146 {
kono
parents: 14
diff changeset
147 tree t = gimple_phi_arg_def (phi, i);
kono
parents: 14
diff changeset
148 /* If an SSA has already been seen, it may be a loop,
kono
parents: 14
diff changeset
149 but we can continue and ignore this use. Otherwise,
kono
parents: 14
diff changeset
150 add the SSA_NAME to the queue and visit it later. */
kono
parents: 14
diff changeset
151 if (TREE_CODE (t) == SSA_NAME
kono
parents: 14
diff changeset
152 && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
kono
parents: 14
diff changeset
153 worklist.safe_push (t);
kono
parents: 14
diff changeset
154 }
kono
parents: 14
diff changeset
155 continue;
kono
parents: 14
diff changeset
156 }
kono
parents: 14
diff changeset
157
kono
parents: 14
diff changeset
158 /* Uses in stmts always executed when the region header executes
kono
parents: 14
diff changeset
159 are fine. */
kono
parents: 14
diff changeset
160 if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def)))
kono
parents: 14
diff changeset
161 continue;
kono
parents: 14
diff changeset
162
kono
parents: 14
diff changeset
163 /* Handle calls and memory loads conservatively. */
kono
parents: 14
diff changeset
164 if (!is_gimple_assign (def)
kono
parents: 14
diff changeset
165 || (gimple_assign_single_p (def)
kono
parents: 14
diff changeset
166 && gimple_vuse (def)))
kono
parents: 14
diff changeset
167 return true;
kono
parents: 14
diff changeset
168
kono
parents: 14
diff changeset
169 /* Check that any SSA names used to define NAME are also fully
kono
parents: 14
diff changeset
170 defined. */
kono
parents: 14
diff changeset
171 use_operand_p use_p;
kono
parents: 14
diff changeset
172 ssa_op_iter iter;
kono
parents: 14
diff changeset
173 FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
kono
parents: 14
diff changeset
174 {
kono
parents: 14
diff changeset
175 tree t = USE_FROM_PTR (use_p);
kono
parents: 14
diff changeset
176 /* If an SSA has already been seen, it may be a loop,
kono
parents: 14
diff changeset
177 but we can continue and ignore this use. Otherwise,
kono
parents: 14
diff changeset
178 add the SSA_NAME to the queue and visit it later. */
kono
parents: 14
diff changeset
179 if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
kono
parents: 14
diff changeset
180 worklist.safe_push (t);
kono
parents: 14
diff changeset
181 }
kono
parents: 14
diff changeset
182 }
kono
parents: 14
diff changeset
183 return false;
kono
parents: 14
diff changeset
184 }
kono
parents: 14
diff changeset
185
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
186 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 basic blocks (for what it means see comments below). */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
188
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
189 static tree
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
190 tree_may_unswitch_on (basic_block bb, struct loop *loop)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
191 {
16
kono
parents: 14
diff changeset
192 gimple *last, *def;
kono
parents: 14
diff changeset
193 gcond *stmt;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
194 tree cond, use;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
195 basic_block def_bb;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
196 ssa_op_iter iter;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
197
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
198 /* BB must end in a simple conditional jump. */
16
kono
parents: 14
diff changeset
199 last = last_stmt (bb);
kono
parents: 14
diff changeset
200 if (!last || gimple_code (last) != GIMPLE_COND)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
201 return NULL_TREE;
16
kono
parents: 14
diff changeset
202 stmt = as_a <gcond *> (last);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
203
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
204 /* To keep the things simple, we do not directly remove the conditions,
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
205 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
206 loop where we would unswitch again on such a condition. */
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
207 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
208 return NULL_TREE;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
209
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
210 /* Condition must be invariant. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
211 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
213 def = SSA_NAME_DEF_STMT (use);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
214 def_bb = gimple_bb (def);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
215 if (def_bb
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
216 && flow_bb_inside_loop_p (loop, def_bb))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
217 return NULL_TREE;
16
kono
parents: 14
diff changeset
218 /* Unswitching on undefined values would introduce undefined
kono
parents: 14
diff changeset
219 behavior that the original program might never exercise. */
kono
parents: 14
diff changeset
220 if (is_maybe_undefined (use, stmt, loop))
kono
parents: 14
diff changeset
221 return NULL_TREE;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
222 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
223
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
224 cond = build2 (gimple_cond_code (stmt), boolean_type_node,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
225 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
226
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
227 return cond;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
229
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
230 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
231 simplish (sufficient to prevent us from duplicating loop in unswitching
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 unnecessarily). */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
233
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
234 static tree
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
235 simplify_using_entry_checks (struct loop *loop, tree cond)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
236 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
237 edge e = loop_preheader_edge (loop);
16
kono
parents: 14
diff changeset
238 gimple *stmt;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
239
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
240 while (1)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
241 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
242 stmt = last_stmt (e->src);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
243 if (stmt
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
244 && gimple_code (stmt) == GIMPLE_COND
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
245 && gimple_cond_code (stmt) == TREE_CODE (cond)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
246 && operand_equal_p (gimple_cond_lhs (stmt),
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
247 TREE_OPERAND (cond, 0), 0)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
248 && operand_equal_p (gimple_cond_rhs (stmt),
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
249 TREE_OPERAND (cond, 1), 0))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
250 return (e->flags & EDGE_TRUE_VALUE
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
251 ? boolean_true_node
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
252 : boolean_false_node);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
253
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
254 if (!single_pred_p (e->src))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
255 return cond;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
256
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
257 e = single_pred_edge (e->src);
16
kono
parents: 14
diff changeset
258 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
259 return cond;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
260 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
261 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
262
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
263 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
264 it to grow too much, it is too easy to create example on that the code would
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
265 grow exponentially. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
266
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
267 static bool
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
268 tree_unswitch_single_loop (struct loop *loop, int num)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
269 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
270 basic_block *bbs;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
271 struct loop *nloop;
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
272 unsigned i, found;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
273 tree cond = NULL_TREE;
16
kono
parents: 14
diff changeset
274 gimple *stmt;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
275 bool changed = false;
16
kono
parents: 14
diff changeset
276 HOST_WIDE_INT iterations;
kono
parents: 14
diff changeset
277
kono
parents: 14
diff changeset
278 /* Perform initial tests if unswitch is eligible. */
kono
parents: 14
diff changeset
279 if (num == 0)
kono
parents: 14
diff changeset
280 {
kono
parents: 14
diff changeset
281 /* Do not unswitch in cold regions. */
kono
parents: 14
diff changeset
282 if (optimize_loop_for_size_p (loop))
kono
parents: 14
diff changeset
283 {
kono
parents: 14
diff changeset
284 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
285 fprintf (dump_file, ";; Not unswitching cold loops\n");
kono
parents: 14
diff changeset
286 return false;
kono
parents: 14
diff changeset
287 }
kono
parents: 14
diff changeset
288
kono
parents: 14
diff changeset
289 /* The loop should not be too large, to limit code growth. */
kono
parents: 14
diff changeset
290 if (tree_num_loop_insns (loop, &eni_size_weights)
kono
parents: 14
diff changeset
291 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
kono
parents: 14
diff changeset
292 {
kono
parents: 14
diff changeset
293 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
294 fprintf (dump_file, ";; Not unswitching, loop too big\n");
kono
parents: 14
diff changeset
295 return false;
kono
parents: 14
diff changeset
296 }
kono
parents: 14
diff changeset
297
kono
parents: 14
diff changeset
298 /* If the loop is not expected to iterate, there is no need
kono
parents: 14
diff changeset
299 for unswitching. */
kono
parents: 14
diff changeset
300 iterations = estimated_loop_iterations_int (loop);
kono
parents: 14
diff changeset
301 if (iterations < 0)
kono
parents: 14
diff changeset
302 iterations = likely_max_loop_iterations_int (loop);
kono
parents: 14
diff changeset
303 if (iterations >= 0 && iterations <= 1)
kono
parents: 14
diff changeset
304 {
kono
parents: 14
diff changeset
305 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
306 fprintf (dump_file, ";; Not unswitching, loop is not expected"
kono
parents: 14
diff changeset
307 " to iterate\n");
kono
parents: 14
diff changeset
308 return false;
kono
parents: 14
diff changeset
309 }
kono
parents: 14
diff changeset
310 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
311
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
312 i = 0;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
313 bbs = get_loop_body (loop);
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
314 found = loop->num_nodes;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
315
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
316 while (1)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
317 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
318 /* Find a bb to unswitch on. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
319 for (; i < loop->num_nodes; i++)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
320 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
321 break;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
322
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
323 if (i == loop->num_nodes)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
324 {
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
325 if (dump_file
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
326 && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
327 && (dump_flags & TDF_DETAILS))
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
328 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
329
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
330 if (found == loop->num_nodes)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
331 {
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
332 free (bbs);
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
333 return changed;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
334 }
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
335 break;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
336 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
337
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
338 cond = simplify_using_entry_checks (loop, cond);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
339 stmt = last_stmt (bbs[i]);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
340 if (integer_nonzerop (cond))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
341 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
342 /* Remove false path. */
16
kono
parents: 14
diff changeset
343 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
kono
parents: 14
diff changeset
344 boolean_true_node);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
345 changed = true;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
346 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
347 else if (integer_zerop (cond))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
348 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
349 /* Remove true path. */
16
kono
parents: 14
diff changeset
350 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
kono
parents: 14
diff changeset
351 boolean_false_node);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
352 changed = true;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
353 }
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
354 /* Do not unswitch too much. */
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
355 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
356 {
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
357 i++;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
358 continue;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
359 }
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
360 /* In nested tree_unswitch_single_loop first optimize all conditions
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
361 using entry checks, then discover still reachable blocks in the
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
362 loop and find the condition only among those still reachable bbs. */
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
363 else if (num != 0)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
364 {
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
365 if (found == loop->num_nodes)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
366 found = i;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
367 i++;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
368 continue;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
369 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
370 else
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
371 {
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
372 found = i;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
373 break;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
374 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
375
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
376 update_stmt (stmt);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
377 i++;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
378 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
379
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
380 if (num != 0)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
381 {
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
382 basic_block *tos, *worklist;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
383
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
384 /* When called recursively, first do a quick discovery
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
385 of reachable bbs after the above changes and only
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
386 consider conditions in still reachable bbs. */
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
387 tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
388
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
389 for (i = 0; i < loop->num_nodes; i++)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
390 bbs[i]->flags &= ~BB_REACHABLE;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
391
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
392 /* Start with marking header. */
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
393 *tos++ = bbs[0];
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
394 bbs[0]->flags |= BB_REACHABLE;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
395
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
396 /* Iterate: find everything reachable from what we've already seen
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
397 within the same innermost loop. Don't look through false edges
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
398 if condition is always true or true edges if condition is
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
399 always false. */
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
400 while (tos != worklist)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
401 {
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
402 basic_block b = *--tos;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
403 edge e;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
404 edge_iterator ei;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
405 int flags = 0;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
406
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
407 if (EDGE_COUNT (b->succs) == 2)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
408 {
16
kono
parents: 14
diff changeset
409 gimple *stmt = last_stmt (b);
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
410 if (stmt
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
411 && gimple_code (stmt) == GIMPLE_COND)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
412 {
16
kono
parents: 14
diff changeset
413 gcond *cond_stmt = as_a <gcond *> (stmt);
kono
parents: 14
diff changeset
414 if (gimple_cond_true_p (cond_stmt))
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
415 flags = EDGE_FALSE_VALUE;
16
kono
parents: 14
diff changeset
416 else if (gimple_cond_false_p (cond_stmt))
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
417 flags = EDGE_TRUE_VALUE;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
418 }
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
419 }
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
420
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
421 FOR_EACH_EDGE (e, ei, b->succs)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
422 {
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
423 basic_block dest = e->dest;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
424
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
425 if (dest->loop_father == loop
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
426 && !(dest->flags & BB_REACHABLE)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
427 && !(e->flags & flags))
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
428 {
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
429 *tos++ = dest;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
430 dest->flags |= BB_REACHABLE;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
431 }
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
432 }
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
433 }
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
434
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
435 free (worklist);
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
436
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
437 /* Find a bb to unswitch on. */
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
438 for (; found < loop->num_nodes; found++)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
439 if ((bbs[found]->flags & BB_REACHABLE)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
440 && (cond = tree_may_unswitch_on (bbs[found], loop)))
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
441 break;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
442
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
443 if (found == loop->num_nodes)
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
444 {
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
445 free (bbs);
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
446 return changed;
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
447 }
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
448 }
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
449
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
450 if (dump_file && (dump_flags & TDF_DETAILS))
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
451 fprintf (dump_file, ";; Unswitching loop\n");
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
452
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
453 initialize_original_copy_tables ();
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
454 /* Unswitch the loop on this condition. */
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
455 nloop = tree_unswitch_loop (loop, bbs[found], cond);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
456 if (!nloop)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
457 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
458 free_original_copy_tables ();
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
459 free (bbs);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
460 return changed;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
461 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
462
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
463 /* Update the SSA form after unswitching. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
464 update_ssa (TODO_update_ssa);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
465 free_original_copy_tables ();
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
466
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
467 /* Invoke itself on modified loops. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
468 tree_unswitch_single_loop (nloop, num + 1);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
469 tree_unswitch_single_loop (loop, num + 1);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
470 free (bbs);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
471 return true;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
472 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
473
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
474 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
475 unswitching of innermost loops. COND is the condition determining which
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
476 loop is entered -- the new loop is entered if COND is true. Returns NULL
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
477 if impossible, new loop otherwise. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
478
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
479 static struct loop *
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
480 tree_unswitch_loop (struct loop *loop,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
481 basic_block unswitch_on, tree cond)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
482 {
16
kono
parents: 14
diff changeset
483 profile_probability prob_true;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
484 edge edge_true, edge_false;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
485
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
486 /* Some sanity checking. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
487 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
488 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
489 gcc_assert (loop->inner == NULL);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
490
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
491 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
492 prob_true = edge_true->probability;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
493 return loop_version (loop, unshare_expr (cond),
16
kono
parents: 14
diff changeset
494 NULL, prob_true,
kono
parents: 14
diff changeset
495 prob_true.invert (),
kono
parents: 14
diff changeset
496 prob_true, prob_true.invert (),
kono
parents: 14
diff changeset
497 false);
kono
parents: 14
diff changeset
498 }
kono
parents: 14
diff changeset
499
kono
parents: 14
diff changeset
500 /* Unswitch outer loops by hoisting invariant guard on
kono
parents: 14
diff changeset
501 inner loop without code duplication. */
kono
parents: 14
diff changeset
502 static bool
kono
parents: 14
diff changeset
503 tree_unswitch_outer_loop (struct loop *loop)
kono
parents: 14
diff changeset
504 {
kono
parents: 14
diff changeset
505 edge exit, guard;
kono
parents: 14
diff changeset
506 HOST_WIDE_INT iterations;
kono
parents: 14
diff changeset
507
kono
parents: 14
diff changeset
508 gcc_assert (loop->inner);
kono
parents: 14
diff changeset
509 if (loop->inner->next)
kono
parents: 14
diff changeset
510 return false;
kono
parents: 14
diff changeset
511 /* Accept loops with single exit only which is not from inner loop. */
kono
parents: 14
diff changeset
512 exit = single_exit (loop);
kono
parents: 14
diff changeset
513 if (!exit || exit->src->loop_father != loop)
kono
parents: 14
diff changeset
514 return false;
kono
parents: 14
diff changeset
515 /* Check that phi argument of exit edge is not defined inside loop. */
kono
parents: 14
diff changeset
516 if (!check_exit_phi (loop))
kono
parents: 14
diff changeset
517 return false;
kono
parents: 14
diff changeset
518 /* If the loop is not expected to iterate, there is no need
kono
parents: 14
diff changeset
519 for unswitching. */
kono
parents: 14
diff changeset
520 iterations = estimated_loop_iterations_int (loop);
kono
parents: 14
diff changeset
521 if (iterations < 0)
kono
parents: 14
diff changeset
522 iterations = likely_max_loop_iterations_int (loop);
kono
parents: 14
diff changeset
523 if (iterations >= 0 && iterations <= 1)
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 fprintf (dump_file, ";; Not unswitching, loop is not expected"
kono
parents: 14
diff changeset
527 " to iterate\n");
kono
parents: 14
diff changeset
528 return false;
kono
parents: 14
diff changeset
529 }
kono
parents: 14
diff changeset
530
kono
parents: 14
diff changeset
531 bool changed = false;
kono
parents: 14
diff changeset
532 while ((guard = find_loop_guard (loop)))
kono
parents: 14
diff changeset
533 {
kono
parents: 14
diff changeset
534 if (! changed)
kono
parents: 14
diff changeset
535 rewrite_virtuals_into_loop_closed_ssa (loop);
kono
parents: 14
diff changeset
536 hoist_guard (loop, guard);
kono
parents: 14
diff changeset
537 changed = true;
kono
parents: 14
diff changeset
538 }
kono
parents: 14
diff changeset
539 return changed;
kono
parents: 14
diff changeset
540 }
kono
parents: 14
diff changeset
541
kono
parents: 14
diff changeset
542 /* Checks if the body of the LOOP is within an invariant guard. If this
kono
parents: 14
diff changeset
543 is the case, returns the edge that jumps over the real body of the loop,
kono
parents: 14
diff changeset
544 otherwise returns NULL. */
kono
parents: 14
diff changeset
545
kono
parents: 14
diff changeset
546 static edge
kono
parents: 14
diff changeset
547 find_loop_guard (struct loop *loop)
kono
parents: 14
diff changeset
548 {
kono
parents: 14
diff changeset
549 basic_block header = loop->header;
kono
parents: 14
diff changeset
550 edge guard_edge, te, fe;
kono
parents: 14
diff changeset
551 basic_block *body = NULL;
kono
parents: 14
diff changeset
552 unsigned i;
kono
parents: 14
diff changeset
553 tree use;
kono
parents: 14
diff changeset
554 ssa_op_iter iter;
kono
parents: 14
diff changeset
555
kono
parents: 14
diff changeset
556 /* We check for the following situation:
kono
parents: 14
diff changeset
557
kono
parents: 14
diff changeset
558 while (1)
kono
parents: 14
diff changeset
559 {
kono
parents: 14
diff changeset
560 [header]]
kono
parents: 14
diff changeset
561 loop_phi_nodes;
kono
parents: 14
diff changeset
562 something1;
kono
parents: 14
diff changeset
563 if (cond1)
kono
parents: 14
diff changeset
564 body;
kono
parents: 14
diff changeset
565 nvar = phi(orig, bvar) ... for all variables changed in body;
kono
parents: 14
diff changeset
566 [guard_end]
kono
parents: 14
diff changeset
567 something2;
kono
parents: 14
diff changeset
568 if (cond2)
kono
parents: 14
diff changeset
569 break;
kono
parents: 14
diff changeset
570 something3;
kono
parents: 14
diff changeset
571 }
kono
parents: 14
diff changeset
572
kono
parents: 14
diff changeset
573 where:
kono
parents: 14
diff changeset
574
kono
parents: 14
diff changeset
575 1) cond1 is loop invariant
kono
parents: 14
diff changeset
576 2) If cond1 is false, then the loop is essentially empty; i.e.,
kono
parents: 14
diff changeset
577 a) nothing in something1, something2 and something3 has side
kono
parents: 14
diff changeset
578 effects
kono
parents: 14
diff changeset
579 b) anything defined in something1, something2 and something3
kono
parents: 14
diff changeset
580 is not used outside of the loop. */
kono
parents: 14
diff changeset
581
kono
parents: 14
diff changeset
582 gcond *cond;
kono
parents: 14
diff changeset
583 do
kono
parents: 14
diff changeset
584 {
kono
parents: 14
diff changeset
585 basic_block next = NULL;
kono
parents: 14
diff changeset
586 if (single_succ_p (header))
kono
parents: 14
diff changeset
587 next = single_succ (header);
kono
parents: 14
diff changeset
588 else
kono
parents: 14
diff changeset
589 {
kono
parents: 14
diff changeset
590 cond = dyn_cast <gcond *> (last_stmt (header));
kono
parents: 14
diff changeset
591 if (! cond)
kono
parents: 14
diff changeset
592 return NULL;
kono
parents: 14
diff changeset
593 extract_true_false_edges_from_block (header, &te, &fe);
kono
parents: 14
diff changeset
594 /* Make sure to skip earlier hoisted guards that are left
kono
parents: 14
diff changeset
595 in place as if (true). */
kono
parents: 14
diff changeset
596 if (gimple_cond_true_p (cond))
kono
parents: 14
diff changeset
597 next = te->dest;
kono
parents: 14
diff changeset
598 else if (gimple_cond_false_p (cond))
kono
parents: 14
diff changeset
599 next = fe->dest;
kono
parents: 14
diff changeset
600 else
kono
parents: 14
diff changeset
601 break;
kono
parents: 14
diff changeset
602 }
kono
parents: 14
diff changeset
603 /* Never traverse a backedge. */
kono
parents: 14
diff changeset
604 if (header->loop_father->header == next)
kono
parents: 14
diff changeset
605 return NULL;
kono
parents: 14
diff changeset
606 header = next;
kono
parents: 14
diff changeset
607 }
kono
parents: 14
diff changeset
608 while (1);
kono
parents: 14
diff changeset
609 if (!flow_bb_inside_loop_p (loop, te->dest)
kono
parents: 14
diff changeset
610 || !flow_bb_inside_loop_p (loop, fe->dest))
kono
parents: 14
diff changeset
611 return NULL;
kono
parents: 14
diff changeset
612
kono
parents: 14
diff changeset
613 if (just_once_each_iteration_p (loop, te->dest)
kono
parents: 14
diff changeset
614 || (single_succ_p (te->dest)
kono
parents: 14
diff changeset
615 && just_once_each_iteration_p (loop, single_succ (te->dest))))
kono
parents: 14
diff changeset
616 {
kono
parents: 14
diff changeset
617 if (just_once_each_iteration_p (loop, fe->dest))
kono
parents: 14
diff changeset
618 return NULL;
kono
parents: 14
diff changeset
619 guard_edge = te;
kono
parents: 14
diff changeset
620 }
kono
parents: 14
diff changeset
621 else if (just_once_each_iteration_p (loop, fe->dest)
kono
parents: 14
diff changeset
622 || (single_succ_p (fe->dest)
kono
parents: 14
diff changeset
623 && just_once_each_iteration_p (loop, single_succ (fe->dest))))
kono
parents: 14
diff changeset
624 guard_edge = fe;
kono
parents: 14
diff changeset
625 else
kono
parents: 14
diff changeset
626 return NULL;
kono
parents: 14
diff changeset
627
kono
parents: 14
diff changeset
628 /* Guard edge must skip inner loop. */
kono
parents: 14
diff changeset
629 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
kono
parents: 14
diff changeset
630 guard_edge == fe ? te->dest : fe->dest))
kono
parents: 14
diff changeset
631 {
kono
parents: 14
diff changeset
632 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
633 fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n",
kono
parents: 14
diff changeset
634 guard_edge->src->index, guard_edge->dest->index);
kono
parents: 14
diff changeset
635 return NULL;
kono
parents: 14
diff changeset
636 }
kono
parents: 14
diff changeset
637 if (guard_edge->dest == loop->latch)
kono
parents: 14
diff changeset
638 {
kono
parents: 14
diff changeset
639 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
640 fprintf (dump_file, "Guard edge destination is loop latch.\n");
kono
parents: 14
diff changeset
641 return NULL;
kono
parents: 14
diff changeset
642 }
kono
parents: 14
diff changeset
643
kono
parents: 14
diff changeset
644 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
645 fprintf (dump_file,
kono
parents: 14
diff changeset
646 "Considering guard %d -> %d in loop %d\n",
kono
parents: 14
diff changeset
647 guard_edge->src->index, guard_edge->dest->index, loop->num);
kono
parents: 14
diff changeset
648 /* Check if condition operands do not have definitions inside loop since
kono
parents: 14
diff changeset
649 any bb copying is not performed. */
kono
parents: 14
diff changeset
650 FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
kono
parents: 14
diff changeset
651 {
kono
parents: 14
diff changeset
652 gimple *def = SSA_NAME_DEF_STMT (use);
kono
parents: 14
diff changeset
653 basic_block def_bb = gimple_bb (def);
kono
parents: 14
diff changeset
654 if (def_bb
kono
parents: 14
diff changeset
655 && flow_bb_inside_loop_p (loop, def_bb))
kono
parents: 14
diff changeset
656 {
kono
parents: 14
diff changeset
657 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
658 fprintf (dump_file, " guard operands have definitions"
kono
parents: 14
diff changeset
659 " inside loop\n");
kono
parents: 14
diff changeset
660 return NULL;
kono
parents: 14
diff changeset
661 }
kono
parents: 14
diff changeset
662 }
kono
parents: 14
diff changeset
663
kono
parents: 14
diff changeset
664 body = get_loop_body (loop);
kono
parents: 14
diff changeset
665 for (i = 0; i < loop->num_nodes; i++)
kono
parents: 14
diff changeset
666 {
kono
parents: 14
diff changeset
667 basic_block bb = body[i];
kono
parents: 14
diff changeset
668 if (bb->loop_father != loop)
kono
parents: 14
diff changeset
669 continue;
kono
parents: 14
diff changeset
670 if (bb->flags & BB_IRREDUCIBLE_LOOP)
kono
parents: 14
diff changeset
671 {
kono
parents: 14
diff changeset
672 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
673 fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
kono
parents: 14
diff changeset
674 bb->index);
kono
parents: 14
diff changeset
675 guard_edge = NULL;
kono
parents: 14
diff changeset
676 goto end;
kono
parents: 14
diff changeset
677 }
kono
parents: 14
diff changeset
678 if (!empty_bb_without_guard_p (loop, bb))
kono
parents: 14
diff changeset
679 {
kono
parents: 14
diff changeset
680 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
681 fprintf (dump_file, " block %d has side effects\n", bb->index);
kono
parents: 14
diff changeset
682 guard_edge = NULL;
kono
parents: 14
diff changeset
683 goto end;
kono
parents: 14
diff changeset
684 }
kono
parents: 14
diff changeset
685 }
kono
parents: 14
diff changeset
686
kono
parents: 14
diff changeset
687 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
688 fprintf (dump_file, " suitable to hoist\n");
kono
parents: 14
diff changeset
689 end:
kono
parents: 14
diff changeset
690 if (body)
kono
parents: 14
diff changeset
691 free (body);
kono
parents: 14
diff changeset
692 return guard_edge;
kono
parents: 14
diff changeset
693 }
kono
parents: 14
diff changeset
694
kono
parents: 14
diff changeset
695 /* Returns true if
kono
parents: 14
diff changeset
696 1) no statement in BB has side effects
kono
parents: 14
diff changeset
697 2) assuming that edge GUARD is always taken, all definitions in BB
kono
parents: 14
diff changeset
698 are noy used outside of the loop.
kono
parents: 14
diff changeset
699 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
kono
parents: 14
diff changeset
700 PROCESSED is a set of ssa names for that we already tested whether they
kono
parents: 14
diff changeset
701 are invariant or not. */
kono
parents: 14
diff changeset
702
kono
parents: 14
diff changeset
703 static bool
kono
parents: 14
diff changeset
704 empty_bb_without_guard_p (struct loop *loop, basic_block bb)
kono
parents: 14
diff changeset
705 {
kono
parents: 14
diff changeset
706 basic_block exit_bb = single_exit (loop)->src;
kono
parents: 14
diff changeset
707 bool may_be_used_outside = (bb == exit_bb
kono
parents: 14
diff changeset
708 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
kono
parents: 14
diff changeset
709 tree name;
kono
parents: 14
diff changeset
710 ssa_op_iter op_iter;
kono
parents: 14
diff changeset
711
kono
parents: 14
diff changeset
712 /* Phi nodes do not have side effects, but their results might be used
kono
parents: 14
diff changeset
713 outside of the loop. */
kono
parents: 14
diff changeset
714 if (may_be_used_outside)
kono
parents: 14
diff changeset
715 {
kono
parents: 14
diff changeset
716 for (gphi_iterator gsi = gsi_start_phis (bb);
kono
parents: 14
diff changeset
717 !gsi_end_p (gsi); gsi_next (&gsi))
kono
parents: 14
diff changeset
718 {
kono
parents: 14
diff changeset
719 gphi *phi = gsi.phi ();
kono
parents: 14
diff changeset
720 name = PHI_RESULT (phi);
kono
parents: 14
diff changeset
721 if (virtual_operand_p (name))
kono
parents: 14
diff changeset
722 continue;
kono
parents: 14
diff changeset
723
kono
parents: 14
diff changeset
724 if (used_outside_loop_p (loop, name))
kono
parents: 14
diff changeset
725 return false;
kono
parents: 14
diff changeset
726 }
kono
parents: 14
diff changeset
727 }
kono
parents: 14
diff changeset
728
kono
parents: 14
diff changeset
729 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
kono
parents: 14
diff changeset
730 !gsi_end_p (gsi); gsi_next (&gsi))
kono
parents: 14
diff changeset
731 {
kono
parents: 14
diff changeset
732 gimple *stmt = gsi_stmt (gsi);
kono
parents: 14
diff changeset
733 if (gimple_has_side_effects (stmt))
kono
parents: 14
diff changeset
734 return false;
kono
parents: 14
diff changeset
735
kono
parents: 14
diff changeset
736 if (gimple_vdef(stmt))
kono
parents: 14
diff changeset
737 return false;
kono
parents: 14
diff changeset
738
kono
parents: 14
diff changeset
739 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
kono
parents: 14
diff changeset
740 {
kono
parents: 14
diff changeset
741 if (may_be_used_outside
kono
parents: 14
diff changeset
742 && used_outside_loop_p (loop, name))
kono
parents: 14
diff changeset
743 return false;
kono
parents: 14
diff changeset
744 }
kono
parents: 14
diff changeset
745 }
kono
parents: 14
diff changeset
746 return true;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
747 }
16
kono
parents: 14
diff changeset
748
kono
parents: 14
diff changeset
749 /* Return true if NAME is used outside of LOOP. */
kono
parents: 14
diff changeset
750
kono
parents: 14
diff changeset
751 static bool
kono
parents: 14
diff changeset
752 used_outside_loop_p (struct loop *loop, tree name)
kono
parents: 14
diff changeset
753 {
kono
parents: 14
diff changeset
754 imm_use_iterator it;
kono
parents: 14
diff changeset
755 use_operand_p use;
kono
parents: 14
diff changeset
756
kono
parents: 14
diff changeset
757 FOR_EACH_IMM_USE_FAST (use, it, name)
kono
parents: 14
diff changeset
758 {
kono
parents: 14
diff changeset
759 gimple *stmt = USE_STMT (use);
kono
parents: 14
diff changeset
760 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
kono
parents: 14
diff changeset
761 return true;
kono
parents: 14
diff changeset
762 }
kono
parents: 14
diff changeset
763
kono
parents: 14
diff changeset
764 return false;
kono
parents: 14
diff changeset
765 }
kono
parents: 14
diff changeset
766
kono
parents: 14
diff changeset
767 /* Return argument for loop preheader edge in header virtual phi if any. */
kono
parents: 14
diff changeset
768
kono
parents: 14
diff changeset
769 static tree
kono
parents: 14
diff changeset
770 get_vop_from_header (struct loop *loop)
kono
parents: 14
diff changeset
771 {
kono
parents: 14
diff changeset
772 for (gphi_iterator gsi = gsi_start_phis (loop->header);
kono
parents: 14
diff changeset
773 !gsi_end_p (gsi); gsi_next (&gsi))
kono
parents: 14
diff changeset
774 {
kono
parents: 14
diff changeset
775 gphi *phi = gsi.phi ();
kono
parents: 14
diff changeset
776 if (!virtual_operand_p (gimple_phi_result (phi)))
kono
parents: 14
diff changeset
777 continue;
kono
parents: 14
diff changeset
778 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
kono
parents: 14
diff changeset
779 }
kono
parents: 14
diff changeset
780 return NULL_TREE;
kono
parents: 14
diff changeset
781 }
kono
parents: 14
diff changeset
782
kono
parents: 14
diff changeset
783 /* Move the check of GUARD outside of LOOP. */
kono
parents: 14
diff changeset
784
kono
parents: 14
diff changeset
785 static void
kono
parents: 14
diff changeset
786 hoist_guard (struct loop *loop, edge guard)
kono
parents: 14
diff changeset
787 {
kono
parents: 14
diff changeset
788 edge exit = single_exit (loop);
kono
parents: 14
diff changeset
789 edge preh = loop_preheader_edge (loop);
kono
parents: 14
diff changeset
790 basic_block pre_header = preh->src;
kono
parents: 14
diff changeset
791 basic_block bb;
kono
parents: 14
diff changeset
792 edge te, fe, e, new_edge;
kono
parents: 14
diff changeset
793 gimple *stmt;
kono
parents: 14
diff changeset
794 basic_block guard_bb = guard->src;
kono
parents: 14
diff changeset
795 edge not_guard;
kono
parents: 14
diff changeset
796 gimple_stmt_iterator gsi;
kono
parents: 14
diff changeset
797 int flags = 0;
kono
parents: 14
diff changeset
798 bool fix_dom_of_exit;
kono
parents: 14
diff changeset
799 gcond *cond_stmt, *new_cond_stmt;
kono
parents: 14
diff changeset
800
kono
parents: 14
diff changeset
801 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
kono
parents: 14
diff changeset
802 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
kono
parents: 14
diff changeset
803 gsi = gsi_last_bb (guard_bb);
kono
parents: 14
diff changeset
804 stmt = gsi_stmt (gsi);
kono
parents: 14
diff changeset
805 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
kono
parents: 14
diff changeset
806 cond_stmt = as_a <gcond *> (stmt);
kono
parents: 14
diff changeset
807 extract_true_false_edges_from_block (guard_bb, &te, &fe);
kono
parents: 14
diff changeset
808 /* Insert guard to PRE_HEADER. */
kono
parents: 14
diff changeset
809 if (!empty_block_p (pre_header))
kono
parents: 14
diff changeset
810 gsi = gsi_last_bb (pre_header);
kono
parents: 14
diff changeset
811 else
kono
parents: 14
diff changeset
812 gsi = gsi_start_bb (pre_header);
kono
parents: 14
diff changeset
813 /* Create copy of COND_STMT. */
kono
parents: 14
diff changeset
814 new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
kono
parents: 14
diff changeset
815 gimple_cond_lhs (cond_stmt),
kono
parents: 14
diff changeset
816 gimple_cond_rhs (cond_stmt),
kono
parents: 14
diff changeset
817 NULL_TREE, NULL_TREE);
kono
parents: 14
diff changeset
818 gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
kono
parents: 14
diff changeset
819 /* Convert COND_STMT to true/false conditional. */
kono
parents: 14
diff changeset
820 if (guard == te)
kono
parents: 14
diff changeset
821 gimple_cond_make_false (cond_stmt);
kono
parents: 14
diff changeset
822 else
kono
parents: 14
diff changeset
823 gimple_cond_make_true (cond_stmt);
kono
parents: 14
diff changeset
824 update_stmt (cond_stmt);
kono
parents: 14
diff changeset
825 /* Create new loop pre-header. */
kono
parents: 14
diff changeset
826 e = split_block (pre_header, last_stmt (pre_header));
kono
parents: 14
diff changeset
827 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
828 {
kono
parents: 14
diff changeset
829 fprintf (dump_file, " Moving guard %i->%i (prob ",
kono
parents: 14
diff changeset
830 guard->src->index, guard->dest->index);
kono
parents: 14
diff changeset
831 guard->probability.dump (dump_file);
kono
parents: 14
diff changeset
832 fprintf (dump_file, ") to bb %i, new preheader is %i\n",
kono
parents: 14
diff changeset
833 e->src->index, e->dest->index);
kono
parents: 14
diff changeset
834 }
kono
parents: 14
diff changeset
835
kono
parents: 14
diff changeset
836 gcc_assert (loop_preheader_edge (loop)->src == e->dest);
kono
parents: 14
diff changeset
837
kono
parents: 14
diff changeset
838 if (guard == fe)
kono
parents: 14
diff changeset
839 {
kono
parents: 14
diff changeset
840 e->flags = EDGE_TRUE_VALUE;
kono
parents: 14
diff changeset
841 flags |= EDGE_FALSE_VALUE;
kono
parents: 14
diff changeset
842 not_guard = te;
kono
parents: 14
diff changeset
843 }
kono
parents: 14
diff changeset
844 else
kono
parents: 14
diff changeset
845 {
kono
parents: 14
diff changeset
846 e->flags = EDGE_FALSE_VALUE;
kono
parents: 14
diff changeset
847 flags |= EDGE_TRUE_VALUE;
kono
parents: 14
diff changeset
848 not_guard = fe;
kono
parents: 14
diff changeset
849 }
kono
parents: 14
diff changeset
850 new_edge = make_edge (pre_header, exit->dest, flags);
kono
parents: 14
diff changeset
851
kono
parents: 14
diff changeset
852 /* Determine the probability that we skip the loop. Assume that loop has
kono
parents: 14
diff changeset
853 same average number of iterations regardless outcome of guard. */
kono
parents: 14
diff changeset
854 new_edge->probability = guard->probability;
kono
parents: 14
diff changeset
855 profile_count skip_count = guard->src->count > 0
kono
parents: 14
diff changeset
856 ? guard->count ().apply_scale (pre_header->count,
kono
parents: 14
diff changeset
857 guard->src->count)
kono
parents: 14
diff changeset
858 : guard->count ().apply_probability (new_edge->probability);
kono
parents: 14
diff changeset
859
kono
parents: 14
diff changeset
860 if (skip_count > e->count ())
kono
parents: 14
diff changeset
861 {
kono
parents: 14
diff changeset
862 fprintf (dump_file, " Capping count; expect profile inconsistency\n");
kono
parents: 14
diff changeset
863 skip_count = e->count ();
kono
parents: 14
diff changeset
864 }
kono
parents: 14
diff changeset
865 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
866 {
kono
parents: 14
diff changeset
867 fprintf (dump_file, " Estimated probability of skipping loop is ");
kono
parents: 14
diff changeset
868 new_edge->probability.dump (dump_file);
kono
parents: 14
diff changeset
869 fprintf (dump_file, "\n");
kono
parents: 14
diff changeset
870 }
kono
parents: 14
diff changeset
871
kono
parents: 14
diff changeset
872 /* Update profile after the transform:
kono
parents: 14
diff changeset
873
kono
parents: 14
diff changeset
874 First decrease count of path from newly hoisted loop guard
kono
parents: 14
diff changeset
875 to loop header... */
kono
parents: 14
diff changeset
876 e->probability = new_edge->probability.invert ();
kono
parents: 14
diff changeset
877 e->dest->count = e->count ();
kono
parents: 14
diff changeset
878 e->dest->frequency = EDGE_FREQUENCY (e);
kono
parents: 14
diff changeset
879
kono
parents: 14
diff changeset
880 /* ... now update profile to represent that original guard will be optimized
kono
parents: 14
diff changeset
881 away ... */
kono
parents: 14
diff changeset
882 guard->probability = profile_probability::never ();
kono
parents: 14
diff changeset
883 not_guard->probability = profile_probability::always ();
kono
parents: 14
diff changeset
884
kono
parents: 14
diff changeset
885 /* ... finally scale everything in the loop except for guarded basic blocks
kono
parents: 14
diff changeset
886 where profile does not change. */
kono
parents: 14
diff changeset
887 basic_block *body = get_loop_body (loop);
kono
parents: 14
diff changeset
888
kono
parents: 14
diff changeset
889 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
890 fprintf (dump_file, " Scaling nonguarded BBs in loop:");
kono
parents: 14
diff changeset
891 for (unsigned int i = 0; i < loop->num_nodes; i++)
kono
parents: 14
diff changeset
892 {
kono
parents: 14
diff changeset
893 basic_block bb = body[i];
kono
parents: 14
diff changeset
894 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
kono
parents: 14
diff changeset
895 {
kono
parents: 14
diff changeset
896 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
897 fprintf (dump_file, " %i", bb->index);
kono
parents: 14
diff changeset
898 if (e->probability.initialized_p ())
kono
parents: 14
diff changeset
899 scale_bbs_frequencies (&bb, 1, e->probability);
kono
parents: 14
diff changeset
900 }
kono
parents: 14
diff changeset
901 }
kono
parents: 14
diff changeset
902
kono
parents: 14
diff changeset
903 if (fix_dom_of_exit)
kono
parents: 14
diff changeset
904 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
kono
parents: 14
diff changeset
905 /* Add NEW_ADGE argument for all phi in post-header block. */
kono
parents: 14
diff changeset
906 bb = exit->dest;
kono
parents: 14
diff changeset
907 for (gphi_iterator gsi = gsi_start_phis (bb);
kono
parents: 14
diff changeset
908 !gsi_end_p (gsi); gsi_next (&gsi))
kono
parents: 14
diff changeset
909 {
kono
parents: 14
diff changeset
910 gphi *phi = gsi.phi ();
kono
parents: 14
diff changeset
911 tree arg;
kono
parents: 14
diff changeset
912 if (virtual_operand_p (gimple_phi_result (phi)))
kono
parents: 14
diff changeset
913 {
kono
parents: 14
diff changeset
914 arg = get_vop_from_header (loop);
kono
parents: 14
diff changeset
915 if (arg == NULL_TREE)
kono
parents: 14
diff changeset
916 /* Use exit edge argument. */
kono
parents: 14
diff changeset
917 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
kono
parents: 14
diff changeset
918 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
kono
parents: 14
diff changeset
919 }
kono
parents: 14
diff changeset
920 else
kono
parents: 14
diff changeset
921 {
kono
parents: 14
diff changeset
922 /* Use exit edge argument. */
kono
parents: 14
diff changeset
923 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
kono
parents: 14
diff changeset
924 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
kono
parents: 14
diff changeset
925 }
kono
parents: 14
diff changeset
926 }
kono
parents: 14
diff changeset
927
kono
parents: 14
diff changeset
928 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
929 fprintf (dump_file, "\n guard hoisted.\n");
kono
parents: 14
diff changeset
930
kono
parents: 14
diff changeset
931 free (body);
kono
parents: 14
diff changeset
932 }
kono
parents: 14
diff changeset
933
kono
parents: 14
diff changeset
934 /* Return true if phi argument for exit edge can be used
kono
parents: 14
diff changeset
935 for edge around loop. */
kono
parents: 14
diff changeset
936
kono
parents: 14
diff changeset
937 static bool
kono
parents: 14
diff changeset
938 check_exit_phi (struct loop *loop)
kono
parents: 14
diff changeset
939 {
kono
parents: 14
diff changeset
940 edge exit = single_exit (loop);
kono
parents: 14
diff changeset
941 basic_block pre_header = loop_preheader_edge (loop)->src;
kono
parents: 14
diff changeset
942
kono
parents: 14
diff changeset
943 for (gphi_iterator gsi = gsi_start_phis (exit->dest);
kono
parents: 14
diff changeset
944 !gsi_end_p (gsi); gsi_next (&gsi))
kono
parents: 14
diff changeset
945 {
kono
parents: 14
diff changeset
946 gphi *phi = gsi.phi ();
kono
parents: 14
diff changeset
947 tree arg;
kono
parents: 14
diff changeset
948 gimple *def;
kono
parents: 14
diff changeset
949 basic_block def_bb;
kono
parents: 14
diff changeset
950 if (virtual_operand_p (gimple_phi_result (phi)))
kono
parents: 14
diff changeset
951 continue;
kono
parents: 14
diff changeset
952 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
kono
parents: 14
diff changeset
953 if (TREE_CODE (arg) != SSA_NAME)
kono
parents: 14
diff changeset
954 continue;
kono
parents: 14
diff changeset
955 def = SSA_NAME_DEF_STMT (arg);
kono
parents: 14
diff changeset
956 if (!def)
kono
parents: 14
diff changeset
957 continue;
kono
parents: 14
diff changeset
958 def_bb = gimple_bb (def);
kono
parents: 14
diff changeset
959 if (!def_bb)
kono
parents: 14
diff changeset
960 continue;
kono
parents: 14
diff changeset
961 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
kono
parents: 14
diff changeset
962 /* Definition inside loop! */
kono
parents: 14
diff changeset
963 return false;
kono
parents: 14
diff changeset
964 /* Check loop closed phi invariant. */
kono
parents: 14
diff changeset
965 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
kono
parents: 14
diff changeset
966 return false;
kono
parents: 14
diff changeset
967 }
kono
parents: 14
diff changeset
968 return true;
kono
parents: 14
diff changeset
969 }
kono
parents: 14
diff changeset
970
kono
parents: 14
diff changeset
971 /* Loop unswitching pass. */
kono
parents: 14
diff changeset
972
kono
parents: 14
diff changeset
973 namespace {
kono
parents: 14
diff changeset
974
kono
parents: 14
diff changeset
975 const pass_data pass_data_tree_unswitch =
kono
parents: 14
diff changeset
976 {
kono
parents: 14
diff changeset
977 GIMPLE_PASS, /* type */
kono
parents: 14
diff changeset
978 "unswitch", /* name */
kono
parents: 14
diff changeset
979 OPTGROUP_LOOP, /* optinfo_flags */
kono
parents: 14
diff changeset
980 TV_TREE_LOOP_UNSWITCH, /* tv_id */
kono
parents: 14
diff changeset
981 PROP_cfg, /* properties_required */
kono
parents: 14
diff changeset
982 0, /* properties_provided */
kono
parents: 14
diff changeset
983 0, /* properties_destroyed */
kono
parents: 14
diff changeset
984 0, /* todo_flags_start */
kono
parents: 14
diff changeset
985 0, /* todo_flags_finish */
kono
parents: 14
diff changeset
986 };
kono
parents: 14
diff changeset
987
kono
parents: 14
diff changeset
988 class pass_tree_unswitch : public gimple_opt_pass
kono
parents: 14
diff changeset
989 {
kono
parents: 14
diff changeset
990 public:
kono
parents: 14
diff changeset
991 pass_tree_unswitch (gcc::context *ctxt)
kono
parents: 14
diff changeset
992 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
kono
parents: 14
diff changeset
993 {}
kono
parents: 14
diff changeset
994
kono
parents: 14
diff changeset
995 /* opt_pass methods: */
kono
parents: 14
diff changeset
996 virtual bool gate (function *) { return flag_unswitch_loops != 0; }
kono
parents: 14
diff changeset
997 virtual unsigned int execute (function *);
kono
parents: 14
diff changeset
998
kono
parents: 14
diff changeset
999 }; // class pass_tree_unswitch
kono
parents: 14
diff changeset
1000
kono
parents: 14
diff changeset
1001 unsigned int
kono
parents: 14
diff changeset
1002 pass_tree_unswitch::execute (function *fun)
kono
parents: 14
diff changeset
1003 {
kono
parents: 14
diff changeset
1004 if (number_of_loops (fun) <= 1)
kono
parents: 14
diff changeset
1005 return 0;
kono
parents: 14
diff changeset
1006
kono
parents: 14
diff changeset
1007 return tree_ssa_unswitch_loops ();
kono
parents: 14
diff changeset
1008 }
kono
parents: 14
diff changeset
1009
kono
parents: 14
diff changeset
1010 } // anon namespace
kono
parents: 14
diff changeset
1011
kono
parents: 14
diff changeset
1012 gimple_opt_pass *
kono
parents: 14
diff changeset
1013 make_pass_tree_unswitch (gcc::context *ctxt)
kono
parents: 14
diff changeset
1014 {
kono
parents: 14
diff changeset
1015 return new pass_tree_unswitch (ctxt);
kono
parents: 14
diff changeset
1016 }
kono
parents: 14
diff changeset
1017
kono
parents: 14
diff changeset
1018