| 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-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // This pass canonicalizes freeze instructions in a loop by pushing them out to |
| 10 | // the preheader. |
| 11 | // |
| 12 | // loop: |
| 13 | // i = phi init, i.next |
| 14 | // i.next = add nsw i, 1 |
| 15 | // i.next.fr = freeze i.next // push this out of this loop |
| 16 | // use(i.next.fr) |
| 17 | // br i1 (i.next <= N), loop, exit |
| 18 | // => |
| 19 | // init.fr = freeze init |
| 20 | // loop: |
| 21 | // i = phi init.fr, i.next |
| 22 | // i.next = add i, 1 // nsw is dropped here |
| 23 | // use(i.next) |
| 24 | // br i1 (i.next <= N), loop, exit |
| 25 | // |
| 26 | // Removing freezes from these chains help scalar evolution successfully analyze |
| 27 | // 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 | |
| 47 | using namespace llvm; |
| 48 | |
| 49 | #define DEBUG_TYPE "canon-freeze" |
| 50 | |
| 51 | namespace { |
| 52 | |
| 53 | class CanonicalizeFreezeInLoops : public LoopPass { |
| 54 | public: |
| 55 | static char ID; |
| 56 | |
| 57 | CanonicalizeFreezeInLoops(); |
| 58 | |
| 59 | private: |
| 60 | bool runOnLoop(Loop *L, LPPassManager &LPM) override; |
| 61 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
| 62 | }; |
| 63 | |
| 64 | class 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 are |
| 71 | // 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 | |
| 81 | public: |
| 82 | CanonicalizeFreezeInLoopsImpl(Loop *L, ScalarEvolution &SE, DominatorTree &DT) |
| 83 | : L(L), SE(SE), DT(DT) {} |
| 84 | bool run(); |
| 85 | }; |
| 86 | |
| 87 | struct FrozenIndPHIInfo { |
| 88 | // A freeze instruction that uses an induction phi |
| 89 | FreezeInst *FI = nullptr; |
| 90 | // The induction phi, step instruction, the operand idx of StepInst which is |
| 91 | // a step value |
| 92 | 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 | } // namespace |
| 103 | |
| 104 | template <> 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(PtrVal: 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 let |
| 126 | // SCEV forget user. The inserted freeze is placed in the preheader. |
| 127 | void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) { |
| 128 | auto *PH = L->getLoopPreheader(); |
| 129 | |
| 130 | auto *UserI = cast<Instruction>(Val: 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(V: ValueToFr, AC: nullptr, CtxI: UserI, DT: &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(V: UserI); |
| 145 | } |
| 146 | |
| 147 | bool 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: &PHI, L, SE: &SE, D&: ID)) |
| 157 | continue; |
| 158 | |
| 159 | LLVM_DEBUG(dbgs() << "canonfr: PHI: " << PHI << "\n" ); |
| 160 | FrozenIndPHIInfo Info(&PHI, ID.getInductionBinOp()); |
| 161 | if (!Info.StepInst || !canHandleInst(I: Info.StepInst)) { |
| 162 | // The stepping instruction has unknown form. |
| 163 | // Ignore this PHI. |
| 164 | continue; |
| 165 | } |
| 166 | |
| 167 | Info.StepValIdx = Info.StepInst->getOperand(i_nocapture: 0) == &PHI; |
| 168 | Value *StepV = Info.StepInst->getOperand(i_nocapture: Info.StepValIdx); |
| 169 | if (auto *StepI = dyn_cast<Instruction>(Val: StepV)) { |
| 170 | if (L->contains(BB: StepI->getParent())) { |
| 171 | // The step value is inside the loop. Freezing step value will introduce |
| 172 | // 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>(Val: U)) { |
| 179 | LLVM_DEBUG(dbgs() << "canonfr: found: " << *FI << "\n" ); |
| 180 | Info.FI = FI; |
| 181 | Candidates.insert(X: Info); |
| 182 | } |
| 183 | }; |
| 184 | for_each(Range: PHI.users(), F: Visit); |
| 185 | for_each(Range: Info.StepInst->users(), F: 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(Ptr: 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(V: StepI, AC: nullptr, CtxI: StepI, DT: &DT)) { |
| 202 | LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *StepI << "\n" ); |
| 203 | StepI->dropPoisonGeneratingFlags(); |
| 204 | SE.forgetValue(V: StepI); |
| 205 | } |
| 206 | |
| 207 | InsertFreezeAndForgetFromSCEV(U&: StepI->getOperandUse(i: Info.StepValIdx)); |
| 208 | |
| 209 | unsigned OperandIdx = |
| 210 | PHI->getOperandNumForIncomingValue(i: PHI->getIncomingValue(i: 0) == StepI); |
| 211 | InsertFreezeAndForgetFromSCEV(U&: PHI->getOperandUse(i: 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(V: FI); |
| 219 | FI->replaceAllUsesWith(V: FI->getOperand(i_nocapture: 0)); |
| 220 | FI->eraseFromParent(); |
| 221 | } |
| 222 | |
| 223 | return true; |
| 224 | } |
| 225 | |
| 226 | CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) { |
| 227 | initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry()); |
| 228 | } |
| 229 | |
| 230 | void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const { |
| 231 | AU.addPreservedID(ID&: LoopSimplifyID); |
| 232 | AU.addRequired<LoopInfoWrapperPass>(); |
| 233 | AU.addPreserved<LoopInfoWrapperPass>(); |
| 234 | AU.addRequiredID(ID&: LoopSimplifyID); |
| 235 | AU.addRequired<ScalarEvolutionWrapperPass>(); |
| 236 | AU.addPreserved<ScalarEvolutionWrapperPass>(); |
| 237 | AU.addRequired<DominatorTreeWrapperPass>(); |
| 238 | AU.addPreserved<DominatorTreeWrapperPass>(); |
| 239 | } |
| 240 | |
| 241 | bool 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 | |
| 250 | PreservedAnalyses |
| 251 | CanonicalizeFreezeInLoopsPass::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 | |
| 260 | INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze" , |
| 261 | "Canonicalize Freeze Instructions in Loops" , false, false) |
| 262 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
| 263 | INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) |
| 264 | INITIALIZE_PASS_DEPENDENCY(LoopSimplify) |
| 265 | INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze" , |
| 266 | "Canonicalize Freeze Instructions in Loops" , false, false) |
| 267 | |
| 268 | Pass *llvm::createCanonicalizeFreezeInLoopsPass() { |
| 269 | return new CanonicalizeFreezeInLoops(); |
| 270 | } |
| 271 | |
| 272 | char CanonicalizeFreezeInLoops::ID = 0; |
| 273 | |