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
48 using namespace llvm;
49
50 #define DEBUG_TYPE "canon-freeze"
51
52 namespace {
53
54 class CanonicalizeFreezeInLoops : public LoopPass {
55 public:
56 static char ID;
57
58 CanonicalizeFreezeInLoops();
59
60 private:
61 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
62 void getAnalysisUsage(AnalysisUsage &AU) const override;
63 };
64
65 class 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.
canHandleInst(const Instruction * I)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
82 public:
CanonicalizeFreezeInLoopsImpl(Loop * L,ScalarEvolution & SE,DominatorTree & DT)83 CanonicalizeFreezeInLoopsImpl(Loop *L, ScalarEvolution &SE, DominatorTree &DT)
84 : L(L), SE(SE), DT(DT) {}
85 bool run();
86 };
87
88 } // anonymous namespace
89
90 namespace llvm {
91
92 struct 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
FrozenIndPHIInfollvm::FrozenIndPHIInfo101 FrozenIndPHIInfo(PHINode *PHI, BinaryOperator *StepInst)
102 : PHI(PHI), StepInst(StepInst) {}
103
operator ==llvm::FrozenIndPHIInfo104 bool operator==(const FrozenIndPHIInfo &Other) { return FI == Other.FI; }
105 };
106
107 template <> struct DenseMapInfo<FrozenIndPHIInfo> {
getEmptyKeyllvm::DenseMapInfo108 static inline FrozenIndPHIInfo getEmptyKey() {
109 return FrozenIndPHIInfo(DenseMapInfo<PHINode *>::getEmptyKey(),
110 DenseMapInfo<BinaryOperator *>::getEmptyKey());
111 }
112
getTombstoneKeyllvm::DenseMapInfo113 static inline FrozenIndPHIInfo getTombstoneKey() {
114 return FrozenIndPHIInfo(DenseMapInfo<PHINode *>::getTombstoneKey(),
115 DenseMapInfo<BinaryOperator *>::getTombstoneKey());
116 }
117
getHashValuellvm::DenseMapInfo118 static unsigned getHashValue(const FrozenIndPHIInfo &Val) {
119 return DenseMapInfo<FreezeInst *>::getHashValue(Val.FI);
120 };
121
isEqualllvm::DenseMapInfo122 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.
InsertFreezeAndForgetFromSCEV(Use & U)132 void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) {
133 auto *PH = L->getLoopPreheader();
134
135 auto *UserI = cast<Instruction>(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(ValueToFr, nullptr, UserI, &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()));
148
149 SE.forgetValue(UserI);
150 }
151
run()152 bool 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, L, &SE, ID))
162 continue;
163
164 LLVM_DEBUG(dbgs() << "canonfr: PHI: " << PHI << "\n");
165 FrozenIndPHIInfo Info(&PHI, ID.getInductionBinOp());
166 if (!Info.StepInst || !canHandleInst(Info.StepInst)) {
167 // The stepping instruction has unknown form.
168 // Ignore this PHI.
169 continue;
170 }
171
172 Info.StepValIdx = Info.StepInst->getOperand(0) == &PHI;
173 Value *StepV = Info.StepInst->getOperand(Info.StepValIdx);
174 if (auto *StepI = dyn_cast<Instruction>(StepV)) {
175 if (L->contains(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>(U)) {
184 LLVM_DEBUG(dbgs() << "canonfr: found: " << *FI << "\n");
185 Info.FI = FI;
186 Candidates.insert(Info);
187 }
188 };
189 for_each(PHI.users(), Visit);
190 for_each(Info.StepInst->users(), 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(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(StepI, nullptr, StepI, &DT)) {
207 LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *StepI << "\n");
208 StepI->dropPoisonGeneratingFlags();
209 SE.forgetValue(StepI);
210 }
211
212 InsertFreezeAndForgetFromSCEV(StepI->getOperandUse(Info.StepValIdx));
213
214 unsigned OperandIdx =
215 PHI->getOperandNumForIncomingValue(PHI->getIncomingValue(0) == StepI);
216 InsertFreezeAndForgetFromSCEV(PHI->getOperandUse(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(FI);
224 FI->replaceAllUsesWith(FI->getOperand(0));
225 FI->eraseFromParent();
226 }
227
228 return true;
229 }
230
CanonicalizeFreezeInLoops()231 CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {
232 initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry());
233 }
234
getAnalysisUsage(AnalysisUsage & AU) const235 void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {
236 AU.addPreservedID(LoopSimplifyID);
237 AU.addRequired<LoopInfoWrapperPass>();
238 AU.addPreserved<LoopInfoWrapperPass>();
239 AU.addRequiredID(LoopSimplifyID);
240 AU.addRequired<ScalarEvolutionWrapperPass>();
241 AU.addPreserved<ScalarEvolutionWrapperPass>();
242 AU.addRequired<DominatorTreeWrapperPass>();
243 AU.addPreserved<DominatorTreeWrapperPass>();
244 }
245
runOnLoop(Loop * L,LPPassManager &)246 bool 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
255 PreservedAnalyses
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater & U)256 CanonicalizeFreezeInLoopsPass::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
265 INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",
266 "Canonicalize Freeze Instructions in Loops", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)267 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
268 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
269 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
270 INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
271 "Canonicalize Freeze Instructions in Loops", false, false)
272
273 Pass *llvm::createCanonicalizeFreezeInLoopsPass() {
274 return new CanonicalizeFreezeInLoops();
275 }
276
277 char CanonicalizeFreezeInLoops::ID = 0;
278