OSDN Git Service

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