xref: /openbsd-src/gnu/gcc/gcc/tree-ssa-threadedge.c (revision 404b540a9034ac75a6199ad1a32d1bbc7a0d4210)
1*404b540aSrobert /* SSA Jump Threading
2*404b540aSrobert    Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
3*404b540aSrobert    Contributed by Jeff Law  <law@redhat.com>
4*404b540aSrobert 
5*404b540aSrobert This file is part of GCC.
6*404b540aSrobert 
7*404b540aSrobert GCC is free software; you can redistribute it and/or modify
8*404b540aSrobert it under the terms of the GNU General Public License as published by
9*404b540aSrobert the Free Software Foundation; either version 2, or (at your option)
10*404b540aSrobert any later version.
11*404b540aSrobert 
12*404b540aSrobert GCC is distributed in the hope that it will be useful,
13*404b540aSrobert but WITHOUT ANY WARRANTY; without even the implied warranty of
14*404b540aSrobert MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15*404b540aSrobert GNU General Public License for more details.
16*404b540aSrobert 
17*404b540aSrobert You should have received a copy of the GNU General Public License
18*404b540aSrobert along with GCC; see the file COPYING.  If not, write to
19*404b540aSrobert the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20*404b540aSrobert Boston, MA 02110-1301, USA.  */
21*404b540aSrobert 
22*404b540aSrobert #include "config.h"
23*404b540aSrobert #include "system.h"
24*404b540aSrobert #include "coretypes.h"
25*404b540aSrobert #include "tm.h"
26*404b540aSrobert #include "tree.h"
27*404b540aSrobert #include "flags.h"
28*404b540aSrobert #include "rtl.h"
29*404b540aSrobert #include "tm_p.h"
30*404b540aSrobert #include "ggc.h"
31*404b540aSrobert #include "basic-block.h"
32*404b540aSrobert #include "cfgloop.h"
33*404b540aSrobert #include "output.h"
34*404b540aSrobert #include "expr.h"
35*404b540aSrobert #include "function.h"
36*404b540aSrobert #include "diagnostic.h"
37*404b540aSrobert #include "timevar.h"
38*404b540aSrobert #include "tree-dump.h"
39*404b540aSrobert #include "tree-flow.h"
40*404b540aSrobert #include "domwalk.h"
41*404b540aSrobert #include "real.h"
42*404b540aSrobert #include "tree-pass.h"
43*404b540aSrobert #include "tree-ssa-propagate.h"
44*404b540aSrobert #include "langhooks.h"
45*404b540aSrobert #include "params.h"
46*404b540aSrobert 
47*404b540aSrobert /* To avoid code explosion due to jump threading, we limit the
48*404b540aSrobert    number of statements we are going to copy.  This variable
49*404b540aSrobert    holds the number of statements currently seen that we'll have
50*404b540aSrobert    to copy as part of the jump threading process.  */
51*404b540aSrobert static int stmt_count;
52*404b540aSrobert 
53*404b540aSrobert /* Return TRUE if we may be able to thread an incoming edge into
54*404b540aSrobert    BB to an outgoing edge from BB.  Return FALSE otherwise.  */
55*404b540aSrobert 
56*404b540aSrobert bool
potentially_threadable_block(basic_block bb)57*404b540aSrobert potentially_threadable_block (basic_block bb)
58*404b540aSrobert {
59*404b540aSrobert   block_stmt_iterator bsi;
60*404b540aSrobert 
61*404b540aSrobert   /* If BB has a single successor or a single predecessor, then
62*404b540aSrobert      there is no threading opportunity.  */
63*404b540aSrobert   if (single_succ_p (bb) || single_pred_p (bb))
64*404b540aSrobert     return false;
65*404b540aSrobert 
66*404b540aSrobert   /* If BB does not end with a conditional, switch or computed goto,
67*404b540aSrobert      then there is no threading opportunity.  */
68*404b540aSrobert   bsi = bsi_last (bb);
69*404b540aSrobert   if (bsi_end_p (bsi)
70*404b540aSrobert       || ! bsi_stmt (bsi)
71*404b540aSrobert       || (TREE_CODE (bsi_stmt (bsi)) != COND_EXPR
72*404b540aSrobert 	  && TREE_CODE (bsi_stmt (bsi)) != GOTO_EXPR
73*404b540aSrobert 	  && TREE_CODE (bsi_stmt (bsi)) != SWITCH_EXPR))
74*404b540aSrobert     return false;
75*404b540aSrobert 
76*404b540aSrobert   return true;
77*404b540aSrobert }
78*404b540aSrobert 
79*404b540aSrobert /* Return the LHS of any ASSERT_EXPR where OP appears as the first
80*404b540aSrobert    argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
81*404b540aSrobert    BB.  If no such ASSERT_EXPR is found, return OP.  */
82*404b540aSrobert 
83*404b540aSrobert static tree
lhs_of_dominating_assert(tree op,basic_block bb,tree stmt)84*404b540aSrobert lhs_of_dominating_assert (tree op, basic_block bb, tree stmt)
85*404b540aSrobert {
86*404b540aSrobert   imm_use_iterator imm_iter;
87*404b540aSrobert   tree use_stmt;
88*404b540aSrobert   use_operand_p use_p;
89*404b540aSrobert 
90*404b540aSrobert   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op)
91*404b540aSrobert     {
92*404b540aSrobert       use_stmt = USE_STMT (use_p);
93*404b540aSrobert       if (use_stmt != stmt
94*404b540aSrobert           && TREE_CODE (use_stmt) == MODIFY_EXPR
95*404b540aSrobert           && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == ASSERT_EXPR
96*404b540aSrobert           && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 0) == op
97*404b540aSrobert 	  && dominated_by_p (CDI_DOMINATORS, bb, bb_for_stmt (use_stmt)))
98*404b540aSrobert 	{
99*404b540aSrobert 	  return TREE_OPERAND (use_stmt, 0);
100*404b540aSrobert 	}
101*404b540aSrobert     }
102*404b540aSrobert   return op;
103*404b540aSrobert }
104*404b540aSrobert 
105*404b540aSrobert 
106*404b540aSrobert /* We record temporary equivalences created by PHI nodes or
107*404b540aSrobert    statements within the target block.  Doing so allows us to
108*404b540aSrobert    identify more jump threading opportunities, even in blocks
109*404b540aSrobert    with side effects.
110*404b540aSrobert 
111*404b540aSrobert    We keep track of those temporary equivalences in a stack
112*404b540aSrobert    structure so that we can unwind them when we're done processing
113*404b540aSrobert    a particular edge.  This routine handles unwinding the data
114*404b540aSrobert    structures.  */
115*404b540aSrobert 
116*404b540aSrobert static void
remove_temporary_equivalences(VEC (tree,heap)** stack)117*404b540aSrobert remove_temporary_equivalences (VEC(tree, heap) **stack)
118*404b540aSrobert {
119*404b540aSrobert   while (VEC_length (tree, *stack) > 0)
120*404b540aSrobert     {
121*404b540aSrobert       tree prev_value, dest;
122*404b540aSrobert 
123*404b540aSrobert       dest = VEC_pop (tree, *stack);
124*404b540aSrobert 
125*404b540aSrobert       /* A NULL value indicates we should stop unwinding, otherwise
126*404b540aSrobert 	 pop off the next entry as they're recorded in pairs.  */
127*404b540aSrobert       if (dest == NULL)
128*404b540aSrobert 	break;
129*404b540aSrobert 
130*404b540aSrobert       prev_value = VEC_pop (tree, *stack);
131*404b540aSrobert       SSA_NAME_VALUE (dest) = prev_value;
132*404b540aSrobert     }
133*404b540aSrobert }
134*404b540aSrobert 
135*404b540aSrobert /* Record a temporary equivalence, saving enough information so that
136*404b540aSrobert    we can restore the state of recorded equivalences when we're
137*404b540aSrobert    done processing the current edge.  */
138*404b540aSrobert 
139*404b540aSrobert static void
record_temporary_equivalence(tree x,tree y,VEC (tree,heap)** stack)140*404b540aSrobert record_temporary_equivalence (tree x, tree y, VEC(tree, heap) **stack)
141*404b540aSrobert {
142*404b540aSrobert   tree prev_x = SSA_NAME_VALUE (x);
143*404b540aSrobert 
144*404b540aSrobert   if (TREE_CODE (y) == SSA_NAME)
145*404b540aSrobert     {
146*404b540aSrobert       tree tmp = SSA_NAME_VALUE (y);
147*404b540aSrobert       y = tmp ? tmp : y;
148*404b540aSrobert     }
149*404b540aSrobert 
150*404b540aSrobert   SSA_NAME_VALUE (x) = y;
151*404b540aSrobert   VEC_reserve (tree, heap, *stack, 2);
152*404b540aSrobert   VEC_quick_push (tree, *stack, prev_x);
153*404b540aSrobert   VEC_quick_push (tree, *stack, x);
154*404b540aSrobert }
155*404b540aSrobert 
156*404b540aSrobert /* Record temporary equivalences created by PHIs at the target of the
157*404b540aSrobert    edge E.  Record unwind information for the equivalences onto STACK.
158*404b540aSrobert 
159*404b540aSrobert    If a PHI which prevents threading is encountered, then return FALSE
160*404b540aSrobert    indicating we should not thread this edge, else return TRUE.  */
161*404b540aSrobert 
162*404b540aSrobert static bool
record_temporary_equivalences_from_phis(edge e,VEC (tree,heap)** stack)163*404b540aSrobert record_temporary_equivalences_from_phis (edge e, VEC(tree, heap) **stack)
164*404b540aSrobert {
165*404b540aSrobert   tree phi;
166*404b540aSrobert 
167*404b540aSrobert   /* Each PHI creates a temporary equivalence, record them.
168*404b540aSrobert      These are context sensitive equivalences and will be removed
169*404b540aSrobert      later.  */
170*404b540aSrobert   for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
171*404b540aSrobert     {
172*404b540aSrobert       tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
173*404b540aSrobert       tree dst = PHI_RESULT (phi);
174*404b540aSrobert 
175*404b540aSrobert       /* If the desired argument is not the same as this PHI's result
176*404b540aSrobert 	 and it is set by a PHI in E->dest, then we can not thread
177*404b540aSrobert 	 through E->dest.  */
178*404b540aSrobert       if (src != dst
179*404b540aSrobert 	  && TREE_CODE (src) == SSA_NAME
180*404b540aSrobert 	  && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE
181*404b540aSrobert 	  && bb_for_stmt (SSA_NAME_DEF_STMT (src)) == e->dest)
182*404b540aSrobert 	return false;
183*404b540aSrobert 
184*404b540aSrobert       /* We consider any non-virtual PHI as a statement since it
185*404b540aSrobert 	 count result in a constant assignment or copy operation.  */
186*404b540aSrobert       if (is_gimple_reg (dst))
187*404b540aSrobert 	stmt_count++;
188*404b540aSrobert 
189*404b540aSrobert       record_temporary_equivalence (dst, src, stack);
190*404b540aSrobert     }
191*404b540aSrobert   return true;
192*404b540aSrobert }
193*404b540aSrobert 
194*404b540aSrobert /* Try to simplify each statement in E->dest, ultimately leading to
195*404b540aSrobert    a simplification of the COND_EXPR at the end of E->dest.
196*404b540aSrobert 
197*404b540aSrobert    Record unwind information for temporary equivalences onto STACK.
198*404b540aSrobert 
199*404b540aSrobert    Use SIMPLIFY (a pointer to a callback function) to further simplify
200*404b540aSrobert    statements using pass specific information.
201*404b540aSrobert 
202*404b540aSrobert    We might consider marking just those statements which ultimately
203*404b540aSrobert    feed the COND_EXPR.  It's not clear if the overhead of bookkeeping
204*404b540aSrobert    would be recovered by trying to simplify fewer statements.
205*404b540aSrobert 
206*404b540aSrobert    If we are able to simplify a statement into the form
207*404b540aSrobert    SSA_NAME = (SSA_NAME | gimple invariant), then we can record
208*404b540aSrobert    a context sensitive equivalency which may help us simplify
209*404b540aSrobert    later statements in E->dest.  */
210*404b540aSrobert 
211*404b540aSrobert static tree
record_temporary_equivalences_from_stmts_at_dest(edge e,VEC (tree,heap)** stack,tree (* simplify)(tree,tree))212*404b540aSrobert record_temporary_equivalences_from_stmts_at_dest (edge e,
213*404b540aSrobert 						  VEC(tree, heap) **stack,
214*404b540aSrobert 						  tree (*simplify) (tree,
215*404b540aSrobert 								    tree))
216*404b540aSrobert {
217*404b540aSrobert   block_stmt_iterator bsi;
218*404b540aSrobert   tree stmt = NULL;
219*404b540aSrobert   int max_stmt_count;
220*404b540aSrobert 
221*404b540aSrobert   max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS);
222*404b540aSrobert 
223*404b540aSrobert   /* Walk through each statement in the block recording equivalences
224*404b540aSrobert      we discover.  Note any equivalences we discover are context
225*404b540aSrobert      sensitive (ie, are dependent on traversing E) and must be unwound
226*404b540aSrobert      when we're finished processing E.  */
227*404b540aSrobert   for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
228*404b540aSrobert     {
229*404b540aSrobert       tree cached_lhs = NULL;
230*404b540aSrobert 
231*404b540aSrobert       stmt = bsi_stmt (bsi);
232*404b540aSrobert 
233*404b540aSrobert       /* Ignore empty statements and labels.  */
234*404b540aSrobert       if (IS_EMPTY_STMT (stmt) || TREE_CODE (stmt) == LABEL_EXPR)
235*404b540aSrobert 	continue;
236*404b540aSrobert 
237*404b540aSrobert       /* If the statement has volatile operands, then we assume we
238*404b540aSrobert 	 can not thread through this block.  This is overly
239*404b540aSrobert 	 conservative in some ways.  */
240*404b540aSrobert       if (TREE_CODE (stmt) == ASM_EXPR && ASM_VOLATILE_P (stmt))
241*404b540aSrobert 	return NULL;
242*404b540aSrobert 
243*404b540aSrobert       /* If duplicating this block is going to cause too much code
244*404b540aSrobert 	 expansion, then do not thread through this block.  */
245*404b540aSrobert       stmt_count++;
246*404b540aSrobert       if (stmt_count > max_stmt_count)
247*404b540aSrobert 	return NULL;
248*404b540aSrobert 
249*404b540aSrobert       /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
250*404b540aSrobert 	 value, then do not try to simplify this statement as it will
251*404b540aSrobert 	 not simplify in any way that is helpful for jump threading.  */
252*404b540aSrobert       if (TREE_CODE (stmt) != MODIFY_EXPR
253*404b540aSrobert 	  || TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
254*404b540aSrobert 	continue;
255*404b540aSrobert 
256*404b540aSrobert       /* At this point we have a statement which assigns an RHS to an
257*404b540aSrobert 	 SSA_VAR on the LHS.  We want to try and simplify this statement
258*404b540aSrobert 	 to expose more context sensitive equivalences which in turn may
259*404b540aSrobert 	 allow us to simplify the condition at the end of the loop.
260*404b540aSrobert 
261*404b540aSrobert 	 Handle simple copy operations as well as implied copies from
262*404b540aSrobert 	 ASSERT_EXPRs.  */
263*404b540aSrobert       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
264*404b540aSrobert 	cached_lhs = TREE_OPERAND (stmt, 1);
265*404b540aSrobert       else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
266*404b540aSrobert 	cached_lhs = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
267*404b540aSrobert       else
268*404b540aSrobert 	{
269*404b540aSrobert 	  /* A statement that is not a trivial copy or ASSERT_EXPR.
270*404b540aSrobert 	     We're going to temporarily copy propagate the operands
271*404b540aSrobert 	     and see if that allows us to simplify this statement.  */
272*404b540aSrobert 	  tree *copy, pre_fold_expr;
273*404b540aSrobert 	  ssa_op_iter iter;
274*404b540aSrobert 	  use_operand_p use_p;
275*404b540aSrobert 	  unsigned int num, i = 0;
276*404b540aSrobert 
277*404b540aSrobert 	  num = NUM_SSA_OPERANDS (stmt, (SSA_OP_USE | SSA_OP_VUSE));
278*404b540aSrobert 	  copy = XCNEWVEC (tree, num);
279*404b540aSrobert 
280*404b540aSrobert 	  /* Make a copy of the uses & vuses into USES_COPY, then cprop into
281*404b540aSrobert 	     the operands.  */
282*404b540aSrobert 	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
283*404b540aSrobert 	    {
284*404b540aSrobert 	      tree tmp = NULL;
285*404b540aSrobert 	      tree use = USE_FROM_PTR (use_p);
286*404b540aSrobert 
287*404b540aSrobert 	      copy[i++] = use;
288*404b540aSrobert 	      if (TREE_CODE (use) == SSA_NAME)
289*404b540aSrobert 		tmp = SSA_NAME_VALUE (use);
290*404b540aSrobert 	      if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
291*404b540aSrobert 		SET_USE (use_p, tmp);
292*404b540aSrobert 	    }
293*404b540aSrobert 
294*404b540aSrobert 	  /* Try to fold/lookup the new expression.  Inserting the
295*404b540aSrobert 	     expression into the hash table is unlikely to help
296*404b540aSrobert 	     Sadly, we have to handle conditional assignments specially
297*404b540aSrobert 	     here, because fold expects all the operands of an expression
298*404b540aSrobert 	     to be folded before the expression itself is folded, but we
299*404b540aSrobert 	     can't just substitute the folded condition here.  */
300*404b540aSrobert 	  if (TREE_CODE (TREE_OPERAND (stmt, 1)) == COND_EXPR)
301*404b540aSrobert 	    {
302*404b540aSrobert 	      tree cond = COND_EXPR_COND (TREE_OPERAND (stmt, 1));
303*404b540aSrobert 	      cond = fold (cond);
304*404b540aSrobert 	      if (cond == boolean_true_node)
305*404b540aSrobert 		pre_fold_expr = COND_EXPR_THEN (TREE_OPERAND (stmt, 1));
306*404b540aSrobert 	      else if (cond == boolean_false_node)
307*404b540aSrobert 		pre_fold_expr = COND_EXPR_ELSE (TREE_OPERAND (stmt, 1));
308*404b540aSrobert 	      else
309*404b540aSrobert 		pre_fold_expr = TREE_OPERAND (stmt, 1);
310*404b540aSrobert 	    }
311*404b540aSrobert 	  else
312*404b540aSrobert 	    pre_fold_expr = TREE_OPERAND (stmt, 1);
313*404b540aSrobert 
314*404b540aSrobert 	  if (pre_fold_expr)
315*404b540aSrobert 	    {
316*404b540aSrobert 	      cached_lhs = fold (pre_fold_expr);
317*404b540aSrobert 	      if (TREE_CODE (cached_lhs) != SSA_NAME
318*404b540aSrobert 		  && !is_gimple_min_invariant (cached_lhs))
319*404b540aSrobert 	        cached_lhs = (*simplify) (stmt, stmt);
320*404b540aSrobert 	    }
321*404b540aSrobert 
322*404b540aSrobert 	  /* Restore the statement's original uses/defs.  */
323*404b540aSrobert 	  i = 0;
324*404b540aSrobert 	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
325*404b540aSrobert 	    SET_USE (use_p, copy[i++]);
326*404b540aSrobert 
327*404b540aSrobert 	  free (copy);
328*404b540aSrobert 	}
329*404b540aSrobert 
330*404b540aSrobert       /* Record the context sensitive equivalence if we were able
331*404b540aSrobert 	 to simplify this statement.  */
332*404b540aSrobert       if (cached_lhs
333*404b540aSrobert 	  && (TREE_CODE (cached_lhs) == SSA_NAME
334*404b540aSrobert 	      || is_gimple_min_invariant (cached_lhs)))
335*404b540aSrobert 	record_temporary_equivalence (TREE_OPERAND (stmt, 0),
336*404b540aSrobert 				      cached_lhs,
337*404b540aSrobert 				      stack);
338*404b540aSrobert     }
339*404b540aSrobert   return stmt;
340*404b540aSrobert }
341*404b540aSrobert 
342*404b540aSrobert /* Simplify the control statement at the end of the block E->dest.
343*404b540aSrobert 
344*404b540aSrobert    To avoid allocating memory unnecessarily, a scratch COND_EXPR
345*404b540aSrobert    is available to use/clobber in DUMMY_COND.
346*404b540aSrobert 
347*404b540aSrobert    Use SIMPLIFY (a pointer to a callback function) to further simplify
348*404b540aSrobert    a condition using pass specific information.
349*404b540aSrobert 
350*404b540aSrobert    Return the simplified condition or NULL if simplification could
351*404b540aSrobert    not be performed.  */
352*404b540aSrobert 
353*404b540aSrobert static tree
simplify_control_stmt_condition(edge e,tree stmt,tree dummy_cond,tree (* simplify)(tree,tree),bool handle_dominating_asserts)354*404b540aSrobert simplify_control_stmt_condition (edge e,
355*404b540aSrobert 				 tree stmt,
356*404b540aSrobert 				 tree dummy_cond,
357*404b540aSrobert 				 tree (*simplify) (tree, tree),
358*404b540aSrobert 				 bool handle_dominating_asserts)
359*404b540aSrobert {
360*404b540aSrobert   tree cond, cached_lhs;
361*404b540aSrobert 
362*404b540aSrobert   if (TREE_CODE (stmt) == COND_EXPR)
363*404b540aSrobert     cond = COND_EXPR_COND (stmt);
364*404b540aSrobert   else if (TREE_CODE (stmt) == GOTO_EXPR)
365*404b540aSrobert     cond = GOTO_DESTINATION (stmt);
366*404b540aSrobert   else
367*404b540aSrobert     cond = SWITCH_COND (stmt);
368*404b540aSrobert 
369*404b540aSrobert   /* For comparisons, we have to update both operands, then try
370*404b540aSrobert      to simplify the comparison.  */
371*404b540aSrobert   if (COMPARISON_CLASS_P (cond))
372*404b540aSrobert     {
373*404b540aSrobert       tree op0, op1;
374*404b540aSrobert       enum tree_code cond_code;
375*404b540aSrobert 
376*404b540aSrobert       op0 = TREE_OPERAND (cond, 0);
377*404b540aSrobert       op1 = TREE_OPERAND (cond, 1);
378*404b540aSrobert       cond_code = TREE_CODE (cond);
379*404b540aSrobert 
380*404b540aSrobert       /* Get the current value of both operands.  */
381*404b540aSrobert       if (TREE_CODE (op0) == SSA_NAME)
382*404b540aSrobert 	{
383*404b540aSrobert           tree tmp = SSA_NAME_VALUE (op0);
384*404b540aSrobert 	  if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
385*404b540aSrobert 	    op0 = tmp;
386*404b540aSrobert 	}
387*404b540aSrobert 
388*404b540aSrobert       if (TREE_CODE (op1) == SSA_NAME)
389*404b540aSrobert 	{
390*404b540aSrobert 	  tree tmp = SSA_NAME_VALUE (op1);
391*404b540aSrobert 	  if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
392*404b540aSrobert 	    op1 = tmp;
393*404b540aSrobert 	}
394*404b540aSrobert 
395*404b540aSrobert       if (handle_dominating_asserts)
396*404b540aSrobert 	{
397*404b540aSrobert 	  /* Now see if the operand was consumed by an ASSERT_EXPR
398*404b540aSrobert 	     which dominates E->src.  If so, we want to replace the
399*404b540aSrobert 	     operand with the LHS of the ASSERT_EXPR.  */
400*404b540aSrobert 	  if (TREE_CODE (op0) == SSA_NAME)
401*404b540aSrobert 	    op0 = lhs_of_dominating_assert (op0, e->src, stmt);
402*404b540aSrobert 
403*404b540aSrobert 	  if (TREE_CODE (op1) == SSA_NAME)
404*404b540aSrobert 	    op1 = lhs_of_dominating_assert (op1, e->src, stmt);
405*404b540aSrobert 	}
406*404b540aSrobert 
407*404b540aSrobert       /* We may need to canonicalize the comparison.  For
408*404b540aSrobert 	 example, op0 might be a constant while op1 is an
409*404b540aSrobert 	 SSA_NAME.  Failure to canonicalize will cause us to
410*404b540aSrobert 	 miss threading opportunities.  */
411*404b540aSrobert       if (cond_code != SSA_NAME
412*404b540aSrobert 	  && tree_swap_operands_p (op0, op1, false))
413*404b540aSrobert 	{
414*404b540aSrobert 	  tree tmp;
415*404b540aSrobert 	  cond_code = swap_tree_comparison (TREE_CODE (cond));
416*404b540aSrobert 	  tmp = op0;
417*404b540aSrobert 	  op0 = op1;
418*404b540aSrobert 	  op1 = tmp;
419*404b540aSrobert 	}
420*404b540aSrobert 
421*404b540aSrobert       /* Stuff the operator and operands into our dummy conditional
422*404b540aSrobert 	 expression.  */
423*404b540aSrobert       TREE_SET_CODE (COND_EXPR_COND (dummy_cond), cond_code);
424*404b540aSrobert       TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op0;
425*404b540aSrobert       TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1) = op1;
426*404b540aSrobert 
427*404b540aSrobert       /* We absolutely do not care about any type conversions
428*404b540aSrobert          we only care about a zero/nonzero value.  */
429*404b540aSrobert       fold_defer_overflow_warnings ();
430*404b540aSrobert 
431*404b540aSrobert       cached_lhs = fold (COND_EXPR_COND (dummy_cond));
432*404b540aSrobert       while (TREE_CODE (cached_lhs) == NOP_EXPR
433*404b540aSrobert 	     || TREE_CODE (cached_lhs) == CONVERT_EXPR
434*404b540aSrobert 	     || TREE_CODE (cached_lhs) == NON_LVALUE_EXPR)
435*404b540aSrobert 	cached_lhs = TREE_OPERAND (cached_lhs, 0);
436*404b540aSrobert 
437*404b540aSrobert       fold_undefer_overflow_warnings (is_gimple_min_invariant (cached_lhs),
438*404b540aSrobert 				      stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
439*404b540aSrobert 
440*404b540aSrobert       /* If we have not simplified the condition down to an invariant,
441*404b540aSrobert 	 then use the pass specific callback to simplify the condition.  */
442*404b540aSrobert       if (! is_gimple_min_invariant (cached_lhs))
443*404b540aSrobert 	cached_lhs = (*simplify) (dummy_cond, stmt);
444*404b540aSrobert     }
445*404b540aSrobert 
446*404b540aSrobert   /* We can have conditionals which just test the state of a variable
447*404b540aSrobert      rather than use a relational operator.  These are simpler to handle.  */
448*404b540aSrobert   else if (TREE_CODE (cond) == SSA_NAME)
449*404b540aSrobert     {
450*404b540aSrobert       cached_lhs = cond;
451*404b540aSrobert 
452*404b540aSrobert       /* Get the variable's current value from the equivalency chains.
453*404b540aSrobert 
454*404b540aSrobert 	 It is possible to get loops in the SSA_NAME_VALUE chains
455*404b540aSrobert 	 (consider threading the backedge of a loop where we have
456*404b540aSrobert 	 a loop invariant SSA_NAME used in the condition.  */
457*404b540aSrobert       if (cached_lhs
458*404b540aSrobert 	  && TREE_CODE (cached_lhs) == SSA_NAME
459*404b540aSrobert 	  && SSA_NAME_VALUE (cached_lhs))
460*404b540aSrobert 	cached_lhs = SSA_NAME_VALUE (cached_lhs);
461*404b540aSrobert 
462*404b540aSrobert       /* If we're dominated by a suitable ASSERT_EXPR, then
463*404b540aSrobert 	 update CACHED_LHS appropriately.  */
464*404b540aSrobert       if (handle_dominating_asserts && TREE_CODE (cached_lhs) == SSA_NAME)
465*404b540aSrobert 	cached_lhs = lhs_of_dominating_assert (cached_lhs, e->src, stmt);
466*404b540aSrobert 
467*404b540aSrobert       /* If we haven't simplified to an invariant yet, then use the
468*404b540aSrobert 	 pass specific callback to try and simplify it further.  */
469*404b540aSrobert       if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
470*404b540aSrobert         cached_lhs = (*simplify) (stmt, stmt);
471*404b540aSrobert     }
472*404b540aSrobert   else
473*404b540aSrobert     cached_lhs = NULL;
474*404b540aSrobert 
475*404b540aSrobert   return cached_lhs;
476*404b540aSrobert }
477*404b540aSrobert 
478*404b540aSrobert /* We are exiting E->src, see if E->dest ends with a conditional
479*404b540aSrobert    jump which has a known value when reached via E.
480*404b540aSrobert 
481*404b540aSrobert    Special care is necessary if E is a back edge in the CFG as we
482*404b540aSrobert    may have already recorded equivalences for E->dest into our
483*404b540aSrobert    various tables, including the result of the conditional at
484*404b540aSrobert    the end of E->dest.  Threading opportunities are severely
485*404b540aSrobert    limited in that case to avoid short-circuiting the loop
486*404b540aSrobert    incorrectly.
487*404b540aSrobert 
488*404b540aSrobert    Note it is quite common for the first block inside a loop to
489*404b540aSrobert    end with a conditional which is either always true or always
490*404b540aSrobert    false when reached via the loop backedge.  Thus we do not want
491*404b540aSrobert    to blindly disable threading across a loop backedge.  */
492*404b540aSrobert 
493*404b540aSrobert void
thread_across_edge(tree dummy_cond,edge e,bool handle_dominating_asserts,VEC (tree,heap)** stack,tree (* simplify)(tree,tree))494*404b540aSrobert thread_across_edge (tree dummy_cond,
495*404b540aSrobert 		    edge e,
496*404b540aSrobert 		    bool handle_dominating_asserts,
497*404b540aSrobert 		    VEC(tree, heap) **stack,
498*404b540aSrobert 		    tree (*simplify) (tree, tree))
499*404b540aSrobert {
500*404b540aSrobert   tree stmt;
501*404b540aSrobert 
502*404b540aSrobert   /* If E is a backedge, then we want to verify that the COND_EXPR,
503*404b540aSrobert      SWITCH_EXPR or GOTO_EXPR at the end of e->dest is not affected
504*404b540aSrobert      by any statements in e->dest.  If it is affected, then it is not
505*404b540aSrobert      safe to thread this edge.  */
506*404b540aSrobert   if (e->flags & EDGE_DFS_BACK)
507*404b540aSrobert     {
508*404b540aSrobert       ssa_op_iter iter;
509*404b540aSrobert       use_operand_p use_p;
510*404b540aSrobert       tree last = bsi_stmt (bsi_last (e->dest));
511*404b540aSrobert 
512*404b540aSrobert       FOR_EACH_SSA_USE_OPERAND (use_p, last, iter, SSA_OP_USE | SSA_OP_VUSE)
513*404b540aSrobert 	{
514*404b540aSrobert 	  tree use = USE_FROM_PTR (use_p);
515*404b540aSrobert 
516*404b540aSrobert           if (TREE_CODE (use) == SSA_NAME
517*404b540aSrobert 	      && TREE_CODE (SSA_NAME_DEF_STMT (use)) != PHI_NODE
518*404b540aSrobert 	      && bb_for_stmt (SSA_NAME_DEF_STMT (use)) == e->dest)
519*404b540aSrobert 	    goto fail;
520*404b540aSrobert 	}
521*404b540aSrobert     }
522*404b540aSrobert 
523*404b540aSrobert   stmt_count = 0;
524*404b540aSrobert 
525*404b540aSrobert   /* PHIs create temporary equivalences.  */
526*404b540aSrobert   if (!record_temporary_equivalences_from_phis (e, stack))
527*404b540aSrobert     goto fail;
528*404b540aSrobert 
529*404b540aSrobert   /* Now walk each statement recording any context sensitive
530*404b540aSrobert      temporary equivalences we can detect.  */
531*404b540aSrobert   stmt = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify);
532*404b540aSrobert   if (!stmt)
533*404b540aSrobert     goto fail;
534*404b540aSrobert 
535*404b540aSrobert   /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
536*404b540aSrobert      will be taken.  */
537*404b540aSrobert   if (TREE_CODE (stmt) == COND_EXPR
538*404b540aSrobert       || TREE_CODE (stmt) == GOTO_EXPR
539*404b540aSrobert       || TREE_CODE (stmt) == SWITCH_EXPR)
540*404b540aSrobert     {
541*404b540aSrobert       tree cond;
542*404b540aSrobert 
543*404b540aSrobert       /* Extract and simplify the condition.  */
544*404b540aSrobert       cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify, handle_dominating_asserts);
545*404b540aSrobert 
546*404b540aSrobert       if (cond && is_gimple_min_invariant (cond))
547*404b540aSrobert 	{
548*404b540aSrobert 	  edge taken_edge = find_taken_edge (e->dest, cond);
549*404b540aSrobert 	  basic_block dest = (taken_edge ? taken_edge->dest : NULL);
550*404b540aSrobert 
551*404b540aSrobert 	  if (dest == e->dest)
552*404b540aSrobert 	    goto fail;
553*404b540aSrobert 
554*404b540aSrobert 	  remove_temporary_equivalences (stack);
555*404b540aSrobert 	  register_jump_thread (e, taken_edge);
556*404b540aSrobert 	}
557*404b540aSrobert     }
558*404b540aSrobert 
559*404b540aSrobert  fail:
560*404b540aSrobert   remove_temporary_equivalences (stack);
561*404b540aSrobert }
562