Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- GVNExpression.h - GVN Expression classes -----------------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

/// \file

///

/// The header file for the GVN pass that contains expression handling

/// classes

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H

#define LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H

#include "llvm/ADT/Hashing.h"

#include "llvm/ADT/iterator_range.h"

#include "llvm/Analysis/MemorySSA.h"

#include "llvm/IR/Constant.h"

#include "llvm/IR/Instructions.h"

#include "llvm/IR/Value.h"

#include "llvm/Support/Allocator.h"

#include "llvm/Support/ArrayRecycler.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/Compiler.h"

#include "llvm/Support/raw_ostream.h"

#include <algorithm>

#include <cassert>

#include <iterator>

#include <utility>

namespace llvm {

class BasicBlock;

class Type;

namespace GVNExpression {

enum ExpressionType {

  ET_Base,

  ET_Constant,

  ET_Variable,

  ET_Dead,

  ET_Unknown,

  ET_BasicStart,

  ET_Basic,

  ET_AggregateValue,

  ET_Phi,

  ET_MemoryStart,

  ET_Call,

  ET_Load,

  ET_Store,

  ET_MemoryEnd,

  ET_BasicEnd

};

class Expression {

private:

  ExpressionType EType;

  unsigned Opcode;

  mutable hash_code HashVal = 0;

public:

  Expression(ExpressionType ET = ET_Base, unsigned O = ~2U)

      : EType(ET), Opcode(O) {}

  Expression(const Expression &) = delete;

  Expression &operator=(const Expression &) = delete;

  virtual ~Expression();

  static unsigned getEmptyKey() { return ~0U; }

  static unsigned getTombstoneKey() { return ~1U; }

  bool operator!=(const Expression &Other) const { return !(*this == Other); }

  bool operator==(const Expression &Other) const {

    if (getOpcode() != Other.getOpcode())

      return false;

    if (getOpcode() == getEmptyKey() || getOpcode() == getTombstoneKey())

      return true;

    // Compare the expression type for anything but load and store.

    // For load and store we set the opcode to zero to make them equal.

    if (getExpressionType() != ET_Load && getExpressionType() != ET_Store &&

        getExpressionType() != Other.getExpressionType())

      return false;

    return equals(Other);

  }

  hash_code getComputedHash() const {

    // It's theoretically possible for a thing to hash to zero.  In that case,

    // we will just compute the hash a few extra times, which is no worse that

    // we did before, which was to compute it always.

    if (static_cast<unsigned>(HashVal) == 0)

      HashVal = getHashValue();

    return HashVal;

  }

  virtual bool equals(const Expression &Other) const { return true; }

  // Return true if the two expressions are exactly the same, including the

  // normally ignored fields.

  virtual bool exactlyEquals(const Expression &Other) const {

    return getExpressionType() == Other.getExpressionType() && equals(Other);

  }

  unsigned getOpcode() const { return Opcode; }

  void setOpcode(unsigned opcode) { Opcode = opcode; }

  ExpressionType getExpressionType() const { return EType; }

  // We deliberately leave the expression type out of the hash value.

  virtual hash_code getHashValue() const { return getOpcode(); }

  // Debugging support

  virtual void printInternal(raw_ostream &OS, bool PrintEType) const {

    if (PrintEType)

      OS << "etype = " << getExpressionType() << ",";

    OS << "opcode = " << getOpcode() << ", ";

  }

  void print(raw_ostream &OS) const {

    OS << "{ ";

    printInternal(OS, true);

    OS << "}";

  }

  LLVM_DUMP_METHOD void dump() const;

};

inline raw_ostream &operator<<(raw_ostream &OS, const Expression &E) {

  E.print(OS);

  return OS;

}

class BasicExpression : public Expression {

private:

  using RecyclerType = ArrayRecycler<Value *>;

  using RecyclerCapacity = RecyclerType::Capacity;

  Value **Operands = nullptr;

  unsigned MaxOperands;

  unsigned NumOperands = 0;

  Type *ValueType = nullptr;

public:

  BasicExpression(unsigned NumOperands)

      : BasicExpression(NumOperands, ET_Basic) {}

  BasicExpression(unsigned NumOperands, ExpressionType ET)

      : Expression(ET), MaxOperands(NumOperands) {}

  BasicExpression() = delete;

  BasicExpression(const BasicExpression &) = delete;

  BasicExpression &operator=(const BasicExpression &) = delete;

  ~BasicExpression() override;

  static bool classof(const Expression *EB) {

    ExpressionType ET = EB->getExpressionType();

    return ET > ET_BasicStart && ET < ET_BasicEnd;

  }

  /// Swap two operands. Used during GVN to put commutative operands in

  /// order.

  void swapOperands(unsigned First, unsigned Second) {

    std::swap(Operands[First], Operands[Second]);

  }

  Value *getOperand(unsigned N) const {

    assert(Operands && "Operands not allocated");

    assert(N < NumOperands && "Operand out of range");

    return Operands[N];

  }

  void setOperand(unsigned N, Value *V) {

    assert(Operands && "Operands not allocated before setting");

    assert(N < NumOperands && "Operand out of range");

    Operands[N] = V;

  }

  unsigned getNumOperands() const { return NumOperands; }

  using op_iterator = Value **;

  using const_op_iterator = Value *const *;

  op_iterator op_begin() { return Operands; }

  op_iterator op_end() { return Operands + NumOperands; }

  const_op_iterator op_begin() const { return Operands; }

  const_op_iterator op_end() const { return Operands + NumOperands; }

  iterator_range<op_iterator> operands() {

    return iterator_range<op_iterator>(op_begin(), op_end());

  }

  iterator_range<const_op_iterator> operands() const {

    return iterator_range<const_op_iterator>(op_begin(), op_end());

  }

  void op_push_back(Value *Arg) {

    assert(NumOperands < MaxOperands && "Tried to add too many operands");

    assert(Operands && "Operandss not allocated before pushing");

    Operands[NumOperands++] = Arg;

  }

  bool op_empty() const { return getNumOperands() == 0; }

  void allocateOperands(RecyclerType &Recycler, BumpPtrAllocator &Allocator) {

    assert(!Operands && "Operands already allocated");

    Operands = Recycler.allocate(RecyclerCapacity::get(MaxOperands), Allocator);

  }

  void deallocateOperands(RecyclerType &Recycler) {

    Recycler.deallocate(RecyclerCapacity::get(MaxOperands), Operands);

  }

  void setType(Type *T) { ValueType = T; }

  Type *getType() const { return ValueType; }

  bool equals(const Expression &Other) const override {

    if (getOpcode() != Other.getOpcode())

      return false;

    const auto &OE = cast<BasicExpression>(Other);

    return getType() == OE.getType() && NumOperands == OE.NumOperands &&

           std::equal(op_begin(), op_end(), OE.op_begin());

  }

  hash_code getHashValue() const override {

    return hash_combine(this->Expression::getHashValue(), ValueType,

                        hash_combine_range(op_begin(), op_end()));

  }

  // Debugging support

  void printInternal(raw_ostream &OS, bool PrintEType) const override {

    if (PrintEType)

      OS << "ExpressionTypeBasic, ";

    this->Expression::printInternal(OS, false);

    OS << "operands = {";

    for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {

      OS << "[" << i << "] = ";

      Operands[i]->printAsOperand(OS);

      OS << "  ";

    }

    OS << "} ";

  }

};

class op_inserter {

private:

  using Container = BasicExpression;

  Container *BE;

public:

  using iterator_category = std::output_iterator_tag;

  using value_type = void;

  using difference_type = void;

  using pointer = void;

  using reference = void;

  explicit op_inserter(BasicExpression &E) : BE(&E) {}

  explicit op_inserter(BasicExpression *E) : BE(E) {}

  op_inserter &operator=(Value *val) {

    BE->op_push_back(val);

    return *this;

  }

  op_inserter &operator*() { return *this; }

  op_inserter &operator++() { return *this; }

  op_inserter &operator++(int) { return *this; }

};

class MemoryExpression : public BasicExpression {

private:

  const MemoryAccess *MemoryLeader;

public:

  MemoryExpression(unsigned NumOperands, enum ExpressionType EType,

                   const MemoryAccess *MemoryLeader)

      : BasicExpression(NumOperands, EType), MemoryLeader(MemoryLeader) {}

  MemoryExpression() = delete;

  MemoryExpression(const MemoryExpression &) = delete;

  MemoryExpression &operator=(const MemoryExpression &) = delete;

  static bool classof(const Expression *EB) {

    return EB->getExpressionType() > ET_MemoryStart &&

           EB->getExpressionType() < ET_MemoryEnd;

  }

  hash_code getHashValue() const override {

    return hash_combine(this->BasicExpression::getHashValue(), MemoryLeader);

  }

  bool equals(const Expression &Other) const override {

    if (!this->BasicExpression::equals(Other))

      return false;

    const MemoryExpression &OtherMCE = cast<MemoryExpression>(Other);

    return MemoryLeader == OtherMCE.MemoryLeader;

  }

  const MemoryAccess *getMemoryLeader() const { return MemoryLeader; }

  void setMemoryLeader(const MemoryAccess *ML) { MemoryLeader = ML; }

};

class CallExpression final : public MemoryExpression {

private:

  CallInst *Call;

public:

  CallExpression(unsigned NumOperands, CallInst *C,

                 const MemoryAccess *MemoryLeader)

      : MemoryExpression(NumOperands, ET_Call, MemoryLeader), Call(C) {}

  CallExpression() = delete;

  CallExpression(const CallExpression &) = delete;

  CallExpression &operator=(const CallExpression &) = delete;

  ~CallExpression() override;

  static bool classof(const Expression *EB) {

    return EB->getExpressionType() == ET_Call;

  }

  // Debugging support

  void printInternal(raw_ostream &OS, bool PrintEType) const override {

    if (PrintEType)

      OS << "ExpressionTypeCall, ";

    this->BasicExpression::printInternal(OS, false);

    OS << " represents call at ";

    Call->printAsOperand(OS);

  }

};

class LoadExpression final : public MemoryExpression {

private:

  LoadInst *Load;

public:

  LoadExpression(unsigned NumOperands, LoadInst *L,

                 const MemoryAccess *MemoryLeader)

      : LoadExpression(ET_Load, NumOperands, L, MemoryLeader) {}

  LoadExpression(enum ExpressionType EType, unsigned NumOperands, LoadInst *L,

                 const MemoryAccess *MemoryLeader)

      : MemoryExpression(NumOperands, EType, MemoryLeader), Load(L) {}

  LoadExpression() = delete;

  LoadExpression(const LoadExpression &) = delete;

  LoadExpression &operator=(const LoadExpression &) = delete;

  ~LoadExpression() override;

  static bool classof(const Expression *EB) {

    return EB->getExpressionType() == ET_Load;

  }

  LoadInst *getLoadInst() const { return Load; }

  void setLoadInst(LoadInst *L) { Load = L; }

  bool equals(const Expression &Other) const override;

  bool exactlyEquals(const Expression &Other) const override {

    return Expression::exactlyEquals(Other) &&

           cast<LoadExpression>(Other).getLoadInst() == getLoadInst();

  }

  // Debugging support

  void printInternal(raw_ostream &OS, bool PrintEType) const override {

    if (PrintEType)

      OS << "ExpressionTypeLoad, ";

    this->BasicExpression::printInternal(OS, false);

    OS << " represents Load at ";

    Load->printAsOperand(OS);

    OS << " with MemoryLeader " << *getMemoryLeader();

  }

};

class StoreExpression final : public MemoryExpression {

private:

  StoreInst *Store;

  Value *StoredValue;

public:

  StoreExpression(unsigned NumOperands, StoreInst *S, Value *StoredValue,

                  const MemoryAccess *MemoryLeader)

      : MemoryExpression(NumOperands, ET_Store, MemoryLeader), Store(S),

        StoredValue(StoredValue) {}

  StoreExpression() = delete;

  StoreExpression(const StoreExpression &) = delete;

  StoreExpression &operator=(const StoreExpression &) = delete;

  ~StoreExpression() override;

  static bool classof(const Expression *EB) {

    return EB->getExpressionType() == ET_Store;

  }

  StoreInst *getStoreInst() const { return Store; }

  Value *getStoredValue() const { return StoredValue; }

  bool equals(const Expression &Other) const override;

  bool exactlyEquals(const Expression &Other) const override {

    return Expression::exactlyEquals(Other) &&

           cast<StoreExpression>(Other).getStoreInst() == getStoreInst();

  }

  // Debugging support

  void printInternal(raw_ostream &OS, bool PrintEType) const override {

    if (PrintEType)

      OS << "ExpressionTypeStore, ";

    this->BasicExpression::printInternal(OS, false);

    OS << " represents Store  " << *Store;

    OS << " with StoredValue ";

    StoredValue->printAsOperand(OS);

    OS << " and MemoryLeader " << *getMemoryLeader();

  }

};

class AggregateValueExpression final : public BasicExpression {

private:

  unsigned MaxIntOperands;

  unsigned NumIntOperands = 0;

  unsigned *IntOperands = nullptr;

public:

  AggregateValueExpression(unsigned NumOperands, unsigned NumIntOperands)

      : BasicExpression(NumOperands, ET_AggregateValue),

        MaxIntOperands(NumIntOperands) {}

  AggregateValueExpression() = delete;

  AggregateValueExpression(const AggregateValueExpression &) = delete;

  AggregateValueExpression &

  operator=(const AggregateValueExpression &) = delete;

  ~AggregateValueExpression() override;

  static bool classof(const Expression *EB) {

    return EB->getExpressionType() == ET_AggregateValue;

  }

  using int_arg_iterator = unsigned *;

  using const_int_arg_iterator = const unsigned *;

  int_arg_iterator int_op_begin() { return IntOperands; }

  int_arg_iterator int_op_end() { return IntOperands + NumIntOperands; }

  const_int_arg_iterator int_op_begin() const { return IntOperands; }

  const_int_arg_iterator int_op_end() const {

    return IntOperands + NumIntOperands;

  }

  unsigned int_op_size() const { return NumIntOperands; }

  bool int_op_empty() const { return NumIntOperands == 0; }

  void int_op_push_back(unsigned IntOperand) {

    assert(NumIntOperands < MaxIntOperands &&

           "Tried to add too many int operands");

    assert(IntOperands && "Operands not allocated before pushing");

    IntOperands[NumIntOperands++] = IntOperand;

  }

  virtual void allocateIntOperands(BumpPtrAllocator &Allocator) {

    assert(!IntOperands && "Operands already allocated");

    IntOperands = Allocator.Allocate<unsigned>(MaxIntOperands);

  }

  bool equals(const Expression &Other) const override {

    if (!this->BasicExpression::equals(Other))

      return false;

    const AggregateValueExpression &OE = cast<AggregateValueExpression>(Other);

    return NumIntOperands == OE.NumIntOperands &&

           std::equal(int_op_begin(), int_op_end(), OE.int_op_begin());

  }

  hash_code getHashValue() const override {

    return hash_combine(this->BasicExpression::getHashValue(),

                        hash_combine_range(int_op_begin(), int_op_end()));

  }

  // Debugging support

  void printInternal(raw_ostream &OS, bool PrintEType) const override {

    if (PrintEType)

      OS << "ExpressionTypeAggregateValue, ";

    this->BasicExpression::printInternal(OS, false);

    OS << ", intoperands = {";

    for (unsigned i = 0, e = int_op_size(); i != e; ++i) {

      OS << "[" << i << "] = " << IntOperands[i] << "  ";

    }

    OS << "}";

  }

};

class int_op_inserter {

private:

  using Container = AggregateValueExpression;

  Container *AVE;

public:

  using iterator_category = std::output_iterator_tag;

  using value_type = void;

  using difference_type = void;

  using pointer = void;

  using reference = void;

  explicit int_op_inserter(AggregateValueExpression &E) : AVE(&E) {}

  explicit int_op_inserter(AggregateValueExpression *E) : AVE(E) {}

  int_op_inserter &operator=(unsigned int val) {

    AVE->int_op_push_back(val);

    return *this;

  }

  int_op_inserter &operator*() { return *this; }

  int_op_inserter &operator++() { return *this; }

  int_op_inserter &operator++(int) { return *this; }

};

class PHIExpression final : public BasicExpression {

private:

  BasicBlock *BB;

public:

  PHIExpression(unsigned NumOperands, BasicBlock *B)

      : BasicExpression(NumOperands, ET_Phi), BB(B) {}

  PHIExpression() = delete;

  PHIExpression(const PHIExpression &) = delete;

  PHIExpression &operator=(const PHIExpression &) = delete;

  ~PHIExpression() override;

  static bool classof(const Expression *EB) {

    return EB->getExpressionType() == ET_Phi;

  }

  bool equals(const Expression &Other) const override {

    if (!this->BasicExpression::equals(Other))

      return false;

    const PHIExpression &OE = cast<PHIExpression>(Other);

    return BB == OE.BB;

  }

  hash_code getHashValue() const override {

    return hash_combine(this->BasicExpression::getHashValue(), BB);

  }

  // Debugging support

  void printInternal(raw_ostream &OS, bool PrintEType) const override {

    if (PrintEType)

      OS << "ExpressionTypePhi, ";

    this->BasicExpression::printInternal(OS, false);

    OS << "bb = " << BB;

  }

};

class DeadExpression final : public Expression {

public:

  DeadExpression() : Expression(ET_Dead) {}

  DeadExpression(const DeadExpression &) = delete;

  DeadExpression &operator=(const DeadExpression &) = delete;

  static bool classof(const Expression *E) {

    return E->getExpressionType() == ET_Dead;

  }

};

class VariableExpression final : public Expression {

private:

  Value *VariableValue;

public:

  VariableExpression(Value *V) : Expression(ET_Variable), VariableValue(V) {}

  VariableExpression() = delete;

  VariableExpression(const VariableExpression &) = delete;

  VariableExpression &operator=(const VariableExpression &) = delete;

  static bool classof(const Expression *EB) {

    return EB->getExpressionType() == ET_Variable;

  }

  Value *getVariableValue() const { return VariableValue; }

  void setVariableValue(Value *V) { VariableValue = V; }

  bool equals(const Expression &Other) const override {

    const VariableExpression &OC = cast<VariableExpression>(Other);

    return VariableValue == OC.VariableValue;

  }

  hash_code getHashValue() const override {

    return hash_combine(this->Expression::getHashValue(),

                        VariableValue->getType(), VariableValue);

  }

  // Debugging support

  void printInternal(raw_ostream &OS, bool PrintEType) const override {

    if (PrintEType)

      OS << "ExpressionTypeVariable, ";

    this->Expression::printInternal(OS, false);

    OS << " variable = " << *VariableValue;

  }

};

class ConstantExpression final : public Expression {

private:

  Constant *ConstantValue = nullptr;

public:

  ConstantExpression() : Expression(ET_Constant) {}

  ConstantExpression(Constant *constantValue)

      : Expression(ET_Constant), ConstantValue(constantValue) {}

  ConstantExpression(const ConstantExpression &) = delete;

  ConstantExpression &operator=(const ConstantExpression &) = delete;

  static bool classof(const Expression *EB) {

    return EB->getExpressionType() == ET_Constant;

  }

  Constant *getConstantValue() const { return ConstantValue; }

  void setConstantValue(Constant *V) { ConstantValue = V; }

  bool equals(const Expression &Other) const override {

    const ConstantExpression &OC = cast<ConstantExpression>(Other);

    return ConstantValue == OC.ConstantValue;

  }

  hash_code getHashValue() const override {

    return hash_combine(this->Expression::getHashValue(),

                        ConstantValue->getType(), ConstantValue);

  }

  // Debugging support

  void printInternal(raw_ostream &OS, bool PrintEType) const override {

    if (PrintEType)

      OS << "ExpressionTypeConstant, ";

    this->Expression::printInternal(OS, false);

    OS << " constant = " << *ConstantValue;

  }

};

class UnknownExpression final : public Expression {

private:

  Instruction *Inst;

public:

  UnknownExpression(Instruction *I) : Expression(ET_Unknown), Inst(I) {}

  UnknownExpression() = delete;

  UnknownExpression(const UnknownExpression &) = delete;

  UnknownExpression &operator=(const UnknownExpression &) = delete;

  static bool classof(const Expression *EB) {

    return EB->getExpressionType() == ET_Unknown;

  }

  Instruction *getInstruction() const { return Inst; }

  void setInstruction(Instruction *I) { Inst = I; }

  bool equals(const Expression &Other) const override {

    const auto &OU = cast<UnknownExpression>(Other);

    return Inst == OU.Inst;

  }

  hash_code getHashValue() const override {

    return hash_combine(this->Expression::getHashValue(), Inst);

  }

  // Debugging support

  void printInternal(raw_ostream &OS, bool PrintEType) const override {

    if (PrintEType)

      OS << "ExpressionTypeUnknown, ";

    this->Expression::printInternal(OS, false);

    OS << " inst = " << *Inst;

  }

};

} // end namespace GVNExpression

} // end namespace llvm

#endif // LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H