LLVM 19.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
33#include "llvm/ADT/STLExtras.h"
34#include "llvm/ADT/SetVector.h"
35#include "llvm/ADT/SmallSet.h"
42#include "llvm/IR/Dominators.h"
44#include "llvm/Pass.h"
45#include "llvm/Support/Debug.h"
47
48using namespace llvm;
49
50#define DEBUG_TYPE "canon-freeze"
51
52namespace {
53
54class CanonicalizeFreezeInLoops : public LoopPass {
55public:
56 static char ID;
57
58 CanonicalizeFreezeInLoops();
59
60private:
61 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
62 void getAnalysisUsage(AnalysisUsage &AU) const override;
63};
64
65class CanonicalizeFreezeInLoopsImpl {
66 Loop *L;
68 DominatorTree &DT;
69
70 // Can freeze instruction be pushed into operands of I?
71 // In order to do this, I should not create a poison after I's flags are
72 // stripped.
73 bool canHandleInst(const Instruction *I) {
74 auto Opc = I->getOpcode();
75 // If add/sub/mul, drop nsw/nuw flags.
76 return Opc == Instruction::Add || Opc == Instruction::Sub ||
77 Opc == Instruction::Mul;
78 }
79
80 void InsertFreezeAndForgetFromSCEV(Use &U);
81
82public:
83 CanonicalizeFreezeInLoopsImpl(Loop *L, ScalarEvolution &SE, DominatorTree &DT)
84 : L(L), SE(SE), DT(DT) {}
85 bool run();
86};
87
88} // anonymous namespace
89
90namespace llvm {
91
93 // A freeze instruction that uses an induction phi
94 FreezeInst *FI = nullptr;
95 // The induction phi, step instruction, the operand idx of StepInst which is
96 // a step value
99 unsigned StepValIdx = 0;
100
102 : PHI(PHI), StepInst(StepInst) {}
103
104 bool operator==(const FrozenIndPHIInfo &Other) { return FI == Other.FI; }
105};
106
107template <> struct DenseMapInfo<FrozenIndPHIInfo> {
111 }
112
116 }
117
118 static unsigned getHashValue(const FrozenIndPHIInfo &Val) {
120 };
121
122 static bool isEqual(const FrozenIndPHIInfo &LHS,
123 const FrozenIndPHIInfo &RHS) {
124 return LHS.FI == RHS.FI;
125 };
126};
127
128} // end namespace llvm
129
130// Given U = (value, user), replace value with freeze(value), and let
131// SCEV forget user. The inserted freeze is placed in the preheader.
132void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) {
133 auto *PH = L->getLoopPreheader();
134
135 auto *UserI = cast<Instruction>(U.getUser());
136 auto *ValueToFr = U.get();
137 assert(L->contains(UserI->getParent()) &&
138 "Should not process an instruction that isn't inside the loop");
139 if (isGuaranteedNotToBeUndefOrPoison(ValueToFr, nullptr, UserI, &DT))
140 return;
141
142 LLVM_DEBUG(dbgs() << "canonfr: inserting freeze:\n");
143 LLVM_DEBUG(dbgs() << "\tUser: " << *U.getUser() << "\n");
144 LLVM_DEBUG(dbgs() << "\tOperand: " << *U.get() << "\n");
145
146 U.set(new FreezeInst(ValueToFr, ValueToFr->getName() + ".frozen",
147 PH->getTerminator()));
148
149 SE.forgetValue(UserI);
150}
151
152bool CanonicalizeFreezeInLoopsImpl::run() {
153 // The loop should be in LoopSimplify form.
154 if (!L->isLoopSimplifyForm())
155 return false;
156
158
159 for (auto &PHI : L->getHeader()->phis()) {
162 continue;
163
164 LLVM_DEBUG(dbgs() << "canonfr: PHI: " << PHI << "\n");
165 FrozenIndPHIInfo Info(&PHI, ID.getInductionBinOp());
166 if (!Info.StepInst || !canHandleInst(Info.StepInst)) {
167 // The stepping instruction has unknown form.
168 // Ignore this PHI.
169 continue;
170 }
171
172 Info.StepValIdx = Info.StepInst->getOperand(0) == &PHI;
173 Value *StepV = Info.StepInst->getOperand(Info.StepValIdx);
174 if (auto *StepI = dyn_cast<Instruction>(StepV)) {
175 if (L->contains(StepI->getParent())) {
176 // The step value is inside the loop. Freezing step value will introduce
177 // another freeze into the loop, so skip this PHI.
178 continue;
179 }
180 }
181
182 auto Visit = [&](User *U) {
183 if (auto *FI = dyn_cast<FreezeInst>(U)) {
184 LLVM_DEBUG(dbgs() << "canonfr: found: " << *FI << "\n");
185 Info.FI = FI;
186 Candidates.insert(Info);
187 }
188 };
189 for_each(PHI.users(), Visit);
190 for_each(Info.StepInst->users(), Visit);
191 }
192
193 if (Candidates.empty())
194 return false;
195
196 SmallSet<PHINode *, 8> ProcessedPHIs;
197 for (const auto &Info : Candidates) {
198 PHINode *PHI = Info.PHI;
199 if (!ProcessedPHIs.insert(Info.PHI).second)
200 continue;
201
202 BinaryOperator *StepI = Info.StepInst;
203 assert(StepI && "Step instruction should have been found");
204
205 // Drop flags from the step instruction.
206 if (!isGuaranteedNotToBeUndefOrPoison(StepI, nullptr, StepI, &DT)) {
207 LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *StepI << "\n");
209 SE.forgetValue(StepI);
210 }
211
212 InsertFreezeAndForgetFromSCEV(StepI->getOperandUse(Info.StepValIdx));
213
214 unsigned OperandIdx =
215 PHI->getOperandNumForIncomingValue(PHI->getIncomingValue(0) == StepI);
216 InsertFreezeAndForgetFromSCEV(PHI->getOperandUse(OperandIdx));
217 }
218
219 // Finally, remove the old freeze instructions.
220 for (const auto &Item : Candidates) {
221 auto *FI = Item.FI;
222 LLVM_DEBUG(dbgs() << "canonfr: removing " << *FI << "\n");
223 SE.forgetValue(FI);
224 FI->replaceAllUsesWith(FI->getOperand(0));
225 FI->eraseFromParent();
226 }
227
228 return true;
229}
230
231CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {
233}
234
235void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {
244}
245
246bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) {
247 if (skipLoop(L))
248 return false;
249
250 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
251 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
252 return CanonicalizeFreezeInLoopsImpl(L, SE, DT).run();
253}
254
258 LPMUpdater &U) {
259 if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run())
260 return PreservedAnalyses::all();
261
263}
264
265INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",
266 "Canonicalize Freeze Instructions in Loops", false, false)
269INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
270INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
271 "Canonicalize Freeze Instructions in Loops", false, false)
272
274 return new CanonicalizeFreezeInLoops();
275}
276
277char CanonicalizeFreezeInLoops::ID = 0;
Rewrite undef for PHI
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines DenseMapInfo traits for DenseMap.
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 implements a set that has insertion order iteration characteristics.
This file defines the SmallSet class.
Value * RHS
Value * LHS
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
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:313
DominatorTree & getDomTree()
Definition: Dominators.h:321
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:593
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: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
The main scalar evolution driver.
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
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
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:1724
char & LoopSimplifyID
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
@ Other
Any other memory.
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 &)
static unsigned getHashValue(const FrozenIndPHIInfo &Val)
static bool isEqual(const FrozenIndPHIInfo &LHS, const FrozenIndPHIInfo &RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:50
FrozenIndPHIInfo(PHINode *PHI, BinaryOperator *StepInst)
bool operator==(const FrozenIndPHIInfo &Other)
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...