Index: include/llvm/Transforms/Utils/Local.h =================================================================== --- include/llvm/Transforms/Utils/Local.h +++ include/llvm/Transforms/Utils/Local.h @@ -201,7 +201,8 @@ /// providing the set of loop headers that SimplifyCFG should not eliminate. bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options = {}, - SmallPtrSetImpl *LoopHeaders = nullptr); + SmallPtrSetImpl *LoopHeaders = nullptr, + SmallPtrSetImpl *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 Index: lib/Transforms/Scalar/SimplifyCFGPass.cpp =================================================================== --- lib/Transforms/Scalar/SimplifyCFGPass.cpp +++ lib/Transforms/Scalar/SimplifyCFGPass.cpp @@ -153,15 +153,18 @@ SmallVector, 32> Edges; FindFunctionBackedges(F, Edges); SmallPtrSet LoopHeaders; - for (unsigned i = 0, e = Edges.size(); i != e; ++i) + SmallPtrSet BackEdges; + for (unsigned i = 0, e = Edges.size(); i != e; ++i) { + BackEdges.insert(const_cast(Edges[i].first)); LoopHeaders.insert(const_cast(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; } Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -173,6 +173,7 @@ const TargetTransformInfo &TTI; const DataLayout &DL; SmallPtrSetImpl *LoopHeaders; + SmallPtrSetImpl *BackEdges; const SimplifyCFGOptions &Options; Value *isValueEqualityComparison(TerminatorInst *TI); @@ -198,8 +199,10 @@ public: SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL, SmallPtrSetImpl *LoopHeaders, + SmallPtrSetImpl *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); }; @@ -3839,6 +3842,8 @@ BB->eraseFromParent(); if (LoopHeaders) LoopHeaders->erase(BB); + if (BackEdges) + BackEdges->erase(BB); return true; } @@ -4060,6 +4065,8 @@ BB->eraseFromParent(); if (LoopHeaders) LoopHeaders->erase(BB); + if (BackEdges) + BackEdges->erase(BB); } return true; @@ -4222,6 +4229,8 @@ BB->eraseFromParent(); if (LoopHeaders) LoopHeaders->erase(BB); + if (BackEdges) + BackEdges->erase(BB); return true; } @@ -5726,22 +5735,32 @@ 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. - // 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)) + 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.) + 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 @@ -6052,8 +6071,9 @@ bool llvm::simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options, - SmallPtrSetImpl *LoopHeaders) { + SmallPtrSetImpl *LoopHeaders, + SmallPtrSetImpl *BackEdges) { return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), LoopHeaders, - Options) + BackEdges, Options) .run(BB); } Index: test/Transforms/LoopUnswitch/2015-06-17-Metadata.ll =================================================================== --- test/Transforms/LoopUnswitch/2015-06-17-Metadata.ll +++ test/Transforms/LoopUnswitch/2015-06-17-Metadata.ll @@ -16,7 +16,7 @@ %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 @@ -53,7 +53,7 @@ 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 ] Index: test/Transforms/LoopUnswitch/infinite-loop.ll =================================================================== --- test/Transforms/LoopUnswitch/infinite-loop.ll +++ test/Transforms/LoopUnswitch/infinite-loop.ll @@ -16,7 +16,7 @@ ; 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 Index: test/Transforms/SimplifyCFG/UncondBranchToHeader.ll =================================================================== --- test/Transforms/SimplifyCFG/UncondBranchToHeader.ll +++ test/Transforms/SimplifyCFG/UncondBranchToHeader.ll @@ -2,6 +2,7 @@ ; 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 @@ -16,3 +17,25 @@ 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 +}