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