2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Memory disambiguator
12 #ifndef FIRM_ANA_IRMEMORY_H
13 #define FIRM_ANA_IRMEMORY_H
15 #include "firm_types.h"
19 * @defgroup ir_memory Memory Disambiguator
21 * A memory disambiguator checks whether 2 given SSA values representing
27 /** The alias relation of two memory addresses. */
28 typedef enum ir_alias_relation {
29 ir_no_alias, /**< No alias. */
30 ir_may_alias, /**< Unknown state, may alias. */
31 ir_sure_alias /**< Sure alias. */
34 /** The state of the entity usage flags. */
35 typedef enum ir_entity_usage_computed_state {
36 ir_entity_usage_not_computed,
37 ir_entity_usage_computed
38 } ir_entity_usage_computed_state;
40 /** Possible options for the memory disambiguator. */
41 typedef enum ir_disambuigator_options {
42 aa_opt_no_opt = 0, /**< no options: most conservative */
43 aa_opt_type_based = 1, /**< use type based alias analysis: strict typed source language */
44 aa_opt_byte_type_may_alias = 2, /**< if type based analysis is enabled: bytes types may alias other types */
45 aa_opt_no_alias_args = 4, /**< arguments do not alias each other but may alias global storage */
46 aa_opt_no_alias_args_global = 8, /**< arguments do not alias global storage */
47 aa_opt_no_alias = 16, /**< two addresses NEVER alias, use with CAUTION (gcc -fno-alias) */
48 aa_opt_inherited = 128 /**< only for implementation: options from a graph are inherited from global */
49 } ir_disambuigator_options;
50 ENUM_BITSET(ir_disambuigator_options)
53 * Classify storage locations.
54 * Except ir_sc_pointer they are all disjoint.
55 * ir_sc_pointer potentially aliases all classes which don't have a
58 typedef enum ir_storage_class_class_t {
59 ir_sc_pointer = 0x0, /**< generic pointer, may be anything */
60 ir_sc_globalvar = 0x1, /**< an address of a global variable */
61 ir_sc_localvar = 0x2, /**< an address of a local variable or method argument */
62 ir_sc_tls = 0x3, /**< an address of a thread local storage variable */
63 ir_sc_malloced = 0x4, /**< an allocated heap address */
64 ir_sc_globaladdr = 0x5, /**< a constant address of something */
66 ir_sc_modifier_nottaken = 0x80, /**< if set, the address of the variable was not taken */
67 ir_sc_modifier_argument = 0x40, /**< if set pointer was a function argument */
68 ir_sc_modifiers = ir_sc_modifier_nottaken | ir_sc_modifier_argument
69 } ir_storage_class_class_t;
70 ENUM_BITSET(ir_storage_class_class_t)
72 /** Returns the base storage class (ignore modifier) */
73 FIRM_API ir_storage_class_class_t get_base_sc(ir_storage_class_class_t x);
76 * A source language specific memory disambiguator function.
77 * Called by get_alias_relation().
79 typedef ir_alias_relation (*DISAMBIGUATOR_FUNC)(
80 const ir_node *adr1, const ir_mode *mode1,
81 const ir_node *adr2, const ir_mode *mode2);
84 * Classify a base pointer.
86 * @param irn the node representing the base address
87 * @param ent the base entity of the base address iff any
89 FIRM_API ir_storage_class_class_t classify_pointer(const ir_node *irn,
90 const ir_entity *ent);
93 * Returns a human readable name for an alias relation.
95 FIRM_API const char *get_ir_alias_relation_name(ir_alias_relation rel);
98 * Determine the alias relation between two addresses.
100 * @param adr1 The first address.
101 * @param mode1 The mode of the first memory access.
102 * @param adr2 The second address.
103 * @param mode2 The mode of the second memory access.
105 * The memory disambiguator tries to determine the alias state between
106 * two memory addresses. The following rules are used:
108 * - different variable from the same segment never alias (R1 a)
109 * - variables from different segments never alias when:
110 * - a global variable and a local one never alias (R1 b)
111 * - a global variable and a TLS one never alias (R1 c)
112 * - a local variable and a TLS one never alias (R1 d)
113 * - a local variable and a parameter never alias (R1 e)
114 * - a global variable and the result of a malloc routine never alias (R1 f)
115 * - a local variable and the result of a malloc routine never alias (R1 g)
116 * - a TLS variable and the result of a malloc routine never alias (R1 h)
117 * - a parameter and the result of a malloc routine (obtained in the
118 * same routine as the parameter) never alias (R1 i)
119 * - two different variables never alias (R2)
120 * - if one is a variable whose address has never been taken
121 * there is no alias (R3)
122 * - if two memory addresses have the same base and their offsets
123 * do not describe overlapping regions there is no alias (R4)
124 * - if opt_strong_typed is set and both addresses describe entities,
125 * different types never alias (R5)
127 * If none of these rules apply, the points-to framework must be
128 * interrogated to detect the alias relation.
130 FIRM_API ir_alias_relation get_alias_relation(
131 const ir_node *adr1, const ir_mode *mode1,
132 const ir_node *adr2, const ir_mode *mode2);
135 * Sets a source language specific memory disambiguator function.
137 * @param func The callback.
139 FIRM_API void set_language_memory_disambiguator(DISAMBIGUATOR_FUNC func);
142 * Initialize the relation cache.
144 FIRM_API void mem_disambig_init(void);
147 * Determine the alias relation between two addresses and
150 * @param adr1 The first address.
151 * @param mode1 The mode of the first memory access.
152 * @param adr2 The second address.
153 * @param mode2 The mode of the second memory access.
155 * @see get_alias_relation()
157 FIRM_API ir_alias_relation get_alias_relation_ex(
158 const ir_node *adr1, const ir_mode *mode1,
159 const ir_node *adr2, const ir_mode *mode2);
162 * Free the relation cache.
164 FIRM_API void mem_disambig_term(void);
167 * Assure that the entity usage flags have been computed for the given graph.
169 * This analysis computes the entity usage state for all local variables.
171 * Even then the information is not cleaned from the variables, call
172 * assure_irg_entity_usage_computed() again for recomputation.
174 FIRM_API void assure_irg_entity_usage_computed(ir_graph *irg);
177 * Returns the current address taken state of the globals.
179 FIRM_API ir_entity_usage_computed_state get_irp_globals_entity_usage_state(void);
182 * Sets the current address taken state of the globals.
184 * @param state the new state
186 FIRM_API void set_irp_globals_entity_usage_state(ir_entity_usage_computed_state state);
189 * Assure that the address taken flag is computed for the global and TLS entities (variables).
191 * This is an interprocedural analysis that computes the address_taken state
192 * for all global and TLS variables.
194 * Note that this is a conservative estimation that by no Firm transformation
195 * can be invalidated, so it's only recomputed if manually triggered by calling
196 * set_irp_globals_entity_usage_state(ir_entity_usage_not_computed).
197 * Even then the information is not cleaned from the variables, call
198 * assure_irp_globals_entity_usage_computed() again for recomputation.
200 FIRM_API void assure_irp_globals_entity_usage_computed(void);
203 * Returns the memory disambiguator options for a graph.
205 * @param irg the graph
207 FIRM_API unsigned get_irg_memory_disambiguator_options(const ir_graph *irg);
210 * Sets the memory disambiguator options for a graph.
212 * @param irg the graph
213 * @param options a set of options
215 FIRM_API void set_irg_memory_disambiguator_options(ir_graph *irg,
219 * Sets the global disambiguator options for all graphs not having local
222 * @param options a set of options
224 FIRM_API void set_irp_memory_disambiguator_options(unsigned options);
227 * Mark all private methods, i.e. those of which all call sites are known.
228 * We use a very convervative estimation yet: If the address of a method is
229 * never taken AND its visibility is visibility_local, then it's private.
231 FIRM_API void mark_private_methods(void);
234 * Creates an ir_prog pass for mark_private_methods().
236 * @param name the name of this pass or NULL
238 * @return the newly created ir_prog pass
240 FIRM_API ir_prog_pass_t *mark_private_methods_pass(const char *name);