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 | // Adjust range as an equivalence. |
95 | void adjust_equivalence_range (vrange &range); |
96 | |
97 | class relation_oracle |
98 | { |
99 | public: |
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; |
117 | protected: |
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 | |
133 | class equiv_chain |
134 | { |
135 | public: |
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 | |
143 | class pe_slice |
144 | { |
145 | public: |
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 | |
156 | class equiv_oracle : public relation_oracle |
157 | { |
158 | public: |
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 | |
175 | protected: |
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; |
179 | private: |
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 | |
198 | class relation_chain_head |
199 | { |
200 | public: |
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 | |
217 | class dom_oracle : public equiv_oracle |
218 | { |
219 | public: |
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; |
233 | private: |
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 | |
264 | class path_oracle : public relation_oracle |
265 | { |
266 | public: |
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; |
279 | private: |
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. |
291 | class equiv_relation_iterator { |
292 | public: |
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); |
297 | protected: |
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. |
330 | class relation_trio |
331 | { |
332 | public: |
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 | |
345 | protected: |
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 | |
359 | inline relation_trio::relation_trio () |
360 | { |
361 | STATIC_ASSERT (VREL_LAST <= (1 << TRIO_SHIFT)); |
362 | m_val = 0; |
363 | } |
364 | |
365 | inline 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 | |
376 | inline relation_trio |
377 | relation_trio::lhs_op1 (relation_kind k) |
378 | { |
379 | return relation_trio (k, VREL_VARYING, VREL_VARYING); |
380 | } |
381 | inline relation_trio |
382 | relation_trio::lhs_op2 (relation_kind k) |
383 | { |
384 | return relation_trio (VREL_VARYING, k, VREL_VARYING); |
385 | } |
386 | inline relation_trio |
387 | relation_trio::op1_op2 (relation_kind k) |
388 | { |
389 | return relation_trio (VREL_VARYING, VREL_VARYING, k); |
390 | } |
391 | |
392 | inline relation_kind |
393 | relation_trio::lhs_op1 () |
394 | { |
395 | return (relation_kind) (m_val & TRIO_MASK); |
396 | } |
397 | |
398 | inline relation_kind |
399 | relation_trio::lhs_op2 () |
400 | { |
401 | return (relation_kind) ((m_val >> TRIO_SHIFT) & TRIO_MASK); |
402 | } |
403 | |
404 | inline relation_kind |
405 | relation_trio::op1_op2 () |
406 | { |
407 | return (relation_kind) ((m_val >> (TRIO_SHIFT * 2)) & TRIO_MASK); |
408 | } |
409 | |
410 | inline relation_trio |
411 | relation_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 | |
422 | class value_relation |
423 | { |
424 | public: |
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; |
440 | private: |
441 | relation_kind related; |
442 | tree name1, name2; |
443 | }; |
444 | |
445 | // Set relation R between ssa_name N1 and N2. |
446 | |
447 | inline void |
448 | value_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 | |
459 | inline |
460 | value_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 | |
469 | inline |
470 | value_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 | |
478 | inline int |
479 | pe_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 | |
499 | inline relation_kind |
500 | bits_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 | |
519 | inline relation_kind |
520 | pe_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 | |