Index: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/include/llvm/InitializePasses.h @@ -215,6 +215,7 @@ void initializeLoopExtractorPass(PassRegistry&); void initializeLoopIdiomRecognizeLegacyPassPass(PassRegistry&); void initializeLoopInfoWrapperPassPass(PassRegistry&); +void initializeLoopInstSimplifyLegacyPassPass(PassRegistry&); void initializeLoopInterchangePass(PassRegistry&); void initializeLoopLoadEliminationPass(PassRegistry&); void initializeLoopPassPass(PassRegistry&); Index: llvm/trunk/include/llvm/Transforms/Scalar.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Scalar.h +++ llvm/trunk/include/llvm/Transforms/Scalar.h @@ -176,6 +176,12 @@ //===----------------------------------------------------------------------===// // +// LoopInstSimplify - This pass simplifies instructions in a loop's body. +// +Pass *createLoopInstSimplifyPass(); + +//===----------------------------------------------------------------------===// +// // LoopUnroll - This pass is a simple loop unrolling pass. // Pass *createLoopUnrollPass(int OptLevel = 2, int Threshold = -1, int Count = -1, Index: llvm/trunk/include/llvm/Transforms/Scalar/LoopInstSimplify.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Scalar/LoopInstSimplify.h +++ llvm/trunk/include/llvm/Transforms/Scalar/LoopInstSimplify.h @@ -0,0 +1,34 @@ +//===- LoopInstSimplify.h - Loop Inst Simplify Pass -------------*- C++ -*-===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H +#define LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H + +#include "llvm/Analysis/LoopAnalysisManager.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Loop; +class LPMUpdater; + +/// Performs Loop Inst Simplify Pass. +class LoopInstSimplifyPass : public PassInfoMixin { +public: + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H Index: llvm/trunk/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/trunk/lib/Passes/PassBuilder.cpp +++ llvm/trunk/lib/Passes/PassBuilder.cpp @@ -111,6 +111,7 @@ #include "llvm/Transforms/Scalar/LoopDeletion.h" #include "llvm/Transforms/Scalar/LoopDistribute.h" #include "llvm/Transforms/Scalar/LoopIdiomRecognize.h" +#include "llvm/Transforms/Scalar/LoopInstSimplify.h" #include "llvm/Transforms/Scalar/LoopLoadElimination.h" #include "llvm/Transforms/Scalar/LoopPassManager.h" #include "llvm/Transforms/Scalar/LoopPredication.h" @@ -391,8 +392,9 @@ // FIXME: Currently this is split into two loop pass pipelines because we run // some function passes in between them. These can and should be replaced by // loop pass equivalenst but those aren't ready yet. Specifically, - // `SimplifyCFGPass` and `InstCombinePass` are used. We just have - // `LoopSimplifyCFGPass` which isn't yet powerful enough. + // `SimplifyCFGPass` and `InstCombinePass` are used. We have + // `LoopSimplifyCFGPass` which isn't yet powerful enough, and the closest to + // the other we have is `LoopInstSimplify`. LoopPassManager LPM1(DebugLogging), LPM2(DebugLogging); // Rotate Loop - disable header duplication at -Oz Index: llvm/trunk/lib/Passes/PassRegistry.def =================================================================== --- llvm/trunk/lib/Passes/PassRegistry.def +++ llvm/trunk/lib/Passes/PassRegistry.def @@ -230,6 +230,7 @@ LOOP_PASS("invalidate", InvalidateAllAnalysesPass()) LOOP_PASS("licm", LICMPass()) LOOP_PASS("loop-idiom", LoopIdiomRecognizePass()) +LOOP_PASS("loop-instsimplify", LoopInstSimplifyPass()) LOOP_PASS("rotate", LoopRotatePass()) LOOP_PASS("no-op-loop", NoOpLoopPass()) LOOP_PASS("print", PrintLoopPass(dbgs())) Index: llvm/trunk/lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Transforms/Scalar/CMakeLists.txt +++ llvm/trunk/lib/Transforms/Scalar/CMakeLists.txt @@ -28,6 +28,7 @@ LoopDataPrefetch.cpp LoopDistribute.cpp LoopIdiomRecognize.cpp + LoopInstSimplify.cpp LoopInterchange.cpp LoopLoadElimination.cpp LoopPassManager.cpp Index: llvm/trunk/lib/Transforms/Scalar/LoopInstSimplify.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LoopInstSimplify.cpp +++ llvm/trunk/lib/Transforms/Scalar/LoopInstSimplify.cpp @@ -0,0 +1,223 @@ +//===- 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. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/LoopInstSimplify.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/Utils/Local.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" +#include "llvm/IR/User.h" +#include "llvm/Pass.h" +#include "llvm/Support/Casting.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/LoopUtils.h" +#include +#include + +using namespace llvm; + +#define DEBUG_TYPE "loop-instsimplify" + +STATISTIC(NumSimplified, "Number of redundant instructions simplified"); + +static bool SimplifyLoopInst(Loop *L, DominatorTree *DT, LoopInfo *LI, + AssumptionCache *AC, + const TargetLibraryInfo *TLI) { + SmallVector ExitBlocks; + L->getUniqueExitBlocks(ExitBlocks); + array_pod_sort(ExitBlocks.begin(), ExitBlocks.end()); + + SmallPtrSet S1, S2, *ToSimplify = &S1, *Next = &S2; + + // The bit we are stealing from the pointer represents whether this basic + // block is the header of a subloop, in which case we only process its phis. + using WorklistItem = PointerIntPair; + SmallVector VisitStack; + SmallPtrSet Visited; + + bool Changed = false; + bool LocalChanged; + do { + LocalChanged = false; + + VisitStack.clear(); + Visited.clear(); + + VisitStack.push_back(WorklistItem(L->getHeader(), false)); + + while (!VisitStack.empty()) { + WorklistItem Item = VisitStack.pop_back_val(); + BasicBlock *BB = Item.getPointer(); + bool IsSubloopHeader = Item.getInt(); + const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); + + // Simplify instructions in the current basic block. + for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { + Instruction *I = &*BI++; + + // The first time through the loop ToSimplify is empty and we try to + // simplify all instructions. On later iterations ToSimplify is not + // empty and we only bother simplifying instructions that are in it. + if (!ToSimplify->empty() && !ToSimplify->count(I)) + continue; + + // Don't bother simplifying unused instructions. + if (!I->use_empty()) { + Value *V = SimplifyInstruction(I, {DL, TLI, DT, AC}); + if (V && LI->replacementPreservesLCSSAForm(I, V)) { + // Mark all uses for resimplification next time round the loop. + for (User *U : I->users()) + Next->insert(cast(U)); + + I->replaceAllUsesWith(V); + LocalChanged = true; + ++NumSimplified; + } + } + if (RecursivelyDeleteTriviallyDeadInstructions(I, TLI)) { + // RecursivelyDeleteTriviallyDeadInstruction can remove more than one + // instruction, so simply incrementing the iterator does not work. + // When instructions get deleted re-iterate instead. + BI = BB->begin(); + BE = BB->end(); + LocalChanged = true; + } + + if (IsSubloopHeader && !isa(I)) + break; + } + + // Add all successors to the worklist, except for loop exit blocks and the + // bodies of subloops. We visit the headers of loops so that we can + // process + // their phis, but we contract the rest of the subloop body and only + // follow + // edges leading back to the original loop. + for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; + ++SI) { + BasicBlock *SuccBB = *SI; + if (!Visited.insert(SuccBB).second) + continue; + + const Loop *SuccLoop = LI->getLoopFor(SuccBB); + if (SuccLoop && SuccLoop->getHeader() == SuccBB && + L->contains(SuccLoop)) { + VisitStack.push_back(WorklistItem(SuccBB, true)); + + SmallVector SubLoopExitBlocks; + SuccLoop->getExitBlocks(SubLoopExitBlocks); + + for (unsigned i = 0; i < SubLoopExitBlocks.size(); ++i) { + BasicBlock *ExitBB = SubLoopExitBlocks[i]; + if (LI->getLoopFor(ExitBB) == L && Visited.insert(ExitBB).second) + VisitStack.push_back(WorklistItem(ExitBB, false)); + } + + continue; + } + + bool IsExitBlock = + std::binary_search(ExitBlocks.begin(), ExitBlocks.end(), SuccBB); + if (IsExitBlock) + continue; + + VisitStack.push_back(WorklistItem(SuccBB, false)); + } + } + + // Place the list of instructions to simplify on the next loop iteration + // into ToSimplify. + std::swap(ToSimplify, Next); + Next->clear(); + + Changed |= LocalChanged; + } while (LocalChanged); + + return Changed; +} + +namespace { + +class LoopInstSimplifyLegacyPass : public LoopPass { +public: + static char ID; // Pass ID, replacement for typeid + + LoopInstSimplifyLegacyPass() : LoopPass(ID) { + initializeLoopInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnLoop(Loop *L, LPPassManager &LPM) override { + if (skipLoop(L)) + return false; + DominatorTreeWrapperPass *DTWP = + getAnalysisIfAvailable(); + DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr; + LoopInfo *LI = &getAnalysis().getLoopInfo(); + AssumptionCache *AC = + &getAnalysis().getAssumptionCache( + *L->getHeader()->getParent()); + const TargetLibraryInfo *TLI = + &getAnalysis().getTLI(); + + return SimplifyLoopInst(L, DT, LI, AC, TLI); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + AU.setPreservesCFG(); + getLoopAnalysisUsage(AU); + } +}; + +} // end anonymous namespace + +PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LPMUpdater &) { + if (!SimplifyLoopInst(&L, &AR.DT, &AR.LI, &AR.AC, &AR.TLI)) + return PreservedAnalyses::all(); + + auto PA = getLoopPassPreservedAnalyses(); + PA.preserveSet(); + return PA; +} + +char LoopInstSimplifyLegacyPass::ID = 0; + +INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify", + "Simplify instructions in loops", false, false) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(LoopPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify", + "Simplify instructions in loops", false, false) + +Pass *llvm::createLoopInstSimplifyPass() { + return new LoopInstSimplifyLegacyPass(); +} Index: llvm/trunk/lib/Transforms/Scalar/Scalar.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/Scalar.cpp +++ llvm/trunk/lib/Transforms/Scalar/Scalar.cpp @@ -62,6 +62,7 @@ initializeLoopDataPrefetchLegacyPassPass(Registry); initializeLoopDeletionLegacyPassPass(Registry); initializeLoopAccessLegacyAnalysisPass(Registry); + initializeLoopInstSimplifyLegacyPassPass(Registry); initializeLoopInterchangePass(Registry); initializeLoopPredicationLegacyPassPass(Registry); initializeLoopRotateLegacyPassPass(Registry); Index: llvm/trunk/test/Feature/optnone-opt.ll =================================================================== --- llvm/trunk/test/Feature/optnone-opt.ll +++ llvm/trunk/test/Feature/optnone-opt.ll @@ -3,7 +3,7 @@ ; RUN: opt -O2 -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-O1 --check-prefix=OPT-O2O3 ; RUN: opt -O3 -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-O1 --check-prefix=OPT-O2O3 ; RUN: opt -dce -die -gvn-hoist -loweratomic -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-MORE -; RUN: opt -indvars -licm -loop-deletion -loop-extract -loop-idiom -loop-reduce -loop-reroll -loop-rotate -loop-unroll -loop-unswitch -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-LOOP +; RUN: opt -indvars -licm -loop-deletion -loop-extract -loop-idiom -loop-instsimplify -loop-reduce -loop-reroll -loop-rotate -loop-unroll -loop-unswitch -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-LOOP ; REQUIRES: asserts @@ -67,5 +67,6 @@ ; OPT-LOOP-DAG: Skipping pass 'Recognize loop idioms' ; OPT-LOOP-DAG: Skipping pass 'Reroll loops' ; OPT-LOOP-DAG: Skipping pass 'Rotate Loops' +; OPT-LOOP-DAG: Skipping pass 'Simplify instructions in loops' ; OPT-LOOP-DAG: Skipping pass 'Unroll loops' ; OPT-LOOP-DAG: Skipping pass 'Unswitch loops'