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