1 /* Conditional constant propagation pass for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003 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 void 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
);
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. */
967 if (TREE_TYPE (retval
) != TREE_TYPE (rhs
))
968 retval
= fold_convert (TREE_TYPE (rhs
), retval
);
970 if (TREE_TYPE (retval
) == TREE_TYPE (rhs
))
974 /* No simplification was possible. */
979 /* Evaluate statement STMT. */
982 evaluate_stmt (tree stmt
)
986 latticevalue likelyvalue
= likely_value (stmt
);
988 /* If the statement is likely to have a CONSTANT result, then try
989 to fold the statement to determine the constant value. */
990 if (likelyvalue
== CONSTANT
)
991 simplified
= ccp_fold (stmt
);
992 /* If the statement is likely to have a VARYING result, then do not
993 bother folding the statement. */
994 else if (likelyvalue
== VARYING
)
995 simplified
= get_rhs (stmt
);
996 /* Otherwise the statement is likely to have an UNDEFINED value and
997 there will be nothing to do. */
999 simplified
= NULL_TREE
;
1001 if (simplified
&& is_gimple_min_invariant (simplified
))
1003 /* The statement produced a constant value. */
1004 val
.lattice_val
= CONSTANT
;
1005 val
.const_val
= simplified
;
1009 /* The statement produced a nonconstant value. If the statement
1010 had undefined operands, then the result of the statement should
1011 be undefined. Else the result of the statement is VARYING. */
1012 val
.lattice_val
= (likelyvalue
== UNDEFINED
? UNDEFINED
: VARYING
);
1013 val
.const_val
= NULL_TREE
;
1020 /* Debugging dumps. */
1023 dump_lattice_value (FILE *outf
, const char *prefix
, value val
)
1025 switch (val
.lattice_val
)
1028 fprintf (outf
, "%sUNDEFINED", prefix
);
1031 fprintf (outf
, "%sVARYING", prefix
);
1034 fprintf (outf
, "%sCONSTANT ", prefix
);
1035 print_generic_expr (outf
, val
.const_val
, dump_flags
);
1042 /* Given a constant value VAL for bitfield FIELD, and a destination
1043 variable VAR, return VAL appropriately widened to fit into VAR. If
1044 FIELD is wider than HOST_WIDE_INT, NULL is returned. */
1047 widen_bitfield (tree val
, tree field
, tree var
)
1049 unsigned HOST_WIDE_INT var_size
, field_size
;
1051 unsigned HOST_WIDE_INT mask
;
1054 /* We can only do this if the size of the type and field and VAL are
1055 all constants representable in HOST_WIDE_INT. */
1056 if (!host_integerp (TYPE_SIZE (TREE_TYPE (var
)), 1)
1057 || !host_integerp (DECL_SIZE (field
), 1)
1058 || !host_integerp (val
, 0))
1061 var_size
= tree_low_cst (TYPE_SIZE (TREE_TYPE (var
)), 1);
1062 field_size
= tree_low_cst (DECL_SIZE (field
), 1);
1064 /* Give up if either the bitfield or the variable are too wide. */
1065 if (field_size
> HOST_BITS_PER_WIDE_INT
|| var_size
> HOST_BITS_PER_WIDE_INT
)
1068 #if defined ENABLE_CHECKING
1069 if (var_size
< field_size
)
1073 /* If the sign bit of the value is not set or the field's type is unsigned,
1074 just mask off the high order bits of the value. */
1075 if (DECL_UNSIGNED (field
)
1076 || !(tree_low_cst (val
, 0) & (((HOST_WIDE_INT
)1) << (field_size
- 1))))
1078 /* Zero extension. Build a mask with the lower 'field_size' bits
1079 set and a BIT_AND_EXPR node to clear the high order bits of
1081 for (i
= 0, mask
= 0; i
< field_size
; i
++)
1082 mask
|= ((HOST_WIDE_INT
) 1) << i
;
1084 wide_val
= build (BIT_AND_EXPR
, TREE_TYPE (var
), val
,
1085 fold_convert (TREE_TYPE (var
), build_int_2 (mask
, 0)));
1089 /* Sign extension. Create a mask with the upper 'field_size'
1090 bits set and a BIT_IOR_EXPR to set the high order bits of the
1092 for (i
= 0, mask
= 0; i
< (var_size
- field_size
); i
++)
1093 mask
|= ((HOST_WIDE_INT
) 1) << (var_size
- i
- 1);
1095 wide_val
= build (BIT_IOR_EXPR
, TREE_TYPE (var
), val
,
1096 fold_convert (TREE_TYPE (var
), build_int_2 (mask
, 0)));
1099 return fold (wide_val
);
1103 /* Function indicating whether we ought to include information for 'var'
1104 when calculating immediate uses. */
1107 need_imm_uses_for (tree var
)
1109 return get_value (var
)->lattice_val
!= VARYING
;
1113 /* Initialize local data structures and worklists for CCP. */
1120 sbitmap virtual_var
;
1122 /* Worklists of SSA edges. */
1123 VARRAY_TREE_INIT (ssa_edges
, 20, "ssa_edges");
1124 VARRAY_TREE_INIT (varying_ssa_edges
, 20, "varying_ssa_edges");
1126 executable_blocks
= sbitmap_alloc (last_basic_block
);
1127 sbitmap_zero (executable_blocks
);
1129 bb_in_list
= sbitmap_alloc (last_basic_block
);
1130 sbitmap_zero (bb_in_list
);
1132 value_vector
= (value
*) xmalloc (num_ssa_names
* sizeof (value
));
1133 memset (value_vector
, 0, num_ssa_names
* sizeof (value
));
1135 /* 1 if ssa variable is used in a virtual variable context. */
1136 virtual_var
= sbitmap_alloc (num_ssa_names
);
1137 sbitmap_zero (virtual_var
);
1139 /* Initialize default values and simulation flags for PHI nodes, statements
1143 block_stmt_iterator i
;
1147 v_may_def_optype v_may_defs
;
1148 v_must_def_optype v_must_defs
;
1152 /* Get the default value for each definition. */
1153 for (i
= bsi_start (bb
); !bsi_end_p (i
); bsi_next (&i
))
1156 stmt
= bsi_stmt (i
);
1157 get_stmt_operands (stmt
);
1158 ann
= stmt_ann (stmt
);
1159 defs
= DEF_OPS (ann
);
1160 for (x
= 0; x
< NUM_DEFS (defs
); x
++)
1162 tree def
= DEF_OP (defs
, x
);
1163 if (get_value (def
)->lattice_val
== VARYING
)
1166 DONT_SIMULATE_AGAIN (stmt
) = vary
;
1168 /* Mark all V_MAY_DEF operands VARYING. */
1169 v_may_defs
= V_MAY_DEF_OPS (ann
);
1170 for (x
= 0; x
< NUM_V_MAY_DEFS (v_may_defs
); x
++)
1172 tree res
= V_MAY_DEF_RESULT (v_may_defs
, x
);
1173 get_value (res
)->lattice_val
= VARYING
;
1174 SET_BIT (virtual_var
, SSA_NAME_VERSION (res
));
1177 /* Mark all V_MUST_DEF operands VARYING. */
1178 v_must_defs
= V_MUST_DEF_OPS (ann
);
1179 for (x
= 0; x
< NUM_V_MUST_DEFS (v_must_defs
); x
++)
1181 tree v_must_def
= V_MUST_DEF_OP (v_must_defs
, x
);
1182 get_value (v_must_def
)->lattice_val
= VARYING
;
1183 SET_BIT (virtual_var
, SSA_NAME_VERSION (v_must_def
));
1187 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1188 e
->flags
&= ~EDGE_EXECUTABLE
;
1191 /* Now process PHI nodes. */
1196 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1199 val
= get_value (PHI_RESULT (phi
));
1200 if (val
->lattice_val
!= VARYING
)
1202 for (x
= 0; x
< PHI_NUM_ARGS (phi
); x
++)
1204 var
= PHI_ARG_DEF (phi
, x
);
1205 /* If one argument is virtual, the result is virtual, and
1206 therefore varying. */
1207 if (TREE_CODE (var
) == SSA_NAME
)
1209 if (TEST_BIT (virtual_var
, SSA_NAME_VERSION (var
)))
1211 val
->lattice_val
= VARYING
;
1212 SET_BIT (virtual_var
,
1213 SSA_NAME_VERSION (PHI_RESULT (phi
)));
1219 DONT_SIMULATE_AGAIN (phi
) = ((val
->lattice_val
== VARYING
) ? 1 : 0);
1223 sbitmap_free (virtual_var
);
1224 /* Compute immediate uses for variables we care about. */
1225 compute_immediate_uses (TDFA_USE_OPS
, need_imm_uses_for
);
1227 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1228 dump_immediate_uses (dump_file
);
1230 VARRAY_BB_INIT (cfg_blocks
, 20, "cfg_blocks");
1232 /* Seed the algorithm by adding the successors of the entry block to the
1234 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
1236 if (e
->dest
!= EXIT_BLOCK_PTR
)
1238 e
->flags
|= EDGE_EXECUTABLE
;
1239 cfg_blocks_add (e
->dest
);
1245 /* Free allocated storage. */
1251 varying_ssa_edges
= NULL
;
1253 free (value_vector
);
1254 sbitmap_free (bb_in_list
);
1255 sbitmap_free (executable_blocks
);
1259 /* Is the block worklist empty. */
1262 cfg_blocks_empty_p (void)
1264 return (cfg_blocks_num
== 0);
1267 /* Add a basic block to the worklist. */
1270 cfg_blocks_add (basic_block bb
)
1272 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
1275 if (TEST_BIT (bb_in_list
, bb
->index
))
1278 if (cfg_blocks_empty_p ())
1280 cfg_blocks_tail
= cfg_blocks_head
= 0;
1286 if (cfg_blocks_num
> VARRAY_SIZE (cfg_blocks
))
1288 /* We have to grow the array now. Adjust to queue to occupy the
1289 full space of the original array. */
1290 cfg_blocks_tail
= VARRAY_SIZE (cfg_blocks
);
1291 cfg_blocks_head
= 0;
1292 VARRAY_GROW (cfg_blocks
, 2 * VARRAY_SIZE (cfg_blocks
));
1295 cfg_blocks_tail
= (cfg_blocks_tail
+ 1) % VARRAY_SIZE (cfg_blocks
);
1297 VARRAY_BB (cfg_blocks
, cfg_blocks_tail
) = bb
;
1298 SET_BIT (bb_in_list
, bb
->index
);
1301 /* Remove a block from the worklist. */
1304 cfg_blocks_get (void)
1308 bb
= VARRAY_BB (cfg_blocks
, cfg_blocks_head
);
1310 #ifdef ENABLE_CHECKING
1311 if (cfg_blocks_empty_p () || !bb
)
1315 cfg_blocks_head
= (cfg_blocks_head
+ 1) % VARRAY_SIZE (cfg_blocks
);
1317 RESET_BIT (bb_in_list
, bb
->index
);
1322 /* We have just defined a new value for VAR. Add all immediate uses
1323 of VAR to the ssa_edges or varying_ssa_edges worklist. */
1325 add_var_to_ssa_edges_worklist (tree var
, value val
)
1327 tree stmt
= SSA_NAME_DEF_STMT (var
);
1328 dataflow_t df
= get_immediate_uses (stmt
);
1329 int num_uses
= num_immediate_uses (df
);
1332 for (i
= 0; i
< num_uses
; i
++)
1334 tree use
= immediate_use (df
, i
);
1336 if (!DONT_SIMULATE_AGAIN (use
))
1338 stmt_ann_t ann
= stmt_ann (use
);
1339 if (ann
->in_ccp_worklist
== 0)
1341 ann
->in_ccp_worklist
= 1;
1342 if (val
.lattice_val
== VARYING
)
1343 VARRAY_PUSH_TREE (varying_ssa_edges
, use
);
1345 VARRAY_PUSH_TREE (ssa_edges
, use
);
1351 /* Set the lattice value for the variable VAR to VARYING. */
1354 def_to_varying (tree var
)
1357 val
.lattice_val
= VARYING
;
1358 val
.const_val
= NULL_TREE
;
1359 set_lattice_value (var
, val
);
1362 /* Set the lattice value for variable VAR to VAL. */
1365 set_lattice_value (tree var
, value val
)
1367 value
*old
= get_value (var
);
1369 #ifdef ENABLE_CHECKING
1370 if (val
.lattice_val
== UNDEFINED
)
1372 /* CONSTANT->UNDEFINED is never a valid state transition. */
1373 if (old
->lattice_val
== CONSTANT
)
1376 /* VARYING->UNDEFINED is generally not a valid state transition,
1377 except for values which are initialized to VARYING. */
1378 if (old
->lattice_val
== VARYING
1379 && get_default_value (var
).lattice_val
!= VARYING
)
1382 else if (val
.lattice_val
== CONSTANT
)
1384 /* VARYING -> CONSTANT is an invalid state transition, except
1385 for objects which start off in a VARYING state. */
1386 if (old
->lattice_val
== VARYING
1387 && get_default_value (var
).lattice_val
!= VARYING
)
1392 /* If the constant for VAR has changed, then this VAR is really varying. */
1393 if (old
->lattice_val
== CONSTANT
&& val
.lattice_val
== CONSTANT
1394 && !simple_cst_equal (old
->const_val
, val
.const_val
))
1396 val
.lattice_val
= VARYING
;
1397 val
.const_val
= NULL_TREE
;
1400 if (old
->lattice_val
!= val
.lattice_val
)
1402 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1404 dump_lattice_value (dump_file
,
1405 "Lattice value changed to ", val
);
1406 fprintf (dump_file
, ". Adding definition to SSA edges.\n");
1409 add_var_to_ssa_edges_worklist (var
, val
);
1414 /* Replace USE references in statement STMT with their immediate reaching
1415 definition. Return true if at least one reference was replaced. If
1416 REPLACED_ADDRESSES_P is given, it will be set to true if an address
1417 constant was replaced. */
1420 replace_uses_in (tree stmt
, bool *replaced_addresses_p
)
1422 bool replaced
= false;
1426 if (replaced_addresses_p
)
1427 *replaced_addresses_p
= false;
1429 get_stmt_operands (stmt
);
1431 uses
= STMT_USE_OPS (stmt
);
1432 for (i
= 0; i
< NUM_USES (uses
); i
++)
1434 use_operand_p use
= USE_OP_PTR (uses
, i
);
1435 value
*val
= get_value (USE_FROM_PTR (use
));
1437 if (val
->lattice_val
== CONSTANT
)
1439 SET_USE (use
, val
->const_val
);
1441 if (POINTER_TYPE_P (TREE_TYPE (USE_FROM_PTR (use
)))
1442 && replaced_addresses_p
)
1443 *replaced_addresses_p
= true;
1450 /* Return the likely latticevalue for STMT.
1452 If STMT has no operands, then return CONSTANT.
1454 Else if any operands of STMT are undefined, then return UNDEFINED.
1456 Else if any operands of STMT are constants, then return CONSTANT.
1458 Else return VARYING. */
1461 likely_value (tree stmt
)
1465 int found_constant
= 0;
1468 /* If the statement makes aliased loads or has volatile operands, it
1469 won't fold to a constant value. */
1470 ann
= stmt_ann (stmt
);
1471 if (ann
->makes_aliased_loads
|| ann
->has_volatile_ops
)
1474 /* A CALL_EXPR is assumed to be varying. This may be overly conservative,
1475 in the presence of const and pure calls. */
1476 if (get_call_expr_in (stmt
) != NULL_TREE
)
1479 get_stmt_operands (stmt
);
1481 uses
= USE_OPS (ann
);
1482 for (i
= 0; i
< NUM_USES (uses
); i
++)
1484 tree use
= USE_OP (uses
, i
);
1485 value
*val
= get_value (use
);
1487 if (val
->lattice_val
== UNDEFINED
)
1490 if (val
->lattice_val
== CONSTANT
)
1494 return ((found_constant
|| !uses
) ? CONSTANT
: VARYING
);
1497 /* A subroutine of fold_stmt_r. Attempts to fold *(A+O) to A[X].
1498 BASE is an array type. OFFSET is a byte displacement. ORIG_TYPE
1499 is the desired result type. */
1502 maybe_fold_offset_to_array_ref (tree base
, tree offset
, tree orig_type
)
1504 tree min_idx
, idx
, elt_offset
= integer_zero_node
;
1505 tree array_type
, elt_type
, elt_size
;
1507 /* If BASE is an ARRAY_REF, we can pick up another offset (this time
1508 measured in units of the size of elements type) from that ARRAY_REF).
1509 We can't do anything if either is variable.
1511 The case we handle here is *(&A[N]+O). */
1512 if (TREE_CODE (base
) == ARRAY_REF
)
1514 tree low_bound
= array_ref_low_bound (base
);
1516 elt_offset
= TREE_OPERAND (base
, 1);
1517 if (TREE_CODE (low_bound
) != INTEGER_CST
1518 || TREE_CODE (elt_offset
) != INTEGER_CST
)
1521 elt_offset
= int_const_binop (MINUS_EXPR
, elt_offset
, low_bound
, 0);
1522 base
= TREE_OPERAND (base
, 0);
1525 /* Ignore stupid user tricks of indexing non-array variables. */
1526 array_type
= TREE_TYPE (base
);
1527 if (TREE_CODE (array_type
) != ARRAY_TYPE
)
1529 elt_type
= TREE_TYPE (array_type
);
1530 if (!lang_hooks
.types_compatible_p (orig_type
, elt_type
))
1533 /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the
1534 element type (so we can use the alignment if it's not constant).
1535 Otherwise, compute the offset as an index by using a division. If the
1536 division isn't exact, then don't do anything. */
1537 elt_size
= TYPE_SIZE_UNIT (elt_type
);
1538 if (integer_zerop (offset
))
1540 if (TREE_CODE (elt_size
) != INTEGER_CST
)
1541 elt_size
= size_int (TYPE_ALIGN (elt_type
));
1543 idx
= integer_zero_node
;
1547 unsigned HOST_WIDE_INT lquo
, lrem
;
1548 HOST_WIDE_INT hquo
, hrem
;
1550 if (TREE_CODE (elt_size
) != INTEGER_CST
1551 || div_and_round_double (TRUNC_DIV_EXPR
, 1,
1552 TREE_INT_CST_LOW (offset
),
1553 TREE_INT_CST_HIGH (offset
),
1554 TREE_INT_CST_LOW (elt_size
),
1555 TREE_INT_CST_HIGH (elt_size
),
1556 &lquo
, &hquo
, &lrem
, &hrem
)
1560 idx
= build_int_2_wide (lquo
, hquo
);
1563 /* Assume the low bound is zero. If there is a domain type, get the
1564 low bound, if any, convert the index into that type, and add the
1566 min_idx
= integer_zero_node
;
1567 if (TYPE_DOMAIN (array_type
))
1569 if (TYPE_MIN_VALUE (TYPE_DOMAIN (array_type
)))
1570 min_idx
= TYPE_MIN_VALUE (TYPE_DOMAIN (array_type
));
1572 min_idx
= fold_convert (TYPE_DOMAIN (array_type
), min_idx
);
1574 if (TREE_CODE (min_idx
) != INTEGER_CST
)
1577 idx
= fold_convert (TYPE_DOMAIN (array_type
), idx
);
1578 elt_offset
= fold_convert (TYPE_DOMAIN (array_type
), elt_offset
);
1581 if (!integer_zerop (min_idx
))
1582 idx
= int_const_binop (PLUS_EXPR
, idx
, min_idx
, 0);
1583 if (!integer_zerop (elt_offset
))
1584 idx
= int_const_binop (PLUS_EXPR
, idx
, elt_offset
, 0);
1586 return build (ARRAY_REF
, orig_type
, base
, idx
, min_idx
,
1587 size_int (tree_low_cst (elt_size
, 1)
1588 / (TYPE_ALIGN (elt_type
) / BITS_PER_UNIT
)));
1591 /* A subroutine of fold_stmt_r. Attempts to fold *(S+O) to S.X.
1592 BASE is a record type. OFFSET is a byte displacement. ORIG_TYPE
1593 is the desired result type. */
1594 /* ??? This doesn't handle class inheritance. */
1597 maybe_fold_offset_to_component_ref (tree record_type
, tree base
, tree offset
,
1598 tree orig_type
, bool base_is_ptr
)
1600 tree f
, t
, field_type
, tail_array_field
;
1602 if (TREE_CODE (record_type
) != RECORD_TYPE
1603 && TREE_CODE (record_type
) != UNION_TYPE
1604 && TREE_CODE (record_type
) != QUAL_UNION_TYPE
)
1607 /* Short-circuit silly cases. */
1608 if (lang_hooks
.types_compatible_p (record_type
, orig_type
))
1611 tail_array_field
= NULL_TREE
;
1612 for (f
= TYPE_FIELDS (record_type
); f
; f
= TREE_CHAIN (f
))
1616 if (TREE_CODE (f
) != FIELD_DECL
)
1618 if (DECL_BIT_FIELD (f
))
1620 if (TREE_CODE (DECL_FIELD_OFFSET (f
)) != INTEGER_CST
)
1623 /* ??? Java creates "interesting" fields for representing base classes.
1624 They have no name, and have no context. With no context, we get into
1625 trouble with nonoverlapping_component_refs_p. Skip them. */
1626 if (!DECL_FIELD_CONTEXT (f
))
1629 /* The previous array field isn't at the end. */
1630 tail_array_field
= NULL_TREE
;
1632 /* Check to see if this offset overlaps with the field. */
1633 cmp
= tree_int_cst_compare (DECL_FIELD_OFFSET (f
), offset
);
1637 field_type
= TREE_TYPE (f
);
1640 /* Don't care about offsets into the middle of scalars. */
1641 if (!AGGREGATE_TYPE_P (field_type
))
1644 /* Check for array at the end of the struct. This is often
1645 used as for flexible array members. We should be able to
1646 turn this into an array access anyway. */
1647 if (TREE_CODE (field_type
) == ARRAY_TYPE
)
1648 tail_array_field
= f
;
1650 /* Check the end of the field against the offset. */
1651 if (!DECL_SIZE_UNIT (f
)
1652 || TREE_CODE (DECL_SIZE_UNIT (f
)) != INTEGER_CST
)
1654 t
= int_const_binop (MINUS_EXPR
, offset
, DECL_FIELD_OFFSET (f
), 1);
1655 if (!tree_int_cst_lt (t
, DECL_SIZE_UNIT (f
)))
1658 /* If we matched, then set offset to the displacement into
1663 /* Here we exactly match the offset being checked. If the types match,
1664 then we can return that field. */
1665 else if (lang_hooks
.types_compatible_p (orig_type
, field_type
))
1668 base
= build1 (INDIRECT_REF
, record_type
, base
);
1669 t
= build (COMPONENT_REF
, field_type
, base
, f
, NULL_TREE
);
1673 /* Don't care about type-punning of scalars. */
1674 else if (!AGGREGATE_TYPE_P (field_type
))
1680 if (!tail_array_field
)
1683 f
= tail_array_field
;
1684 field_type
= TREE_TYPE (f
);
1687 /* If we get here, we've got an aggregate field, and a possibly
1688 nonzero offset into them. Recurse and hope for a valid match. */
1690 base
= build1 (INDIRECT_REF
, record_type
, base
);
1691 base
= build (COMPONENT_REF
, field_type
, base
, f
, NULL_TREE
);
1693 t
= maybe_fold_offset_to_array_ref (base
, offset
, orig_type
);
1696 return maybe_fold_offset_to_component_ref (field_type
, base
, offset
,
1700 /* A subroutine of fold_stmt_r. Attempt to simplify *(BASE+OFFSET).
1701 Return the simplified expression, or NULL if nothing could be done. */
1704 maybe_fold_stmt_indirect (tree expr
, tree base
, tree offset
)
1708 /* We may well have constructed a double-nested PLUS_EXPR via multiple
1709 substitutions. Fold that down to one. Remove NON_LVALUE_EXPRs that
1710 are sometimes added. */
1713 TREE_OPERAND (expr
, 0) = base
;
1715 /* One possibility is that the address reduces to a string constant. */
1716 t
= fold_read_from_constant_string (expr
);
1720 /* Add in any offset from a PLUS_EXPR. */
1721 if (TREE_CODE (base
) == PLUS_EXPR
)
1725 offset2
= TREE_OPERAND (base
, 1);
1726 if (TREE_CODE (offset2
) != INTEGER_CST
)
1728 base
= TREE_OPERAND (base
, 0);
1730 offset
= int_const_binop (PLUS_EXPR
, offset
, offset2
, 1);
1733 if (TREE_CODE (base
) == ADDR_EXPR
)
1735 /* Strip the ADDR_EXPR. */
1736 base
= TREE_OPERAND (base
, 0);
1738 /* Try folding *(&B+O) to B[X]. */
1739 t
= maybe_fold_offset_to_array_ref (base
, offset
, TREE_TYPE (expr
));
1743 /* Try folding *(&B+O) to B.X. */
1744 t
= maybe_fold_offset_to_component_ref (TREE_TYPE (base
), base
, offset
,
1745 TREE_TYPE (expr
), false);
1749 /* Fold *&B to B. We can only do this if EXPR is the same type
1750 as BASE. We can't do this if EXPR is the element type of an array
1751 and BASE is the array. */
1752 if (integer_zerop (offset
)
1753 && lang_hooks
.types_compatible_p (TREE_TYPE (base
),
1759 /* We can get here for out-of-range string constant accesses,
1760 such as "_"[3]. Bail out of the entire substitution search
1761 and arrange for the entire statement to be replaced by a
1762 call to __builtin_trap. In all likelyhood this will all be
1763 constant-folded away, but in the meantime we can't leave with
1764 something that get_expr_operands can't understand. */
1768 if (TREE_CODE (t
) == ADDR_EXPR
1769 && TREE_CODE (TREE_OPERAND (t
, 0)) == STRING_CST
)
1771 /* FIXME: Except that this causes problems elsewhere with dead
1772 code not being deleted, and we abort in the rtl expanders
1773 because we failed to remove some ssa_name. In the meantime,
1774 just return zero. */
1775 /* FIXME2: This condition should be signaled by
1776 fold_read_from_constant_string directly, rather than
1777 re-checking for it here. */
1778 return integer_zero_node
;
1781 /* Try folding *(B+O) to B->X. Still an improvement. */
1782 if (POINTER_TYPE_P (TREE_TYPE (base
)))
1784 t
= maybe_fold_offset_to_component_ref (TREE_TYPE (TREE_TYPE (base
)),
1786 TREE_TYPE (expr
), true);
1792 /* Otherwise we had an offset that we could not simplify. */
1796 /* A subroutine of fold_stmt_r. EXPR is a PLUS_EXPR.
1798 A quaint feature extant in our address arithmetic is that there
1799 can be hidden type changes here. The type of the result need
1800 not be the same as the type of the input pointer.
1802 What we're after here is an expression of the form
1803 (T *)(&array + const)
1804 where the cast doesn't actually exist, but is implicit in the
1805 type of the PLUS_EXPR. We'd like to turn this into
1807 which may be able to propagate further. */
1810 maybe_fold_stmt_addition (tree expr
)
1812 tree op0
= TREE_OPERAND (expr
, 0);
1813 tree op1
= TREE_OPERAND (expr
, 1);
1814 tree ptr_type
= TREE_TYPE (expr
);
1817 bool subtract
= (TREE_CODE (expr
) == MINUS_EXPR
);
1819 /* We're only interested in pointer arithmetic. */
1820 if (!POINTER_TYPE_P (ptr_type
))
1822 /* Canonicalize the integral operand to op1. */
1823 if (INTEGRAL_TYPE_P (TREE_TYPE (op0
)))
1827 t
= op0
, op0
= op1
, op1
= t
;
1829 /* It had better be a constant. */
1830 if (TREE_CODE (op1
) != INTEGER_CST
)
1832 /* The first operand should be an ADDR_EXPR. */
1833 if (TREE_CODE (op0
) != ADDR_EXPR
)
1835 op0
= TREE_OPERAND (op0
, 0);
1837 /* If the first operand is an ARRAY_REF, expand it so that we can fold
1838 the offset into it. */
1839 while (TREE_CODE (op0
) == ARRAY_REF
)
1841 tree array_obj
= TREE_OPERAND (op0
, 0);
1842 tree array_idx
= TREE_OPERAND (op0
, 1);
1843 tree elt_type
= TREE_TYPE (op0
);
1844 tree elt_size
= TYPE_SIZE_UNIT (elt_type
);
1847 if (TREE_CODE (array_idx
) != INTEGER_CST
)
1849 if (TREE_CODE (elt_size
) != INTEGER_CST
)
1852 /* Un-bias the index by the min index of the array type. */
1853 min_idx
= TYPE_DOMAIN (TREE_TYPE (array_obj
));
1856 min_idx
= TYPE_MIN_VALUE (min_idx
);
1859 if (TREE_CODE (min_idx
) != INTEGER_CST
)
1862 array_idx
= convert (TREE_TYPE (min_idx
), array_idx
);
1863 if (!integer_zerop (min_idx
))
1864 array_idx
= int_const_binop (MINUS_EXPR
, array_idx
,
1869 /* Convert the index to a byte offset. */
1870 array_idx
= convert (sizetype
, array_idx
);
1871 array_idx
= int_const_binop (MULT_EXPR
, array_idx
, elt_size
, 0);
1873 /* Update the operands for the next round, or for folding. */
1874 /* If we're manipulating unsigned types, then folding into negative
1875 values can produce incorrect results. Particularly if the type
1876 is smaller than the width of the pointer. */
1878 && TYPE_UNSIGNED (TREE_TYPE (op1
))
1879 && tree_int_cst_lt (array_idx
, op1
))
1881 op1
= int_const_binop (subtract
? MINUS_EXPR
: PLUS_EXPR
,
1887 /* If we weren't able to fold the subtraction into another array reference,
1888 canonicalize the integer for passing to the array and component ref
1889 simplification functions. */
1892 if (TYPE_UNSIGNED (TREE_TYPE (op1
)))
1894 op1
= fold (build1 (NEGATE_EXPR
, TREE_TYPE (op1
), op1
));
1895 /* ??? In theory fold should always produce another integer. */
1896 if (TREE_CODE (op1
) != INTEGER_CST
)
1900 ptd_type
= TREE_TYPE (ptr_type
);
1902 /* At which point we can try some of the same things as for indirects. */
1903 t
= maybe_fold_offset_to_array_ref (op0
, op1
, ptd_type
);
1905 t
= maybe_fold_offset_to_component_ref (TREE_TYPE (op0
), op0
, op1
,
1908 t
= build1 (ADDR_EXPR
, ptr_type
, t
);
1913 /* Subroutine of fold_stmt called via walk_tree. We perform several
1914 simplifications of EXPR_P, mostly having to do with pointer arithmetic. */
1917 fold_stmt_r (tree
*expr_p
, int *walk_subtrees
, void *data
)
1919 bool *changed_p
= data
;
1920 tree expr
= *expr_p
, t
;
1922 /* ??? It'd be nice if walk_tree had a pre-order option. */
1923 switch (TREE_CODE (expr
))
1926 t
= walk_tree (&TREE_OPERAND (expr
, 0), fold_stmt_r
, data
, NULL
);
1931 t
= maybe_fold_stmt_indirect (expr
, TREE_OPERAND (expr
, 0),
1935 /* ??? Could handle ARRAY_REF here, as a variant of INDIRECT_REF.
1936 We'd only want to bother decomposing an existing ARRAY_REF if
1937 the base array is found to have another offset contained within.
1938 Otherwise we'd be wasting time. */
1941 t
= walk_tree (&TREE_OPERAND (expr
, 0), fold_stmt_r
, data
, NULL
);
1946 /* Set TREE_INVARIANT properly so that the value is properly
1947 considered constant, and so gets propagated as expected. */
1949 recompute_tree_invarant_for_addr_expr (expr
);
1954 t
= walk_tree (&TREE_OPERAND (expr
, 0), fold_stmt_r
, data
, NULL
);
1957 t
= walk_tree (&TREE_OPERAND (expr
, 1), fold_stmt_r
, data
, NULL
);
1962 t
= maybe_fold_stmt_addition (expr
);
1966 t
= walk_tree (&TREE_OPERAND (expr
, 0), fold_stmt_r
, data
, NULL
);
1971 /* Make sure the FIELD_DECL is actually a field in the type on
1972 the lhs. In cases with IMA it is possible that it came
1973 from another, equivalent type at this point. We have
1974 already checked the equivalence in this case.
1975 Match on type plus offset, to allow for unnamed fields.
1976 We won't necessarily get the corresponding field for
1977 unions; this is believed to be harmless. */
1979 if ((current_file_decl
&& TREE_CHAIN (current_file_decl
))
1980 && (DECL_FIELD_CONTEXT (TREE_OPERAND (expr
, 1)) !=
1981 TREE_TYPE (TREE_OPERAND (expr
, 0))))
1984 tree orig_field
= TREE_OPERAND (expr
, 1);
1985 tree orig_type
= TREE_TYPE (orig_field
);
1986 for (f
= TYPE_FIELDS (TREE_TYPE (TREE_OPERAND (expr
, 0)));
1987 f
; f
= TREE_CHAIN (f
))
1989 if (lang_hooks
.types_compatible_p (TREE_TYPE (f
), orig_type
)
1990 && tree_int_cst_compare (DECL_FIELD_BIT_OFFSET (f
),
1991 DECL_FIELD_BIT_OFFSET (orig_field
))
1993 && tree_int_cst_compare (DECL_FIELD_OFFSET (f
),
1994 DECL_FIELD_OFFSET (orig_field
))
1997 TREE_OPERAND (expr
, 1) = f
;
2001 /* Fall through is an error; it will be detected in tree-sra. */
2018 /* Fold the statement pointed by STMT_P. In some cases, this function may
2019 replace the whole statement with a new one. Returns true iff folding
2020 makes any changes. */
2023 fold_stmt (tree
*stmt_p
)
2025 tree rhs
, result
, stmt
;
2026 bool changed
= false;
2030 /* If we replaced constants and the statement makes pointer dereferences,
2031 then we may need to fold instances of *&VAR into VAR, etc. */
2032 if (walk_tree (stmt_p
, fold_stmt_r
, &changed
, NULL
))
2035 = build_function_call_expr (implicit_built_in_decls
[BUILT_IN_TRAP
],
2040 rhs
= get_rhs (stmt
);
2045 if (TREE_CODE (rhs
) == CALL_EXPR
)
2049 /* Check for builtins that CCP can handle using information not
2050 available in the generic fold routines. */
2051 callee
= get_callee_fndecl (rhs
);
2052 if (callee
&& DECL_BUILT_IN (callee
))
2053 result
= ccp_fold_builtin (stmt
, rhs
);
2056 /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve
2057 here are when we've propagated the address of a decl into the
2059 /* ??? Should perhaps do this in fold proper. However, doing it
2060 there requires that we create a new CALL_EXPR, and that requires
2061 copying EH region info to the new node. Easier to just do it
2062 here where we can just smash the call operand. */
2063 callee
= TREE_OPERAND (rhs
, 0);
2064 if (TREE_CODE (callee
) == OBJ_TYPE_REF
2065 && lang_hooks
.fold_obj_type_ref
2066 && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee
)) == ADDR_EXPR
2067 && DECL_P (TREE_OPERAND (OBJ_TYPE_REF_OBJECT (callee
), 0)))
2071 t
= TREE_TYPE (TREE_OPERAND (OBJ_TYPE_REF_OBJECT (callee
), 0));
2072 t
= lang_hooks
.fold_obj_type_ref (callee
, t
);
2075 TREE_OPERAND (rhs
, 0) = t
;
2082 /* If we couldn't fold the RHS, hand over to the generic fold routines. */
2083 if (result
== NULL_TREE
)
2084 result
= fold (rhs
);
2086 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
2087 may have been added by fold, and "useless" type conversions that might
2088 now be apparent due to propagation. */
2089 STRIP_USELESS_TYPE_CONVERSION (result
);
2094 set_rhs (stmt_p
, result
);
2100 /* Get the main expression from statement STMT. */
2105 enum tree_code code
= TREE_CODE (stmt
);
2107 if (code
== MODIFY_EXPR
)
2108 return TREE_OPERAND (stmt
, 1);
2109 if (code
== COND_EXPR
)
2110 return COND_EXPR_COND (stmt
);
2111 else if (code
== SWITCH_EXPR
)
2112 return SWITCH_COND (stmt
);
2113 else if (code
== RETURN_EXPR
)
2115 if (!TREE_OPERAND (stmt
, 0))
2117 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
)
2118 return TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1);
2120 return TREE_OPERAND (stmt
, 0);
2122 else if (code
== GOTO_EXPR
)
2123 return GOTO_DESTINATION (stmt
);
2124 else if (code
== LABEL_EXPR
)
2125 return LABEL_EXPR_LABEL (stmt
);
2131 /* Set the main expression of *STMT_P to EXPR. */
2134 set_rhs (tree
*stmt_p
, tree expr
)
2136 tree stmt
= *stmt_p
;
2137 enum tree_code code
= TREE_CODE (stmt
);
2139 if (code
== MODIFY_EXPR
)
2140 TREE_OPERAND (stmt
, 1) = expr
;
2141 else if (code
== COND_EXPR
)
2142 COND_EXPR_COND (stmt
) = expr
;
2143 else if (code
== SWITCH_EXPR
)
2144 SWITCH_COND (stmt
) = expr
;
2145 else if (code
== RETURN_EXPR
)
2147 if (TREE_OPERAND (stmt
, 0)
2148 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
)
2149 TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1) = expr
;
2151 TREE_OPERAND (stmt
, 0) = expr
;
2153 else if (code
== GOTO_EXPR
)
2154 GOTO_DESTINATION (stmt
) = expr
;
2155 else if (code
== LABEL_EXPR
)
2156 LABEL_EXPR_LABEL (stmt
) = expr
;
2159 /* Replace the whole statement with EXPR. If EXPR has no side
2160 effects, then replace *STMT_P with an empty statement. */
2161 stmt_ann_t ann
= stmt_ann (stmt
);
2162 *stmt_p
= TREE_SIDE_EFFECTS (expr
) ? expr
: build_empty_stmt ();
2163 (*stmt_p
)->common
.ann
= (tree_ann_t
) ann
;
2165 if (TREE_SIDE_EFFECTS (expr
))
2168 v_may_def_optype v_may_defs
;
2169 v_must_def_optype v_must_defs
;
2172 /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
2174 defs
= DEF_OPS (ann
);
2175 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
2177 tree var
= DEF_OP (defs
, i
);
2178 if (TREE_CODE (var
) == SSA_NAME
)
2179 SSA_NAME_DEF_STMT (var
) = *stmt_p
;
2182 v_may_defs
= V_MAY_DEF_OPS (ann
);
2183 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
2185 tree var
= V_MAY_DEF_RESULT (v_may_defs
, i
);
2186 if (TREE_CODE (var
) == SSA_NAME
)
2187 SSA_NAME_DEF_STMT (var
) = *stmt_p
;
2190 v_must_defs
= V_MUST_DEF_OPS (ann
);
2191 for (i
= 0; i
< NUM_V_MUST_DEFS (v_must_defs
); i
++)
2193 tree var
= V_MUST_DEF_OP (v_must_defs
, i
);
2194 if (TREE_CODE (var
) == SSA_NAME
)
2195 SSA_NAME_DEF_STMT (var
) = *stmt_p
;
2202 /* Return a default value for variable VAR using the following rules:
2204 1- Global and static variables are considered VARYING, unless they are
2207 2- Function arguments are considered VARYING.
2209 3- Any other value is considered UNDEFINED. This is useful when
2210 considering PHI nodes. PHI arguments that are undefined do not
2211 change the constant value of the PHI node, which allows for more
2212 constants to be propagated. */
2215 get_default_value (tree var
)
2220 if (TREE_CODE (var
) == SSA_NAME
)
2221 sym
= SSA_NAME_VAR (var
);
2224 #ifdef ENABLE_CHECKING
2231 val
.lattice_val
= UNDEFINED
;
2232 val
.const_val
= NULL_TREE
;
2234 if (TREE_CODE (sym
) == PARM_DECL
|| TREE_THIS_VOLATILE (sym
))
2236 /* Function arguments and volatile variables are considered VARYING. */
2237 val
.lattice_val
= VARYING
;
2239 else if (decl_function_context (sym
) != current_function_decl
2240 || TREE_STATIC (sym
))
2242 /* Globals and static variables are considered VARYING, unless they
2243 are declared 'const'. */
2244 val
.lattice_val
= VARYING
;
2246 if (TREE_READONLY (sym
)
2247 && DECL_INITIAL (sym
)
2248 && is_gimple_min_invariant (DECL_INITIAL (sym
)))
2250 val
.lattice_val
= CONSTANT
;
2251 val
.const_val
= DECL_INITIAL (sym
);
2256 enum tree_code code
;
2257 tree stmt
= SSA_NAME_DEF_STMT (var
);
2259 if (!IS_EMPTY_STMT (stmt
))
2261 code
= TREE_CODE (stmt
);
2262 if (code
!= MODIFY_EXPR
&& code
!= PHI_NODE
)
2263 val
.lattice_val
= VARYING
;
2271 /* Fold builtin call FN in statement STMT. If it cannot be folded into a
2272 constant, return NULL_TREE. Otherwise, return its constant value. */
2275 ccp_fold_builtin (tree stmt
, tree fn
)
2277 tree result
, strlen_val
[2];
2278 tree arglist
= TREE_OPERAND (fn
, 1), a
;
2279 tree callee
= get_callee_fndecl (fn
);
2283 /* Ignore MD builtins. */
2284 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_MD
)
2287 /* First try the generic builtin folder. If that succeeds, return the
2289 result
= fold_builtin (fn
);
2293 /* If the builtin could not be folded, and it has no argument list,
2298 /* Limit the work only for builtins we know how to simplify. */
2299 switch (DECL_FUNCTION_CODE (callee
))
2301 case BUILT_IN_STRLEN
:
2302 case BUILT_IN_FPUTS
:
2303 case BUILT_IN_FPUTS_UNLOCKED
:
2306 case BUILT_IN_STRCPY
:
2307 case BUILT_IN_STRNCPY
:
2314 /* Try to use the dataflow information gathered by the CCP process. */
2315 visited
= BITMAP_XMALLOC ();
2317 memset (strlen_val
, 0, sizeof (strlen_val
));
2318 for (i
= 0, a
= arglist
;
2320 i
++, strlen_arg
>>= 1, a
= TREE_CHAIN (a
))
2323 bitmap_clear (visited
);
2324 if (!get_strlen (TREE_VALUE (a
), &strlen_val
[i
], visited
))
2325 strlen_val
[i
] = NULL_TREE
;
2328 BITMAP_XFREE (visited
);
2330 /* FIXME. All this code looks dangerous in the sense that it might
2331 create non-gimple expressions. */
2332 switch (DECL_FUNCTION_CODE (callee
))
2334 case BUILT_IN_STRLEN
:
2335 /* Convert from the internal "sizetype" type to "size_t". */
2339 tree
new = convert (size_type_node
, strlen_val
[0]);
2341 /* If the result is not a valid gimple value, or not a cast
2342 of a valid gimple value, then we can not use the result. */
2343 if (is_gimple_val (new)
2344 || (is_gimple_cast (new)
2345 && is_gimple_val (TREE_OPERAND (new, 0))))
2350 return strlen_val
[0];
2351 case BUILT_IN_STRCPY
:
2353 && is_gimple_val (strlen_val
[1]))
2354 return simplify_builtin_strcpy (arglist
, strlen_val
[1]);
2355 case BUILT_IN_STRNCPY
:
2357 && is_gimple_val (strlen_val
[1]))
2358 return simplify_builtin_strncpy (arglist
, strlen_val
[1]);
2359 case BUILT_IN_FPUTS
:
2360 return simplify_builtin_fputs (arglist
,
2361 TREE_CODE (stmt
) != MODIFY_EXPR
, 0,
2363 case BUILT_IN_FPUTS_UNLOCKED
:
2364 return simplify_builtin_fputs (arglist
,
2365 TREE_CODE (stmt
) != MODIFY_EXPR
, 1,
2376 /* Return the string length of ARG in LENGTH. If ARG is an SSA name variable,
2377 follow its use-def chains. If LENGTH is not NULL and its value is not
2378 equal to the length we determine, or if we are unable to determine the
2379 length, return false. VISITED is a bitmap of visited variables. */
2382 get_strlen (tree arg
, tree
*length
, bitmap visited
)
2384 tree var
, def_stmt
, val
;
2386 if (TREE_CODE (arg
) != SSA_NAME
)
2388 val
= c_strlen (arg
, 1);
2392 if (*length
&& simple_cst_equal (val
, *length
) != 1)
2399 /* If we were already here, break the infinite cycle. */
2400 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (arg
)))
2402 bitmap_set_bit (visited
, SSA_NAME_VERSION (arg
));
2405 def_stmt
= SSA_NAME_DEF_STMT (var
);
2407 switch (TREE_CODE (def_stmt
))
2413 /* The RHS of the statement defining VAR must either have a
2414 constant length or come from another SSA_NAME with a constant
2416 rhs
= TREE_OPERAND (def_stmt
, 1);
2418 if (TREE_CODE (rhs
) == SSA_NAME
)
2419 return get_strlen (rhs
, length
, visited
);
2421 /* See if the RHS is a constant length. */
2422 len
= c_strlen (rhs
, 1);
2425 if (*length
&& simple_cst_equal (len
, *length
) != 1)
2437 /* All the arguments of the PHI node must have the same constant
2441 for (i
= 0; i
< PHI_NUM_ARGS (def_stmt
); i
++)
2443 tree arg
= PHI_ARG_DEF (def_stmt
, i
);
2445 /* If this PHI has itself as an argument, we cannot
2446 determine the string length of this argument. However,
2447 if we can find a constant string length for the other
2448 PHI args then we can still be sure that this is a
2449 constant string length. So be optimistic and just
2450 continue with the next argument. */
2451 if (arg
== PHI_RESULT (def_stmt
))
2454 if (!get_strlen (arg
, length
, visited
))
2470 /* A simple pass that attempts to fold all builtin functions. This pass
2471 is run after we've propagated as many constants as we can. */
2474 execute_fold_all_builtins (void)
2479 block_stmt_iterator i
;
2480 for (i
= bsi_start (bb
); !bsi_end_p (i
); bsi_next (&i
))
2482 tree
*stmtp
= bsi_stmt_ptr (i
);
2483 tree call
= get_rhs (*stmtp
);
2484 tree callee
, result
;
2486 if (!call
|| TREE_CODE (call
) != CALL_EXPR
)
2488 callee
= get_callee_fndecl (call
);
2489 if (!callee
|| DECL_BUILT_IN_CLASS (callee
) != BUILT_IN_NORMAL
)
2492 result
= ccp_fold_builtin (*stmtp
, call
);
2494 switch (DECL_FUNCTION_CODE (callee
))
2496 case BUILT_IN_CONSTANT_P
:
2497 /* Resolve __builtin_constant_p. If it hasn't been
2498 folded to integer_one_node by now, it's fairly
2499 certain that the value simply isn't constant. */
2500 result
= integer_zero_node
;
2507 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2509 fprintf (dump_file
, "Simplified\n ");
2510 print_generic_stmt (dump_file
, *stmtp
, dump_flags
);
2513 set_rhs (stmtp
, result
);
2514 modify_stmt (*stmtp
);
2516 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2518 fprintf (dump_file
, "to\n ");
2519 print_generic_stmt (dump_file
, *stmtp
, dump_flags
);
2520 fprintf (dump_file
, "\n");
2526 struct tree_opt_pass pass_fold_builtins
=
2530 execute_fold_all_builtins
, /* execute */
2533 0, /* static_pass_number */
2535 PROP_cfg
| PROP_ssa
, /* properties_required */
2536 0, /* properties_provided */
2537 0, /* properties_destroyed */
2538 0, /* todo_flags_start */
2539 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */
2543 #include "gt-tree-ssa-ccp.h"