contrib/llvm/include/llvm/Transforms/Scalar/GVNExpression.h

   1 //======- GVNExpression.h - GVN Expression classes -------*- C++ -*-==-------=//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 /// \file
  10 ///
  11 /// The header file for the GVN pass that contains expression handling
  12 /// classes
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H
  17 #define LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H
  18
  19 #include "llvm/ADT/Hashing.h"
  20 #include "llvm/IR/Constant.h"
  21 #include "llvm/IR/Instructions.h"
  22 #include "llvm/IR/Value.h"
  23 #include "llvm/Support/Allocator.h"
  24 #include "llvm/Support/ArrayRecycler.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 #include "llvm/Transforms/Utils/MemorySSA.h"
  28 #include <algorithm>
  29
  30 namespace llvm {
  31 class MemoryAccess;
  32
  33 namespace GVNExpression {
  34
  35 enum ExpressionType {
  36   ET_Base,
  37   ET_Constant,
  38   ET_Variable,
  39   ET_Unknown,
  40   ET_BasicStart,
  41   ET_Basic,
  42   ET_Call,
  43   ET_AggregateValue,
  44   ET_Phi,
  45   ET_Load,
  46   ET_Store,
  47   ET_BasicEnd
  48 };
  49
  50 class Expression {
  51 private:
  52   ExpressionType EType;
  53   unsigned Opcode;
  54
  55 public:
  56   Expression(const Expression &) = delete;
  57   Expression(ExpressionType ET = ET_Base, unsigned O = ~2U)
  58       : EType(ET), Opcode(O) {}
  59   void operator=(const Expression &) = delete;
  60   virtual ~Expression();
  61
  62   static unsigned getEmptyKey() { return ~0U; }
  63   static unsigned getTombstoneKey() { return ~1U; }
  64
  65   bool operator==(const Expression &Other) const {
  66     if (getOpcode() != Other.getOpcode())
  67       return false;
  68     if (getOpcode() == getEmptyKey() || getOpcode() == getTombstoneKey())
  69       return true;
  70     // Compare the expression type for anything but load and store.
  71     // For load and store we set the opcode to zero.
  72     // This is needed for load coercion.
  73     if (getExpressionType() != ET_Load && getExpressionType() != ET_Store &&
  74         getExpressionType() != Other.getExpressionType())
  75       return false;
  76
  77     return equals(Other);
  78   }
  79
  80   virtual bool equals(const Expression &Other) const { return true; }
  81
  82   unsigned getOpcode() const { return Opcode; }
  83   void setOpcode(unsigned opcode) { Opcode = opcode; }
  84   ExpressionType getExpressionType() const { return EType; }
  85
  86   virtual hash_code getHashValue() const {
  87     return hash_combine(getExpressionType(), getOpcode());
  88   }
  89
  90   //
  91   // Debugging support
  92   //
  93   virtual void printInternal(raw_ostream &OS, bool PrintEType) const {
  94     if (PrintEType)
  95       OS << "etype = " << getExpressionType() << ",";
  96     OS << "opcode = " << getOpcode() << ", ";
  97   }
  98
  99   void print(raw_ostream &OS) const {
 100     OS << "{ ";
 101     printInternal(OS, true);
 102     OS << "}";
 103   }
 104   void dump() const { print(dbgs()); }
 105 };
 106
 107 inline raw_ostream &operator<<(raw_ostream &OS, const Expression &E) {
 108   E.print(OS);
 109   return OS;
 110 }
 111
 112 class BasicExpression : public Expression {
 113 private:
 114   typedef ArrayRecycler<Value *> RecyclerType;
 115   typedef RecyclerType::Capacity RecyclerCapacity;
 116   Value **Operands;
 117   unsigned MaxOperands;
 118   unsigned NumOperands;
 119   Type *ValueType;
 120
 121 public:
 122   static bool classof(const Expression *EB) {
 123     ExpressionType ET = EB->getExpressionType();
 124     return ET > ET_BasicStart && ET < ET_BasicEnd;
 125   }
 126
 127   BasicExpression(unsigned NumOperands)
 128       : BasicExpression(NumOperands, ET_Basic) {}
 129   BasicExpression(unsigned NumOperands, ExpressionType ET)
 130       : Expression(ET), Operands(nullptr), MaxOperands(NumOperands),
 131         NumOperands(0), ValueType(nullptr) {}
 132   virtual ~BasicExpression() override;
 133   void operator=(const BasicExpression &) = delete;
 134   BasicExpression(const BasicExpression &) = delete;
 135   BasicExpression() = delete;
 136
 137   /// \brief Swap two operands. Used during GVN to put commutative operands in
 138   /// order.
 139   void swapOperands(unsigned First, unsigned Second) {
 140     std::swap(Operands[First], Operands[Second]);
 141   }
 142
 143   Value *getOperand(unsigned N) const {
 144     assert(Operands && "Operands not allocated");
 145     assert(N < NumOperands && "Operand out of range");
 146     return Operands[N];
 147   }
 148
 149   void setOperand(unsigned N, Value *V) {
 150     assert(Operands && "Operands not allocated before setting");
 151     assert(N < NumOperands && "Operand out of range");
 152     Operands[N] = V;
 153   }
 154
 155   unsigned getNumOperands() const { return NumOperands; }
 156
 157   typedef Value **op_iterator;
 158   typedef Value *const *const_op_iterator;
 159   op_iterator op_begin() { return Operands; }
 160   op_iterator op_end() { return Operands + NumOperands; }
 161   const_op_iterator op_begin() const { return Operands; }
 162   const_op_iterator op_end() const { return Operands + NumOperands; }
 163   iterator_range<op_iterator> operands() {
 164     return iterator_range<op_iterator>(op_begin(), op_end());
 165   }
 166   iterator_range<const_op_iterator> operands() const {
 167     return iterator_range<const_op_iterator>(op_begin(), op_end());
 168   }
 169
 170   void op_push_back(Value *Arg) {
 171     assert(NumOperands < MaxOperands && "Tried to add too many operands");
 172     assert(Operands && "Operandss not allocated before pushing");
 173     Operands[NumOperands++] = Arg;
 174   }
 175   bool op_empty() const { return getNumOperands() == 0; }
 176
 177   void allocateOperands(RecyclerType &Recycler, BumpPtrAllocator &Allocator) {
 178     assert(!Operands && "Operands already allocated");
 179     Operands = Recycler.allocate(RecyclerCapacity::get(MaxOperands), Allocator);
 180   }
 181   void deallocateOperands(RecyclerType &Recycler) {
 182     Recycler.deallocate(RecyclerCapacity::get(MaxOperands), Operands);
 183   }
 184
 185   void setType(Type *T) { ValueType = T; }
 186   Type *getType() const { return ValueType; }
 187
 188   virtual bool equals(const Expression &Other) const override {
 189     if (getOpcode() != Other.getOpcode())
 190       return false;
 191
 192     const auto &OE = cast<BasicExpression>(Other);
 193     return getType() == OE.getType() && NumOperands == OE.NumOperands &&
 194            std::equal(op_begin(), op_end(), OE.op_begin());
 195   }
 196
 197   virtual hash_code getHashValue() const override {
 198     return hash_combine(getExpressionType(), getOpcode(), ValueType,
 199                         hash_combine_range(op_begin(), op_end()));
 200   }
 201
 202   //
 203   // Debugging support
 204   //
 205   virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
 206     if (PrintEType)
 207       OS << "ExpressionTypeBasic, ";
 208
 209     this->Expression::printInternal(OS, false);
 210     OS << "operands = {";
 211     for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 212       OS << "[" << i << "] = ";
 213       Operands[i]->printAsOperand(OS);
 214       OS << "  ";
 215     }
 216     OS << "} ";
 217   }
 218 };
 219 class op_inserter
 220     : public std::iterator<std::output_iterator_tag, void, void, void, void> {
 221 private:
 222   typedef BasicExpression Container;
 223   Container *BE;
 224
 225 public:
 226   explicit op_inserter(BasicExpression &E) : BE(&E) {}
 227   explicit op_inserter(BasicExpression *E) : BE(E) {}
 228
 229   op_inserter &operator=(Value *val) {
 230     BE->op_push_back(val);
 231     return *this;
 232   }
 233   op_inserter &operator*() { return *this; }
 234   op_inserter &operator++() { return *this; }
 235   op_inserter &operator++(int) { return *this; }
 236 };
 237
 238 class CallExpression final : public BasicExpression {
 239 private:
 240   CallInst *Call;
 241   MemoryAccess *DefiningAccess;
 242
 243 public:
 244   static bool classof(const Expression *EB) {
 245     return EB->getExpressionType() == ET_Call;
 246   }
 247
 248   CallExpression(unsigned NumOperands, CallInst *C, MemoryAccess *DA)
 249       : BasicExpression(NumOperands, ET_Call), Call(C), DefiningAccess(DA) {}
 250   void operator=(const CallExpression &) = delete;
 251   CallExpression(const CallExpression &) = delete;
 252   CallExpression() = delete;
 253   virtual ~CallExpression() override;
 254
 255   virtual bool equals(const Expression &Other) const override {
 256     if (!this->BasicExpression::equals(Other))
 257       return false;
 258     const auto &OE = cast<CallExpression>(Other);
 259     return DefiningAccess == OE.DefiningAccess;
 260   }
 261
 262   virtual hash_code getHashValue() const override {
 263     return hash_combine(this->BasicExpression::getHashValue(), DefiningAccess);
 264   }
 265
 266   //
 267   // Debugging support
 268   //
 269   virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
 270     if (PrintEType)
 271       OS << "ExpressionTypeCall, ";
 272     this->BasicExpression::printInternal(OS, false);
 273     OS << " represents call at " << Call;
 274   }
 275 };
 276
 277 class LoadExpression final : public BasicExpression {
 278 private:
 279   LoadInst *Load;
 280   MemoryAccess *DefiningAccess;
 281   unsigned Alignment;
 282
 283 public:
 284   static bool classof(const Expression *EB) {
 285     return EB->getExpressionType() == ET_Load;
 286   }
 287
 288   LoadExpression(unsigned NumOperands, LoadInst *L, MemoryAccess *DA)
 289       : LoadExpression(ET_Load, NumOperands, L, DA) {}
 290   LoadExpression(enum ExpressionType EType, unsigned NumOperands, LoadInst *L,
 291                  MemoryAccess *DA)
 292       : BasicExpression(NumOperands, EType), Load(L), DefiningAccess(DA) {
 293     Alignment = L ? L->getAlignment() : 0;
 294   }
 295   void operator=(const LoadExpression &) = delete;
 296   LoadExpression(const LoadExpression &) = delete;
 297   LoadExpression() = delete;
 298   virtual ~LoadExpression() override;
 299
 300   LoadInst *getLoadInst() const { return Load; }
 301   void setLoadInst(LoadInst *L) { Load = L; }
 302
 303   MemoryAccess *getDefiningAccess() const { return DefiningAccess; }
 304   void setDefiningAccess(MemoryAccess *MA) { DefiningAccess = MA; }
 305   unsigned getAlignment() const { return Alignment; }
 306   void setAlignment(unsigned Align) { Alignment = Align; }
 307
 308   virtual bool equals(const Expression &Other) const override;
 309
 310   virtual hash_code getHashValue() const override {
 311     return hash_combine(getOpcode(), getType(), DefiningAccess,
 312                         hash_combine_range(op_begin(), op_end()));
 313   }
 314
 315   //
 316   // Debugging support
 317   //
 318   virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
 319     if (PrintEType)
 320       OS << "ExpressionTypeLoad, ";
 321     this->BasicExpression::printInternal(OS, false);
 322     OS << " represents Load at " << Load;
 323     OS << " with DefiningAccess " << *DefiningAccess;
 324   }
 325 };
 326
 327 class StoreExpression final : public BasicExpression {
 328 private:
 329   StoreInst *Store;
 330   MemoryAccess *DefiningAccess;
 331
 332 public:
 333   static bool classof(const Expression *EB) {
 334     return EB->getExpressionType() == ET_Store;
 335   }
 336
 337   StoreExpression(unsigned NumOperands, StoreInst *S, MemoryAccess *DA)
 338       : BasicExpression(NumOperands, ET_Store), Store(S), DefiningAccess(DA) {}
 339   void operator=(const StoreExpression &) = delete;
 340   StoreExpression(const StoreExpression &) = delete;
 341   StoreExpression() = delete;
 342   virtual ~StoreExpression() override;
 343
 344   StoreInst *getStoreInst() const { return Store; }
 345   MemoryAccess *getDefiningAccess() const { return DefiningAccess; }
 346
 347   virtual bool equals(const Expression &Other) const override;
 348
 349   virtual hash_code getHashValue() const override {
 350     return hash_combine(getOpcode(), getType(), DefiningAccess,
 351                         hash_combine_range(op_begin(), op_end()));
 352   }
 353
 354   //
 355   // Debugging support
 356   //
 357   virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
 358     if (PrintEType)
 359       OS << "ExpressionTypeStore, ";
 360     this->BasicExpression::printInternal(OS, false);
 361     OS << " represents Store at " << Store;
 362     OS << " with DefiningAccess " << *DefiningAccess;
 363   }
 364 };
 365
 366 class AggregateValueExpression final : public BasicExpression {
 367 private:
 368   unsigned MaxIntOperands;
 369   unsigned NumIntOperands;
 370   unsigned *IntOperands;
 371
 372 public:
 373   static bool classof(const Expression *EB) {
 374     return EB->getExpressionType() == ET_AggregateValue;
 375   }
 376
 377   AggregateValueExpression(unsigned NumOperands, unsigned NumIntOperands)
 378       : BasicExpression(NumOperands, ET_AggregateValue),
 379         MaxIntOperands(NumIntOperands), NumIntOperands(0),
 380         IntOperands(nullptr) {}
 381
 382   void operator=(const AggregateValueExpression &) = delete;
 383   AggregateValueExpression(const AggregateValueExpression &) = delete;
 384   AggregateValueExpression() = delete;
 385   virtual ~AggregateValueExpression() override;
 386
 387   typedef unsigned *int_arg_iterator;
 388   typedef const unsigned *const_int_arg_iterator;
 389
 390   int_arg_iterator int_op_begin() { return IntOperands; }
 391   int_arg_iterator int_op_end() { return IntOperands + NumIntOperands; }
 392   const_int_arg_iterator int_op_begin() const { return IntOperands; }
 393   const_int_arg_iterator int_op_end() const {
 394     return IntOperands + NumIntOperands;
 395   }
 396   unsigned int_op_size() const { return NumIntOperands; }
 397   bool int_op_empty() const { return NumIntOperands == 0; }
 398   void int_op_push_back(unsigned IntOperand) {
 399     assert(NumIntOperands < MaxIntOperands &&
 400            "Tried to add too many int operands");
 401     assert(IntOperands && "Operands not allocated before pushing");
 402     IntOperands[NumIntOperands++] = IntOperand;
 403   }
 404
 405   virtual void allocateIntOperands(BumpPtrAllocator &Allocator) {
 406     assert(!IntOperands && "Operands already allocated");
 407     IntOperands = Allocator.Allocate<unsigned>(MaxIntOperands);
 408   }
 409
 410   virtual bool equals(const Expression &Other) const override {
 411     if (!this->BasicExpression::equals(Other))
 412       return false;
 413     const AggregateValueExpression &OE = cast<AggregateValueExpression>(Other);
 414     return NumIntOperands == OE.NumIntOperands &&
 415            std::equal(int_op_begin(), int_op_end(), OE.int_op_begin());
 416   }
 417
 418   virtual hash_code getHashValue() const override {
 419     return hash_combine(this->BasicExpression::getHashValue(),
 420                         hash_combine_range(int_op_begin(), int_op_end()));
 421   }
 422
 423   //
 424   // Debugging support
 425   //
 426   virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
 427     if (PrintEType)
 428       OS << "ExpressionTypeAggregateValue, ";
 429     this->BasicExpression::printInternal(OS, false);
 430     OS << ", intoperands = {";
 431     for (unsigned i = 0, e = int_op_size(); i != e; ++i) {
 432       OS << "[" << i << "] = " << IntOperands[i] << "  ";
 433     }
 434     OS << "}";
 435   }
 436 };
 437 class int_op_inserter
 438     : public std::iterator<std::output_iterator_tag, void, void, void, void> {
 439 private:
 440   typedef AggregateValueExpression Container;
 441   Container *AVE;
 442
 443 public:
 444   explicit int_op_inserter(AggregateValueExpression &E) : AVE(&E) {}
 445   explicit int_op_inserter(AggregateValueExpression *E) : AVE(E) {}
 446   int_op_inserter &operator=(unsigned int val) {
 447     AVE->int_op_push_back(val);
 448     return *this;
 449   }
 450   int_op_inserter &operator*() { return *this; }
 451   int_op_inserter &operator++() { return *this; }
 452   int_op_inserter &operator++(int) { return *this; }
 453 };
 454
 455 class PHIExpression final : public BasicExpression {
 456 private:
 457   BasicBlock *BB;
 458
 459 public:
 460   static bool classof(const Expression *EB) {
 461     return EB->getExpressionType() == ET_Phi;
 462   }
 463
 464   PHIExpression(unsigned NumOperands, BasicBlock *B)
 465       : BasicExpression(NumOperands, ET_Phi), BB(B) {}
 466   void operator=(const PHIExpression &) = delete;
 467   PHIExpression(const PHIExpression &) = delete;
 468   PHIExpression() = delete;
 469   virtual ~PHIExpression() override;
 470
 471   virtual bool equals(const Expression &Other) const override {
 472     if (!this->BasicExpression::equals(Other))
 473       return false;
 474     const PHIExpression &OE = cast<PHIExpression>(Other);
 475     return BB == OE.BB;
 476   }
 477
 478   virtual hash_code getHashValue() const override {
 479     return hash_combine(this->BasicExpression::getHashValue(), BB);
 480   }
 481
 482   //
 483   // Debugging support
 484   //
 485   virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
 486     if (PrintEType)
 487       OS << "ExpressionTypePhi, ";
 488     this->BasicExpression::printInternal(OS, false);
 489     OS << "bb = " << BB;
 490   }
 491 };
 492
 493 class VariableExpression final : public Expression {
 494 private:
 495   Value *VariableValue;
 496
 497 public:
 498   static bool classof(const Expression *EB) {
 499     return EB->getExpressionType() == ET_Variable;
 500   }
 501
 502   VariableExpression(Value *V) : Expression(ET_Variable), VariableValue(V) {}
 503   void operator=(const VariableExpression &) = delete;
 504   VariableExpression(const VariableExpression &) = delete;
 505   VariableExpression() = delete;
 506
 507   Value *getVariableValue() const { return VariableValue; }
 508   void setVariableValue(Value *V) { VariableValue = V; }
 509   virtual bool equals(const Expression &Other) const override {
 510     const VariableExpression &OC = cast<VariableExpression>(Other);
 511     return VariableValue == OC.VariableValue;
 512   }
 513
 514   virtual hash_code getHashValue() const override {
 515     return hash_combine(getExpressionType(), VariableValue->getType(),
 516                         VariableValue);
 517   }
 518
 519   //
 520   // Debugging support
 521   //
 522   virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
 523     if (PrintEType)
 524       OS << "ExpressionTypeVariable, ";
 525     this->Expression::printInternal(OS, false);
 526     OS << " variable = " << *VariableValue;
 527   }
 528 };
 529
 530 class ConstantExpression final : public Expression {
 531 private:
 532   Constant *ConstantValue;
 533
 534 public:
 535   static bool classof(const Expression *EB) {
 536     return EB->getExpressionType() == ET_Constant;
 537   }
 538
 539   ConstantExpression() : Expression(ET_Constant), ConstantValue(NULL) {}
 540   ConstantExpression(Constant *constantValue)
 541       : Expression(ET_Constant), ConstantValue(constantValue) {}
 542   void operator=(const ConstantExpression &) = delete;
 543   ConstantExpression(const ConstantExpression &) = delete;
 544
 545   Constant *getConstantValue() const { return ConstantValue; }
 546   void setConstantValue(Constant *V) { ConstantValue = V; }
 547
 548   virtual bool equals(const Expression &Other) const override {
 549     const ConstantExpression &OC = cast<ConstantExpression>(Other);
 550     return ConstantValue == OC.ConstantValue;
 551   }
 552
 553   virtual hash_code getHashValue() const override {
 554     return hash_combine(getExpressionType(), ConstantValue->getType(),
 555                         ConstantValue);
 556   }
 557
 558   //
 559   // Debugging support
 560   //
 561   virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
 562     if (PrintEType)
 563       OS << "ExpressionTypeConstant, ";
 564     this->Expression::printInternal(OS, false);
 565     OS << " constant = " << *ConstantValue;
 566   }
 567 };
 568
 569 class UnknownExpression final : public Expression {
 570 private:
 571   Instruction *Inst;
 572
 573 public:
 574   static bool classof(const Expression *EB) {
 575     return EB->getExpressionType() == ET_Unknown;
 576   }
 577
 578   UnknownExpression(Instruction *I) : Expression(ET_Unknown), Inst(I) {}
 579   void operator=(const UnknownExpression &) = delete;
 580   UnknownExpression(const UnknownExpression &) = delete;
 581   UnknownExpression() = delete;
 582
 583   Instruction *getInstruction() const { return Inst; }
 584   void setInstruction(Instruction *I) { Inst = I; }
 585   virtual bool equals(const Expression &Other) const override {
 586     const auto &OU = cast<UnknownExpression>(Other);
 587     return Inst == OU.Inst;
 588   }
 589   virtual hash_code getHashValue() const override {
 590     return hash_combine(getExpressionType(), Inst);
 591   }
 592   //
 593   // Debugging support
 594   //
 595   virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
 596     if (PrintEType)
 597       OS << "ExpressionTypeUnknown, ";
 598     this->Expression::printInternal(OS, false);
 599     OS << " inst = " << *Inst;
 600   }
 601 };
 602 }
 603 }
 604
 605 #endif