contrib/llvm/lib/Transforms/Scalar/GVNSink.cpp

   1 //===- GVNSink.cpp - sink expressions into successors ---------------------===//
   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 //
  10 /// \file GVNSink.cpp
  11 /// This pass attempts to sink instructions into successors, reducing static
  12 /// instruction count and enabling if-conversion.
  13 ///
  14 /// We use a variant of global value numbering to decide what can be sunk.
  15 /// Consider:
  16 ///
  17 /// [ %a1 = add i32 %b, 1  ]   [ %c1 = add i32 %d, 1  ]
  18 /// [ %a2 = xor i32 %a1, 1 ]   [ %c2 = xor i32 %c1, 1 ]
  19 ///                  \           /
  20 ///            [ %e = phi i32 %a2, %c2 ]
  21 ///            [ add i32 %e, 4         ]
  22 ///
  23 ///
  24 /// GVN would number %a1 and %c1 differently because they compute different
  25 /// results - the VN of an instruction is a function of its opcode and the
  26 /// transitive closure of its operands. This is the key property for hoisting
  27 /// and CSE.
  28 ///
  29 /// What we want when sinking however is for a numbering that is a function of
  30 /// the *uses* of an instruction, which allows us to answer the question "if I
  31 /// replace %a1 with %c1, will it contribute in an equivalent way to all
  32 /// successive instructions?". The PostValueTable class in GVN provides this
  33 /// mapping.
  34 //
  35 //===----------------------------------------------------------------------===//
  36
  37 #include "llvm/ADT/ArrayRef.h"
  38 #include "llvm/ADT/DenseMap.h"
  39 #include "llvm/ADT/DenseMapInfo.h"
  40 #include "llvm/ADT/DenseSet.h"
  41 #include "llvm/ADT/Hashing.h"
  42 #include "llvm/ADT/None.h"
  43 #include "llvm/ADT/Optional.h"
  44 #include "llvm/ADT/PostOrderIterator.h"
  45 #include "llvm/ADT/STLExtras.h"
  46 #include "llvm/ADT/SmallPtrSet.h"
  47 #include "llvm/ADT/SmallVector.h"
  48 #include "llvm/ADT/Statistic.h"
  49 #include "llvm/ADT/StringExtras.h"
  50 #include "llvm/Analysis/GlobalsModRef.h"
  51 #include "llvm/Transforms/Utils/Local.h"
  52 #include "llvm/IR/BasicBlock.h"
  53 #include "llvm/IR/CFG.h"
  54 #include "llvm/IR/Constants.h"
  55 #include "llvm/IR/Function.h"
  56 #include "llvm/IR/InstrTypes.h"
  57 #include "llvm/IR/Instruction.h"
  58 #include "llvm/IR/Instructions.h"
  59 #include "llvm/IR/PassManager.h"
  60 #include "llvm/IR/Type.h"
  61 #include "llvm/IR/Use.h"
  62 #include "llvm/IR/Value.h"
  63 #include "llvm/Pass.h"
  64 #include "llvm/Support/Allocator.h"
  65 #include "llvm/Support/ArrayRecycler.h"
  66 #include "llvm/Support/AtomicOrdering.h"
  67 #include "llvm/Support/Casting.h"
  68 #include "llvm/Support/Compiler.h"
  69 #include "llvm/Support/Debug.h"
  70 #include "llvm/Support/raw_ostream.h"
  71 #include "llvm/Transforms/Scalar.h"
  72 #include "llvm/Transforms/Scalar/GVN.h"
  73 #include "llvm/Transforms/Scalar/GVNExpression.h"
  74 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  75 #include <algorithm>
  76 #include <cassert>
  77 #include <cstddef>
  78 #include <cstdint>
  79 #include <iterator>
  80 #include <utility>
  81
  82 using namespace llvm;
  83
  84 #define DEBUG_TYPE "gvn-sink"
  85
  86 STATISTIC(NumRemoved, "Number of instructions removed");
  87
  88 namespace llvm {
  89 namespace GVNExpression {
  90
  91 LLVM_DUMP_METHOD void Expression::dump() const {
  92   print(dbgs());
  93   dbgs() << "\n";
  94 }
  95
  96 } // end namespace GVNExpression
  97 } // end namespace llvm
  98
  99 namespace {
 100
 101 static bool isMemoryInst(const Instruction *I) {
 102   return isa<LoadInst>(I) || isa<StoreInst>(I) ||
 103          (isa<InvokeInst>(I) && !cast<InvokeInst>(I)->doesNotAccessMemory()) ||
 104          (isa<CallInst>(I) && !cast<CallInst>(I)->doesNotAccessMemory());
 105 }
 106
 107 /// Iterates through instructions in a set of blocks in reverse order from the
 108 /// first non-terminator. For example (assume all blocks have size n):
 109 ///   LockstepReverseIterator I([B1, B2, B3]);
 110 ///   *I-- = [B1[n], B2[n], B3[n]];
 111 ///   *I-- = [B1[n-1], B2[n-1], B3[n-1]];
 112 ///   *I-- = [B1[n-2], B2[n-2], B3[n-2]];
 113 ///   ...
 114 ///
 115 /// It continues until all blocks have been exhausted. Use \c getActiveBlocks()
 116 /// to
 117 /// determine which blocks are still going and the order they appear in the
 118 /// list returned by operator*.
 119 class LockstepReverseIterator {
 120   ArrayRef<BasicBlock *> Blocks;
 121   SmallSetVector<BasicBlock *, 4> ActiveBlocks;
 122   SmallVector<Instruction *, 4> Insts;
 123   bool Fail;
 124
 125 public:
 126   LockstepReverseIterator(ArrayRef<BasicBlock *> Blocks) : Blocks(Blocks) {
 127     reset();
 128   }
 129
 130   void reset() {
 131     Fail = false;
 132     ActiveBlocks.clear();
 133     for (BasicBlock *BB : Blocks)
 134       ActiveBlocks.insert(BB);
 135     Insts.clear();
 136     for (BasicBlock *BB : Blocks) {
 137       if (BB->size() <= 1) {
 138         // Block wasn't big enough - only contained a terminator.
 139         ActiveBlocks.remove(BB);
 140         continue;
 141       }
 142       Insts.push_back(BB->getTerminator()->getPrevNode());
 143     }
 144     if (Insts.empty())
 145       Fail = true;
 146   }
 147
 148   bool isValid() const { return !Fail; }
 149   ArrayRef<Instruction *> operator*() const { return Insts; }
 150
 151   // Note: This needs to return a SmallSetVector as the elements of
 152   // ActiveBlocks will be later copied to Blocks using std::copy. The
 153   // resultant order of elements in Blocks needs to be deterministic.
 154   // Using SmallPtrSet instead causes non-deterministic order while
 155   // copying. And we cannot simply sort Blocks as they need to match the
 156   // corresponding Values.
 157   SmallSetVector<BasicBlock *, 4> &getActiveBlocks() { return ActiveBlocks; }
 158
 159   void restrictToBlocks(SmallSetVector<BasicBlock *, 4> &Blocks) {
 160     for (auto II = Insts.begin(); II != Insts.end();) {
 161       if (std::find(Blocks.begin(), Blocks.end(), (*II)->getParent()) ==
 162           Blocks.end()) {
 163         ActiveBlocks.remove((*II)->getParent());
 164         II = Insts.erase(II);
 165       } else {
 166         ++II;
 167       }
 168     }
 169   }
 170
 171   void operator--() {
 172     if (Fail)
 173       return;
 174     SmallVector<Instruction *, 4> NewInsts;
 175     for (auto *Inst : Insts) {
 176       if (Inst == &Inst->getParent()->front())
 177         ActiveBlocks.remove(Inst->getParent());
 178       else
 179         NewInsts.push_back(Inst->getPrevNode());
 180     }
 181     if (NewInsts.empty()) {
 182       Fail = true;
 183       return;
 184     }
 185     Insts = NewInsts;
 186   }
 187 };
 188
 189 //===----------------------------------------------------------------------===//
 190
 191 /// Candidate solution for sinking. There may be different ways to
 192 /// sink instructions, differing in the number of instructions sunk,
 193 /// the number of predecessors sunk from and the number of PHIs
 194 /// required.
 195 struct SinkingInstructionCandidate {
 196   unsigned NumBlocks;
 197   unsigned NumInstructions;
 198   unsigned NumPHIs;
 199   unsigned NumMemoryInsts;
 200   int Cost = -1;
 201   SmallVector<BasicBlock *, 4> Blocks;
 202
 203   void calculateCost(unsigned NumOrigPHIs, unsigned NumOrigBlocks) {
 204     unsigned NumExtraPHIs = NumPHIs - NumOrigPHIs;
 205     unsigned SplitEdgeCost = (NumOrigBlocks > NumBlocks) ? 2 : 0;
 206     Cost = (NumInstructions * (NumBlocks - 1)) -
 207            (NumExtraPHIs *
 208             NumExtraPHIs) // PHIs are expensive, so make sure they're worth it.
 209            - SplitEdgeCost;
 210   }
 211
 212   bool operator>(const SinkingInstructionCandidate &Other) const {
 213     return Cost > Other.Cost;
 214   }
 215 };
 216
 217 #ifndef NDEBUG
 218 raw_ostream &operator<<(raw_ostream &OS, const SinkingInstructionCandidate &C) {
 219   OS << "<Candidate Cost=" << C.Cost << " #Blocks=" << C.NumBlocks
 220      << " #Insts=" << C.NumInstructions << " #PHIs=" << C.NumPHIs << ">";
 221   return OS;
 222 }
 223 #endif
 224
 225 //===----------------------------------------------------------------------===//
 226
 227 /// Describes a PHI node that may or may not exist. These track the PHIs
 228 /// that must be created if we sunk a sequence of instructions. It provides
 229 /// a hash function for efficient equality comparisons.
 230 class ModelledPHI {
 231   SmallVector<Value *, 4> Values;
 232   SmallVector<BasicBlock *, 4> Blocks;
 233
 234 public:
 235   ModelledPHI() = default;
 236
 237   ModelledPHI(const PHINode *PN) {
 238     // BasicBlock comes first so we sort by basic block pointer order, then by value pointer order.
 239     SmallVector<std::pair<BasicBlock *, Value *>, 4> Ops;
 240     for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I)
 241       Ops.push_back({PN->getIncomingBlock(I), PN->getIncomingValue(I)});
 242     llvm::sort(Ops.begin(), Ops.end());
 243     for (auto &P : Ops) {
 244       Blocks.push_back(P.first);
 245       Values.push_back(P.second);
 246     }
 247   }
 248
 249   /// Create a dummy ModelledPHI that will compare unequal to any other ModelledPHI
 250   /// without the same ID.
 251   /// \note This is specifically for DenseMapInfo - do not use this!
 252   static ModelledPHI createDummy(size_t ID) {
 253     ModelledPHI M;
 254     M.Values.push_back(reinterpret_cast<Value*>(ID));
 255     return M;
 256   }
 257
 258   /// Create a PHI from an array of incoming values and incoming blocks.
 259   template <typename VArray, typename BArray>
 260   ModelledPHI(const VArray &V, const BArray &B) {
 261     std::copy(V.begin(), V.end(), std::back_inserter(Values));
 262     std::copy(B.begin(), B.end(), std::back_inserter(Blocks));
 263   }
 264
 265   /// Create a PHI from [I[OpNum] for I in Insts].
 266   template <typename BArray>
 267   ModelledPHI(ArrayRef<Instruction *> Insts, unsigned OpNum, const BArray &B) {
 268     std::copy(B.begin(), B.end(), std::back_inserter(Blocks));
 269     for (auto *I : Insts)
 270       Values.push_back(I->getOperand(OpNum));
 271   }
 272
 273   /// Restrict the PHI's contents down to only \c NewBlocks.
 274   /// \c NewBlocks must be a subset of \c this->Blocks.
 275   void restrictToBlocks(const SmallSetVector<BasicBlock *, 4> &NewBlocks) {
 276     auto BI = Blocks.begin();
 277     auto VI = Values.begin();
 278     while (BI != Blocks.end()) {
 279       assert(VI != Values.end());
 280       if (std::find(NewBlocks.begin(), NewBlocks.end(), *BI) ==
 281           NewBlocks.end()) {
 282         BI = Blocks.erase(BI);
 283         VI = Values.erase(VI);
 284       } else {
 285         ++BI;
 286         ++VI;
 287       }
 288     }
 289     assert(Blocks.size() == NewBlocks.size());
 290   }
 291
 292   ArrayRef<Value *> getValues() const { return Values; }
 293
 294   bool areAllIncomingValuesSame() const {
 295     return llvm::all_of(Values, [&](Value *V) { return V == Values[0]; });
 296   }
 297
 298   bool areAllIncomingValuesSameType() const {
 299     return llvm::all_of(
 300         Values, [&](Value *V) { return V->getType() == Values[0]->getType(); });
 301   }
 302
 303   bool areAnyIncomingValuesConstant() const {
 304     return llvm::any_of(Values, [&](Value *V) { return isa<Constant>(V); });
 305   }
 306
 307   // Hash functor
 308   unsigned hash() const {
 309       return (unsigned)hash_combine_range(Values.begin(), Values.end());
 310   }
 311
 312   bool operator==(const ModelledPHI &Other) const {
 313     return Values == Other.Values && Blocks == Other.Blocks;
 314   }
 315 };
 316
 317 template <typename ModelledPHI> struct DenseMapInfo {
 318   static inline ModelledPHI &getEmptyKey() {
 319     static ModelledPHI Dummy = ModelledPHI::createDummy(0);
 320     return Dummy;
 321   }
 322
 323   static inline ModelledPHI &getTombstoneKey() {
 324     static ModelledPHI Dummy = ModelledPHI::createDummy(1);
 325     return Dummy;
 326   }
 327
 328   static unsigned getHashValue(const ModelledPHI &V) { return V.hash(); }
 329
 330   static bool isEqual(const ModelledPHI &LHS, const ModelledPHI &RHS) {
 331     return LHS == RHS;
 332   }
 333 };
 334
 335 using ModelledPHISet = DenseSet<ModelledPHI, DenseMapInfo<ModelledPHI>>;
 336
 337 //===----------------------------------------------------------------------===//
 338 //                             ValueTable
 339 //===----------------------------------------------------------------------===//
 340 // This is a value number table where the value number is a function of the
 341 // *uses* of a value, rather than its operands. Thus, if VN(A) == VN(B) we know
 342 // that the program would be equivalent if we replaced A with PHI(A, B).
 343 //===----------------------------------------------------------------------===//
 344
 345 /// A GVN expression describing how an instruction is used. The operands
 346 /// field of BasicExpression is used to store uses, not operands.
 347 ///
 348 /// This class also contains fields for discriminators used when determining
 349 /// equivalence of instructions with sideeffects.
 350 class InstructionUseExpr : public GVNExpression::BasicExpression {
 351   unsigned MemoryUseOrder = -1;
 352   bool Volatile = false;
 353
 354 public:
 355   InstructionUseExpr(Instruction *I, ArrayRecycler<Value *> &R,
 356                      BumpPtrAllocator &A)
 357       : GVNExpression::BasicExpression(I->getNumUses()) {
 358     allocateOperands(R, A);
 359     setOpcode(I->getOpcode());
 360     setType(I->getType());
 361
 362     for (auto &U : I->uses())
 363       op_push_back(U.getUser());
 364     llvm::sort(op_begin(), op_end());
 365   }
 366
 367   void setMemoryUseOrder(unsigned MUO) { MemoryUseOrder = MUO; }
 368   void setVolatile(bool V) { Volatile = V; }
 369
 370   hash_code getHashValue() const override {
 371     return hash_combine(GVNExpression::BasicExpression::getHashValue(),
 372                         MemoryUseOrder, Volatile);
 373   }
 374
 375   template <typename Function> hash_code getHashValue(Function MapFn) {
 376     hash_code H =
 377         hash_combine(getOpcode(), getType(), MemoryUseOrder, Volatile);
 378     for (auto *V : operands())
 379       H = hash_combine(H, MapFn(V));
 380     return H;
 381   }
 382 };
 383
 384 class ValueTable {
 385   DenseMap<Value *, uint32_t> ValueNumbering;
 386   DenseMap<GVNExpression::Expression *, uint32_t> ExpressionNumbering;
 387   DenseMap<size_t, uint32_t> HashNumbering;
 388   BumpPtrAllocator Allocator;
 389   ArrayRecycler<Value *> Recycler;
 390   uint32_t nextValueNumber = 1;
 391
 392   /// Create an expression for I based on its opcode and its uses. If I
 393   /// touches or reads memory, the expression is also based upon its memory
 394   /// order - see \c getMemoryUseOrder().
 395   InstructionUseExpr *createExpr(Instruction *I) {
 396     InstructionUseExpr *E =
 397         new (Allocator) InstructionUseExpr(I, Recycler, Allocator);
 398     if (isMemoryInst(I))
 399       E->setMemoryUseOrder(getMemoryUseOrder(I));
 400
 401     if (CmpInst *C = dyn_cast<CmpInst>(I)) {
 402       CmpInst::Predicate Predicate = C->getPredicate();
 403       E->setOpcode((C->getOpcode() << 8) | Predicate);
 404     }
 405     return E;
 406   }
 407
 408   /// Helper to compute the value number for a memory instruction
 409   /// (LoadInst/StoreInst), including checking the memory ordering and
 410   /// volatility.
 411   template <class Inst> InstructionUseExpr *createMemoryExpr(Inst *I) {
 412     if (isStrongerThanUnordered(I->getOrdering()) || I->isAtomic())
 413       return nullptr;
 414     InstructionUseExpr *E = createExpr(I);
 415     E->setVolatile(I->isVolatile());
 416     return E;
 417   }
 418
 419 public:
 420   ValueTable() = default;
 421
 422   /// Returns the value number for the specified value, assigning
 423   /// it a new number if it did not have one before.
 424   uint32_t lookupOrAdd(Value *V) {
 425     auto VI = ValueNumbering.find(V);
 426     if (VI != ValueNumbering.end())
 427       return VI->second;
 428
 429     if (!isa<Instruction>(V)) {
 430       ValueNumbering[V] = nextValueNumber;
 431       return nextValueNumber++;
 432     }
 433
 434     Instruction *I = cast<Instruction>(V);
 435     InstructionUseExpr *exp = nullptr;
 436     switch (I->getOpcode()) {
 437     case Instruction::Load:
 438       exp = createMemoryExpr(cast<LoadInst>(I));
 439       break;
 440     case Instruction::Store:
 441       exp = createMemoryExpr(cast<StoreInst>(I));
 442       break;
 443     case Instruction::Call:
 444     case Instruction::Invoke:
 445     case Instruction::Add:
 446     case Instruction::FAdd:
 447     case Instruction::Sub:
 448     case Instruction::FSub:
 449     case Instruction::Mul:
 450     case Instruction::FMul:
 451     case Instruction::UDiv:
 452     case Instruction::SDiv:
 453     case Instruction::FDiv:
 454     case Instruction::URem:
 455     case Instruction::SRem:
 456     case Instruction::FRem:
 457     case Instruction::Shl:
 458     case Instruction::LShr:
 459     case Instruction::AShr:
 460     case Instruction::And:
 461     case Instruction::Or:
 462     case Instruction::Xor:
 463     case Instruction::ICmp:
 464     case Instruction::FCmp:
 465     case Instruction::Trunc:
 466     case Instruction::ZExt:
 467     case Instruction::SExt:
 468     case Instruction::FPToUI:
 469     case Instruction::FPToSI:
 470     case Instruction::UIToFP:
 471     case Instruction::SIToFP:
 472     case Instruction::FPTrunc:
 473     case Instruction::FPExt:
 474     case Instruction::PtrToInt:
 475     case Instruction::IntToPtr:
 476     case Instruction::BitCast:
 477     case Instruction::Select:
 478     case Instruction::ExtractElement:
 479     case Instruction::InsertElement:
 480     case Instruction::ShuffleVector:
 481     case Instruction::InsertValue:
 482     case Instruction::GetElementPtr:
 483       exp = createExpr(I);
 484       break;
 485     default:
 486       break;
 487     }
 488
 489     if (!exp) {
 490       ValueNumbering[V] = nextValueNumber;
 491       return nextValueNumber++;
 492     }
 493
 494     uint32_t e = ExpressionNumbering[exp];
 495     if (!e) {
 496       hash_code H = exp->getHashValue([=](Value *V) { return lookupOrAdd(V); });
 497       auto I = HashNumbering.find(H);
 498       if (I != HashNumbering.end()) {
 499         e = I->second;
 500       } else {
 501         e = nextValueNumber++;
 502         HashNumbering[H] = e;
 503         ExpressionNumbering[exp] = e;
 504       }
 505     }
 506     ValueNumbering[V] = e;
 507     return e;
 508   }
 509
 510   /// Returns the value number of the specified value. Fails if the value has
 511   /// not yet been numbered.
 512   uint32_t lookup(Value *V) const {
 513     auto VI = ValueNumbering.find(V);
 514     assert(VI != ValueNumbering.end() && "Value not numbered?");
 515     return VI->second;
 516   }
 517
 518   /// Removes all value numberings and resets the value table.
 519   void clear() {
 520     ValueNumbering.clear();
 521     ExpressionNumbering.clear();
 522     HashNumbering.clear();
 523     Recycler.clear(Allocator);
 524     nextValueNumber = 1;
 525   }
 526
 527   /// \c Inst uses or touches memory. Return an ID describing the memory state
 528   /// at \c Inst such that if getMemoryUseOrder(I1) == getMemoryUseOrder(I2),
 529   /// the exact same memory operations happen after I1 and I2.
 530   ///
 531   /// This is a very hard problem in general, so we use domain-specific
 532   /// knowledge that we only ever check for equivalence between blocks sharing a
 533   /// single immediate successor that is common, and when determining if I1 ==
 534   /// I2 we will have already determined that next(I1) == next(I2). This
 535   /// inductive property allows us to simply return the value number of the next
 536   /// instruction that defines memory.
 537   uint32_t getMemoryUseOrder(Instruction *Inst) {
 538     auto *BB = Inst->getParent();
 539     for (auto I = std::next(Inst->getIterator()), E = BB->end();
 540          I != E && !I->isTerminator(); ++I) {
 541       if (!isMemoryInst(&*I))
 542         continue;
 543       if (isa<LoadInst>(&*I))
 544         continue;
 545       CallInst *CI = dyn_cast<CallInst>(&*I);
 546       if (CI && CI->onlyReadsMemory())
 547         continue;
 548       InvokeInst *II = dyn_cast<InvokeInst>(&*I);
 549       if (II && II->onlyReadsMemory())
 550         continue;
 551       return lookupOrAdd(&*I);
 552     }
 553     return 0;
 554   }
 555 };
 556
 557 //===----------------------------------------------------------------------===//
 558
 559 class GVNSink {
 560 public:
 561   GVNSink() = default;
 562
 563   bool run(Function &F) {
 564     LLVM_DEBUG(dbgs() << "GVNSink: running on function @" << F.getName()
 565                       << "\n");
 566
 567     unsigned NumSunk = 0;
 568     ReversePostOrderTraversal<Function*> RPOT(&F);
 569     for (auto *N : RPOT)
 570       NumSunk += sinkBB(N);
 571
 572     return NumSunk > 0;
 573   }
 574
 575 private:
 576   ValueTable VN;
 577
 578   bool isInstructionBlacklisted(Instruction *I) {
 579     // These instructions may change or break semantics if moved.
 580     if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) ||
 581         I->getType()->isTokenTy())
 582       return true;
 583     return false;
 584   }
 585
 586   /// The main heuristic function. Analyze the set of instructions pointed to by
 587   /// LRI and return a candidate solution if these instructions can be sunk, or
 588   /// None otherwise.
 589   Optional<SinkingInstructionCandidate> analyzeInstructionForSinking(
 590       LockstepReverseIterator &LRI, unsigned &InstNum, unsigned &MemoryInstNum,
 591       ModelledPHISet &NeededPHIs, SmallPtrSetImpl<Value *> &PHIContents);
 592
 593   /// Create a ModelledPHI for each PHI in BB, adding to PHIs.
 594   void analyzeInitialPHIs(BasicBlock *BB, ModelledPHISet &PHIs,
 595                           SmallPtrSetImpl<Value *> &PHIContents) {
 596     for (PHINode &PN : BB->phis()) {
 597       auto MPHI = ModelledPHI(&PN);
 598       PHIs.insert(MPHI);
 599       for (auto *V : MPHI.getValues())
 600         PHIContents.insert(V);
 601     }
 602   }
 603
 604   /// The main instruction sinking driver. Set up state and try and sink
 605   /// instructions into BBEnd from its predecessors.
 606   unsigned sinkBB(BasicBlock *BBEnd);
 607
 608   /// Perform the actual mechanics of sinking an instruction from Blocks into
 609   /// BBEnd, which is their only successor.
 610   void sinkLastInstruction(ArrayRef<BasicBlock *> Blocks, BasicBlock *BBEnd);
 611
 612   /// Remove PHIs that all have the same incoming value.
 613   void foldPointlessPHINodes(BasicBlock *BB) {
 614     auto I = BB->begin();
 615     while (PHINode *PN = dyn_cast<PHINode>(I++)) {
 616       if (!llvm::all_of(PN->incoming_values(), [&](const Value *V) {
 617             return V == PN->getIncomingValue(0);
 618           }))
 619         continue;
 620       if (PN->getIncomingValue(0) != PN)
 621         PN->replaceAllUsesWith(PN->getIncomingValue(0));
 622       else
 623         PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 624       PN->eraseFromParent();
 625     }
 626   }
 627 };
 628
 629 Optional<SinkingInstructionCandidate> GVNSink::analyzeInstructionForSinking(
 630   LockstepReverseIterator &LRI, unsigned &InstNum, unsigned &MemoryInstNum,
 631   ModelledPHISet &NeededPHIs, SmallPtrSetImpl<Value *> &PHIContents) {
 632   auto Insts = *LRI;
 633   LLVM_DEBUG(dbgs() << " -- Analyzing instruction set: [\n"; for (auto *I
 634                                                                   : Insts) {
 635     I->dump();
 636   } dbgs() << " ]\n";);
 637
 638   DenseMap<uint32_t, unsigned> VNums;
 639   for (auto *I : Insts) {
 640     uint32_t N = VN.lookupOrAdd(I);
 641     LLVM_DEBUG(dbgs() << " VN=" << Twine::utohexstr(N) << " for" << *I << "\n");
 642     if (N == ~0U)
 643       return None;
 644     VNums[N]++;
 645   }
 646   unsigned VNumToSink =
 647       std::max_element(VNums.begin(), VNums.end(),
 648                        [](const std::pair<uint32_t, unsigned> &I,
 649                           const std::pair<uint32_t, unsigned> &J) {
 650                          return I.second < J.second;
 651                        })
 652           ->first;
 653
 654   if (VNums[VNumToSink] == 1)
 655     // Can't sink anything!
 656     return None;
 657
 658   // Now restrict the number of incoming blocks down to only those with
 659   // VNumToSink.
 660   auto &ActivePreds = LRI.getActiveBlocks();
 661   unsigned InitialActivePredSize = ActivePreds.size();
 662   SmallVector<Instruction *, 4> NewInsts;
 663   for (auto *I : Insts) {
 664     if (VN.lookup(I) != VNumToSink)
 665       ActivePreds.remove(I->getParent());
 666     else
 667       NewInsts.push_back(I);
 668   }
 669   for (auto *I : NewInsts)
 670     if (isInstructionBlacklisted(I))
 671       return None;
 672
 673   // If we've restricted the incoming blocks, restrict all needed PHIs also
 674   // to that set.
 675   bool RecomputePHIContents = false;
 676   if (ActivePreds.size() != InitialActivePredSize) {
 677     ModelledPHISet NewNeededPHIs;
 678     for (auto P : NeededPHIs) {
 679       P.restrictToBlocks(ActivePreds);
 680       NewNeededPHIs.insert(P);
 681     }
 682     NeededPHIs = NewNeededPHIs;
 683     LRI.restrictToBlocks(ActivePreds);
 684     RecomputePHIContents = true;
 685   }
 686
 687   // The sunk instruction's results.
 688   ModelledPHI NewPHI(NewInsts, ActivePreds);
 689
 690   // Does sinking this instruction render previous PHIs redundant?
 691   if (NeededPHIs.find(NewPHI) != NeededPHIs.end()) {
 692     NeededPHIs.erase(NewPHI);
 693     RecomputePHIContents = true;
 694   }
 695
 696   if (RecomputePHIContents) {
 697     // The needed PHIs have changed, so recompute the set of all needed
 698     // values.
 699     PHIContents.clear();
 700     for (auto &PHI : NeededPHIs)
 701       PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end());
 702   }
 703
 704   // Is this instruction required by a later PHI that doesn't match this PHI?
 705   // if so, we can't sink this instruction.
 706   for (auto *V : NewPHI.getValues())
 707     if (PHIContents.count(V))
 708       // V exists in this PHI, but the whole PHI is different to NewPHI
 709       // (else it would have been removed earlier). We cannot continue
 710       // because this isn't representable.
 711       return None;
 712
 713   // Which operands need PHIs?
 714   // FIXME: If any of these fail, we should partition up the candidates to
 715   // try and continue making progress.
 716   Instruction *I0 = NewInsts[0];
 717   for (unsigned OpNum = 0, E = I0->getNumOperands(); OpNum != E; ++OpNum) {
 718     ModelledPHI PHI(NewInsts, OpNum, ActivePreds);
 719     if (PHI.areAllIncomingValuesSame())
 720       continue;
 721     if (!canReplaceOperandWithVariable(I0, OpNum))
 722       // We can 't create a PHI from this instruction!
 723       return None;
 724     if (NeededPHIs.count(PHI))
 725       continue;
 726     if (!PHI.areAllIncomingValuesSameType())
 727       return None;
 728     // Don't create indirect calls! The called value is the final operand.
 729     if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OpNum == E - 1 &&
 730         PHI.areAnyIncomingValuesConstant())
 731       return None;
 732
 733     NeededPHIs.reserve(NeededPHIs.size());
 734     NeededPHIs.insert(PHI);
 735     PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end());
 736   }
 737
 738   if (isMemoryInst(NewInsts[0]))
 739     ++MemoryInstNum;
 740
 741   SinkingInstructionCandidate Cand;
 742   Cand.NumInstructions = ++InstNum;
 743   Cand.NumMemoryInsts = MemoryInstNum;
 744   Cand.NumBlocks = ActivePreds.size();
 745   Cand.NumPHIs = NeededPHIs.size();
 746   for (auto *C : ActivePreds)
 747     Cand.Blocks.push_back(C);
 748
 749   return Cand;
 750 }
 751
 752 unsigned GVNSink::sinkBB(BasicBlock *BBEnd) {
 753   LLVM_DEBUG(dbgs() << "GVNSink: running on basic block ";
 754              BBEnd->printAsOperand(dbgs()); dbgs() << "\n");
 755   SmallVector<BasicBlock *, 4> Preds;
 756   for (auto *B : predecessors(BBEnd)) {
 757     auto *T = B->getTerminator();
 758     if (isa<BranchInst>(T) || isa<SwitchInst>(T))
 759       Preds.push_back(B);
 760     else
 761       return 0;
 762   }
 763   if (Preds.size() < 2)
 764     return 0;
 765   llvm::sort(Preds.begin(), Preds.end());
 766
 767   unsigned NumOrigPreds = Preds.size();
 768   // We can only sink instructions through unconditional branches.
 769   for (auto I = Preds.begin(); I != Preds.end();) {
 770     if ((*I)->getTerminator()->getNumSuccessors() != 1)
 771       I = Preds.erase(I);
 772     else
 773       ++I;
 774   }
 775
 776   LockstepReverseIterator LRI(Preds);
 777   SmallVector<SinkingInstructionCandidate, 4> Candidates;
 778   unsigned InstNum = 0, MemoryInstNum = 0;
 779   ModelledPHISet NeededPHIs;
 780   SmallPtrSet<Value *, 4> PHIContents;
 781   analyzeInitialPHIs(BBEnd, NeededPHIs, PHIContents);
 782   unsigned NumOrigPHIs = NeededPHIs.size();
 783
 784   while (LRI.isValid()) {
 785     auto Cand = analyzeInstructionForSinking(LRI, InstNum, MemoryInstNum,
 786                                              NeededPHIs, PHIContents);
 787     if (!Cand)
 788       break;
 789     Cand->calculateCost(NumOrigPHIs, Preds.size());
 790     Candidates.emplace_back(*Cand);
 791     --LRI;
 792   }
 793
 794   std::stable_sort(
 795       Candidates.begin(), Candidates.end(),
 796       [](const SinkingInstructionCandidate &A,
 797          const SinkingInstructionCandidate &B) { return A > B; });
 798   LLVM_DEBUG(dbgs() << " -- Sinking candidates:\n"; for (auto &C
 799                                                          : Candidates) dbgs()
 800                                                     << "  " << C << "\n";);
 801
 802   // Pick the top candidate, as long it is positive!
 803   if (Candidates.empty() || Candidates.front().Cost <= 0)
 804     return 0;
 805   auto C = Candidates.front();
 806
 807   LLVM_DEBUG(dbgs() << " -- Sinking: " << C << "\n");
 808   BasicBlock *InsertBB = BBEnd;
 809   if (C.Blocks.size() < NumOrigPreds) {
 810     LLVM_DEBUG(dbgs() << " -- Splitting edge to ";
 811                BBEnd->printAsOperand(dbgs()); dbgs() << "\n");
 812     InsertBB = SplitBlockPredecessors(BBEnd, C.Blocks, ".gvnsink.split");
 813     if (!InsertBB) {
 814       LLVM_DEBUG(dbgs() << " -- FAILED to split edge!\n");
 815       // Edge couldn't be split.
 816       return 0;
 817     }
 818   }
 819
 820   for (unsigned I = 0; I < C.NumInstructions; ++I)
 821     sinkLastInstruction(C.Blocks, InsertBB);
 822
 823   return C.NumInstructions;
 824 }
 825
 826 void GVNSink::sinkLastInstruction(ArrayRef<BasicBlock *> Blocks,
 827                                   BasicBlock *BBEnd) {
 828   SmallVector<Instruction *, 4> Insts;
 829   for (BasicBlock *BB : Blocks)
 830     Insts.push_back(BB->getTerminator()->getPrevNode());
 831   Instruction *I0 = Insts.front();
 832
 833   SmallVector<Value *, 4> NewOperands;
 834   for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) {
 835     bool NeedPHI = llvm::any_of(Insts, [&I0, O](const Instruction *I) {
 836       return I->getOperand(O) != I0->getOperand(O);
 837     });
 838     if (!NeedPHI) {
 839       NewOperands.push_back(I0->getOperand(O));
 840       continue;
 841     }
 842
 843     // Create a new PHI in the successor block and populate it.
 844     auto *Op = I0->getOperand(O);
 845     assert(!Op->getType()->isTokenTy() && "Can't PHI tokens!");
 846     auto *PN = PHINode::Create(Op->getType(), Insts.size(),
 847                                Op->getName() + ".sink", &BBEnd->front());
 848     for (auto *I : Insts)
 849       PN->addIncoming(I->getOperand(O), I->getParent());
 850     NewOperands.push_back(PN);
 851   }
 852
 853   // Arbitrarily use I0 as the new "common" instruction; remap its operands
 854   // and move it to the start of the successor block.
 855   for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O)
 856     I0->getOperandUse(O).set(NewOperands[O]);
 857   I0->moveBefore(&*BBEnd->getFirstInsertionPt());
 858
 859   // Update metadata and IR flags.
 860   for (auto *I : Insts)
 861     if (I != I0) {
 862       combineMetadataForCSE(I0, I);
 863       I0->andIRFlags(I);
 864     }
 865
 866   for (auto *I : Insts)
 867     if (I != I0)
 868       I->replaceAllUsesWith(I0);
 869   foldPointlessPHINodes(BBEnd);
 870
 871   // Finally nuke all instructions apart from the common instruction.
 872   for (auto *I : Insts)
 873     if (I != I0)
 874       I->eraseFromParent();
 875
 876   NumRemoved += Insts.size() - 1;
 877 }
 878
 879 ////////////////////////////////////////////////////////////////////////////////
 880 // Pass machinery / boilerplate
 881
 882 class GVNSinkLegacyPass : public FunctionPass {
 883 public:
 884   static char ID;
 885
 886   GVNSinkLegacyPass() : FunctionPass(ID) {
 887     initializeGVNSinkLegacyPassPass(*PassRegistry::getPassRegistry());
 888   }
 889
 890   bool runOnFunction(Function &F) override {
 891     if (skipFunction(F))
 892       return false;
 893     GVNSink G;
 894     return G.run(F);
 895   }
 896
 897   void getAnalysisUsage(AnalysisUsage &AU) const override {
 898     AU.addPreserved<GlobalsAAWrapperPass>();
 899   }
 900 };
 901
 902 } // end anonymous namespace
 903
 904 PreservedAnalyses GVNSinkPass::run(Function &F, FunctionAnalysisManager &AM) {
 905   GVNSink G;
 906   if (!G.run(F))
 907     return PreservedAnalyses::all();
 908
 909   PreservedAnalyses PA;
 910   PA.preserve<GlobalsAA>();
 911   return PA;
 912 }
 913
 914 char GVNSinkLegacyPass::ID = 0;
 915
 916 INITIALIZE_PASS_BEGIN(GVNSinkLegacyPass, "gvn-sink",
 917                       "Early GVN sinking of Expressions", false, false)
 918 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 919 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 920 INITIALIZE_PASS_END(GVNSinkLegacyPass, "gvn-sink",
 921                     "Early GVN sinking of Expressions", false, false)
 922
 923 FunctionPass *llvm::createGVNSinkPass() { return new GVNSinkLegacyPass(); }