In LICM, don't create more than one copy of an instruction per loop exit block when sinking.

[eugenis]

Summary

Fixes exponential compilation complexity in PR19835.

http://llvm.org/bugs/show_bug.cgi?id=19835

[aemerson]

On the surface changes look OK to me, but obviously wait for someone else to review.

One thing about the test: AFAIK we've moved away from the convention of adding the dates to the names of tests.

[eugenis]

Renamed the test.

[eugenis]

Thanks.
There is ~14 tests starting with 2014-, but I agree it's a waste of space.

[hfinkel]

Please make sure that you include the explanation from the PR (starting with "The problem is in LICM::sink, which does not handle the following pattern well:") into the commit message. LGTM.

test/Transforms/LICM/extra-copies.ll

37

Please remove the extra metadata (like this one), and any unneeded attributes.

[chandlerc]

What Hal said, plus one more request. =] Patch looks good otherwise.

lib/Transforms/Scalar/LICM.cpp

567–598

I would factor some part of this into a helper function, there is too much deeply nested conditional logic here. Maybe the right thing to do is to factor out the logic handling the build up a clone in the exit block?

(But do that in a separate patch either before or after landing th ebugfix)

[eugenis]

test/Transforms/LICM/extra-copies.ll

37

done

[eugenis]

Committed as r211673.
Thanks for the review!
I'll look into refactoring this code now.

lib/Transforms/Scalar/LICM.cpp

void LICM::sink(Instruction &I) {
   Changed = true;
 
 #ifndef NDEBUG
   SmallVector<BasicBlock *, 32> ExitBlocks;
   CurLoop->getUniqueExitBlocks(ExitBlocks);
   SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end());
 #endif
 
+  // Clones of this instruction. Don't create more than one per exit block!
+  SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
+
   // If this instruction is only used outside of the loop, then all users are
   // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
   // the instruction.
   while (!I.use_empty()) {
     // The user must be a PHI node.
     PHINode *PN = cast<PHINode>(I.user_back());
 
     BasicBlock *ExitBlock = PN->getParent();
     assert(ExitBlockSet.count(ExitBlock) &&
            "The LCSSA PHI is not in an exit block!");
 
-    Instruction *New = I.clone();
+    Instruction *New;
+    auto It = SunkCopies.find(ExitBlock);
+    if (It != SunkCopies.end()) {
+      New = It->second;
+    } else {
+      New = I.clone();
+      SunkCopies[ExitBlock] = New;
       ExitBlock->getInstList().insert(ExitBlock->getFirstInsertionPt(), New);
       if (!I.getName().empty())
         New->setName(I.getName() + ".le");
 
       // Build LCSSA PHI nodes for any in-loop operands. Note that this is
       // particularly cheap because we can rip off the PHI node that we're
       // replacing for the number and blocks of the predecessors.
       // OPT: If this shows up in a profile, we can instead finish sinking all
       // invariant instructions, and then walk their operands to re-establish
       // LCSSA. That will eliminate creating PHI nodes just to nuke them when
       // sinking bottom-up.
       for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
            ++OI)
         if (Instruction *OInst = dyn_cast<Instruction>(*OI))
           if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
             if (!OLoop->contains(PN)) {
               PHINode *OpPN = PHINode::Create(
                   OInst->getType(), PN->getNumIncomingValues(),
                   OInst->getName() + ".lcssa", ExitBlock->begin());
               for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
                 OpPN->addIncoming(OInst, PN->getIncomingBlock(i));
               *OI = OpPN;
             }
+    }
 
     PN->replaceAllUsesWith(New);
     PN->eraseFromParent();
   }
 
   CurAST->deleteValue(&I);
   I.eraseFromParent();
 }
 

test/Transforms/LICM/extra-copies.ll

+; RUN: opt < %s -licm -S | FileCheck %s
+; PR19835
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @f(i32 %x) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %storemerge4 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %mul = mul nsw i32 %x, %x
+  %add2 = add nsw i32 %mul, %x
+  %mul3 = add nsw i32 %add2, %mul
+  %inc = add nsw i32 %storemerge4, 1
+  %cmp = icmp slt i32 %inc, 100
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  %a9.0.lcssa = phi i32 [ %mul3, %for.body ]
+  ret i32 %a9.0.lcssa
+}
+
+; Test that there is exactly one copy of mul nsw i32 %x, %x in the exit block.
+; CHECK: define i32 @f(i32 [[X:%.*]])
+; CHECK: for.end:
+; CHECK-NOT: mul nsw i32 [[X]], [[X]]
+; CHECK: mul nsw i32 [[X]], [[X]]
+; CHECK-NOT: mul nsw i32 [[X]], [[X]]