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