Use the new 'InvariantInfo' property to eliminate redundant loads with --instcombine

[lvoufo]

Summary

Similar to GVN in D14004: While processing instructions in InstCombine, mark global variables and alloca instructions corresponding to each encountered invariant intrinsic call as indicating 'writeonce' memory locations that either have been written into or can be written into again (once). Then, while scanning instructions backwards looking for available loads for a given memory location, be sure to temporarily disable or reset the markings, as appropriate.

This patch is a break-down of (corrected) D13606.

[nlewycky]

Patch needs testcases.

lib/Transforms/InstCombine/InstructionCombining.cpp

1961

Why bother? We're guaranteed to visit the invariant.start and the invariant.end, right? Just handle invariant_start by replacing it with an undef, and let the generic "EraseInstFromFunction" call (below on line 1975) handle the invariant.end?

I think the other case is an invariant applying to a bitcast instead of to the original object. Does this function work in that case? (Does it even pass isAllocSiteRemovable?)

lib/Analysis/Loads.cpp

 }
 
 /// DefMaxInstsToScan - the default number of maximum instructions
 /// to scan in the block, used by FindAvailableLoadedValue().
 /// FindAvailableLoadedValue() was introduced in r60148, to improve jump
 /// threading in part by eliminating partially redundant loads.
 /// At that point, the value of MaxInstsToScan was already set to '6'
 /// without documented explanation.
-cl::opt<unsigned>
-llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden,
+/// Let's bump this number up to '8' to improve the chances of behaviorial
+/// match between -instcombine and -inline -instcombine.
+cl::opt<unsigned> llvm::DefMaxInstsToScan(
+    "available-load-scan-limit", cl::init(8), cl::Hidden,
     cl::desc("Use this to specify the default maximum number of instructions "
              "to scan backward from a given instruction, when searching for "
              "available loaded value"));
 
 /// \brief Scan the ScanBB block backwards to see if we have the value at the
 /// memory address *Ptr locally available within a small number of instructions.
 ///
 /// The scan starts from \c ScanFrom. \c MaxInstsToScan specifies the maximum
 /// instructions to scan in the block. If it is set to \c 0, it will scan the whole
 /// block.
 ///
Value *llvm::FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB,
 
   const DataLayout &DL = ScanBB->getModule()->getDataLayout();
 
   // Try to get the store size for the type.
   uint64_t AccessSize = DL.getTypeStoreSize(AccessTy);
 
   Value *StrippedPtr = Ptr->stripPointerCasts();
 
+  // We're about to scan backwards. Preserve the initial invariant_start
+  // intrinsic marking on this load, for subsequent instructions.
+  // First, compute the info to preserve.
+  // Then, actually preserve the info before backward scanning starts.
+  InvariantInfo &InvInfo = ScanBB->getModule()->getInvariantInfo();
+  PreservedInvariantInfo Preserved(StrippedPtr, DL, InvInfo);
+  PreserveInvariantInfo PIO(Preserved);
+
   while (ScanFrom != ScanBB->begin()) {
     // We must ignore debug info directives when counting (otherwise they
     // would affect codegen).
     Instruction *Inst = --ScanFrom;
     if (isa<DbgInfoIntrinsic>(Inst))
       continue;
 
+    // Same for invariant intrinsics, which may also unset preserved
+    // invariant info.
+    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
+      if (AA && BackwardScanInvariantIntrinsic(II, Preserved, InvInfo)) continue;
+    }
+
     // Restore ScanFrom to expected value in case next test succeeds
     ScanFrom++;
 
     // Don't scan huge blocks.
     if (MaxInstsToScan-- == 0)
       return nullptr;
 
     --ScanFrom;

lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::assume: {
     // then this one is redundant, and should be removed.
     APInt KnownZero(1, 0), KnownOne(1, 0);
     computeKnownBits(IIOperand, KnownZero, KnownOne, 0, II);
     if (KnownOne.isAllOnesValue())
       return EraseInstFromFunction(*II);
 
     break;
   }
+  case Intrinsic::invariant_start:
+  case Intrinsic::invariant_end:
+    processInvariantIntrinsic(II, InvInfo);
+    break;
   case Intrinsic::experimental_gc_relocate: {
     // Translate facts known about a pointer before relocating into
     // facts about the relocate value, while being careful to
     // preserve relocation semantics.
     GCRelocateOperands Operands(II);
     Value *DerivedPtr = Operands.getDerivedPtr();
     auto *GCRelocateType = cast<PointerType>(II->getType());
 

lib/Transforms/InstCombine/InstCombineInternal.h

 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
 
 #define DEBUG_TYPE "instcombine"
 
 namespace llvm {
 class CallSite;
 class DataLayout;
 class DominatorTree;
+class InvariantInfo;
 class TargetLibraryInfo;
 class DbgDeclareInst;
 class MemIntrinsic;
 class MemSetInst;
 
 /// \brief Assign a complexity or rank value to LLVM Values.
 ///
 /// This routine maps IR values to various complexity ranks:
private:
   AliasAnalysis *AA;
 
   // Required analyses.
   // FIXME: These can never be null and should be references.
   AssumptionCache *AC;
   TargetLibraryInfo *TLI;
   DominatorTree *DT;
   const DataLayout &DL;
+  InvariantInfo &InvInfo;
 
   // Optional analyses. When non-null, these can both be used to do better
   // combining and will be updated to reflect any changes.
   LoopInfo *LI;
 
   bool MadeIRChange;
 
 public:
   InstCombiner(InstCombineWorklist &Worklist, BuilderTy *Builder,
                bool MinimizeSize, AliasAnalysis *AA,
                AssumptionCache *AC, TargetLibraryInfo *TLI,
-               DominatorTree *DT, const DataLayout &DL, LoopInfo *LI)
+               DominatorTree *DT, const DataLayout &DL,
+               InvariantInfo &InvInfo, LoopInfo *LI)
       : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
-        AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL), LI(LI), MadeIRChange(false) {}
+        AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL), InvInfo(InvInfo), LI(LI),
+        MadeIRChange(false) {}
 
   /// \brief Run the combiner over the entire worklist until it is empty.
   ///
   /// \returns true if the IR is changed.
   bool run();
 
   AssumptionCache *getAssumptionCache() const { return AC; }
 

lib/Transforms/InstCombine/InstructionCombining.cpp

for (unsigned i = 0, e = Users.size(); i != e; ++i) {
       } else if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) {
         ReplaceInstUsesWith(*I, UndefValue::get(I->getType()));
       } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
         if (II->getIntrinsicID() == Intrinsic::objectsize) {
           ConstantInt *CI = cast<ConstantInt>(II->getArgOperand(1));
           uint64_t DontKnow = CI->isZero() ? -1ULL : 0;
           ReplaceInstUsesWith(*I, ConstantInt::get(I->getType(), DontKnow));
         }
+
+        // If this is a paired invariant_start, then erase its invariant_end,
+        // and all of its other uses.
+        if (II->getIntrinsicID() == Intrinsic::invariant_start) {
+          SmallVector<IntrinsicInst *, 4> UsesToRemove;
+          for (Use &U : II->uses()) {
+            IntrinsicInst *User = cast<IntrinsicInst>(U.getUser());
+            assert(User->getIntrinsicID() == Intrinsic::invariant_end &&
+                   "The paired instruction should be an invariant_end.");
+            UsesToRemove.push_back(User);
+          }
+          for (unsigned i = 0, e = UsesToRemove.size(); i != e; ++i)
+            EraseInstFromFunction(*UsesToRemove[i]);
+        }
       }
       EraseInstFromFunction(*I);
     }
 
     if (InvokeInst *II = dyn_cast<InvokeInst>(&MI)) {
       // Replace invoke with a NOP intrinsic to maintain the original CFG
       Module *M = II->getParent()->getParent()->getParent();
       Function *F = Intrinsic::getDeclaration(M, Intrinsic::donothing);

 }
 
 static bool
 combineInstructionsOverFunction(Function &F, InstCombineWorklist &Worklist,
                                 AliasAnalysis *AA, AssumptionCache &AC,
                                 TargetLibraryInfo &TLI, DominatorTree &DT,
                                 LoopInfo *LI = nullptr) {
   auto &DL = F.getParent()->getDataLayout();
+  auto &InvInfo = F.getParent()->getInvariantInfo();
 
   /// Builder - This is an IRBuilder that automatically inserts new
   /// instructions into the worklist when they are created.
   IRBuilder<true, TargetFolder, InstCombineIRInserter> Builder(
       F.getContext(), TargetFolder(DL), InstCombineIRInserter(Worklist, &AC));
 
   // Lower dbg.declare intrinsics otherwise their value may be clobbered
   // by instcombiner.
   bool DbgDeclaresChanged = LowerDbgDeclare(F);
 
   // Iterate while there is work to do.
   int Iteration = 0;
   for (;;) {
     ++Iteration;
     DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "
                  << F.getName() << "\n");
 
     bool Changed = false;
     if (prepareICWorklistFromFunction(F, DL, &TLI, Worklist))
       Changed = true;
 
     InstCombiner IC(Worklist, &Builder, F.optForMinSize(),
-                    AA, &AC, &TLI, &DT, DL, LI);
+                    AA, &AC, &TLI, &DT, DL, InvInfo, LI);
     if (IC.run())
       Changed = true;
 
     if (!Changed)
       break;
   }
 
   return DbgDeclaresChanged || Iteration > 1;