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