diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2020-07-26 19:36:28 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2020-07-26 19:36:28 +0000 |
commit | cfca06d7963fa0909f90483b42a6d7d194d01e08 (patch) | |
tree | 209fb2a2d68f8f277793fc8df46c753d31bc853b /llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp | |
parent | 706b4fc47bbc608932d3b491ae19a3b9cde9497b (diff) |
Notes
Diffstat (limited to 'llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp')
-rw-r--r-- | llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp | 250 |
1 files changed, 250 insertions, 0 deletions
diff --git a/llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp b/llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp new file mode 100644 index 000000000000..1ae17c64b8f6 --- /dev/null +++ b/llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp @@ -0,0 +1,250 @@ +//==- CanonicalizeFreezeInLoops - Canonicalize freezes in a loop-*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This pass canonicalizes freeze instructions in a loop by pushing them out to +// the preheader. +// +// loop: +// i = phi init, i.next +// i.next = add nsw i, 1 +// i.next.fr = freeze i.next // push this out of this loop +// use(i.next.fr) +// br i1 (i.next <= N), loop, exit +// => +// init.fr = freeze init +// loop: +// i = phi init.fr, i.next +// i.next = add i, 1 // nsw is dropped here +// use(i.next) +// br i1 (i.next <= N), loop, exit +// +// Removing freezes from these chains help scalar evolution successfully analyze +// expressions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/IVDescriptors.h" +#include "llvm/Analysis/IVUsers.h" +#include "llvm/Analysis/LoopAnalysisManager.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/Dominators.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Transforms/Utils.h" + +using namespace llvm; + +#define DEBUG_TYPE "canon-freeze" + +namespace { + +class CanonicalizeFreezeInLoops : public LoopPass { +public: + static char ID; + + CanonicalizeFreezeInLoops(); + +private: + bool runOnLoop(Loop *L, LPPassManager &LPM) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +class CanonicalizeFreezeInLoopsImpl { + Loop *L; + ScalarEvolution &SE; + DominatorTree &DT; + + struct FrozenIndPHIInfo { + // A freeze instruction that uses an induction phi + FreezeInst *FI = nullptr; + // The induction phi, step instruction, the operand idx of StepInst which is + // a step value + PHINode *PHI; + BinaryOperator *StepInst; + unsigned StepValIdx = 0; + + FrozenIndPHIInfo(PHINode *PHI, BinaryOperator *StepInst) + : PHI(PHI), StepInst(StepInst) {} + }; + + // Can freeze instruction be pushed into operands of I? + // In order to do this, I should not create a poison after I's flags are + // stripped. + bool canHandleInst(const Instruction *I) { + auto Opc = I->getOpcode(); + // If add/sub/mul, drop nsw/nuw flags. + return Opc == Instruction::Add || Opc == Instruction::Sub || + Opc == Instruction::Mul; + } + + void InsertFreezeAndForgetFromSCEV(Use &U); + +public: + CanonicalizeFreezeInLoopsImpl(Loop *L, ScalarEvolution &SE, DominatorTree &DT) + : L(L), SE(SE), DT(DT) {} + bool run(); +}; + +} // anonymous namespace + +// Given U = (value, user), replace value with freeze(value), and let +// SCEV forget user. The inserted freeze is placed in the preheader. +void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) { + auto *PH = L->getLoopPreheader(); + + auto *UserI = cast<Instruction>(U.getUser()); + auto *ValueToFr = U.get(); + assert(L->contains(UserI->getParent()) && + "Should not process an instruction that isn't inside the loop"); + if (isGuaranteedNotToBeUndefOrPoison(ValueToFr, UserI, &DT)) + return; + + LLVM_DEBUG(dbgs() << "canonfr: inserting freeze:\n"); + LLVM_DEBUG(dbgs() << "\tUser: " << *U.getUser() << "\n"); + LLVM_DEBUG(dbgs() << "\tOperand: " << *U.get() << "\n"); + + U.set(new FreezeInst(ValueToFr, ValueToFr->getName() + ".frozen", + PH->getTerminator())); + + SE.forgetValue(UserI); +} + +bool CanonicalizeFreezeInLoopsImpl::run() { + // The loop should be in LoopSimplify form. + if (!L->isLoopSimplifyForm()) + return false; + + SmallVector<FrozenIndPHIInfo, 4> Candidates; + + for (auto &PHI : L->getHeader()->phis()) { + InductionDescriptor ID; + if (!InductionDescriptor::isInductionPHI(&PHI, L, &SE, ID)) + continue; + + LLVM_DEBUG(dbgs() << "canonfr: PHI: " << PHI << "\n"); + FrozenIndPHIInfo Info(&PHI, ID.getInductionBinOp()); + if (!Info.StepInst || !canHandleInst(Info.StepInst)) { + // The stepping instruction has unknown form. + // Ignore this PHI. + continue; + } + + Info.StepValIdx = Info.StepInst->getOperand(0) == &PHI; + Value *StepV = Info.StepInst->getOperand(Info.StepValIdx); + if (auto *StepI = dyn_cast<Instruction>(StepV)) { + if (L->contains(StepI->getParent())) { + // The step value is inside the loop. Freezing step value will introduce + // another freeze into the loop, so skip this PHI. + continue; + } + } + + auto Visit = [&](User *U) { + if (auto *FI = dyn_cast<FreezeInst>(U)) { + LLVM_DEBUG(dbgs() << "canonfr: found: " << *FI << "\n"); + Info.FI = FI; + Candidates.push_back(Info); + } + }; + for_each(PHI.users(), Visit); + for_each(Info.StepInst->users(), Visit); + } + + if (Candidates.empty()) + return false; + + SmallSet<PHINode *, 8> ProcessedPHIs; + for (const auto &Info : Candidates) { + PHINode *PHI = Info.PHI; + if (!ProcessedPHIs.insert(Info.PHI).second) + continue; + + BinaryOperator *StepI = Info.StepInst; + assert(StepI && "Step instruction should have been found"); + + // Drop flags from the step instruction. + if (!isGuaranteedNotToBeUndefOrPoison(StepI, StepI, &DT)) { + LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *StepI << "\n"); + StepI->dropPoisonGeneratingFlags(); + SE.forgetValue(StepI); + } + + InsertFreezeAndForgetFromSCEV(StepI->getOperandUse(Info.StepValIdx)); + + unsigned OperandIdx = + PHI->getOperandNumForIncomingValue(PHI->getIncomingValue(0) == StepI); + InsertFreezeAndForgetFromSCEV(PHI->getOperandUse(OperandIdx)); + } + + // Finally, remove the old freeze instructions. + for (const auto &Item : Candidates) { + auto *FI = Item.FI; + LLVM_DEBUG(dbgs() << "canonfr: removing " << *FI << "\n"); + SE.forgetValue(FI); + FI->replaceAllUsesWith(FI->getOperand(0)); + FI->eraseFromParent(); + } + + return true; +} + +CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) { + initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry()); +} + +void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addPreservedID(LoopSimplifyID); + AU.addRequired<LoopInfoWrapperPass>(); + AU.addPreserved<LoopInfoWrapperPass>(); + AU.addRequiredID(LoopSimplifyID); + AU.addRequired<ScalarEvolutionWrapperPass>(); + AU.addPreserved<ScalarEvolutionWrapperPass>(); + AU.addRequired<DominatorTreeWrapperPass>(); + AU.addPreserved<DominatorTreeWrapperPass>(); +} + +bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) { + if (skipLoop(L)) + return false; + + auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); + auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); + return CanonicalizeFreezeInLoopsImpl(L, SE, DT).run(); +} + +PreservedAnalyses +CanonicalizeFreezeInLoopsPass::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LPMUpdater &U) { + if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run()) + return PreservedAnalyses::all(); + + return getLoopPassPreservedAnalyses(); +} + +INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze", + "Canonicalize Freeze Instructions in Loops", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopSimplify) +INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze", + "Canonicalize Freeze Instructions in Loops", false, false) + +Pass *llvm::createCanonicalizeFreezeInLoopsPass() { + return new CanonicalizeFreezeInLoops(); +} + +char CanonicalizeFreezeInLoops::ID = 0; |