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