Adapt the use of @llvm.invariant.start/end intrinsics for load elimination purposes from -gvn to -instcombine

[lvoufo]

Summary

Like -gvn (and -globalopt), -instcombine is made to require the -invariant-info-marker pass; and the lookup of available loads that it depends on (FindAvailableLoadedValue() in Loads.cpp) also takes invariant info into consideration.

Changes in the definition of FindAvailableLoadedValue() prompt updates of its calls in Lint.cpp and JumpTherading.cpp.

In addition, invariant info analysis must be registered as a function analysis to preserve regression tests with 'opt -passes=instcombine' such as 'test/Transforms/InstCombine/load.ll'. [cf. PassBuilder.cpp and PassRegistry.cpp]

[lvoufo]

Fix patch.

include/llvm/Analysis/Loads.h

 // This file declares simple local analyses for load instructions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_LOADS_H
 #define LLVM_ANALYSIS_LOADS_H
 
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/InvariantInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/Support/CommandLine.h"
 
 namespace llvm {
 
 class DataLayout;
 class MDNode;
 

 /// specify an alias analysis implementation, which makes this more precise.
 ///
 /// If AATags is non-null and a load or store is found, the AA tags from the
 /// load or store are recorded there.  If there are no AA tags or if no access
 /// is found, it is left unmodified.
 Value *FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB,
                                 BasicBlock::iterator &ScanFrom,
                                 unsigned MaxInstsToScan = DefMaxInstsToScan,
+                                InvariantInfo *InvInfo = nullptr,
                                 AliasAnalysis *AA = nullptr,
                                 AAMDNodes *AATags = nullptr);
 
 }
 
 #endif

lib/Analysis/Lint.cpp

if (LoadInst *L = dyn_cast<LoadInst>(V)) {
     BasicBlock::iterator BBI = L->getIterator();
     BasicBlock *BB = L->getParent();
     SmallPtrSet<BasicBlock *, 4> VisitedBlocks;
     for (;;) {
       if (!VisitedBlocks.insert(BB).second)
         break;
       if (Value *U =
           FindAvailableLoadedValue(L->getPointerOperand(),
-                                   BB, BBI, DefMaxInstsToScan, AA))
+                                   BB, BBI, DefMaxInstsToScan, nullptr, AA))
         return findValueImpl(U, OffsetOk, Visited);
       if (BBI != BB->begin()) break;
       BB = BB->getUniquePredecessor();
       if (!BB) break;
       BBI = BB->end();
     }
   } else if (PHINode *PN = dyn_cast<PHINode>(V)) {
     if (Value *W = PN->hasConstantValue())

lib/Analysis/Loads.cpp

 /// makes this more precise.
 ///
 /// If \c AATags is non-null and a load or store is found, the AA tags from the
 /// load or store are recorded there. If there are no AA tags or if no access is
 /// found, it is left unmodified.
 Value *llvm::FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB,
                                       BasicBlock::iterator &ScanFrom,
                                       unsigned MaxInstsToScan,
+                                      InvariantInfo *InvInfo,
                                       AliasAnalysis *AA, AAMDNodes *AATags) {
   if (MaxInstsToScan == 0)
     MaxInstsToScan = ~0U;
 
   Type *AccessTy = cast<PointerType>(Ptr->getType())->getElementType();
 
   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.
+  PreserveInvariantInfoRAII Preserved(StrippedPtr, DL, InvInfo);
+
   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/Passes/PassBuilder.cpp

 /// helpers to aid in analyzing, debugging, and testing passes and pass
 /// pipelines.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Passes/PassBuilder.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/InvariantInfo.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/PassManager.h"

lib/Passes/PassRegistry.def

 CGSCC_PASS("no-op-cgscc", NoOpCGSCCPass())
 #undef CGSCC_PASS
 
 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())
 FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis())
+FUNCTION_ANALYSIS("invariantinfo", InvariantInfoAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
 FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis())
 FUNCTION_ANALYSIS("scalar-evolution", ScalarEvolutionAnalysis())
 FUNCTION_ANALYSIS("targetlibinfo", TargetLibraryAnalysis())
 FUNCTION_ANALYSIS("targetir",
                   TM ? TM->getTargetIRAnalysis() : TargetIRAnalysis())
 #undef FUNCTION_ANALYSIS
 

lib/Transforms/IPO/GlobalOpt.cpp

static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL,
                                       InvariantInfo &InvInfo) {
 
   // Scan the function's blocks to process invariant (start) intrinsics.
   // This will mark writeonce global variables as written, and is necessary to
   // do here because EvaluateBlock(), via EvaluateFunction() (below), could
   // exit before processing the invariant intrinsic call, e.g., if a call to
   // a function declaration that we cannot constant fold occurs before the
   // intrinsic call.
-  //processInvariantIntrinsics(InvInfo, F);
+  processInvariantIntrinsics(InvInfo, F);
 
   // Call the function.
   Evaluator Eval(DL, TLI);
   Constant *RetValDummy;
   bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
                                            SmallVector<Constant*, 0>());
 
   if (EvalSuccess) {

lib/Transforms/InstCombine/InstCombineCalls.cpp

 //===- InstCombineCalls.cpp -----------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visitCall and visitInvoke functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/InvariantInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Statepoint.h"
 #include "llvm/Transforms/Utils/BuildLibCalls.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
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:
   // Mode in which we are running the combiner.
   const bool MinimizeSize;
 
   AliasAnalysis *AA;
 
   // Required analyses.
   // FIXME: These can never be null and should be references.
   AssumptionCache *AC;
+  InvariantInfo *InvInfo;
   TargetLibraryInfo *TLI;
   DominatorTree *DT;
   const DataLayout &DL;
 
   // 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), InvInfo(InvInfo), TLI(TLI), DT(DT), DL(DL), 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/InstCombineLoadStoreAlloca.cpp

Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
 
   // Do really simple store-to-load forwarding and load CSE, to catch cases
   // where there are several consecutive memory accesses to the same location,
   // separated by a few arithmetic operations.
   BasicBlock::iterator BBI(LI);
   AAMDNodes AATags;
   if (Value *AvailableVal =
       FindAvailableLoadedValue(Op, LI.getParent(), BBI,
-                               DefMaxInstsToScan, AA, &AATags)) {
+                               DefMaxInstsToScan, InvInfo, AA, &AATags)) {
     if (LoadInst *NLI = dyn_cast<LoadInst>(AvailableVal)) {
       unsigned KnownIDs[] = {
           LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
           LLVMContext::MD_noalias,         LLVMContext::MD_range,
           LLVMContext::MD_invariant_load,  LLVMContext::MD_nonnull,
           LLVMContext::MD_invariant_group, LLVMContext::MD_align,
           LLVMContext::MD_dereferenceable,
           LLVMContext::MD_dereferenceable_or_null};

lib/Transforms/InstCombine/InstructionCombining.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/InvariantInfo.h"
 #include "llvm/Analysis/LibCallSemantics.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL,
   }
 
   return MadeIRChange;
 }
 
 static bool
 combineInstructionsOverFunction(Function &F, InstCombineWorklist &Worklist,
                                 AliasAnalysis *AA, AssumptionCache &AC,
+                                InvariantInfo &InvInfo,
                                 TargetLibraryInfo &TLI, DominatorTree &DT,
                                 LoopInfo *LI = nullptr) {
   auto &DL = F.getParent()->getDataLayout();
 
   /// 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));
for (;;) {
     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;
 }
 
 PreservedAnalyses InstCombinePass::run(Function &F,
                                        AnalysisManager<Function> *AM) {
   auto &AC = AM->getResult<AssumptionAnalysis>(F);
+  auto &InvInfo = AM->getResult<InvariantInfoAnalysis>(F);
   auto &DT = AM->getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM->getResult<TargetLibraryAnalysis>(F);
 
   auto *LI = AM->getCachedResult<LoopAnalysis>(F);
 
   // FIXME: The AliasAnalysis is not yet supported in the new pass manager
-  if (!combineInstructionsOverFunction(F, Worklist, nullptr, AC, TLI, DT, LI))
+  if (!combineInstructionsOverFunction(F, Worklist, nullptr, AC, InvInfo,
+                                       TLI, DT, LI))
     // No changes, all analyses are preserved.
     return PreservedAnalyses::all();
 
   // Mark all the analyses that instcombine updates as preserved.
   // FIXME: Need a way to preserve CFG analyses here!
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   return PA;
public:
   bool runOnFunction(Function &F) override;
 };
 }
 
 void InstructionCombiningPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
   AU.addRequired<AAResultsWrapperPass>();
   AU.addRequired<AssumptionCacheTracker>();
+  AU.addRequired<InvariantInfoMarkerPass>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addPreserved<GlobalsAAWrapperPass>();
 }
 
 bool InstructionCombiningPass::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
   // Required analyses.
   auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+  auto &InvInfo = getAnalysis<InvariantInfoMarkerPass>().getInvariantInfo();
   auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 
   // Optional analyses.
   auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
 
-  return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, LI);
+  return combineInstructionsOverFunction(F, Worklist, AA, AC, InvInfo,
+                                         TLI, DT, LI);
 }
 
 char InstructionCombiningPass::ID = 0;
 INITIALIZE_PASS_BEGIN(InstructionCombiningPass, "instcombine",
                       "Combine redundant instructions", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(InvariantInfoMarkerPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_END(InstructionCombiningPass, "instcombine",
                     "Combine redundant instructions", false, false)
 
 // Initialization Routines

lib/Transforms/Scalar/JumpThreading.cpp

for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB);
     // If we already scanned this predecessor, skip it.
     if (!PredsScanned.insert(PredBB).second)
       continue;
 
     // Scan the predecessor to see if the value is available in the pred.
     BBIt = PredBB->end();
     AAMDNodes ThisAATags;
     Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt,
-                                                    DefMaxInstsToScan,
+                                                    DefMaxInstsToScan, nullptr,
                                                     nullptr, &ThisAATags);
     if (!PredAvailable) {
       OneUnavailablePred = PredBB;
       continue;
     }
 
     // If AA tags disagree or are not present, forget about them.
     if (AATags != ThisAATags) AATags = AAMDNodes();

test/Transforms/LoadElim/invariant.ll

-; RUN: opt < %s -gvn -S | FileCheck %s --check-prefix=CHECKL --check-prefix=CHECK
-; RUN: opt < %s -globalopt -gvn -S | FileCheck %s --check-prefix=CHECKG --check-prefix=CHECK
+; RUN: opt < %s -gvn -S         | FileCheck %s --check-prefix=CHECKL --check-prefix=CHECK
+; RUN: opt < %s -instcombine -S | FileCheck %s --check-prefix=CHECKL --check-prefix=CHECK
+; RUN: opt < %s -globalopt -gvn -S         | FileCheck %s --check-prefix=CHECKG --check-prefix=CHECK
+; RUN: opt < %s -globalopt -instcombine -S | FileCheck %s --check-prefix=CHECKG --check-prefix=CHECK
 
 ; On a given pointer to allocated memory, invariant_start/end intrinsic
 ; calls indicate that the memory can be considered constant for load
 ; elimination purposes.
 
 define void @example() {
 entry:
   %i = alloca i32