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