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