LLVM  13.0.0git
SSAUpdater.cpp
Go to the documentation of this file.
1 //===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===//
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 file implements the SSAUpdater class.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/DenseMap.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/TinyPtrVector.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/CFG.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/DebugLoc.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/IR/Use.h"
27 #include "llvm/IR/Value.h"
28 #include "llvm/IR/ValueHandle.h"
29 #include "llvm/Support/Casting.h"
30 #include "llvm/Support/Debug.h"
33 #include <cassert>
34 #include <utility>
35 
36 using namespace llvm;
37 
38 #define DEBUG_TYPE "ssaupdater"
39 
41 
42 static AvailableValsTy &getAvailableVals(void *AV) {
43  return *static_cast<AvailableValsTy*>(AV);
44 }
45 
47  : InsertedPHIs(NewPHI) {}
48 
50  delete static_cast<AvailableValsTy*>(AV);
51 }
52 
54  if (!AV)
55  AV = new AvailableValsTy();
56  else
57  getAvailableVals(AV).clear();
58  ProtoType = Ty;
59  ProtoName = std::string(Name);
60 }
61 
63  return getAvailableVals(AV).count(BB);
64 }
65 
67  return getAvailableVals(AV).lookup(BB);
68 }
69 
71  assert(ProtoType && "Need to initialize SSAUpdater");
72  assert(ProtoType == V->getType() &&
73  "All rewritten values must have the same type");
74  getAvailableVals(AV)[BB] = V;
75 }
76 
77 static bool IsEquivalentPHI(PHINode *PHI,
79  unsigned PHINumValues = PHI->getNumIncomingValues();
80  if (PHINumValues != ValueMapping.size())
81  return false;
82 
83  // Scan the phi to see if it matches.
84  for (unsigned i = 0, e = PHINumValues; i != e; ++i)
85  if (ValueMapping[PHI->getIncomingBlock(i)] !=
86  PHI->getIncomingValue(i)) {
87  return false;
88  }
89 
90  return true;
91 }
92 
94  Value *Res = GetValueAtEndOfBlockInternal(BB);
95  return Res;
96 }
97 
99  // If there is no definition of the renamed variable in this block, just use
100  // GetValueAtEndOfBlock to do our work.
101  if (!HasValueForBlock(BB))
102  return GetValueAtEndOfBlock(BB);
103 
104  // Otherwise, we have the hard case. Get the live-in values for each
105  // predecessor.
107  Value *SingularValue = nullptr;
108 
109  // We can get our predecessor info by walking the pred_iterator list, but it
110  // is relatively slow. If we already have PHI nodes in this block, walk one
111  // of them to get the predecessor list instead.
112  if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
113  for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
114  BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
115  Value *PredVal = GetValueAtEndOfBlock(PredBB);
116  PredValues.push_back(std::make_pair(PredBB, PredVal));
117 
118  // Compute SingularValue.
119  if (i == 0)
120  SingularValue = PredVal;
121  else if (PredVal != SingularValue)
122  SingularValue = nullptr;
123  }
124  } else {
125  bool isFirstPred = true;
126  for (BasicBlock *PredBB : predecessors(BB)) {
127  Value *PredVal = GetValueAtEndOfBlock(PredBB);
128  PredValues.push_back(std::make_pair(PredBB, PredVal));
129 
130  // Compute SingularValue.
131  if (isFirstPred) {
132  SingularValue = PredVal;
133  isFirstPred = false;
134  } else if (PredVal != SingularValue)
135  SingularValue = nullptr;
136  }
137  }
138 
139  // If there are no predecessors, just return undef.
140  if (PredValues.empty())
141  return UndefValue::get(ProtoType);
142 
143  // Otherwise, if all the merged values are the same, just use it.
144  if (SingularValue)
145  return SingularValue;
146 
147  // Otherwise, we do need a PHI: check to see if we already have one available
148  // in this block that produces the right value.
149  if (isa<PHINode>(BB->begin())) {
150  SmallDenseMap<BasicBlock *, Value *, 8> ValueMapping(PredValues.begin(),
151  PredValues.end());
152  for (PHINode &SomePHI : BB->phis()) {
153  if (IsEquivalentPHI(&SomePHI, ValueMapping))
154  return &SomePHI;
155  }
156  }
157 
158  // Ok, we have no way out, insert a new one now.
159  PHINode *InsertedPHI = PHINode::Create(ProtoType, PredValues.size(),
160  ProtoName, &BB->front());
161 
162  // Fill in all the predecessors of the PHI.
163  for (const auto &PredValue : PredValues)
164  InsertedPHI->addIncoming(PredValue.second, PredValue.first);
165 
166  // See if the PHI node can be merged to a single value. This can happen in
167  // loop cases when we get a PHI of itself and one other value.
168  if (Value *V =
169  SimplifyInstruction(InsertedPHI, BB->getModule()->getDataLayout())) {
170  InsertedPHI->eraseFromParent();
171  return V;
172  }
173 
174  // Set the DebugLoc of the inserted PHI, if available.
175  DebugLoc DL;
176  if (const Instruction *I = BB->getFirstNonPHI())
177  DL = I->getDebugLoc();
178  InsertedPHI->setDebugLoc(DL);
179 
180  // If the client wants to know about all new instructions, tell it.
181  if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
182 
183  LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
184  return InsertedPHI;
185 }
186 
188  Instruction *User = cast<Instruction>(U.getUser());
189 
190  Value *V;
191  if (PHINode *UserPN = dyn_cast<PHINode>(User))
192  V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
193  else
194  V = GetValueInMiddleOfBlock(User->getParent());
195 
196  U.set(V);
197 }
198 
200  Instruction *User = cast<Instruction>(U.getUser());
201 
202  Value *V;
203  if (PHINode *UserPN = dyn_cast<PHINode>(User))
204  V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
205  else
206  V = GetValueAtEndOfBlock(User->getParent());
207 
208  U.set(V);
209 }
210 
211 namespace llvm {
212 
213 template<>
215 public:
216  using BlkT = BasicBlock;
217  using ValT = Value *;
218  using PhiT = PHINode;
220 
223 
224  class PHI_iterator {
225  private:
226  PHINode *PHI;
227  unsigned idx;
228 
229  public:
230  explicit PHI_iterator(PHINode *P) // begin iterator
231  : PHI(P), idx(0) {}
232  PHI_iterator(PHINode *P, bool) // end iterator
233  : PHI(P), idx(PHI->getNumIncomingValues()) {}
234 
235  PHI_iterator &operator++() { ++idx; return *this; }
236  bool operator==(const PHI_iterator& x) const { return idx == x.idx; }
237  bool operator!=(const PHI_iterator& x) const { return !operator==(x); }
238 
239  Value *getIncomingValue() { return PHI->getIncomingValue(idx); }
241  };
242 
243  static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
244  static PHI_iterator PHI_end(PhiT *PHI) {
245  return PHI_iterator(PHI, true);
246  }
247 
248  /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
249  /// vector, set Info->NumPreds, and allocate space in Info->Preds.
252  // We can get our predecessor info by walking the pred_iterator list,
253  // but it is relatively slow. If we already have PHI nodes in this
254  // block, walk one of them to get the predecessor list instead.
255  if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin()))
256  append_range(*Preds, SomePhi->blocks());
257  else
258  append_range(*Preds, predecessors(BB));
259  }
260 
261  /// GetUndefVal - Get an undefined value of the same type as the value
262  /// being handled.
263  static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) {
264  return UndefValue::get(Updater->ProtoType);
265  }
266 
267  /// CreateEmptyPHI - Create a new PHI instruction in the specified block.
268  /// Reserve space for the operands but do not fill them in yet.
269  static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds,
270  SSAUpdater *Updater) {
271  PHINode *PHI = PHINode::Create(Updater->ProtoType, NumPreds,
272  Updater->ProtoName, &BB->front());
273  return PHI;
274  }
275 
276  /// AddPHIOperand - Add the specified value as an operand of the PHI for
277  /// the specified predecessor block.
278  static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) {
279  PHI->addIncoming(Val, Pred);
280  }
281 
282  /// ValueIsPHI - Check if a value is a PHI.
283  static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) {
284  return dyn_cast<PHINode>(Val);
285  }
286 
287  /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
288  /// operands, i.e., it was just added.
289  static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) {
290  PHINode *PHI = ValueIsPHI(Val, Updater);
291  if (PHI && PHI->getNumIncomingValues() == 0)
292  return PHI;
293  return nullptr;
294  }
295 
296  /// GetPHIValue - For the specified PHI instruction, return the value
297  /// that it defines.
298  static Value *GetPHIValue(PHINode *PHI) {
299  return PHI;
300  }
301 };
302 
303 } // end namespace llvm
304 
305 /// Check to see if AvailableVals has an entry for the specified BB and if so,
306 /// return it. If not, construct SSA form by first calculating the required
307 /// placement of PHIs and then inserting new PHIs where needed.
308 Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
309  AvailableValsTy &AvailableVals = getAvailableVals(AV);
310  if (Value *V = AvailableVals[BB])
311  return V;
312 
313  SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
314  return Impl.GetValue(BB);
315 }
316 
317 //===----------------------------------------------------------------------===//
318 // LoadAndStorePromoter Implementation
319 //===----------------------------------------------------------------------===//
320 
323  SSAUpdater &S, StringRef BaseName) : SSA(S) {
324  if (Insts.empty()) return;
325 
326  const Value *SomeVal;
327  if (const LoadInst *LI = dyn_cast<LoadInst>(Insts[0]))
328  SomeVal = LI;
329  else
330  SomeVal = cast<StoreInst>(Insts[0])->getOperand(0);
331 
332  if (BaseName.empty())
333  BaseName = SomeVal->getName();
334  SSA.Initialize(SomeVal->getType(), BaseName);
335 }
336 
338  // First step: bucket up uses of the alloca by the block they occur in.
339  // This is important because we have to handle multiple defs/uses in a block
340  // ourselves: SSAUpdater is purely for cross-block references.
342 
343  for (Instruction *User : Insts)
344  UsesByBlock[User->getParent()].push_back(User);
345 
346  // Okay, now we can iterate over all the blocks in the function with uses,
347  // processing them. Keep track of which loads are loading a live-in value.
348  // Walk the uses in the use-list order to be determinstic.
349  SmallVector<LoadInst *, 32> LiveInLoads;
350  DenseMap<Value *, Value *> ReplacedLoads;
351 
352  for (Instruction *User : Insts) {
353  BasicBlock *BB = User->getParent();
354  TinyPtrVector<Instruction *> &BlockUses = UsesByBlock[BB];
355 
356  // If this block has already been processed, ignore this repeat use.
357  if (BlockUses.empty()) continue;
358 
359  // Okay, this is the first use in the block. If this block just has a
360  // single user in it, we can rewrite it trivially.
361  if (BlockUses.size() == 1) {
362  // If it is a store, it is a trivial def of the value in the block.
363  if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
365  SSA.AddAvailableValue(BB, SI->getOperand(0));
366  } else
367  // Otherwise it is a load, queue it to rewrite as a live-in load.
368  LiveInLoads.push_back(cast<LoadInst>(User));
369  BlockUses.clear();
370  continue;
371  }
372 
373  // Otherwise, check to see if this block is all loads.
374  bool HasStore = false;
375  for (Instruction *I : BlockUses) {
376  if (isa<StoreInst>(I)) {
377  HasStore = true;
378  break;
379  }
380  }
381 
382  // If so, we can queue them all as live in loads. We don't have an
383  // efficient way to tell which on is first in the block and don't want to
384  // scan large blocks, so just add all loads as live ins.
385  if (!HasStore) {
386  for (Instruction *I : BlockUses)
387  LiveInLoads.push_back(cast<LoadInst>(I));
388  BlockUses.clear();
389  continue;
390  }
391 
392  // Otherwise, we have mixed loads and stores (or just a bunch of stores).
393  // Since SSAUpdater is purely for cross-block values, we need to determine
394  // the order of these instructions in the block. If the first use in the
395  // block is a load, then it uses the live in value. The last store defines
396  // the live out value. We handle this by doing a linear scan of the block.
397  Value *StoredValue = nullptr;
398  for (Instruction &I : *BB) {
399  if (LoadInst *L = dyn_cast<LoadInst>(&I)) {
400  // If this is a load from an unrelated pointer, ignore it.
401  if (!isInstInList(L, Insts)) continue;
402 
403  // If we haven't seen a store yet, this is a live in use, otherwise
404  // use the stored value.
405  if (StoredValue) {
406  replaceLoadWithValue(L, StoredValue);
407  L->replaceAllUsesWith(StoredValue);
408  ReplacedLoads[L] = StoredValue;
409  } else {
410  LiveInLoads.push_back(L);
411  }
412  continue;
413  }
414 
415  if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
416  // If this is a store to an unrelated pointer, ignore it.
417  if (!isInstInList(SI, Insts)) continue;
419 
420  // Remember that this is the active value in the block.
421  StoredValue = SI->getOperand(0);
422  }
423  }
424 
425  // The last stored value that happened is the live-out for the block.
426  assert(StoredValue && "Already checked that there is a store in block");
427  SSA.AddAvailableValue(BB, StoredValue);
428  BlockUses.clear();
429  }
430 
431  // Okay, now we rewrite all loads that use live-in values in the loop,
432  // inserting PHI nodes as necessary.
433  for (LoadInst *ALoad : LiveInLoads) {
434  Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent());
435  replaceLoadWithValue(ALoad, NewVal);
436 
437  // Avoid assertions in unreachable code.
438  if (NewVal == ALoad) NewVal = UndefValue::get(NewVal->getType());
439  ALoad->replaceAllUsesWith(NewVal);
440  ReplacedLoads[ALoad] = NewVal;
441  }
442 
443  // Allow the client to do stuff before we start nuking things.
445 
446  // Now that everything is rewritten, delete the old instructions from the
447  // function. They should all be dead now.
448  for (Instruction *User : Insts) {
449  // If this is a load that still has uses, then the load must have been added
450  // as a live value in the SSAUpdate data structure for a block (e.g. because
451  // the loaded value was stored later). In this case, we need to recursively
452  // propagate the updates until we get to the real value.
453  if (!User->use_empty()) {
454  Value *NewVal = ReplacedLoads[User];
455  assert(NewVal && "not a replaced load?");
456 
457  // Propagate down to the ultimate replacee. The intermediately loads
458  // could theoretically already have been deleted, so we don't want to
459  // dereference the Value*'s.
460  DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal);
461  while (RLI != ReplacedLoads.end()) {
462  NewVal = RLI->second;
463  RLI = ReplacedLoads.find(NewVal);
464  }
465 
466  replaceLoadWithValue(cast<LoadInst>(User), NewVal);
467  User->replaceAllUsesWith(NewVal);
468  }
469 
471  User->eraseFromParent();
472  }
473 }
474 
475 bool
477  const SmallVectorImpl<Instruction *> &Insts)
478  const {
479  return is_contained(Insts, I);
480 }
llvm::SuccIterator
Definition: CFG.h:139
i
i
Definition: README.txt:29
llvm::SSAUpdater::Initialize
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
Definition: SSAUpdater.cpp:53
llvm::SSAUpdaterTraits< SSAUpdater >::PHI_iterator::getIncomingBlock
BasicBlock * getIncomingBlock()
Definition: SSAUpdater.cpp:240
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm
Definition: AllocatorList.h:23
llvm::StringRef::empty
LLVM_NODISCARD bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:156
IsEquivalentPHI
static bool IsEquivalentPHI(PHINode *PHI, SmallDenseMap< BasicBlock *, Value *, 8 > &ValueMapping)
Definition: SSAUpdater.cpp:77
llvm::SSAUpdater::SSAUpdater
SSAUpdater(SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
If InsertedPHIs is specified, it will be filled in with all PHI Nodes created by rewriting.
Definition: SSAUpdater.cpp:46
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::SSAUpdaterTraits< SSAUpdater >::ValueIsPHI
static PHINode * ValueIsPHI(Value *Val, SSAUpdater *Updater)
ValueIsPHI - Check if a value is a PHI.
Definition: SSAUpdater.cpp:283
llvm::DenseMapBase::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
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::SmallDenseMap
Definition: DenseMap.h:880
llvm::DenseMapIterator
Definition: DenseMap.h:56
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::LoadAndStorePromoter::updateDebugInfo
virtual void updateDebugInfo(Instruction *I) const
Called to update debug info associated with the instruction.
Definition: SSAUpdater.h:171
DenseMap.h
llvm::SSAUpdaterTraits< SSAUpdater >::PHI_iterator::operator!=
bool operator!=(const PHI_iterator &x) const
Definition: SSAUpdater.cpp:237
Module.h
llvm::DenseMapBase::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
STLExtras.h
llvm::SSAUpdaterTraits< SSAUpdater >::FindPredecessorBlocks
static void FindPredecessorBlocks(BasicBlock *BB, SmallVectorImpl< BasicBlock * > *Preds)
FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds vector, set Info->NumPreds,...
Definition: SSAUpdater.cpp:250
Use.h
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:158
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::LoadAndStorePromoter::replaceLoadWithValue
virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const
Clients can choose to implement this to get notified right before a load is RAUW'd another value.
Definition: SSAUpdater.h:165
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Instruction.h
Constants.h
llvm::SSAUpdaterTraits< SSAUpdater >::PHI_iterator::operator==
bool operator==(const PHI_iterator &x) const
Definition: SSAUpdater.cpp:236
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2668
llvm::User
Definition: User.h:44
llvm::LoadAndStorePromoter::run
void run(const SmallVectorImpl< Instruction * > &Insts)
This does the promotion.
Definition: SSAUpdater.cpp:337
SI
@ SI
Definition: SIInstrInfo.cpp:7411
SSAUpdaterImpl.h
llvm::SSAUpdater::RewriteUseAfterInsertions
void RewriteUseAfterInsertions(Use &U)
Rewrite a use like RewriteUse but handling in-block definitions.
Definition: SSAUpdater.cpp:199
llvm::Instruction
Definition: Instruction.h:45
llvm::SSAUpdaterTraits< SSAUpdater >::GetPHIValue
static Value * GetPHIValue(PHINode *PHI)
GetPHIValue - For the specified PHI instruction, return the value that it defines.
Definition: SSAUpdater.cpp:298
llvm::SimplifyInstruction
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:5788
llvm::SSAUpdaterTraits< SSAUpdater >::ValueIsNewPHI
static PHINode * ValueIsNewPHI(Value *Val, SSAUpdater *Updater)
ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source operands, i....
Definition: SSAUpdater.cpp:289
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1770
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
DebugLoc.h
llvm::SSAUpdaterTraits< SSAUpdater >::PHI_end
static PHI_iterator PHI_end(PhiT *PHI)
Definition: SSAUpdater.cpp:244
llvm::SSAUpdaterTraits< SSAUpdater >::BlkSucc_begin
static BlkSucc_iterator BlkSucc_begin(BlkT *BB)
Definition: SSAUpdater.cpp:221
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2664
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:357
CFG.h
llvm::SSAUpdater::~SSAUpdater
~SSAUpdater()
Definition: SSAUpdater.cpp:49
llvm::Use::set
void set(Value *Val)
Definition: Value.h:872
BasicBlock.h
SSA
Memory SSA
Definition: MemorySSA.cpp:73
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:303
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:111
llvm::TinyPtrVector::clear
void clear()
Definition: TinyPtrVector.h:271
llvm::SSAUpdater::GetValueInMiddleOfBlock
Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block.
Definition: SSAUpdater.cpp:98
llvm::SSAUpdaterTraits< SSAUpdater >::AddPHIOperand
static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred)
AddPHIOperand - Add the specified value as an operand of the PHI for the specified predecessor block.
Definition: SSAUpdater.cpp:278
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2722
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::SSAUpdaterTraits< SSAUpdater >::CreateEmptyPHI
static Value * CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds, SSAUpdater *Updater)
CreateEmptyPHI - Create a new PHI instruction in the specified block.
Definition: SSAUpdater.cpp:269
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1547
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:362
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2037
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
TinyPtrVector.h
llvm::LoadAndStorePromoter::SSA
SSAUpdater & SSA
Definition: SSAUpdater.h:138
llvm::SSAUpdaterTraits< SSAUpdater >::PHI_begin
static PHI_iterator PHI_begin(PhiT *PHI)
Definition: SSAUpdater.cpp:243
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::TinyPtrVector::size
unsigned size() const
Definition: TinyPtrVector.h:172
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::SSAUpdaterTraits< SSAUpdater >::BlkSucc_end
static BlkSucc_iterator BlkSucc_end(BlkT *BB)
Definition: SSAUpdater.cpp:222
llvm::SSAUpdater::GetValueAtEndOfBlock
Value * GetValueAtEndOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live at the end of the specified block.
Definition: SSAUpdater.cpp:93
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::SSAUpdater::FindValueForBlock
Value * FindValueForBlock(BasicBlock *BB) const
Return the value for the specified block if the SSAUpdater has one, otherwise return nullptr.
Definition: SSAUpdater.cpp:66
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:527
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1667
llvm::LoadAndStorePromoter::LoadAndStorePromoter
LoadAndStorePromoter(ArrayRef< const Instruction * > Insts, SSAUpdater &S, StringRef Name=StringRef())
Definition: SSAUpdater.cpp:322
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
AvailableValsTy
DenseMap< BasicBlock *, Value * > AvailableValsTy
Definition: SSAUpdater.cpp:40
SSAUpdater.h
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:299
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
ValueHandle.h
llvm::SSAUpdater::HasValueForBlock
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
Definition: SSAUpdater.cpp:62
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::PHINode::Create
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Definition: Instructions.h:2614
Casting.h
llvm::SSAUpdaterTraits< SSAUpdater >::GetUndefVal
static Value * GetUndefVal(BasicBlock *BB, SSAUpdater *Updater)
GetUndefVal - Get an undefined value of the same type as the value being handled.
Definition: SSAUpdater.cpp:263
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::size
unsigned size() const
Definition: DenseMap.h:100
x
TODO unsigned x
Definition: README.txt:10
llvm::SSAUpdaterTraits< SSAUpdater >::PHI_iterator::PHI_iterator
PHI_iterator(PHINode *P)
Definition: SSAUpdater.cpp:230
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::SSAUpdaterTraits
Definition: MachineSSAUpdater.h:28
llvm::TinyPtrVector::empty
bool empty() const
Definition: TinyPtrVector.h:163
Instructions.h
SmallVector.h
llvm::LoadAndStorePromoter::doExtraRewritesBeforeFinalDeletion
virtual void doExtraRewritesBeforeFinalDeletion()
This hook is invoked after all the stores are found and inserted as available values.
Definition: SSAUpdater.h:161
llvm::SSAUpdater::RewriteUse
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Definition: SSAUpdater.cpp:187
InstructionSimplify.h
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2688
llvm::PHINode
Definition: Instructions.h:2572
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::succ_iterator
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:243
llvm::SSAUpdaterTraits< SSAUpdater >::PHI_iterator::operator++
PHI_iterator & operator++()
Definition: SSAUpdater.cpp:235
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::LoadAndStorePromoter::instructionDeleted
virtual void instructionDeleted(Instruction *I) const
Called before each instruction is deleted.
Definition: SSAUpdater.h:168
getAvailableVals
static AvailableValsTy & getAvailableVals(void *AV)
Definition: SSAUpdater.cpp:42
llvm::SSAUpdater::AddAvailableValue
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdater.cpp:70
raw_ostream.h
llvm::TinyPtrVector
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
llvm::SSAUpdater
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:38
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::SSAUpdaterTraits< SSAUpdater >::PHI_iterator::PHI_iterator
PHI_iterator(PHINode *P, bool)
Definition: SSAUpdater.cpp:232
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SSAUpdaterTraits< SSAUpdater >::PHI_iterator::getIncomingValue
Value * getIncomingValue()
Definition: SSAUpdater.cpp:239
llvm::LoadAndStorePromoter::isInstInList
virtual bool isInstInList(Instruction *I, const SmallVectorImpl< Instruction * > &Insts) const
Return true if the specified instruction is in the Inst list.
Definition: SSAUpdater.cpp:476
llvm::SSAUpdaterImpl
Definition: SSAUpdaterImpl.h:30