[Reassociate] Skip analysis of dead code to avoid infinite loop.

[bjope]

Summary

It was detected that the reassociate pass could enter an inifite
loop when analysing dead code. Simply skipping to analyse basic
blocks that are dead avoids such problems (and as a side effect
we avoid spending time on optimising dead code).

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

[davide]

lib/Transforms/Scalar/Reassociate.cpp

2182–2185 ↗

(On Diff #76427)

You may want to expand this comment a bit.

[• dberlin]

lib/Transforms/Scalar/Reassociate.cpp

2182–2185 ↗

(On Diff #76427)

There is also a much simpler and more consistent fix:

Iterate in the same order rankmap was built.

You can share the ReversePostOrder ordering, and use it here, and then both are doing the same thing, so there can't be any mismatches.

[bjope]

lib/Transforms/Scalar/Reassociate.cpp

2182–2185 ↗

(On Diff #76427)

Ok. I have no idea if the iteration order in here in ReassociatePass::run is important or not, so I did not dare to do such a change. I just wanted to correct the bug in easiest way without changing anything else.

I also read somewhere that the ReversePostOrder iteration is very expensive and should be avoided. So doing that twice seemed like a bad idea. But maybe your idea was to save the order somehow by adding another data structure?

If it does not matter in which order the basic blocks are analysed, then I guess it is possible to iterate over the keys in the RankMap map (however, I'm not familiar about the DenseMap iterators so I do not know about if that is cheap, if order is predictable when debugging different builds, etc).

I still think my solution is a minimal impact bugfix.
If someone wants to refactor/optimise etc on this later, then I don't mind.

[bjope]

Updated according to comments.

The solution is now based on using the same Reverse Post Order Traversal
both when building the RankMap and when doing optimisations.
This changes the order in which basic blocks are optimised, but as far
as I understand the end result should be the same.

[mehdi_amini]

LGTM, Thanks!

llvm/trunk/include/llvm/Transforms/Scalar/Reassociate.h

class ReassociatePass : public PassInfoMixin<ReassociatePass> {
   DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
   SetVector<AssertingVH<Instruction>> RedoInsts;
   bool MadeChange;
 
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
 
 private:
-  void BuildRankMap(Function &F);
+  void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
   unsigned getRank(Value *V);
   void canonicalizeOperands(Instruction *I);
   void ReassociateExpression(BinaryOperator *I);
   void RewriteExprTree(BinaryOperator *I,
                        SmallVectorImpl<reassociate::ValueEntry> &Ops);
   Value *OptimizeExpression(BinaryOperator *I,
                             SmallVectorImpl<reassociate::ValueEntry> &Ops);
   Value *OptimizeAdd(Instruction *I,

llvm/trunk/lib/Transforms/Scalar/Reassociate.cpp

if (V->hasOneUse() && isa<Instruction>(V) &&
       (cast<Instruction>(V)->getOpcode() == Opcode1 ||
        cast<Instruction>(V)->getOpcode() == Opcode2) &&
       (!isa<FPMathOperator>(V) ||
        cast<Instruction>(V)->hasUnsafeAlgebra()))
     return cast<BinaryOperator>(V);
   return nullptr;
 }
 
-void ReassociatePass::BuildRankMap(Function &F) {
+void ReassociatePass::BuildRankMap(Function &F,
+                                   ReversePostOrderTraversal<Function*> &RPOT) {
   unsigned i = 2;
 
   // Assign distinct ranks to function arguments.
   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
     ValueRankMap[&*I] = ++i;
     DEBUG(dbgs() << "Calculated Rank[" << I->getName() << "] = " << i << "\n");
   }
 
-  ReversePostOrderTraversal<Function *> RPOT(&F);
+  // Traverse basic blocks in ReversePostOrder
   for (BasicBlock *BB : RPOT) {
     unsigned BBRank = RankMap[BB] = ++i << 16;
 
     // Walk the basic block, adding precomputed ranks for any instructions that
     // we cannot move.  This ensures that the ranks for these instructions are
     // all different in the block.
     for (Instruction &I : *BB)
       if (mayBeMemoryDependent(I))
void ReassociatePass::ReassociateExpression(BinaryOperator *I) {
   }
 
   // Now that we ordered and optimized the expressions, splat them back into
   // the expression tree, removing any unneeded nodes.
   RewriteExprTree(I, Ops);
 }
 
 PreservedAnalyses ReassociatePass::run(Function &F, FunctionAnalysisManager &) {
+  // Get the functions basic blocks in Reverse Post Order. This order is used by
+  // BuildRankMap to pre calculate ranks correctly. It also excludes dead basic
+  // blocks (it has been seen that the analysis in this pass could hang when
+  // analysing dead basic blocks).
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+
   // Calculate the rank map for F.
-  BuildRankMap(F);
+  BuildRankMap(F, RPOT);
 
   MadeChange = false;
-  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
+  // Traverse the same blocks that was analysed by BuildRankMap.
+  for (BasicBlock *BI : RPOT) {
+    assert(RankMap.count(&*BI) && "BB should be ranked.");
     // Optimize every instruction in the basic block.
     for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;)
       if (isInstructionTriviallyDead(&*II)) {
         EraseInst(&*II++);
       } else {
         OptimizeInst(&*II);
         assert(II->getParent() == &*BI && "Moved to a different block!");
         ++II;

llvm/trunk/test/Transforms/Reassociate/deadcode.ll

+; RUN: opt < %s -reassociate -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 -reassociate pass ends up in an infinite loop
+; when analysing the 'deadloop1' basic block. See "Bugzilla - Bug 30818".
+define void @deadloop1() {
+  br label %endlabel
+
+deadloop1:
+  %1 = xor i32 %2, 7
+  %2 = xor i32 %1, 8
+  br label %deadloop1
+
+endlabel:
+  ret void
+}
+
+
+; Another example showing that dead code could result in infinite loops in
+; reassociate pass. See "Bugzilla - Bug 30818".
+define void @deadloop2() {
+  br label %endlabel
+
+deadloop2:
+  %1 = and i32 %2, 7
+  %2 = and i32 %3, 8
+  %3 = and i32 %1, 6
+  br label %deadloop2
+
+endlabel:
+  ret void
+}