[SimplifyCFG] Don't remove preheaders when we need canonical loops.

[dmgreen]

Summary

Commit rL324208 loosened a restriction on removing basic blocks
in the intent to remove empty back edge blocks, but also started
removing preheaders in the process. This prevents the preheaders
from being removed when we want to keep loop simple form.

[efriedma]

You might need to update the BackEdges set in more places, if we can introduce backedges in certain cases.

What passes benefit from having SimplifyCFG keep around empty preheaders?

[skatkov]

Does it eliminate your regression?
I double the Eli's question: "What passes benefit from having SimplifyCFG keep around empty preheaders?"

lib/Transforms/Utils/SimplifyCFG.cpp

5740–5741

It becomes complicated. Could you please re-write it in a more readable way?

I guess lambda with explicit ifs and possible comments may do things cleaner in terms of reading this.

[pacxx]

I don't see any use of empty preheaders. Can you explain for which cases empty preheaders are important?

[dmgreen]

Updated to simplify if condition.

[dmgreen]

Hello all

Yes, from rL324572 I'm seeing multiple small regressions and two large-ish ones (no improvements unfortunately - I usually try to look for reasons why changes like that are a net gain, even if they cause some regressions, but in this case my numbers are not being very kind in that regard). I believe removing preheaders was not intended, and this "fixes" all of the regressions except for one of the big ones. That looks like it's to do with loop rotate choosing a differently loop header, and the knock on affects of that. I'm still trying to pull apart why exactly that is making things worse there.

For this patch - which was suggested by Serguie as a potential fix (I should have mentioned that somewhere - sorry). I agree that if we need loop simple form then that pass will re-create the loop preheader for us. So the change in rL324572 to remove preheaders should be benign, except for block layout, anything that might benefit from less critical edges and the fact that we are repeatedly removing and recreating loop preheaders through the pass pipeline. The NeedCanonicalLoop option seems to be requiring that we don't break loop simple form, which this patch aims to fix. So not a direct fix (I'm not sure that would even be possible for all these regressions) but hopefully a sensible change none-the-less (?)

lib/Transforms/Utils/SimplifyCFG.cpp

5740–5741

I agree this one was giving me trouble. Thanks for the lambda suggestion, that's a good idea.

[skatkov]

What is about Eli's comment?

When you remove backedge you introduce new backedge. So you need to add new backedge to the list of the backedges.

[pacxx]

Maybe we should introduce some annotation to loops that are in simple form. Passes like SimplifyCFG may honor this annotation and don't remove empty preheaders. Removing and recreating empty preheaders seems wrong.

[dmgreen]

When you remove backedge you introduce new backedge. So you need to add new backedge to the list of the backedges.

I looked into this a little, and had convinced myself that it would be OK (if we add a new backedge, we probably don't want to remove it again in the same pass). Looking at it again though, that might not be correct. I've not done much work in simplify cfg before. Do you think this would involve updating the backedge list in many places?

Perhaps we can turn this around, calculate the Preheaders as Preds(Headers) - Backedges and use that instead.

Maybe we should introduce some annotation to loops that are in simple form.

I don't think that annotations are the way that this is usually handled in llvm, if we can help it. (Plus clang creates preheaders, but wouldn't mark the loops as loop simple form.) I guess the standard way to do this would be to have simplifyCFG know more about loops (using LoopInfo and check if the loop is in simple form). But I suspect that isn't what we would want here if we can take a lighter approach.

[skatkov]

In D43293#1011553, @dmgreen wrote:

When you remove backedge you introduce new backedge. So you need to add new backedge to the list of the backedges.

I looked into this a little, and had convinced myself that it would be OK (if we add a new backedge, we probably don't want to remove it again in the same pass). Looking at it again though, that might not be correct. I've not done much work in simplify cfg before. Do you think this would involve updating the backedge list in many places?

Perhaps we can turn this around, calculate the Preheaders as Preds(Headers) - Backedges and use that instead.

I do not follow how computing Preheaders as Preds(Headers) - Backedges will help you.
In general, potentially you can have CFG like empty backedge coming to pre-header only and predecessor of backedge is also empty block having only one predecessor. In this case current implementation will eliminate only one backedge and preserve the second one.

In my understanding each time you are removing backedge you need add all its predecessors to backedge if this backedge is not a loop header. The last case seems to me impossible (otherwise you eliminate the loop and can be asserted).
To minimize changes you can introduce the utility which will do this check (and even you can put LoopHeader erase to the same utility function) and everywhere you invoke backedge erase you can invoke this utility..

include/llvm/Transforms/Utils/Local.h

 /// This function is used to do simplification of a CFG.  For example, it
 /// adjusts branches to branches to eliminate the extra hop, it eliminates
 /// unreachable basic blocks, and does other peephole optimization of the CFG.
 /// It returns true if a modification was made, possibly deleting the basic
 /// block that was pointed to. LoopHeaders is an optional input parameter
 /// providing the set of loop headers that SimplifyCFG should not eliminate.
 bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
                  const SimplifyCFGOptions &Options = {},
-                 SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr);
+                 SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr,
+                 SmallPtrSetImpl<BasicBlock *> *BackEdges = nullptr);
 
 /// This function is used to flatten a CFG. For example, it uses parallel-and
 /// and parallel-or mode to collapse if-conditions and merge if-regions with
 /// identical statements.
 bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr);
 
 /// If this basic block is ONLY a setcc and a branch, and if a predecessor
 /// branches to us and one of our successors, fold the setcc into the

lib/Transforms/Scalar/SimplifyCFGPass.cpp

 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
                                    const SimplifyCFGOptions &Options) {
   bool Changed = false;
   bool LocalChange = true;
 
   SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
   FindFunctionBackedges(F, Edges);
   SmallPtrSet<BasicBlock *, 16> LoopHeaders;
-  for (unsigned i = 0, e = Edges.size(); i != e; ++i)
+  SmallPtrSet<BasicBlock *, 16> BackEdges;
+  for (unsigned i = 0, e = Edges.size(); i != e; ++i) {
+    BackEdges.insert(const_cast<BasicBlock *>(Edges[i].first));
     LoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
+  }
 
   while (LocalChange) {
     LocalChange = false;
 
     // Loop over all of the basic blocks and remove them if they are unneeded.
     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
-      if (simplifyCFG(&*BBIt++, TTI, Options, &LoopHeaders)) {
+      if (simplifyCFG(&*BBIt++, TTI, Options, &LoopHeaders, &BackEdges)) {
         LocalChange = true;
         ++NumSimpl;
       }
     }
     Changed |= LocalChange;
   }
   return Changed;
 }

lib/Transforms/Utils/SimplifyCFG.cpp

struct ValueEqualityComparisonCase {
 
   bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; }
 };
 
 class SimplifyCFGOpt {
   const TargetTransformInfo &TTI;
   const DataLayout &DL;
   SmallPtrSetImpl<BasicBlock *> *LoopHeaders;
+  SmallPtrSetImpl<BasicBlock *> *BackEdges;
   const SimplifyCFGOptions &Options;
 
   Value *isValueEqualityComparison(TerminatorInst *TI);
   BasicBlock *GetValueEqualityComparisonCases(
       TerminatorInst *TI, std::vector<ValueEqualityComparisonCase> &Cases);
   bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
                                                      BasicBlock *Pred,
                                                      IRBuilder<> &Builder);
class SimplifyCFGOpt {
   bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
   bool SimplifyIndirectBr(IndirectBrInst *IBI);
   bool SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder);
   bool SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder);
 
 public:
   SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL,
                  SmallPtrSetImpl<BasicBlock *> *LoopHeaders,
+                 SmallPtrSetImpl<BasicBlock *> *BackEdges,
                  const SimplifyCFGOptions &Opts)
-      : TTI(TTI), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {}
+      : TTI(TTI), DL(DL), LoopHeaders(LoopHeaders), BackEdges(BackEdges),
+        Options(Opts) {}
 
   bool run(BasicBlock *BB);
 };
 
 } // end anonymous namespace
 
 /// Return true if it is safe to merge these two
 /// terminator instructions together.
for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
     BasicBlock *Pred = *PI++;
     removeUnwindEdge(Pred);
   }
 
   // The landingpad is now unreachable.  Zap it.
   BB->eraseFromParent();
   if (LoopHeaders)
     LoopHeaders->erase(BB);
+  if (BackEdges)
+    BackEdges->erase(BB);
   return true;
 }
 
 static bool removeEmptyCleanup(CleanupReturnInst *RI) {
   // If this is a trivial cleanup pad that executes no instructions, it can be
   // eliminated.  If the cleanup pad continues to the caller, any predecessor
   // that is an EH pad will be updated to continue to the caller and any
   // predecessor that terminates with an invoke instruction will have its invoke
if (!UncondBranchPreds.empty() && DupRet) {
     }
 
     // If we eliminated all predecessors of the block, delete the block now.
     if (pred_empty(BB)) {
       // We know there are no successors, so just nuke the block.
       BB->eraseFromParent();
       if (LoopHeaders)
         LoopHeaders->erase(BB);
+      if (BackEdges)
+        BackEdges->erase(BB);
     }
 
     return true;
   }
 
   // Check out all of the conditional branches going to this return
   // instruction.  If any of them just select between returns, change the
   // branch itself into a select/return pair.
bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) {
   }
 
   // If this block is now dead, remove it.
   if (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) {
     // We know there are no successors, so just nuke the block.
     BB->eraseFromParent();
     if (LoopHeaders)
       LoopHeaders->erase(BB);
+    if (BackEdges)
+      BackEdges->erase(BB);
     return true;
   }
 
   return Changed;
 }
 
 static bool CasesAreContiguous(SmallVectorImpl<ConstantInt *> &Cases) {
   assert(Cases.size() >= 1);
for (BasicBlock *OtherPred : predecessors(Succ)) {
     return true;
   }
   return false;
 }
 
 bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI,
                                           IRBuilder<> &Builder) {
   BasicBlock *BB = BI->getParent();
-  BasicBlock *Succ = BI->getSuccessor(0);
+  BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator();
 
   // If the Terminator is the only non-phi instruction, simplify the block.
+  auto ShouldTryToSimplifyUncondBranchFromEmptyBlock = [&]() {
+    BasicBlock *Succ = BI->getSuccessor(0);
+    if (!I->isTerminator() || BB == &BB->getParent()->getEntryBlock())
+      return false;
+
     // If LoopHeader is provided, check if the block or its successor is a loop
     // header. (This is for early invocations before loop simplify and
     // vectorization to keep canonical loop forms for nested loops. These blocks
     // can be eliminated when the pass is invoked later in the back-end.)
-  // Note that if BB has only one predecessor then we do not introduce new
-  // backedge, so we can eliminate BB.
-  bool NeedCanonicalLoop =
-      Options.NeedCanonicalLoop &&
-      (LoopHeaders && std::distance(pred_begin(BB), pred_end(BB)) > 1 &&
-       (LoopHeaders->count(BB) || LoopHeaders->count(Succ)));
-  BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator();
-  if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() &&
-      !NeedCanonicalLoop && TryToSimplifyUncondBranchFromEmptyBlock(BB))
+    if (Options.NeedCanonicalLoop && LoopHeaders) {
+      if (LoopHeaders->count(BB))
+        return false;
+      // If BB is a backedge and has only one predecessor then we do not
+      // introduce new backedge, so we can eliminate BB.
+      if (LoopHeaders->count(Succ) &&
+          ((BackEdges && !BackEdges->count(BB)) || !BB->getSinglePredecessor()))
+        return false;
+    }
+
+    return true;
+  };
+  if (ShouldTryToSimplifyUncondBranchFromEmptyBlock() &&
+      TryToSimplifyUncondBranchFromEmptyBlock(BB))
     return true;
 
   // If the only instruction in the block is a seteq/setne comparison against a
   // constant, try to simplify the block.
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))
     if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) {
       for (++I; isa<DbgInfoIntrinsic>(I); ++I)
         ;
if (SimplifyIndirectBr(IBI))
       return true;
   }
 
   return Changed;
 }
 
 bool llvm::simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
                        const SimplifyCFGOptions &Options,
-                       SmallPtrSetImpl<BasicBlock *> *LoopHeaders) {
+                       SmallPtrSetImpl<BasicBlock *> *LoopHeaders,
+                       SmallPtrSetImpl<BasicBlock *> *BackEdges) {
   return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), LoopHeaders,
-                        Options)
+                        BackEdges, Options)
       .run(BB);
 }

test/Transforms/LoopUnswitch/2015-06-17-Metadata.ll

 
 for.body:                                         ; preds = %for.inc, %for.body.lr.ph
   %inc.i = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
   %mul.i = phi i32 [ 3, %for.body.lr.ph ], [ %mul.p, %for.inc ]
   %add.i = phi i32 [ %a, %for.body.lr.ph ], [ %add.p, %for.inc ]
   %cmp1 = icmp eq i32 %a, 12345
   br i1 %cmp1, label %if.then, label %if.else, !prof !0
 ; CHECK: %cmp1 = icmp eq i32 %a, 12345
-; CHECK-NEXT: br i1 %cmp1, label %for.body.us, label %for.body, !prof !0
+; CHECK-NEXT: br i1 %cmp1, label %for.body.preheader.split.us, label %for.body.preheader.split, !prof !0
 if.then:                                          ; preds = %for.body
 ; CHECK: for.body.us:
 ; CHECK: add nsw i32 %{{.*}}, 123
 ; CHECK: %exitcond.us = icmp eq i32 %inc.us, %b
 ; CHECK: br i1 %exitcond.us, label %for.cond.cleanup, label %for.body.us
   %add = add nsw i32 %add.i, 123
   br label %for.inc
 

 }
 
 define void @foo_swapped(i32 %a, i32 %b) {
 ;CHECK-LABEL: foo_swapped
 entry:
   br label %for.body
 ;CHECK: entry:
 ;CHECK-NEXT: %cmp1 = icmp eq i32 1, 2
-;CHECK-NEXT: br i1 %cmp1, label %for.body, label %for.cond.cleanup.split, !prof !1
+;CHECK-NEXT: br i1 %cmp1, label %entry.split, label %for.cond.cleanup.split, !prof !1
 ;CHECK: for.body:
 for.body:                                         ; preds = %for.inc, %entry
   %inc.i = phi i32 [ 0, %entry ], [ %inc, %if.then ]
   %add.i = phi i32 [ 100, %entry ], [ %add, %if.then ]
   %inc = add nuw nsw i32 %inc.i, 1
   %cmp1 = icmp eq i32 1, 2
   br i1 %cmp1, label %if.then, label  %for.cond.cleanup, !prof !0
 

test/Transforms/LoopUnswitch/infinite-loop.ll

 ; STATS: 2 loop-unswitch - Number of branches unswitched
 ; STATS: 2 loop-unswitch - Number of unswitches that are trivial
 
 ; CHECK-LABEL: @func_16(
 ; CHECK-NEXT: entry:
 ; CHECK-NEXT: br i1 %a, label %entry.split, label %abort0.split
 
 ; CHECK: entry.split:
-; CHECK-NEXT: br i1 %b, label %for.body, label %abort1.split
+; CHECK-NEXT: br i1 %b, label %entry.split.split, label %abort1.split
 
 ; CHECK: for.body:
 ; CHECK-NEXT: br label %for.body
 
 ; CHECK: abort0.split:
 ; CHECK-NEXT: call void @end0() [[NOR_NUW:#[0-9]+]]
 ; CHECK-NEXT: unreachable
 

test/Transforms/SimplifyCFG/UncondBranchToHeader.ll

 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
 
 ; Check that we can get rid of empty block leading to header
 ; if it does not introduce new edge.
+; CHECK-LABEL: test
 define i32 @test(i32 %c) {
 entry:
   br label %header
 header:
   %i = phi i32 [0, %entry], [%i.1, %backedge]
   %i.1 = add i32 %i, 1
   %cmp = icmp slt i32 %i.1, %c
   br i1 %cmp, label %backedge, label %exit
 ; CHECK-NOT: backedge:
 backedge:
   br label %header
 exit:
   ret i32 %i
 }
+
+; But not preheaders
+; CHECK-LABEL test2
+define i32 @test2(i32 %c) {
+entry:
+  %cond = icmp ne i32 %c, 0
+  br i1 %cond, label %preheader, label %exit
+; CHECK: preheader:
+preheader:
+  br label %header
+header:
+  %i = phi i32 [0, %preheader], [%i.1, %backedge]
+  %i.1 = add i32 %i, 1
+  %cmp = icmp slt i32 %i.1, %c
+  br i1 %cmp, label %backedge, label %exit
+; CHECK-NOT: backedge:
+backedge:
+  br label %header
+exit:
+  %r = phi i32 [0, %entry], [%i, %header]
+  ret i32 %r
+}