LLVM 18.0.0git
CanonicalizeFreezeInLoops.cpp
Go to the documentation of this file.
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
32#include "llvm/ADT/STLExtras.h"
33#include "llvm/ADT/SmallSet.h"
41#include "llvm/IR/Dominators.h"
43#include "llvm/Pass.h"
44#include "llvm/Support/Debug.h"
46
47using namespace llvm;
48
49#define DEBUG_TYPE "canon-freeze"
50
51namespace {
52
53class CanonicalizeFreezeInLoops : public LoopPass {
54public:
55 static char ID;
56
57 CanonicalizeFreezeInLoops();
58
59private:
60 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
61 void getAnalysisUsage(AnalysisUsage &AU) const override;
62};
63
64class CanonicalizeFreezeInLoopsImpl {
65 Loop *L;
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
94public:
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.
104void 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
124bool CanonicalizeFreezeInLoopsImpl::run() {
125 // The loop should be in LoopSimplify form.
126 if (!L->isLoopSimplifyForm())
127 return false;
128
130
131 for (auto &PHI : L->getHeader()->phis()) {
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");
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
203CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {
205}
206
207void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {
216}
217
218bool 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
230 LPMUpdater &U) {
231 if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run())
232 return PreservedAnalyses::all();
233
235}
236
237INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",
238 "Canonicalize Freeze Instructions in Loops", false, false)
241INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
242INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
243 "Canonicalize Freeze Instructions in Loops", false, false)
244
246 return new CanonicalizeFreezeInLoops();
247}
248
249char CanonicalizeFreezeInLoops::ID = 0;
Rewrite undef for PHI
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
#define LLVM_DEBUG(X)
Definition: Debug.h:101
Hexagon Hardware Loops
This header provides classes for managing per-loop analyses.
#define I(x, y, z)
Definition: MD5.cpp:58
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallSet class.
This file defines the SmallVector class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:649
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:283
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:310
DominatorTree & getDomTree()
Definition: Dominators.h:318
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
This class represents a freeze function that returns random concrete value if an operand is either a ...
A struct for saving information about induction variables.
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:591
virtual bool runOnLoop(Loop *L, LPPassManager &LPM)=0
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:172
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:178
The main scalar evolution driver.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
const Use & getOperandUse(unsigned i) const
Definition: User.h:182
LLVM Value Representation.
Definition: Value.h:74
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1719
char & LoopSimplifyID
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Pass * createCanonicalizeFreezeInLoopsPass()
void initializeCanonicalizeFreezeInLoopsPass(PassRegistry &)
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...