[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

237

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 ↗

(On Diff #91999)

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 ↗

(On Diff #91999)

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 ↗

(On Diff #91999)

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

71

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.

lib/Transforms/Scalar/LoadCombine.cpp

 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetFolder.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
struct LoadPOPPair {
   PointerOffsetPair POP;
   /// \brief The new load needs to be created before the first load in IR order.
   unsigned InsertOrder;
 };
 
 class LoadCombine : public BasicBlockPass {
   LLVMContext *C;
   AliasAnalysis *AA;
+  DominatorTree *DT;
 
 public:
   LoadCombine() : BasicBlockPass(ID), C(nullptr), AA(nullptr) {
     initializeLoadCombinePass(*PassRegistry::getPassRegistry());
   }
-  
   using llvm::Pass::doInitialization;
   bool doInitialization(Function &) override;
   bool runOnBasicBlock(BasicBlock &BB) override;
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AAResultsWrapperPass>();
+    AU.addRequired<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 
   StringRef getPassName() const override { return LDCOMBINE_NAME; }
   static char ID;
 
   typedef IRBuilder<TargetFolder> BuilderTy;
 
 private:
bool LoadCombine::combineLoads(SmallVectorImpl<LoadPOPPair> &Loads) {
   }
 
   NumLoadsCombined = NumLoadsCombined + Loads.size();
   return true;
 }
 
 bool LoadCombine::runOnBasicBlock(BasicBlock &BB) {
   if (skipBasicBlock(BB))
     return false;
 
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+  // Skip analysing dead blocks (not forward reachable from function entry).
+  if (!DT->isReachableFromEntry(&BB)) {
+    DEBUG(dbgs() << "LC: skipping unreachable " << BB.getName() <<
+          " in " << BB.getParent()->getName() << "\n");
+    return false;
+  }
 
   IRBuilder<TargetFolder> TheBuilder(
       BB.getContext(), TargetFolder(BB.getModule()->getDataLayout()));
   Builder = &TheBuilder;
 
   DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> LoadMap;
   AliasSetTracker AST(*AA);
 

test/Transforms/LoadCombine/deadcode.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -load-combine -S < %s | FileCheck %s
+
+; 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() {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    ret void
+; CHECK:       bb1:
+; CHECK-NEXT:    [[_TMP4:%.*]] = load i16, i16* [[_TMP10:%.*]], align 1
+; CHECK-NEXT:    [[_TMP10]] = getelementptr i16, i16* [[_TMP10]], i16 1
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[_TMP7:%.*]] = load i16, i16* [[_TMP12:%.*]], align 1
+; CHECK-NEXT:    [[_TMP12]] = getelementptr i16, i16* [[_TMP12]], i16 1
+; CHECK-NEXT:    br label [[BB2:%.*]]
+;
+  ret void
+
+bb1:
+  %_tmp4 = load i16, i16* %_tmp10, align 1
+  %_tmp10 = getelementptr i16, i16* %_tmp10, i16 1
+  br label %bb1
+
+; A second basic block. Running the test with -debug-pass=Executions shows
+; that we only run the Dominator Tree Construction one time for each function,
+; also when having multiple basic blocks in the function.
+bb2:
+  %_tmp7 = load i16, i16* %_tmp12, align 1
+  %_tmp12 = getelementptr i16, i16* %_tmp12, i16 1
+  br label %bb2
+
+}