1 //===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the SSAUpdater class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Transforms/Utils/SSAUpdater.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/TinyPtrVector.h"
17 #include "llvm/Analysis/InstructionSimplify.h"
18 #include "llvm/IR/CFG.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/IntrinsicInst.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
25 #include "llvm/Transforms/Utils/Local.h"
26 #include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
30 #define DEBUG_TYPE "ssaupdater"
32 typedef DenseMap
<BasicBlock
*, Value
*> AvailableValsTy
;
33 static AvailableValsTy
&getAvailableVals(void *AV
) {
34 return *static_cast<AvailableValsTy
*>(AV
);
37 SSAUpdater::SSAUpdater(SmallVectorImpl
<PHINode
*> *NewPHI
)
38 : AV(nullptr), ProtoType(nullptr), ProtoName(), InsertedPHIs(NewPHI
) {}
40 SSAUpdater::~SSAUpdater() {
41 delete static_cast<AvailableValsTy
*>(AV
);
44 void SSAUpdater::Initialize(Type
*Ty
, StringRef Name
) {
46 AV
= new AvailableValsTy();
48 getAvailableVals(AV
).clear();
53 bool SSAUpdater::HasValueForBlock(BasicBlock
*BB
) const {
54 return getAvailableVals(AV
).count(BB
);
57 void SSAUpdater::AddAvailableValue(BasicBlock
*BB
, Value
*V
) {
58 assert(ProtoType
&& "Need to initialize SSAUpdater");
59 assert(ProtoType
== V
->getType() &&
60 "All rewritten values must have the same type");
61 getAvailableVals(AV
)[BB
] = V
;
64 static bool IsEquivalentPHI(PHINode
*PHI
,
65 SmallDenseMap
<BasicBlock
*, Value
*, 8> &ValueMapping
) {
66 unsigned PHINumValues
= PHI
->getNumIncomingValues();
67 if (PHINumValues
!= ValueMapping
.size())
70 // Scan the phi to see if it matches.
71 for (unsigned i
= 0, e
= PHINumValues
; i
!= e
; ++i
)
72 if (ValueMapping
[PHI
->getIncomingBlock(i
)] !=
73 PHI
->getIncomingValue(i
)) {
80 Value
*SSAUpdater::GetValueAtEndOfBlock(BasicBlock
*BB
) {
81 Value
*Res
= GetValueAtEndOfBlockInternal(BB
);
85 Value
*SSAUpdater::GetValueInMiddleOfBlock(BasicBlock
*BB
) {
86 // If there is no definition of the renamed variable in this block, just use
87 // GetValueAtEndOfBlock to do our work.
88 if (!HasValueForBlock(BB
))
89 return GetValueAtEndOfBlock(BB
);
91 // Otherwise, we have the hard case. Get the live-in values for each
93 SmallVector
<std::pair
<BasicBlock
*, Value
*>, 8> PredValues
;
94 Value
*SingularValue
= nullptr;
96 // We can get our predecessor info by walking the pred_iterator list, but it
97 // is relatively slow. If we already have PHI nodes in this block, walk one
98 // of them to get the predecessor list instead.
99 if (PHINode
*SomePhi
= dyn_cast
<PHINode
>(BB
->begin())) {
100 for (unsigned i
= 0, e
= SomePhi
->getNumIncomingValues(); i
!= e
; ++i
) {
101 BasicBlock
*PredBB
= SomePhi
->getIncomingBlock(i
);
102 Value
*PredVal
= GetValueAtEndOfBlock(PredBB
);
103 PredValues
.push_back(std::make_pair(PredBB
, PredVal
));
105 // Compute SingularValue.
107 SingularValue
= PredVal
;
108 else if (PredVal
!= SingularValue
)
109 SingularValue
= nullptr;
112 bool isFirstPred
= true;
113 for (pred_iterator PI
= pred_begin(BB
), E
= pred_end(BB
); PI
!= E
; ++PI
) {
114 BasicBlock
*PredBB
= *PI
;
115 Value
*PredVal
= GetValueAtEndOfBlock(PredBB
);
116 PredValues
.push_back(std::make_pair(PredBB
, PredVal
));
118 // Compute SingularValue.
120 SingularValue
= PredVal
;
122 } else if (PredVal
!= SingularValue
)
123 SingularValue
= nullptr;
127 // If there are no predecessors, just return undef.
128 if (PredValues
.empty())
129 return UndefValue::get(ProtoType
);
131 // Otherwise, if all the merged values are the same, just use it.
133 return SingularValue
;
135 // Otherwise, we do need a PHI: check to see if we already have one available
136 // in this block that produces the right value.
137 if (isa
<PHINode
>(BB
->begin())) {
138 SmallDenseMap
<BasicBlock
*, Value
*, 8> ValueMapping(PredValues
.begin(),
141 for (BasicBlock::iterator It
= BB
->begin();
142 (SomePHI
= dyn_cast
<PHINode
>(It
)); ++It
) {
143 if (IsEquivalentPHI(SomePHI
, ValueMapping
))
148 // Ok, we have no way out, insert a new one now.
149 PHINode
*InsertedPHI
= PHINode::Create(ProtoType
, PredValues
.size(),
150 ProtoName
, &BB
->front());
152 // Fill in all the predecessors of the PHI.
153 for (unsigned i
= 0, e
= PredValues
.size(); i
!= e
; ++i
)
154 InsertedPHI
->addIncoming(PredValues
[i
].second
, PredValues
[i
].first
);
156 // See if the PHI node can be merged to a single value. This can happen in
157 // loop cases when we get a PHI of itself and one other value.
158 if (Value
*V
= SimplifyInstruction(InsertedPHI
)) {
159 InsertedPHI
->eraseFromParent();
163 // Set the DebugLoc of the inserted PHI, if available.
165 if (const Instruction
*I
= BB
->getFirstNonPHI())
166 DL
= I
->getDebugLoc();
167 InsertedPHI
->setDebugLoc(DL
);
169 // If the client wants to know about all new instructions, tell it.
170 if (InsertedPHIs
) InsertedPHIs
->push_back(InsertedPHI
);
172 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI
<< "\n");
176 void SSAUpdater::RewriteUse(Use
&U
) {
177 Instruction
*User
= cast
<Instruction
>(U
.getUser());
180 if (PHINode
*UserPN
= dyn_cast
<PHINode
>(User
))
181 V
= GetValueAtEndOfBlock(UserPN
->getIncomingBlock(U
));
183 V
= GetValueInMiddleOfBlock(User
->getParent());
185 // Notify that users of the existing value that it is being replaced.
186 Value
*OldVal
= U
.get();
187 if (OldVal
!= V
&& OldVal
->hasValueHandle())
188 ValueHandleBase::ValueIsRAUWd(OldVal
, V
);
193 void SSAUpdater::RewriteUseAfterInsertions(Use
&U
) {
194 Instruction
*User
= cast
<Instruction
>(U
.getUser());
197 if (PHINode
*UserPN
= dyn_cast
<PHINode
>(User
))
198 V
= GetValueAtEndOfBlock(UserPN
->getIncomingBlock(U
));
200 V
= GetValueAtEndOfBlock(User
->getParent());
207 class SSAUpdaterTraits
<SSAUpdater
> {
209 typedef BasicBlock BlkT
;
211 typedef PHINode PhiT
;
213 typedef succ_iterator BlkSucc_iterator
;
214 static BlkSucc_iterator
BlkSucc_begin(BlkT
*BB
) { return succ_begin(BB
); }
215 static BlkSucc_iterator
BlkSucc_end(BlkT
*BB
) { return succ_end(BB
); }
223 explicit PHI_iterator(PHINode
*P
) // begin iterator
225 PHI_iterator(PHINode
*P
, bool) // end iterator
226 : PHI(P
), idx(PHI
->getNumIncomingValues()) {}
228 PHI_iterator
&operator++() { ++idx
; return *this; }
229 bool operator==(const PHI_iterator
& x
) const { return idx
== x
.idx
; }
230 bool operator!=(const PHI_iterator
& x
) const { return !operator==(x
); }
231 Value
*getIncomingValue() { return PHI
->getIncomingValue(idx
); }
232 BasicBlock
*getIncomingBlock() { return PHI
->getIncomingBlock(idx
); }
235 static PHI_iterator
PHI_begin(PhiT
*PHI
) { return PHI_iterator(PHI
); }
236 static PHI_iterator
PHI_end(PhiT
*PHI
) {
237 return PHI_iterator(PHI
, true);
240 /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
241 /// vector, set Info->NumPreds, and allocate space in Info->Preds.
242 static void FindPredecessorBlocks(BasicBlock
*BB
,
243 SmallVectorImpl
<BasicBlock
*> *Preds
) {
244 // We can get our predecessor info by walking the pred_iterator list,
245 // but it is relatively slow. If we already have PHI nodes in this
246 // block, walk one of them to get the predecessor list instead.
247 if (PHINode
*SomePhi
= dyn_cast
<PHINode
>(BB
->begin())) {
248 for (unsigned PI
= 0, E
= SomePhi
->getNumIncomingValues(); PI
!= E
; ++PI
)
249 Preds
->push_back(SomePhi
->getIncomingBlock(PI
));
251 for (pred_iterator PI
= pred_begin(BB
), E
= pred_end(BB
); PI
!= E
; ++PI
)
252 Preds
->push_back(*PI
);
256 /// GetUndefVal - Get an undefined value of the same type as the value
258 static Value
*GetUndefVal(BasicBlock
*BB
, SSAUpdater
*Updater
) {
259 return UndefValue::get(Updater
->ProtoType
);
262 /// CreateEmptyPHI - Create a new PHI instruction in the specified block.
263 /// Reserve space for the operands but do not fill them in yet.
264 static Value
*CreateEmptyPHI(BasicBlock
*BB
, unsigned NumPreds
,
265 SSAUpdater
*Updater
) {
266 PHINode
*PHI
= PHINode::Create(Updater
->ProtoType
, NumPreds
,
267 Updater
->ProtoName
, &BB
->front());
271 /// AddPHIOperand - Add the specified value as an operand of the PHI for
272 /// the specified predecessor block.
273 static void AddPHIOperand(PHINode
*PHI
, Value
*Val
, BasicBlock
*Pred
) {
274 PHI
->addIncoming(Val
, Pred
);
277 /// InstrIsPHI - Check if an instruction is a PHI.
279 static PHINode
*InstrIsPHI(Instruction
*I
) {
280 return dyn_cast
<PHINode
>(I
);
283 /// ValueIsPHI - Check if a value is a PHI.
285 static PHINode
*ValueIsPHI(Value
*Val
, SSAUpdater
*Updater
) {
286 return dyn_cast
<PHINode
>(Val
);
289 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
290 /// operands, i.e., it was just added.
291 static PHINode
*ValueIsNewPHI(Value
*Val
, SSAUpdater
*Updater
) {
292 PHINode
*PHI
= ValueIsPHI(Val
, Updater
);
293 if (PHI
&& PHI
->getNumIncomingValues() == 0)
298 /// GetPHIValue - For the specified PHI instruction, return the value
300 static Value
*GetPHIValue(PHINode
*PHI
) {
305 } // End llvm namespace
307 /// Check to see if AvailableVals has an entry for the specified BB and if so,
308 /// return it. If not, construct SSA form by first calculating the required
309 /// placement of PHIs and then inserting new PHIs where needed.
310 Value
*SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock
*BB
) {
311 AvailableValsTy
&AvailableVals
= getAvailableVals(AV
);
312 if (Value
*V
= AvailableVals
[BB
])
315 SSAUpdaterImpl
<SSAUpdater
> Impl(this, &AvailableVals
, InsertedPHIs
);
316 return Impl
.GetValue(BB
);
319 //===----------------------------------------------------------------------===//
320 // LoadAndStorePromoter Implementation
321 //===----------------------------------------------------------------------===//
323 LoadAndStorePromoter::
324 LoadAndStorePromoter(const SmallVectorImpl
<Instruction
*> &Insts
,
325 SSAUpdater
&S
, StringRef BaseName
) : SSA(S
) {
326 if (Insts
.empty()) return;
329 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(Insts
[0]))
332 SomeVal
= cast
<StoreInst
>(Insts
[0])->getOperand(0);
334 if (BaseName
.empty())
335 BaseName
= SomeVal
->getName();
336 SSA
.Initialize(SomeVal
->getType(), BaseName
);
340 void LoadAndStorePromoter::
341 run(const SmallVectorImpl
<Instruction
*> &Insts
) const {
343 // First step: bucket up uses of the alloca by the block they occur in.
344 // This is important because we have to handle multiple defs/uses in a block
345 // ourselves: SSAUpdater is purely for cross-block references.
346 DenseMap
<BasicBlock
*, TinyPtrVector
<Instruction
*> > UsesByBlock
;
348 for (unsigned i
= 0, e
= Insts
.size(); i
!= e
; ++i
) {
349 Instruction
*User
= Insts
[i
];
350 UsesByBlock
[User
->getParent()].push_back(User
);
353 // Okay, now we can iterate over all the blocks in the function with uses,
354 // processing them. Keep track of which loads are loading a live-in value.
355 // Walk the uses in the use-list order to be determinstic.
356 SmallVector
<LoadInst
*, 32> LiveInLoads
;
357 DenseMap
<Value
*, Value
*> ReplacedLoads
;
359 for (unsigned i
= 0, e
= Insts
.size(); i
!= e
; ++i
) {
360 Instruction
*User
= Insts
[i
];
361 BasicBlock
*BB
= User
->getParent();
362 TinyPtrVector
<Instruction
*> &BlockUses
= UsesByBlock
[BB
];
364 // If this block has already been processed, ignore this repeat use.
365 if (BlockUses
.empty()) continue;
367 // Okay, this is the first use in the block. If this block just has a
368 // single user in it, we can rewrite it trivially.
369 if (BlockUses
.size() == 1) {
370 // If it is a store, it is a trivial def of the value in the block.
371 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(User
)) {
373 SSA
.AddAvailableValue(BB
, SI
->getOperand(0));
375 // Otherwise it is a load, queue it to rewrite as a live-in load.
376 LiveInLoads
.push_back(cast
<LoadInst
>(User
));
381 // Otherwise, check to see if this block is all loads.
382 bool HasStore
= false;
383 for (unsigned i
= 0, e
= BlockUses
.size(); i
!= e
; ++i
) {
384 if (isa
<StoreInst
>(BlockUses
[i
])) {
390 // If so, we can queue them all as live in loads. We don't have an
391 // efficient way to tell which on is first in the block and don't want to
392 // scan large blocks, so just add all loads as live ins.
394 for (unsigned i
= 0, e
= BlockUses
.size(); i
!= e
; ++i
)
395 LiveInLoads
.push_back(cast
<LoadInst
>(BlockUses
[i
]));
400 // Otherwise, we have mixed loads and stores (or just a bunch of stores).
401 // Since SSAUpdater is purely for cross-block values, we need to determine
402 // the order of these instructions in the block. If the first use in the
403 // block is a load, then it uses the live in value. The last store defines
404 // the live out value. We handle this by doing a linear scan of the block.
405 Value
*StoredValue
= nullptr;
406 for (BasicBlock::iterator II
= BB
->begin(), E
= BB
->end(); II
!= E
; ++II
) {
407 if (LoadInst
*L
= dyn_cast
<LoadInst
>(II
)) {
408 // If this is a load from an unrelated pointer, ignore it.
409 if (!isInstInList(L
, Insts
)) continue;
411 // If we haven't seen a store yet, this is a live in use, otherwise
412 // use the stored value.
414 replaceLoadWithValue(L
, StoredValue
);
415 L
->replaceAllUsesWith(StoredValue
);
416 ReplacedLoads
[L
] = StoredValue
;
418 LiveInLoads
.push_back(L
);
423 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(II
)) {
424 // If this is a store to an unrelated pointer, ignore it.
425 if (!isInstInList(SI
, Insts
)) continue;
428 // Remember that this is the active value in the block.
429 StoredValue
= SI
->getOperand(0);
433 // The last stored value that happened is the live-out for the block.
434 assert(StoredValue
&& "Already checked that there is a store in block");
435 SSA
.AddAvailableValue(BB
, StoredValue
);
439 // Okay, now we rewrite all loads that use live-in values in the loop,
440 // inserting PHI nodes as necessary.
441 for (unsigned i
= 0, e
= LiveInLoads
.size(); i
!= e
; ++i
) {
442 LoadInst
*ALoad
= LiveInLoads
[i
];
443 Value
*NewVal
= SSA
.GetValueInMiddleOfBlock(ALoad
->getParent());
444 replaceLoadWithValue(ALoad
, NewVal
);
446 // Avoid assertions in unreachable code.
447 if (NewVal
== ALoad
) NewVal
= UndefValue::get(NewVal
->getType());
448 ALoad
->replaceAllUsesWith(NewVal
);
449 ReplacedLoads
[ALoad
] = NewVal
;
452 // Allow the client to do stuff before we start nuking things.
453 doExtraRewritesBeforeFinalDeletion();
455 // Now that everything is rewritten, delete the old instructions from the
456 // function. They should all be dead now.
457 for (unsigned i
= 0, e
= Insts
.size(); i
!= e
; ++i
) {
458 Instruction
*User
= Insts
[i
];
460 // If this is a load that still has uses, then the load must have been added
461 // as a live value in the SSAUpdate data structure for a block (e.g. because
462 // the loaded value was stored later). In this case, we need to recursively
463 // propagate the updates until we get to the real value.
464 if (!User
->use_empty()) {
465 Value
*NewVal
= ReplacedLoads
[User
];
466 assert(NewVal
&& "not a replaced load?");
468 // Propagate down to the ultimate replacee. The intermediately loads
469 // could theoretically already have been deleted, so we don't want to
470 // dereference the Value*'s.
471 DenseMap
<Value
*, Value
*>::iterator RLI
= ReplacedLoads
.find(NewVal
);
472 while (RLI
!= ReplacedLoads
.end()) {
473 NewVal
= RLI
->second
;
474 RLI
= ReplacedLoads
.find(NewVal
);
477 replaceLoadWithValue(cast
<LoadInst
>(User
), NewVal
);
478 User
->replaceAllUsesWith(NewVal
);
481 instructionDeleted(User
);
482 User
->eraseFromParent();
487 LoadAndStorePromoter::isInstInList(Instruction
*I
,
488 const SmallVectorImpl
<Instruction
*> &Insts
)
490 return std::find(Insts
.begin(), Insts
.end(), I
) != Insts
.end();