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