From 832f61117d69019376c4aabedd4de3831279e288 Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Mon, 3 Jan 2011 00:25:16 +0000 Subject: [PATCH] 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 --- include/llvm/InitializePasses.h | 1 + include/llvm/Transforms/Scalar.h | 6 ++ lib/Transforms/Scalar/CMakeLists.txt | 1 + lib/Transforms/Scalar/LoopInstSimplify.cpp | 112 +++++++++++++++++++++ lib/Transforms/Scalar/Scalar.cpp | 1 + 5 files changed, 121 insertions(+) create mode 100644 lib/Transforms/Scalar/LoopInstSimplify.cpp diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index 8d3fa86f266..c89d4fefa8a 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -128,6 +128,7 @@ void initializeLoopDeletionPass(PassRegistry&); void initializeLoopDependenceAnalysisPass(PassRegistry&); void initializeLoopExtractorPass(PassRegistry&); void initializeLoopInfoPass(PassRegistry&); +void initializeLoopInstSimplifyPass(PassRegistry&); void initializeLoopRotatePass(PassRegistry&); void initializeLoopSimplifyPass(PassRegistry&); void initializeLoopSplitterPass(PassRegistry&); diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h index f494586c59b..039e4a2f408 100644 --- a/include/llvm/Transforms/Scalar.h +++ b/include/llvm/Transforms/Scalar.h @@ -117,6 +117,12 @@ Pass *createLoopStrengthReducePass(const TargetLowering *TLI = 0); // Pass *createLoopUnswitchPass(bool OptimizeForSize = false); +//===----------------------------------------------------------------------===// +// +// LoopInstSimplify - This pass simplifies instructions in a loop's body. +// +Pass *createLoopInstSimplifyPass(); + //===----------------------------------------------------------------------===// // // LoopUnroll - This pass is a simple loop unrolling pass. diff --git a/lib/Transforms/Scalar/CMakeLists.txt b/lib/Transforms/Scalar/CMakeLists.txt index 8173a31a86b..68c017b9be9 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 00000000000..0400288031b --- /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(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + 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(); + const LoopInfo* LI = &getAnalysis(); + const TargetData* TD = getAnalysisIfAvailable(); + + bool Changed = false; + bool LocalChanged; + do { + LocalChanged = false; + + SmallPtrSet Visited; + SmallVector 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& 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 27c11186d6a..2b13bcacc19 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); -- 2.34.1