LLVM  14.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/DenseMap.h"
33 #include "llvm/ADT/STLExtras.h"
34 #include "llvm/ADT/SmallVector.h"
37 #include "llvm/Analysis/LoopInfo.h"
38 #include "llvm/Analysis/LoopPass.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 
130 
131  for (auto &PHI : L->getHeader()->phis()) {
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 {
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 
228 CanonicalizeFreezeInLoopsPass::run(Loop &L, LoopAnalysisManager &AM,
230  LPMUpdater &U) {
231  if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run())
232  return PreservedAnalyses::all();
233 
235 }
236 
237 INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",
238  "Canonicalize Freeze Instructions in Loops", false, false)
241 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
242 INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
243  "Canonicalize Freeze Instructions in Loops", false, false)
244 
246  return new CanonicalizeFreezeInLoops();
247 }
248 
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Pass.h
llvm::isGuaranteedNotToBeUndefOrPoison
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.
Definition: ValueTracking.cpp:5280
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::PHINode::getOperandNumForIncomingValue
static unsigned getOperandNumForIncomingValue(unsigned i)
Definition: Instructions.h:2754
llvm::Use::get
Value * get() const
Definition: Use.h:67
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
ScalarEvolution.h
DenseMap.h
Instructions
Code Generation Notes for reduce the size of the ISel and reduce repetition in the implementation In a small number of this can cause even when no optimisation has taken place Instructions
Definition: MSA.txt:11
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1268
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
STLExtras.h
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
LoopAnalysisManager.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::User::getOperandUse
const Use & getOperandUse(unsigned i) const
Definition: User.h:182
llvm::InductionDescriptor
A struct for saving information about induction variables.
Definition: IVDescriptors.h:297
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2744
llvm::User
Definition: User.h:44
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
freeze
canon freeze
Definition: CanonicalizeFreezeInLoops.cpp:242
false
Definition: StackSlotColoring.cpp:142
in
The object format emitted by the WebAssembly backed is documented in
Definition: README.txt:11
llvm::Instruction
Definition: Instruction.h:45
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze", "Canonicalize Freeze Instructions in Loops", false, false) INITIALIZE_PASS_END(CanonicalizeFreezeInLoops
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2123
llvm::LPPassManager
Definition: LoopPass.h:75
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::initializeCanonicalizeFreezeInLoopsPass
void initializeCanonicalizeFreezeInLoopsPass(PassRegistry &)
Utils.h
IVDescriptors.h
CanonicalizeFreezeInLoops.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::createCanonicalizeFreezeInLoopsPass
Pass * createCanonicalizeFreezeInLoopsPass()
Definition: CanonicalizeFreezeInLoops.cpp:245
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:140
llvm::Use::set
void set(Value *Val)
Definition: Value.h:868
llvm::for_each
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:1593
llvm::LoopPass
Definition: LoopPass.h:27
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:263
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
I
#define I(x, y, z)
Definition: MD5.cpp:59
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Loops
canon Canonicalize Freeze Instructions in Loops
Definition: CanonicalizeFreezeInLoops.cpp:243
llvm::BinaryOperator
Definition: InstrTypes.h:190
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
LoopPass.h
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:180
llvm::InductionDescriptor::isInductionPHI
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.
Definition: IVDescriptors.cpp:1345
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:799
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::DominatorTreeWrapperPass::getDomTree
DominatorTree & getDomTree()
Definition: Dominators.h:295
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
SmallVector.h
Dominators.h
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5369
llvm::PHINode
Definition: Instructions.h:2648
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:267
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::Instruction::dropPoisonGeneratingFlags
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
Definition: Instruction.cpp:148
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38