[LoadCombine] Avoid analysing dead basic blocks

[KennethH]

Summary

Dead basic blocks may be forming a loop, for which SSA form is
fulfilled, but with a circular def-use chain. LoadCombine could
enter an infinite loop when analysing such dead code. This patch
solves the problem by simply avoiding to analyse all basic blocks
that aren't forward reachable, from function entry, in LoadCombine.

Fixes https://bugs.llvm.org/show_bug.cgi?id=27065

[KennethH]

Seems to solve:
opt /tmp/infinite.ll -jump-threading -load-combine
in https://bugs.llvm.org/show_bug.cgi?id=27065

[grandinj]

lib/Transforms/Scalar/LoadCombine.cpp

233

presumably checking IsAlive is cheaper than calling skipBasicBlock, so maybe it should be tested first?

[zzheng]

Can we remove such dead BBs before entering passes that would spin forever on them?

[• dberlin]

In D31032#703353, @zzheng wrote:

Can we remove such dead BBs before entering passes that would spin forever on them?

You don't want to :)

lib/IR/LegacyPassManager.cpp

1283

1. You need to define dead.

If you mean "forward unreachable", please use that.

2. RPOT is not the optimal order for some problems (in fact, for some, it's optimally bad), and forcing that order seems ... concerning.

I'm pretty strongly against forcing a bb order in a generic pass infrastructure.

3. It looks like we have 3 or 4 basic block passes.

Are they getting anything from being basicblockpasses?

It looks like they could all be trivially changed to functionpasses, and those that can't handle dead code, could just be changed to do what they need to.

For example, DCE has a dominator tree around, it can tell whether things are forward unreachable without wasting time doing a reverse postorder traversal.

IMHO, that is a better solution (and helps new PM) than forcing a pass order here.

[bjope]

lib/IR/LegacyPassManager.cpp

1283

What do you mean by "forcing an order"?

We have not changed the order in which basic block passes are executed here. All we did was adding the IsAlive flag to tell the basic block passes if the BB it should operate on is "forward reachable" (from the function entry) or not. And then it is up to each BasicBlockPass to make a choice if it should operate on the BB or not.

The idea was that passes like the BasicBlockPassPrinter should be able to also print the dead blocks, whereas LoadCombine could avoid spending time on optimizing the code that most likely will be removed by DCE later anyway. So that is why we provide the flag instead of simply skipping to iterate over the "dead" blocks.

[• dberlin]

lib/IR/LegacyPassManager.cpp

1283

Yes, you are right, i misread that part.
Note that RPOT is expensive and unnecessary here.
You could just use depth_first_search. Just use the version with an external visited set, and it will fill in the set for you.

I'm still strongly of the opinion to simply kill basicblockpass rather than add another O(basic blocks) walk that not everything needs.

Every other pass also properly handles dead or unreachable code themselves, without help from the pass infrastructure.

[KennethH]

I have updated according to most of the comments.
I think that the re-factoring of all basic block passes to function passed should be done as a separate task.

[• dberlin]

In D31032#706349, @KennethH wrote:

I have updated according to most of the comments.

Note: You are still calling it "IsAlive", which again, does not really tell anyone what it is supposed to mean :)
However, ...

I think that the re-factoring of all basic block passes to function passed should be done as a separate task.

That's fine, if you want to fix it by making BB passes more expensive and doing another walk of all BB's, you are welcome to.
This, to me, feels like a hack-around to try to paper over how these passes operate.
Someone else can approve that if they are comfortable with it :)

[bjope]

Solution was changed into using the DominatorTree analysis to
determine if basic blocks are "dead". This makes the patch
local to LoadCombine.cpp.

[KennethH]

Mr Berlin had a valid point. This looks like a much cleaner solution.

[bjope]

KennethH gave me permission to upload the improved solution (that uses DominatorTree analysis). This feels like a more "kosher" solution.

The currently suggested solution (for avoiding to optimize on dead code in LoadCombine) is similar to the solution used in BBVectorize. So there is really nothing new invented here.

I'm just afraid that I might have missed something fundamental about "adding a new analysis" (my experience in playing around with analysis passes is very limited).
So any feedback is welcome!

[grosser]

This looks pretty straightforward to me. I think if there are no other concerns, I think this should go in.

[davide]

lib/Transforms/Scalar/LoadCombine.cpp

69

I'm not an expert on LoadCombine but I think this preserve is correct because LoadCombine doesn't do any cross-BB combining or modifies the CFG structure. That said, if what I say is correct, I expect setPreserveCFG to preserve the DominatorTree already? Can you please double check?

test/Transforms/LoadCombine/deadcode.ll

2

Can you add a CHECK line, to make sure we leave the block alone?

[bjope]

Addressed comments from davide:

1. Removed the not needed explicit addPreserved for DominatorTree (it is included in setPreservesCFG).
2. Generated CHECKs in the test case.

I also added a second basic block to the test case. This was useful for some manual test to see that the Dominator Tree only is created once per function, even if the LoadCombine pass is executed multiple times (for each BB). I.e. checking that the DomTree actually is preserved.

[KennethH]

Looks good.

[davide]

LGTM now.

include/llvm/Pass.h

public:
 
   /// doInitialization - Virtual method overridden by BasicBlockPass subclasses
   /// to do any necessary per-function initialization.
   ///
   virtual bool doInitialization(Function &);
 
   /// runOnBasicBlock - Virtual method overriden by subclasses to do the
   /// per-basicblock processing of the pass.
+  /// IsAlive can be used to determine if the basicblock is dead or alive.
   ///
-  virtual bool runOnBasicBlock(BasicBlock &BB) = 0;
+  virtual bool runOnBasicBlock(BasicBlock &BB, bool IsAlive) = 0;
 
   /// doFinalization - Virtual method overriden by BasicBlockPass subclasses to
   /// do any post processing needed after all passes have run.
   ///
   virtual bool doFinalization(Function &);
 
   void assignPassManager(PMStack &PMS, PassManagerType T) override;
 

lib/IR/IRPrintingPasses.cpp

class PrintBasicBlockPass : public BasicBlockPass {
   std::string Banner;
 
 public:
   static char ID;
   PrintBasicBlockPass() : BasicBlockPass(ID), Out(dbgs()) {}
   PrintBasicBlockPass(raw_ostream &Out, const std::string &Banner)
       : BasicBlockPass(ID), Out(Out), Banner(Banner) {}
 
-  bool runOnBasicBlock(BasicBlock &BB) override {
+  bool runOnBasicBlock(BasicBlock &BB, bool /* IsAlive */) override {
     Out << Banner << BB;
     return false;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
   }
 

lib/IR/LegacyPassManager.cpp

 //===- LegacyPassManager.cpp - LLVM Pass Infrastructure Implementation ----===//
 //
 //                     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 legacy LLVM Pass Manager infrastructure.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/LegacyPassManager.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/IR/CFG.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/LegacyPassManagers.h"
 #include "llvm/IR/LegacyPassNameParser.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Chrono.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"

 /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
 /// the function, and if so, return true.
 bool BBPassManager::runOnFunction(Function &F) {
   if (F.isDeclaration())
     return false;
 
   bool Changed = doInitialization(F);
 
+  // Scan the functions basic blocks in Reverse Post Order. This excludes dead
+  // basic blocks (it has been seen that the analysis in some passes could hang
+  // when analysing dead basic blocks).
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+  SmallPtrSet<BasicBlock *, 32> LiveBlocks;
+  for (BasicBlock *I : RPOT)
+    LiveBlocks.insert(I);
+
   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       BasicBlockPass *BP = getContainedPass(Index);
       bool LocalChanged = false;
 
       dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, I->getName());
       dumpRequiredSet(BP);
 
       initializeAnalysisImpl(BP);
 
       {
         // If the pass crashes, remember this.
         PassManagerPrettyStackEntry X(BP, *I);
         TimeRegion PassTimer(getPassTimer(BP));
 
-        LocalChanged |= BP->runOnBasicBlock(*I);
+        LocalChanged |= BP->runOnBasicBlock(*I, LiveBlocks.count(&*I));
       }
 
       Changed |= LocalChanged;
       if (LocalChanged)
         dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG,
                      I->getName());
       dumpPreservedSet(BP);
       dumpUsedSet(BP);

lib/Target/NVPTX/NVPTXLowerAlloca.cpp

 using namespace llvm;
 
 namespace llvm {
 void initializeNVPTXLowerAllocaPass(PassRegistry &);
 }
 
 namespace {
 class NVPTXLowerAlloca : public BasicBlockPass {
-  bool runOnBasicBlock(BasicBlock &BB) override;
+  bool runOnBasicBlock(BasicBlock &BB, bool /* IsAlive */) override;
 
 public:
   static char ID; // Pass identification, replacement for typeid
   NVPTXLowerAlloca() : BasicBlockPass(ID) {}
   StringRef getPassName() const override {
     return "convert address space of alloca'ed memory to local";
   }
 };
 } // namespace
 
 char NVPTXLowerAlloca::ID = 1;
 
 INITIALIZE_PASS(NVPTXLowerAlloca, "nvptx-lower-alloca",
                 "Lower Alloca", false, false)
 
 // =============================================================================
 // Main function for this pass.
 // =============================================================================
-bool NVPTXLowerAlloca::runOnBasicBlock(BasicBlock &BB) {
+bool NVPTXLowerAlloca::runOnBasicBlock(BasicBlock &BB, bool /* IsAlive */) {
   if (skipBasicBlock(BB))
     return false;
 
   bool Changed = false;
   for (auto &I : BB) {
     if (auto allocaInst = dyn_cast<AllocaInst>(&I)) {
       Changed = true;
       auto PTy = dyn_cast<PointerType>(allocaInst->getType());

lib/Transforms/Scalar/DCE.cpp

namespace {
   //===--------------------------------------------------------------------===//
   // DeadInstElimination pass implementation
   //
   struct DeadInstElimination : public BasicBlockPass {
     static char ID; // Pass identification, replacement for typeid
     DeadInstElimination() : BasicBlockPass(ID) {
       initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry());
     }
-    bool runOnBasicBlock(BasicBlock &BB) override {
+    bool runOnBasicBlock(BasicBlock &BB, bool /* IsAlive */) override {
       if (skipBasicBlock(BB))
         return false;
       auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
       TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
       bool Changed = false;
       for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
         Instruction *Inst = &*DI++;
         if (isInstructionTriviallyDead(Inst, TLI)) {

lib/Transforms/Scalar/LoadCombine.cpp

 
 public:
   LoadCombine() : BasicBlockPass(ID), C(nullptr), AA(nullptr) {
     initializeLoadCombinePass(*PassRegistry::getPassRegistry());
   }
   
   using llvm::Pass::doInitialization;
   bool doInitialization(Function &) override;
-  bool runOnBasicBlock(BasicBlock &BB) override;
+  bool runOnBasicBlock(BasicBlock &BB, bool IsAlive) override;
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 
   StringRef getPassName() const override { return LDCOMBINE_NAME; }
   static char ID;
 
   typedef IRBuilder<TargetFolder> BuilderTy;
 
 private:
   BuilderTy *Builder;
Value *V = Builder->CreateExtractInteger(
         (L.POP.Offset - Loads[0].POP.Offset).getZExtValue(), "combine.extract");
     L.Load->replaceAllUsesWith(V);
   }
 
   NumLoadsCombined = NumLoadsCombined + Loads.size();
   return true;
 }
 
-bool LoadCombine::runOnBasicBlock(BasicBlock &BB) {
-  if (skipBasicBlock(BB))
+bool LoadCombine::runOnBasicBlock(BasicBlock &BB, bool IsAlive) {
+  if (skipBasicBlock(BB) || !IsAlive)
     return false;
 
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   IRBuilder<TargetFolder> TheBuilder(
       BB.getContext(), TargetFolder(BB.getModule()->getDataLayout()));
   Builder = &TheBuilder;
 

lib/Transforms/Vectorize/BBVectorize.cpp

bool vectorizeBB(BasicBlock &BB) {
           if (!vectorizePairs(BB, true)) break;
         }
       }
 
       DEBUG(dbgs() << "BBV: done!\n");
       return changed;
     }
 
-    bool runOnBasicBlock(BasicBlock &BB) override {
+    bool runOnBasicBlock(BasicBlock &BB, bool /* IsAlive */) override {
       // OptimizeNone check deferred to vectorizeBB().
 
       AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
       DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
       SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
       TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
       TTI = IgnoreTargetInfo
                 ? nullptr

test/Transforms/LoadCombine/deadcode.ll

+; RUN: opt < %s -load-combine -disable-output
+
+; It has been detected that dead loops like the one in this test case can be
+; created by -jump-threading (it was detected by a csmith generated program).
+;
+; According to -verify this is valid input (even if it could be discussed if
+; the dead loop really satisfies SSA form).
+;
+; The problem found was that the -load-combine pass ends up in an infinite loop
+; when analysing the 'bb1' basic block.
+define void @test1() {
+  ret void
+
+bb1:
+  %_tmp4 = load i16, i16* %_tmp10, align 1
+  %_tmp10 = getelementptr i16, i16* %_tmp10, i16 1
+  br label %bb1
+}

tools/bugpoint-passes/TestPasses.cpp

namespace {
   public:
     static char ID; // Pass ID, replacement for typeid
     CrashOnCalls() : BasicBlockPass(ID) {}
   private:
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesAll();
     }
 
-    bool runOnBasicBlock(BasicBlock &BB) override {
+    bool runOnBasicBlock(BasicBlock &BB, bool /* IsAlive */) override {
       for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
         if (isa<CallInst>(*I))
           abort();
 
       return false;
     }
   };
 }
 
 char CrashOnCalls::ID = 0;
 static RegisterPass<CrashOnCalls>
   X("bugpoint-crashcalls",
     "BugPoint Test Pass - Intentionally crash on CallInsts");
 
 namespace {
   /// DeleteCalls - This pass is used to test bugpoint.  It intentionally
   /// deletes some call instructions, "misoptimizing" the program.
   class DeleteCalls : public BasicBlockPass {
   public:
     static char ID; // Pass ID, replacement for typeid
     DeleteCalls() : BasicBlockPass(ID) {}
   private:
-    bool runOnBasicBlock(BasicBlock &BB) override {
+    bool runOnBasicBlock(BasicBlock &BB, bool /* IsAlive */) override {
       for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
         if (CallInst *CI = dyn_cast<CallInst>(I)) {
           if (!CI->use_empty())
             CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
           CI->getParent()->getInstList().erase(CI);
           break;
         }
       return false;

tools/opt/PassPrinters.cpp

struct BasicBlockPassPrinter : public BasicBlockPass {
   bool QuietPass;
 
   BasicBlockPassPrinter(const PassInfo *PI, raw_ostream &out, bool Quiet)
       : BasicBlockPass(ID), PassToPrint(PI), Out(out), QuietPass(Quiet) {
     std::string PassToPrintName = PassToPrint->getPassName();
     PassName = "BasicBlockPass Printer: " + PassToPrintName;
   }
 
-  bool runOnBasicBlock(BasicBlock &BB) override {
+  bool runOnBasicBlock(BasicBlock &BB, bool /* IsAlive */) override {
     if (!QuietPass)
       Out << "Printing Analysis info for BasicBlock '" << BB.getName()
           << "': Pass " << PassToPrint->getPassName() << ":\n";
 
     // Get and print pass...
     getAnalysisID<Pass>(PassToPrint->getTypeInfo())
         .print(Out, BB.getParent()->getParent());
     return false;

unittests/IR/LegacyPassManagerTest.cpp

public:
         EXPECT_FALSE(initialized);
         initialized = true;
         return false;
       }
       bool doInitialization(Function &F) override {
         inited++;
         return false;
       }
-      bool runOnBasicBlock(BasicBlock &BB) override {
+      bool runOnBasicBlock(BasicBlock &BB, bool /* IsAlive */) override {
         run();
         return false;
       }
       bool doFinalization(Function &F) override {
         fin++;
         return false;
       }
       bool doFinalization(Module &M) override {