diff options
author | Cameron Zwarich <zwarich@apple.com> | 2011-01-03 00:25:16 +0000 |
---|---|---|
committer | Cameron Zwarich <zwarich@apple.com> | 2011-01-03 00:25:16 +0000 |
commit | 832f61117d69019376c4aabedd4de3831279e288 (patch) | |
tree | c47be67fe90ab424bf8b7d7e81886dcdb363f968 /lib/Transforms/Scalar | |
parent | 67678c8307bca7fa867059669ead579215cda732 (diff) | |
download | llvm-832f61117d69019376c4aabedd4de3831279e288.tar.gz llvm-832f61117d69019376c4aabedd4de3831279e288.tar.bz2 llvm-832f61117d69019376c4aabedd4de3831279e288.tar.xz |
Add a new loop-instsimplify pass, with the intention of replacing the instance
of instcombine that is currently in the middle of the loop pass pipeline. This
commit only checks in the pass; it will hopefully be enabled by default later.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122719 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Transforms/Scalar')
-rw-r--r-- | lib/Transforms/Scalar/CMakeLists.txt | 1 | ||||
-rw-r--r-- | lib/Transforms/Scalar/LoopInstSimplify.cpp | 112 | ||||
-rw-r--r-- | lib/Transforms/Scalar/Scalar.cpp | 1 |
3 files changed, 114 insertions, 0 deletions
diff --git a/lib/Transforms/Scalar/CMakeLists.txt b/lib/Transforms/Scalar/CMakeLists.txt index 8173a31a86..68c017b9be 100644 --- a/lib/Transforms/Scalar/CMakeLists.txt +++ b/lib/Transforms/Scalar/CMakeLists.txt @@ -13,6 +13,7 @@ add_llvm_library(LLVMScalarOpts LICM.cpp LoopDeletion.cpp LoopIdiomRecognize.cpp + LoopInstSimplify.cpp LoopRotation.cpp LoopStrengthReduce.cpp LoopUnrollPass.cpp diff --git a/lib/Transforms/Scalar/LoopInstSimplify.cpp b/lib/Transforms/Scalar/LoopInstSimplify.cpp new file mode 100644 index 0000000000..0400288031 --- /dev/null +++ b/lib/Transforms/Scalar/LoopInstSimplify.cpp @@ -0,0 +1,112 @@ +//===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs lightweight instruction simplification on loop bodies. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "loop-instsimplify" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/ADT/Statistic.h" +using namespace llvm; + +STATISTIC(NumSimplified, "Number of redundant instructions simplified"); + +namespace { + class LoopInstSimplify : public LoopPass { + public: + static char ID; // Pass ID, replacement for typeid + LoopInstSimplify() : LoopPass(ID) { + initializeLoopInstSimplifyPass(*PassRegistry::getPassRegistry()); + } + + bool runOnLoop(Loop*, LPPassManager&); + + virtual void getAnalysisUsage(AnalysisUsage& AU) const { + AU.setPreservesCFG(); + AU.addRequired<DominatorTree>(); + AU.addPreserved<DominatorTree>(); + AU.addRequired<LoopInfo>(); + AU.addPreserved<LoopInfo>(); + AU.addPreservedID(LCSSAID); + } + }; +} + +char LoopInstSimplify::ID = 0; +INITIALIZE_PASS_BEGIN(LoopInstSimplify, "loop-instsimplify", + "Simplify instructions in loops", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_DEPENDENCY(LoopInfo) +INITIALIZE_PASS_DEPENDENCY(LCSSA) +INITIALIZE_PASS_END(LoopInstSimplify, "loop-instsimplify", + "Simplify instructions in loops", false, false) + +Pass* llvm::createLoopInstSimplifyPass() { + return new LoopInstSimplify(); +} + +bool LoopInstSimplify::runOnLoop(Loop* L, LPPassManager& LPM) { + DominatorTree* DT = &getAnalysis<DominatorTree>(); + const LoopInfo* LI = &getAnalysis<LoopInfo>(); + const TargetData* TD = getAnalysisIfAvailable<TargetData>(); + + bool Changed = false; + bool LocalChanged; + do { + LocalChanged = false; + + SmallPtrSet<BasicBlock*, 32> Visited; + SmallVector<BasicBlock*, 32> VisitStack; + + VisitStack.push_back(L->getHeader()); + + while (!VisitStack.empty()) { + BasicBlock* BB = VisitStack.back(); + VisitStack.pop_back(); + + if (Visited.count(BB)) + continue; + Visited.insert(BB); + + for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { + Instruction* I = BI++; + // Don't bother simplifying unused instructions. + if (!I->use_empty()) { + if (Value* V = SimplifyInstruction(I, TD, DT)) { + I->replaceAllUsesWith(V); + LocalChanged = true; + ++NumSimplified; + } + } + LocalChanged |= RecursivelyDeleteTriviallyDeadInstructions(I); + } + Changed |= LocalChanged; + + DomTreeNode* Node = DT->getNode(BB); + const std::vector<DomTreeNode*>& Children = Node->getChildren(); + for (unsigned i = 0; i < Children.size(); ++i) { + // Only visit children that are in the same loop. + BasicBlock* ChildBB = Children[i]->getBlock(); + if (!Visited.count(ChildBB) && LI->getLoopFor(ChildBB) == L) + VisitStack.push_back(ChildBB); + } + } + } while (LocalChanged); + + // Nothing that SimplifyInstruction() does should invalidate LCSSA form. + assert(L->isLCSSAForm(*DT)); + + return Changed; +} diff --git a/lib/Transforms/Scalar/Scalar.cpp b/lib/Transforms/Scalar/Scalar.cpp index 27c11186d6..2b13bcacc1 100644 --- a/lib/Transforms/Scalar/Scalar.cpp +++ b/lib/Transforms/Scalar/Scalar.cpp @@ -41,6 +41,7 @@ void llvm::initializeScalarOpts(PassRegistry &Registry) { initializeJumpThreadingPass(Registry); initializeLICMPass(Registry); initializeLoopDeletionPass(Registry); + initializeLoopInstSimplifyPass(Registry); initializeLoopRotatePass(Registry); initializeLoopStrengthReducePass(Registry); initializeLoopUnrollPass(Registry); |