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

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents
children 84e7813d76e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
16
kono
parents:
diff changeset
1 /* SSA Jump Threading
kono
parents:
diff changeset
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
kono
parents:
diff changeset
3
kono
parents:
diff changeset
4 This file is part of GCC.
kono
parents:
diff changeset
5
kono
parents:
diff changeset
6 GCC is free software; you can redistribute it and/or modify
kono
parents:
diff changeset
7 it under the terms of the GNU General Public License as published by
kono
parents:
diff changeset
8 the Free Software Foundation; either version 3, or (at your option)
kono
parents:
diff changeset
9 any later version.
kono
parents:
diff changeset
10
kono
parents:
diff changeset
11 GCC is distributed in the hope that it will be useful,
kono
parents:
diff changeset
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
kono
parents:
diff changeset
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
kono
parents:
diff changeset
14 GNU General Public License for more details.
kono
parents:
diff changeset
15
kono
parents:
diff changeset
16 You should have received a copy of the GNU General Public License
kono
parents:
diff changeset
17 along with GCC; see the file COPYING3. If not see
kono
parents:
diff changeset
18 <http://www.gnu.org/licenses/>. */
kono
parents:
diff changeset
19
kono
parents:
diff changeset
20 #include "config.h"
kono
parents:
diff changeset
21 #include "system.h"
kono
parents:
diff changeset
22 #include "coretypes.h"
kono
parents:
diff changeset
23 #include "backend.h"
kono
parents:
diff changeset
24 #include "predict.h"
kono
parents:
diff changeset
25 #include "tree.h"
kono
parents:
diff changeset
26 #include "gimple.h"
kono
parents:
diff changeset
27 #include "fold-const.h"
kono
parents:
diff changeset
28 #include "cfgloop.h"
kono
parents:
diff changeset
29 #include "gimple-iterator.h"
kono
parents:
diff changeset
30 #include "tree-cfg.h"
kono
parents:
diff changeset
31 #include "tree-ssa-threadupdate.h"
kono
parents:
diff changeset
32 #include "params.h"
kono
parents:
diff changeset
33 #include "tree-ssa-loop.h"
kono
parents:
diff changeset
34 #include "cfganal.h"
kono
parents:
diff changeset
35 #include "tree-pass.h"
kono
parents:
diff changeset
36 #include "gimple-ssa.h"
kono
parents:
diff changeset
37 #include "tree-phinodes.h"
kono
parents:
diff changeset
38 #include "tree-inline.h"
kono
parents:
diff changeset
39 #include "tree-vectorizer.h"
kono
parents:
diff changeset
40
kono
parents:
diff changeset
41 static int max_threaded_paths;
kono
parents:
diff changeset
42
kono
parents:
diff changeset
43 /* Simple helper to get the last statement from BB, which is assumed
kono
parents:
diff changeset
44 to be a control statement. Return NULL if the last statement is
kono
parents:
diff changeset
45 not a control statement. */
kono
parents:
diff changeset
46
kono
parents:
diff changeset
47 static gimple *
kono
parents:
diff changeset
48 get_gimple_control_stmt (basic_block bb)
kono
parents:
diff changeset
49 {
kono
parents:
diff changeset
50 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
kono
parents:
diff changeset
51
kono
parents:
diff changeset
52 if (gsi_end_p (gsi))
kono
parents:
diff changeset
53 return NULL;
kono
parents:
diff changeset
54
kono
parents:
diff changeset
55 gimple *stmt = gsi_stmt (gsi);
kono
parents:
diff changeset
56 enum gimple_code code = gimple_code (stmt);
kono
parents:
diff changeset
57 if (code == GIMPLE_COND || code == GIMPLE_SWITCH || code == GIMPLE_GOTO)
kono
parents:
diff changeset
58 return stmt;
kono
parents:
diff changeset
59 return NULL;
kono
parents:
diff changeset
60 }
kono
parents:
diff changeset
61
kono
parents:
diff changeset
62 /* Return true if the CFG contains at least one path from START_BB to
kono
parents:
diff changeset
63 END_BB. When a path is found, record in PATH the blocks from
kono
parents:
diff changeset
64 END_BB to START_BB. VISITED_BBS is used to make sure we don't fall
kono
parents:
diff changeset
65 into an infinite loop. Bound the recursion to basic blocks
kono
parents:
diff changeset
66 belonging to LOOP. */
kono
parents:
diff changeset
67
kono
parents:
diff changeset
68 static bool
kono
parents:
diff changeset
69 fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
kono
parents:
diff changeset
70 vec<basic_block> &path,
kono
parents:
diff changeset
71 hash_set<basic_block> &visited_bbs, loop_p loop)
kono
parents:
diff changeset
72 {
kono
parents:
diff changeset
73 if (loop != start_bb->loop_father)
kono
parents:
diff changeset
74 return false;
kono
parents:
diff changeset
75
kono
parents:
diff changeset
76 if (start_bb == end_bb)
kono
parents:
diff changeset
77 {
kono
parents:
diff changeset
78 path.safe_push (start_bb);
kono
parents:
diff changeset
79 return true;
kono
parents:
diff changeset
80 }
kono
parents:
diff changeset
81
kono
parents:
diff changeset
82 if (!visited_bbs.add (start_bb))
kono
parents:
diff changeset
83 {
kono
parents:
diff changeset
84 edge e;
kono
parents:
diff changeset
85 edge_iterator ei;
kono
parents:
diff changeset
86 FOR_EACH_EDGE (e, ei, start_bb->succs)
kono
parents:
diff changeset
87 if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop))
kono
parents:
diff changeset
88 {
kono
parents:
diff changeset
89 path.safe_push (start_bb);
kono
parents:
diff changeset
90 return true;
kono
parents:
diff changeset
91 }
kono
parents:
diff changeset
92 }
kono
parents:
diff changeset
93
kono
parents:
diff changeset
94 return false;
kono
parents:
diff changeset
95 }
kono
parents:
diff changeset
96
kono
parents:
diff changeset
97 /* Examine jump threading path PATH to which we want to add BBI.
kono
parents:
diff changeset
98
kono
parents:
diff changeset
99 If the resulting path is profitable to thread, then return the
kono
parents:
diff changeset
100 final taken edge from the path, NULL otherwise.
kono
parents:
diff changeset
101
kono
parents:
diff changeset
102 NAME is the SSA_NAME of the variable we found to have a constant
kono
parents:
diff changeset
103 value on PATH. ARG is the constant value of NAME on that path.
kono
parents:
diff changeset
104
kono
parents:
diff changeset
105 BBI will be appended to PATH when we have a profitable jump threading
kono
parents:
diff changeset
106 path. Callers are responsible for removing BBI from PATH in that case.
kono
parents:
diff changeset
107
kono
parents:
diff changeset
108 SPEED_P indicate that we could increase code size to improve the
kono
parents:
diff changeset
109 code path. */
kono
parents:
diff changeset
110
kono
parents:
diff changeset
111 static edge
kono
parents:
diff changeset
112 profitable_jump_thread_path (vec<basic_block> &path,
kono
parents:
diff changeset
113 basic_block bbi, tree name, tree arg,
kono
parents:
diff changeset
114 bool speed_p, bool *creates_irreducible_loop)
kono
parents:
diff changeset
115 {
kono
parents:
diff changeset
116 /* Note BBI is not in the path yet, hence the +1 in the test below
kono
parents:
diff changeset
117 to make sure BBI is accounted for in the path length test. */
kono
parents:
diff changeset
118
kono
parents:
diff changeset
119 /* We can get a length of 0 here when the statement that
kono
parents:
diff changeset
120 makes a conditional generate a compile-time constant
kono
parents:
diff changeset
121 result is in the same block as the conditional.
kono
parents:
diff changeset
122
kono
parents:
diff changeset
123 That's not really a jump threading opportunity, but instead is
kono
parents:
diff changeset
124 simple cprop & simplification. We could handle it here if we
kono
parents:
diff changeset
125 wanted by wiring up all the incoming edges. If we run this
kono
parents:
diff changeset
126 early in IPA, that might be worth doing. For now we just
kono
parents:
diff changeset
127 reject that case. */
kono
parents:
diff changeset
128 if (path.is_empty ())
kono
parents:
diff changeset
129 return NULL;
kono
parents:
diff changeset
130
kono
parents:
diff changeset
131 if (path.length () + 1 > (unsigned) PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
kono
parents:
diff changeset
132 {
kono
parents:
diff changeset
133 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
134 fprintf (dump_file, "FSM jump-thread path not considered: "
kono
parents:
diff changeset
135 "the number of basic blocks on the path "
kono
parents:
diff changeset
136 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
kono
parents:
diff changeset
137 return NULL;
kono
parents:
diff changeset
138 }
kono
parents:
diff changeset
139
kono
parents:
diff changeset
140 if (max_threaded_paths <= 0)
kono
parents:
diff changeset
141 {
kono
parents:
diff changeset
142 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
143 fprintf (dump_file, "FSM jump-thread path not considered: "
kono
parents:
diff changeset
144 "the number of previously recorded FSM paths to "
kono
parents:
diff changeset
145 "thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
kono
parents:
diff changeset
146 return NULL;
kono
parents:
diff changeset
147 }
kono
parents:
diff changeset
148
kono
parents:
diff changeset
149 /* Add BBI to the path.
kono
parents:
diff changeset
150 From this point onward, if we decide we the path is not profitable
kono
parents:
diff changeset
151 to thread, we must remove BBI from the path. */
kono
parents:
diff changeset
152 path.safe_push (bbi);
kono
parents:
diff changeset
153
kono
parents:
diff changeset
154 int n_insns = 0;
kono
parents:
diff changeset
155 gimple_stmt_iterator gsi;
kono
parents:
diff changeset
156 loop_p loop = path[0]->loop_father;
kono
parents:
diff changeset
157 bool path_crosses_loops = false;
kono
parents:
diff changeset
158 bool threaded_through_latch = false;
kono
parents:
diff changeset
159 bool multiway_branch_in_path = false;
kono
parents:
diff changeset
160 bool threaded_multiway_branch = false;
kono
parents:
diff changeset
161 bool contains_hot_bb = false;
kono
parents:
diff changeset
162
kono
parents:
diff changeset
163 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
164 fprintf (dump_file, "Checking profitability of path (backwards): ");
kono
parents:
diff changeset
165
kono
parents:
diff changeset
166 /* Count the number of instructions on the path: as these instructions
kono
parents:
diff changeset
167 will have to be duplicated, we will not record the path if there
kono
parents:
diff changeset
168 are too many instructions on the path. Also check that all the
kono
parents:
diff changeset
169 blocks in the path belong to a single loop. */
kono
parents:
diff changeset
170 for (unsigned j = 0; j < path.length (); j++)
kono
parents:
diff changeset
171 {
kono
parents:
diff changeset
172 basic_block bb = path[j];
kono
parents:
diff changeset
173
kono
parents:
diff changeset
174 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
175 fprintf (dump_file, " bb:%i", bb->index);
kono
parents:
diff changeset
176 /* Remember, blocks in the path are stored in opposite order
kono
parents:
diff changeset
177 in the PATH array. The last entry in the array represents
kono
parents:
diff changeset
178 the block with an outgoing edge that we will redirect to the
kono
parents:
diff changeset
179 jump threading path. Thus we don't care about that block's
kono
parents:
diff changeset
180 loop father, nor how many statements are in that block because
kono
parents:
diff changeset
181 it will not be copied or whether or not it ends in a multiway
kono
parents:
diff changeset
182 branch. */
kono
parents:
diff changeset
183 if (j < path.length () - 1)
kono
parents:
diff changeset
184 {
kono
parents:
diff changeset
185 int orig_n_insns = n_insns;
kono
parents:
diff changeset
186 if (bb->loop_father != loop)
kono
parents:
diff changeset
187 {
kono
parents:
diff changeset
188 path_crosses_loops = true;
kono
parents:
diff changeset
189 break;
kono
parents:
diff changeset
190 }
kono
parents:
diff changeset
191
kono
parents:
diff changeset
192 /* PHIs in the path will create degenerate PHIS in the
kono
parents:
diff changeset
193 copied path which will then get propagated away, so
kono
parents:
diff changeset
194 looking at just the duplicate path the PHIs would
kono
parents:
diff changeset
195 seem unimportant.
kono
parents:
diff changeset
196
kono
parents:
diff changeset
197 But those PHIs, because they're assignments to objects
kono
parents:
diff changeset
198 typically with lives that exist outside the thread path,
kono
parents:
diff changeset
199 will tend to generate PHIs (or at least new PHI arguments)
kono
parents:
diff changeset
200 at points where we leave the thread path and rejoin
kono
parents:
diff changeset
201 the original blocks. So we do want to account for them.
kono
parents:
diff changeset
202
kono
parents:
diff changeset
203 We ignore virtual PHIs. We also ignore cases where BB
kono
parents:
diff changeset
204 has a single incoming edge. That's the most common
kono
parents:
diff changeset
205 degenerate PHI we'll see here. Finally we ignore PHIs
kono
parents:
diff changeset
206 that are associated with the value we're tracking as
kono
parents:
diff changeset
207 that object likely dies. */
kono
parents:
diff changeset
208 if (EDGE_COUNT (bb->succs) > 1 && EDGE_COUNT (bb->preds) > 1)
kono
parents:
diff changeset
209 {
kono
parents:
diff changeset
210 for (gphi_iterator gsip = gsi_start_phis (bb);
kono
parents:
diff changeset
211 !gsi_end_p (gsip);
kono
parents:
diff changeset
212 gsi_next (&gsip))
kono
parents:
diff changeset
213 {
kono
parents:
diff changeset
214 gphi *phi = gsip.phi ();
kono
parents:
diff changeset
215 tree dst = gimple_phi_result (phi);
kono
parents:
diff changeset
216
kono
parents:
diff changeset
217 /* Note that if both NAME and DST are anonymous
kono
parents:
diff changeset
218 SSA_NAMEs, then we do not have enough information
kono
parents:
diff changeset
219 to consider them associated. */
kono
parents:
diff changeset
220 if (dst != name
kono
parents:
diff changeset
221 && (SSA_NAME_VAR (dst) != SSA_NAME_VAR (name)
kono
parents:
diff changeset
222 || !SSA_NAME_VAR (dst))
kono
parents:
diff changeset
223 && !virtual_operand_p (dst))
kono
parents:
diff changeset
224 ++n_insns;
kono
parents:
diff changeset
225 }
kono
parents:
diff changeset
226 }
kono
parents:
diff changeset
227
kono
parents:
diff changeset
228 if (!contains_hot_bb && speed_p)
kono
parents:
diff changeset
229 contains_hot_bb |= optimize_bb_for_speed_p (bb);
kono
parents:
diff changeset
230 for (gsi = gsi_after_labels (bb);
kono
parents:
diff changeset
231 !gsi_end_p (gsi);
kono
parents:
diff changeset
232 gsi_next_nondebug (&gsi))
kono
parents:
diff changeset
233 {
kono
parents:
diff changeset
234 gimple *stmt = gsi_stmt (gsi);
kono
parents:
diff changeset
235 /* Do not count empty statements and labels. */
kono
parents:
diff changeset
236 if (gimple_code (stmt) != GIMPLE_NOP
kono
parents:
diff changeset
237 && !(gimple_code (stmt) == GIMPLE_ASSIGN
kono
parents:
diff changeset
238 && gimple_assign_rhs_code (stmt) == ASSERT_EXPR)
kono
parents:
diff changeset
239 && !is_gimple_debug (stmt))
kono
parents:
diff changeset
240 n_insns += estimate_num_insns (stmt, &eni_size_weights);
kono
parents:
diff changeset
241 }
kono
parents:
diff changeset
242 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
243 fprintf (dump_file, " (%i insns)", n_insns-orig_n_insns);
kono
parents:
diff changeset
244
kono
parents:
diff changeset
245 /* We do not look at the block with the threaded branch
kono
parents:
diff changeset
246 in this loop. So if any block with a last statement that
kono
parents:
diff changeset
247 is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a
kono
parents:
diff changeset
248 multiway branch on our path.
kono
parents:
diff changeset
249
kono
parents:
diff changeset
250 The block in PATH[0] is special, it's the block were we're
kono
parents:
diff changeset
251 going to be able to eliminate its branch. */
kono
parents:
diff changeset
252 gimple *last = last_stmt (bb);
kono
parents:
diff changeset
253 if (last && (gimple_code (last) == GIMPLE_SWITCH
kono
parents:
diff changeset
254 || gimple_code (last) == GIMPLE_GOTO))
kono
parents:
diff changeset
255 {
kono
parents:
diff changeset
256 if (j == 0)
kono
parents:
diff changeset
257 threaded_multiway_branch = true;
kono
parents:
diff changeset
258 else
kono
parents:
diff changeset
259 multiway_branch_in_path = true;
kono
parents:
diff changeset
260 }
kono
parents:
diff changeset
261 }
kono
parents:
diff changeset
262
kono
parents:
diff changeset
263 /* Note if we thread through the latch, we will want to include
kono
parents:
diff changeset
264 the last entry in the array when determining if we thread
kono
parents:
diff changeset
265 through the loop latch. */
kono
parents:
diff changeset
266 if (loop->latch == bb)
kono
parents:
diff changeset
267 threaded_through_latch = true;
kono
parents:
diff changeset
268 }
kono
parents:
diff changeset
269
kono
parents:
diff changeset
270 gimple *stmt = get_gimple_control_stmt (path[0]);
kono
parents:
diff changeset
271 gcc_assert (stmt);
kono
parents:
diff changeset
272
kono
parents:
diff changeset
273 /* We are going to remove the control statement at the end of the
kono
parents:
diff changeset
274 last block in the threading path. So don't count it against our
kono
parents:
diff changeset
275 statement count. */
kono
parents:
diff changeset
276
kono
parents:
diff changeset
277 int stmt_insns = estimate_num_insns (stmt, &eni_size_weights);
kono
parents:
diff changeset
278 n_insns-= stmt_insns;
kono
parents:
diff changeset
279
kono
parents:
diff changeset
280 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
281 fprintf (dump_file, "\n Control statement insns: %i\n"
kono
parents:
diff changeset
282 " Overall: %i insns\n",
kono
parents:
diff changeset
283 stmt_insns, n_insns);
kono
parents:
diff changeset
284
kono
parents:
diff changeset
285 /* We have found a constant value for ARG. For GIMPLE_SWITCH
kono
parents:
diff changeset
286 and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND
kono
parents:
diff changeset
287 we need to substitute, fold and simplify so we can determine
kono
parents:
diff changeset
288 the edge taken out of the last block. */
kono
parents:
diff changeset
289 if (gimple_code (stmt) == GIMPLE_COND)
kono
parents:
diff changeset
290 {
kono
parents:
diff changeset
291 enum tree_code cond_code = gimple_cond_code (stmt);
kono
parents:
diff changeset
292
kono
parents:
diff changeset
293 /* We know the underyling format of the condition. */
kono
parents:
diff changeset
294 arg = fold_binary (cond_code, boolean_type_node,
kono
parents:
diff changeset
295 arg, gimple_cond_rhs (stmt));
kono
parents:
diff changeset
296 }
kono
parents:
diff changeset
297
kono
parents:
diff changeset
298 /* If this path threaded through the loop latch back into the
kono
parents:
diff changeset
299 same loop and the destination does not dominate the loop
kono
parents:
diff changeset
300 latch, then this thread would create an irreducible loop.
kono
parents:
diff changeset
301
kono
parents:
diff changeset
302 We have to know the outgoing edge to figure this out. */
kono
parents:
diff changeset
303 edge taken_edge = find_taken_edge (path[0], arg);
kono
parents:
diff changeset
304
kono
parents:
diff changeset
305 /* There are cases where we may not be able to extract the
kono
parents:
diff changeset
306 taken edge. For example, a computed goto to an absolute
kono
parents:
diff changeset
307 address. Handle those cases gracefully. */
kono
parents:
diff changeset
308 if (taken_edge == NULL)
kono
parents:
diff changeset
309 {
kono
parents:
diff changeset
310 path.pop ();
kono
parents:
diff changeset
311 return NULL;
kono
parents:
diff changeset
312 }
kono
parents:
diff changeset
313
kono
parents:
diff changeset
314 *creates_irreducible_loop = false;
kono
parents:
diff changeset
315 if (threaded_through_latch
kono
parents:
diff changeset
316 && loop == taken_edge->dest->loop_father
kono
parents:
diff changeset
317 && (determine_bb_domination_status (loop, taken_edge->dest)
kono
parents:
diff changeset
318 == DOMST_NONDOMINATING))
kono
parents:
diff changeset
319 *creates_irreducible_loop = true;
kono
parents:
diff changeset
320
kono
parents:
diff changeset
321 if (path_crosses_loops)
kono
parents:
diff changeset
322 {
kono
parents:
diff changeset
323 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
324 fprintf (dump_file, "FSM jump-thread path not considered: "
kono
parents:
diff changeset
325 "the path crosses loops.\n");
kono
parents:
diff changeset
326 path.pop ();
kono
parents:
diff changeset
327 return NULL;
kono
parents:
diff changeset
328 }
kono
parents:
diff changeset
329
kono
parents:
diff changeset
330 /* Threading is profitable if the path duplicated is hot but also
kono
parents:
diff changeset
331 in a case we separate cold path from hot path and permit optimization
kono
parents:
diff changeset
332 of the hot path later. Be on the agressive side here. In some testcases,
kono
parents:
diff changeset
333 as in PR 78407 this leads to noticeable improvements. */
kono
parents:
diff changeset
334 if (speed_p && (optimize_edge_for_speed_p (taken_edge) || contains_hot_bb))
kono
parents:
diff changeset
335 {
kono
parents:
diff changeset
336 if (n_insns >= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS))
kono
parents:
diff changeset
337 {
kono
parents:
diff changeset
338 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
339 fprintf (dump_file, "FSM jump-thread path not considered: "
kono
parents:
diff changeset
340 "the number of instructions on the path "
kono
parents:
diff changeset
341 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
kono
parents:
diff changeset
342 path.pop ();
kono
parents:
diff changeset
343 return NULL;
kono
parents:
diff changeset
344 }
kono
parents:
diff changeset
345 }
kono
parents:
diff changeset
346 else if (n_insns > 1)
kono
parents:
diff changeset
347 {
kono
parents:
diff changeset
348 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
349 fprintf (dump_file, "FSM jump-thread path not considered: "
kono
parents:
diff changeset
350 "duplication of %i insns is needed and optimizing for size.\n",
kono
parents:
diff changeset
351 n_insns);
kono
parents:
diff changeset
352 path.pop ();
kono
parents:
diff changeset
353 return NULL;
kono
parents:
diff changeset
354 }
kono
parents:
diff changeset
355
kono
parents:
diff changeset
356 /* We avoid creating irreducible inner loops unless we thread through
kono
parents:
diff changeset
357 a multiway branch, in which case we have deemed it worth losing
kono
parents:
diff changeset
358 other loop optimizations later.
kono
parents:
diff changeset
359
kono
parents:
diff changeset
360 We also consider it worth creating an irreducible inner loop if
kono
parents:
diff changeset
361 the number of copied statement is low relative to the length of
kono
parents:
diff changeset
362 the path -- in that case there's little the traditional loop
kono
parents:
diff changeset
363 optimizer would have done anyway, so an irreducible loop is not
kono
parents:
diff changeset
364 so bad. */
kono
parents:
diff changeset
365 if (!threaded_multiway_branch && *creates_irreducible_loop
kono
parents:
diff changeset
366 && (n_insns * (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
kono
parents:
diff changeset
367 > (path.length () *
kono
parents:
diff changeset
368 (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS))))
kono
parents:
diff changeset
369
kono
parents:
diff changeset
370 {
kono
parents:
diff changeset
371 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
372 fprintf (dump_file,
kono
parents:
diff changeset
373 "FSM would create irreducible loop without threading "
kono
parents:
diff changeset
374 "multiway branch.\n");
kono
parents:
diff changeset
375 path.pop ();
kono
parents:
diff changeset
376 return NULL;
kono
parents:
diff changeset
377 }
kono
parents:
diff changeset
378
kono
parents:
diff changeset
379
kono
parents:
diff changeset
380 /* If this path does not thread through the loop latch, then we are
kono
parents:
diff changeset
381 using the FSM threader to find old style jump threads. This
kono
parents:
diff changeset
382 is good, except the FSM threader does not re-use an existing
kono
parents:
diff changeset
383 threading path to reduce code duplication.
kono
parents:
diff changeset
384
kono
parents:
diff changeset
385 So for that case, drastically reduce the number of statements
kono
parents:
diff changeset
386 we are allowed to copy. */
kono
parents:
diff changeset
387 if (!(threaded_through_latch && threaded_multiway_branch)
kono
parents:
diff changeset
388 && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
kono
parents:
diff changeset
389 >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS)))
kono
parents:
diff changeset
390 {
kono
parents:
diff changeset
391 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
392 fprintf (dump_file,
kono
parents:
diff changeset
393 "FSM did not thread around loop and would copy too "
kono
parents:
diff changeset
394 "many statements.\n");
kono
parents:
diff changeset
395 path.pop ();
kono
parents:
diff changeset
396 return NULL;
kono
parents:
diff changeset
397 }
kono
parents:
diff changeset
398
kono
parents:
diff changeset
399 /* When there is a multi-way branch on the path, then threading can
kono
parents:
diff changeset
400 explode the CFG due to duplicating the edges for that multi-way
kono
parents:
diff changeset
401 branch. So like above, only allow a multi-way branch on the path
kono
parents:
diff changeset
402 if we actually thread a multi-way branch. */
kono
parents:
diff changeset
403 if (!threaded_multiway_branch && multiway_branch_in_path)
kono
parents:
diff changeset
404 {
kono
parents:
diff changeset
405 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents:
diff changeset
406 fprintf (dump_file,
kono
parents:
diff changeset
407 "FSM Thread through multiway branch without threading "
kono
parents:
diff changeset
408 "a multiway branch.\n");
kono
parents:
diff changeset
409 path.pop ();
kono
parents:
diff changeset
410 return NULL;
kono
parents:
diff changeset
411 }
kono
parents:
diff changeset
412 return taken_edge;
kono
parents:
diff changeset
413 }
kono
parents:
diff changeset
414
kono
parents:
diff changeset
415 /* PATH is vector of blocks forming a jump threading path in reverse
kono
parents:
diff changeset
416 order. TAKEN_EDGE is the edge taken from path[0].
kono
parents:
diff changeset
417
kono
parents:
diff changeset
418 Convert that path into the form used by register_jump_thread and
kono
parents:
diff changeset
419 register the path. */
kono
parents:
diff changeset
420
kono
parents:
diff changeset
421 static void
kono
parents:
diff changeset
422 convert_and_register_jump_thread_path (vec<basic_block> &path, edge taken_edge)
kono
parents:
diff changeset
423 {
kono
parents:
diff changeset
424 vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> ();
kono
parents:
diff changeset
425
kono
parents:
diff changeset
426 /* Record the edges between the blocks in PATH. */
kono
parents:
diff changeset
427 for (unsigned int j = 0; j + 1 < path.length (); j++)
kono
parents:
diff changeset
428 {
kono
parents:
diff changeset
429 basic_block bb1 = path[path.length () - j - 1];
kono
parents:
diff changeset
430 basic_block bb2 = path[path.length () - j - 2];
kono
parents:
diff changeset
431
kono
parents:
diff changeset
432 edge e = find_edge (bb1, bb2);
kono
parents:
diff changeset
433 gcc_assert (e);
kono
parents:
diff changeset
434 jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
kono
parents:
diff changeset
435 jump_thread_path->safe_push (x);
kono
parents:
diff changeset
436 }
kono
parents:
diff changeset
437
kono
parents:
diff changeset
438 /* Add the edge taken when the control variable has value ARG. */
kono
parents:
diff changeset
439 jump_thread_edge *x
kono
parents:
diff changeset
440 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
kono
parents:
diff changeset
441 jump_thread_path->safe_push (x);
kono
parents:
diff changeset
442
kono
parents:
diff changeset
443 register_jump_thread (jump_thread_path);
kono
parents:
diff changeset
444 --max_threaded_paths;
kono
parents:
diff changeset
445 }
kono
parents:
diff changeset
446
kono
parents:
diff changeset
447 /* While following a chain of SSA_NAME definitions, we jumped from a
kono
parents:
diff changeset
448 definition in LAST_BB to a definition in NEW_BB (walking
kono
parents:
diff changeset
449 backwards).
kono
parents:
diff changeset
450
kono
parents:
diff changeset
451 Verify there is a single path between the blocks and none of the
kono
parents:
diff changeset
452 blocks in the path is already in VISITED_BBS. If so, then update
kono
parents:
diff changeset
453 VISISTED_BBS, add the new blocks to PATH and return TRUE.
kono
parents:
diff changeset
454 Otherwise return FALSE.
kono
parents:
diff changeset
455
kono
parents:
diff changeset
456 Store the length of the subpath in NEXT_PATH_LENGTH. */
kono
parents:
diff changeset
457
kono
parents:
diff changeset
458 static bool
kono
parents:
diff changeset
459 check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb,
kono
parents:
diff changeset
460 hash_set<basic_block> &visited_bbs,
kono
parents:
diff changeset
461 vec<basic_block> &path,
kono
parents:
diff changeset
462 int *next_path_length)
kono
parents:
diff changeset
463 {
kono
parents:
diff changeset
464 edge e;
kono
parents:
diff changeset
465 int e_count = 0;
kono
parents:
diff changeset
466 edge_iterator ei;
kono
parents:
diff changeset
467 auto_vec<basic_block> next_path;
kono
parents:
diff changeset
468
kono
parents:
diff changeset
469 FOR_EACH_EDGE (e, ei, last_bb->preds)
kono
parents:
diff changeset
470 {
kono
parents:
diff changeset
471 hash_set<basic_block> visited_bbs;
kono
parents:
diff changeset
472
kono
parents:
diff changeset
473 if (fsm_find_thread_path (new_bb, e->src, next_path, visited_bbs,
kono
parents:
diff changeset
474 e->src->loop_father))
kono
parents:
diff changeset
475 ++e_count;
kono
parents:
diff changeset
476
kono
parents:
diff changeset
477 /* If there is more than one path, stop. */
kono
parents:
diff changeset
478 if (e_count > 1)
kono
parents:
diff changeset
479 return false;
kono
parents:
diff changeset
480 }
kono
parents:
diff changeset
481
kono
parents:
diff changeset
482 /* Stop if we have not found a path: this could occur when the recursion
kono
parents:
diff changeset
483 is stopped by one of the bounds. */
kono
parents:
diff changeset
484 if (e_count == 0)
kono
parents:
diff changeset
485 return false;
kono
parents:
diff changeset
486
kono
parents:
diff changeset
487 /* Make sure we haven't already visited any of the nodes in
kono
parents:
diff changeset
488 NEXT_PATH. Don't add them here to avoid pollution. */
kono
parents:
diff changeset
489 for (unsigned int i = 0; i + 1 < next_path.length (); i++)
kono
parents:
diff changeset
490 {
kono
parents:
diff changeset
491 if (visited_bbs.contains (next_path[i]))
kono
parents:
diff changeset
492 return false;
kono
parents:
diff changeset
493 }
kono
parents:
diff changeset
494
kono
parents:
diff changeset
495 /* Now add the nodes to VISISTED_BBS. */
kono
parents:
diff changeset
496 for (unsigned int i = 0; i + 1 < next_path.length (); i++)
kono
parents:
diff changeset
497 visited_bbs.add (next_path[i]);
kono
parents:
diff changeset
498
kono
parents:
diff changeset
499 /* Append all the nodes from NEXT_PATH to PATH. */
kono
parents:
diff changeset
500 path.safe_splice (next_path);
kono
parents:
diff changeset
501 *next_path_length = next_path.length ();
kono
parents:
diff changeset
502
kono
parents:
diff changeset
503 return true;
kono
parents:
diff changeset
504 }
kono
parents:
diff changeset
505
kono
parents:
diff changeset
506 /* If this is a profitable jump thread path, register it.
kono
parents:
diff changeset
507
kono
parents:
diff changeset
508 NAME is an SSA NAME with a possible constant value of ARG on PATH.
kono
parents:
diff changeset
509
kono
parents:
diff changeset
510 DEF_BB is the basic block that ultimately defines the constant.
kono
parents:
diff changeset
511
kono
parents:
diff changeset
512 SPEED_P indicate that we could increase code size to improve the
kono
parents:
diff changeset
513 code path.
kono
parents:
diff changeset
514 */
kono
parents:
diff changeset
515
kono
parents:
diff changeset
516 static void
kono
parents:
diff changeset
517 register_jump_thread_path_if_profitable (vec<basic_block> &path,
kono
parents:
diff changeset
518 tree name,
kono
parents:
diff changeset
519 tree arg,
kono
parents:
diff changeset
520 basic_block def_bb,
kono
parents:
diff changeset
521 bool speed_p)
kono
parents:
diff changeset
522 {
kono
parents:
diff changeset
523 if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant)
kono
parents:
diff changeset
524 return;
kono
parents:
diff changeset
525
kono
parents:
diff changeset
526 bool irreducible = false;
kono
parents:
diff changeset
527 edge taken_edge = profitable_jump_thread_path (path, def_bb, name, arg,
kono
parents:
diff changeset
528 speed_p, &irreducible);
kono
parents:
diff changeset
529 if (taken_edge)
kono
parents:
diff changeset
530 {
kono
parents:
diff changeset
531 convert_and_register_jump_thread_path (path, taken_edge);
kono
parents:
diff changeset
532 path.pop ();
kono
parents:
diff changeset
533
kono
parents:
diff changeset
534 if (irreducible)
kono
parents:
diff changeset
535 vect_free_loop_info_assumptions (path[0]->loop_father);
kono
parents:
diff changeset
536 }
kono
parents:
diff changeset
537 }
kono
parents:
diff changeset
538
kono
parents:
diff changeset
539 static void fsm_find_control_statement_thread_paths (tree,
kono
parents:
diff changeset
540 hash_set<basic_block> &,
kono
parents:
diff changeset
541 vec<basic_block> &,
kono
parents:
diff changeset
542 bool, bool);
kono
parents:
diff changeset
543
kono
parents:
diff changeset
544 /* Given PHI which defines NAME in block DEF_BB, recurse through the
kono
parents:
diff changeset
545 PHI's arguments searching for paths where NAME will ultimately have
kono
parents:
diff changeset
546 a constant value.
kono
parents:
diff changeset
547
kono
parents:
diff changeset
548 VISITED_BBS tracks the blocks that have been encountered.
kono
parents:
diff changeset
549
kono
parents:
diff changeset
550 PATH contains the series of blocks to traverse that will result in
kono
parents:
diff changeset
551 NAME having a constant value.
kono
parents:
diff changeset
552
kono
parents:
diff changeset
553 SEEN_LOOP_PHI tracks if we have recursed through a loop PHI node.
kono
parents:
diff changeset
554
kono
parents:
diff changeset
555 SPEED_P indicates if we are optimizing for speed over space. */
kono
parents:
diff changeset
556
kono
parents:
diff changeset
557 static void
kono
parents:
diff changeset
558 handle_phi (gphi *phi, tree name, basic_block def_bb,
kono
parents:
diff changeset
559 hash_set<basic_block> &visited_bbs,
kono
parents:
diff changeset
560 vec<basic_block> &path,
kono
parents:
diff changeset
561 bool seen_loop_phi, bool speed_p)
kono
parents:
diff changeset
562 {
kono
parents:
diff changeset
563 /* Iterate over the arguments of PHI. */
kono
parents:
diff changeset
564 for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
kono
parents:
diff changeset
565 {
kono
parents:
diff changeset
566 tree arg = gimple_phi_arg_def (phi, i);
kono
parents:
diff changeset
567 basic_block bbi = gimple_phi_arg_edge (phi, i)->src;
kono
parents:
diff changeset
568
kono
parents:
diff changeset
569 /* Skip edges pointing outside the current loop. */
kono
parents:
diff changeset
570 if (!arg || def_bb->loop_father != bbi->loop_father)
kono
parents:
diff changeset
571 continue;
kono
parents:
diff changeset
572
kono
parents:
diff changeset
573 if (TREE_CODE (arg) == SSA_NAME)
kono
parents:
diff changeset
574 {
kono
parents:
diff changeset
575 path.safe_push (bbi);
kono
parents:
diff changeset
576 /* Recursively follow SSA_NAMEs looking for a constant
kono
parents:
diff changeset
577 definition. */
kono
parents:
diff changeset
578 fsm_find_control_statement_thread_paths (arg, visited_bbs, path,
kono
parents:
diff changeset
579 seen_loop_phi, speed_p);
kono
parents:
diff changeset
580
kono
parents:
diff changeset
581 path.pop ();
kono
parents:
diff changeset
582 continue;
kono
parents:
diff changeset
583 }
kono
parents:
diff changeset
584
kono
parents:
diff changeset
585 register_jump_thread_path_if_profitable (path, name, arg, bbi, speed_p);
kono
parents:
diff changeset
586 }
kono
parents:
diff changeset
587 }
kono
parents:
diff changeset
588
kono
parents:
diff changeset
589 /* Return TRUE if STMT is a gimple assignment we want to either directly
kono
parents:
diff changeset
590 handle or recurse through. Return FALSE otherwise.
kono
parents:
diff changeset
591
kono
parents:
diff changeset
592 Note that adding more cases here requires adding cases to handle_assignment
kono
parents:
diff changeset
593 below. */
kono
parents:
diff changeset
594
kono
parents:
diff changeset
595 static bool
kono
parents:
diff changeset
596 handle_assignment_p (gimple *stmt)
kono
parents:
diff changeset
597 {
kono
parents:
diff changeset
598 if (is_gimple_assign (stmt))
kono
parents:
diff changeset
599 {
kono
parents:
diff changeset
600 enum tree_code def_code = gimple_assign_rhs_code (stmt);
kono
parents:
diff changeset
601
kono
parents:
diff changeset
602 /* If the RHS is an SSA_NAME, then we will recurse through it.
kono
parents:
diff changeset
603 Go ahead and filter out cases where the SSA_NAME is a default
kono
parents:
diff changeset
604 definition. There's little to be gained by trying to handle that. */
kono
parents:
diff changeset
605 if (def_code == SSA_NAME
kono
parents:
diff changeset
606 && !SSA_NAME_IS_DEFAULT_DEF (gimple_assign_rhs1 (stmt)))
kono
parents:
diff changeset
607 return true;
kono
parents:
diff changeset
608
kono
parents:
diff changeset
609 /* If the RHS is a constant, then it's a terminal that we'll want
kono
parents:
diff changeset
610 to handle as well. */
kono
parents:
diff changeset
611 if (TREE_CODE_CLASS (def_code) == tcc_constant)
kono
parents:
diff changeset
612 return true;
kono
parents:
diff changeset
613 }
kono
parents:
diff changeset
614
kono
parents:
diff changeset
615 /* Anything not explicitly allowed is not handled. */
kono
parents:
diff changeset
616 return false;
kono
parents:
diff changeset
617 }
kono
parents:
diff changeset
618
kono
parents:
diff changeset
619 /* Given STMT which defines NAME in block DEF_BB, recurse through the
kono
parents:
diff changeset
620 PHI's arguments searching for paths where NAME will ultimately have
kono
parents:
diff changeset
621 a constant value.
kono
parents:
diff changeset
622
kono
parents:
diff changeset
623 VISITED_BBS tracks the blocks that have been encountered.
kono
parents:
diff changeset
624
kono
parents:
diff changeset
625 PATH contains the series of blocks to traverse that will result in
kono
parents:
diff changeset
626 NAME having a constant value.
kono
parents:
diff changeset
627
kono
parents:
diff changeset
628 SEEN_LOOP_PHI tracks if we have recursed through a loop PHI node.
kono
parents:
diff changeset
629
kono
parents:
diff changeset
630 SPEED_P indicates if we are optimizing for speed over space. */
kono
parents:
diff changeset
631
kono
parents:
diff changeset
632 static void
kono
parents:
diff changeset
633 handle_assignment (gimple *stmt, tree name, basic_block def_bb,
kono
parents:
diff changeset
634 hash_set<basic_block> &visited_bbs,
kono
parents:
diff changeset
635 vec<basic_block> &path,
kono
parents:
diff changeset
636 bool seen_loop_phi, bool speed_p)
kono
parents:
diff changeset
637 {
kono
parents:
diff changeset
638 tree arg = gimple_assign_rhs1 (stmt);
kono
parents:
diff changeset
639
kono
parents:
diff changeset
640 if (TREE_CODE (arg) == SSA_NAME)
kono
parents:
diff changeset
641 fsm_find_control_statement_thread_paths (arg, visited_bbs,
kono
parents:
diff changeset
642 path, seen_loop_phi, speed_p);
kono
parents:
diff changeset
643
kono
parents:
diff changeset
644 else
kono
parents:
diff changeset
645 {
kono
parents:
diff changeset
646 /* register_jump_thread_path_if_profitable will push the current
kono
parents:
diff changeset
647 block onto the path. But the path will always have the current
kono
parents:
diff changeset
648 block at this point. So we can just pop it. */
kono
parents:
diff changeset
649 path.pop ();
kono
parents:
diff changeset
650
kono
parents:
diff changeset
651 register_jump_thread_path_if_profitable (path, name, arg, def_bb,
kono
parents:
diff changeset
652 speed_p);
kono
parents:
diff changeset
653
kono
parents:
diff changeset
654 /* And put the current block back onto the path so that the
kono
parents:
diff changeset
655 state of the stack is unchanged when we leave. */
kono
parents:
diff changeset
656 path.safe_push (def_bb);
kono
parents:
diff changeset
657 }
kono
parents:
diff changeset
658 }
kono
parents:
diff changeset
659
kono
parents:
diff changeset
660 /* We trace the value of the SSA_NAME NAME back through any phi nodes
kono
parents:
diff changeset
661 looking for places where it gets a constant value and save the
kono
parents:
diff changeset
662 path.
kono
parents:
diff changeset
663
kono
parents:
diff changeset
664 SPEED_P indicate that we could increase code size to improve the
kono
parents:
diff changeset
665 code path. */
kono
parents:
diff changeset
666
kono
parents:
diff changeset
667 static void
kono
parents:
diff changeset
668 fsm_find_control_statement_thread_paths (tree name,
kono
parents:
diff changeset
669 hash_set<basic_block> &visited_bbs,
kono
parents:
diff changeset
670 vec<basic_block> &path,
kono
parents:
diff changeset
671 bool seen_loop_phi, bool speed_p)
kono
parents:
diff changeset
672 {
kono
parents:
diff changeset
673 /* If NAME appears in an abnormal PHI, then don't try to trace its
kono
parents:
diff changeset
674 value back through PHI nodes. */
kono
parents:
diff changeset
675 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
kono
parents:
diff changeset
676 return;
kono
parents:
diff changeset
677
kono
parents:
diff changeset
678 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
kono
parents:
diff changeset
679 basic_block def_bb = gimple_bb (def_stmt);
kono
parents:
diff changeset
680
kono
parents:
diff changeset
681 if (def_bb == NULL)
kono
parents:
diff changeset
682 return;
kono
parents:
diff changeset
683
kono
parents:
diff changeset
684 /* We allow the SSA chain to contains PHIs and simple copies and constant
kono
parents:
diff changeset
685 initializations. */
kono
parents:
diff changeset
686 if (gimple_code (def_stmt) != GIMPLE_PHI
kono
parents:
diff changeset
687 && gimple_code (def_stmt) != GIMPLE_ASSIGN)
kono
parents:
diff changeset
688 return;
kono
parents:
diff changeset
689
kono
parents:
diff changeset
690 if (gimple_code (def_stmt) == GIMPLE_PHI
kono
parents:
diff changeset
691 && (gimple_phi_num_args (def_stmt)
kono
parents:
diff changeset
692 >= (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS)))
kono
parents:
diff changeset
693 return;
kono
parents:
diff changeset
694
kono
parents:
diff changeset
695 if (is_gimple_assign (def_stmt)
kono
parents:
diff changeset
696 && ! handle_assignment_p (def_stmt))
kono
parents:
diff changeset
697 return;
kono
parents:
diff changeset
698
kono
parents:
diff changeset
699 /* Avoid infinite recursion. */
kono
parents:
diff changeset
700 if (visited_bbs.add (def_bb))
kono
parents:
diff changeset
701 return;
kono
parents:
diff changeset
702
kono
parents:
diff changeset
703 int next_path_length = 0;
kono
parents:
diff changeset
704 basic_block last_bb_in_path = path.last ();
kono
parents:
diff changeset
705
kono
parents:
diff changeset
706 if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt))
kono
parents:
diff changeset
707 {
kono
parents:
diff changeset
708 /* Do not walk through more than one loop PHI node. */
kono
parents:
diff changeset
709 if (seen_loop_phi)
kono
parents:
diff changeset
710 return;
kono
parents:
diff changeset
711 seen_loop_phi = true;
kono
parents:
diff changeset
712 }
kono
parents:
diff changeset
713
kono
parents:
diff changeset
714 /* Following the chain of SSA_NAME definitions, we jumped from a definition in
kono
parents:
diff changeset
715 LAST_BB_IN_PATH to a definition in DEF_BB. When these basic blocks are
kono
parents:
diff changeset
716 different, append to PATH the blocks from LAST_BB_IN_PATH to DEF_BB. */
kono
parents:
diff changeset
717 if (def_bb != last_bb_in_path)
kono
parents:
diff changeset
718 {
kono
parents:
diff changeset
719 /* When DEF_BB == LAST_BB_IN_PATH, then the first block in the path
kono
parents:
diff changeset
720 will already be in VISITED_BBS. When they are not equal, then we
kono
parents:
diff changeset
721 must ensure that first block is accounted for to ensure we do not
kono
parents:
diff changeset
722 create bogus jump threading paths. */
kono
parents:
diff changeset
723 visited_bbs.add (path[0]);
kono
parents:
diff changeset
724 if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb,
kono
parents:
diff changeset
725 visited_bbs, path,
kono
parents:
diff changeset
726 &next_path_length))
kono
parents:
diff changeset
727 return;
kono
parents:
diff changeset
728 }
kono
parents:
diff changeset
729
kono
parents:
diff changeset
730 gcc_assert (path.last () == def_bb);
kono
parents:
diff changeset
731
kono
parents:
diff changeset
732 if (gimple_code (def_stmt) == GIMPLE_PHI)
kono
parents:
diff changeset
733 handle_phi (as_a <gphi *> (def_stmt), name, def_bb,
kono
parents:
diff changeset
734 visited_bbs, path, seen_loop_phi, speed_p);
kono
parents:
diff changeset
735 else if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
kono
parents:
diff changeset
736 handle_assignment (def_stmt, name, def_bb,
kono
parents:
diff changeset
737 visited_bbs, path, seen_loop_phi, speed_p);
kono
parents:
diff changeset
738
kono
parents:
diff changeset
739 /* Remove all the nodes that we added from NEXT_PATH. */
kono
parents:
diff changeset
740 if (next_path_length)
kono
parents:
diff changeset
741 path.truncate (path.length () - next_path_length);
kono
parents:
diff changeset
742 }
kono
parents:
diff changeset
743
kono
parents:
diff changeset
744 /* Search backwards from BB looking for paths where NAME (an SSA_NAME)
kono
parents:
diff changeset
745 is a constant. Record such paths for jump threading.
kono
parents:
diff changeset
746
kono
parents:
diff changeset
747 It is assumed that BB ends with a control statement and that by
kono
parents:
diff changeset
748 finding a path where NAME is a constant, we can thread the path.
kono
parents:
diff changeset
749 SPEED_P indicate that we could increase code size to improve the
kono
parents:
diff changeset
750 code path. */
kono
parents:
diff changeset
751
kono
parents:
diff changeset
752 void
kono
parents:
diff changeset
753 find_jump_threads_backwards (basic_block bb, bool speed_p)
kono
parents:
diff changeset
754 {
kono
parents:
diff changeset
755 gimple *stmt = get_gimple_control_stmt (bb);
kono
parents:
diff changeset
756 if (!stmt)
kono
parents:
diff changeset
757 return;
kono
parents:
diff changeset
758
kono
parents:
diff changeset
759 enum gimple_code code = gimple_code (stmt);
kono
parents:
diff changeset
760 tree name = NULL;
kono
parents:
diff changeset
761 if (code == GIMPLE_SWITCH)
kono
parents:
diff changeset
762 name = gimple_switch_index (as_a <gswitch *> (stmt));
kono
parents:
diff changeset
763 else if (code == GIMPLE_GOTO)
kono
parents:
diff changeset
764 name = gimple_goto_dest (stmt);
kono
parents:
diff changeset
765 else if (code == GIMPLE_COND)
kono
parents:
diff changeset
766 {
kono
parents:
diff changeset
767 if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
kono
parents:
diff changeset
768 && TREE_CODE_CLASS (TREE_CODE (gimple_cond_rhs (stmt))) == tcc_constant
kono
parents:
diff changeset
769 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
kono
parents:
diff changeset
770 || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
kono
parents:
diff changeset
771 name = gimple_cond_lhs (stmt);
kono
parents:
diff changeset
772 }
kono
parents:
diff changeset
773
kono
parents:
diff changeset
774 if (!name || TREE_CODE (name) != SSA_NAME)
kono
parents:
diff changeset
775 return;
kono
parents:
diff changeset
776
kono
parents:
diff changeset
777 auto_vec<basic_block> bb_path;
kono
parents:
diff changeset
778 bb_path.safe_push (bb);
kono
parents:
diff changeset
779 hash_set<basic_block> visited_bbs;
kono
parents:
diff changeset
780
kono
parents:
diff changeset
781 max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS);
kono
parents:
diff changeset
782 fsm_find_control_statement_thread_paths (name, visited_bbs, bb_path, false,
kono
parents:
diff changeset
783 speed_p);
kono
parents:
diff changeset
784 }
kono
parents:
diff changeset
785
kono
parents:
diff changeset
786 namespace {
kono
parents:
diff changeset
787
kono
parents:
diff changeset
788 const pass_data pass_data_thread_jumps =
kono
parents:
diff changeset
789 {
kono
parents:
diff changeset
790 GIMPLE_PASS,
kono
parents:
diff changeset
791 "thread",
kono
parents:
diff changeset
792 OPTGROUP_NONE,
kono
parents:
diff changeset
793 TV_TREE_SSA_THREAD_JUMPS,
kono
parents:
diff changeset
794 ( PROP_cfg | PROP_ssa ),
kono
parents:
diff changeset
795 0,
kono
parents:
diff changeset
796 0,
kono
parents:
diff changeset
797 0,
kono
parents:
diff changeset
798 TODO_update_ssa,
kono
parents:
diff changeset
799 };
kono
parents:
diff changeset
800
kono
parents:
diff changeset
801 class pass_thread_jumps : public gimple_opt_pass
kono
parents:
diff changeset
802 {
kono
parents:
diff changeset
803 public:
kono
parents:
diff changeset
804 pass_thread_jumps (gcc::context *ctxt)
kono
parents:
diff changeset
805 : gimple_opt_pass (pass_data_thread_jumps, ctxt)
kono
parents:
diff changeset
806 {}
kono
parents:
diff changeset
807
kono
parents:
diff changeset
808 opt_pass * clone (void) { return new pass_thread_jumps (m_ctxt); }
kono
parents:
diff changeset
809 virtual bool gate (function *);
kono
parents:
diff changeset
810 virtual unsigned int execute (function *);
kono
parents:
diff changeset
811 };
kono
parents:
diff changeset
812
kono
parents:
diff changeset
813 bool
kono
parents:
diff changeset
814 pass_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
kono
parents:
diff changeset
815 {
kono
parents:
diff changeset
816 return flag_expensive_optimizations;
kono
parents:
diff changeset
817 }
kono
parents:
diff changeset
818
kono
parents:
diff changeset
819
kono
parents:
diff changeset
820 unsigned int
kono
parents:
diff changeset
821 pass_thread_jumps::execute (function *fun)
kono
parents:
diff changeset
822 {
kono
parents:
diff changeset
823 loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
kono
parents:
diff changeset
824
kono
parents:
diff changeset
825 /* Try to thread each block with more than one successor. */
kono
parents:
diff changeset
826 basic_block bb;
kono
parents:
diff changeset
827 FOR_EACH_BB_FN (bb, fun)
kono
parents:
diff changeset
828 {
kono
parents:
diff changeset
829 if (EDGE_COUNT (bb->succs) > 1)
kono
parents:
diff changeset
830 find_jump_threads_backwards (bb, true);
kono
parents:
diff changeset
831 }
kono
parents:
diff changeset
832 bool changed = thread_through_all_blocks (true);
kono
parents:
diff changeset
833
kono
parents:
diff changeset
834 loop_optimizer_finalize ();
kono
parents:
diff changeset
835 return changed ? TODO_cleanup_cfg : 0;
kono
parents:
diff changeset
836 }
kono
parents:
diff changeset
837
kono
parents:
diff changeset
838 }
kono
parents:
diff changeset
839
kono
parents:
diff changeset
840 gimple_opt_pass *
kono
parents:
diff changeset
841 make_pass_thread_jumps (gcc::context *ctxt)
kono
parents:
diff changeset
842 {
kono
parents:
diff changeset
843 return new pass_thread_jumps (ctxt);
kono
parents:
diff changeset
844 }
kono
parents:
diff changeset
845
kono
parents:
diff changeset
846 namespace {
kono
parents:
diff changeset
847
kono
parents:
diff changeset
848 const pass_data pass_data_early_thread_jumps =
kono
parents:
diff changeset
849 {
kono
parents:
diff changeset
850 GIMPLE_PASS,
kono
parents:
diff changeset
851 "ethread",
kono
parents:
diff changeset
852 OPTGROUP_NONE,
kono
parents:
diff changeset
853 TV_TREE_SSA_THREAD_JUMPS,
kono
parents:
diff changeset
854 ( PROP_cfg | PROP_ssa ),
kono
parents:
diff changeset
855 0,
kono
parents:
diff changeset
856 0,
kono
parents:
diff changeset
857 0,
kono
parents:
diff changeset
858 ( TODO_cleanup_cfg | TODO_update_ssa ),
kono
parents:
diff changeset
859 };
kono
parents:
diff changeset
860
kono
parents:
diff changeset
861 class pass_early_thread_jumps : public gimple_opt_pass
kono
parents:
diff changeset
862 {
kono
parents:
diff changeset
863 public:
kono
parents:
diff changeset
864 pass_early_thread_jumps (gcc::context *ctxt)
kono
parents:
diff changeset
865 : gimple_opt_pass (pass_data_early_thread_jumps, ctxt)
kono
parents:
diff changeset
866 {}
kono
parents:
diff changeset
867
kono
parents:
diff changeset
868 opt_pass * clone (void) { return new pass_early_thread_jumps (m_ctxt); }
kono
parents:
diff changeset
869 virtual bool gate (function *);
kono
parents:
diff changeset
870 virtual unsigned int execute (function *);
kono
parents:
diff changeset
871 };
kono
parents:
diff changeset
872
kono
parents:
diff changeset
873 bool
kono
parents:
diff changeset
874 pass_early_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
kono
parents:
diff changeset
875 {
kono
parents:
diff changeset
876 return true;
kono
parents:
diff changeset
877 }
kono
parents:
diff changeset
878
kono
parents:
diff changeset
879
kono
parents:
diff changeset
880 unsigned int
kono
parents:
diff changeset
881 pass_early_thread_jumps::execute (function *fun)
kono
parents:
diff changeset
882 {
kono
parents:
diff changeset
883 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
kono
parents:
diff changeset
884
kono
parents:
diff changeset
885 /* Try to thread each block with more than one successor. */
kono
parents:
diff changeset
886 basic_block bb;
kono
parents:
diff changeset
887 FOR_EACH_BB_FN (bb, fun)
kono
parents:
diff changeset
888 {
kono
parents:
diff changeset
889 if (EDGE_COUNT (bb->succs) > 1)
kono
parents:
diff changeset
890 find_jump_threads_backwards (bb, false);
kono
parents:
diff changeset
891 }
kono
parents:
diff changeset
892 thread_through_all_blocks (true);
kono
parents:
diff changeset
893
kono
parents:
diff changeset
894 loop_optimizer_finalize ();
kono
parents:
diff changeset
895 return 0;
kono
parents:
diff changeset
896 }
kono
parents:
diff changeset
897
kono
parents:
diff changeset
898 }
kono
parents:
diff changeset
899
kono
parents:
diff changeset
900 gimple_opt_pass *
kono
parents:
diff changeset
901 make_pass_early_thread_jumps (gcc::context *ctxt)
kono
parents:
diff changeset
902 {
kono
parents:
diff changeset
903 return new pass_early_thread_jumps (ctxt);
kono
parents:
diff changeset
904 }