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

   1 //===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
   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 // This pass performs a simple dominator tree walk that eliminates trivially
  11 // redundant instructions.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Scalar/EarlyCSE.h"
  16 #include "llvm/ADT/Hashing.h"
  17 #include "llvm/ADT/ScopedHashTable.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/Analysis/AssumptionCache.h"
  20 #include "llvm/Analysis/GlobalsModRef.h"
  21 #include "llvm/Analysis/InstructionSimplify.h"
  22 #include "llvm/Analysis/MemorySSA.h"
  23 #include "llvm/Analysis/MemorySSAUpdater.h"
  24 #include "llvm/Analysis/TargetLibraryInfo.h"
  25 #include "llvm/Analysis/TargetTransformInfo.h"
  26 #include "llvm/IR/DataLayout.h"
  27 #include "llvm/IR/Dominators.h"
  28 #include "llvm/IR/Instructions.h"
  29 #include "llvm/IR/IntrinsicInst.h"
  30 #include "llvm/IR/PatternMatch.h"
  31 #include "llvm/Pass.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/RecyclingAllocator.h"
  34 #include "llvm/Support/raw_ostream.h"
  35 #include "llvm/Transforms/Scalar.h"
  36 #include "llvm/Transforms/Utils/Local.h"
  37 #include <deque>
  38 using namespace llvm;
  39 using namespace llvm::PatternMatch;
  40
  41 #define DEBUG_TYPE "early-cse"
  42
  43 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
  44 STATISTIC(NumCSE,      "Number of instructions CSE'd");
  45 STATISTIC(NumCSECVP,   "Number of compare instructions CVP'd");
  46 STATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
  47 STATISTIC(NumCSECall,  "Number of call instructions CSE'd");
  48 STATISTIC(NumDSE,      "Number of trivial dead stores removed");
  49
  50 //===----------------------------------------------------------------------===//
  51 // SimpleValue
  52 //===----------------------------------------------------------------------===//
  53
  54 namespace {
  55 /// \brief Struct representing the available values in the scoped hash table.
  56 struct SimpleValue {
  57   Instruction *Inst;
  58
  59   SimpleValue(Instruction *I) : Inst(I) {
  60     assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
  61   }
  62
  63   bool isSentinel() const {
  64     return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
  65            Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
  66   }
  67
  68   static bool canHandle(Instruction *Inst) {
  69     // This can only handle non-void readnone functions.
  70     if (CallInst *CI = dyn_cast<CallInst>(Inst))
  71       return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
  72     return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
  73            isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
  74            isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
  75            isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
  76            isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
  77   }
  78 };
  79 }
  80
  81 namespace llvm {
  82 template <> struct DenseMapInfo<SimpleValue> {
  83   static inline SimpleValue getEmptyKey() {
  84     return DenseMapInfo<Instruction *>::getEmptyKey();
  85   }
  86   static inline SimpleValue getTombstoneKey() {
  87     return DenseMapInfo<Instruction *>::getTombstoneKey();
  88   }
  89   static unsigned getHashValue(SimpleValue Val);
  90   static bool isEqual(SimpleValue LHS, SimpleValue RHS);
  91 };
  92 }
  93
  94 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
  95   Instruction *Inst = Val.Inst;
  96   // Hash in all of the operands as pointers.
  97   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
  98     Value *LHS = BinOp->getOperand(0);
  99     Value *RHS = BinOp->getOperand(1);
 100     if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
 101       std::swap(LHS, RHS);
 102
 103     return hash_combine(BinOp->getOpcode(), LHS, RHS);
 104   }
 105
 106   if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
 107     Value *LHS = CI->getOperand(0);
 108     Value *RHS = CI->getOperand(1);
 109     CmpInst::Predicate Pred = CI->getPredicate();
 110     if (Inst->getOperand(0) > Inst->getOperand(1)) {
 111       std::swap(LHS, RHS);
 112       Pred = CI->getSwappedPredicate();
 113     }
 114     return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
 115   }
 116
 117   if (CastInst *CI = dyn_cast<CastInst>(Inst))
 118     return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
 119
 120   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
 121     return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
 122                         hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
 123
 124   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
 125     return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
 126                         IVI->getOperand(1),
 127                         hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
 128
 129   assert((isa<CallInst>(Inst) || isa<BinaryOperator>(Inst) ||
 130           isa<GetElementPtrInst>(Inst) || isa<SelectInst>(Inst) ||
 131           isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
 132           isa<ShuffleVectorInst>(Inst)) &&
 133          "Invalid/unknown instruction");
 134
 135   // Mix in the opcode.
 136   return hash_combine(
 137       Inst->getOpcode(),
 138       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
 139 }
 140
 141 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
 142   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 143
 144   if (LHS.isSentinel() || RHS.isSentinel())
 145     return LHSI == RHSI;
 146
 147   if (LHSI->getOpcode() != RHSI->getOpcode())
 148     return false;
 149   if (LHSI->isIdenticalToWhenDefined(RHSI))
 150     return true;
 151
 152   // If we're not strictly identical, we still might be a commutable instruction
 153   if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
 154     if (!LHSBinOp->isCommutative())
 155       return false;
 156
 157     assert(isa<BinaryOperator>(RHSI) &&
 158            "same opcode, but different instruction type?");
 159     BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
 160
 161     // Commuted equality
 162     return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
 163            LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
 164   }
 165   if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
 166     assert(isa<CmpInst>(RHSI) &&
 167            "same opcode, but different instruction type?");
 168     CmpInst *RHSCmp = cast<CmpInst>(RHSI);
 169     // Commuted equality
 170     return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
 171            LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
 172            LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
 173   }
 174
 175   return false;
 176 }
 177
 178 //===----------------------------------------------------------------------===//
 179 // CallValue
 180 //===----------------------------------------------------------------------===//
 181
 182 namespace {
 183 /// \brief Struct representing the available call values in the scoped hash
 184 /// table.
 185 struct CallValue {
 186   Instruction *Inst;
 187
 188   CallValue(Instruction *I) : Inst(I) {
 189     assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
 190   }
 191
 192   bool isSentinel() const {
 193     return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
 194            Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
 195   }
 196
 197   static bool canHandle(Instruction *Inst) {
 198     // Don't value number anything that returns void.
 199     if (Inst->getType()->isVoidTy())
 200       return false;
 201
 202     CallInst *CI = dyn_cast<CallInst>(Inst);
 203     if (!CI || !CI->onlyReadsMemory())
 204       return false;
 205     return true;
 206   }
 207 };
 208 }
 209
 210 namespace llvm {
 211 template <> struct DenseMapInfo<CallValue> {
 212   static inline CallValue getEmptyKey() {
 213     return DenseMapInfo<Instruction *>::getEmptyKey();
 214   }
 215   static inline CallValue getTombstoneKey() {
 216     return DenseMapInfo<Instruction *>::getTombstoneKey();
 217   }
 218   static unsigned getHashValue(CallValue Val);
 219   static bool isEqual(CallValue LHS, CallValue RHS);
 220 };
 221 }
 222
 223 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
 224   Instruction *Inst = Val.Inst;
 225   // Hash all of the operands as pointers and mix in the opcode.
 226   return hash_combine(
 227       Inst->getOpcode(),
 228       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
 229 }
 230
 231 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
 232   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 233   if (LHS.isSentinel() || RHS.isSentinel())
 234     return LHSI == RHSI;
 235   return LHSI->isIdenticalTo(RHSI);
 236 }
 237
 238 //===----------------------------------------------------------------------===//
 239 // EarlyCSE implementation
 240 //===----------------------------------------------------------------------===//
 241
 242 namespace {
 243 /// \brief A simple and fast domtree-based CSE pass.
 244 ///
 245 /// This pass does a simple depth-first walk over the dominator tree,
 246 /// eliminating trivially redundant instructions and using instsimplify to
 247 /// canonicalize things as it goes. It is intended to be fast and catch obvious
 248 /// cases so that instcombine and other passes are more effective. It is
 249 /// expected that a later pass of GVN will catch the interesting/hard cases.
 250 class EarlyCSE {
 251 public:
 252   const TargetLibraryInfo &TLI;
 253   const TargetTransformInfo &TTI;
 254   DominatorTree &DT;
 255   AssumptionCache &AC;
 256   MemorySSA *MSSA;
 257   std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
 258   typedef RecyclingAllocator<
 259       BumpPtrAllocator, ScopedHashTableVal<SimpleValue, Value *>> AllocatorTy;
 260   typedef ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
 261                           AllocatorTy> ScopedHTType;
 262
 263   /// \brief A scoped hash table of the current values of all of our simple
 264   /// scalar expressions.
 265   ///
 266   /// As we walk down the domtree, we look to see if instructions are in this:
 267   /// if so, we replace them with what we find, otherwise we insert them so
 268   /// that dominated values can succeed in their lookup.
 269   ScopedHTType AvailableValues;
 270
 271   /// A scoped hash table of the current values of previously encounted memory
 272   /// locations.
 273   ///
 274   /// This allows us to get efficient access to dominating loads or stores when
 275   /// we have a fully redundant load.  In addition to the most recent load, we
 276   /// keep track of a generation count of the read, which is compared against
 277   /// the current generation count.  The current generation count is incremented
 278   /// after every possibly writing memory operation, which ensures that we only
 279   /// CSE loads with other loads that have no intervening store.  Ordering
 280   /// events (such as fences or atomic instructions) increment the generation
 281   /// count as well; essentially, we model these as writes to all possible
 282   /// locations.  Note that atomic and/or volatile loads and stores can be
 283   /// present the table; it is the responsibility of the consumer to inspect
 284   /// the atomicity/volatility if needed.
 285   struct LoadValue {
 286     Instruction *DefInst;
 287     unsigned Generation;
 288     int MatchingId;
 289     bool IsAtomic;
 290     bool IsInvariant;
 291     LoadValue()
 292         : DefInst(nullptr), Generation(0), MatchingId(-1), IsAtomic(false),
 293           IsInvariant(false) {}
 294     LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
 295               bool IsAtomic, bool IsInvariant)
 296         : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
 297           IsAtomic(IsAtomic), IsInvariant(IsInvariant) {}
 298   };
 299   typedef RecyclingAllocator<BumpPtrAllocator,
 300                              ScopedHashTableVal<Value *, LoadValue>>
 301       LoadMapAllocator;
 302   typedef ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
 303                           LoadMapAllocator> LoadHTType;
 304   LoadHTType AvailableLoads;
 305
 306   /// \brief A scoped hash table of the current values of read-only call
 307   /// values.
 308   ///
 309   /// It uses the same generation count as loads.
 310   typedef ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>
 311       CallHTType;
 312   CallHTType AvailableCalls;
 313
 314   /// \brief This is the current generation of the memory value.
 315   unsigned CurrentGeneration;
 316
 317   /// \brief Set up the EarlyCSE runner for a particular function.
 318   EarlyCSE(const TargetLibraryInfo &TLI, const TargetTransformInfo &TTI,
 319            DominatorTree &DT, AssumptionCache &AC, MemorySSA *MSSA)
 320       : TLI(TLI), TTI(TTI), DT(DT), AC(AC), MSSA(MSSA),
 321         MSSAUpdater(make_unique<MemorySSAUpdater>(MSSA)), CurrentGeneration(0) {
 322   }
 323
 324   bool run();
 325
 326 private:
 327   // Almost a POD, but needs to call the constructors for the scoped hash
 328   // tables so that a new scope gets pushed on. These are RAII so that the
 329   // scope gets popped when the NodeScope is destroyed.
 330   class NodeScope {
 331   public:
 332     NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
 333               CallHTType &AvailableCalls)
 334         : Scope(AvailableValues), LoadScope(AvailableLoads),
 335           CallScope(AvailableCalls) {}
 336
 337   private:
 338     NodeScope(const NodeScope &) = delete;
 339     void operator=(const NodeScope &) = delete;
 340
 341     ScopedHTType::ScopeTy Scope;
 342     LoadHTType::ScopeTy LoadScope;
 343     CallHTType::ScopeTy CallScope;
 344   };
 345
 346   // Contains all the needed information to create a stack for doing a depth
 347   // first traversal of the tree. This includes scopes for values, loads, and
 348   // calls as well as the generation. There is a child iterator so that the
 349   // children do not need to be store separately.
 350   class StackNode {
 351   public:
 352     StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
 353               CallHTType &AvailableCalls, unsigned cg, DomTreeNode *n,
 354               DomTreeNode::iterator child, DomTreeNode::iterator end)
 355         : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
 356           EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls),
 357           Processed(false) {}
 358
 359     // Accessors.
 360     unsigned currentGeneration() { return CurrentGeneration; }
 361     unsigned childGeneration() { return ChildGeneration; }
 362     void childGeneration(unsigned generation) { ChildGeneration = generation; }
 363     DomTreeNode *node() { return Node; }
 364     DomTreeNode::iterator childIter() { return ChildIter; }
 365     DomTreeNode *nextChild() {
 366       DomTreeNode *child = *ChildIter;
 367       ++ChildIter;
 368       return child;
 369     }
 370     DomTreeNode::iterator end() { return EndIter; }
 371     bool isProcessed() { return Processed; }
 372     void process() { Processed = true; }
 373
 374   private:
 375     StackNode(const StackNode &) = delete;
 376     void operator=(const StackNode &) = delete;
 377
 378     // Members.
 379     unsigned CurrentGeneration;
 380     unsigned ChildGeneration;
 381     DomTreeNode *Node;
 382     DomTreeNode::iterator ChildIter;
 383     DomTreeNode::iterator EndIter;
 384     NodeScope Scopes;
 385     bool Processed;
 386   };
 387
 388   /// \brief Wrapper class to handle memory instructions, including loads,
 389   /// stores and intrinsic loads and stores defined by the target.
 390   class ParseMemoryInst {
 391   public:
 392     ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI)
 393       : IsTargetMemInst(false), Inst(Inst) {
 394       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
 395         if (TTI.getTgtMemIntrinsic(II, Info))
 396           IsTargetMemInst = true;
 397     }
 398     bool isLoad() const {
 399       if (IsTargetMemInst) return Info.ReadMem;
 400       return isa<LoadInst>(Inst);
 401     }
 402     bool isStore() const {
 403       if (IsTargetMemInst) return Info.WriteMem;
 404       return isa<StoreInst>(Inst);
 405     }
 406     bool isAtomic() const {
 407       if (IsTargetMemInst)
 408         return Info.Ordering != AtomicOrdering::NotAtomic;
 409       return Inst->isAtomic();
 410     }
 411     bool isUnordered() const {
 412       if (IsTargetMemInst)
 413         return Info.isUnordered();
 414
 415       if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
 416         return LI->isUnordered();
 417       } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 418         return SI->isUnordered();
 419       }
 420       // Conservative answer
 421       return !Inst->isAtomic();
 422     }
 423
 424     bool isVolatile() const {
 425       if (IsTargetMemInst)
 426         return Info.IsVolatile;
 427
 428       if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
 429         return LI->isVolatile();
 430       } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 431         return SI->isVolatile();
 432       }
 433       // Conservative answer
 434       return true;
 435     }
 436
 437     bool isInvariantLoad() const {
 438       if (auto *LI = dyn_cast<LoadInst>(Inst))
 439         return LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr;
 440       return false;
 441     }
 442
 443     bool isMatchingMemLoc(const ParseMemoryInst &Inst) const {
 444       return (getPointerOperand() == Inst.getPointerOperand() &&
 445               getMatchingId() == Inst.getMatchingId());
 446     }
 447     bool isValid() const { return getPointerOperand() != nullptr; }
 448
 449     // For regular (non-intrinsic) loads/stores, this is set to -1. For
 450     // intrinsic loads/stores, the id is retrieved from the corresponding
 451     // field in the MemIntrinsicInfo structure.  That field contains
 452     // non-negative values only.
 453     int getMatchingId() const {
 454       if (IsTargetMemInst) return Info.MatchingId;
 455       return -1;
 456     }
 457     Value *getPointerOperand() const {
 458       if (IsTargetMemInst) return Info.PtrVal;
 459       if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
 460         return LI->getPointerOperand();
 461       } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 462         return SI->getPointerOperand();
 463       }
 464       return nullptr;
 465     }
 466     bool mayReadFromMemory() const {
 467       if (IsTargetMemInst) return Info.ReadMem;
 468       return Inst->mayReadFromMemory();
 469     }
 470     bool mayWriteToMemory() const {
 471       if (IsTargetMemInst) return Info.WriteMem;
 472       return Inst->mayWriteToMemory();
 473     }
 474
 475   private:
 476     bool IsTargetMemInst;
 477     MemIntrinsicInfo Info;
 478     Instruction *Inst;
 479   };
 480
 481   bool processNode(DomTreeNode *Node);
 482
 483   Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const {
 484     if (auto *LI = dyn_cast<LoadInst>(Inst))
 485       return LI;
 486     if (auto *SI = dyn_cast<StoreInst>(Inst))
 487       return SI->getValueOperand();
 488     assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
 489     return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst),
 490                                                  ExpectedType);
 491   }
 492
 493   bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
 494                            Instruction *EarlierInst, Instruction *LaterInst);
 495
 496   void removeMSSA(Instruction *Inst) {
 497     if (!MSSA)
 498       return;
 499     // Removing a store here can leave MemorySSA in an unoptimized state by
 500     // creating MemoryPhis that have identical arguments and by creating
 501     // MemoryUses whose defining access is not an actual clobber.  We handle the
 502     // phi case eagerly here.  The non-optimized MemoryUse case is lazily
 503     // updated by MemorySSA getClobberingMemoryAccess.
 504     if (MemoryAccess *MA = MSSA->getMemoryAccess(Inst)) {
 505       // Optimize MemoryPhi nodes that may become redundant by having all the
 506       // same input values once MA is removed.
 507       SmallVector<MemoryPhi *, 4> PhisToCheck;
 508       SmallVector<MemoryAccess *, 8> WorkQueue;
 509       WorkQueue.push_back(MA);
 510       // Process MemoryPhi nodes in FIFO order using a ever-growing vector since
 511       // we shouldn't be processing that many phis and this will avoid an
 512       // allocation in almost all cases.
 513       for (unsigned I = 0; I < WorkQueue.size(); ++I) {
 514         MemoryAccess *WI = WorkQueue[I];
 515
 516         for (auto *U : WI->users())
 517           if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U))
 518             PhisToCheck.push_back(MP);
 519
 520         MSSAUpdater->removeMemoryAccess(WI);
 521
 522         for (MemoryPhi *MP : PhisToCheck) {
 523           MemoryAccess *FirstIn = MP->getIncomingValue(0);
 524           if (all_of(MP->incoming_values(),
 525                      [=](Use &In) { return In == FirstIn; }))
 526             WorkQueue.push_back(MP);
 527         }
 528         PhisToCheck.clear();
 529       }
 530     }
 531   }
 532 };
 533 }
 534
 535 /// Determine if the memory referenced by LaterInst is from the same heap
 536 /// version as EarlierInst.
 537 /// This is currently called in two scenarios:
 538 ///
 539 ///   load p
 540 ///   ...
 541 ///   load p
 542 ///
 543 /// and
 544 ///
 545 ///   x = load p
 546 ///   ...
 547 ///   store x, p
 548 ///
 549 /// in both cases we want to verify that there are no possible writes to the
 550 /// memory referenced by p between the earlier and later instruction.
 551 bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
 552                                    unsigned LaterGeneration,
 553                                    Instruction *EarlierInst,
 554                                    Instruction *LaterInst) {
 555   // Check the simple memory generation tracking first.
 556   if (EarlierGeneration == LaterGeneration)
 557     return true;
 558
 559   if (!MSSA)
 560     return false;
 561
 562   // Since we know LaterDef dominates LaterInst and EarlierInst dominates
 563   // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
 564   // EarlierInst and LaterInst and neither can any other write that potentially
 565   // clobbers LaterInst.
 566   MemoryAccess *LaterDef =
 567       MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
 568   return MSSA->dominates(LaterDef, MSSA->getMemoryAccess(EarlierInst));
 569 }
 570
 571 bool EarlyCSE::processNode(DomTreeNode *Node) {
 572   bool Changed = false;
 573   BasicBlock *BB = Node->getBlock();
 574
 575   // If this block has a single predecessor, then the predecessor is the parent
 576   // of the domtree node and all of the live out memory values are still current
 577   // in this block.  If this block has multiple predecessors, then they could
 578   // have invalidated the live-out memory values of our parent value.  For now,
 579   // just be conservative and invalidate memory if this block has multiple
 580   // predecessors.
 581   if (!BB->getSinglePredecessor())
 582     ++CurrentGeneration;
 583
 584   // If this node has a single predecessor which ends in a conditional branch,
 585   // we can infer the value of the branch condition given that we took this
 586   // path.  We need the single predecessor to ensure there's not another path
 587   // which reaches this block where the condition might hold a different
 588   // value.  Since we're adding this to the scoped hash table (like any other
 589   // def), it will have been popped if we encounter a future merge block.
 590   if (BasicBlock *Pred = BB->getSinglePredecessor()) {
 591     auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
 592     if (BI && BI->isConditional()) {
 593       auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
 594       if (CondInst && SimpleValue::canHandle(CondInst)) {
 595         assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
 596         auto *TorF = (BI->getSuccessor(0) == BB)
 597                          ? ConstantInt::getTrue(BB->getContext())
 598                          : ConstantInt::getFalse(BB->getContext());
 599         AvailableValues.insert(CondInst, TorF);
 600         DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
 601                      << CondInst->getName() << "' as " << *TorF << " in "
 602                      << BB->getName() << "\n");
 603         // Replace all dominated uses with the known value.
 604         if (unsigned Count = replaceDominatedUsesWith(
 605                 CondInst, TorF, DT, BasicBlockEdge(Pred, BB))) {
 606           Changed = true;
 607           NumCSECVP = NumCSECVP + Count;
 608         }
 609       }
 610     }
 611   }
 612
 613   /// LastStore - Keep track of the last non-volatile store that we saw... for
 614   /// as long as there in no instruction that reads memory.  If we see a store
 615   /// to the same location, we delete the dead store.  This zaps trivial dead
 616   /// stores which can occur in bitfield code among other things.
 617   Instruction *LastStore = nullptr;
 618
 619   const DataLayout &DL = BB->getModule()->getDataLayout();
 620
 621   // See if any instructions in the block can be eliminated.  If so, do it.  If
 622   // not, add them to AvailableValues.
 623   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
 624     Instruction *Inst = &*I++;
 625
 626     // Dead instructions should just be removed.
 627     if (isInstructionTriviallyDead(Inst, &TLI)) {
 628       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
 629       removeMSSA(Inst);
 630       Inst->eraseFromParent();
 631       Changed = true;
 632       ++NumSimplify;
 633       continue;
 634     }
 635
 636     // Skip assume intrinsics, they don't really have side effects (although
 637     // they're marked as such to ensure preservation of control dependencies),
 638     // and this pass will not disturb any of the assumption's control
 639     // dependencies.
 640     if (match(Inst, m_Intrinsic<Intrinsic::assume>())) {
 641       DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n');
 642       continue;
 643     }
 644
 645     // Skip invariant.start intrinsics since they only read memory, and we can
 646     // forward values across it. Also, we dont need to consume the last store
 647     // since the semantics of invariant.start allow us to perform DSE of the
 648     // last store, if there was a store following invariant.start. Consider:
 649     //
 650     // store 30, i8* p
 651     // invariant.start(p)
 652     // store 40, i8* p
 653     // We can DSE the store to 30, since the store 40 to invariant location p
 654     // causes undefined behaviour.
 655     if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>()))
 656       continue;
 657
 658     if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
 659       if (auto *CondI =
 660               dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
 661         // The condition we're on guarding here is true for all dominated
 662         // locations.
 663         if (SimpleValue::canHandle(CondI))
 664           AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
 665       }
 666
 667       // Guard intrinsics read all memory, but don't write any memory.
 668       // Accordingly, don't update the generation but consume the last store (to
 669       // avoid an incorrect DSE).
 670       LastStore = nullptr;
 671       continue;
 672     }
 673
 674     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
 675     // its simpler value.
 676     if (Value *V = SimplifyInstruction(Inst, DL, &TLI, &DT, &AC)) {
 677       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
 678       bool Killed = false;
 679       if (!Inst->use_empty()) {
 680         Inst->replaceAllUsesWith(V);
 681         Changed = true;
 682       }
 683       if (isInstructionTriviallyDead(Inst, &TLI)) {
 684         removeMSSA(Inst);
 685         Inst->eraseFromParent();
 686         Changed = true;
 687         Killed = true;
 688       }
 689       if (Changed)
 690         ++NumSimplify;
 691       if (Killed)
 692         continue;
 693     }
 694
 695     // If this is a simple instruction that we can value number, process it.
 696     if (SimpleValue::canHandle(Inst)) {
 697       // See if the instruction has an available value.  If so, use it.
 698       if (Value *V = AvailableValues.lookup(Inst)) {
 699         DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
 700         if (auto *I = dyn_cast<Instruction>(V))
 701           I->andIRFlags(Inst);
 702         Inst->replaceAllUsesWith(V);
 703         removeMSSA(Inst);
 704         Inst->eraseFromParent();
 705         Changed = true;
 706         ++NumCSE;
 707         continue;
 708       }
 709
 710       // Otherwise, just remember that this value is available.
 711       AvailableValues.insert(Inst, Inst);
 712       continue;
 713     }
 714
 715     ParseMemoryInst MemInst(Inst, TTI);
 716     // If this is a non-volatile load, process it.
 717     if (MemInst.isValid() && MemInst.isLoad()) {
 718       // (conservatively) we can't peak past the ordering implied by this
 719       // operation, but we can add this load to our set of available values
 720       if (MemInst.isVolatile() || !MemInst.isUnordered()) {
 721         LastStore = nullptr;
 722         ++CurrentGeneration;
 723       }
 724
 725       // If we have an available version of this load, and if it is the right
 726       // generation or the load is known to be from an invariant location,
 727       // replace this instruction.
 728       //
 729       // If either the dominating load or the current load are invariant, then
 730       // we can assume the current load loads the same value as the dominating
 731       // load.
 732       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
 733       if (InVal.DefInst != nullptr &&
 734           InVal.MatchingId == MemInst.getMatchingId() &&
 735           // We don't yet handle removing loads with ordering of any kind.
 736           !MemInst.isVolatile() && MemInst.isUnordered() &&
 737           // We can't replace an atomic load with one which isn't also atomic.
 738           InVal.IsAtomic >= MemInst.isAtomic() &&
 739           (InVal.IsInvariant || MemInst.isInvariantLoad() ||
 740            isSameMemGeneration(InVal.Generation, CurrentGeneration,
 741                                InVal.DefInst, Inst))) {
 742         Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
 743         if (Op != nullptr) {
 744           DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
 745                        << "  to: " << *InVal.DefInst << '\n');
 746           if (!Inst->use_empty())
 747             Inst->replaceAllUsesWith(Op);
 748           removeMSSA(Inst);
 749           Inst->eraseFromParent();
 750           Changed = true;
 751           ++NumCSELoad;
 752           continue;
 753         }
 754       }
 755
 756       // Otherwise, remember that we have this instruction.
 757       AvailableLoads.insert(
 758           MemInst.getPointerOperand(),
 759           LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
 760                     MemInst.isAtomic(), MemInst.isInvariantLoad()));
 761       LastStore = nullptr;
 762       continue;
 763     }
 764
 765     // If this instruction may read from memory or throw (and potentially read
 766     // from memory in the exception handler), forget LastStore.  Load/store
 767     // intrinsics will indicate both a read and a write to memory.  The target
 768     // may override this (e.g. so that a store intrinsic does not read from
 769     // memory, and thus will be treated the same as a regular store for
 770     // commoning purposes).
 771     if ((Inst->mayReadFromMemory() || Inst->mayThrow()) &&
 772         !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
 773       LastStore = nullptr;
 774
 775     // If this is a read-only call, process it.
 776     if (CallValue::canHandle(Inst)) {
 777       // If we have an available version of this call, and if it is the right
 778       // generation, replace this instruction.
 779       std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(Inst);
 780       if (InVal.first != nullptr &&
 781           isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
 782                               Inst)) {
 783         DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst
 784                      << "  to: " << *InVal.first << '\n');
 785         if (!Inst->use_empty())
 786           Inst->replaceAllUsesWith(InVal.first);
 787         removeMSSA(Inst);
 788         Inst->eraseFromParent();
 789         Changed = true;
 790         ++NumCSECall;
 791         continue;
 792       }
 793
 794       // Otherwise, remember that we have this instruction.
 795       AvailableCalls.insert(
 796           Inst, std::pair<Instruction *, unsigned>(Inst, CurrentGeneration));
 797       continue;
 798     }
 799
 800     // A release fence requires that all stores complete before it, but does
 801     // not prevent the reordering of following loads 'before' the fence.  As a
 802     // result, we don't need to consider it as writing to memory and don't need
 803     // to advance the generation.  We do need to prevent DSE across the fence,
 804     // but that's handled above.
 805     if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
 806       if (FI->getOrdering() == AtomicOrdering::Release) {
 807         assert(Inst->mayReadFromMemory() && "relied on to prevent DSE above");
 808         continue;
 809       }
 810
 811     // write back DSE - If we write back the same value we just loaded from
 812     // the same location and haven't passed any intervening writes or ordering
 813     // operations, we can remove the write.  The primary benefit is in allowing
 814     // the available load table to remain valid and value forward past where
 815     // the store originally was.
 816     if (MemInst.isValid() && MemInst.isStore()) {
 817       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
 818       if (InVal.DefInst &&
 819           InVal.DefInst == getOrCreateResult(Inst, InVal.DefInst->getType()) &&
 820           InVal.MatchingId == MemInst.getMatchingId() &&
 821           // We don't yet handle removing stores with ordering of any kind.
 822           !MemInst.isVolatile() && MemInst.isUnordered() &&
 823           isSameMemGeneration(InVal.Generation, CurrentGeneration,
 824                               InVal.DefInst, Inst)) {
 825         // It is okay to have a LastStore to a different pointer here if MemorySSA
 826         // tells us that the load and store are from the same memory generation.
 827         // In that case, LastStore should keep its present value since we're
 828         // removing the current store.
 829         assert((!LastStore ||
 830                 ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
 831                     MemInst.getPointerOperand() ||
 832                 MSSA) &&
 833                "can't have an intervening store if not using MemorySSA!");
 834         DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << *Inst << '\n');
 835         removeMSSA(Inst);
 836         Inst->eraseFromParent();
 837         Changed = true;
 838         ++NumDSE;
 839         // We can avoid incrementing the generation count since we were able
 840         // to eliminate this store.
 841         continue;
 842       }
 843     }
 844
 845     // Okay, this isn't something we can CSE at all.  Check to see if it is
 846     // something that could modify memory.  If so, our available memory values
 847     // cannot be used so bump the generation count.
 848     if (Inst->mayWriteToMemory()) {
 849       ++CurrentGeneration;
 850
 851       if (MemInst.isValid() && MemInst.isStore()) {
 852         // We do a trivial form of DSE if there are two stores to the same
 853         // location with no intervening loads.  Delete the earlier store.
 854         // At the moment, we don't remove ordered stores, but do remove
 855         // unordered atomic stores.  There's no special requirement (for
 856         // unordered atomics) about removing atomic stores only in favor of
 857         // other atomic stores since we we're going to execute the non-atomic
 858         // one anyway and the atomic one might never have become visible.
 859         if (LastStore) {
 860           ParseMemoryInst LastStoreMemInst(LastStore, TTI);
 861           assert(LastStoreMemInst.isUnordered() &&
 862                  !LastStoreMemInst.isVolatile() &&
 863                  "Violated invariant");
 864           if (LastStoreMemInst.isMatchingMemLoc(MemInst)) {
 865             DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
 866                          << "  due to: " << *Inst << '\n');
 867             removeMSSA(LastStore);
 868             LastStore->eraseFromParent();
 869             Changed = true;
 870             ++NumDSE;
 871             LastStore = nullptr;
 872           }
 873           // fallthrough - we can exploit information about this store
 874         }
 875
 876         // Okay, we just invalidated anything we knew about loaded values.  Try
 877         // to salvage *something* by remembering that the stored value is a live
 878         // version of the pointer.  It is safe to forward from volatile stores
 879         // to non-volatile loads, so we don't have to check for volatility of
 880         // the store.
 881         AvailableLoads.insert(
 882             MemInst.getPointerOperand(),
 883             LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
 884                       MemInst.isAtomic(), /*IsInvariant=*/false));
 885
 886         // Remember that this was the last unordered store we saw for DSE. We
 887         // don't yet handle DSE on ordered or volatile stores since we don't
 888         // have a good way to model the ordering requirement for following
 889         // passes  once the store is removed.  We could insert a fence, but
 890         // since fences are slightly stronger than stores in their ordering,
 891         // it's not clear this is a profitable transform. Another option would
 892         // be to merge the ordering with that of the post dominating store.
 893         if (MemInst.isUnordered() && !MemInst.isVolatile())
 894           LastStore = Inst;
 895         else
 896           LastStore = nullptr;
 897       }
 898     }
 899   }
 900
 901   return Changed;
 902 }
 903
 904 bool EarlyCSE::run() {
 905   // Note, deque is being used here because there is significant performance
 906   // gains over vector when the container becomes very large due to the
 907   // specific access patterns. For more information see the mailing list
 908   // discussion on this:
 909   // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
 910   std::deque<StackNode *> nodesToProcess;
 911
 912   bool Changed = false;
 913
 914   // Process the root node.
 915   nodesToProcess.push_back(new StackNode(
 916       AvailableValues, AvailableLoads, AvailableCalls, CurrentGeneration,
 917       DT.getRootNode(), DT.getRootNode()->begin(), DT.getRootNode()->end()));
 918
 919   // Save the current generation.
 920   unsigned LiveOutGeneration = CurrentGeneration;
 921
 922   // Process the stack.
 923   while (!nodesToProcess.empty()) {
 924     // Grab the first item off the stack. Set the current generation, remove
 925     // the node from the stack, and process it.
 926     StackNode *NodeToProcess = nodesToProcess.back();
 927
 928     // Initialize class members.
 929     CurrentGeneration = NodeToProcess->currentGeneration();
 930
 931     // Check if the node needs to be processed.
 932     if (!NodeToProcess->isProcessed()) {
 933       // Process the node.
 934       Changed |= processNode(NodeToProcess->node());
 935       NodeToProcess->childGeneration(CurrentGeneration);
 936       NodeToProcess->process();
 937     } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
 938       // Push the next child onto the stack.
 939       DomTreeNode *child = NodeToProcess->nextChild();
 940       nodesToProcess.push_back(
 941           new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
 942                         NodeToProcess->childGeneration(), child, child->begin(),
 943                         child->end()));
 944     } else {
 945       // It has been processed, and there are no more children to process,
 946       // so delete it and pop it off the stack.
 947       delete NodeToProcess;
 948       nodesToProcess.pop_back();
 949     }
 950   } // while (!nodes...)
 951
 952   // Reset the current generation.
 953   CurrentGeneration = LiveOutGeneration;
 954
 955   return Changed;
 956 }
 957
 958 PreservedAnalyses EarlyCSEPass::run(Function &F,
 959                                     FunctionAnalysisManager &AM) {
 960   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
 961   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
 962   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 963   auto &AC = AM.getResult<AssumptionAnalysis>(F);
 964   auto *MSSA =
 965       UseMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() : nullptr;
 966
 967   EarlyCSE CSE(TLI, TTI, DT, AC, MSSA);
 968
 969   if (!CSE.run())
 970     return PreservedAnalyses::all();
 971
 972   PreservedAnalyses PA;
 973   PA.preserveSet<CFGAnalyses>();
 974   PA.preserve<GlobalsAA>();
 975   if (UseMemorySSA)
 976     PA.preserve<MemorySSAAnalysis>();
 977   return PA;
 978 }
 979
 980 namespace {
 981 /// \brief A simple and fast domtree-based CSE pass.
 982 ///
 983 /// This pass does a simple depth-first walk over the dominator tree,
 984 /// eliminating trivially redundant instructions and using instsimplify to
 985 /// canonicalize things as it goes. It is intended to be fast and catch obvious
 986 /// cases so that instcombine and other passes are more effective. It is
 987 /// expected that a later pass of GVN will catch the interesting/hard cases.
 988 template<bool UseMemorySSA>
 989 class EarlyCSELegacyCommonPass : public FunctionPass {
 990 public:
 991   static char ID;
 992
 993   EarlyCSELegacyCommonPass() : FunctionPass(ID) {
 994     if (UseMemorySSA)
 995       initializeEarlyCSEMemSSALegacyPassPass(*PassRegistry::getPassRegistry());
 996     else
 997       initializeEarlyCSELegacyPassPass(*PassRegistry::getPassRegistry());
 998   }
 999
1000   bool runOnFunction(Function &F) override {
1001     if (skipFunction(F))
1002       return false;
1003
1004     auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1005     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1006     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1007     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1008     auto *MSSA =
1009         UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() : nullptr;
1010
1011     EarlyCSE CSE(TLI, TTI, DT, AC, MSSA);
1012
1013     return CSE.run();
1014   }
1015
1016   void getAnalysisUsage(AnalysisUsage &AU) const override {
1017     AU.addRequired<AssumptionCacheTracker>();
1018     AU.addRequired<DominatorTreeWrapperPass>();
1019     AU.addRequired<TargetLibraryInfoWrapperPass>();
1020     AU.addRequired<TargetTransformInfoWrapperPass>();
1021     if (UseMemorySSA) {
1022       AU.addRequired<MemorySSAWrapperPass>();
1023       AU.addPreserved<MemorySSAWrapperPass>();
1024     }
1025     AU.addPreserved<GlobalsAAWrapperPass>();
1026     AU.setPreservesCFG();
1027   }
1028 };
1029 }
1030
1031 using EarlyCSELegacyPass = EarlyCSELegacyCommonPass</*UseMemorySSA=*/false>;
1032
1033 template<>
1034 char EarlyCSELegacyPass::ID = 0;
1035
1036 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
1037                       false)
1038 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1039 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1040 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1041 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1042 INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)
1043
1044 using EarlyCSEMemSSALegacyPass =
1045     EarlyCSELegacyCommonPass</*UseMemorySSA=*/true>;
1046
1047 template<>
1048 char EarlyCSEMemSSALegacyPass::ID = 0;
1049
1050 FunctionPass *llvm::createEarlyCSEPass(bool UseMemorySSA) {
1051   if (UseMemorySSA)
1052     return new EarlyCSEMemSSALegacyPass();
1053   else
1054     return new EarlyCSELegacyPass();
1055 }
1056
1057 INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1058                       "Early CSE w/ MemorySSA", false, false)
1059 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1060 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1061 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1062 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1063 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
1064 INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1065                     "Early CSE w/ MemorySSA", false, false)