1 /* Conditional constant propagation pass for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
4 Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 2, or (at your option) any
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 /* Conditional constant propagation.
27 Constant propagation with conditional branches,
28 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
30 Building an Optimizing Compiler,
31 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
33 Advanced Compiler Design and Implementation,
34 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
38 #include "coretypes.h"
43 #include "langhooks.h"
45 /* These RTL headers are needed for basic-block.h. */
48 #include "hard-reg-set.h"
49 #include "basic-block.h"
51 #include "diagnostic.h"
52 #include "tree-inline.h"
53 #include "tree-flow.h"
54 #include "tree-gimple.h"
55 #include "tree-dump.h"
56 #include "tree-pass.h"
62 /* Possible lattice values. */
71 /* Use the TREE_VISITED bitflag to mark statements and PHI nodes that have
72 been deemed VARYING and shouldn't be simulated again. */
73 #define DONT_SIMULATE_AGAIN(T) TREE_VISITED (T)
75 /* Main structure for CCP. Contains the lattice value and, if it's a
76 constant, the constant value. */
79 latticevalue lattice_val;
83 /* A bitmap to keep track of executable blocks in the CFG. */
84 static sbitmap executable_blocks;
86 /* Array of control flow edges on the worklist. */
87 static GTY(()) varray_type cfg_blocks = NULL;
89 static unsigned int cfg_blocks_num = 0;
90 static int cfg_blocks_tail;
91 static int cfg_blocks_head;
93 static sbitmap bb_in_list;
95 /* This is used to track the current value of each variable. */
96 static value *value_vector;
98 /* Worklist of SSA edges which will need reexamination as their definition
99 has changed. SSA edges are def-use edges in the SSA web. For each
100 edge, we store the definition statement or PHI node D. The destination
101 nodes that need to be visited are accessed using immediate_uses
103 static GTY(()) varray_type ssa_edges;
105 /* Identical to SSA_EDGES. For performance reasons, the list of SSA
106 edges is split into two. One contains all SSA edges who need to be
107 reexamined because their lattice value changed to varying (this
108 worklist), and the other contains all other SSA edges to be
109 reexamined (ssa_edges).
111 Since most values in the program are varying, the ideal situation
112 is to move them to that lattice value as quickly as possible.
113 Thus, it doesn't make sense to process any other type of lattice
114 value until all varying values are propagated fully, which is one
115 thing using the varying worklist achieves. In addition, if you
116 don't use a separate worklist for varying edges, you end up with
117 situations where lattice values move from
118 undefined->constant->varying instead of undefined->varying.
120 static GTY(()) varray_type varying_ssa_edges;
123 static void initialize (void);
124 static void finalize (void);
125 static void visit_phi_node (tree);
126 static tree ccp_fold (tree);
127 static value cp_lattice_meet (value, value);
128 static void visit_stmt (tree);
129 static void visit_cond_stmt (tree);
130 static void visit_assignment (tree);
131 static void add_var_to_ssa_edges_worklist (tree, value);
132 static void add_outgoing_control_edges (basic_block);
133 static void add_control_edge (edge);
134 static void def_to_varying (tree);
135 static void set_lattice_value (tree, value);
136 static void simulate_block (basic_block);
137 static void simulate_stmt (tree);
138 static void substitute_and_fold (void);
139 static value evaluate_stmt (tree);
140 static void dump_lattice_value (FILE *, const char *, value);
141 static bool replace_uses_in (tree, bool *);
142 static latticevalue likely_value (tree);
143 static tree get_rhs (tree);
144 static bool set_rhs (tree *, tree);
145 static value *get_value (tree);
146 static value get_default_value (tree);
147 static tree ccp_fold_builtin (tree, tree);
148 static bool get_strlen (tree, tree *, bitmap);
149 static inline bool cfg_blocks_empty_p (void);
150 static void cfg_blocks_add (basic_block);
151 static basic_block cfg_blocks_get (void);
152 static bool need_imm_uses_for (tree var);
154 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
155 drain. This pops statements off the given WORKLIST and processes
156 them until there are no more statements on WORKLIST. */
159 process_ssa_edge_worklist (varray_type *worklist)
161 /* Drain the entire worklist. */
162 while (VARRAY_ACTIVE_SIZE (*worklist) > 0)
164 /* Pull the statement to simulate off the worklist. */
165 tree stmt = VARRAY_TOP_TREE (*worklist);
166 stmt_ann_t ann = stmt_ann (stmt);
167 VARRAY_POP (*worklist);
169 /* visit_stmt can "cancel" reevaluation of some statements.
170 If it does, then in_ccp_worklist will be zero. */
171 if (ann->in_ccp_worklist)
173 ann->in_ccp_worklist = 0;
174 simulate_stmt (stmt);
179 /* Main entry point for SSA Conditional Constant Propagation. FNDECL is
180 the declaration for the function to optimize.
182 On exit, VARS_TO_RENAME will contain the symbols that have been exposed by
183 the propagation of ADDR_EXPR expressions into pointer dereferences and need
184 to be renamed into SSA.
186 PHASE indicates which dump file from the DUMP_FILES array to use when
187 dumping debugging information. */
194 /* Iterate until the worklists are empty. */
195 while (!cfg_blocks_empty_p ()
196 || VARRAY_ACTIVE_SIZE (ssa_edges) > 0
197 || VARRAY_ACTIVE_SIZE (varying_ssa_edges) > 0)
199 if (!cfg_blocks_empty_p ())
201 /* Pull the next block to simulate off the worklist. */
202 basic_block dest_block = cfg_blocks_get ();
203 simulate_block (dest_block);
206 /* In order to move things to varying as quickly as
207 possible,process the VARYING_SSA_EDGES worklist first. */
208 process_ssa_edge_worklist (&varying_ssa_edges);
210 /* Now process the SSA_EDGES worklist. */
211 process_ssa_edge_worklist (&ssa_edges);
214 /* Now perform substitutions based on the known constant values. */
215 substitute_and_fold ();
217 /* Now cleanup any unreachable code. */
220 /* Free allocated memory. */
223 /* Debugging dumps. */
224 if (dump_file && (dump_flags & TDF_DETAILS))
226 dump_referenced_vars (dump_file);
227 fprintf (dump_file, "\n\n");
234 return flag_tree_ccp != 0;
237 struct tree_opt_pass pass_ccp =
241 tree_ssa_ccp, /* execute */
244 0, /* static_pass_number */
245 TV_TREE_CCP, /* tv_id */
246 PROP_cfg | PROP_ssa, /* properties_required */
247 0, /* properties_provided */
248 0, /* properties_destroyed */
249 0, /* todo_flags_start */
250 TODO_dump_func | TODO_rename_vars
251 | TODO_ggc_collect | TODO_verify_ssa
252 | TODO_verify_stmts /* todo_flags_finish */
256 /* Get the constant value associated with variable VAR. */
263 #if defined ENABLE_CHECKING
264 if (TREE_CODE (var) != SSA_NAME)
268 val = &value_vector[SSA_NAME_VERSION (var)];
269 if (val->lattice_val == UNINITIALIZED)
270 *val = get_default_value (var);
276 /* Simulate the execution of BLOCK. Evaluate the statement associated
277 with each variable reference inside the block. */
280 simulate_block (basic_block block)
284 /* There is nothing to do for the exit block. */
285 if (block == EXIT_BLOCK_PTR)
288 if (dump_file && (dump_flags & TDF_DETAILS))
289 fprintf (dump_file, "\nSimulating block %d\n", block->index);
291 /* Always simulate PHI nodes, even if we have simulated this block
293 for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
294 visit_phi_node (phi);
296 /* If this is the first time we've simulated this block, then we
297 must simulate each of its statements. */
298 if (!TEST_BIT (executable_blocks, block->index))
300 block_stmt_iterator j;
301 unsigned int normal_edge_count;
304 /* Note that we have simulated this block. */
305 SET_BIT (executable_blocks, block->index);
307 for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
308 visit_stmt (bsi_stmt (j));
310 /* We can not predict when abnormal edges will be executed, so
311 once a block is considered executable, we consider any
312 outgoing abnormal edges as executable.
314 At the same time, if this block has only one successor that is
315 reached by non-abnormal edges, then add that successor to the
317 normal_edge_count = 0;
319 for (e = block->succ; e; e = e->succ_next)
321 if (e->flags & EDGE_ABNORMAL)
323 add_control_edge (e);
332 if (normal_edge_count == 1)
333 add_control_edge (normal_edge);
338 /* Follow the def-use edges for statement DEF_STMT and simulate all the
339 statements reached by it. */
342 simulate_stmt (tree use_stmt)
344 basic_block use_bb = bb_for_stmt (use_stmt);
346 if (dump_file && (dump_flags & TDF_DETAILS))
348 fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
349 print_generic_stmt (dump_file, use_stmt, dump_flags);
352 if (TREE_CODE (use_stmt) == PHI_NODE)
354 /* PHI nodes are always visited, regardless of whether or not the
355 destination block is executable. */
356 visit_phi_node (use_stmt);
358 else if (TEST_BIT (executable_blocks, use_bb->index))
360 /* Otherwise, visit the statement containing the use reached by
361 DEF, only if the destination block is marked executable. */
362 visit_stmt (use_stmt);
367 /* Perform final substitution and folding. After this pass the program
368 should still be in SSA form. */
371 substitute_and_fold (void)
375 if (dump_file && (dump_flags & TDF_DETAILS))
377 "\nSubstituing constants and folding statements\n\n");
379 /* Substitute constants in every statement of every basic block. */
382 block_stmt_iterator i;
385 /* Propagate our known constants into PHI nodes. */
386 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
390 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
393 use_operand_p orig_p = PHI_ARG_DEF_PTR (phi, i);
394 tree orig = USE_FROM_PTR (orig_p);
396 if (! SSA_VAR_P (orig))
399 new_val = get_value (orig);
400 if (new_val->lattice_val == CONSTANT
401 && may_propagate_copy (orig, new_val->const_val))
402 SET_USE (orig_p, new_val->const_val);
406 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
408 bool replaced_address;
409 tree stmt = bsi_stmt (i);
411 /* Skip statements that have been folded already. */
412 if (stmt_modified_p (stmt) || !is_exec_stmt (stmt))
415 /* Replace the statement with its folded version and mark it
417 if (dump_file && (dump_flags & TDF_DETAILS))
419 fprintf (dump_file, "Line %d: replaced ", get_lineno (stmt));
420 print_generic_stmt (dump_file, stmt, TDF_SLIM);
423 if (replace_uses_in (stmt, &replaced_address))
425 bool changed = fold_stmt (bsi_stmt_ptr (i));
428 /* If we folded a builtin function, we'll likely
429 need to rename VDEFs. */
430 if (replaced_address || changed)
432 mark_new_vars_to_rename (stmt, vars_to_rename);
433 if (maybe_clean_eh_stmt (stmt))
434 tree_purge_dead_eh_edges (bb);
438 if (dump_file && (dump_flags & TDF_DETAILS))
440 fprintf (dump_file, " with ");
441 print_generic_stmt (dump_file, stmt, TDF_SLIM);
442 fprintf (dump_file, "\n");
449 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
450 lattice values to determine PHI_NODE's lattice value. The value of a
451 PHI node is determined calling cp_lattice_meet() with all the arguments
452 of the PHI node that are incoming via executable edges. */
455 visit_phi_node (tree phi)
457 bool short_circuit = 0;
458 value phi_val, *curr_val;
461 /* If the PHI node has already been deemed to be VARYING, don't simulate
463 if (DONT_SIMULATE_AGAIN (phi))
466 if (dump_file && (dump_flags & TDF_DETAILS))
468 fprintf (dump_file, "\nVisiting PHI node: ");
469 print_generic_expr (dump_file, phi, dump_flags);
472 curr_val = get_value (PHI_RESULT (phi));
473 switch (curr_val->lattice_val)
476 if (dump_file && (dump_flags & TDF_DETAILS))
477 fprintf (dump_file, "\n Shortcircuit. Default of VARYING.");
487 phi_val.lattice_val = UNDEFINED;
488 phi_val.const_val = NULL_TREE;
495 /* If the variable is volatile or the variable is never referenced in a
496 real operand, then consider the PHI node VARYING. */
497 if (short_circuit || TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi))))
499 phi_val.lattice_val = VARYING;
500 phi_val.const_val = NULL;
503 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
505 /* Compute the meet operator over all the PHI arguments. */
506 edge e = PHI_ARG_EDGE (phi, i);
508 if (dump_file && (dump_flags & TDF_DETAILS))
511 "\n Argument #%d (%d -> %d %sexecutable)\n",
512 i, e->src->index, e->dest->index,
513 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
516 /* If the incoming edge is executable, Compute the meet operator for
517 the existing value of the PHI node and the current PHI argument. */
518 if (e->flags & EDGE_EXECUTABLE)
520 tree rdef = PHI_ARG_DEF (phi, i);
521 value *rdef_val, val;
523 if (is_gimple_min_invariant (rdef))
525 val.lattice_val = CONSTANT;
526 val.const_val = rdef;
530 rdef_val = get_value (rdef);
532 phi_val = cp_lattice_meet (phi_val, *rdef_val);
534 if (dump_file && (dump_flags & TDF_DETAILS))
536 fprintf (dump_file, "\t");
537 print_generic_expr (dump_file, rdef, dump_flags);
538 dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
539 fprintf (dump_file, "\n");
542 if (phi_val.lattice_val == VARYING)
547 if (dump_file && (dump_flags & TDF_DETAILS))
549 dump_lattice_value (dump_file, "\n PHI node value: ", phi_val);
550 fprintf (dump_file, "\n\n");
553 set_lattice_value (PHI_RESULT (phi), phi_val);
554 if (phi_val.lattice_val == VARYING)
555 DONT_SIMULATE_AGAIN (phi) = 1;
559 /* Compute the meet operator between VAL1 and VAL2:
561 any M UNDEFINED = any
562 any M VARYING = VARYING
563 Ci M Cj = Ci if (i == j)
564 Ci M Cj = VARYING if (i != j) */
566 cp_lattice_meet (value val1, value val2)
570 /* any M UNDEFINED = any. */
571 if (val1.lattice_val == UNDEFINED)
573 else if (val2.lattice_val == UNDEFINED)
576 /* any M VARYING = VARYING. */
577 if (val1.lattice_val == VARYING || val2.lattice_val == VARYING)
579 result.lattice_val = VARYING;
580 result.const_val = NULL_TREE;
584 /* Ci M Cj = Ci if (i == j)
585 Ci M Cj = VARYING if (i != j) */
586 if (simple_cst_equal (val1.const_val, val2.const_val) == 1)
588 result.lattice_val = CONSTANT;
589 result.const_val = val1.const_val;
593 result.lattice_val = VARYING;
594 result.const_val = NULL_TREE;
601 /* Evaluate statement STMT. If the statement produces an output value and
602 its evaluation changes the lattice value of its output, do the following:
604 - If the statement is an assignment, add all the SSA edges starting at
607 - If the statement is a conditional branch:
608 . If the statement evaluates to non-constant, add all edges to
610 . If the statement is constant, add the edge executed as the
611 result of the branch. */
614 visit_stmt (tree stmt)
619 v_may_def_optype v_may_defs;
620 v_must_def_optype v_must_defs;
622 /* If the statement has already been deemed to be VARYING, don't simulate
624 if (DONT_SIMULATE_AGAIN (stmt))
627 if (dump_file && (dump_flags & TDF_DETAILS))
629 fprintf (dump_file, "\nVisiting statement: ");
630 print_generic_stmt (dump_file, stmt, TDF_SLIM);
631 fprintf (dump_file, "\n");
634 ann = stmt_ann (stmt);
636 /* If this statement is already in the worklist then "cancel" it. The
637 reevaluation implied by the worklist entry will produce the same
638 value we generate here and thus reevaluating it again from the
639 worklist is pointless. */
640 if (ann->in_ccp_worklist)
641 ann->in_ccp_worklist = 0;
643 /* Now examine the statement. If the statement is an assignment that
644 produces a single output value, evaluate its RHS to see if the lattice
645 value of its output has changed. */
646 if (TREE_CODE (stmt) == MODIFY_EXPR
647 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
648 visit_assignment (stmt);
650 /* Definitions made by statements other than assignments to SSA_NAMEs
651 represent unknown modifications to their outputs. Mark them VARYING. */
652 else if (NUM_DEFS (defs = DEF_OPS (ann)) != 0)
654 DONT_SIMULATE_AGAIN (stmt) = 1;
655 for (i = 0; i < NUM_DEFS (defs); i++)
657 tree def = DEF_OP (defs, i);
658 def_to_varying (def);
662 /* If STMT is a conditional branch, see if we can determine which branch
664 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
665 visit_cond_stmt (stmt);
667 /* Any other kind of statement is not interesting for constant
668 propagation and, therefore, not worth simulating. */
671 DONT_SIMULATE_AGAIN (stmt) = 1;
673 /* If STMT is a computed goto, then mark all the output edges
675 if (computed_goto_p (stmt))
676 add_outgoing_control_edges (bb_for_stmt (stmt));
679 /* Mark all V_MAY_DEF operands VARYING. */
680 v_may_defs = V_MAY_DEF_OPS (ann);
681 for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
682 def_to_varying (V_MAY_DEF_RESULT (v_may_defs, i));
684 /* Mark all V_MUST_DEF operands VARYING. */
685 v_must_defs = V_MUST_DEF_OPS (ann);
686 for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
687 def_to_varying (V_MUST_DEF_OP (v_must_defs, i));
691 /* Visit the assignment statement STMT. Set the value of its LHS to the
692 value computed by the RHS. */
695 visit_assignment (tree stmt)
700 lhs = TREE_OPERAND (stmt, 0);
701 rhs = TREE_OPERAND (stmt, 1);
703 if (TREE_THIS_VOLATILE (SSA_NAME_VAR (lhs)))
705 /* Volatile variables are always VARYING. */
706 val.lattice_val = VARYING;
707 val.const_val = NULL_TREE;
709 else if (TREE_CODE (rhs) == SSA_NAME)
711 /* For a simple copy operation, we copy the lattice values. */
712 value *nval = get_value (rhs);
717 /* Evaluate the statement. */
718 val = evaluate_stmt (stmt);
721 /* FIXME: Hack. If this was a definition of a bitfield, we need to widen
722 the constant value into the type of the destination variable. This
723 should not be necessary if GCC represented bitfields properly. */
725 tree lhs = TREE_OPERAND (stmt, 0);
726 if (val.lattice_val == CONSTANT
727 && TREE_CODE (lhs) == COMPONENT_REF
728 && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
730 tree w = widen_bitfield (val.const_val, TREE_OPERAND (lhs, 1), lhs);
732 if (w && is_gimple_min_invariant (w))
736 val.lattice_val = VARYING;
737 val.const_val = NULL;
742 /* Set the lattice value of the statement's output. */
743 set_lattice_value (lhs, val);
744 if (val.lattice_val == VARYING)
745 DONT_SIMULATE_AGAIN (stmt) = 1;
749 /* Visit the conditional statement STMT. If it evaluates to a constant value,
750 mark outgoing edges appropriately. */
753 visit_cond_stmt (tree stmt)
759 block = bb_for_stmt (stmt);
760 val = evaluate_stmt (stmt);
762 /* Find which edge out of the conditional block will be taken and add it
763 to the worklist. If no single edge can be determined statically, add
764 all outgoing edges from BLOCK. */
765 e = find_taken_edge (block, val.const_val);
767 add_control_edge (e);
770 DONT_SIMULATE_AGAIN (stmt) = 1;
771 add_outgoing_control_edges (block);
776 /* Add all the edges coming out of BB to the control flow worklist. */
779 add_outgoing_control_edges (basic_block bb)
783 for (e = bb->succ; e; e = e->succ_next)
784 add_control_edge (e);
788 /* Add edge E to the control flow worklist. */
791 add_control_edge (edge e)
793 basic_block bb = e->dest;
794 if (bb == EXIT_BLOCK_PTR)
797 /* If the edge had already been executed, skip it. */
798 if (e->flags & EDGE_EXECUTABLE)
801 e->flags |= EDGE_EXECUTABLE;
803 /* If the block is already in the list, we're done. */
804 if (TEST_BIT (bb_in_list, bb->index))
809 if (dump_file && (dump_flags & TDF_DETAILS))
810 fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
811 e->src->index, e->dest->index);
815 /* CCP specific front-end to the non-destructive constant folding routines.
817 Attempt to simplify the RHS of STMT knowing that one or more
818 operands are constants.
820 If simplification is possible, return the simplified RHS,
821 otherwise return the original RHS. */
826 tree rhs = get_rhs (stmt);
827 enum tree_code code = TREE_CODE (rhs);
828 int kind = TREE_CODE_CLASS (code);
829 tree retval = NULL_TREE;
831 /* If the RHS is just a variable, then that variable must now have
832 a constant value that we can return directly. */
833 if (TREE_CODE (rhs) == SSA_NAME)
834 return get_value (rhs)->const_val;
836 /* Unary operators. Note that we know the single operand must
837 be a constant. So this should almost always return a
841 /* Handle unary operators which can appear in GIMPLE form. */
842 tree op0 = TREE_OPERAND (rhs, 0);
844 /* Simplify the operand down to a constant. */
845 if (TREE_CODE (op0) == SSA_NAME)
847 value *val = get_value (op0);
848 if (val->lattice_val == CONSTANT)
849 op0 = get_value (op0)->const_val;
852 retval = nondestructive_fold_unary_to_constant (code,
856 /* If we folded, but did not create an invariant, then we can not
857 use this expression. */
858 if (retval && ! is_gimple_min_invariant (retval))
861 /* If we could not fold the expression, but the arguments are all
862 constants and gimple values, then build and return the new
865 In some cases the new expression is still something we can
866 use as a replacement for an argument. This happens with
867 NOP conversions of types for example.
869 In other cases the new expression can not be used as a
870 replacement for an argument (as it would create non-gimple
871 code). But the new expression can still be used to derive
873 if (! retval && is_gimple_min_invariant (op0))
874 return build1 (code, TREE_TYPE (rhs), op0);
877 /* Binary and comparison operators. We know one or both of the
878 operands are constants. */
881 || code == TRUTH_AND_EXPR
882 || code == TRUTH_OR_EXPR
883 || code == TRUTH_XOR_EXPR)
885 /* Handle binary and comparison operators that can appear in
887 tree op0 = TREE_OPERAND (rhs, 0);
888 tree op1 = TREE_OPERAND (rhs, 1);
890 /* Simplify the operands down to constants when appropriate. */
891 if (TREE_CODE (op0) == SSA_NAME)
893 value *val = get_value (op0);
894 if (val->lattice_val == CONSTANT)
895 op0 = val->const_val;
898 if (TREE_CODE (op1) == SSA_NAME)
900 value *val = get_value (op1);
901 if (val->lattice_val == CONSTANT)
902 op1 = val->const_val;
905 retval = nondestructive_fold_binary_to_constant (code,
909 /* If we folded, but did not create an invariant, then we can not
910 use this expression. */
911 if (retval && ! is_gimple_min_invariant (retval))
914 /* If we could not fold the expression, but the arguments are all
915 constants and gimple values, then build and return the new
918 In some cases the new expression is still something we can
919 use as a replacement for an argument. This happens with
920 NOP conversions of types for example.
922 In other cases the new expression can not be used as a
923 replacement for an argument (as it would create non-gimple
924 code). But the new expression can still be used to derive
927 && is_gimple_min_invariant (op0)
928 && is_gimple_min_invariant (op1))
929 return build (code, TREE_TYPE (rhs), op0, op1);
932 /* We may be able to fold away calls to builtin functions if their
933 arguments are constants. */
934 else if (code == CALL_EXPR
935 && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
936 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
938 && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
940 use_optype uses = STMT_USE_OPS (stmt);
941 if (NUM_USES (uses) != 0)
946 /* Preserve the original values of every operand. */
947 orig = xmalloc (sizeof (tree) * NUM_USES (uses));
948 for (i = 0; i < NUM_USES (uses); i++)
949 orig[i] = USE_OP (uses, i);
951 /* Substitute operands with their values and try to fold. */
952 replace_uses_in (stmt, NULL);
953 retval = fold_builtin (rhs, false);
955 /* Restore operands to their original form. */
956 for (i = 0; i < NUM_USES (uses); i++)
957 SET_USE_OP (uses, i, orig[i]);
964 /* If we got a simplified form, see if we need to convert its type. */
966 return fold_convert (TREE_TYPE (rhs), retval);
968 /* No simplification was possible. */
973 /* Evaluate statement STMT. */
976 evaluate_stmt (tree stmt)
980 latticevalue likelyvalue = likely_value (stmt);
982 /* If the statement is likely to have a CONSTANT result, then try
983 to fold the statement to determine the constant value. */
984 if (likelyvalue == CONSTANT)
985 simplified = ccp_fold (stmt);
986 /* If the statement is likely to have a VARYING result, then do not
987 bother folding the statement. */
988 else if (likelyvalue == VARYING)
989 simplified = get_rhs (stmt);
990 /* Otherwise the statement is likely to have an UNDEFINED value and
991 there will be nothing to do. */
993 simplified = NULL_TREE;
995 if (simplified && is_gimple_min_invariant (simplified))
997 /* The statement produced a constant value. */
998 val.lattice_val = CONSTANT;
999 val.const_val = simplified;
1003 /* The statement produced a nonconstant value. If the statement
1004 had undefined operands, then the result of the statement should
1005 be undefined. Else the result of the statement is VARYING. */
1006 val.lattice_val = (likelyvalue == UNDEFINED ? UNDEFINED : VARYING);
1007 val.const_val = NULL_TREE;
1014 /* Debugging dumps. */
1017 dump_lattice_value (FILE *outf, const char *prefix, value val)
1019 switch (val.lattice_val)
1022 fprintf (outf, "%sUNDEFINED", prefix);
1025 fprintf (outf, "%sVARYING", prefix);
1028 fprintf (outf, "%sCONSTANT ", prefix);
1029 print_generic_expr (outf, val.const_val, dump_flags);
1036 /* Given a constant value VAL for bitfield FIELD, and a destination
1037 variable VAR, return VAL appropriately widened to fit into VAR. If
1038 FIELD is wider than HOST_WIDE_INT, NULL is returned. */
1041 widen_bitfield (tree val, tree field, tree var)
1043 unsigned HOST_WIDE_INT var_size, field_size;
1045 unsigned HOST_WIDE_INT mask;
1048 /* We can only do this if the size of the type and field and VAL are
1049 all constants representable in HOST_WIDE_INT. */
1050 if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1)
1051 || !host_integerp (DECL_SIZE (field), 1)
1052 || !host_integerp (val, 0))
1055 var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1);
1056 field_size = tree_low_cst (DECL_SIZE (field), 1);
1058 /* Give up if either the bitfield or the variable are too wide. */
1059 if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT)
1062 #if defined ENABLE_CHECKING
1063 if (var_size < field_size)
1067 /* If the sign bit of the value is not set or the field's type is unsigned,
1068 just mask off the high order bits of the value. */
1069 if (DECL_UNSIGNED (field)
1070 || !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1))))
1072 /* Zero extension. Build a mask with the lower 'field_size' bits
1073 set and a BIT_AND_EXPR node to clear the high order bits of
1075 for (i = 0, mask = 0; i < field_size; i++)
1076 mask |= ((HOST_WIDE_INT) 1) << i;
1078 wide_val = build (BIT_AND_EXPR, TREE_TYPE (var), val,
1079 fold_convert (TREE_TYPE (var), build_int_2 (mask, 0)));
1083 /* Sign extension. Create a mask with the upper 'field_size'
1084 bits set and a BIT_IOR_EXPR to set the high order bits of the
1086 for (i = 0, mask = 0; i < (var_size - field_size); i++)
1087 mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1);
1089 wide_val = build (BIT_IOR_EXPR, TREE_TYPE (var), val,
1090 fold_convert (TREE_TYPE (var), build_int_2 (mask, 0)));
1093 return fold (wide_val);
1097 /* Function indicating whether we ought to include information for 'var'
1098 when calculating immediate uses. */
1101 need_imm_uses_for (tree var)
1103 return get_value (var)->lattice_val != VARYING;
1107 /* Initialize local data structures and worklists for CCP. */
1114 sbitmap virtual_var;
1116 /* Worklists of SSA edges. */
1117 VARRAY_TREE_INIT (ssa_edges, 20, "ssa_edges");
1118 VARRAY_TREE_INIT (varying_ssa_edges, 20, "varying_ssa_edges");
1120 executable_blocks = sbitmap_alloc (last_basic_block);
1121 sbitmap_zero (executable_blocks);
1123 bb_in_list = sbitmap_alloc (last_basic_block);
1124 sbitmap_zero (bb_in_list);
1126 value_vector = (value *) xmalloc (num_ssa_names * sizeof (value));
1127 memset (value_vector, 0, num_ssa_names * sizeof (value));
1129 /* 1 if ssa variable is used in a virtual variable context. */
1130 virtual_var = sbitmap_alloc (num_ssa_names);
1131 sbitmap_zero (virtual_var);
1133 /* Initialize default values and simulation flags for PHI nodes, statements
1137 block_stmt_iterator i;
1141 v_may_def_optype v_may_defs;
1142 v_must_def_optype v_must_defs;
1146 /* Get the default value for each definition. */
1147 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
1150 stmt = bsi_stmt (i);
1151 get_stmt_operands (stmt);
1152 ann = stmt_ann (stmt);
1153 defs = DEF_OPS (ann);
1154 for (x = 0; x < NUM_DEFS (defs); x++)
1156 tree def = DEF_OP (defs, x);
1157 if (get_value (def)->lattice_val == VARYING)
1160 DONT_SIMULATE_AGAIN (stmt) = vary;
1162 /* Mark all V_MAY_DEF operands VARYING. */
1163 v_may_defs = V_MAY_DEF_OPS (ann);
1164 for (x = 0; x < NUM_V_MAY_DEFS (v_may_defs); x++)
1166 tree res = V_MAY_DEF_RESULT (v_may_defs, x);
1167 get_value (res)->lattice_val = VARYING;
1168 SET_BIT (virtual_var, SSA_NAME_VERSION (res));
1171 /* Mark all V_MUST_DEF operands VARYING. */
1172 v_must_defs = V_MUST_DEF_OPS (ann);
1173 for (x = 0; x < NUM_V_MUST_DEFS (v_must_defs); x++)
1175 tree v_must_def = V_MUST_DEF_OP (v_must_defs, x);
1176 get_value (v_must_def)->lattice_val = VARYING;
1177 SET_BIT (virtual_var, SSA_NAME_VERSION (v_must_def));
1181 for (e = bb->succ; e; e = e->succ_next)
1182 e->flags &= ~EDGE_EXECUTABLE;
1185 /* Now process PHI nodes. */
1190 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1193 val = get_value (PHI_RESULT (phi));
1194 if (val->lattice_val != VARYING)
1196 for (x = 0; x < PHI_NUM_ARGS (phi); x++)
1198 var = PHI_ARG_DEF (phi, x);
1199 /* If one argument is virtual, the result is virtual, and
1200 therefore varying. */
1201 if (TREE_CODE (var) == SSA_NAME)
1203 if (TEST_BIT (virtual_var, SSA_NAME_VERSION (var)))
1205 val->lattice_val = VARYING;
1206 SET_BIT (virtual_var,
1207 SSA_NAME_VERSION (PHI_RESULT (phi)));
1213 DONT_SIMULATE_AGAIN (phi) = ((val->lattice_val == VARYING) ? 1 : 0);
1217 sbitmap_free (virtual_var);
1218 /* Compute immediate uses for variables we care about. */
1219 compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
1221 if (dump_file && (dump_flags & TDF_DETAILS))
1222 dump_immediate_uses (dump_file);
1224 VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
1226 /* Seed the algorithm by adding the successors of the entry block to the
1228 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
1230 if (e->dest != EXIT_BLOCK_PTR)
1232 e->flags |= EDGE_EXECUTABLE;
1233 cfg_blocks_add (e->dest);
1239 /* Free allocated storage. */
1245 varying_ssa_edges = NULL;
1247 free (value_vector);
1248 sbitmap_free (bb_in_list);
1249 sbitmap_free (executable_blocks);
1253 /* Is the block worklist empty. */
1256 cfg_blocks_empty_p (void)
1258 return (cfg_blocks_num == 0);
1261 /* Add a basic block to the worklist. */
1264 cfg_blocks_add (basic_block bb)
1266 if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
1269 if (TEST_BIT (bb_in_list, bb->index))
1272 if (cfg_blocks_empty_p ())
1274 cfg_blocks_tail = cfg_blocks_head = 0;
1280 if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks))
1282 /* We have to grow the array now. Adjust to queue to occupy the
1283 full space of the original array. */
1284 cfg_blocks_tail = VARRAY_SIZE (cfg_blocks);
1285 cfg_blocks_head = 0;
1286 VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks));
1289 cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks);
1291 VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb;
1292 SET_BIT (bb_in_list, bb->index);
1295 /* Remove a block from the worklist. */
1298 cfg_blocks_get (void)
1302 bb = VARRAY_BB (cfg_blocks, cfg_blocks_head);
1304 #ifdef ENABLE_CHECKING
1305 if (cfg_blocks_empty_p () || !bb)
1309 cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks);
1311 RESET_BIT (bb_in_list, bb->index);
1316 /* We have just defined a new value for VAR. Add all immediate uses
1317 of VAR to the ssa_edges or varying_ssa_edges worklist. */
1319 add_var_to_ssa_edges_worklist (tree var, value val)
1321 tree stmt = SSA_NAME_DEF_STMT (var);
1322 dataflow_t df = get_immediate_uses (stmt);
1323 int num_uses = num_immediate_uses (df);
1326 for (i = 0; i < num_uses; i++)
1328 tree use = immediate_use (df, i);
1330 if (!DONT_SIMULATE_AGAIN (use))
1332 stmt_ann_t ann = stmt_ann (use);
1333 if (ann->in_ccp_worklist == 0)
1335 ann->in_ccp_worklist = 1;
1336 if (val.lattice_val == VARYING)
1337 VARRAY_PUSH_TREE (varying_ssa_edges, use);
1339 VARRAY_PUSH_TREE (ssa_edges, use);
1345 /* Set the lattice value for the variable VAR to VARYING. */
1348 def_to_varying (tree var)
1351 val.lattice_val = VARYING;
1352 val.const_val = NULL_TREE;
1353 set_lattice_value (var, val);
1356 /* Set the lattice value for variable VAR to VAL. */
1359 set_lattice_value (tree var, value val)
1361 value *old = get_value (var);
1363 #ifdef ENABLE_CHECKING
1364 if (val.lattice_val == UNDEFINED)
1366 /* CONSTANT->UNDEFINED is never a valid state transition. */
1367 if (old->lattice_val == CONSTANT)
1370 /* VARYING->UNDEFINED is generally not a valid state transition,
1371 except for values which are initialized to VARYING. */
1372 if (old->lattice_val == VARYING
1373 && get_default_value (var).lattice_val != VARYING)
1376 else if (val.lattice_val == CONSTANT)
1378 /* VARYING -> CONSTANT is an invalid state transition, except
1379 for objects which start off in a VARYING state. */
1380 if (old->lattice_val == VARYING
1381 && get_default_value (var).lattice_val != VARYING)
1386 /* If the constant for VAR has changed, then this VAR is really varying. */
1387 if (old->lattice_val == CONSTANT && val.lattice_val == CONSTANT
1388 && !simple_cst_equal (old->const_val, val.const_val))
1390 val.lattice_val = VARYING;
1391 val.const_val = NULL_TREE;
1394 if (old->lattice_val != val.lattice_val)
1396 if (dump_file && (dump_flags & TDF_DETAILS))
1398 dump_lattice_value (dump_file,
1399 "Lattice value changed to ", val);
1400 fprintf (dump_file, ". Adding definition to SSA edges.\n");
1403 add_var_to_ssa_edges_worklist (var, val);
1408 /* Replace USE references in statement STMT with their immediate reaching
1409 definition. Return true if at least one reference was replaced. If
1410 REPLACED_ADDRESSES_P is given, it will be set to true if an address
1411 constant was replaced. */
1414 replace_uses_in (tree stmt, bool *replaced_addresses_p)
1416 bool replaced = false;
1420 if (replaced_addresses_p)
1421 *replaced_addresses_p = false;
1423 get_stmt_operands (stmt);
1425 uses = STMT_USE_OPS (stmt);
1426 for (i = 0; i < NUM_USES (uses); i++)
1428 use_operand_p use = USE_OP_PTR (uses, i);
1429 value *val = get_value (USE_FROM_PTR (use));
1431 if (val->lattice_val == CONSTANT)
1433 SET_USE (use, val->const_val);
1435 if (POINTER_TYPE_P (TREE_TYPE (USE_FROM_PTR (use)))
1436 && replaced_addresses_p)
1437 *replaced_addresses_p = true;
1444 /* Return the likely latticevalue for STMT.
1446 If STMT has no operands, then return CONSTANT.
1448 Else if any operands of STMT are undefined, then return UNDEFINED.
1450 Else if any operands of STMT are constants, then return CONSTANT.
1452 Else return VARYING. */
1455 likely_value (tree stmt)
1459 int found_constant = 0;
1462 /* If the statement makes aliased loads or has volatile operands, it
1463 won't fold to a constant value. */
1464 ann = stmt_ann (stmt);
1465 if (ann->makes_aliased_loads || ann->has_volatile_ops)
1468 /* A CALL_EXPR is assumed to be varying. This may be overly conservative,
1469 in the presence of const and pure calls. */
1470 if (get_call_expr_in (stmt) != NULL_TREE)
1473 get_stmt_operands (stmt);
1475 uses = USE_OPS (ann);
1476 for (i = 0; i < NUM_USES (uses); i++)
1478 tree use = USE_OP (uses, i);
1479 value *val = get_value (use);
1481 if (val->lattice_val == UNDEFINED)
1484 if (val->lattice_val == CONSTANT)
1488 return ((found_constant || !uses) ? CONSTANT : VARYING);
1491 /* A subroutine of fold_stmt_r. Attempts to fold *(A+O) to A[X].
1492 BASE is an array type. OFFSET is a byte displacement. ORIG_TYPE
1493 is the desired result type. */
1496 maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type)
1498 tree min_idx, idx, elt_offset = integer_zero_node;
1499 tree array_type, elt_type, elt_size;
1501 /* If BASE is an ARRAY_REF, we can pick up another offset (this time
1502 measured in units of the size of elements type) from that ARRAY_REF).
1503 We can't do anything if either is variable.
1505 The case we handle here is *(&A[N]+O). */
1506 if (TREE_CODE (base) == ARRAY_REF)
1508 tree low_bound = array_ref_low_bound (base);
1510 elt_offset = TREE_OPERAND (base, 1);
1511 if (TREE_CODE (low_bound) != INTEGER_CST
1512 || TREE_CODE (elt_offset) != INTEGER_CST)
1515 elt_offset = int_const_binop (MINUS_EXPR, elt_offset, low_bound, 0);
1516 base = TREE_OPERAND (base, 0);
1519 /* Ignore stupid user tricks of indexing non-array variables. */
1520 array_type = TREE_TYPE (base);
1521 if (TREE_CODE (array_type) != ARRAY_TYPE)
1523 elt_type = TREE_TYPE (array_type);
1524 if (!lang_hooks.types_compatible_p (orig_type, elt_type))
1527 /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the
1528 element type (so we can use the alignment if it's not constant).
1529 Otherwise, compute the offset as an index by using a division. If the
1530 division isn't exact, then don't do anything. */
1531 elt_size = TYPE_SIZE_UNIT (elt_type);
1532 if (integer_zerop (offset))
1534 if (TREE_CODE (elt_size) != INTEGER_CST)
1535 elt_size = size_int (TYPE_ALIGN (elt_type));
1537 idx = integer_zero_node;
1541 unsigned HOST_WIDE_INT lquo, lrem;
1542 HOST_WIDE_INT hquo, hrem;
1544 if (TREE_CODE (elt_size) != INTEGER_CST
1545 || div_and_round_double (TRUNC_DIV_EXPR, 1,
1546 TREE_INT_CST_LOW (offset),
1547 TREE_INT_CST_HIGH (offset),
1548 TREE_INT_CST_LOW (elt_size),
1549 TREE_INT_CST_HIGH (elt_size),
1550 &lquo, &hquo, &lrem, &hrem)
1554 idx = build_int_2_wide (lquo, hquo);
1557 /* Assume the low bound is zero. If there is a domain type, get the
1558 low bound, if any, convert the index into that type, and add the
1560 min_idx = integer_zero_node;
1561 if (TYPE_DOMAIN (array_type))
1563 if (TYPE_MIN_VALUE (TYPE_DOMAIN (array_type)))
1564 min_idx = TYPE_MIN_VALUE (TYPE_DOMAIN (array_type));
1566 min_idx = fold_convert (TYPE_DOMAIN (array_type), min_idx);
1568 if (TREE_CODE (min_idx) != INTEGER_CST)
1571 idx = fold_convert (TYPE_DOMAIN (array_type), idx);
1572 elt_offset = fold_convert (TYPE_DOMAIN (array_type), elt_offset);
1575 if (!integer_zerop (min_idx))
1576 idx = int_const_binop (PLUS_EXPR, idx, min_idx, 0);
1577 if (!integer_zerop (elt_offset))
1578 idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0);
1580 return build (ARRAY_REF, orig_type, base, idx, min_idx,
1581 size_int (tree_low_cst (elt_size, 1)
1582 / (TYPE_ALIGN (elt_type) / BITS_PER_UNIT)));
1585 /* A subroutine of fold_stmt_r. Attempts to fold *(S+O) to S.X.
1586 BASE is a record type. OFFSET is a byte displacement. ORIG_TYPE
1587 is the desired result type. */
1588 /* ??? This doesn't handle class inheritance. */
1591 maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset,
1592 tree orig_type, bool base_is_ptr)
1594 tree f, t, field_type, tail_array_field;
1596 if (TREE_CODE (record_type) != RECORD_TYPE
1597 && TREE_CODE (record_type) != UNION_TYPE
1598 && TREE_CODE (record_type) != QUAL_UNION_TYPE)
1601 /* Short-circuit silly cases. */
1602 if (lang_hooks.types_compatible_p (record_type, orig_type))
1605 tail_array_field = NULL_TREE;
1606 for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f))
1610 if (TREE_CODE (f) != FIELD_DECL)
1612 if (DECL_BIT_FIELD (f))
1614 if (TREE_CODE (DECL_FIELD_OFFSET (f)) != INTEGER_CST)
1617 /* ??? Java creates "interesting" fields for representing base classes.
1618 They have no name, and have no context. With no context, we get into
1619 trouble with nonoverlapping_component_refs_p. Skip them. */
1620 if (!DECL_FIELD_CONTEXT (f))
1623 /* The previous array field isn't at the end. */
1624 tail_array_field = NULL_TREE;
1626 /* Check to see if this offset overlaps with the field. */
1627 cmp = tree_int_cst_compare (DECL_FIELD_OFFSET (f), offset);
1631 field_type = TREE_TYPE (f);
1634 /* Don't care about offsets into the middle of scalars. */
1635 if (!AGGREGATE_TYPE_P (field_type))
1638 /* Check for array at the end of the struct. This is often
1639 used as for flexible array members. We should be able to
1640 turn this into an array access anyway. */
1641 if (TREE_CODE (field_type) == ARRAY_TYPE)
1642 tail_array_field = f;
1644 /* Check the end of the field against the offset. */
1645 if (!DECL_SIZE_UNIT (f)
1646 || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
1648 t = int_const_binop (MINUS_EXPR, offset, DECL_FIELD_OFFSET (f), 1);
1649 if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
1652 /* If we matched, then set offset to the displacement into
1657 /* Here we exactly match the offset being checked. If the types match,
1658 then we can return that field. */
1659 else if (lang_hooks.types_compatible_p (orig_type, field_type))
1662 base = build1 (INDIRECT_REF, record_type, base);
1663 t = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
1667 /* Don't care about type-punning of scalars. */
1668 else if (!AGGREGATE_TYPE_P (field_type))
1674 if (!tail_array_field)
1677 f = tail_array_field;
1678 field_type = TREE_TYPE (f);
1681 /* If we get here, we've got an aggregate field, and a possibly
1682 nonzero offset into them. Recurse and hope for a valid match. */
1684 base = build1 (INDIRECT_REF, record_type, base);
1685 base = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
1687 t = maybe_fold_offset_to_array_ref (base, offset, orig_type);
1690 return maybe_fold_offset_to_component_ref (field_type, base, offset,
1694 /* A subroutine of fold_stmt_r. Attempt to simplify *(BASE+OFFSET).
1695 Return the simplified expression, or NULL if nothing could be done. */
1698 maybe_fold_stmt_indirect (tree expr, tree base, tree offset)
1702 /* We may well have constructed a double-nested PLUS_EXPR via multiple
1703 substitutions. Fold that down to one. Remove NON_LVALUE_EXPRs that
1704 are sometimes added. */
1707 TREE_OPERAND (expr, 0) = base;
1709 /* One possibility is that the address reduces to a string constant. */
1710 t = fold_read_from_constant_string (expr);
1714 /* Add in any offset from a PLUS_EXPR. */
1715 if (TREE_CODE (base) == PLUS_EXPR)
1719 offset2 = TREE_OPERAND (base, 1);
1720 if (TREE_CODE (offset2) != INTEGER_CST)
1722 base = TREE_OPERAND (base, 0);
1724 offset = int_const_binop (PLUS_EXPR, offset, offset2, 1);
1727 if (TREE_CODE (base) == ADDR_EXPR)
1729 /* Strip the ADDR_EXPR. */
1730 base = TREE_OPERAND (base, 0);
1732 /* Try folding *(&B+O) to B[X]. */
1733 t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE (expr));
1737 /* Try folding *(&B+O) to B.X. */
1738 t = maybe_fold_offset_to_component_ref (TREE_TYPE (base), base, offset,
1739 TREE_TYPE (expr), false);
1743 /* Fold *&B to B. We can only do this if EXPR is the same type
1744 as BASE. We can't do this if EXPR is the element type of an array
1745 and BASE is the array. */
1746 if (integer_zerop (offset)
1747 && lang_hooks.types_compatible_p (TREE_TYPE (base),
1753 /* We can get here for out-of-range string constant accesses,
1754 such as "_"[3]. Bail out of the entire substitution search
1755 and arrange for the entire statement to be replaced by a
1756 call to __builtin_trap. In all likelyhood this will all be
1757 constant-folded away, but in the meantime we can't leave with
1758 something that get_expr_operands can't understand. */
1762 if (TREE_CODE (t) == ADDR_EXPR
1763 && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
1765 /* FIXME: Except that this causes problems elsewhere with dead
1766 code not being deleted, and we abort in the rtl expanders
1767 because we failed to remove some ssa_name. In the meantime,
1768 just return zero. */
1769 /* FIXME2: This condition should be signaled by
1770 fold_read_from_constant_string directly, rather than
1771 re-checking for it here. */
1772 return integer_zero_node;
1775 /* Try folding *(B+O) to B->X. Still an improvement. */
1776 if (POINTER_TYPE_P (TREE_TYPE (base)))
1778 t = maybe_fold_offset_to_component_ref (TREE_TYPE (TREE_TYPE (base)),
1780 TREE_TYPE (expr), true);
1786 /* Otherwise we had an offset that we could not simplify. */
1790 /* A subroutine of fold_stmt_r. EXPR is a PLUS_EXPR.
1792 A quaint feature extant in our address arithmetic is that there
1793 can be hidden type changes here. The type of the result need
1794 not be the same as the type of the input pointer.
1796 What we're after here is an expression of the form
1797 (T *)(&array + const)
1798 where the cast doesn't actually exist, but is implicit in the
1799 type of the PLUS_EXPR. We'd like to turn this into
1801 which may be able to propagate further. */
1804 maybe_fold_stmt_addition (tree expr)
1806 tree op0 = TREE_OPERAND (expr, 0);
1807 tree op1 = TREE_OPERAND (expr, 1);
1808 tree ptr_type = TREE_TYPE (expr);
1811 bool subtract = (TREE_CODE (expr) == MINUS_EXPR);
1813 /* We're only interested in pointer arithmetic. */
1814 if (!POINTER_TYPE_P (ptr_type))
1816 /* Canonicalize the integral operand to op1. */
1817 if (INTEGRAL_TYPE_P (TREE_TYPE (op0)))
1821 t = op0, op0 = op1, op1 = t;
1823 /* It had better be a constant. */
1824 if (TREE_CODE (op1) != INTEGER_CST)
1826 /* The first operand should be an ADDR_EXPR. */
1827 if (TREE_CODE (op0) != ADDR_EXPR)
1829 op0 = TREE_OPERAND (op0, 0);
1831 /* If the first operand is an ARRAY_REF, expand it so that we can fold
1832 the offset into it. */
1833 while (TREE_CODE (op0) == ARRAY_REF)
1835 tree array_obj = TREE_OPERAND (op0, 0);
1836 tree array_idx = TREE_OPERAND (op0, 1);
1837 tree elt_type = TREE_TYPE (op0);
1838 tree elt_size = TYPE_SIZE_UNIT (elt_type);
1841 if (TREE_CODE (array_idx) != INTEGER_CST)
1843 if (TREE_CODE (elt_size) != INTEGER_CST)
1846 /* Un-bias the index by the min index of the array type. */
1847 min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj));
1850 min_idx = TYPE_MIN_VALUE (min_idx);
1853 if (TREE_CODE (min_idx) != INTEGER_CST)
1856 array_idx = convert (TREE_TYPE (min_idx), array_idx);
1857 if (!integer_zerop (min_idx))
1858 array_idx = int_const_binop (MINUS_EXPR, array_idx,
1863 /* Convert the index to a byte offset. */
1864 array_idx = convert (sizetype, array_idx);
1865 array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0);
1867 /* Update the operands for the next round, or for folding. */
1868 /* If we're manipulating unsigned types, then folding into negative
1869 values can produce incorrect results. Particularly if the type
1870 is smaller than the width of the pointer. */
1872 && TYPE_UNSIGNED (TREE_TYPE (op1))
1873 && tree_int_cst_lt (array_idx, op1))
1875 op1 = int_const_binop (subtract ? MINUS_EXPR : PLUS_EXPR,
1881 /* If we weren't able to fold the subtraction into another array reference,
1882 canonicalize the integer for passing to the array and component ref
1883 simplification functions. */
1886 if (TYPE_UNSIGNED (TREE_TYPE (op1)))
1888 op1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (op1), op1));
1889 /* ??? In theory fold should always produce another integer. */
1890 if (TREE_CODE (op1) != INTEGER_CST)
1894 ptd_type = TREE_TYPE (ptr_type);
1896 /* At which point we can try some of the same things as for indirects. */
1897 t = maybe_fold_offset_to_array_ref (op0, op1, ptd_type);
1899 t = maybe_fold_offset_to_component_ref (TREE_TYPE (op0), op0, op1,
1902 t = build1 (ADDR_EXPR, ptr_type, t);
1907 /* Subroutine of fold_stmt called via walk_tree. We perform several
1908 simplifications of EXPR_P, mostly having to do with pointer arithmetic. */
1911 fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data)
1913 bool *changed_p = data;
1914 tree expr = *expr_p, t;
1916 /* ??? It'd be nice if walk_tree had a pre-order option. */
1917 switch (TREE_CODE (expr))
1920 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1925 t = maybe_fold_stmt_indirect (expr, TREE_OPERAND (expr, 0),
1929 /* ??? Could handle ARRAY_REF here, as a variant of INDIRECT_REF.
1930 We'd only want to bother decomposing an existing ARRAY_REF if
1931 the base array is found to have another offset contained within.
1932 Otherwise we'd be wasting time. */
1935 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1940 /* Set TREE_INVARIANT properly so that the value is properly
1941 considered constant, and so gets propagated as expected. */
1943 recompute_tree_invarant_for_addr_expr (expr);
1948 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1951 t = walk_tree (&TREE_OPERAND (expr, 1), fold_stmt_r, data, NULL);
1956 t = maybe_fold_stmt_addition (expr);
1960 t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1965 /* Make sure the FIELD_DECL is actually a field in the type on the lhs.
1966 We've already checked that the records are compatible, so we should
1967 come up with a set of compatible fields. */
1969 tree expr_record = TREE_TYPE (TREE_OPERAND (expr, 0));
1970 tree expr_field = TREE_OPERAND (expr, 1);
1972 if (DECL_FIELD_CONTEXT (expr_field) != TYPE_MAIN_VARIANT (expr_record))
1974 expr_field = find_compatible_field (expr_record, expr_field);
1975 TREE_OPERAND (expr, 1) = expr_field;
1993 /* Fold the statement pointed by STMT_P. In some cases, this function may
1994 replace the whole statement with a new one. Returns true iff folding
1995 makes any changes. */
1998 fold_stmt (tree *stmt_p)
2000 tree rhs, result, stmt;
2001 bool changed = false;
2005 /* If we replaced constants and the statement makes pointer dereferences,
2006 then we may need to fold instances of *&VAR into VAR, etc. */
2007 if (walk_tree (stmt_p, fold_stmt_r, &changed, NULL))
2010 = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP],
2015 rhs = get_rhs (stmt);
2020 if (TREE_CODE (rhs) == CALL_EXPR)
2024 /* Check for builtins that CCP can handle using information not
2025 available in the generic fold routines. */
2026 callee = get_callee_fndecl (rhs);
2027 if (callee && DECL_BUILT_IN (callee))
2028 result = ccp_fold_builtin (stmt, rhs);
2031 /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve
2032 here are when we've propagated the address of a decl into the
2034 /* ??? Should perhaps do this in fold proper. However, doing it
2035 there requires that we create a new CALL_EXPR, and that requires
2036 copying EH region info to the new node. Easier to just do it
2037 here where we can just smash the call operand. */
2038 callee = TREE_OPERAND (rhs, 0);
2039 if (TREE_CODE (callee) == OBJ_TYPE_REF
2040 && lang_hooks.fold_obj_type_ref
2041 && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
2042 && DECL_P (TREE_OPERAND (OBJ_TYPE_REF_OBJECT (callee), 0)))
2046 /* ??? Caution: Broken ADDR_EXPR semantics means that
2047 looking at the type of the operand of the addr_expr
2048 can yield an array type. See silly exception in
2049 check_pointer_types_r. */
2051 t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
2052 t = lang_hooks.fold_obj_type_ref (callee, t);
2055 TREE_OPERAND (rhs, 0) = t;
2062 /* If we couldn't fold the RHS, hand over to the generic fold routines. */
2063 if (result == NULL_TREE)
2064 result = fold (rhs);
2066 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
2067 may have been added by fold, and "useless" type conversions that might
2068 now be apparent due to propagation. */
2069 STRIP_USELESS_TYPE_CONVERSION (result);
2072 changed |= set_rhs (stmt_p, result);
2077 /* Get the main expression from statement STMT. */
2082 enum tree_code code = TREE_CODE (stmt);
2087 stmt = TREE_OPERAND (stmt, 0);
2089 return get_rhs (stmt);
2094 return TREE_OPERAND (stmt, 1);
2097 return COND_EXPR_COND (stmt);
2099 return SWITCH_COND (stmt);
2101 return GOTO_DESTINATION (stmt);
2103 return LABEL_EXPR_LABEL (stmt);
2111 /* Set the main expression of *STMT_P to EXPR. */
2114 set_rhs (tree *stmt_p, tree expr)
2116 tree stmt = *stmt_p, op;
2117 enum tree_code code = TREE_CODE (expr);
2120 /* Verify the constant folded result is valid gimple. */
2121 if (TREE_CODE_CLASS (code) == '2')
2123 if (!is_gimple_val (TREE_OPERAND (expr, 0))
2124 || !is_gimple_val (TREE_OPERAND (expr, 1)))
2127 else if (TREE_CODE_CLASS (code) == '1')
2129 if (!is_gimple_val (TREE_OPERAND (expr, 0)))
2133 switch (TREE_CODE (stmt))
2136 op = TREE_OPERAND (stmt, 0);
2137 if (TREE_CODE (op) != MODIFY_EXPR)
2139 TREE_OPERAND (stmt, 0) = expr;
2146 TREE_OPERAND (stmt, 1) = expr;
2150 COND_EXPR_COND (stmt) = expr;
2153 SWITCH_COND (stmt) = expr;
2156 GOTO_DESTINATION (stmt) = expr;
2159 LABEL_EXPR_LABEL (stmt) = expr;
2163 /* Replace the whole statement with EXPR. If EXPR has no side
2164 effects, then replace *STMT_P with an empty statement. */
2165 ann = stmt_ann (stmt);
2166 *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
2167 (*stmt_p)->common.ann = (tree_ann_t) ann;
2169 if (TREE_SIDE_EFFECTS (expr))
2172 v_may_def_optype v_may_defs;
2173 v_must_def_optype v_must_defs;
2176 /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
2178 defs = DEF_OPS (ann);
2179 for (i = 0; i < NUM_DEFS (defs); i++)
2181 tree var = DEF_OP (defs, i);
2182 if (TREE_CODE (var) == SSA_NAME)
2183 SSA_NAME_DEF_STMT (var) = *stmt_p;
2186 v_may_defs = V_MAY_DEF_OPS (ann);
2187 for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
2189 tree var = V_MAY_DEF_RESULT (v_may_defs, i);
2190 if (TREE_CODE (var) == SSA_NAME)
2191 SSA_NAME_DEF_STMT (var) = *stmt_p;
2194 v_must_defs = V_MUST_DEF_OPS (ann);
2195 for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
2197 tree var = V_MUST_DEF_OP (v_must_defs, i);
2198 if (TREE_CODE (var) == SSA_NAME)
2199 SSA_NAME_DEF_STMT (var) = *stmt_p;
2209 /* Return a default value for variable VAR using the following rules:
2211 1- Global and static variables are considered VARYING, unless they are
2214 2- Function arguments are considered VARYING.
2216 3- Any other value is considered UNDEFINED. This is useful when
2217 considering PHI nodes. PHI arguments that are undefined do not
2218 change the constant value of the PHI node, which allows for more
2219 constants to be propagated. */
2222 get_default_value (tree var)
2227 if (TREE_CODE (var) == SSA_NAME)
2228 sym = SSA_NAME_VAR (var);
2231 #ifdef ENABLE_CHECKING
2238 val.lattice_val = UNDEFINED;
2239 val.const_val = NULL_TREE;
2241 if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym))
2243 /* Function arguments and volatile variables are considered VARYING. */
2244 val.lattice_val = VARYING;
2246 else if (decl_function_context (sym) != current_function_decl
2247 || TREE_STATIC (sym))
2249 /* Globals and static variables are considered VARYING, unless they
2250 are declared 'const'. */
2251 val.lattice_val = VARYING;
2253 if (TREE_READONLY (sym)
2254 && DECL_INITIAL (sym)
2255 && is_gimple_min_invariant (DECL_INITIAL (sym)))
2257 val.lattice_val = CONSTANT;
2258 val.const_val = DECL_INITIAL (sym);
2263 enum tree_code code;
2264 tree stmt = SSA_NAME_DEF_STMT (var);
2266 if (!IS_EMPTY_STMT (stmt))
2268 code = TREE_CODE (stmt);
2269 if (code != MODIFY_EXPR && code != PHI_NODE)
2270 val.lattice_val = VARYING;
2278 /* Fold builtin call FN in statement STMT. If it cannot be folded into a
2279 constant, return NULL_TREE. Otherwise, return its constant value. */
2282 ccp_fold_builtin (tree stmt, tree fn)
2284 tree result, strlen_val[2];
2285 tree callee, arglist, a;
2290 ignore = TREE_CODE (stmt) != MODIFY_EXPR;
2292 /* First try the generic builtin folder. If that succeeds, return the
2294 result = fold_builtin (fn, ignore);
2298 STRIP_NOPS (result);
2302 /* Ignore MD builtins. */
2303 callee = get_callee_fndecl (fn);
2304 if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
2307 /* If the builtin could not be folded, and it has no argument list,
2309 arglist = TREE_OPERAND (fn, 1);
2313 /* Limit the work only for builtins we know how to simplify. */
2314 switch (DECL_FUNCTION_CODE (callee))
2316 case BUILT_IN_STRLEN:
2317 case BUILT_IN_FPUTS:
2318 case BUILT_IN_FPUTS_UNLOCKED:
2321 case BUILT_IN_STRCPY:
2322 case BUILT_IN_STRNCPY:
2329 /* Try to use the dataflow information gathered by the CCP process. */
2330 visited = BITMAP_XMALLOC ();
2332 memset (strlen_val, 0, sizeof (strlen_val));
2333 for (i = 0, a = arglist;
2335 i++, strlen_arg >>= 1, a = TREE_CHAIN (a))
2338 bitmap_clear (visited);
2339 if (!get_strlen (TREE_VALUE (a), &strlen_val[i], visited))
2340 strlen_val[i] = NULL_TREE;
2343 BITMAP_XFREE (visited);
2346 switch (DECL_FUNCTION_CODE (callee))
2348 case BUILT_IN_STRLEN:
2351 tree new = fold_convert (TREE_TYPE (fn), strlen_val[0]);
2353 /* If the result is not a valid gimple value, or not a cast
2354 of a valid gimple value, then we can not use the result. */
2355 if (is_gimple_val (new)
2356 || (is_gimple_cast (new)
2357 && is_gimple_val (TREE_OPERAND (new, 0))))
2362 case BUILT_IN_STRCPY:
2363 if (strlen_val[1] && is_gimple_val (strlen_val[1]))
2364 result = fold_builtin_strcpy (fn, strlen_val[1]);
2367 case BUILT_IN_STRNCPY:
2368 if (strlen_val[1] && is_gimple_val (strlen_val[1]))
2369 result = fold_builtin_strncpy (fn, strlen_val[1]);
2372 case BUILT_IN_FPUTS:
2373 result = fold_builtin_fputs (arglist,
2374 TREE_CODE (stmt) != MODIFY_EXPR, 0,
2378 case BUILT_IN_FPUTS_UNLOCKED:
2379 result = fold_builtin_fputs (arglist,
2380 TREE_CODE (stmt) != MODIFY_EXPR, 1,
2388 if (result && ignore)
2390 /* STRIP_NOPS isn't strong enough -- it'll stop when we change modes,
2391 but given that we're ignoring the result, we don't care what type
2392 is being returned by the transformed function. */
2393 while (TREE_CODE (result) == NOP_EXPR
2394 || TREE_CODE (result) == CONVERT_EXPR
2395 || TREE_CODE (result) == NON_LVALUE_EXPR)
2396 result = TREE_OPERAND (result, 0);
2403 /* Return the string length of ARG in LENGTH. If ARG is an SSA name variable,
2404 follow its use-def chains. If LENGTH is not NULL and its value is not
2405 equal to the length we determine, or if we are unable to determine the
2406 length, return false. VISITED is a bitmap of visited variables. */
2409 get_strlen (tree arg, tree *length, bitmap visited)
2411 tree var, def_stmt, val;
2413 if (TREE_CODE (arg) != SSA_NAME)
2415 val = c_strlen (arg, 1);
2419 if (*length && simple_cst_equal (val, *length) != 1)
2426 /* If we were already here, break the infinite cycle. */
2427 if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
2429 bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
2432 def_stmt = SSA_NAME_DEF_STMT (var);
2434 switch (TREE_CODE (def_stmt))
2440 /* The RHS of the statement defining VAR must either have a
2441 constant length or come from another SSA_NAME with a constant
2443 rhs = TREE_OPERAND (def_stmt, 1);
2445 if (TREE_CODE (rhs) == SSA_NAME)
2446 return get_strlen (rhs, length, visited);
2448 /* See if the RHS is a constant length. */
2449 len = c_strlen (rhs, 1);
2452 if (*length && simple_cst_equal (len, *length) != 1)
2464 /* All the arguments of the PHI node must have the same constant
2468 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
2470 tree arg = PHI_ARG_DEF (def_stmt, i);
2472 /* If this PHI has itself as an argument, we cannot
2473 determine the string length of this argument. However,
2474 if we can find a constant string length for the other
2475 PHI args then we can still be sure that this is a
2476 constant string length. So be optimistic and just
2477 continue with the next argument. */
2478 if (arg == PHI_RESULT (def_stmt))
2481 if (!get_strlen (arg, length, visited))
2497 /* A simple pass that attempts to fold all builtin functions. This pass
2498 is run after we've propagated as many constants as we can. */
2501 execute_fold_all_builtins (void)
2506 block_stmt_iterator i;
2507 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
2509 tree *stmtp = bsi_stmt_ptr (i);
2510 tree call = get_rhs (*stmtp);
2511 tree callee, result;
2513 if (!call || TREE_CODE (call) != CALL_EXPR)
2515 callee = get_callee_fndecl (call);
2516 if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
2519 result = ccp_fold_builtin (*stmtp, call);
2521 switch (DECL_FUNCTION_CODE (callee))
2523 case BUILT_IN_CONSTANT_P:
2524 /* Resolve __builtin_constant_p. If it hasn't been
2525 folded to integer_one_node by now, it's fairly
2526 certain that the value simply isn't constant. */
2527 result = integer_zero_node;
2534 if (dump_file && (dump_flags & TDF_DETAILS))
2536 fprintf (dump_file, "Simplified\n ");
2537 print_generic_stmt (dump_file, *stmtp, dump_flags);
2540 if (set_rhs (stmtp, result))
2541 modify_stmt (*stmtp);
2543 if (dump_file && (dump_flags & TDF_DETAILS))
2545 fprintf (dump_file, "to\n ");
2546 print_generic_stmt (dump_file, *stmtp, dump_flags);
2547 fprintf (dump_file, "\n");
2553 struct tree_opt_pass pass_fold_builtins =
2557 execute_fold_all_builtins, /* execute */
2560 0, /* static_pass_number */
2562 PROP_cfg | PROP_ssa, /* properties_required */
2563 0, /* properties_provided */
2564 0, /* properties_destroyed */
2565 0, /* todo_flags_start */
2566 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
2570 #include "gt-tree-ssa-ccp.h"