Line data Source code
1 : /* Header file for the value range relational processing.
2 : Copyright (C) 2020-2026 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 5684963 : inline bool relation_lt_le_gt_ge_p (relation_kind r)
86 5684963 : { return (r >= VREL_LT && r <= VREL_GE); }
87 176259082 : inline bool relation_partial_equiv_p (relation_kind r)
88 117999342 : { return (r >= VREL_PE8 && r <= VREL_PE64); }
89 149581804 : inline bool relation_equiv_p (relation_kind r)
90 149581804 : { return r == VREL_EQ || relation_partial_equiv_p (r); }
91 :
92 : void print_relation (FILE *f, relation_kind rel);
93 :
94 : // Adjust range as an equivalence.
95 : void adjust_equivalence_range (vrange &range);
96 :
97 54442782 : class relation_oracle
98 : {
99 : public:
100 54727373 : virtual ~relation_oracle () { }
101 :
102 : // register a relation between 2 ssa names.
103 : bool record (gimple *, relation_kind, tree, tree);
104 : bool record (edge, relation_kind, tree, tree);
105 1137168 : virtual bool record (basic_block, relation_kind, tree, tree) { return false; }
106 :
107 : // Query if there is any relation between SSA1 and SSA2.
108 : relation_kind query (gimple *s, tree ssa1, tree ssa2);
109 : relation_kind query (edge e, tree ssa1, tree ssa2);
110 14172366 : virtual relation_kind query (basic_block, tree, tree) { return VREL_VARYING; }
111 :
112 0 : virtual void dump (FILE *, basic_block) const { }
113 0 : virtual void dump (FILE *) const { }
114 : void debug () const;
115 : protected:
116 : friend class equiv_relation_iterator;
117 : friend class block_relation_iterator;
118 0 : virtual class relation_chain *next_relation (basic_block,
119 : relation_chain *,
120 : tree) const
121 0 : { return NULL; }
122 : // Return equivalency set for an SSA name in a basic block.
123 1 : virtual const_bitmap equiv_set (tree, basic_block) { return NULL; }
124 : // Return partial equivalency record for an SSA name.
125 1 : virtual const class pe_slice *partial_equiv_set (tree) { return NULL; }
126 : void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb);
127 : // Query for a relation between two equivalency sets in a basic block.
128 0 : virtual relation_kind query (basic_block, const_bitmap, const_bitmap)
129 0 : { return VREL_VARYING; }
130 : friend class path_oracle;
131 : };
132 :
133 : // Instance with no storage used for default queries with no active oracle.
134 : extern relation_oracle default_relation_oracle;
135 :
136 : // This class represents an equivalency set, and contains a link to the next
137 : // one in the list to be searched.
138 :
139 : class equiv_chain
140 : {
141 : public:
142 : bitmap m_names; // ssa-names in equiv set.
143 : basic_block m_bb; // Block this belongs to
144 : equiv_chain *m_next; // Next in block list.
145 : void dump (FILE *f) const; // Show names in this list.
146 : equiv_chain *find (unsigned ssa);
147 : };
148 :
149 : class pe_slice
150 : {
151 : public:
152 : tree ssa_base; // Slice of this name.
153 : relation_kind code; // bits that are equivalent.
154 : bitmap members; // Other members in the partial equivalency.
155 : };
156 :
157 : // The equivalency oracle maintains equivalencies using the dominator tree.
158 : // Equivalencies apply to an entire basic block. Equivalencies on edges
159 : // can be represented only on edges whose destination is a single-pred block,
160 : // and the equivalence is simply applied to that successor block.
161 :
162 : class equiv_oracle : public relation_oracle
163 : {
164 : public:
165 : equiv_oracle ();
166 : ~equiv_oracle ();
167 :
168 : const_bitmap equiv_set (tree ssa, basic_block bb) final override;
169 : bool record (basic_block bb, relation_kind k, tree ssa1, tree ssa2) override;
170 :
171 : relation_kind partial_equiv (tree ssa1, tree ssa2, tree *base = NULL) const;
172 : relation_kind query (basic_block, tree, tree) override;
173 : relation_kind query (basic_block, const_bitmap, const_bitmap) override;
174 : void dump (FILE *f, basic_block bb) const override;
175 : void dump (FILE *f) const override;
176 :
177 : protected:
178 : bool add_partial_equiv (relation_kind, tree, tree);
179 : const pe_slice *partial_equiv_set (tree name) final override;
180 49207804 : inline bool has_equiv_p (unsigned v) { return bitmap_bit_p (m_equiv_set, v); }
181 : bitmap_obstack m_bitmaps;
182 : struct obstack m_chain_obstack;
183 : private:
184 : bitmap m_equiv_set; // Index by ssa-name. true if an equivalence exists.
185 : vec <equiv_chain *> m_equiv; // Index by BB. list of equivalences.
186 : vec <bitmap> m_self_equiv; // Index by ssa-name, self equivalency set.
187 : vec <pe_slice> m_partial; // Partial equivalencies.
188 :
189 : void limit_check (basic_block bb = NULL);
190 : equiv_chain *find_equiv_block (unsigned ssa, int bb) const;
191 : equiv_chain *find_equiv_dom (tree name, basic_block bb) const;
192 :
193 : bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1);
194 : bitmap register_equiv (basic_block bb, equiv_chain *equiv_1,
195 : equiv_chain *equiv_2);
196 : void register_initial_def (tree ssa);
197 : void add_equiv_to_block (basic_block bb, bitmap equiv);
198 : };
199 :
200 : // Summary block header for relations.
201 :
202 : class relation_chain_head
203 : {
204 : public:
205 : bitmap m_names; // ssa_names with relations in this block.
206 : class relation_chain *m_head; // List of relations in block.
207 : int m_num_relations; // Number of relations in block.
208 : relation_kind find_relation (const_bitmap b1, const_bitmap b2) const;
209 : };
210 :
211 : // A relation oracle maintains a set of relations between ssa_names using the
212 : // dominator tree structures. Equivalencies are considered a subset of
213 : // a general relation and maintained by an equivalence oracle by transparently
214 : // passing any EQ_EXPR relations to it.
215 : // Relations are handled at the basic block level. All relations apply to
216 : // an entire block, and are thus kept in a summary index by block.
217 : // Similar to the equivalence oracle, edges are handled by applying the
218 : // relation to the destination block of the edge, but ONLY if that block
219 : // has a single successor. For now.
220 :
221 : class dom_oracle : public equiv_oracle
222 : {
223 : public:
224 : dom_oracle (bool do_trans_p = true);
225 : ~dom_oracle ();
226 :
227 : bool record (basic_block bb, relation_kind k, tree op1, tree op2)
228 : final override;
229 :
230 : relation_kind query (basic_block bb, tree ssa1, tree ssa2) final override;
231 : relation_kind query (basic_block bb, const_bitmap b1, const_bitmap b2)
232 : final override;
233 :
234 : void dump (FILE *f, basic_block bb) const final override;
235 : void dump (FILE *f) const final override;
236 : protected:
237 : virtual relation_chain *next_relation (basic_block, relation_chain *,
238 : tree) const override;
239 : bool m_do_trans_p;
240 : bitmap m_tmp, m_tmp2;
241 : bitmap m_relation_set; // Index by ssa-name. True if a relation exists
242 : vec <relation_chain_head> m_relations; // Index by BB, list of relations.
243 : relation_kind find_relation_block (unsigned bb, const_bitmap b1,
244 : const_bitmap b2) const;
245 : relation_kind find_relation_block (int bb, unsigned v1, unsigned v2,
246 : relation_chain **obj = NULL) const;
247 : relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const;
248 : relation_chain *set_one_relation (basic_block bb, relation_kind k, tree op1,
249 : tree op2);
250 : void register_transitives (basic_block, const class value_relation &);
251 :
252 : };
253 :
254 : // A path_oracle implements relations in a list. The only sense of ordering
255 : // is the latest registered relation is the first found during a search.
256 : // It can be constructed with an optional "root" oracle which will be used
257 : // to look up any relations not found in the list.
258 : // This allows the client to walk paths starting at some block and register
259 : // and query relations along that path, ignoring other edges.
260 : //
261 : // For registering a relation, a query if made of the root oracle if there is
262 : // any known relationship at block BB, and it is combined with this new
263 : // relation and entered in the list.
264 : //
265 : // Queries are resolved by looking first in the list, and only if nothing is
266 : // found is the root oracle queried at block BB.
267 : //
268 : // reset_path is used to clear all locally registered paths to initial state.
269 :
270 : class path_oracle : public relation_oracle
271 : {
272 : public:
273 : path_oracle (relation_oracle *oracle = NULL);
274 : ~path_oracle ();
275 : const_bitmap equiv_set (tree, basic_block) final override;
276 : bool record (basic_block, relation_kind, tree, tree) final override;
277 : void killing_def (tree);
278 : relation_kind query (basic_block, tree, tree) final override;
279 : relation_kind query (basic_block, const_bitmap, const_bitmap) final override;
280 : void reset_path (relation_oracle *oracle = NULL);
281 52722554 : void set_root_oracle (relation_oracle *oracle) { m_root = oracle; }
282 : void dump (FILE *, basic_block) const final override;
283 : void dump (FILE *) const final override;
284 : private:
285 : bool register_equiv (basic_block bb, tree ssa1, tree ssa2);
286 : equiv_chain m_equiv;
287 : relation_chain_head m_relations;
288 : relation_oracle *m_root;
289 : bitmap m_killed_defs;
290 :
291 : bitmap_obstack m_bitmaps;
292 : struct obstack m_chain_obstack;
293 : };
294 :
295 : // Used to assist with iterating over the equivalence list.
296 : class equiv_relation_iterator {
297 : public:
298 : equiv_relation_iterator (relation_oracle *oracle, basic_block bb, tree name,
299 : bool full = true, bool partial = false);
300 : void next ();
301 : tree get_name (relation_kind *rel = NULL);
302 : protected:
303 : relation_oracle *m_oracle;
304 : const_bitmap m_bm;
305 : const pe_slice *m_pe;
306 : bitmap_iterator m_bi;
307 : unsigned m_y;
308 : tree m_name;
309 : };
310 :
311 : #define FOR_EACH_EQUIVALENCE(oracle, bb, name, equiv_name) \
312 : for (equiv_relation_iterator iter (oracle, bb, name, true, false); \
313 : ((equiv_name) = iter.get_name ()); \
314 : iter.next ())
315 :
316 : #define FOR_EACH_PARTIAL_EQUIV(oracle, bb, name, equiv_name, equiv_rel) \
317 : for (equiv_relation_iterator iter (oracle, bb, name, false, true); \
318 : ((equiv_name) = iter.get_name (&equiv_rel)); \
319 : iter.next ())
320 :
321 : #define FOR_EACH_PARTIAL_AND_FULL_EQUIV(oracle, bb, name, equiv_name, \
322 : equiv_rel) \
323 : for (equiv_relation_iterator iter (oracle, bb, name, true, true); \
324 : ((equiv_name) = iter.get_name (&equiv_rel)); \
325 : iter.next ())
326 :
327 : // -----------------------------------------------------------------------
328 :
329 : // Range-ops deals with a LHS and 2 operands. A relation trio is a set of
330 : // 3 potential relations packed into a single unsigned value.
331 : // 1 - LHS relation OP1
332 : // 2 - LHS relation OP2
333 : // 3 - OP1 relation OP2
334 : // VREL_VARYING is a value of 0, and is the default for each position.
335 : class relation_trio
336 : {
337 : public:
338 : relation_trio ();
339 : relation_trio (relation_kind lhs_op1, relation_kind lhs_op2,
340 : relation_kind op1_op2);
341 : relation_kind lhs_op1 ();
342 : relation_kind lhs_op2 ();
343 : relation_kind op1_op2 ();
344 : relation_trio swap_op1_op2 ();
345 :
346 : static relation_trio lhs_op1 (relation_kind k);
347 : static relation_trio lhs_op2 (relation_kind k);
348 : static relation_trio op1_op2 (relation_kind k);
349 :
350 : protected:
351 : unsigned m_val;
352 : };
353 :
354 : // Default VREL_VARYING for all 3 relations.
355 : #define TRIO_VARYING relation_trio ()
356 :
357 : #define TRIO_SHIFT 4
358 : #define TRIO_MASK 0x000F
359 :
360 : // These 3 classes are shortcuts for when a caller has a single relation to
361 : // pass as a trio, it can simply construct the appropriate one. The other
362 : // unspecified relations will be VREL_VARYING.
363 :
364 257603736 : inline relation_trio::relation_trio ()
365 : {
366 257603736 : STATIC_ASSERT (VREL_LAST <= (1 << TRIO_SHIFT));
367 257603736 : m_val = 0;
368 : }
369 :
370 239561201 : inline relation_trio::relation_trio (relation_kind lhs_op1,
371 : relation_kind lhs_op2,
372 : relation_kind op1_op2)
373 : {
374 239561201 : STATIC_ASSERT (VREL_LAST <= (1 << TRIO_SHIFT));
375 239561201 : unsigned i1 = (unsigned) lhs_op1;
376 239561201 : unsigned i2 = ((unsigned) lhs_op2) << TRIO_SHIFT;
377 239561201 : unsigned i3 = ((unsigned) op1_op2) << (TRIO_SHIFT * 2);
378 239561201 : m_val = i1 | i2 | i3;
379 : }
380 :
381 : inline relation_trio
382 776023 : relation_trio::lhs_op1 (relation_kind k)
383 : {
384 776023 : return relation_trio (k, VREL_VARYING, VREL_VARYING);
385 : }
386 : inline relation_trio
387 615191 : relation_trio::lhs_op2 (relation_kind k)
388 : {
389 615191 : return relation_trio (VREL_VARYING, k, VREL_VARYING);
390 : }
391 : inline relation_trio
392 172034701 : relation_trio::op1_op2 (relation_kind k)
393 : {
394 172034701 : return relation_trio (VREL_VARYING, VREL_VARYING, k);
395 : }
396 :
397 : inline relation_kind
398 22055127 : relation_trio::lhs_op1 ()
399 : {
400 12405337 : return (relation_kind) (m_val & TRIO_MASK);
401 : }
402 :
403 : inline relation_kind
404 9901788 : relation_trio::lhs_op2 ()
405 : {
406 10040106 : return (relation_kind) ((m_val >> TRIO_SHIFT) & TRIO_MASK);
407 : }
408 :
409 : inline relation_kind
410 320251303 : relation_trio::op1_op2 ()
411 : {
412 310349516 : return (relation_kind) ((m_val >> (TRIO_SHIFT * 2)) & TRIO_MASK);
413 : }
414 :
415 : inline relation_trio
416 9901787 : relation_trio::swap_op1_op2 ()
417 : {
418 9901787 : return relation_trio (lhs_op2 (), lhs_op1 (), relation_swap (op1_op2 ()));
419 : }
420 :
421 : // -----------------------------------------------------------------------
422 :
423 : // The value-relation class is used to encapsulate the representation of an
424 : // individual relation between 2 ssa-names, and to facilitate operating on
425 : // the relation.
426 :
427 : class value_relation
428 : {
429 : public:
430 : value_relation ();
431 : value_relation (relation_kind kind, tree n1, tree n2);
432 : void set_relation (relation_kind kind, tree n1, tree n2);
433 :
434 34022996 : inline relation_kind kind () const { return related; }
435 154035625 : inline tree op1 () const { return name1; }
436 151362450 : inline tree op2 () const { return name2; }
437 :
438 : relation_trio create_trio (tree lhs, tree op1, tree op2);
439 : bool union_ (value_relation &p);
440 : bool intersect (value_relation &p);
441 : void swap ();
442 : bool apply_transitive (const value_relation &rel);
443 :
444 : void dump (FILE *f) const;
445 : private:
446 : relation_kind related;
447 : tree name1, name2;
448 : };
449 :
450 : // Set relation R between ssa_name N1 and N2.
451 :
452 : inline void
453 120893197 : value_relation::set_relation (relation_kind r, tree n1, tree n2)
454 : {
455 120893197 : gcc_checking_assert (TREE_CODE (n1) == SSA_NAME
456 : && TREE_CODE (n2) == SSA_NAME);
457 120893197 : related = r;
458 120893197 : name1 = n1;
459 120893197 : name2 = n2;
460 120893197 : }
461 :
462 : // Default constructor.
463 :
464 : inline
465 124848399 : value_relation::value_relation ()
466 : {
467 124848399 : related = VREL_VARYING;
468 124848399 : name1 = NULL_TREE;
469 124848399 : name2 = NULL_TREE;
470 : }
471 :
472 : // Constructor for relation R between SSA version N1 and N2.
473 :
474 : inline
475 40171834 : value_relation::value_relation (relation_kind kind, tree n1, tree n2)
476 : {
477 40171834 : set_relation (kind, n1, n2);
478 : }
479 :
480 :
481 : class block_relation_iterator {
482 : public:
483 : block_relation_iterator (const relation_oracle *oracle, basic_block bb,
484 : value_relation &, tree name = NULL);
485 : void get_next_relation (value_relation &vr);
486 : const relation_oracle *m_oracle;
487 : basic_block m_bb;
488 : relation_chain *m_ptr;
489 : bool m_done;
490 : tree m_name;
491 : };
492 :
493 : #define FOR_EACH_RELATION_BB(oracle, bb, vr) \
494 : for (block_relation_iterator iter (oracle, bb, vr); \
495 : !iter.m_done; \
496 : iter.get_next_relation (vr))
497 :
498 : #define FOR_EACH_RELATION_NAME(oracle, bb, name, vr) \
499 : for (block_relation_iterator iter (oracle, bb, vr, name); \
500 : !iter.m_done; \
501 : iter.get_next_relation (vr))
502 :
503 :
504 : // Return the number of bits associated with partial equivalency T.
505 : // Return 0 if this is not a supported partial equivalency relation.
506 :
507 : inline int
508 17845900 : pe_to_bits (relation_kind t)
509 : {
510 17845900 : switch (t)
511 : {
512 : case VREL_PE8:
513 : return 8;
514 : case VREL_PE16:
515 : return 16;
516 : case VREL_PE32:
517 : return 32;
518 : case VREL_PE64:
519 : return 64;
520 : default:
521 : return 0;
522 : }
523 : }
524 :
525 : // Return the partial equivalency code associated with the number of BITS.
526 : // return VREL_VARYING if there is no exact match.
527 :
528 : inline relation_kind
529 37490870 : bits_to_pe (int bits)
530 : {
531 37490870 : switch (bits)
532 : {
533 : case 8:
534 : return VREL_PE8;
535 : case 16:
536 : return VREL_PE16;
537 : case 32:
538 : return VREL_PE32;
539 : case 64:
540 : return VREL_PE64;
541 : default:
542 : return VREL_VARYING;
543 : }
544 : }
545 :
546 : // Given partial equivalencies T1 and T2, return the smallest kind.
547 :
548 : inline relation_kind
549 8182224 : pe_min (relation_kind t1, relation_kind t2)
550 : {
551 8182224 : gcc_checking_assert (relation_partial_equiv_p (t1));
552 8182224 : gcc_checking_assert (relation_partial_equiv_p (t2));
553 : // VREL_PE are declared small to large, so simple min will suffice.
554 8182224 : return MIN (t1, t2);
555 : }
556 : #endif /* GCC_VALUE_RELATION_H */
|
