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
5 This file is part of GCC.
6
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
10 version.
11
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
15 for more details.
16
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/>. */
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
63 typedef 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.
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); }
91
92 void print_relation (FILE *f, relation_kind rel);
93
94 class relation_oracle
95 {
96 public:
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);
102
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;
107
108 relation_kind validate_relation (relation_kind, tree, tree);
109 relation_kind validate_relation (relation_kind, vrange &, vrange &);
110
111 virtual void dump (FILE *, basic_block) const = 0;
112 virtual void dump (FILE *) const = 0;
113 void debug () const;
114 protected:
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,
123 const_bitmap) = 0;
124 friend class path_oracle;
125 };
126
127 // This class represents an equivalency set, and contains a link to the next
128 // one in the list to be searched.
129
130 class equiv_chain
131 {
132 public:
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);
138 };
139
140 class pe_slice
141 {
142 public:
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.
146 };
147
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 successor block.
152
153 class equiv_oracle : public relation_oracle
154 {
155 public:
156 equiv_oracle ();
157 ~equiv_oracle ();
158
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,
162 tree ssa2) override;
163
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)
168 override;
169 void dump (FILE *f, basic_block bb) const override;
170 void dump (FILE *f) const override;
171
172 protected:
173 bitmap_obstack m_bitmaps;
174 struct obstack m_chain_obstack;
175 private:
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.
180
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;
184
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);
190 };
191
192 // Summary block header for relations.
193
194 class relation_chain_head
195 {
196 public:
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;
201 };
202
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.
212
213 class dom_oracle : public equiv_oracle
214 {
215 public:
216 dom_oracle ();
217 ~dom_oracle ();
218
219 void register_relation (basic_block bb, relation_kind k, tree op1, tree op2)
220 final override;
221
222 relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2)
223 final override;
224 relation_kind query_relation (basic_block bb, const_bitmap b1,
225 const_bitmap b2) final override;
226
227 void dump (FILE *f, basic_block bb) const final override;
228 void dump (FILE *f) const final override;
229 private:
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,
239 tree op2);
240 void register_transitives (basic_block, const class value_relation &);
241
242 };
243
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.
250 //
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.
254 //
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.
257 //
258 // reset_path is used to clear all locally registered paths to initial state.
259
260 class path_oracle : public relation_oracle
261 {
262 public:
263 path_oracle (relation_oracle *oracle = NULL);
264 ~path_oracle ();
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)
270 final override;
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;
275 private:
276 void register_equiv (basic_block bb, tree ssa1, tree ssa2);
277 equiv_chain m_equiv;
278 relation_chain_head m_relations;
279 relation_oracle *m_root;
280 bitmap m_killed_defs;
281
282 bitmap_obstack m_bitmaps;
283 struct obstack m_chain_obstack;
284 };
285
286 // Used to assist with iterating over the equivalence list.
287 class equiv_relation_iterator {
288 public:
289 equiv_relation_iterator (relation_oracle *oracle, basic_block bb, tree name,
290 bool full = true, bool partial = false);
291 void next ();
292 tree get_name (relation_kind *rel = NULL);
293 protected:
294 relation_oracle *m_oracle;
295 const_bitmap m_bm;
296 const pe_slice *m_pe;
297 bitmap_iterator m_bi;
298 unsigned m_y;
299 tree m_name;
300 };
301
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 ()); \
305 iter.next ())
306
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)); \
310 iter.next ())
311
312 #define FOR_EACH_PARTIAL_AND_FULL_EQUIV(oracle, bb, name, equiv_name, \
313 equiv_rel) \
314 for (equiv_relation_iterator iter (oracle, bb, name, true, true); \
315 ((equiv_name) = iter.get_name (&equiv_rel)); \
316 iter.next ())
317
318 // -----------------------------------------------------------------------
319
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.
326 class relation_trio
327 {
328 public:
329 relation_trio ();
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 ();
336
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);
340
341 protected:
342 unsigned m_val;
343 };
344
345 // Default VREL_VARYING for all 3 relations.
346 #define TRIO_VARYING relation_trio ()
347
348 #define TRIO_SHIFT 4
349 #define TRIO_MASK 0x000F
350
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 relations will be VREL_VARYING.
354
355 inline relation_trio::relation_trio ()
356 {
357 STATIC_ASSERT (VREL_LAST <= (1 << TRIO_SHIFT));
358 m_val = 0;
359 }
360
361 inline relation_trio::relation_trio (relation_kind lhs_op1,
362 relation_kind lhs_op2,
363 relation_kind op1_op2)
364 {
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;
370 }
371
372 inline relation_trio
373 relation_trio::lhs_op1 (relation_kind k)
374 {
375 return relation_trio (k, VREL_VARYING, VREL_VARYING);
376 }
377 inline relation_trio
378 relation_trio::lhs_op2 (relation_kind k)
379 {
380 return relation_trio (VREL_VARYING, k, VREL_VARYING);
381 }
382 inline relation_trio
383 relation_trio::op1_op2 (relation_kind k)
384 {
385 return relation_trio (VREL_VARYING, VREL_VARYING, k);
386 }
387
388 inline relation_kind
389 relation_trio::lhs_op1 ()
390 {
391 return (relation_kind) (m_val & TRIO_MASK);
392 }
393
394 inline relation_kind
395 relation_trio::lhs_op2 ()
396 {
397 return (relation_kind) ((m_val >> TRIO_SHIFT) & TRIO_MASK);
398 }
399
400 inline relation_kind
401 relation_trio::op1_op2 ()
402 {
403 return (relation_kind) ((m_val >> (TRIO_SHIFT * 2)) & TRIO_MASK);
404 }
405
406 inline relation_trio
407 relation_trio::swap_op1_op2 ()
408 {
409 return relation_trio (lhs_op2 (), lhs_op1 (), relation_swap (op1_op2 ()));
410 }
411
412 // -----------------------------------------------------------------------
413
414 // The value-relation class is used to encapsulate the representation of an
415 // individual relation between 2 ssa-names, and to facilitate operating on
416 // the relation.
417
418 class value_relation
419 {
420 public:
421 value_relation ();
422 value_relation (relation_kind kind, tree n1, tree n2);
423 void set_relation (relation_kind kind, tree n1, tree n2);
424
425 inline relation_kind kind () const { return related; }
426 inline tree op1 () const { return name1; }
427 inline tree op2 () const { return name2; }
428
429 relation_trio create_trio (tree lhs, tree op1, tree op2);
430 bool union_ (value_relation &p);
431 bool intersect (value_relation &p);
432 void negate ();
433 bool apply_transitive (const value_relation &rel);
434
435 void dump (FILE *f) const;
436 private:
437 relation_kind related;
438 tree name1, name2;
439 };
440
441 // Set relation R between ssa_name N1 and N2.
442
443 inline void
444 value_relation::set_relation (relation_kind r, tree n1, tree n2)
445 {
446 gcc_checking_assert (TREE_CODE (n1) == SSA_NAME
447 && TREE_CODE (n2) == SSA_NAME);
448 related = r;
449 name1 = n1;
450 name2 = n2;
451 }
452
453 // Default constructor.
454
455 inline
456 value_relation::value_relation ()
457 {
458 related = VREL_VARYING;
459 name1 = NULL_TREE;
460 name2 = NULL_TREE;
461 }
462
463 // Constructor for relation R between SSA version N1 and N2.
464
465 inline
466 value_relation::value_relation (relation_kind kind, tree n1, tree n2)
467 {
468 set_relation (kind, n1, n2);
469 }
470
471 // Return the number of bits associated with partial equivalency T.
472 // Return 0 if this is not a supported partial equivalency relation.
473
474 inline int
475 pe_to_bits (relation_kind t)
476 {
477 switch (t)
478 {
479 case VREL_PE8:
480 return 8;
481 case VREL_PE16:
482 return 16;
483 case VREL_PE32:
484 return 32;
485 case VREL_PE64:
486 return 64;
487 default:
488 return 0;
489 }
490 }
491
492 // Return the partial equivalency code associated with the number of BITS.
493 // return VREL_VARYING if there is no exact match.
494
495 inline relation_kind
496 bits_to_pe (int bits)
497 {
498 switch (bits)
499 {
500 case 8:
501 return VREL_PE8;
502 case 16:
503 return VREL_PE16;
504 case 32:
505 return VREL_PE32;
506 case 64:
507 return VREL_PE64;
508 default:
509 return VREL_VARYING;
510 }
511 }
512
513 // Given partial equivalencies T1 and T2, return the smallest kind.
514
515 inline relation_kind
516 pe_min (relation_kind t1, relation_kind t2)
517 {
518 gcc_checking_assert (relation_partial_equiv_p (t1));
519 gcc_checking_assert (relation_partial_equiv_p (t2));
520 // VREL_PE are declared small to large, so simple min will suffice.
521 return MIN (t1, t2);
522 }
523 #endif /* GCC_VALUE_RELATION_H */