1 /* Header file for the value range relational processing.
2 Copyright (C) 2020-2022 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #ifndef GCC_VALUE_RELATION_H
22 #define GCC_VALUE_RELATION_H
25 // This file provides access to a relation oracle which can be used to
26 // maintain and query relations and equivalences between SSA_NAMES.
28 // The general range_query object provided in value-query.h provides
29 // access to an oracle, if one is available, via the oracle() method.
30 // Thre are also a couple of access routines provided, which even if there is
31 // no oracle, will return the default VREL_VARYING no relation.
33 // Typically, when a ranger object is active, there will be an oracle, and
34 // any information available can be directly queried. Ranger also sets and
35 // utilizes the relation information to enhance it's range calculations, this
36 // is totally transparent to the client, and they are free to make queries.
38 // relation_kind is a new enum which represents the different relations,
39 // often with a direct mapping to treee codes. ie VREL_EQ is equivalent to
42 // A query is made requesting the relation between SSA1 and SSA@ in a basic
43 // block, or on an edge, the possible return values are:
45 // VREL_EQ, VREL_NE, VREL_LT, VREL_LE, VREL_GT, and VREL_GE mean the same.
46 // VREL_VARYING : No relation between the 2 names.
47 // VREL_UNDEFINED : Impossible relation (ie, A < B && A > B)
49 // The oracle maintains VREL_EQ relations with equivalency sets, so if a
50 // relation comes back VREL_EQ, it is also possible to query the set of
51 // equivlaencies. These are basically bitmaps over ssa_names. An iterator is
52 // provided later for this activity.
54 // Relations are maintained via the dominace trees and are optimized assuming
55 // they are registered in dominance order. When a new relation is added, it
56 // is intersected with whatever existing relation exists in the dominance tree
57 // and registered at the specified block.
60 // These codes are arranged such that VREL_VARYING is the first code, and all
61 // the rest are contiguous.
63 typedef enum relation_kind_t
65 VREL_VARYING
= 0, // No known relation, AKA varying.
66 VREL_UNDEFINED
, // Impossible relation, ie (r1 < r2) && (r2 > r1)
73 VREL_PE8
, // 8 bit partial equivalency
74 VREL_PE16
, // 16 bit partial equivalency
75 VREL_PE32
, // 32 bit partial equivalency
76 VREL_PE64
, // 64 bit partial equivalency
77 VREL_LAST
// terminate, not a real relation.
80 // General relation kind transformations.
81 relation_kind
relation_union (relation_kind r1
, relation_kind r2
);
82 relation_kind
relation_intersect (relation_kind r1
, relation_kind r2
);
83 relation_kind
relation_negate (relation_kind r
);
84 relation_kind
relation_swap (relation_kind r
);
85 inline bool relation_lt_le_gt_ge_p (relation_kind r
)
86 { return (r
>= VREL_LT
&& r
<= VREL_GE
); }
87 inline bool relation_partial_equiv_p (relation_kind r
)
88 { return (r
>= VREL_PE8
&& r
<= VREL_PE64
); }
89 inline bool relation_equiv_p (relation_kind r
)
90 { return r
== VREL_EQ
|| relation_partial_equiv_p (r
); }
92 void print_relation (FILE *f
, relation_kind rel
);
97 virtual ~relation_oracle () { }
98 // register a relation between 2 ssa names at a stmt.
99 void register_stmt (gimple
*, relation_kind
, tree
, tree
);
100 // register a relation between 2 ssa names on an edge.
101 void register_edge (edge
, relation_kind
, tree
, tree
);
103 // register a relation between 2 ssa names in a basic block.
104 virtual void register_relation (basic_block
, relation_kind
, tree
, tree
) = 0;
105 // Query for a relation between two ssa names in a basic block.
106 virtual relation_kind
query_relation (basic_block
, tree
, tree
) = 0;
108 relation_kind
validate_relation (relation_kind
, tree
, tree
);
109 relation_kind
validate_relation (relation_kind
, vrange
&, vrange
&);
111 virtual void dump (FILE *, basic_block
) const = 0;
112 virtual void dump (FILE *) const = 0;
115 friend class equiv_relation_iterator
;
116 // Return equivalency set for an SSA name in a basic block.
117 virtual const_bitmap
equiv_set (tree
, basic_block
) = 0;
118 // Return partial equivalency record for an SSA name.
119 virtual const class pe_slice
*partial_equiv_set (tree
) { return NULL
; }
120 void valid_equivs (bitmap b
, const_bitmap equivs
, basic_block bb
);
121 // Query for a relation between two equivalency sets in a basic block.
122 virtual relation_kind
query_relation (basic_block
, const_bitmap
,
124 friend class path_oracle
;
127 // This class represents an equivalency set, and contains a link to the next
128 // one in the list to be searched.
133 bitmap m_names
; // ssa-names in equiv set.
134 basic_block m_bb
; // Block this belongs to
135 equiv_chain
*m_next
; // Next in block list.
136 void dump (FILE *f
) const; // Show names in this list.
137 equiv_chain
*find (unsigned ssa
);
143 tree ssa_base
; // Slice of this name.
144 relation_kind code
; // bits that are equivalent.
145 bitmap members
; // Other members in the partial equivalency.
148 // The equivalency oracle maintains equivalencies using the dominator tree.
149 // Equivalencies apply to an entire basic block. Equivalencies on edges
150 // can be represented only on edges whose destination is a single-pred block,
151 // and the equivalence is simply applied to that succesor block.
153 class equiv_oracle
: public relation_oracle
159 const_bitmap
equiv_set (tree ssa
, basic_block bb
) final override
;
160 const pe_slice
*partial_equiv_set (tree name
) final override
;
161 void register_relation (basic_block bb
, relation_kind k
, tree ssa1
,
164 void add_partial_equiv (relation_kind
, tree
, tree
);
165 relation_kind
partial_equiv (tree ssa1
, tree ssa2
, tree
*base
= NULL
) const;
166 relation_kind
query_relation (basic_block
, tree
, tree
) override
;
167 relation_kind
query_relation (basic_block
, const_bitmap
, const_bitmap
)
169 void dump (FILE *f
, basic_block bb
) const override
;
170 void dump (FILE *f
) const override
;
173 bitmap_obstack m_bitmaps
;
174 struct obstack m_chain_obstack
;
176 bitmap m_equiv_set
; // Index by ssa-name. true if an equivalence exists.
177 vec
<equiv_chain
*> m_equiv
; // Index by BB. list of equivalences.
178 vec
<bitmap
> m_self_equiv
; // Index by ssa-name, self equivalency set.
179 vec
<pe_slice
> m_partial
; // Partial equivalencies.
181 void limit_check (basic_block bb
= NULL
);
182 equiv_chain
*find_equiv_block (unsigned ssa
, int bb
) const;
183 equiv_chain
*find_equiv_dom (tree name
, basic_block bb
) const;
185 bitmap
register_equiv (basic_block bb
, unsigned v
, equiv_chain
*equiv_1
);
186 bitmap
register_equiv (basic_block bb
, equiv_chain
*equiv_1
,
187 equiv_chain
*equiv_2
);
188 void register_initial_def (tree ssa
);
189 void add_equiv_to_block (basic_block bb
, bitmap equiv
);
192 // Summary block header for relations.
194 class relation_chain_head
197 bitmap m_names
; // ssa_names with relations in this block.
198 class relation_chain
*m_head
; // List of relations in block.
199 int m_num_relations
; // Number of relations in block.
200 relation_kind
find_relation (const_bitmap b1
, const_bitmap b2
) const;
203 // A relation oracle maintains a set of relations between ssa_names using the
204 // dominator tree structures. Equivalencies are considered a subset of
205 // a general relation and maintained by an equivalence oracle by transparently
206 // passing any EQ_EXPR relations to it.
207 // Relations are handled at the basic block level. All relations apply to
208 // an entire block, and are thus kept in a summary index by block.
209 // Similar to the equivalence oracle, edges are handled by applying the
210 // relation to the destination block of the edge, but ONLY if that block
211 // has a single successor. For now.
213 class dom_oracle
: public equiv_oracle
219 void register_relation (basic_block bb
, relation_kind k
, tree op1
, tree op2
)
222 relation_kind
query_relation (basic_block bb
, tree ssa1
, tree ssa2
)
224 relation_kind
query_relation (basic_block bb
, const_bitmap b1
,
225 const_bitmap b2
) final override
;
227 void dump (FILE *f
, basic_block bb
) const final override
;
228 void dump (FILE *f
) const final override
;
230 bitmap m_tmp
, m_tmp2
;
231 bitmap m_relation_set
; // Index by ssa-name. True if a relation exists
232 vec
<relation_chain_head
> m_relations
; // Index by BB, list of relations.
233 relation_kind
find_relation_block (unsigned bb
, const_bitmap b1
,
234 const_bitmap b2
) const;
235 relation_kind
find_relation_block (int bb
, unsigned v1
, unsigned v2
,
236 relation_chain
**obj
= NULL
) const;
237 relation_kind
find_relation_dom (basic_block bb
, unsigned v1
, unsigned v2
) const;
238 relation_chain
*set_one_relation (basic_block bb
, relation_kind k
, tree op1
,
240 void register_transitives (basic_block
, const class value_relation
&);
244 // A path_oracle implements relations in a list. The only sense of ordering
245 // is the latest registered relation is the first found during a search.
246 // It can be constructed with an optional "root" oracle which will be used
247 // to look up any relations not found in the list.
248 // This allows the client to walk paths starting at some block and register
249 // and query relations along that path, ignoring other edges.
251 // For registering a relation, a query if made of the root oracle if there is
252 // any known relationship at block BB, and it is combined with this new
253 // relation and entered in the list.
255 // Queries are resolved by looking first in the list, and only if nothing is
256 // found is the root oracle queried at block BB.
258 // reset_path is used to clear all locally registered paths to initial state.
260 class path_oracle
: public relation_oracle
263 path_oracle (relation_oracle
*oracle
= NULL
);
265 const_bitmap
equiv_set (tree
, basic_block
) final override
;
266 void register_relation (basic_block
, relation_kind
, tree
, tree
) final override
;
267 void killing_def (tree
);
268 relation_kind
query_relation (basic_block
, tree
, tree
) final override
;
269 relation_kind
query_relation (basic_block
, const_bitmap
, const_bitmap
)
271 void reset_path (relation_oracle
*oracle
= NULL
);
272 void set_root_oracle (relation_oracle
*oracle
) { m_root
= oracle
; }
273 void dump (FILE *, basic_block
) const final override
;
274 void dump (FILE *) const final override
;
276 void register_equiv (basic_block bb
, tree ssa1
, tree ssa2
);
278 relation_chain_head m_relations
;
279 relation_oracle
*m_root
;
280 bitmap m_killed_defs
;
282 bitmap_obstack m_bitmaps
;
283 struct obstack m_chain_obstack
;
286 // Used to assist with iterating over the equivalence list.
287 class equiv_relation_iterator
{
289 equiv_relation_iterator (relation_oracle
*oracle
, basic_block bb
, tree name
,
290 bool full
= true, bool partial
= false);
292 tree
get_name (relation_kind
*rel
= NULL
);
294 relation_oracle
*m_oracle
;
296 const pe_slice
*m_pe
;
297 bitmap_iterator m_bi
;
302 #define FOR_EACH_EQUIVALENCE(oracle, bb, name, equiv_name) \
303 for (equiv_relation_iterator iter (oracle, bb, name, true, false); \
304 ((equiv_name) = iter.get_name ()); \
307 #define FOR_EACH_PARTIAL_EQUIV(oracle, bb, name, equiv_name, equiv_rel) \
308 for (equiv_relation_iterator iter (oracle, bb, name, false, true); \
309 ((equiv_name) = iter.get_name (&equiv_rel)); \
312 #define FOR_EACH_PARTIAL_AND_FULL_EQUIV(oracle, bb, name, equiv_name, \
314 for (equiv_relation_iterator iter (oracle, bb, name, true, true); \
315 ((equiv_name) = iter.get_name (&equiv_rel)); \
318 // -----------------------------------------------------------------------
320 // Range-ops deals with a LHS and 2 operands. A relation trio is a set of
321 // 3 potential relations packed into a single unsigned value.
322 // 1 - LHS relation OP1
323 // 2 - LHS relation OP2
324 // 3 - OP1 relation OP2
325 // VREL_VARYING is a value of 0, and is the default for each position.
330 relation_trio (relation_kind lhs_op1
, relation_kind lhs_op2
,
331 relation_kind op1_op2
);
332 relation_kind
lhs_op1 ();
333 relation_kind
lhs_op2 ();
334 relation_kind
op1_op2 ();
335 relation_trio
swap_op1_op2 ();
337 static relation_trio
lhs_op1 (relation_kind k
);
338 static relation_trio
lhs_op2 (relation_kind k
);
339 static relation_trio
op1_op2 (relation_kind k
);
345 // Default VREL_VARYING for all 3 relations.
346 #define TRIO_VARYING relation_trio ()
349 #define TRIO_MASK 0x000F
351 // These 3 classes are shortcuts for when a caller has a single relation to
352 // pass as a trio, it can simply construct the appropriate one. The other
353 // unspecified realtions will be VREL_VARYING.
355 inline relation_trio::relation_trio ()
357 STATIC_ASSERT (VREL_LAST
<= (1 << TRIO_SHIFT
));
361 inline relation_trio::relation_trio (relation_kind lhs_op1
,
362 relation_kind lhs_op2
,
363 relation_kind op1_op2
)
365 STATIC_ASSERT (VREL_LAST
<= (1 << TRIO_SHIFT
));
366 unsigned i1
= (unsigned) lhs_op1
;
367 unsigned i2
= ((unsigned) lhs_op2
) << TRIO_SHIFT
;
368 unsigned i3
= ((unsigned) op1_op2
) << (TRIO_SHIFT
* 2);
369 m_val
= i1
| i2
| i3
;
373 relation_trio::lhs_op1 (relation_kind k
)
375 return relation_trio (k
, VREL_VARYING
, VREL_VARYING
);
378 relation_trio::lhs_op2 (relation_kind k
)
380 return relation_trio (VREL_VARYING
, k
, VREL_VARYING
);
383 relation_trio::op1_op2 (relation_kind k
)
385 return relation_trio (VREL_VARYING
, VREL_VARYING
, k
);
389 relation_trio::lhs_op1 ()
391 return (relation_kind
) (m_val
& TRIO_MASK
);
395 relation_trio::lhs_op2 ()
397 return (relation_kind
) ((m_val
>> TRIO_SHIFT
) & TRIO_MASK
);
401 relation_trio::op1_op2 ()
403 return (relation_kind
) ((m_val
>> (TRIO_SHIFT
* 2)) & TRIO_MASK
);
407 relation_trio::swap_op1_op2 ()
409 return relation_trio (lhs_op2 (), lhs_op1 (), relation_swap (op1_op2 ()));
412 // -----------------------------------------------------------------------
414 // The value-relation class is used to encapsulate the represention of an
415 // individual relation between 2 ssa-names, and to facilitate operating on
422 value_relation (relation_kind kind
, tree n1
, tree n2
);
423 void set_relation (relation_kind kind
, tree n1
, tree n2
);
425 inline relation_kind
kind () const { return related
; }
426 inline tree
op1 () const { return name1
; }
427 inline tree
op2 () const { return name2
; }
429 bool union_ (value_relation
&p
);
430 bool intersect (value_relation
&p
);
432 bool apply_transitive (const value_relation
&rel
);
434 void dump (FILE *f
) const;
436 relation_kind related
;
440 // Set relation R between ssa_name N1 and N2.
443 value_relation::set_relation (relation_kind r
, tree n1
, tree n2
)
445 gcc_checking_assert (TREE_CODE (n1
) == SSA_NAME
446 && TREE_CODE (n2
) == SSA_NAME
);
449 related
= VREL_VARYING
;
459 // Default constructor.
462 value_relation::value_relation ()
464 related
= VREL_VARYING
;
469 // Constructor for relation R between SSA version N1 nd N2.
472 value_relation::value_relation (relation_kind kind
, tree n1
, tree n2
)
474 set_relation (kind
, n1
, n2
);
477 // Return the number of bits associated with partial equivalency T.
478 // Return 0 if this is not a supported partial equivalency relation.
481 pe_to_bits (relation_kind t
)
498 // Return the partial equivalency code associated with the number of BITS.
499 // return VREL_VARYING if there is no exact match.
502 bits_to_pe (int bits
)
519 // Given partial equivalencies T1 and T2, return the snmallest kind.
522 pe_min (relation_kind t1
, relation_kind t2
)
524 gcc_checking_assert (relation_partial_equiv_p (t1
));
525 gcc_checking_assert (relation_partial_equiv_p (t2
));
526 // VREL_PE are declared small to large, so simple min will suffice.
529 #endif /* GCC_VALUE_RELATION_H */