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
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 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
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 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
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(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.
127void 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
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: &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
226CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {
227 initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry());
228}
229
230void 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
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
250PreservedAnalyses
251CanonicalizeFreezeInLoopsPass::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