LLVM  15.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/SmallVector.h"
36 #include "llvm/Analysis/LoopInfo.h"
37 #include "llvm/Analysis/LoopPass.h"
40 #include "llvm/IR/Dominators.h"
41 #include "llvm/InitializePasses.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/Debug.h"
44 #include "llvm/Transforms/Utils.h"
45 
46 using namespace llvm;
47 
48 #define DEBUG_TYPE "canon-freeze"
49 
50 namespace {
51 
52 class CanonicalizeFreezeInLoops : public LoopPass {
53 public:
54  static char ID;
55 
56  CanonicalizeFreezeInLoops();
57 
58 private:
59  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
60  void getAnalysisUsage(AnalysisUsage &AU) const override;
61 };
62 
63 class CanonicalizeFreezeInLoopsImpl {
64  Loop *L;
65  ScalarEvolution &SE;
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 
93 public:
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.
103 void 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 
124  // The loop should be in LoopSimplify form.
125  if (!L->isLoopSimplifyForm())
126  return false;
127 
129 
130  for (auto &PHI : L->getHeader()->phis()) {
132  if (!InductionDescriptor::isInductionPHI(&PHI, L, &SE, ID))
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");
179  StepI->dropPoisonGeneratingFlags();
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 
202 CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {
203  initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry());
204 }
205 
206 void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {
215 }
216 
217 bool 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 
236 INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",
237  "Canonicalize Freeze Instructions in Loops", false, false)
240 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
241 INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
242  "Canonicalize Freeze Instructions in Loops", false, false)
243 
245  return new CanonicalizeFreezeInLoops();
246 }
247 
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
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:5404
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::PHINode::getOperandNumForIncomingValue
static unsigned getOperandNumForIncomingValue(unsigned i)
Definition: Instructions.h:2757
llvm::Use::get
Value * get() const
Definition: Use.h:66
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
ScalarEvolution.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:1287
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
STLExtras.h
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:54
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:306
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2747
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:241
false
Definition: StackSlotColoring.cpp:141
in
The object format emitted by the WebAssembly backed is documented in
Definition: README.txt:11
llvm::Instruction
Definition: Instruction.h:42
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:302
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2145
llvm::LPPassManager
Definition: LoopPass.h:76
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::initializeCanonicalizeFreezeInLoopsPass
void initializeCanonicalizeFreezeInLoopsPass(PassRegistry &)
Utils.h
IVDescriptors.h
CanonicalizeFreezeInLoops.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:101
LoopInfo.h
llvm::createCanonicalizeFreezeInLoopsPass
Pass * createCanonicalizeFreezeInLoopsPass()
Definition: CanonicalizeFreezeInLoops.cpp:244
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:137
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:1610
llvm::LoopPass
Definition: LoopPass.h:28
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
I
#define I(x, y, z)
Definition: MD5.cpp:58
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Loops
canon Canonicalize Freeze Instructions in Loops
Definition: CanonicalizeFreezeInLoops.cpp:242
llvm::BinaryOperator
Definition: InstrTypes.h:188
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
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:182
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:1504
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:794
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::DominatorTreeWrapperPass::getDomTree
DominatorTree & getDomTree()
Definition: Dominators.h:310
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:56
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:5394
llvm::PHINode
Definition: Instructions.h:2651
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:277
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:147
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38