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