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