/* Header file for the value range relational processing. | |

Copyright (C) 2020-2021 Free Software Foundation, Inc. | |

Contributed by Andrew MacLeod <amacleod@redhat.com> | |

This file is part of GCC. | |

GCC is free software; you can redistribute it and/or modify it under | |

the terms of the GNU General Public License as published by the Free | |

Software Foundation; either version 3, or (at your option) any later | |

version. | |

GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |

WARRANTY; without even the implied warranty of MERCHANTABILITY or | |

FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |

for more details. | |

You should have received a copy of the GNU General Public License | |

along with GCC; see the file COPYING3. If not see | |

<http://www.gnu.org/licenses/>. */ | |

#ifndef GCC_VALUE_RELATION_H | |

#define GCC_VALUE_RELATION_H | |

// This file provides access to a relation oracle which can be used to | |

// maintain and query relations and equivalences between SSA_NAMES. | |

// | |

// The general range_query object provided in value-query.h provides | |

// access to an oracle, if one is available, via the oracle() method. | |

// Thre are also a couple of access routines provided, which even if there is | |

// no oracle, will return the default VREL_NONE no relation. | |

// | |

// Typically, when a ranger object is active, there will be an oracle, and | |

// any information available can be directly queried. Ranger also sets and | |

// utilizes the relation information to enhance it's range calculations, this | |

// is totally transparent to the client, and they are free to make queries. | |

// | |

// | |

// relation_kind is a typedef of enum tree_code, but has restricted range | |

// and a couple of extra values. | |

// | |

// A query is made requesting the relation between SSA1 and SSA@ in a basic | |

// block, or on an edge, the possible return values are: | |

// | |

// EQ_EXPR, NE_EXPR, LT_EXPR, LE_EXPR, GT_EXPR, and GE_EXPR mean the same. | |

// VREL_NONE : No relation between the 2 names. | |

// VREL_EMPTY : Impossible relation (ie, A < B && A > B produces VREL_EMPTY. | |

// | |

// The oracle maintains EQ_EXPR relations with equivalency sets, so if a | |

// relation comes back EQ_EXPR, it is also possible to query the set of | |

// equivlaencies. These are basically bitmaps over ssa_names. | |

// | |

// relations are maintained via the dominace trees, are are optimized assuming | |

// they are registered in dominance order. When a new relation is added, it | |

// is intersected with whatever existing relation exists in the dominance tree | |

// and registered at the specified block. | |

// Rather than introduce a new enumerated type for relations, we can use the | |

// existing tree_codes for relations, plus add a couple of #defines for | |

// the other cases. These codes are arranged such that VREL_NONE is the first | |

// code, and all the rest are contiguous. | |

typedef enum tree_code relation_kind; | |

#define VREL_NONE TRUTH_NOT_EXPR | |

#define VREL_EMPTY LTGT_EXPR | |

// General relation kind transformations. | |

relation_kind relation_union (relation_kind r1, relation_kind r2); | |

relation_kind relation_intersect (relation_kind r1, relation_kind r2); | |

relation_kind relation_negate (relation_kind r); | |

relation_kind relation_swap (relation_kind r); | |

void print_relation (FILE *f, relation_kind rel); | |

// Declared internally in value-relation.cc | |

class equiv_chain; | |

// The equivalency oracle maintains equivalencies using the dominator tree. | |

// Equivalencies apply to an entire basic block. Equivalencies on edges | |

// can be represented only on edges whose destination is a single-pred block, | |

// and the equivalence is simply applied to that succesor block. | |

class equiv_oracle | |

{ | |

public: | |

equiv_oracle (); | |

~equiv_oracle (); | |

const_bitmap equiv_set (tree ssa, basic_block bb) const; | |

void register_equiv (basic_block bb, tree ssa1, tree ssa2); | |

void dump (FILE *f, basic_block bb) const; | |

void dump (FILE *f) const; | |

protected: | |

bitmap_obstack m_bitmaps; | |

struct obstack m_chain_obstack; | |

private: | |

bitmap m_equiv_set; // Index by ssa-name. true if an equivalence exists. | |

vec <equiv_chain *> m_equiv; // Index by BB. list of equivalences. | |

void limit_check (basic_block bb = NULL); | |

equiv_chain *find_equiv_block (unsigned ssa, int bb) const; | |

equiv_chain *find_equiv_dom (tree name, basic_block bb) const; | |

bitmap register_equiv (basic_block bb, unsigned v, equiv_chain *equiv_1); | |

bitmap register_equiv (basic_block bb, equiv_chain *equiv_1, | |

equiv_chain *equiv_2); | |

}; | |

// Summary block header for relations. | |

class relation_chain_head | |

{ | |

public: | |

bitmap m_names; // ssa_names with relations in this block. | |

class relation_chain *m_head; // List of relations in block. | |

}; | |

// A relation oracle maintains a set of relations between ssa_names using the | |

// dominator tree structures. Equivalencies are considered a subset of | |

// a general relation and maintained by an equivalence oracle by transparently | |

// passing any EQ_EXPR relations to it. | |

// Relations are handled at the basic block level. All relations apply to | |

// an entire block, and are thus kept in a summary index by block. | |

// Similar to the equivalence oracle, edges are handled by applying the | |

// relation to the destination block of the edge, but ONLY if that block | |

// has a single successor. For now. | |

class relation_oracle : public equiv_oracle | |

{ | |

public: | |

relation_oracle (); | |

~relation_oracle (); | |

void register_relation (gimple *stmt, relation_kind k, tree op1, tree op2); | |

void register_relation (edge e, relation_kind k, tree op1, tree op2); | |

relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2); | |

void dump (FILE *f, basic_block bb) const; | |

void dump (FILE *f) const; | |

void debug () const; | |

private: | |

bitmap m_tmp, m_tmp2; | |

bitmap m_relation_set; // Index by ssa-name. True if a relation exists | |

vec <relation_chain_head> m_relations; // Index by BB, list of relations. | |

relation_kind find_relation_block (unsigned bb, const_bitmap b1, | |

const_bitmap b2); | |

relation_kind find_relation_dom (basic_block bb, const_bitmap b1, | |

const_bitmap b2); | |

relation_kind find_relation_block (int bb, unsigned v1, unsigned v2, | |

relation_chain **obj = NULL); | |

relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2); | |

void register_relation (basic_block bb, relation_kind k, tree op1, tree op2, | |

bool transitive_p = false); | |

void register_transitives (basic_block, const class value_relation &); | |

void register_transitives (basic_block, const value_relation &, const_bitmap, | |

const_bitmap); | |

}; | |

#endif /* GCC_VALUE_RELATION_H */ |