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