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 unsigned getHashValue(const FrozenIndPHIInfo &Val) {
106 return DenseMapInfo<FreezeInst *>::getHashValue(PtrVal: Val.FI);
107 };
108
109 static bool isEqual(const FrozenIndPHIInfo &LHS,
110 const FrozenIndPHIInfo &RHS) {
111 return LHS.FI == RHS.FI;
112 };
113};
114
115// Given U = (value, user), replace value with freeze(value), and let
116// SCEV forget user. The inserted freeze is placed in the preheader.
117void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) {
118 auto *PH = L->getLoopPreheader();
119
120 auto *UserI = cast<Instruction>(Val: U.getUser());
121 auto *ValueToFr = U.get();
122 assert(L->contains(UserI->getParent()) &&
123 "Should not process an instruction that isn't inside the loop");
124 if (isGuaranteedNotToBeUndefOrPoison(V: ValueToFr, AC: nullptr, CtxI: UserI, DT: &DT))
125 return;
126
127 LLVM_DEBUG(dbgs() << "canonfr: inserting freeze:\n");
128 LLVM_DEBUG(dbgs() << "\tUser: " << *U.getUser() << "\n");
129 LLVM_DEBUG(dbgs() << "\tOperand: " << *U.get() << "\n");
130
131 U.set(new FreezeInst(ValueToFr, ValueToFr->getName() + ".frozen",
132 PH->getTerminator()->getIterator()));
133
134 SE.forgetValue(V: UserI);
135}
136
137bool CanonicalizeFreezeInLoopsImpl::run() {
138 // The loop should be in LoopSimplify form.
139 if (!L->isLoopSimplifyForm())
140 return false;
141
142 SmallSetVector<FrozenIndPHIInfo, 4> Candidates;
143
144 for (auto &PHI : L->getHeader()->phis()) {
145 InductionDescriptor ID;
146 if (!InductionDescriptor::isInductionPHI(Phi: &PHI, L, SE: &SE, D&: ID))
147 continue;
148
149 LLVM_DEBUG(dbgs() << "canonfr: PHI: " << PHI << "\n");
150 FrozenIndPHIInfo Info(&PHI, ID.getInductionBinOp());
151 if (!Info.StepInst || !canHandleInst(I: Info.StepInst)) {
152 // The stepping instruction has unknown form.
153 // Ignore this PHI.
154 continue;
155 }
156
157 Info.StepValIdx = Info.StepInst->getOperand(i_nocapture: 0) == &PHI;
158 Value *StepV = Info.StepInst->getOperand(i_nocapture: Info.StepValIdx);
159 if (auto *StepI = dyn_cast<Instruction>(Val: StepV)) {
160 if (L->contains(BB: StepI->getParent())) {
161 // The step value is inside the loop. Freezing step value will introduce
162 // another freeze into the loop, so skip this PHI.
163 continue;
164 }
165 }
166
167 auto Visit = [&](User *U) {
168 if (auto *FI = dyn_cast<FreezeInst>(Val: U)) {
169 LLVM_DEBUG(dbgs() << "canonfr: found: " << *FI << "\n");
170 Info.FI = FI;
171 Candidates.insert(X: Info);
172 }
173 };
174 for_each(Range: PHI.users(), F: Visit);
175 for_each(Range: Info.StepInst->users(), F: Visit);
176 }
177
178 if (Candidates.empty())
179 return false;
180
181 SmallPtrSet<PHINode *, 8> ProcessedPHIs;
182 for (const auto &Info : Candidates) {
183 PHINode *PHI = Info.PHI;
184 if (!ProcessedPHIs.insert(Ptr: Info.PHI).second)
185 continue;
186
187 BinaryOperator *StepI = Info.StepInst;
188 assert(StepI && "Step instruction should have been found");
189
190 // Drop flags from the step instruction.
191 if (!isGuaranteedNotToBeUndefOrPoison(V: StepI, AC: nullptr, CtxI: StepI, DT: &DT)) {
192 LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *StepI << "\n");
193 StepI->dropPoisonGeneratingFlags();
194 SE.forgetValue(V: StepI);
195 }
196
197 InsertFreezeAndForgetFromSCEV(U&: StepI->getOperandUse(i: Info.StepValIdx));
198
199 unsigned OperandIdx =
200 PHI->getOperandNumForIncomingValue(i: PHI->getIncomingValue(i: 0) == StepI);
201 InsertFreezeAndForgetFromSCEV(U&: PHI->getOperandUse(i: OperandIdx));
202 }
203
204 // Finally, remove the old freeze instructions.
205 for (const auto &Item : Candidates) {
206 auto *FI = Item.FI;
207 LLVM_DEBUG(dbgs() << "canonfr: removing " << *FI << "\n");
208 SE.forgetValue(V: FI);
209 FI->replaceAllUsesWith(V: FI->getOperand(i_nocapture: 0));
210 FI->eraseFromParent();
211 }
212
213 return true;
214}
215
216CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {
217 initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry());
218}
219
220void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {
221 AU.addPreservedID(ID&: LoopSimplifyID);
222 AU.addRequired<LoopInfoWrapperPass>();
223 AU.addPreserved<LoopInfoWrapperPass>();
224 AU.addRequiredID(ID&: LoopSimplifyID);
225 AU.addRequired<ScalarEvolutionWrapperPass>();
226 AU.addPreserved<ScalarEvolutionWrapperPass>();
227 AU.addRequired<DominatorTreeWrapperPass>();
228 AU.addPreserved<DominatorTreeWrapperPass>();
229}
230
231bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) {
232 if (skipLoop(L))
233 return false;
234
235 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
236 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
237 return CanonicalizeFreezeInLoopsImpl(L, SE, DT).run();
238}
239
240PreservedAnalyses
241CanonicalizeFreezeInLoopsPass::run(Loop &L, LoopAnalysisManager &AM,
242 LoopStandardAnalysisResults &AR,
243 LPMUpdater &U) {
244 if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run())
245 return PreservedAnalyses::all();
246
247 return getLoopPassPreservedAnalyses();
248}
249
250INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",
251 "Canonicalize Freeze Instructions in Loops", false, false)
252INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
253INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
254INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
255INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
256 "Canonicalize Freeze Instructions in Loops", false, false)
257
258Pass *llvm::createCanonicalizeFreezeInLoopsPass() {
259 return new CanonicalizeFreezeInLoops();
260}
261
262char CanonicalizeFreezeInLoops::ID = 0;
263