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