273 lines · cpp
1//==- CanonicalizeFreezeInLoops - Canonicalize freezes in a loop-*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass canonicalizes freeze instructions in a loop by pushing them out to10// the preheader.11//12// loop:13// i = phi init, i.next14// i.next = add nsw i, 115// i.next.fr = freeze i.next // push this out of this loop16// use(i.next.fr)17// br i1 (i.next <= N), loop, exit18// =>19// init.fr = freeze init20// loop:21// i = phi init.fr, i.next22// i.next = add i, 1 // nsw is dropped here23// use(i.next)24// br i1 (i.next <= N), loop, exit25//26// Removing freezes from these chains help scalar evolution successfully analyze27// expressions.28//29//===----------------------------------------------------------------------===//30 31#include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h"32#include "llvm/ADT/DenseMapInfo.h"33#include "llvm/ADT/STLExtras.h"34#include "llvm/ADT/SetVector.h"35#include "llvm/Analysis/IVDescriptors.h"36#include "llvm/Analysis/LoopAnalysisManager.h"37#include "llvm/Analysis/LoopInfo.h"38#include "llvm/Analysis/LoopPass.h"39#include "llvm/Analysis/ScalarEvolution.h"40#include "llvm/Analysis/ValueTracking.h"41#include "llvm/IR/Dominators.h"42#include "llvm/InitializePasses.h"43#include "llvm/Pass.h"44#include "llvm/Support/Debug.h"45#include "llvm/Transforms/Utils.h"46 47using namespace llvm;48 49#define DEBUG_TYPE "canon-freeze"50 51namespace {52 53class CanonicalizeFreezeInLoops : public LoopPass {54public:55 static char ID;56 57 CanonicalizeFreezeInLoops();58 59private:60 bool runOnLoop(Loop *L, LPPassManager &LPM) override;61 void getAnalysisUsage(AnalysisUsage &AU) const override;62};63 64class CanonicalizeFreezeInLoopsImpl {65 Loop *L;66 ScalarEvolution &SE;67 DominatorTree &DT;68 69 // Can freeze instruction be pushed into operands of I?70 // In order to do this, I should not create a poison after I's flags are71 // stripped.72 bool canHandleInst(const Instruction *I) {73 auto Opc = I->getOpcode();74 // If add/sub/mul, drop nsw/nuw flags.75 return Opc == Instruction::Add || Opc == Instruction::Sub ||76 Opc == Instruction::Mul;77 }78 79 void InsertFreezeAndForgetFromSCEV(Use &U);80 81public:82 CanonicalizeFreezeInLoopsImpl(Loop *L, ScalarEvolution &SE, DominatorTree &DT)83 : L(L), SE(SE), DT(DT) {}84 bool run();85};86 87struct FrozenIndPHIInfo {88 // A freeze instruction that uses an induction phi89 FreezeInst *FI = nullptr;90 // The induction phi, step instruction, the operand idx of StepInst which is91 // a step value92 PHINode *PHI;93 BinaryOperator *StepInst;94 unsigned StepValIdx = 0;95 96 FrozenIndPHIInfo(PHINode *PHI, BinaryOperator *StepInst)97 : PHI(PHI), StepInst(StepInst) {}98 99 bool operator==(const FrozenIndPHIInfo &Other) { return FI == Other.FI; }100};101 102} // namespace103 104template <> struct llvm::DenseMapInfo<FrozenIndPHIInfo> {105 static inline FrozenIndPHIInfo getEmptyKey() {106 return FrozenIndPHIInfo(DenseMapInfo<PHINode *>::getEmptyKey(),107 DenseMapInfo<BinaryOperator *>::getEmptyKey());108 }109 110 static inline FrozenIndPHIInfo getTombstoneKey() {111 return FrozenIndPHIInfo(DenseMapInfo<PHINode *>::getTombstoneKey(),112 DenseMapInfo<BinaryOperator *>::getTombstoneKey());113 }114 115 static unsigned getHashValue(const FrozenIndPHIInfo &Val) {116 return DenseMapInfo<FreezeInst *>::getHashValue(Val.FI);117 };118 119 static bool isEqual(const FrozenIndPHIInfo &LHS,120 const FrozenIndPHIInfo &RHS) {121 return LHS.FI == RHS.FI;122 };123};124 125// Given U = (value, user), replace value with freeze(value), and let126// SCEV forget user. The inserted freeze is placed in the preheader.127void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) {128 auto *PH = L->getLoopPreheader();129 130 auto *UserI = cast<Instruction>(U.getUser());131 auto *ValueToFr = U.get();132 assert(L->contains(UserI->getParent()) &&133 "Should not process an instruction that isn't inside the loop");134 if (isGuaranteedNotToBeUndefOrPoison(ValueToFr, nullptr, UserI, &DT))135 return;136 137 LLVM_DEBUG(dbgs() << "canonfr: inserting freeze:\n");138 LLVM_DEBUG(dbgs() << "\tUser: " << *U.getUser() << "\n");139 LLVM_DEBUG(dbgs() << "\tOperand: " << *U.get() << "\n");140 141 U.set(new FreezeInst(ValueToFr, ValueToFr->getName() + ".frozen",142 PH->getTerminator()->getIterator()));143 144 SE.forgetValue(UserI);145}146 147bool CanonicalizeFreezeInLoopsImpl::run() {148 // The loop should be in LoopSimplify form.149 if (!L->isLoopSimplifyForm())150 return false;151 152 SmallSetVector<FrozenIndPHIInfo, 4> Candidates;153 154 for (auto &PHI : L->getHeader()->phis()) {155 InductionDescriptor ID;156 if (!InductionDescriptor::isInductionPHI(&PHI, L, &SE, ID))157 continue;158 159 LLVM_DEBUG(dbgs() << "canonfr: PHI: " << PHI << "\n");160 FrozenIndPHIInfo Info(&PHI, ID.getInductionBinOp());161 if (!Info.StepInst || !canHandleInst(Info.StepInst)) {162 // The stepping instruction has unknown form.163 // Ignore this PHI.164 continue;165 }166 167 Info.StepValIdx = Info.StepInst->getOperand(0) == &PHI;168 Value *StepV = Info.StepInst->getOperand(Info.StepValIdx);169 if (auto *StepI = dyn_cast<Instruction>(StepV)) {170 if (L->contains(StepI->getParent())) {171 // The step value is inside the loop. Freezing step value will introduce172 // another freeze into the loop, so skip this PHI.173 continue;174 }175 }176 177 auto Visit = [&](User *U) {178 if (auto *FI = dyn_cast<FreezeInst>(U)) {179 LLVM_DEBUG(dbgs() << "canonfr: found: " << *FI << "\n");180 Info.FI = FI;181 Candidates.insert(Info);182 }183 };184 for_each(PHI.users(), Visit);185 for_each(Info.StepInst->users(), Visit);186 }187 188 if (Candidates.empty())189 return false;190 191 SmallPtrSet<PHINode *, 8> ProcessedPHIs;192 for (const auto &Info : Candidates) {193 PHINode *PHI = Info.PHI;194 if (!ProcessedPHIs.insert(Info.PHI).second)195 continue;196 197 BinaryOperator *StepI = Info.StepInst;198 assert(StepI && "Step instruction should have been found");199 200 // Drop flags from the step instruction.201 if (!isGuaranteedNotToBeUndefOrPoison(StepI, nullptr, StepI, &DT)) {202 LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *StepI << "\n");203 StepI->dropPoisonGeneratingFlags();204 SE.forgetValue(StepI);205 }206 207 InsertFreezeAndForgetFromSCEV(StepI->getOperandUse(Info.StepValIdx));208 209 unsigned OperandIdx =210 PHI->getOperandNumForIncomingValue(PHI->getIncomingValue(0) == StepI);211 InsertFreezeAndForgetFromSCEV(PHI->getOperandUse(OperandIdx));212 }213 214 // Finally, remove the old freeze instructions.215 for (const auto &Item : Candidates) {216 auto *FI = Item.FI;217 LLVM_DEBUG(dbgs() << "canonfr: removing " << *FI << "\n");218 SE.forgetValue(FI);219 FI->replaceAllUsesWith(FI->getOperand(0));220 FI->eraseFromParent();221 }222 223 return true;224}225 226CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {227 initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry());228}229 230void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {231 AU.addPreservedID(LoopSimplifyID);232 AU.addRequired<LoopInfoWrapperPass>();233 AU.addPreserved<LoopInfoWrapperPass>();234 AU.addRequiredID(LoopSimplifyID);235 AU.addRequired<ScalarEvolutionWrapperPass>();236 AU.addPreserved<ScalarEvolutionWrapperPass>();237 AU.addRequired<DominatorTreeWrapperPass>();238 AU.addPreserved<DominatorTreeWrapperPass>();239}240 241bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) {242 if (skipLoop(L))243 return false;244 245 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();246 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();247 return CanonicalizeFreezeInLoopsImpl(L, SE, DT).run();248}249 250PreservedAnalyses251CanonicalizeFreezeInLoopsPass::run(Loop &L, LoopAnalysisManager &AM,252 LoopStandardAnalysisResults &AR,253 LPMUpdater &U) {254 if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run())255 return PreservedAnalyses::all();256 257 return getLoopPassPreservedAnalyses();258}259 260INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",261 "Canonicalize Freeze Instructions in Loops", false, false)262INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)263INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)264INITIALIZE_PASS_DEPENDENCY(LoopSimplify)265INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",266 "Canonicalize Freeze Instructions in Loops", false, false)267 268Pass *llvm::createCanonicalizeFreezeInLoopsPass() {269 return new CanonicalizeFreezeInLoops();270}271 272char CanonicalizeFreezeInLoops::ID = 0;273