Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -170,6 +170,7 @@ void initializeLoopInstSimplifyPass(PassRegistry&); void initializeLoopRotatePass(PassRegistry&); void initializeLoopSimplifyPass(PassRegistry&); +void initializeLoopSimplifyCFGPass(PassRegistry&); void initializeLoopStrengthReducePass(PassRegistry&); void initializeGlobalMergePass(PassRegistry&); void initializeLoopRerollPass(PassRegistry&); Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h +++ include/llvm/LinkAllPasses.h @@ -106,6 +106,7 @@ (void) llvm::createLoopExtractorPass(); (void) llvm::createLoopInterchangePass(); (void) llvm::createLoopSimplifyPass(); + (void) llvm::createLoopSimplifyCFGPass(); (void) llvm::createLoopStrengthReducePass(); (void) llvm::createLoopRerollPass(); (void) llvm::createLoopUnrollPass(); Index: include/llvm/Transforms/Scalar.h =================================================================== --- include/llvm/Transforms/Scalar.h +++ include/llvm/Transforms/Scalar.h @@ -493,6 +493,13 @@ // FunctionPass *createLoopLoadEliminationPass(); +//===----------------------------------------------------------------------===// +// +// LoopSimplifyCFG - This pass performs basic CFG simplification on loops, +// primarily to help other loop passes. +// +Pass *createLoopSimplifyCFGPass(); + } // End llvm namespace #endif Index: lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- lib/Transforms/Scalar/CMakeLists.txt +++ lib/Transforms/Scalar/CMakeLists.txt @@ -24,6 +24,7 @@ LoopLoadElimination.cpp LoopRerollPass.cpp LoopRotation.cpp + LoopSimplifyCFG.cpp LoopStrengthReduce.cpp LoopUnrollPass.cpp LoopUnswitch.cpp Index: lib/Transforms/Scalar/LoopSimplifyCFG.cpp =================================================================== --- lib/Transforms/Scalar/LoopSimplifyCFG.cpp +++ lib/Transforms/Scalar/LoopSimplifyCFG.cpp @@ -0,0 +1,117 @@ +//===--------- LoopSimplifyCFG.cpp - Loop CFG Simplification Pass ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the Loop SimplifyCFG Pass. This pass is responsible for +// basic loop CFG cleanup, primarily to assist other loop passes. If you +// encounter a noncanonical CFG construct that causes another loop pass to +// perform suboptimally, this is the place to fix it up. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/DependenceAnalysis.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Dominators.h" +#include "llvm/Transforms/Utils/Local.h" +using namespace llvm; + +#define DEBUG_TYPE "loop-simplifycfg" + +namespace { +class LoopSimplifyCFG : public LoopPass { +public: + static char ID; // Pass ID, replacement for typeid + LoopSimplifyCFG() : LoopPass(ID) { + initializeLoopSimplifyCFGPass(*PassRegistry::getPassRegistry()); + } + + bool runOnLoop(Loop *L, LPPassManager &) override; + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + + AU.addPreserved(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreservedID(LoopSimplifyID); + AU.addPreservedID(LCSSAID); + } +}; +} + +char LoopSimplifyCFG::ID = 0; +INITIALIZE_PASS_BEGIN(LoopSimplifyCFG, "loop-simplifycfg", "Simplify loop CFG", + false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(LoopSimplify) +INITIALIZE_PASS_DEPENDENCY(LCSSA) +INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass) +INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass) +INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) +INITIALIZE_PASS_END(LoopSimplifyCFG, "loop-simplifycfg", "Simplify loop CFG", + false, false) + +Pass *llvm::createLoopSimplifyCFGPass() { return new LoopSimplifyCFG(); } + +/// runOnLoop - Perform basic CFG simplifications to assist other loop passes. +/// For now, this only attempts to merge blocks in the trivial case. +bool LoopSimplifyCFG::runOnLoop(Loop *L, LPPassManager &) { + if (skipOptnoneFunction(L)) + return false; + + bool Changed = false; + DominatorTree *DT = &getAnalysis().getDomTree(); + LoopInfo *LI = &getAnalysis().getLoopInfo(); + + // Copy blocks into a temporary array to avoid iterator invalidation issues + // as we remove them. + SmallVector Blocks; + Blocks.append(L->block_begin(), L->block_end()); + + for (auto Block : Blocks) { + // Attempt to merge blocks in the trivial case. Don't modify blocks which + // belong to other loops. + BasicBlock *Succ = dyn_cast_or_null(Block); + if (!Succ) + continue; + + BasicBlock *Pred = Succ->getSinglePredecessor(); + if (!Pred || !Pred->getSingleSuccessor() || LI->getLoopFor(Pred) != L) + continue; + + // Pred is going to disappear, so we need to update the loop info. + if (L->getHeader() == Pred) + L->moveToHeader(Succ); + LI->removeBlock(Pred); + MergeBasicBlockIntoOnlyPred(Succ, DT); + Changed = true; + } + + return Changed; +} Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -84,6 +84,7 @@ initializeFloat2IntPass(Registry); initializeLoopDistributePass(Registry); initializeLoopLoadEliminationPass(Registry); + initializeLoopSimplifyCFGPass(Registry); } void LLVMInitializeScalarOpts(LLVMPassRegistryRef R) { @@ -154,6 +155,10 @@ unwrap(PM)->add(createLoopRerollPass()); } +void LLVMAddLoopSimplifyCFGPass(LLVMPassManagerRef PM) { + unwrap(PM)->add(createLoopSimplifyCFGPass()); +} + void LLVMAddLoopUnrollPass(LLVMPassManagerRef PM) { unwrap(PM)->add(createLoopUnrollPass()); } Index: test/Transforms/LoopSimplifyCFG/merge-header.ll =================================================================== --- test/Transforms/LoopSimplifyCFG/merge-header.ll +++ test/Transforms/LoopSimplifyCFG/merge-header.ll @@ -0,0 +1,34 @@ +; RUN: opt -S -loop-simplifycfg < %s | FileCheck %s + +; CHECK-LABEL: foo +; CHECK: entry: +; CHECK-NEXT: br label %[[LOOP:[a-z]+]] +; CHECK: [[LOOP]]: +; CHECK-NEXT: phi +; CHECK-NOT: br label +; CHECK: br i1 +define i32 @foo(i32* %P, i64* %Q) { +entry: + br label %outer + +outer: ; preds = %outer.latch2, %entry + %y.2 = phi i32 [ 0, %entry ], [ %y.inc2, %outer.latch2 ] + br label %inner + +inner: ; preds = %outer + store i32 0, i32* %P + store i32 1, i32* %P + store i32 2, i32* %P + %y.inc2 = add nsw i32 %y.2, 1 + %exitcond.outer = icmp eq i32 %y.inc2, 3 + store i32 %y.2, i32* %P + br i1 %exitcond.outer, label %exit, label %outer.latch2 + +outer.latch2: ; preds = %inner + %t = sext i32 %y.inc2 to i64 + store i64 %t, i64* %Q + br label %outer + +exit: ; preds = %inner + ret i32 0 +}