1/* Header file for the value range relational processing.
2 Copyright (C) 2020-2023 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#ifndef GCC_VALUE_RELATION_H
22#define GCC_VALUE_RELATION_H
23
24
25// This file provides access to a relation oracle which can be used to
26// maintain and query relations and equivalences between SSA_NAMES.
27//
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// There are also a couple of access routines provided, which even if there is
31// no oracle, will return the default VREL_VARYING no relation.
32//
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.
37//
38// relation_kind is a new enum which represents the different relations,
39// often with a direct mapping to tree codes. ie VREL_EQ is equivalent to
40// EQ_EXPR.
41//
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:
44//
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)
48//
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// equivalencies. These are basically bitmaps over ssa_names. An iterator is
52// provided later for this activity.
53//
54// Relations are maintained via the dominance 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.
58
59
60// These codes are arranged such that VREL_VARYING is the first code, and all
61// the rest are contiguous.
62
63typedef enum relation_kind_t
64{
65 VREL_VARYING = 0, // No known relation, AKA varying.
66 VREL_UNDEFINED, // Impossible relation, ie (r1 < r2) && (r2 > r1)
67 VREL_LT, // r1 < r2
68 VREL_LE, // r1 <= r2
69 VREL_GT, // r1 > r2
70 VREL_GE, // r1 >= r2
71 VREL_EQ, // r1 == r2
72 VREL_NE, // r1 != r2
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.
78} relation_kind;
79
80// General relation kind transformations.
81relation_kind relation_union (relation_kind r1, relation_kind r2);
82relation_kind relation_intersect (relation_kind r1, relation_kind r2);
83relation_kind relation_negate (relation_kind r);
84relation_kind relation_swap (relation_kind r);
85inline bool relation_lt_le_gt_ge_p (relation_kind r)
86 { return (r >= VREL_LT && r <= VREL_GE); }
87inline bool relation_partial_equiv_p (relation_kind r)
88 { return (r >= VREL_PE8 && r <= VREL_PE64); }
89inline bool relation_equiv_p (relation_kind r)
90 { return r == VREL_EQ || relation_partial_equiv_p (r); }
91
92void print_relation (FILE *f, relation_kind rel);
93
94// Adjust range as an equivalence.
95void adjust_equivalence_range (vrange &range);
96
97class relation_oracle
98{
99public:
100 virtual ~relation_oracle () { }
101 // register a relation between 2 ssa names at a stmt.
102 void register_stmt (gimple *, relation_kind, tree, tree);
103 // register a relation between 2 ssa names on an edge.
104 void register_edge (edge, relation_kind, tree, tree);
105
106 // register a relation between 2 ssa names in a basic block.
107 virtual void register_relation (basic_block, relation_kind, tree, tree) = 0;
108 // Query for a relation between two ssa names in a basic block.
109 virtual relation_kind query_relation (basic_block, tree, tree) = 0;
110
111 relation_kind validate_relation (relation_kind, tree, tree);
112 relation_kind validate_relation (relation_kind, vrange &, vrange &);
113
114 virtual void dump (FILE *, basic_block) const = 0;
115 virtual void dump (FILE *) const = 0;
116 void debug () const;
117protected:
118 friend class equiv_relation_iterator;
119 // Return equivalency set for an SSA name in a basic block.
120 virtual const_bitmap equiv_set (tree, basic_block) = 0;
121 // Return partial equivalency record for an SSA name.
122 virtual const class pe_slice *partial_equiv_set (tree) { return NULL; }
123 void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb);
124 // Query for a relation between two equivalency sets in a basic block.
125 virtual relation_kind query_relation (basic_block, const_bitmap,
126 const_bitmap) = 0;
127 friend class path_oracle;
128};
129
130// This class represents an equivalency set, and contains a link to the next
131// one in the list to be searched.
132
133class equiv_chain
134{
135public:
136 bitmap m_names; // ssa-names in equiv set.
137 basic_block m_bb; // Block this belongs to
138 equiv_chain *m_next; // Next in block list.
139 void dump (FILE *f) const; // Show names in this list.
140 equiv_chain *find (unsigned ssa);
141};
142
143class pe_slice
144{
145public:
146 tree ssa_base; // Slice of this name.
147 relation_kind code; // bits that are equivalent.
148 bitmap members; // Other members in the partial equivalency.
149};
150
151// The equivalency oracle maintains equivalencies using the dominator tree.
152// Equivalencies apply to an entire basic block. Equivalencies on edges
153// can be represented only on edges whose destination is a single-pred block,
154// and the equivalence is simply applied to that successor block.
155
156class equiv_oracle : public relation_oracle
157{
158public:
159 equiv_oracle ();
160 ~equiv_oracle ();
161
162 const_bitmap equiv_set (tree ssa, basic_block bb) final override;
163 const pe_slice *partial_equiv_set (tree name) final override;
164 void register_relation (basic_block bb, relation_kind k, tree ssa1,
165 tree ssa2) override;
166
167 void add_partial_equiv (relation_kind, tree, tree);
168 relation_kind partial_equiv (tree ssa1, tree ssa2, tree *base = NULL) const;
169 relation_kind query_relation (basic_block, tree, tree) override;
170 relation_kind query_relation (basic_block, const_bitmap, const_bitmap)
171 override;
172 void dump (FILE *f, basic_block bb) const override;
173 void dump (FILE *f) const override;
174
175protected:
176 inline bool has_equiv_p (unsigned v) { return bitmap_bit_p (m_equiv_set, v); }
177 bitmap_obstack m_bitmaps;
178 struct obstack m_chain_obstack;
179private:
180 bitmap m_equiv_set; // Index by ssa-name. true if an equivalence exists.
181 vec <equiv_chain *> m_equiv; // Index by BB. list of equivalences.
182 vec <bitmap> m_self_equiv; // Index by ssa-name, self equivalency set.
183 vec <pe_slice> m_partial; // Partial equivalencies.
184
185 void limit_check (basic_block bb = NULL);
186 equiv_chain *find_equiv_block (unsigned ssa, int bb) const;
187 equiv_chain *find_equiv_dom (tree name, basic_block bb) const;
188
189 bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1);
190 bitmap register_equiv (basic_block bb, equiv_chain *equiv_1,
191 equiv_chain *equiv_2);
192 void register_initial_def (tree ssa);
193 void add_equiv_to_block (basic_block bb, bitmap equiv);
194};
195
196// Summary block header for relations.
197
198class relation_chain_head
199{
200public:
201 bitmap m_names; // ssa_names with relations in this block.
202 class relation_chain *m_head; // List of relations in block.
203 int m_num_relations; // Number of relations in block.
204 relation_kind find_relation (const_bitmap b1, const_bitmap b2) const;
205};
206
207// A relation oracle maintains a set of relations between ssa_names using the
208// dominator tree structures. Equivalencies are considered a subset of
209// a general relation and maintained by an equivalence oracle by transparently
210// passing any EQ_EXPR relations to it.
211// Relations are handled at the basic block level. All relations apply to
212// an entire block, and are thus kept in a summary index by block.
213// Similar to the equivalence oracle, edges are handled by applying the
214// relation to the destination block of the edge, but ONLY if that block
215// has a single successor. For now.
216
217class dom_oracle : public equiv_oracle
218{
219public:
220 dom_oracle ();
221 ~dom_oracle ();
222
223 void register_relation (basic_block bb, relation_kind k, tree op1, tree op2)
224 final override;
225
226 relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2)
227 final override;
228 relation_kind query_relation (basic_block bb, const_bitmap b1,
229 const_bitmap b2) final override;
230
231 void dump (FILE *f, basic_block bb) const final override;
232 void dump (FILE *f) const final override;
233private:
234 bitmap m_tmp, m_tmp2;
235 bitmap m_relation_set; // Index by ssa-name. True if a relation exists
236 vec <relation_chain_head> m_relations; // Index by BB, list of relations.
237 relation_kind find_relation_block (unsigned bb, const_bitmap b1,
238 const_bitmap b2) const;
239 relation_kind find_relation_block (int bb, unsigned v1, unsigned v2,
240 relation_chain **obj = NULL) const;
241 relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const;
242 relation_chain *set_one_relation (basic_block bb, relation_kind k, tree op1,
243 tree op2);
244 void register_transitives (basic_block, const class value_relation &);
245
246};
247
248// A path_oracle implements relations in a list. The only sense of ordering
249// is the latest registered relation is the first found during a search.
250// It can be constructed with an optional "root" oracle which will be used
251// to look up any relations not found in the list.
252// This allows the client to walk paths starting at some block and register
253// and query relations along that path, ignoring other edges.
254//
255// For registering a relation, a query if made of the root oracle if there is
256// any known relationship at block BB, and it is combined with this new
257// relation and entered in the list.
258//
259// Queries are resolved by looking first in the list, and only if nothing is
260// found is the root oracle queried at block BB.
261//
262// reset_path is used to clear all locally registered paths to initial state.
263
264class path_oracle : public relation_oracle
265{
266public:
267 path_oracle (relation_oracle *oracle = NULL);
268 ~path_oracle ();
269 const_bitmap equiv_set (tree, basic_block) final override;
270 void register_relation (basic_block, relation_kind, tree, tree) final override;
271 void killing_def (tree);
272 relation_kind query_relation (basic_block, tree, tree) final override;
273 relation_kind query_relation (basic_block, const_bitmap, const_bitmap)
274 final override;
275 void reset_path (relation_oracle *oracle = NULL);
276 void set_root_oracle (relation_oracle *oracle) { m_root = oracle; }
277 void dump (FILE *, basic_block) const final override;
278 void dump (FILE *) const final override;
279private:
280 void register_equiv (basic_block bb, tree ssa1, tree ssa2);
281 equiv_chain m_equiv;
282 relation_chain_head m_relations;
283 relation_oracle *m_root;
284 bitmap m_killed_defs;
285
286 bitmap_obstack m_bitmaps;
287 struct obstack m_chain_obstack;
288};
289
290// Used to assist with iterating over the equivalence list.
291class equiv_relation_iterator {
292public:
293 equiv_relation_iterator (relation_oracle *oracle, basic_block bb, tree name,
294 bool full = true, bool partial = false);
295 void next ();
296 tree get_name (relation_kind *rel = NULL);
297protected:
298 relation_oracle *m_oracle;
299 const_bitmap m_bm;
300 const pe_slice *m_pe;
301 bitmap_iterator m_bi;
302 unsigned m_y;
303 tree m_name;
304};
305
306#define FOR_EACH_EQUIVALENCE(oracle, bb, name, equiv_name) \
307 for (equiv_relation_iterator iter (oracle, bb, name, true, false); \
308 ((equiv_name) = iter.get_name ()); \
309 iter.next ())
310
311#define FOR_EACH_PARTIAL_EQUIV(oracle, bb, name, equiv_name, equiv_rel) \
312 for (equiv_relation_iterator iter (oracle, bb, name, false, true); \
313 ((equiv_name) = iter.get_name (&equiv_rel)); \
314 iter.next ())
315
316#define FOR_EACH_PARTIAL_AND_FULL_EQUIV(oracle, bb, name, equiv_name, \
317 equiv_rel) \
318 for (equiv_relation_iterator iter (oracle, bb, name, true, true); \
319 ((equiv_name) = iter.get_name (&equiv_rel)); \
320 iter.next ())
321
322// -----------------------------------------------------------------------
323
324// Range-ops deals with a LHS and 2 operands. A relation trio is a set of
325// 3 potential relations packed into a single unsigned value.
326// 1 - LHS relation OP1
327// 2 - LHS relation OP2
328// 3 - OP1 relation OP2
329// VREL_VARYING is a value of 0, and is the default for each position.
330class relation_trio
331{
332public:
333 relation_trio ();
334 relation_trio (relation_kind lhs_op1, relation_kind lhs_op2,
335 relation_kind op1_op2);
336 relation_kind lhs_op1 ();
337 relation_kind lhs_op2 ();
338 relation_kind op1_op2 ();
339 relation_trio swap_op1_op2 ();
340
341 static relation_trio lhs_op1 (relation_kind k);
342 static relation_trio lhs_op2 (relation_kind k);
343 static relation_trio op1_op2 (relation_kind k);
344
345protected:
346 unsigned m_val;
347};
348
349// Default VREL_VARYING for all 3 relations.
350#define TRIO_VARYING relation_trio ()
351
352#define TRIO_SHIFT 4
353#define TRIO_MASK 0x000F
354
355// These 3 classes are shortcuts for when a caller has a single relation to
356// pass as a trio, it can simply construct the appropriate one. The other
357// unspecified relations will be VREL_VARYING.
358
359inline relation_trio::relation_trio ()
360{
361 STATIC_ASSERT (VREL_LAST <= (1 << TRIO_SHIFT));
362 m_val = 0;
363}
364
365inline relation_trio::relation_trio (relation_kind lhs_op1,
366 relation_kind lhs_op2,
367 relation_kind op1_op2)
368{
369 STATIC_ASSERT (VREL_LAST <= (1 << TRIO_SHIFT));
370 unsigned i1 = (unsigned) lhs_op1;
371 unsigned i2 = ((unsigned) lhs_op2) << TRIO_SHIFT;
372 unsigned i3 = ((unsigned) op1_op2) << (TRIO_SHIFT * 2);
373 m_val = i1 | i2 | i3;
374}
375
376inline relation_trio
377relation_trio::lhs_op1 (relation_kind k)
378{
379 return relation_trio (k, VREL_VARYING, VREL_VARYING);
380}
381inline relation_trio
382relation_trio::lhs_op2 (relation_kind k)
383{
384 return relation_trio (VREL_VARYING, k, VREL_VARYING);
385}
386inline relation_trio
387relation_trio::op1_op2 (relation_kind k)
388{
389 return relation_trio (VREL_VARYING, VREL_VARYING, k);
390}
391
392inline relation_kind
393relation_trio::lhs_op1 ()
394{
395 return (relation_kind) (m_val & TRIO_MASK);
396}
397
398inline relation_kind
399relation_trio::lhs_op2 ()
400{
401 return (relation_kind) ((m_val >> TRIO_SHIFT) & TRIO_MASK);
402}
403
404inline relation_kind
405relation_trio::op1_op2 ()
406{
407 return (relation_kind) ((m_val >> (TRIO_SHIFT * 2)) & TRIO_MASK);
408}
409
410inline relation_trio
411relation_trio::swap_op1_op2 ()
412{
413 return relation_trio (lhs_op2 (), lhs_op1 (), relation_swap (r: op1_op2 ()));
414}
415
416// -----------------------------------------------------------------------
417
418// The value-relation class is used to encapsulate the representation of an
419// individual relation between 2 ssa-names, and to facilitate operating on
420// the relation.
421
422class value_relation
423{
424public:
425 value_relation ();
426 value_relation (relation_kind kind, tree n1, tree n2);
427 void set_relation (relation_kind kind, tree n1, tree n2);
428
429 inline relation_kind kind () const { return related; }
430 inline tree op1 () const { return name1; }
431 inline tree op2 () const { return name2; }
432
433 relation_trio create_trio (tree lhs, tree op1, tree op2);
434 bool union_ (value_relation &p);
435 bool intersect (value_relation &p);
436 void negate ();
437 bool apply_transitive (const value_relation &rel);
438
439 void dump (FILE *f) const;
440private:
441 relation_kind related;
442 tree name1, name2;
443};
444
445// Set relation R between ssa_name N1 and N2.
446
447inline void
448value_relation::set_relation (relation_kind r, tree n1, tree n2)
449{
450 gcc_checking_assert (TREE_CODE (n1) == SSA_NAME
451 && TREE_CODE (n2) == SSA_NAME);
452 related = r;
453 name1 = n1;
454 name2 = n2;
455}
456
457// Default constructor.
458
459inline
460value_relation::value_relation ()
461{
462 related = VREL_VARYING;
463 name1 = NULL_TREE;
464 name2 = NULL_TREE;
465}
466
467// Constructor for relation R between SSA version N1 and N2.
468
469inline
470value_relation::value_relation (relation_kind kind, tree n1, tree n2)
471{
472 set_relation (r: kind, n1, n2);
473}
474
475// Return the number of bits associated with partial equivalency T.
476// Return 0 if this is not a supported partial equivalency relation.
477
478inline int
479pe_to_bits (relation_kind t)
480{
481 switch (t)
482 {
483 case VREL_PE8:
484 return 8;
485 case VREL_PE16:
486 return 16;
487 case VREL_PE32:
488 return 32;
489 case VREL_PE64:
490 return 64;
491 default:
492 return 0;
493 }
494}
495
496// Return the partial equivalency code associated with the number of BITS.
497// return VREL_VARYING if there is no exact match.
498
499inline relation_kind
500bits_to_pe (int bits)
501{
502 switch (bits)
503 {
504 case 8:
505 return VREL_PE8;
506 case 16:
507 return VREL_PE16;
508 case 32:
509 return VREL_PE32;
510 case 64:
511 return VREL_PE64;
512 default:
513 return VREL_VARYING;
514 }
515}
516
517// Given partial equivalencies T1 and T2, return the smallest kind.
518
519inline relation_kind
520pe_min (relation_kind t1, relation_kind t2)
521{
522 gcc_checking_assert (relation_partial_equiv_p (t1));
523 gcc_checking_assert (relation_partial_equiv_p (t2));
524 // VREL_PE are declared small to large, so simple min will suffice.
525 return MIN (t1, t2);
526}
527#endif /* GCC_VALUE_RELATION_H */
528

source code of gcc/value-relation.h