* be.po, ca.po, da.po, de.po, el.po, es.po, fr.po, ja.po, nl.po,
[official-gcc.git] / gcc / tree-ssa-ccp.c
blob6816dafd6c1b24c9d0489bf701c218a95b35a839
1 /* Conditional constant propagation pass for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005
3 Free Software Foundation, Inc.
4 Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
5 Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 2, or (at your option) any
12 later version.
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 02111-1307, USA. */
24 /* Conditional constant propagation (CCP) is based on the SSA
25 propagation engine (tree-ssa-propagate.c). Constant assignments of
26 the form VAR = CST are propagated from the assignments into uses of
27 VAR, which in turn may generate new constants. The simulation uses
28 a four level lattice to keep track of constant values associated
29 with SSA names. Given an SSA name V_i, it may take one of the
30 following values:
32 UNINITIALIZED -> This is the default starting value. V_i
33 has not been processed yet.
35 UNDEFINED -> V_i is a local variable whose definition
36 has not been processed yet. Therefore we
37 don't yet know if its value is a constant
38 or not.
40 CONSTANT -> V_i has been found to hold a constant
41 value C.
43 VARYING -> V_i cannot take a constant value, or if it
44 does, it is not possible to determine it
45 at compile time.
47 The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:
49 1- In ccp_visit_stmt, we are interested in assignments whose RHS
50 evaluates into a constant and conditional jumps whose predicate
51 evaluates into a boolean true or false. When an assignment of
52 the form V_i = CONST is found, V_i's lattice value is set to
53 CONSTANT and CONST is associated with it. This causes the
54 propagation engine to add all the SSA edges coming out the
55 assignment into the worklists, so that statements that use V_i
56 can be visited.
58 If the statement is a conditional with a constant predicate, we
59 mark the outgoing edges as executable or not executable
60 depending on the predicate's value. This is then used when
61 visiting PHI nodes to know when a PHI argument can be ignored.
64 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the
65 same constant C, then the LHS of the PHI is set to C. This
66 evaluation is known as the "meet operation". Since one of the
67 goals of this evaluation is to optimistically return constant
68 values as often as possible, it uses two main short cuts:
70 - If an argument is flowing in through a non-executable edge, it
71 is ignored. This is useful in cases like this:
73 if (PRED)
74 a_9 = 3;
75 else
76 a_10 = 100;
77 a_11 = PHI (a_9, a_10)
79 If PRED is known to always evaluate to false, then we can
80 assume that a_11 will always take its value from a_10, meaning
81 that instead of consider it VARYING (a_9 and a_10 have
82 different values), we can consider it CONSTANT 100.
84 - If an argument has an UNDEFINED value, then it does not affect
85 the outcome of the meet operation. If a variable V_i has an
86 UNDEFINED value, it means that either its defining statement
87 hasn't been visited yet or V_i has no defining statement, in
88 which case the original symbol 'V' is being used
89 uninitialized. Since 'V' is a local variable, the compiler
90 may assume any initial value for it.
93 After propagation, every variable V_i that ends up with a lattice
94 value of CONSTANT will have the associated constant value in the
95 array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for
96 final substitution and folding.
99 Constant propagation in stores and loads (STORE-CCP)
100 ----------------------------------------------------
102 While CCP has all the logic to propagate constants in GIMPLE
103 registers, it is missing the ability to associate constants with
104 stores and loads (i.e., pointer dereferences, structures and
105 global/aliased variables). We don't keep loads and stores in
106 SSA, but we do build a factored use-def web for them (in the
107 virtual operands).
109 For instance, consider the following code fragment:
111 struct A a;
112 const int B = 42;
114 void foo (int i)
116 if (i > 10)
117 a.a = 42;
118 else
120 a.b = 21;
121 a.a = a.b + 21;
124 if (a.a != B)
125 never_executed ();
128 We should be able to deduce that the predicate 'a.a != B' is always
129 false. To achieve this, we associate constant values to the SSA
130 names in the V_MAY_DEF and V_MUST_DEF operands for each store.
131 Additionally, since we also glob partial loads/stores with the base
132 symbol, we also keep track of the memory reference where the
133 constant value was stored (in the MEM_REF field of PROP_VALUE_T).
134 For instance,
136 # a_5 = V_MAY_DEF <a_4>
137 a.a = 2;
139 # VUSE <a_5>
140 x_3 = a.b;
142 In the example above, CCP will associate value '2' with 'a_5', but
143 it would be wrong to replace the load from 'a.b' with '2', because
144 '2' had been stored into a.a.
146 To support STORE-CCP, it is necessary to add a new value to the
147 constant propagation lattice. When evaluating a load for a memory
148 reference we can no longer assume a value of UNDEFINED if we
149 haven't seen a preceding store to the same memory location.
150 Consider, for instance global variables:
152 int A;
154 foo (int i)
156 if (i_3 > 10)
157 A_4 = 3;
158 # A_5 = PHI (A_4, A_2);
160 # VUSE <A_5>
161 A.0_6 = A;
163 return A.0_6;
166 The value of A_2 cannot be assumed to be UNDEFINED, as it may have
167 been defined outside of foo. If we were to assume it UNDEFINED, we
168 would erroneously optimize the above into 'return 3;'. Therefore,
169 when doing STORE-CCP, we introduce a fifth lattice value
170 (UNKNOWN_VAL), which overrides any other value when computing the
171 meet operation in PHI nodes.
173 Though STORE-CCP is not too expensive, it does have to do more work
174 than regular CCP, so it is only enabled at -O2. Both regular CCP
175 and STORE-CCP use the exact same algorithm. The only distinction
176 is that when doing STORE-CCP, the boolean variable DO_STORE_CCP is
177 set to true. This affects the evaluation of statements and PHI
178 nodes.
180 References:
182 Constant propagation with conditional branches,
183 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
185 Building an Optimizing Compiler,
186 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
188 Advanced Compiler Design and Implementation,
189 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
191 #include "config.h"
192 #include "system.h"
193 #include "coretypes.h"
194 #include "tm.h"
195 #include "tree.h"
196 #include "flags.h"
197 #include "rtl.h"
198 #include "tm_p.h"
199 #include "ggc.h"
200 #include "basic-block.h"
201 #include "output.h"
202 #include "expr.h"
203 #include "function.h"
204 #include "diagnostic.h"
205 #include "timevar.h"
206 #include "tree-dump.h"
207 #include "tree-flow.h"
208 #include "tree-pass.h"
209 #include "tree-ssa-propagate.h"
210 #include "langhooks.h"
211 #include "target.h"
214 /* Possible lattice values. */
215 typedef enum
217 UNINITIALIZED = 0,
218 UNDEFINED,
219 UNKNOWN_VAL,
220 CONSTANT,
221 VARYING
222 } ccp_lattice_t;
224 /* Array of propagated constant values. After propagation,
225 CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If
226 the constant is held in an SSA name representing a memory store
227 (i.e., a V_MAY_DEF or V_MUST_DEF), CONST_VAL[I].MEM_REF will
228 contain the actual memory reference used to store (i.e., the LHS of
229 the assignment doing the store). */
230 static prop_value_t *const_val;
232 /* True if we are also propagating constants in stores and loads. */
233 static bool do_store_ccp;
235 /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
237 static void
238 dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val)
240 switch (val.lattice_val)
242 case UNINITIALIZED:
243 fprintf (outf, "%sUNINITIALIZED", prefix);
244 break;
245 case UNDEFINED:
246 fprintf (outf, "%sUNDEFINED", prefix);
247 break;
248 case VARYING:
249 fprintf (outf, "%sVARYING", prefix);
250 break;
251 case UNKNOWN_VAL:
252 fprintf (outf, "%sUNKNOWN_VAL", prefix);
253 break;
254 case CONSTANT:
255 fprintf (outf, "%sCONSTANT ", prefix);
256 print_generic_expr (outf, val.value, dump_flags);
257 break;
258 default:
259 gcc_unreachable ();
264 /* Print lattice value VAL to stderr. */
266 void debug_lattice_value (prop_value_t val);
268 void
269 debug_lattice_value (prop_value_t val)
271 dump_lattice_value (stderr, "", val);
272 fprintf (stderr, "\n");
276 /* Compute a default value for variable VAR and store it in the
277 CONST_VAL array. The following rules are used to get default
278 values:
280 1- Global and static variables that are declared constant are
281 considered CONSTANT.
283 2- Any other value is considered UNDEFINED. This is useful when
284 considering PHI nodes. PHI arguments that are undefined do not
285 change the constant value of the PHI node, which allows for more
286 constants to be propagated.
288 3- If SSA_NAME_VALUE is set and it is a constant, its value is
289 used.
291 4- Variables defined by statements other than assignments and PHI
292 nodes are considered VARYING.
294 5- Variables that are not GIMPLE registers are considered
295 UNKNOWN_VAL, which is really a stronger version of UNDEFINED.
296 It's used to avoid the short circuit evaluation implied by
297 UNDEFINED in ccp_lattice_meet. */
299 static prop_value_t
300 get_default_value (tree var)
302 tree sym = SSA_NAME_VAR (var);
303 prop_value_t val = { UNINITIALIZED, NULL_TREE, NULL_TREE };
305 if (!do_store_ccp && !is_gimple_reg (var))
307 /* Short circuit for regular CCP. We are not interested in any
308 non-register when DO_STORE_CCP is false. */
309 val.lattice_val = VARYING;
311 else if (SSA_NAME_VALUE (var)
312 && is_gimple_min_invariant (SSA_NAME_VALUE (var)))
314 val.lattice_val = CONSTANT;
315 val.value = SSA_NAME_VALUE (var);
317 else if (TREE_STATIC (sym)
318 && TREE_READONLY (sym)
319 && DECL_INITIAL (sym)
320 && is_gimple_min_invariant (DECL_INITIAL (sym)))
322 /* Globals and static variables declared 'const' take their
323 initial value. */
324 val.lattice_val = CONSTANT;
325 val.value = DECL_INITIAL (sym);
326 val.mem_ref = sym;
328 else
330 tree stmt = SSA_NAME_DEF_STMT (var);
332 if (IS_EMPTY_STMT (stmt))
334 /* Variables defined by an empty statement are those used
335 before being initialized. If VAR is a local variable, we
336 can assume initially that it is UNDEFINED. If we are
337 doing STORE-CCP, function arguments and non-register
338 variables are initially UNKNOWN_VAL, because we cannot
339 discard the value incoming from outside of this function
340 (see ccp_lattice_meet for details). */
341 if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL)
342 val.lattice_val = UNDEFINED;
343 else if (do_store_ccp)
344 val.lattice_val = UNKNOWN_VAL;
345 else
346 val.lattice_val = VARYING;
348 else if (TREE_CODE (stmt) == MODIFY_EXPR
349 || TREE_CODE (stmt) == PHI_NODE)
351 /* Any other variable defined by an assignment or a PHI node
352 is considered UNDEFINED (or UNKNOWN_VAL if VAR is not a
353 GIMPLE register). */
354 val.lattice_val = is_gimple_reg (sym) ? UNDEFINED : UNKNOWN_VAL;
356 else
358 /* Otherwise, VAR will never take on a constant value. */
359 val.lattice_val = VARYING;
363 return val;
367 /* Get the constant value associated with variable VAR. If
368 MAY_USE_DEFAULT_P is true, call get_default_value on variables that
369 have the lattice value UNINITIALIZED. */
371 static prop_value_t *
372 get_value (tree var, bool may_use_default_p)
374 prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
375 if (may_use_default_p && val->lattice_val == UNINITIALIZED)
376 *val = get_default_value (var);
378 return val;
382 /* Set the value for variable VAR to NEW_VAL. Return true if the new
383 value is different from VAR's previous value. */
385 static bool
386 set_lattice_value (tree var, prop_value_t new_val)
388 prop_value_t *old_val = get_value (var, false);
390 /* Lattice transitions must always be monotonically increasing in
391 value. We allow two exceptions:
393 1- If *OLD_VAL and NEW_VAL are the same, return false to
394 inform the caller that this was a non-transition.
396 2- If we are doing store-ccp (i.e., DOING_STORE_CCP is true),
397 allow CONSTANT->UNKNOWN_VAL. The UNKNOWN_VAL state is a
398 special type of UNDEFINED state which prevents the short
399 circuit evaluation of PHI arguments (see ccp_visit_phi_node
400 and ccp_lattice_meet). */
401 gcc_assert (old_val->lattice_val <= new_val.lattice_val
402 || (old_val->lattice_val == new_val.lattice_val
403 && old_val->value == new_val.value
404 && old_val->mem_ref == new_val.mem_ref)
405 || (do_store_ccp
406 && old_val->lattice_val == CONSTANT
407 && new_val.lattice_val == UNKNOWN_VAL));
409 if (old_val->lattice_val != new_val.lattice_val)
411 if (dump_file && (dump_flags & TDF_DETAILS))
413 dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
414 fprintf (dump_file, ". %sdding SSA edges to worklist.\n",
415 new_val.lattice_val != UNDEFINED ? "A" : "Not a");
418 *old_val = new_val;
420 /* Transitions UNINITIALIZED -> UNDEFINED are never interesting
421 for propagation purposes. In these cases return false to
422 avoid doing useless work. */
423 return (new_val.lattice_val != UNDEFINED);
426 return false;
430 /* Return the likely CCP lattice value for STMT.
432 If STMT has no operands, then return CONSTANT.
434 Else if any operands of STMT are undefined, then return UNDEFINED.
436 Else if any operands of STMT are constants, then return CONSTANT.
438 Else return VARYING. */
440 static ccp_lattice_t
441 likely_value (tree stmt)
443 bool found_constant;
444 stmt_ann_t ann;
445 tree use;
446 ssa_op_iter iter;
448 ann = stmt_ann (stmt);
450 /* If the statement has volatile operands, it won't fold to a
451 constant value. */
452 if (ann->has_volatile_ops)
453 return VARYING;
455 /* If we are not doing store-ccp, statements with loads
456 and/or stores will never fold into a constant. */
457 if (!do_store_ccp
458 && (ann->makes_aliased_stores
459 || ann->makes_aliased_loads
460 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
461 return VARYING;
464 /* A CALL_EXPR is assumed to be varying. NOTE: This may be overly
465 conservative, in the presence of const and pure calls. */
466 if (get_call_expr_in (stmt) != NULL_TREE)
467 return VARYING;
469 /* Anything other than assignments and conditional jumps are not
470 interesting for CCP. */
471 if (TREE_CODE (stmt) != MODIFY_EXPR
472 && TREE_CODE (stmt) != COND_EXPR
473 && TREE_CODE (stmt) != SWITCH_EXPR)
474 return VARYING;
476 found_constant = false;
477 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE|SSA_OP_VUSE)
479 prop_value_t *val = get_value (use, true);
481 if (val->lattice_val == VARYING)
482 return VARYING;
484 if (val->lattice_val == UNKNOWN_VAL)
486 /* UNKNOWN_VAL is invalid when not doing STORE-CCP. */
487 gcc_assert (do_store_ccp);
488 return UNKNOWN_VAL;
491 if (val->lattice_val == CONSTANT)
492 found_constant = true;
495 if (found_constant
496 || ZERO_SSA_OPERANDS (stmt, SSA_OP_USE)
497 || ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
498 return CONSTANT;
500 return UNDEFINED;
504 /* Initialize local data structures for CCP. */
506 static void
507 ccp_initialize (void)
509 basic_block bb;
511 const_val = xmalloc (num_ssa_names * sizeof (*const_val));
512 memset (const_val, 0, num_ssa_names * sizeof (*const_val));
514 /* Initialize simulation flags for PHI nodes and statements. */
515 FOR_EACH_BB (bb)
517 block_stmt_iterator i;
519 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
521 bool is_varying = false;
522 tree stmt = bsi_stmt (i);
524 if (likely_value (stmt) == VARYING)
527 tree def;
528 ssa_op_iter iter;
530 /* If the statement will not produce a constant, mark
531 all its outputs VARYING. */
532 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
533 get_value (def, false)->lattice_val = VARYING;
535 /* Never mark conditional jumps with DONT_SIMULATE_AGAIN,
536 otherwise the propagator will never add the outgoing
537 control edges. */
538 if (TREE_CODE (stmt) != COND_EXPR
539 && TREE_CODE (stmt) != SWITCH_EXPR)
540 is_varying = true;
543 DONT_SIMULATE_AGAIN (stmt) = is_varying;
547 /* Now process PHI nodes. */
548 FOR_EACH_BB (bb)
550 tree phi;
552 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
554 int i;
555 tree arg;
556 prop_value_t *val = get_value (PHI_RESULT (phi), false);
558 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
560 arg = PHI_ARG_DEF (phi, i);
562 if (TREE_CODE (arg) == SSA_NAME
563 && get_value (arg, false)->lattice_val == VARYING)
565 val->lattice_val = VARYING;
566 break;
570 DONT_SIMULATE_AGAIN (phi) = (val->lattice_val == VARYING);
576 /* Do final substitution of propagated values, cleanup the flowgraph and
577 free allocated storage. */
579 static void
580 ccp_finalize (void)
582 /* Perform substitutions based on the known constant values. */
583 substitute_and_fold (const_val, false);
585 free (const_val);
589 /* Compute the meet operator between *VAL1 and *VAL2. Store the result
590 in VAL1.
592 any M UNDEFINED = any
593 any M UNKNOWN_VAL = UNKNOWN_VAL
594 any M VARYING = VARYING
595 Ci M Cj = Ci if (i == j)
596 Ci M Cj = VARYING if (i != j)
598 Lattice values UNKNOWN_VAL and UNDEFINED are similar but have
599 different semantics at PHI nodes. Both values imply that we don't
600 know whether the variable is constant or not. However, UNKNOWN_VAL
601 values override all others. For instance, suppose that A is a
602 global variable:
604 +------+
606 | / \
607 | / \
608 | | A_1 = 4
609 | \ /
610 | \ /
611 | A_3 = PHI (A_2, A_1)
612 | ... = A_3
614 +----+
616 If the edge into A_2 is not executable, the first visit to A_3 will
617 yield the constant 4. But the second visit to A_3 will be with A_2
618 in state UNKNOWN_VAL. We can no longer conclude that A_3 is 4
619 because A_2 may have been set in another function. If we had used
620 the lattice value UNDEFINED, we would have had wrongly concluded
621 that A_3 is 4. */
624 static void
625 ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2)
627 if (val1->lattice_val == UNDEFINED)
629 /* UNDEFINED M any = any */
630 *val1 = *val2;
632 else if (val2->lattice_val == UNDEFINED)
634 /* any M UNDEFINED = any
635 Nothing to do. VAL1 already contains the value we want. */
638 else if (val1->lattice_val == UNKNOWN_VAL
639 || val2->lattice_val == UNKNOWN_VAL)
641 /* UNKNOWN_VAL values are invalid if we are not doing STORE-CCP. */
642 gcc_assert (do_store_ccp);
644 /* any M UNKNOWN_VAL = UNKNOWN_VAL. */
645 val1->lattice_val = UNKNOWN_VAL;
646 val1->value = NULL_TREE;
647 val1->mem_ref = NULL_TREE;
649 else if (val1->lattice_val == VARYING
650 || val2->lattice_val == VARYING)
652 /* any M VARYING = VARYING. */
653 val1->lattice_val = VARYING;
654 val1->value = NULL_TREE;
655 val1->mem_ref = NULL_TREE;
657 else if (val1->lattice_val == CONSTANT
658 && val2->lattice_val == CONSTANT
659 && simple_cst_equal (val1->value, val2->value) == 1
660 && (!do_store_ccp
661 || simple_cst_equal (val1->mem_ref, val2->mem_ref) == 1))
663 /* Ci M Cj = Ci if (i == j)
664 Ci M Cj = VARYING if (i != j)
666 If these two values come from memory stores, make sure that
667 they come from the same memory reference. */
668 val1->lattice_val = CONSTANT;
669 val1->value = val1->value;
670 val1->mem_ref = val1->mem_ref;
672 else
674 /* Any other combination is VARYING. */
675 val1->lattice_val = VARYING;
676 val1->value = NULL_TREE;
677 val1->mem_ref = NULL_TREE;
682 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
683 lattice values to determine PHI_NODE's lattice value. The value of a
684 PHI node is determined calling ccp_lattice_meet with all the arguments
685 of the PHI node that are incoming via executable edges. */
687 static enum ssa_prop_result
688 ccp_visit_phi_node (tree phi)
690 int i;
691 prop_value_t *old_val, new_val;
693 if (dump_file && (dump_flags & TDF_DETAILS))
695 fprintf (dump_file, "\nVisiting PHI node: ");
696 print_generic_expr (dump_file, phi, dump_flags);
699 old_val = get_value (PHI_RESULT (phi), false);
700 switch (old_val->lattice_val)
702 case VARYING:
703 return SSA_PROP_VARYING;
705 case CONSTANT:
706 new_val = *old_val;
707 break;
709 case UNKNOWN_VAL:
710 /* To avoid the default value of UNKNOWN_VAL overriding
711 that of its possible constant arguments, temporarily
712 set the PHI node's default lattice value to be
713 UNDEFINED. If the PHI node's old value was UNKNOWN_VAL and
714 the new value is UNDEFINED, then we prevent the invalid
715 transition by not calling set_lattice_value. */
716 gcc_assert (do_store_ccp);
718 /* FALLTHRU */
720 case UNDEFINED:
721 case UNINITIALIZED:
722 new_val.lattice_val = UNDEFINED;
723 new_val.value = NULL_TREE;
724 new_val.mem_ref = NULL_TREE;
725 break;
727 default:
728 gcc_unreachable ();
731 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
733 /* Compute the meet operator over all the PHI arguments flowing
734 through executable edges. */
735 edge e = PHI_ARG_EDGE (phi, i);
737 if (dump_file && (dump_flags & TDF_DETAILS))
739 fprintf (dump_file,
740 "\n Argument #%d (%d -> %d %sexecutable)\n",
741 i, e->src->index, e->dest->index,
742 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
745 /* If the incoming edge is executable, Compute the meet operator for
746 the existing value of the PHI node and the current PHI argument. */
747 if (e->flags & EDGE_EXECUTABLE)
749 tree arg = PHI_ARG_DEF (phi, i);
750 prop_value_t arg_val;
752 if (is_gimple_min_invariant (arg))
754 arg_val.lattice_val = CONSTANT;
755 arg_val.value = arg;
756 arg_val.mem_ref = NULL_TREE;
758 else
759 arg_val = *(get_value (arg, true));
761 ccp_lattice_meet (&new_val, &arg_val);
763 if (dump_file && (dump_flags & TDF_DETAILS))
765 fprintf (dump_file, "\t");
766 print_generic_expr (dump_file, arg, dump_flags);
767 dump_lattice_value (dump_file, "\tValue: ", arg_val);
768 fprintf (dump_file, "\n");
771 if (new_val.lattice_val == VARYING)
772 break;
776 if (dump_file && (dump_flags & TDF_DETAILS))
778 dump_lattice_value (dump_file, "\n PHI node value: ", new_val);
779 fprintf (dump_file, "\n\n");
782 /* Check for an invalid change from UNKNOWN_VAL to UNDEFINED. */
783 if (do_store_ccp
784 && old_val->lattice_val == UNKNOWN_VAL
785 && new_val.lattice_val == UNDEFINED)
786 return SSA_PROP_NOT_INTERESTING;
788 /* Otherwise, make the transition to the new value. */
789 if (set_lattice_value (PHI_RESULT (phi), new_val))
791 if (new_val.lattice_val == VARYING)
792 return SSA_PROP_VARYING;
793 else
794 return SSA_PROP_INTERESTING;
796 else
797 return SSA_PROP_NOT_INTERESTING;
801 /* CCP specific front-end to the non-destructive constant folding
802 routines.
804 Attempt to simplify the RHS of STMT knowing that one or more
805 operands are constants.
807 If simplification is possible, return the simplified RHS,
808 otherwise return the original RHS. */
810 static tree
811 ccp_fold (tree stmt)
813 tree rhs = get_rhs (stmt);
814 enum tree_code code = TREE_CODE (rhs);
815 enum tree_code_class kind = TREE_CODE_CLASS (code);
816 tree retval = NULL_TREE;
818 if (TREE_CODE (rhs) == SSA_NAME)
820 /* If the RHS is an SSA_NAME, return its known constant value,
821 if any. */
822 return get_value (rhs, true)->value;
824 else if (do_store_ccp && stmt_makes_single_load (stmt))
826 /* If the RHS is a memory load, see if the VUSEs associated with
827 it are a valid constant for that memory load. */
828 prop_value_t *val = get_value_loaded_by (stmt, const_val);
829 if (val && simple_cst_equal (val->mem_ref, rhs) == 1)
830 return val->value;
831 else
832 return NULL_TREE;
835 /* Unary operators. Note that we know the single operand must
836 be a constant. So this should almost always return a
837 simplified RHS. */
838 if (kind == tcc_unary)
840 /* Handle unary operators which can appear in GIMPLE form. */
841 tree op0 = TREE_OPERAND (rhs, 0);
843 /* Simplify the operand down to a constant. */
844 if (TREE_CODE (op0) == SSA_NAME)
846 prop_value_t *val = get_value (op0, true);
847 if (val->lattice_val == CONSTANT)
848 op0 = get_value (op0, true)->value;
851 return fold_unary (code, TREE_TYPE (rhs), op0);
854 /* Binary and comparison operators. We know one or both of the
855 operands are constants. */
856 else if (kind == tcc_binary
857 || kind == tcc_comparison
858 || code == TRUTH_AND_EXPR
859 || code == TRUTH_OR_EXPR
860 || code == TRUTH_XOR_EXPR)
862 /* Handle binary and comparison operators that can appear in
863 GIMPLE form. */
864 tree op0 = TREE_OPERAND (rhs, 0);
865 tree op1 = TREE_OPERAND (rhs, 1);
867 /* Simplify the operands down to constants when appropriate. */
868 if (TREE_CODE (op0) == SSA_NAME)
870 prop_value_t *val = get_value (op0, true);
871 if (val->lattice_val == CONSTANT)
872 op0 = val->value;
875 if (TREE_CODE (op1) == SSA_NAME)
877 prop_value_t *val = get_value (op1, true);
878 if (val->lattice_val == CONSTANT)
879 op1 = val->value;
882 return fold_binary (code, TREE_TYPE (rhs), op0, op1);
885 /* We may be able to fold away calls to builtin functions if their
886 arguments are constants. */
887 else if (code == CALL_EXPR
888 && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
889 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
890 == FUNCTION_DECL)
891 && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
893 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_USE))
895 tree *orig, var;
896 tree fndecl, arglist;
897 size_t i = 0;
898 ssa_op_iter iter;
899 use_operand_p var_p;
901 /* Preserve the original values of every operand. */
902 orig = xmalloc (sizeof (tree) * NUM_SSA_OPERANDS (stmt, SSA_OP_USE));
903 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
904 orig[i++] = var;
906 /* Substitute operands with their values and try to fold. */
907 replace_uses_in (stmt, NULL, const_val);
908 fndecl = get_callee_fndecl (rhs);
909 arglist = TREE_OPERAND (rhs, 1);
910 retval = fold_builtin (fndecl, arglist, false);
912 /* Restore operands to their original form. */
913 i = 0;
914 FOR_EACH_SSA_USE_OPERAND (var_p, stmt, iter, SSA_OP_USE)
915 SET_USE (var_p, orig[i++]);
916 free (orig);
919 else
920 return rhs;
922 /* If we got a simplified form, see if we need to convert its type. */
923 if (retval)
924 return fold_convert (TREE_TYPE (rhs), retval);
926 /* No simplification was possible. */
927 return rhs;
931 /* Return the tree representing the element referenced by T if T is an
932 ARRAY_REF or COMPONENT_REF into constant aggregates. Return
933 NULL_TREE otherwise. */
935 static tree
936 fold_const_aggregate_ref (tree t)
938 prop_value_t *value;
939 tree base, ctor, idx, field, elt;
941 switch (TREE_CODE (t))
943 case ARRAY_REF:
944 /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its
945 DECL_INITIAL. If BASE is a nested reference into another
946 ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
947 the inner reference. */
948 base = TREE_OPERAND (t, 0);
949 switch (TREE_CODE (base))
951 case VAR_DECL:
952 if (!TREE_READONLY (base)
953 || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE
954 || !targetm.binds_local_p (base))
955 return NULL_TREE;
957 ctor = DECL_INITIAL (base);
958 break;
960 case ARRAY_REF:
961 case COMPONENT_REF:
962 ctor = fold_const_aggregate_ref (base);
963 break;
965 default:
966 return NULL_TREE;
969 if (ctor == NULL_TREE
970 || TREE_CODE (ctor) != CONSTRUCTOR
971 || !TREE_STATIC (ctor))
972 return NULL_TREE;
974 /* Get the index. If we have an SSA_NAME, try to resolve it
975 with the current lattice value for the SSA_NAME. */
976 idx = TREE_OPERAND (t, 1);
977 switch (TREE_CODE (idx))
979 case SSA_NAME:
980 if ((value = get_value (idx, true))
981 && value->lattice_val == CONSTANT
982 && TREE_CODE (value->value) == INTEGER_CST)
983 idx = value->value;
984 else
985 return NULL_TREE;
986 break;
988 case INTEGER_CST:
989 break;
991 default:
992 return NULL_TREE;
995 /* Whoo-hoo! I'll fold ya baby. Yeah! */
996 for (elt = CONSTRUCTOR_ELTS (ctor);
997 (elt && !tree_int_cst_equal (TREE_PURPOSE (elt), idx));
998 elt = TREE_CHAIN (elt))
1001 if (elt)
1002 return TREE_VALUE (elt);
1003 break;
1005 case COMPONENT_REF:
1006 /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its
1007 DECL_INITIAL. If BASE is a nested reference into another
1008 ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
1009 the inner reference. */
1010 base = TREE_OPERAND (t, 0);
1011 switch (TREE_CODE (base))
1013 case VAR_DECL:
1014 if (!TREE_READONLY (base)
1015 || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE
1016 || !targetm.binds_local_p (base))
1017 return NULL_TREE;
1019 ctor = DECL_INITIAL (base);
1020 break;
1022 case ARRAY_REF:
1023 case COMPONENT_REF:
1024 ctor = fold_const_aggregate_ref (base);
1025 break;
1027 default:
1028 return NULL_TREE;
1031 if (ctor == NULL_TREE
1032 || TREE_CODE (ctor) != CONSTRUCTOR
1033 || !TREE_STATIC (ctor))
1034 return NULL_TREE;
1036 field = TREE_OPERAND (t, 1);
1038 for (elt = CONSTRUCTOR_ELTS (ctor); elt; elt = TREE_CHAIN (elt))
1039 if (TREE_PURPOSE (elt) == field
1040 /* FIXME: Handle bit-fields. */
1041 && ! DECL_BIT_FIELD (TREE_PURPOSE (elt)))
1042 return TREE_VALUE (elt);
1043 break;
1045 default:
1046 break;
1049 return NULL_TREE;
1052 /* Evaluate statement STMT. */
1054 static prop_value_t
1055 evaluate_stmt (tree stmt)
1057 prop_value_t val;
1058 tree simplified;
1059 ccp_lattice_t likelyvalue = likely_value (stmt);
1061 val.mem_ref = NULL_TREE;
1063 /* If the statement is likely to have a CONSTANT result, then try
1064 to fold the statement to determine the constant value. */
1065 if (likelyvalue == CONSTANT)
1066 simplified = ccp_fold (stmt);
1067 /* If the statement is likely to have a VARYING result, then do not
1068 bother folding the statement. */
1069 else if (likelyvalue == VARYING)
1070 simplified = get_rhs (stmt);
1071 /* If the statement is an ARRAY_REF or COMPONENT_REF into constant
1072 aggregates, extract the referenced constant. Otherwise the
1073 statement is likely to have an UNDEFINED value, and there will be
1074 nothing to do. Note that fold_const_aggregate_ref returns
1075 NULL_TREE if the first case does not match. */
1076 else
1077 simplified = fold_const_aggregate_ref (get_rhs (stmt));
1079 if (simplified && is_gimple_min_invariant (simplified))
1081 /* The statement produced a constant value. */
1082 val.lattice_val = CONSTANT;
1083 val.value = simplified;
1085 else
1087 /* The statement produced a nonconstant value. If the statement
1088 had UNDEFINED operands, then the result of the statement
1089 should be UNDEFINED. Otherwise, the statement is VARYING. */
1090 val.lattice_val = (likelyvalue == UNDEFINED) ? UNDEFINED : VARYING;
1091 val.value = NULL_TREE;
1094 return val;
1098 /* Visit the assignment statement STMT. Set the value of its LHS to the
1099 value computed by the RHS and store LHS in *OUTPUT_P. If STMT
1100 creates virtual definitions, set the value of each new name to that
1101 of the RHS (if we can derive a constant out of the RHS). */
1103 static enum ssa_prop_result
1104 visit_assignment (tree stmt, tree *output_p)
1106 prop_value_t val;
1107 tree lhs, rhs;
1108 enum ssa_prop_result retval;
1110 lhs = TREE_OPERAND (stmt, 0);
1111 rhs = TREE_OPERAND (stmt, 1);
1113 if (TREE_CODE (rhs) == SSA_NAME)
1115 /* For a simple copy operation, we copy the lattice values. */
1116 prop_value_t *nval = get_value (rhs, true);
1117 val = *nval;
1119 else if (do_store_ccp && stmt_makes_single_load (stmt))
1121 /* Same as above, but the RHS is not a gimple register and yet
1122 has a known VUSE. If STMT is loading from the same memory
1123 location that created the SSA_NAMEs for the virtual operands,
1124 we can propagate the value on the RHS. */
1125 prop_value_t *nval = get_value_loaded_by (stmt, const_val);
1127 if (nval && simple_cst_equal (nval->mem_ref, rhs) == 1)
1128 val = *nval;
1129 else
1130 val = evaluate_stmt (stmt);
1132 else
1133 /* Evaluate the statement. */
1134 val = evaluate_stmt (stmt);
1136 /* If the original LHS was a VIEW_CONVERT_EXPR, modify the constant
1137 value to be a VIEW_CONVERT_EXPR of the old constant value.
1139 ??? Also, if this was a definition of a bitfield, we need to widen
1140 the constant value into the type of the destination variable. This
1141 should not be necessary if GCC represented bitfields properly. */
1143 tree orig_lhs = TREE_OPERAND (stmt, 0);
1145 if (TREE_CODE (orig_lhs) == VIEW_CONVERT_EXPR
1146 && val.lattice_val == CONSTANT)
1148 tree w = fold (build1 (VIEW_CONVERT_EXPR,
1149 TREE_TYPE (TREE_OPERAND (orig_lhs, 0)),
1150 val.value));
1152 orig_lhs = TREE_OPERAND (orig_lhs, 0);
1153 if (w && is_gimple_min_invariant (w))
1154 val.value = w;
1155 else
1157 val.lattice_val = VARYING;
1158 val.value = NULL;
1162 if (val.lattice_val == CONSTANT
1163 && TREE_CODE (orig_lhs) == COMPONENT_REF
1164 && DECL_BIT_FIELD (TREE_OPERAND (orig_lhs, 1)))
1166 tree w = widen_bitfield (val.value, TREE_OPERAND (orig_lhs, 1),
1167 orig_lhs);
1169 if (w && is_gimple_min_invariant (w))
1170 val.value = w;
1171 else
1173 val.lattice_val = VARYING;
1174 val.value = NULL_TREE;
1175 val.mem_ref = NULL_TREE;
1180 retval = SSA_PROP_NOT_INTERESTING;
1182 /* Set the lattice value of the statement's output. */
1183 if (TREE_CODE (lhs) == SSA_NAME)
1185 /* If STMT is an assignment to an SSA_NAME, we only have one
1186 value to set. */
1187 if (set_lattice_value (lhs, val))
1189 *output_p = lhs;
1190 if (val.lattice_val == VARYING)
1191 retval = SSA_PROP_VARYING;
1192 else
1193 retval = SSA_PROP_INTERESTING;
1196 else if (do_store_ccp && stmt_makes_single_store (stmt))
1198 /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands
1199 to the new constant value and mark the LHS as the memory
1200 reference associated with VAL. */
1201 ssa_op_iter i;
1202 tree vdef;
1203 bool changed;
1205 /* Stores cannot take on an UNDEFINED value. */
1206 if (val.lattice_val == UNDEFINED)
1207 val.lattice_val = UNKNOWN_VAL;
1209 /* Mark VAL as stored in the LHS of this assignment. */
1210 val.mem_ref = lhs;
1212 /* Set the value of every VDEF to VAL. */
1213 changed = false;
1214 FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
1215 changed |= set_lattice_value (vdef, val);
1217 /* Note that for propagation purposes, we are only interested in
1218 visiting statements that load the exact same memory reference
1219 stored here. Those statements will have the exact same list
1220 of virtual uses, so it is enough to set the output of this
1221 statement to be its first virtual definition. */
1222 *output_p = first_vdef (stmt);
1223 if (changed)
1225 if (val.lattice_val == VARYING)
1226 retval = SSA_PROP_VARYING;
1227 else
1228 retval = SSA_PROP_INTERESTING;
1232 return retval;
1236 /* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
1237 if it can determine which edge will be taken. Otherwise, return
1238 SSA_PROP_VARYING. */
1240 static enum ssa_prop_result
1241 visit_cond_stmt (tree stmt, edge *taken_edge_p)
1243 prop_value_t val;
1244 basic_block block;
1246 block = bb_for_stmt (stmt);
1247 val = evaluate_stmt (stmt);
1249 /* Find which edge out of the conditional block will be taken and add it
1250 to the worklist. If no single edge can be determined statically,
1251 return SSA_PROP_VARYING to feed all the outgoing edges to the
1252 propagation engine. */
1253 *taken_edge_p = val.value ? find_taken_edge (block, val.value) : 0;
1254 if (*taken_edge_p)
1255 return SSA_PROP_INTERESTING;
1256 else
1257 return SSA_PROP_VARYING;
1261 /* Evaluate statement STMT. If the statement produces an output value and
1262 its evaluation changes the lattice value of its output, return
1263 SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
1264 output value.
1266 If STMT is a conditional branch and we can determine its truth
1267 value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying
1268 value, return SSA_PROP_VARYING. */
1270 static enum ssa_prop_result
1271 ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
1273 tree def;
1274 ssa_op_iter iter;
1276 if (dump_file && (dump_flags & TDF_DETAILS))
1278 fprintf (dump_file, "\nVisiting statement:\n");
1279 print_generic_stmt (dump_file, stmt, dump_flags);
1280 fprintf (dump_file, "\n");
1283 if (TREE_CODE (stmt) == MODIFY_EXPR)
1285 /* If the statement is an assignment that produces a single
1286 output value, evaluate its RHS to see if the lattice value of
1287 its output has changed. */
1288 return visit_assignment (stmt, output_p);
1290 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1292 /* If STMT is a conditional branch, see if we can determine
1293 which branch will be taken. */
1294 return visit_cond_stmt (stmt, taken_edge_p);
1297 /* Any other kind of statement is not interesting for constant
1298 propagation and, therefore, not worth simulating. */
1299 if (dump_file && (dump_flags & TDF_DETAILS))
1300 fprintf (dump_file, "No interesting values produced. Marked VARYING.\n");
1302 /* Definitions made by statements other than assignments to
1303 SSA_NAMEs represent unknown modifications to their outputs.
1304 Mark them VARYING. */
1305 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
1307 prop_value_t v = { VARYING, NULL_TREE, NULL_TREE };
1308 set_lattice_value (def, v);
1311 return SSA_PROP_VARYING;
1315 /* Main entry point for SSA Conditional Constant Propagation. */
1317 static void
1318 execute_ssa_ccp (bool store_ccp)
1320 do_store_ccp = store_ccp;
1321 ccp_initialize ();
1322 ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
1323 ccp_finalize ();
1327 static void
1328 do_ssa_ccp (void)
1330 execute_ssa_ccp (false);
1334 static bool
1335 gate_ccp (void)
1337 return flag_tree_ccp != 0;
1341 struct tree_opt_pass pass_ccp =
1343 "ccp", /* name */
1344 gate_ccp, /* gate */
1345 do_ssa_ccp, /* execute */
1346 NULL, /* sub */
1347 NULL, /* next */
1348 0, /* static_pass_number */
1349 TV_TREE_CCP, /* tv_id */
1350 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1351 0, /* properties_provided */
1352 0, /* properties_destroyed */
1353 0, /* todo_flags_start */
1354 TODO_cleanup_cfg | TODO_dump_func | TODO_update_ssa
1355 | TODO_ggc_collect | TODO_verify_ssa
1356 | TODO_verify_stmts, /* todo_flags_finish */
1357 0 /* letter */
1361 static void
1362 do_ssa_store_ccp (void)
1364 /* If STORE-CCP is not enabled, we just run regular CCP. */
1365 execute_ssa_ccp (flag_tree_store_ccp != 0);
1368 static bool
1369 gate_store_ccp (void)
1371 /* STORE-CCP is enabled only with -ftree-store-ccp, but when
1372 -fno-tree-store-ccp is specified, we should run regular CCP.
1373 That's why the pass is enabled with either flag. */
1374 return flag_tree_store_ccp != 0 || flag_tree_ccp != 0;
1378 struct tree_opt_pass pass_store_ccp =
1380 "store_ccp", /* name */
1381 gate_store_ccp, /* gate */
1382 do_ssa_store_ccp, /* execute */
1383 NULL, /* sub */
1384 NULL, /* next */
1385 0, /* static_pass_number */
1386 TV_TREE_STORE_CCP, /* tv_id */
1387 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1388 0, /* properties_provided */
1389 0, /* properties_destroyed */
1390 0, /* todo_flags_start */
1391 TODO_dump_func | TODO_update_ssa
1392 | TODO_ggc_collect | TODO_verify_ssa
1393 | TODO_cleanup_cfg
1394 | TODO_verify_stmts, /* todo_flags_finish */
1395 0 /* letter */
1398 /* Given a constant value VAL for bitfield FIELD, and a destination
1399 variable VAR, return VAL appropriately widened to fit into VAR. If
1400 FIELD is wider than HOST_WIDE_INT, NULL is returned. */
1402 tree
1403 widen_bitfield (tree val, tree field, tree var)
1405 unsigned HOST_WIDE_INT var_size, field_size;
1406 tree wide_val;
1407 unsigned HOST_WIDE_INT mask;
1408 unsigned int i;
1410 /* We can only do this if the size of the type and field and VAL are
1411 all constants representable in HOST_WIDE_INT. */
1412 if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1)
1413 || !host_integerp (DECL_SIZE (field), 1)
1414 || !host_integerp (val, 0))
1415 return NULL_TREE;
1417 var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1);
1418 field_size = tree_low_cst (DECL_SIZE (field), 1);
1420 /* Give up if either the bitfield or the variable are too wide. */
1421 if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT)
1422 return NULL_TREE;
1424 gcc_assert (var_size >= field_size);
1426 /* If the sign bit of the value is not set or the field's type is unsigned,
1427 just mask off the high order bits of the value. */
1428 if (DECL_UNSIGNED (field)
1429 || !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1))))
1431 /* Zero extension. Build a mask with the lower 'field_size' bits
1432 set and a BIT_AND_EXPR node to clear the high order bits of
1433 the value. */
1434 for (i = 0, mask = 0; i < field_size; i++)
1435 mask |= ((HOST_WIDE_INT) 1) << i;
1437 wide_val = build2 (BIT_AND_EXPR, TREE_TYPE (var), val,
1438 build_int_cst (TREE_TYPE (var), mask));
1440 else
1442 /* Sign extension. Create a mask with the upper 'field_size'
1443 bits set and a BIT_IOR_EXPR to set the high order bits of the
1444 value. */
1445 for (i = 0, mask = 0; i < (var_size - field_size); i++)
1446 mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1);
1448 wide_val = build2 (BIT_IOR_EXPR, TREE_TYPE (var), val,
1449 build_int_cst (TREE_TYPE (var), mask));
1452 return fold (wide_val);
1456 /* A subroutine of fold_stmt_r. Attempts to fold *(A+O) to A[X].
1457 BASE is an array type. OFFSET is a byte displacement. ORIG_TYPE
1458 is the desired result type. */
1460 static tree
1461 maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type)
1463 tree min_idx, idx, elt_offset = integer_zero_node;
1464 tree array_type, elt_type, elt_size;
1466 /* If BASE is an ARRAY_REF, we can pick up another offset (this time
1467 measured in units of the size of elements type) from that ARRAY_REF).
1468 We can't do anything if either is variable.
1470 The case we handle here is *(&A[N]+O). */
1471 if (TREE_CODE (base) == ARRAY_REF)
1473 tree low_bound = array_ref_low_bound (base);
1475 elt_offset = TREE_OPERAND (base, 1);
1476 if (TREE_CODE (low_bound) != INTEGER_CST
1477 || TREE_CODE (elt_offset) != INTEGER_CST)
1478 return NULL_TREE;
1480 elt_offset = int_const_binop (MINUS_EXPR, elt_offset, low_bound, 0);
1481 base = TREE_OPERAND (base, 0);
1484 /* Ignore stupid user tricks of indexing non-array variables. */
1485 array_type = TREE_TYPE (base);
1486 if (TREE_CODE (array_type) != ARRAY_TYPE)
1487 return NULL_TREE;
1488 elt_type = TREE_TYPE (array_type);
1489 if (!lang_hooks.types_compatible_p (orig_type, elt_type))
1490 return NULL_TREE;
1492 /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the
1493 element type (so we can use the alignment if it's not constant).
1494 Otherwise, compute the offset as an index by using a division. If the
1495 division isn't exact, then don't do anything. */
1496 elt_size = TYPE_SIZE_UNIT (elt_type);
1497 if (integer_zerop (offset))
1499 if (TREE_CODE (elt_size) != INTEGER_CST)
1500 elt_size = size_int (TYPE_ALIGN (elt_type));
1502 idx = integer_zero_node;
1504 else
1506 unsigned HOST_WIDE_INT lquo, lrem;
1507 HOST_WIDE_INT hquo, hrem;
1509 if (TREE_CODE (elt_size) != INTEGER_CST
1510 || div_and_round_double (TRUNC_DIV_EXPR, 1,
1511 TREE_INT_CST_LOW (offset),
1512 TREE_INT_CST_HIGH (offset),
1513 TREE_INT_CST_LOW (elt_size),
1514 TREE_INT_CST_HIGH (elt_size),
1515 &lquo, &hquo, &lrem, &hrem)
1516 || lrem || hrem)
1517 return NULL_TREE;
1519 idx = build_int_cst_wide (NULL_TREE, lquo, hquo);
1522 /* Assume the low bound is zero. If there is a domain type, get the
1523 low bound, if any, convert the index into that type, and add the
1524 low bound. */
1525 min_idx = integer_zero_node;
1526 if (TYPE_DOMAIN (array_type))
1528 if (TYPE_MIN_VALUE (TYPE_DOMAIN (array_type)))
1529 min_idx = TYPE_MIN_VALUE (TYPE_DOMAIN (array_type));
1530 else
1531 min_idx = fold_convert (TYPE_DOMAIN (array_type), min_idx);
1533 if (TREE_CODE (min_idx) != INTEGER_CST)
1534 return NULL_TREE;
1536 idx = fold_convert (TYPE_DOMAIN (array_type), idx);
1537 elt_offset = fold_convert (TYPE_DOMAIN (array_type), elt_offset);
1540 if (!integer_zerop (min_idx))
1541 idx = int_const_binop (PLUS_EXPR, idx, min_idx, 0);
1542 if (!integer_zerop (elt_offset))
1543 idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0);
1545 return build (ARRAY_REF, orig_type, base, idx, min_idx,
1546 size_int (tree_low_cst (elt_size, 1)
1547 / (TYPE_ALIGN_UNIT (elt_type))));
1551 /* A subroutine of fold_stmt_r. Attempts to fold *(S+O) to S.X.
1552 BASE is a record type. OFFSET is a byte displacement. ORIG_TYPE
1553 is the desired result type. */
1554 /* ??? This doesn't handle class inheritance. */
1556 static tree
1557 maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset,
1558 tree orig_type, bool base_is_ptr)
1560 tree f, t, field_type, tail_array_field, field_offset;
1562 if (TREE_CODE (record_type) != RECORD_TYPE
1563 && TREE_CODE (record_type) != UNION_TYPE
1564 && TREE_CODE (record_type) != QUAL_UNION_TYPE)
1565 return NULL_TREE;
1567 /* Short-circuit silly cases. */
1568 if (lang_hooks.types_compatible_p (record_type, orig_type))
1569 return NULL_TREE;
1571 tail_array_field = NULL_TREE;
1572 for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f))
1574 int cmp;
1576 if (TREE_CODE (f) != FIELD_DECL)
1577 continue;
1578 if (DECL_BIT_FIELD (f))
1579 continue;
1581 field_offset = byte_position (f);
1582 if (TREE_CODE (field_offset) != INTEGER_CST)
1583 continue;
1585 /* ??? Java creates "interesting" fields for representing base classes.
1586 They have no name, and have no context. With no context, we get into
1587 trouble with nonoverlapping_component_refs_p. Skip them. */
1588 if (!DECL_FIELD_CONTEXT (f))
1589 continue;
1591 /* The previous array field isn't at the end. */
1592 tail_array_field = NULL_TREE;
1594 /* Check to see if this offset overlaps with the field. */
1595 cmp = tree_int_cst_compare (field_offset, offset);
1596 if (cmp > 0)
1597 continue;
1599 field_type = TREE_TYPE (f);
1601 /* Here we exactly match the offset being checked. If the types match,
1602 then we can return that field. */
1603 if (cmp == 0
1604 && lang_hooks.types_compatible_p (orig_type, field_type))
1606 if (base_is_ptr)
1607 base = build1 (INDIRECT_REF, record_type, base);
1608 t = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
1609 return t;
1612 /* Don't care about offsets into the middle of scalars. */
1613 if (!AGGREGATE_TYPE_P (field_type))
1614 continue;
1616 /* Check for array at the end of the struct. This is often
1617 used as for flexible array members. We should be able to
1618 turn this into an array access anyway. */
1619 if (TREE_CODE (field_type) == ARRAY_TYPE)
1620 tail_array_field = f;
1622 /* Check the end of the field against the offset. */
1623 if (!DECL_SIZE_UNIT (f)
1624 || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
1625 continue;
1626 t = int_const_binop (MINUS_EXPR, offset, field_offset, 1);
1627 if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
1628 continue;
1630 /* If we matched, then set offset to the displacement into
1631 this field. */
1632 offset = t;
1633 goto found;
1636 if (!tail_array_field)
1637 return NULL_TREE;
1639 f = tail_array_field;
1640 field_type = TREE_TYPE (f);
1641 offset = int_const_binop (MINUS_EXPR, offset, byte_position (f), 1);
1643 found:
1644 /* If we get here, we've got an aggregate field, and a possibly
1645 nonzero offset into them. Recurse and hope for a valid match. */
1646 if (base_is_ptr)
1647 base = build1 (INDIRECT_REF, record_type, base);
1648 base = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
1650 t = maybe_fold_offset_to_array_ref (base, offset, orig_type);
1651 if (t)
1652 return t;
1653 return maybe_fold_offset_to_component_ref (field_type, base, offset,
1654 orig_type, false);
1658 /* A subroutine of fold_stmt_r. Attempt to simplify *(BASE+OFFSET).
1659 Return the simplified expression, or NULL if nothing could be done. */
1661 static tree
1662 maybe_fold_stmt_indirect (tree expr, tree base, tree offset)
1664 tree t;
1666 /* We may well have constructed a double-nested PLUS_EXPR via multiple
1667 substitutions. Fold that down to one. Remove NON_LVALUE_EXPRs that
1668 are sometimes added. */
1669 base = fold (base);
1670 STRIP_TYPE_NOPS (base);
1671 TREE_OPERAND (expr, 0) = base;
1673 /* One possibility is that the address reduces to a string constant. */
1674 t = fold_read_from_constant_string (expr);
1675 if (t)
1676 return t;
1678 /* Add in any offset from a PLUS_EXPR. */
1679 if (TREE_CODE (base) == PLUS_EXPR)
1681 tree offset2;
1683 offset2 = TREE_OPERAND (base, 1);
1684 if (TREE_CODE (offset2) != INTEGER_CST)
1685 return NULL_TREE;
1686 base = TREE_OPERAND (base, 0);
1688 offset = int_const_binop (PLUS_EXPR, offset, offset2, 1);
1691 if (TREE_CODE (base) == ADDR_EXPR)
1693 /* Strip the ADDR_EXPR. */
1694 base = TREE_OPERAND (base, 0);
1696 /* Fold away CONST_DECL to its value, if the type is scalar. */
1697 if (TREE_CODE (base) == CONST_DECL
1698 && is_gimple_min_invariant (DECL_INITIAL (base)))
1699 return DECL_INITIAL (base);
1701 /* Try folding *(&B+O) to B[X]. */
1702 t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE (expr));
1703 if (t)
1704 return t;
1706 /* Try folding *(&B+O) to B.X. */
1707 t = maybe_fold_offset_to_component_ref (TREE_TYPE (base), base, offset,
1708 TREE_TYPE (expr), false);
1709 if (t)
1710 return t;
1712 /* Fold *&B to B. We can only do this if EXPR is the same type
1713 as BASE. We can't do this if EXPR is the element type of an array
1714 and BASE is the array. */
1715 if (integer_zerop (offset)
1716 && lang_hooks.types_compatible_p (TREE_TYPE (base),
1717 TREE_TYPE (expr)))
1718 return base;
1720 else
1722 /* We can get here for out-of-range string constant accesses,
1723 such as "_"[3]. Bail out of the entire substitution search
1724 and arrange for the entire statement to be replaced by a
1725 call to __builtin_trap. In all likelihood this will all be
1726 constant-folded away, but in the meantime we can't leave with
1727 something that get_expr_operands can't understand. */
1729 t = base;
1730 STRIP_NOPS (t);
1731 if (TREE_CODE (t) == ADDR_EXPR
1732 && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
1734 /* FIXME: Except that this causes problems elsewhere with dead
1735 code not being deleted, and we die in the rtl expanders
1736 because we failed to remove some ssa_name. In the meantime,
1737 just return zero. */
1738 /* FIXME2: This condition should be signaled by
1739 fold_read_from_constant_string directly, rather than
1740 re-checking for it here. */
1741 return integer_zero_node;
1744 /* Try folding *(B+O) to B->X. Still an improvement. */
1745 if (POINTER_TYPE_P (TREE_TYPE (base)))
1747 t = maybe_fold_offset_to_component_ref (TREE_TYPE (TREE_TYPE (base)),
1748 base, offset,
1749 TREE_TYPE (expr), true);
1750 if (t)
1751 return t;
1755 /* Otherwise we had an offset that we could not simplify. */
1756 return NULL_TREE;
1760 /* A subroutine of fold_stmt_r. EXPR is a PLUS_EXPR.
1762 A quaint feature extant in our address arithmetic is that there
1763 can be hidden type changes here. The type of the result need
1764 not be the same as the type of the input pointer.
1766 What we're after here is an expression of the form
1767 (T *)(&array + const)
1768 where the cast doesn't actually exist, but is implicit in the
1769 type of the PLUS_EXPR. We'd like to turn this into
1770 &array[x]
1771 which may be able to propagate further. */
1773 static tree
1774 maybe_fold_stmt_addition (tree expr)
1776 tree op0 = TREE_OPERAND (expr, 0);
1777 tree op1 = TREE_OPERAND (expr, 1);
1778 tree ptr_type = TREE_TYPE (expr);
1779 tree ptd_type;
1780 tree t;
1781 bool subtract = (TREE_CODE (expr) == MINUS_EXPR);
1783 /* We're only interested in pointer arithmetic. */
1784 if (!POINTER_TYPE_P (ptr_type))
1785 return NULL_TREE;
1786 /* Canonicalize the integral operand to op1. */
1787 if (INTEGRAL_TYPE_P (TREE_TYPE (op0)))
1789 if (subtract)
1790 return NULL_TREE;
1791 t = op0, op0 = op1, op1 = t;
1793 /* It had better be a constant. */
1794 if (TREE_CODE (op1) != INTEGER_CST)
1795 return NULL_TREE;
1796 /* The first operand should be an ADDR_EXPR. */
1797 if (TREE_CODE (op0) != ADDR_EXPR)
1798 return NULL_TREE;
1799 op0 = TREE_OPERAND (op0, 0);
1801 /* If the first operand is an ARRAY_REF, expand it so that we can fold
1802 the offset into it. */
1803 while (TREE_CODE (op0) == ARRAY_REF)
1805 tree array_obj = TREE_OPERAND (op0, 0);
1806 tree array_idx = TREE_OPERAND (op0, 1);
1807 tree elt_type = TREE_TYPE (op0);
1808 tree elt_size = TYPE_SIZE_UNIT (elt_type);
1809 tree min_idx;
1811 if (TREE_CODE (array_idx) != INTEGER_CST)
1812 break;
1813 if (TREE_CODE (elt_size) != INTEGER_CST)
1814 break;
1816 /* Un-bias the index by the min index of the array type. */
1817 min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj));
1818 if (min_idx)
1820 min_idx = TYPE_MIN_VALUE (min_idx);
1821 if (min_idx)
1823 if (TREE_CODE (min_idx) != INTEGER_CST)
1824 break;
1826 array_idx = convert (TREE_TYPE (min_idx), array_idx);
1827 if (!integer_zerop (min_idx))
1828 array_idx = int_const_binop (MINUS_EXPR, array_idx,
1829 min_idx, 0);
1833 /* Convert the index to a byte offset. */
1834 array_idx = convert (sizetype, array_idx);
1835 array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0);
1837 /* Update the operands for the next round, or for folding. */
1838 /* If we're manipulating unsigned types, then folding into negative
1839 values can produce incorrect results. Particularly if the type
1840 is smaller than the width of the pointer. */
1841 if (subtract
1842 && TYPE_UNSIGNED (TREE_TYPE (op1))
1843 && tree_int_cst_lt (array_idx, op1))
1844 return NULL;
1845 op1 = int_const_binop (subtract ? MINUS_EXPR : PLUS_EXPR,
1846 array_idx, op1, 0);
1847 subtract = false;
1848 op0 = array_obj;
1851 /* If we weren't able to fold the subtraction into another array reference,
1852 canonicalize the integer for passing to the array and component ref
1853 simplification functions. */
1854 if (subtract)
1856 if (TYPE_UNSIGNED (TREE_TYPE (op1)))
1857 return NULL;
1858 op1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (op1), op1));
1859 /* ??? In theory fold should always produce another integer. */
1860 if (TREE_CODE (op1) != INTEGER_CST)
1861 return NULL;
1864 ptd_type = TREE_TYPE (ptr_type);
1866 /* At which point we can try some of the same things as for indirects. */
1867 t = maybe_fold_offset_to_array_ref (op0, op1, ptd_type);
1868 if (!t)
1869 t = maybe_fold_offset_to_component_ref (TREE_TYPE (op0), op0, op1,
1870 ptd_type, false);
1871 if (t)
1872 t = build1 (ADDR_EXPR, ptr_type, t);
1874 return t;
1877 /* Subroutine of fold_stmt called via walk_tree. We perform several
1878 simplifications of EXPR_P, mostly having to do with pointer arithmetic. */
1880 static tree
1881 fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data)
1883 bool *changed_p = data;
1884 tree expr = *expr_p, t;
1886 /* ??? It'd be nice if walk_tree had a pre-order option. */
1887 switch (TREE_CODE (expr))
1889 case INDIRECT_REF:
1890 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1891 if (t)
1892 return t;
1893 *walk_subtrees = 0;
1895 t = maybe_fold_stmt_indirect (expr, TREE_OPERAND (expr, 0),
1896 integer_zero_node);
1897 break;
1899 /* ??? Could handle ARRAY_REF here, as a variant of INDIRECT_REF.
1900 We'd only want to bother decomposing an existing ARRAY_REF if
1901 the base array is found to have another offset contained within.
1902 Otherwise we'd be wasting time. */
1904 case ADDR_EXPR:
1905 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1906 if (t)
1907 return t;
1908 *walk_subtrees = 0;
1910 /* Set TREE_INVARIANT properly so that the value is properly
1911 considered constant, and so gets propagated as expected. */
1912 if (*changed_p)
1913 recompute_tree_invarant_for_addr_expr (expr);
1914 return NULL_TREE;
1916 case PLUS_EXPR:
1917 case MINUS_EXPR:
1918 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1919 if (t)
1920 return t;
1921 t = walk_tree (&TREE_OPERAND (expr, 1), fold_stmt_r, data, NULL);
1922 if (t)
1923 return t;
1924 *walk_subtrees = 0;
1926 t = maybe_fold_stmt_addition (expr);
1927 break;
1929 case COMPONENT_REF:
1930 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1931 if (t)
1932 return t;
1933 *walk_subtrees = 0;
1935 /* Make sure the FIELD_DECL is actually a field in the type on the lhs.
1936 We've already checked that the records are compatible, so we should
1937 come up with a set of compatible fields. */
1939 tree expr_record = TREE_TYPE (TREE_OPERAND (expr, 0));
1940 tree expr_field = TREE_OPERAND (expr, 1);
1942 if (DECL_FIELD_CONTEXT (expr_field) != TYPE_MAIN_VARIANT (expr_record))
1944 expr_field = find_compatible_field (expr_record, expr_field);
1945 TREE_OPERAND (expr, 1) = expr_field;
1948 break;
1950 case TARGET_MEM_REF:
1951 t = maybe_fold_tmr (expr);
1952 break;
1954 default:
1955 return NULL_TREE;
1958 if (t)
1960 *expr_p = t;
1961 *changed_p = true;
1964 return NULL_TREE;
1968 /* Return the string length of ARG in LENGTH. If ARG is an SSA name variable,
1969 follow its use-def chains. If LENGTH is not NULL and its value is not
1970 equal to the length we determine, or if we are unable to determine the
1971 length, return false. VISITED is a bitmap of visited variables. */
1973 static bool
1974 get_strlen (tree arg, tree *length, bitmap visited)
1976 tree var, def_stmt, val;
1978 if (TREE_CODE (arg) != SSA_NAME)
1980 val = c_strlen (arg, 1);
1981 if (!val)
1982 return false;
1984 if (*length && simple_cst_equal (val, *length) != 1)
1985 return false;
1987 *length = val;
1988 return true;
1991 /* If we were already here, break the infinite cycle. */
1992 if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
1993 return true;
1994 bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
1996 var = arg;
1997 def_stmt = SSA_NAME_DEF_STMT (var);
1999 switch (TREE_CODE (def_stmt))
2001 case MODIFY_EXPR:
2003 tree len, rhs;
2005 /* The RHS of the statement defining VAR must either have a
2006 constant length or come from another SSA_NAME with a constant
2007 length. */
2008 rhs = TREE_OPERAND (def_stmt, 1);
2009 STRIP_NOPS (rhs);
2010 if (TREE_CODE (rhs) == SSA_NAME)
2011 return get_strlen (rhs, length, visited);
2013 /* See if the RHS is a constant length. */
2014 len = c_strlen (rhs, 1);
2015 if (len)
2017 if (*length && simple_cst_equal (len, *length) != 1)
2018 return false;
2020 *length = len;
2021 return true;
2024 break;
2027 case PHI_NODE:
2029 /* All the arguments of the PHI node must have the same constant
2030 length. */
2031 int i;
2033 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
2035 tree arg = PHI_ARG_DEF (def_stmt, i);
2037 /* If this PHI has itself as an argument, we cannot
2038 determine the string length of this argument. However,
2039 if we can find a constant string length for the other
2040 PHI args then we can still be sure that this is a
2041 constant string length. So be optimistic and just
2042 continue with the next argument. */
2043 if (arg == PHI_RESULT (def_stmt))
2044 continue;
2046 if (!get_strlen (arg, length, visited))
2047 return false;
2050 return true;
2053 default:
2054 break;
2058 return false;
2062 /* Fold builtin call FN in statement STMT. If it cannot be folded into a
2063 constant, return NULL_TREE. Otherwise, return its constant value. */
2065 static tree
2066 ccp_fold_builtin (tree stmt, tree fn)
2068 tree result, strlen_val[2];
2069 tree callee, arglist, a;
2070 int strlen_arg, i;
2071 bitmap visited;
2072 bool ignore;
2074 ignore = TREE_CODE (stmt) != MODIFY_EXPR;
2076 /* First try the generic builtin folder. If that succeeds, return the
2077 result directly. */
2078 callee = get_callee_fndecl (fn);
2079 arglist = TREE_OPERAND (fn, 1);
2080 result = fold_builtin (callee, arglist, ignore);
2081 if (result)
2083 if (ignore)
2084 STRIP_NOPS (result);
2085 return result;
2088 /* Ignore MD builtins. */
2089 if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
2090 return NULL_TREE;
2092 /* If the builtin could not be folded, and it has no argument list,
2093 we're done. */
2094 if (!arglist)
2095 return NULL_TREE;
2097 /* Limit the work only for builtins we know how to simplify. */
2098 switch (DECL_FUNCTION_CODE (callee))
2100 case BUILT_IN_STRLEN:
2101 case BUILT_IN_FPUTS:
2102 case BUILT_IN_FPUTS_UNLOCKED:
2103 strlen_arg = 1;
2104 break;
2105 case BUILT_IN_STRCPY:
2106 case BUILT_IN_STRNCPY:
2107 strlen_arg = 2;
2108 break;
2109 default:
2110 return NULL_TREE;
2113 /* Try to use the dataflow information gathered by the CCP process. */
2114 visited = BITMAP_ALLOC (NULL);
2116 memset (strlen_val, 0, sizeof (strlen_val));
2117 for (i = 0, a = arglist;
2118 strlen_arg;
2119 i++, strlen_arg >>= 1, a = TREE_CHAIN (a))
2120 if (strlen_arg & 1)
2122 bitmap_clear (visited);
2123 if (!get_strlen (TREE_VALUE (a), &strlen_val[i], visited))
2124 strlen_val[i] = NULL_TREE;
2127 BITMAP_FREE (visited);
2129 result = NULL_TREE;
2130 switch (DECL_FUNCTION_CODE (callee))
2132 case BUILT_IN_STRLEN:
2133 if (strlen_val[0])
2135 tree new = fold_convert (TREE_TYPE (fn), strlen_val[0]);
2137 /* If the result is not a valid gimple value, or not a cast
2138 of a valid gimple value, then we can not use the result. */
2139 if (is_gimple_val (new)
2140 || (is_gimple_cast (new)
2141 && is_gimple_val (TREE_OPERAND (new, 0))))
2142 return new;
2144 break;
2146 case BUILT_IN_STRCPY:
2147 if (strlen_val[1] && is_gimple_val (strlen_val[1]))
2149 tree fndecl = get_callee_fndecl (fn);
2150 tree arglist = TREE_OPERAND (fn, 1);
2151 result = fold_builtin_strcpy (fndecl, arglist, strlen_val[1]);
2153 break;
2155 case BUILT_IN_STRNCPY:
2156 if (strlen_val[1] && is_gimple_val (strlen_val[1]))
2158 tree fndecl = get_callee_fndecl (fn);
2159 tree arglist = TREE_OPERAND (fn, 1);
2160 result = fold_builtin_strncpy (fndecl, arglist, strlen_val[1]);
2162 break;
2164 case BUILT_IN_FPUTS:
2165 result = fold_builtin_fputs (arglist,
2166 TREE_CODE (stmt) != MODIFY_EXPR, 0,
2167 strlen_val[0]);
2168 break;
2170 case BUILT_IN_FPUTS_UNLOCKED:
2171 result = fold_builtin_fputs (arglist,
2172 TREE_CODE (stmt) != MODIFY_EXPR, 1,
2173 strlen_val[0]);
2174 break;
2176 default:
2177 gcc_unreachable ();
2180 if (result && ignore)
2181 result = fold_ignored_result (result);
2182 return result;
2186 /* Fold the statement pointed by STMT_P. In some cases, this function may
2187 replace the whole statement with a new one. Returns true iff folding
2188 makes any changes. */
2190 bool
2191 fold_stmt (tree *stmt_p)
2193 tree rhs, result, stmt;
2194 bool changed = false;
2196 stmt = *stmt_p;
2198 /* If we replaced constants and the statement makes pointer dereferences,
2199 then we may need to fold instances of *&VAR into VAR, etc. */
2200 if (walk_tree (stmt_p, fold_stmt_r, &changed, NULL))
2202 *stmt_p
2203 = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP],
2204 NULL);
2205 return true;
2208 rhs = get_rhs (stmt);
2209 if (!rhs)
2210 return changed;
2211 result = NULL_TREE;
2213 if (TREE_CODE (rhs) == CALL_EXPR)
2215 tree callee;
2217 /* Check for builtins that CCP can handle using information not
2218 available in the generic fold routines. */
2219 callee = get_callee_fndecl (rhs);
2220 if (callee && DECL_BUILT_IN (callee))
2221 result = ccp_fold_builtin (stmt, rhs);
2222 else
2224 /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve
2225 here are when we've propagated the address of a decl into the
2226 object slot. */
2227 /* ??? Should perhaps do this in fold proper. However, doing it
2228 there requires that we create a new CALL_EXPR, and that requires
2229 copying EH region info to the new node. Easier to just do it
2230 here where we can just smash the call operand. */
2231 callee = TREE_OPERAND (rhs, 0);
2232 if (TREE_CODE (callee) == OBJ_TYPE_REF
2233 && lang_hooks.fold_obj_type_ref
2234 && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
2235 && DECL_P (TREE_OPERAND
2236 (OBJ_TYPE_REF_OBJECT (callee), 0)))
2238 tree t;
2240 /* ??? Caution: Broken ADDR_EXPR semantics means that
2241 looking at the type of the operand of the addr_expr
2242 can yield an array type. See silly exception in
2243 check_pointer_types_r. */
2245 t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
2246 t = lang_hooks.fold_obj_type_ref (callee, t);
2247 if (t)
2249 TREE_OPERAND (rhs, 0) = t;
2250 changed = true;
2256 /* If we couldn't fold the RHS, hand over to the generic fold routines. */
2257 if (result == NULL_TREE)
2258 result = fold (rhs);
2260 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
2261 may have been added by fold, and "useless" type conversions that might
2262 now be apparent due to propagation. */
2263 STRIP_USELESS_TYPE_CONVERSION (result);
2265 if (result != rhs)
2266 changed |= set_rhs (stmt_p, result);
2268 return changed;
2271 /* Perform the minimal folding on statement STMT. Only operations like
2272 *&x created by constant propagation are handled. The statement cannot
2273 be replaced with a new one. */
2275 bool
2276 fold_stmt_inplace (tree stmt)
2278 tree old_stmt = stmt, rhs, new_rhs;
2279 bool changed = false;
2281 walk_tree (&stmt, fold_stmt_r, &changed, NULL);
2282 gcc_assert (stmt == old_stmt);
2284 rhs = get_rhs (stmt);
2285 if (!rhs || rhs == stmt)
2286 return changed;
2288 new_rhs = fold (rhs);
2289 if (new_rhs == rhs)
2290 return changed;
2292 changed |= set_rhs (&stmt, new_rhs);
2293 gcc_assert (stmt == old_stmt);
2295 return changed;
2298 /* Convert EXPR into a GIMPLE value suitable for substitution on the
2299 RHS of an assignment. Insert the necessary statements before
2300 iterator *SI_P. */
2302 static tree
2303 convert_to_gimple_builtin (block_stmt_iterator *si_p, tree expr)
2305 tree_stmt_iterator ti;
2306 tree stmt = bsi_stmt (*si_p);
2307 tree tmp, stmts = NULL;
2309 push_gimplify_context ();
2310 tmp = get_initialized_tmp_var (expr, &stmts, NULL);
2311 pop_gimplify_context (NULL);
2313 if (EXPR_HAS_LOCATION (stmt))
2314 annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt));
2316 /* The replacement can expose previously unreferenced variables. */
2317 for (ti = tsi_start (stmts); !tsi_end_p (ti); tsi_next (&ti))
2319 tree new_stmt = tsi_stmt (ti);
2320 find_new_referenced_vars (tsi_stmt_ptr (ti));
2321 bsi_insert_before (si_p, new_stmt, BSI_NEW_STMT);
2322 mark_new_vars_to_rename (bsi_stmt (*si_p));
2323 bsi_next (si_p);
2326 return tmp;
2330 /* A simple pass that attempts to fold all builtin functions. This pass
2331 is run after we've propagated as many constants as we can. */
2333 static void
2334 execute_fold_all_builtins (void)
2336 bool cfg_changed = false;
2337 basic_block bb;
2338 FOR_EACH_BB (bb)
2340 block_stmt_iterator i;
2341 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
2343 tree *stmtp = bsi_stmt_ptr (i);
2344 tree old_stmt = *stmtp;
2345 tree call = get_rhs (*stmtp);
2346 tree callee, result;
2348 if (!call || TREE_CODE (call) != CALL_EXPR)
2349 continue;
2350 callee = get_callee_fndecl (call);
2351 if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
2352 continue;
2354 result = ccp_fold_builtin (*stmtp, call);
2355 if (!result)
2356 switch (DECL_FUNCTION_CODE (callee))
2358 case BUILT_IN_CONSTANT_P:
2359 /* Resolve __builtin_constant_p. If it hasn't been
2360 folded to integer_one_node by now, it's fairly
2361 certain that the value simply isn't constant. */
2362 result = integer_zero_node;
2363 break;
2365 default:
2366 continue;
2369 if (dump_file && (dump_flags & TDF_DETAILS))
2371 fprintf (dump_file, "Simplified\n ");
2372 print_generic_stmt (dump_file, *stmtp, dump_flags);
2375 if (!set_rhs (stmtp, result))
2377 result = convert_to_gimple_builtin (&i, result);
2378 if (result)
2380 bool ok = set_rhs (stmtp, result);
2382 gcc_assert (ok);
2385 update_stmt (*stmtp);
2386 if (maybe_clean_or_replace_eh_stmt (old_stmt, *stmtp)
2387 && tree_purge_dead_eh_edges (bb))
2388 cfg_changed = true;
2390 if (dump_file && (dump_flags & TDF_DETAILS))
2392 fprintf (dump_file, "to\n ");
2393 print_generic_stmt (dump_file, *stmtp, dump_flags);
2394 fprintf (dump_file, "\n");
2399 /* Delete unreachable blocks. */
2400 if (cfg_changed)
2401 cleanup_tree_cfg ();
2405 struct tree_opt_pass pass_fold_builtins =
2407 "fab", /* name */
2408 NULL, /* gate */
2409 execute_fold_all_builtins, /* execute */
2410 NULL, /* sub */
2411 NULL, /* next */
2412 0, /* static_pass_number */
2413 0, /* tv_id */
2414 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2415 0, /* properties_provided */
2416 0, /* properties_destroyed */
2417 0, /* todo_flags_start */
2418 TODO_dump_func
2419 | TODO_verify_ssa
2420 | TODO_update_ssa, /* todo_flags_finish */
2421 0 /* letter */