tree-ssa-propagate.h revision 259065
1178786Skmacy/* Data structures and function declarations for the SSA value propagation 2178786Skmacy engine. 3178786Skmacy Copyright (C) 2004, 2005 Free Software Foundation, Inc. 4178786Skmacy Contributed by Diego Novillo <dnovillo@redhat.com> 5178786Skmacy 6178786SkmacyThis file is part of GCC. 7178786Skmacy 8178786SkmacyGCC is free software; you can redistribute it and/or modify 9178786Skmacyit under the terms of the GNU General Public License as published by 10178786Skmacythe Free Software Foundation; either version 2, or (at your option) 11178786Skmacyany later version. 12178786Skmacy 13178786SkmacyGCC is distributed in the hope that it will be useful, 14178786Skmacybut WITHOUT ANY WARRANTY; without even the implied warranty of 15178786SkmacyMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16178786SkmacyGNU General Public License for more details. 17178786Skmacy 18178786SkmacyYou should have received a copy of the GNU General Public License 19178786Skmacyalong with GCC; see the file COPYING. If not, write to 20178786Skmacythe Free Software Foundation, 51 Franklin Street, Fifth Floor, 21178786SkmacyBoston, MA 02110-1301, USA. */ 22178786Skmacy 23178786Skmacy#ifndef _TREE_SSA_PROPAGATE_H 24178786Skmacy#define _TREE_SSA_PROPAGATE_H 1 25178786Skmacy 26178786Skmacy/* Use the TREE_VISITED bitflag to mark statements and PHI nodes that 27178786Skmacy have been deemed varying and should not be simulated again. */ 28178786Skmacy#define DONT_SIMULATE_AGAIN(T) TREE_VISITED (T) 29178786Skmacy 30178786Skmacy/* Lattice values used for propagation purposes. Specific instances 31178786Skmacy of a propagation engine must return these values from the statement 32237263Snp and PHI visit functions to direct the engine. */ 33237263Snpenum ssa_prop_result { 34237263Snp /* The statement produces nothing of interest. No edges will be 35178786Skmacy added to the work lists. */ 36178786Skmacy SSA_PROP_NOT_INTERESTING, 37178786Skmacy 38178786Skmacy /* The statement produces an interesting value. The set SSA_NAMEs 39178786Skmacy returned by SSA_PROP_VISIT_STMT should be added to 40178786Skmacy INTERESTING_SSA_EDGES. If the statement being visited is a 41178786Skmacy conditional jump, SSA_PROP_VISIT_STMT should indicate which edge 42178786Skmacy out of the basic block should be marked executable. */ 43178786Skmacy SSA_PROP_INTERESTING, 44178786Skmacy 45178786Skmacy /* The statement produces a varying (i.e., useless) value and 46178786Skmacy should not be simulated again. If the statement being visited 47178786Skmacy is a conditional jump, all the edges coming out of the block 48178786Skmacy will be considered executable. */ 49178786Skmacy SSA_PROP_VARYING 50178786Skmacy}; 51178786Skmacy 52178786Skmacy 53178786Skmacystruct prop_value_d { 54178786Skmacy /* Lattice value. Each propagator is free to define its own 55178786Skmacy lattice and this field is only meaningful while propagating. 56178786Skmacy It will not be used by substitute_and_fold. */ 57178786Skmacy unsigned lattice_val; 58178786Skmacy 59178786Skmacy /* Propagated value. */ 60178786Skmacy tree value; 61178786Skmacy 62178786Skmacy /* If this value is held in an SSA name for a non-register 63178786Skmacy variable, this field holds the actual memory reference 64178786Skmacy associated with this value. This field is taken from 65178786Skmacy the LHS of the assignment that generated the associated SSA 66178786Skmacy name. However, in the case of PHI nodes, this field is copied 67178786Skmacy from the PHI arguments (assuming that all the arguments have 68178786Skmacy the same memory reference). See replace_vuses_in for a more 69178786Skmacy detailed description. */ 70178786Skmacy tree mem_ref; 71237263Snp}; 72237263Snp 73237263Snptypedef struct prop_value_d prop_value_t; 74178786Skmacy 75178786Skmacy 76178786Skmacy/* Type of value ranges. See value_range_d for a description of these 77178786Skmacy types. */ 78237263Snpenum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING }; 79237263Snp 80237263Snp/* Range of values that can be associated with an SSA_NAME after VRP 81237263Snp has executed. */ 82178786Skmacystruct value_range_d 83178786Skmacy{ 84178786Skmacy /* Lattice value represented by this range. */ 85178786Skmacy enum value_range_type type; 86178786Skmacy 87178786Skmacy /* Minimum and maximum values represented by this range. These 88178786Skmacy values should be interpreted as follows: 89178786Skmacy 90178786Skmacy - If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must 91178786Skmacy be NULL. 92178786Skmacy 93178786Skmacy - If TYPE == VR_RANGE then MIN holds the minimum value and 94178786Skmacy MAX holds the maximum value of the range [MIN, MAX]. 95178786Skmacy 96178786Skmacy - If TYPE == ANTI_RANGE the variable is known to NOT 97178786Skmacy take any values in the range [MIN, MAX]. */ 98178786Skmacy tree min; 99178786Skmacy tree max; 100178786Skmacy 101178786Skmacy /* Set of SSA names whose value ranges are equivalent to this one. 102178786Skmacy This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ 103178786Skmacy bitmap equiv; 104178786Skmacy}; 105178786Skmacy 106237263Snptypedef struct value_range_d value_range_t; 107178786Skmacy 108237263Snp 109178786Skmacy/* Call-back functions used by the value propagation engine. */ 110237263Snptypedef enum ssa_prop_result (*ssa_prop_visit_stmt_fn) (tree, edge *, tree *); 111237263Snptypedef enum ssa_prop_result (*ssa_prop_visit_phi_fn) (tree); 112178786Skmacy 113178786Skmacy 114178786Skmacy/* In tree-ssa-propagate.c */ 115237263Snpvoid ssa_propagate (ssa_prop_visit_stmt_fn, ssa_prop_visit_phi_fn); 116178786Skmacytree get_rhs (tree); 117178786Skmacybool set_rhs (tree *, tree); 118178786Skmacytree first_vdef (tree); 119178786Skmacybool stmt_makes_single_load (tree); 120237263Snpbool stmt_makes_single_store (tree); 121178786Skmacyprop_value_t *get_value_loaded_by (tree, prop_value_t *); 122178786Skmacybool replace_uses_in (tree, bool *, prop_value_t *); 123178786Skmacyvoid substitute_and_fold (prop_value_t *, bool); 124178786Skmacy 125237263Snp#endif /* _TREE_SSA_PROPAGATE_H */ 126178786Skmacy