blob: 9e5fb0e7172d4d2d601dac8fe2c4d240401db0d5 [file] [log] [blame]
Chris Lattner60d4e692009-10-10 09:04:27 +00001//===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the SSAUpdater class.
11//
12//===----------------------------------------------------------------------===//
13
Chandler Carruth6bda14b2017-06-06 11:49:48 +000014#include "llvm/Transforms/Utils/SSAUpdater.h"
Chris Lattner60d4e692009-10-10 09:04:27 +000015#include "llvm/ADT/DenseMap.h"
Eugene Zelenko34c23272017-01-18 00:57:48 +000016#include "llvm/ADT/STLExtras.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000017#include "llvm/ADT/SmallVector.h"
Chris Lattner7b70bef2011-07-18 01:43:58 +000018#include "llvm/ADT/TinyPtrVector.h"
Duncan Sands63704952010-11-16 17:41:24 +000019#include "llvm/Analysis/InstructionSimplify.h"
Eugene Zelenko34c23272017-01-18 00:57:48 +000020#include "llvm/IR/BasicBlock.h"
Chandler Carruth1305dc32014-03-04 11:45:46 +000021#include "llvm/IR/CFG.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000022#include "llvm/IR/Constants.h"
Eugene Zelenko34c23272017-01-18 00:57:48 +000023#include "llvm/IR/DebugLoc.h"
24#include "llvm/IR/Instruction.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000025#include "llvm/IR/Instructions.h"
Mehdi Aminia28d91d2015-03-10 02:37:25 +000026#include "llvm/IR/Module.h"
Eugene Zelenko34c23272017-01-18 00:57:48 +000027#include "llvm/IR/Use.h"
28#include "llvm/IR/Value.h"
29#include "llvm/IR/ValueHandle.h"
30#include "llvm/Support/Casting.h"
Chris Lattner60d4e692009-10-10 09:04:27 +000031#include "llvm/Support/Debug.h"
Chris Lattner60d4e692009-10-10 09:04:27 +000032#include "llvm/Support/raw_ostream.h"
Bob Wilsond1b38e32010-05-04 23:18:19 +000033#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
Eugene Zelenko34c23272017-01-18 00:57:48 +000034#include <cassert>
35#include <utility>
Devang Patela8e74112011-04-29 22:28:59 +000036
Chris Lattner60d4e692009-10-10 09:04:27 +000037using namespace llvm;
38
Chandler Carruthe96dd892014-04-21 22:55:11 +000039#define DEBUG_TYPE "ssaupdater"
40
Eugene Zelenko286d5892017-10-11 21:41:43 +000041using AvailableValsTy = DenseMap<BasicBlock *, Value *>;
42
Chris Lattner60d4e692009-10-10 09:04:27 +000043static AvailableValsTy &getAvailableVals(void *AV) {
44 return *static_cast<AvailableValsTy*>(AV);
45}
46
Eugene Zelenko286d5892017-10-11 21:41:43 +000047SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode *> *NewPHI)
Eugene Zelenko34c23272017-01-18 00:57:48 +000048 : InsertedPHIs(NewPHI) {}
Chris Lattner60d4e692009-10-10 09:04:27 +000049
50SSAUpdater::~SSAUpdater() {
Richard Smith257c5f22012-08-17 21:42:44 +000051 delete static_cast<AvailableValsTy*>(AV);
Chris Lattner60d4e692009-10-10 09:04:27 +000052}
53
Chris Lattner229907c2011-07-18 04:54:35 +000054void SSAUpdater::Initialize(Type *Ty, StringRef Name) {
Craig Topperf40110f2014-04-25 05:29:35 +000055 if (!AV)
Chris Lattner60d4e692009-10-10 09:04:27 +000056 AV = new AvailableValsTy();
57 else
58 getAvailableVals(AV).clear();
Duncan Sands67781492010-09-02 08:14:03 +000059 ProtoType = Ty;
60 ProtoName = Name;
Chris Lattner60d4e692009-10-10 09:04:27 +000061}
62
Chris Lattner9c382ce2009-10-10 23:41:48 +000063bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const {
64 return getAvailableVals(AV).count(BB);
65}
66
David Stenbergc9163852018-10-16 08:06:48 +000067Value *SSAUpdater::FindValueForBlock(BasicBlock *BB) const {
68 AvailableValsTy::iterator AVI = getAvailableVals(AV).find(BB);
69 return (AVI != getAvailableVals(AV).end()) ? AVI->second : nullptr;
70}
71
Chris Lattner60d4e692009-10-10 09:04:27 +000072void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
Craig Toppere73658d2014-04-28 04:05:08 +000073 assert(ProtoType && "Need to initialize SSAUpdater");
Duncan Sands67781492010-09-02 08:14:03 +000074 assert(ProtoType == V->getType() &&
Chris Lattner60d4e692009-10-10 09:04:27 +000075 "All rewritten values must have the same type");
76 getAvailableVals(AV)[BB] = V;
77}
78
Bob Wilsonca514252010-04-17 03:08:24 +000079static bool IsEquivalentPHI(PHINode *PHI,
Eugene Zelenko286d5892017-10-11 21:41:43 +000080 SmallDenseMap<BasicBlock *, Value *, 8> &ValueMapping) {
Bob Wilson7577e942010-01-27 22:01:02 +000081 unsigned PHINumValues = PHI->getNumIncomingValues();
82 if (PHINumValues != ValueMapping.size())
83 return false;
84
85 // Scan the phi to see if it matches.
86 for (unsigned i = 0, e = PHINumValues; i != e; ++i)
87 if (ValueMapping[PHI->getIncomingBlock(i)] !=
88 PHI->getIncomingValue(i)) {
89 return false;
90 }
91
92 return true;
93}
94
Chris Lattnere474a8d2009-10-10 22:41:58 +000095Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
Chris Lattnere474a8d2009-10-10 22:41:58 +000096 Value *Res = GetValueAtEndOfBlockInternal(BB);
Chris Lattner60d4e692009-10-10 09:04:27 +000097 return Res;
98}
99
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000100Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
101 // If there is no definition of the renamed variable in this block, just use
102 // GetValueAtEndOfBlock to do our work.
Bob Wilsonca514252010-04-17 03:08:24 +0000103 if (!HasValueForBlock(BB))
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000104 return GetValueAtEndOfBlock(BB);
Duncan Sands0058c7b2009-10-16 15:20:13 +0000105
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000106 // Otherwise, we have the hard case. Get the live-in values for each
107 // predecessor.
Eugene Zelenko286d5892017-10-11 21:41:43 +0000108 SmallVector<std::pair<BasicBlock *, Value *>, 8> PredValues;
Craig Topperf40110f2014-04-25 05:29:35 +0000109 Value *SingularValue = nullptr;
Duncan Sands0058c7b2009-10-16 15:20:13 +0000110
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000111 // We can get our predecessor info by walking the pred_iterator list, but it
112 // is relatively slow. If we already have PHI nodes in this block, walk one
113 // of them to get the predecessor list instead.
114 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
115 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
116 BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
117 Value *PredVal = GetValueAtEndOfBlock(PredBB);
118 PredValues.push_back(std::make_pair(PredBB, PredVal));
Duncan Sands0058c7b2009-10-16 15:20:13 +0000119
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000120 // Compute SingularValue.
121 if (i == 0)
122 SingularValue = PredVal;
123 else if (PredVal != SingularValue)
Craig Topperf40110f2014-04-25 05:29:35 +0000124 SingularValue = nullptr;
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000125 }
126 } else {
127 bool isFirstPred = true;
Duncan P. N. Exon Smith6c990152014-07-21 17:06:51 +0000128 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
129 BasicBlock *PredBB = *PI;
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000130 Value *PredVal = GetValueAtEndOfBlock(PredBB);
131 PredValues.push_back(std::make_pair(PredBB, PredVal));
Duncan Sands0058c7b2009-10-16 15:20:13 +0000132
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000133 // Compute SingularValue.
134 if (isFirstPred) {
135 SingularValue = PredVal;
136 isFirstPred = false;
137 } else if (PredVal != SingularValue)
Craig Topperf40110f2014-04-25 05:29:35 +0000138 SingularValue = nullptr;
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000139 }
140 }
Duncan Sands0058c7b2009-10-16 15:20:13 +0000141
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000142 // If there are no predecessors, just return undef.
143 if (PredValues.empty())
Duncan Sands67781492010-09-02 08:14:03 +0000144 return UndefValue::get(ProtoType);
Duncan Sands0058c7b2009-10-16 15:20:13 +0000145
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000146 // Otherwise, if all the merged values are the same, just use it.
Craig Topperf40110f2014-04-25 05:29:35 +0000147 if (SingularValue)
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000148 return SingularValue;
Duncan Sands0058c7b2009-10-16 15:20:13 +0000149
Bob Wilsonca514252010-04-17 03:08:24 +0000150 // Otherwise, we do need a PHI: check to see if we already have one available
151 // in this block that produces the right value.
152 if (isa<PHINode>(BB->begin())) {
Eugene Zelenko286d5892017-10-11 21:41:43 +0000153 SmallDenseMap<BasicBlock *, Value *, 8> ValueMapping(PredValues.begin(),
154 PredValues.end());
Benjamin Kramerc7fc81e2017-12-30 15:27:33 +0000155 for (PHINode &SomePHI : BB->phis()) {
156 if (IsEquivalentPHI(&SomePHI, ValueMapping))
157 return &SomePHI;
Bob Wilsonca514252010-04-17 03:08:24 +0000158 }
159 }
Bob Wilson7577e942010-01-27 22:01:02 +0000160
Chris Lattner8fb07c52009-12-21 07:16:11 +0000161 // Ok, we have no way out, insert a new one now.
Jay Foad52131342011-03-30 11:28:46 +0000162 PHINode *InsertedPHI = PHINode::Create(ProtoType, PredValues.size(),
163 ProtoName, &BB->front());
Duncan Sands0058c7b2009-10-16 15:20:13 +0000164
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000165 // Fill in all the predecessors of the PHI.
Benjamin Kramerdfedfeb2015-02-19 20:04:02 +0000166 for (const auto &PredValue : PredValues)
167 InsertedPHI->addIncoming(PredValue.second, PredValue.first);
Duncan Sands0058c7b2009-10-16 15:20:13 +0000168
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000169 // See if the PHI node can be merged to a single value. This can happen in
170 // loop cases when we get a PHI of itself and one other value.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000171 if (Value *V =
172 SimplifyInstruction(InsertedPHI, BB->getModule()->getDataLayout())) {
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000173 InsertedPHI->eraseFromParent();
Duncan Sands63704952010-11-16 17:41:24 +0000174 return V;
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000175 }
Chris Lattner249265d2009-10-10 23:15:24 +0000176
Eli Benderskyf0ad3602012-06-25 10:13:14 +0000177 // Set the DebugLoc of the inserted PHI, if available.
178 DebugLoc DL;
179 if (const Instruction *I = BB->getFirstNonPHI())
180 DL = I->getDebugLoc();
181 InsertedPHI->setDebugLoc(DL);
Devang Patela8e74112011-04-29 22:28:59 +0000182
Chris Lattner249265d2009-10-10 23:15:24 +0000183 // If the client wants to know about all new instructions, tell it.
184 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
Duncan Sands0058c7b2009-10-16 15:20:13 +0000185
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000186 LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
Chris Lattner67cdd8b2009-10-10 23:00:11 +0000187 return InsertedPHI;
188}
189
Chris Lattner60d4e692009-10-10 09:04:27 +0000190void SSAUpdater::RewriteUse(Use &U) {
191 Instruction *User = cast<Instruction>(U.getUser());
Bob Wilsonca514252010-04-17 03:08:24 +0000192
Chris Lattner7f903682009-10-20 20:27:49 +0000193 Value *V;
194 if (PHINode *UserPN = dyn_cast<PHINode>(User))
195 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
196 else
197 V = GetValueInMiddleOfBlock(User->getParent());
Duncan Sands0058c7b2009-10-16 15:20:13 +0000198
Nadav Rotem8d804522012-08-13 23:06:54 +0000199 // Notify that users of the existing value that it is being replaced.
200 Value *OldVal = U.get();
201 if (OldVal != V && OldVal->hasValueHandle())
202 ValueHandleBase::ValueIsRAUWd(OldVal, V);
203
Torok Edwincf10ec92009-10-20 15:42:00 +0000204 U.set(V);
Chris Lattner60d4e692009-10-10 09:04:27 +0000205}
206
Chris Lattnerc3fb03e2010-08-29 04:54:06 +0000207void SSAUpdater::RewriteUseAfterInsertions(Use &U) {
208 Instruction *User = cast<Instruction>(U.getUser());
Fangrui Songf78650a2018-07-30 19:41:25 +0000209
Chris Lattnerc3fb03e2010-08-29 04:54:06 +0000210 Value *V;
211 if (PHINode *UserPN = dyn_cast<PHINode>(User))
212 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
213 else
214 V = GetValueAtEndOfBlock(User->getParent());
Fangrui Songf78650a2018-07-30 19:41:25 +0000215
Chris Lattnerc3fb03e2010-08-29 04:54:06 +0000216 U.set(V);
217}
218
Bob Wilsond1b38e32010-05-04 23:18:19 +0000219namespace llvm {
Eugene Zelenko34c23272017-01-18 00:57:48 +0000220
Bob Wilsond1b38e32010-05-04 23:18:19 +0000221template<>
222class SSAUpdaterTraits<SSAUpdater> {
223public:
Eugene Zelenko286d5892017-10-11 21:41:43 +0000224 using BlkT = BasicBlock;
225 using ValT = Value *;
226 using PhiT = PHINode;
227 using BlkSucc_iterator = succ_iterator;
Bob Wilsond1b38e32010-05-04 23:18:19 +0000228
Bob Wilsond1b38e32010-05-04 23:18:19 +0000229 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); }
230 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); }
231
Chandler Carruthc60fbe62012-06-20 08:39:30 +0000232 class PHI_iterator {
233 private:
234 PHINode *PHI;
235 unsigned idx;
236
237 public:
238 explicit PHI_iterator(PHINode *P) // begin iterator
239 : PHI(P), idx(0) {}
240 PHI_iterator(PHINode *P, bool) // end iterator
241 : PHI(P), idx(PHI->getNumIncomingValues()) {}
242
Fangrui Songf78650a2018-07-30 19:41:25 +0000243 PHI_iterator &operator++() { ++idx; return *this; }
Chandler Carruthc60fbe62012-06-20 08:39:30 +0000244 bool operator==(const PHI_iterator& x) const { return idx == x.idx; }
245 bool operator!=(const PHI_iterator& x) const { return !operator==(x); }
Eugene Zelenko34c23272017-01-18 00:57:48 +0000246
Chandler Carruthc60fbe62012-06-20 08:39:30 +0000247 Value *getIncomingValue() { return PHI->getIncomingValue(idx); }
248 BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); }
249 };
250
251 static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
252 static PHI_iterator PHI_end(PhiT *PHI) {
Bob Wilsond1b38e32010-05-04 23:18:19 +0000253 return PHI_iterator(PHI, true);
254 }
255
256 /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
257 /// vector, set Info->NumPreds, and allocate space in Info->Preds.
258 static void FindPredecessorBlocks(BasicBlock *BB,
Eugene Zelenko286d5892017-10-11 21:41:43 +0000259 SmallVectorImpl<BasicBlock *> *Preds) {
Bob Wilsond1b38e32010-05-04 23:18:19 +0000260 // We can get our predecessor info by walking the pred_iterator list,
261 // but it is relatively slow. If we already have PHI nodes in this
262 // block, walk one of them to get the predecessor list instead.
263 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
Benjamin Kramerdfedfeb2015-02-19 20:04:02 +0000264 Preds->append(SomePhi->block_begin(), SomePhi->block_end());
Bob Wilsond1b38e32010-05-04 23:18:19 +0000265 } else {
Duncan P. N. Exon Smith6c990152014-07-21 17:06:51 +0000266 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
267 Preds->push_back(*PI);
Bob Wilsond1b38e32010-05-04 23:18:19 +0000268 }
269 }
270
271 /// GetUndefVal - Get an undefined value of the same type as the value
272 /// being handled.
273 static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) {
Duncan Sands67781492010-09-02 08:14:03 +0000274 return UndefValue::get(Updater->ProtoType);
Bob Wilsond1b38e32010-05-04 23:18:19 +0000275 }
276
277 /// CreateEmptyPHI - Create a new PHI instruction in the specified block.
278 /// Reserve space for the operands but do not fill them in yet.
279 static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds,
280 SSAUpdater *Updater) {
Jay Foad52131342011-03-30 11:28:46 +0000281 PHINode *PHI = PHINode::Create(Updater->ProtoType, NumPreds,
282 Updater->ProtoName, &BB->front());
Bob Wilsond1b38e32010-05-04 23:18:19 +0000283 return PHI;
284 }
285
286 /// AddPHIOperand - Add the specified value as an operand of the PHI for
287 /// the specified predecessor block.
288 static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) {
289 PHI->addIncoming(Val, Pred);
290 }
291
292 /// InstrIsPHI - Check if an instruction is a PHI.
293 ///
294 static PHINode *InstrIsPHI(Instruction *I) {
295 return dyn_cast<PHINode>(I);
296 }
297
298 /// ValueIsPHI - Check if a value is a PHI.
Bob Wilsond1b38e32010-05-04 23:18:19 +0000299 static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) {
300 return dyn_cast<PHINode>(Val);
301 }
302
303 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
304 /// operands, i.e., it was just added.
305 static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) {
306 PHINode *PHI = ValueIsPHI(Val, Updater);
307 if (PHI && PHI->getNumIncomingValues() == 0)
308 return PHI;
Craig Topperf40110f2014-04-25 05:29:35 +0000309 return nullptr;
Bob Wilsond1b38e32010-05-04 23:18:19 +0000310 }
311
312 /// GetPHIValue - For the specified PHI instruction, return the value
313 /// that it defines.
314 static Value *GetPHIValue(PHINode *PHI) {
315 return PHI;
316 }
317};
318
Eugene Zelenko34c23272017-01-18 00:57:48 +0000319} // end namespace llvm
Bob Wilsond1b38e32010-05-04 23:18:19 +0000320
Chandler Carruth6b55dbe2013-07-28 22:00:33 +0000321/// Check to see if AvailableVals has an entry for the specified BB and if so,
322/// return it. If not, construct SSA form by first calculating the required
323/// placement of PHIs and then inserting new PHIs where needed.
Chris Lattnere474a8d2009-10-10 22:41:58 +0000324Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
Chris Lattner60d4e692009-10-10 09:04:27 +0000325 AvailableValsTy &AvailableVals = getAvailableVals(AV);
Bob Wilsonca514252010-04-17 03:08:24 +0000326 if (Value *V = AvailableVals[BB])
327 return V;
Duncan Sands0058c7b2009-10-16 15:20:13 +0000328
Bob Wilsond1b38e32010-05-04 23:18:19 +0000329 SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
330 return Impl.GetValue(BB);
Chris Lattner60d4e692009-10-10 09:04:27 +0000331}
Chris Lattner95294b82011-01-14 19:36:13 +0000332
333//===----------------------------------------------------------------------===//
334// LoadAndStorePromoter Implementation
335//===----------------------------------------------------------------------===//
336
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000337LoadAndStorePromoter::
Eugene Zelenko286d5892017-10-11 21:41:43 +0000338LoadAndStorePromoter(ArrayRef<const Instruction *> Insts,
Devang Patela3cbf522011-07-06 21:09:55 +0000339 SSAUpdater &S, StringRef BaseName) : SSA(S) {
Chris Lattner95294b82011-01-14 19:36:13 +0000340 if (Insts.empty()) return;
Fangrui Songf78650a2018-07-30 19:41:25 +0000341
Pete Cooper41e0ee32015-05-13 01:12:16 +0000342 const Value *SomeVal;
343 if (const LoadInst *LI = dyn_cast<LoadInst>(Insts[0]))
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000344 SomeVal = LI;
Chris Lattner95294b82011-01-14 19:36:13 +0000345 else
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000346 SomeVal = cast<StoreInst>(Insts[0])->getOperand(0);
347
348 if (BaseName.empty())
349 BaseName = SomeVal->getName();
350 SSA.Initialize(SomeVal->getType(), BaseName);
351}
352
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000353void LoadAndStorePromoter::
Eugene Zelenko286d5892017-10-11 21:41:43 +0000354run(const SmallVectorImpl<Instruction *> &Insts) const {
Chris Lattner95294b82011-01-14 19:36:13 +0000355 // First step: bucket up uses of the alloca by the block they occur in.
356 // This is important because we have to handle multiple defs/uses in a block
357 // ourselves: SSAUpdater is purely for cross-block references.
Eugene Zelenko286d5892017-10-11 21:41:43 +0000358 DenseMap<BasicBlock *, TinyPtrVector<Instruction *>> UsesByBlock;
Benjamin Kramerdfedfeb2015-02-19 20:04:02 +0000359
360 for (Instruction *User : Insts)
Chris Lattner95294b82011-01-14 19:36:13 +0000361 UsesByBlock[User->getParent()].push_back(User);
Fangrui Songf78650a2018-07-30 19:41:25 +0000362
Chris Lattner95294b82011-01-14 19:36:13 +0000363 // Okay, now we can iterate over all the blocks in the function with uses,
364 // processing them. Keep track of which loads are loading a live-in value.
365 // Walk the uses in the use-list order to be determinstic.
Eugene Zelenko286d5892017-10-11 21:41:43 +0000366 SmallVector<LoadInst *, 32> LiveInLoads;
367 DenseMap<Value *, Value *> ReplacedLoads;
Benjamin Kramerdfedfeb2015-02-19 20:04:02 +0000368
369 for (Instruction *User : Insts) {
Chris Lattner95294b82011-01-14 19:36:13 +0000370 BasicBlock *BB = User->getParent();
Eugene Zelenko286d5892017-10-11 21:41:43 +0000371 TinyPtrVector<Instruction *> &BlockUses = UsesByBlock[BB];
Fangrui Songf78650a2018-07-30 19:41:25 +0000372
Chris Lattner95294b82011-01-14 19:36:13 +0000373 // If this block has already been processed, ignore this repeat use.
374 if (BlockUses.empty()) continue;
Fangrui Songf78650a2018-07-30 19:41:25 +0000375
Chris Lattner95294b82011-01-14 19:36:13 +0000376 // Okay, this is the first use in the block. If this block just has a
377 // single user in it, we can rewrite it trivially.
378 if (BlockUses.size() == 1) {
379 // If it is a store, it is a trivial def of the value in the block.
Cameron Zwarich843bc7d2011-05-24 03:10:43 +0000380 if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
Devang Patela3cbf522011-07-06 21:09:55 +0000381 updateDebugInfo(SI);
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000382 SSA.AddAvailableValue(BB, SI->getOperand(0));
Fangrui Songf78650a2018-07-30 19:41:25 +0000383 } else
Chris Lattner95294b82011-01-14 19:36:13 +0000384 // Otherwise it is a load, queue it to rewrite as a live-in load.
385 LiveInLoads.push_back(cast<LoadInst>(User));
386 BlockUses.clear();
387 continue;
388 }
Fangrui Songf78650a2018-07-30 19:41:25 +0000389
Chris Lattner95294b82011-01-14 19:36:13 +0000390 // Otherwise, check to see if this block is all loads.
391 bool HasStore = false;
Benjamin Kramerdfedfeb2015-02-19 20:04:02 +0000392 for (Instruction *I : BlockUses) {
393 if (isa<StoreInst>(I)) {
Chris Lattner95294b82011-01-14 19:36:13 +0000394 HasStore = true;
395 break;
396 }
397 }
Fangrui Songf78650a2018-07-30 19:41:25 +0000398
Chris Lattner95294b82011-01-14 19:36:13 +0000399 // If so, we can queue them all as live in loads. We don't have an
400 // efficient way to tell which on is first in the block and don't want to
401 // scan large blocks, so just add all loads as live ins.
402 if (!HasStore) {
Benjamin Kramerdfedfeb2015-02-19 20:04:02 +0000403 for (Instruction *I : BlockUses)
404 LiveInLoads.push_back(cast<LoadInst>(I));
Chris Lattner95294b82011-01-14 19:36:13 +0000405 BlockUses.clear();
406 continue;
407 }
Fangrui Songf78650a2018-07-30 19:41:25 +0000408
Chris Lattner95294b82011-01-14 19:36:13 +0000409 // Otherwise, we have mixed loads and stores (or just a bunch of stores).
410 // Since SSAUpdater is purely for cross-block values, we need to determine
411 // the order of these instructions in the block. If the first use in the
412 // block is a load, then it uses the live in value. The last store defines
413 // the live out value. We handle this by doing a linear scan of the block.
Craig Topperf40110f2014-04-25 05:29:35 +0000414 Value *StoredValue = nullptr;
Benjamin Kramerdfedfeb2015-02-19 20:04:02 +0000415 for (Instruction &I : *BB) {
416 if (LoadInst *L = dyn_cast<LoadInst>(&I)) {
Chris Lattner95294b82011-01-14 19:36:13 +0000417 // If this is a load from an unrelated pointer, ignore it.
418 if (!isInstInList(L, Insts)) continue;
Fangrui Songf78650a2018-07-30 19:41:25 +0000419
Chris Lattner95294b82011-01-14 19:36:13 +0000420 // If we haven't seen a store yet, this is a live in use, otherwise
421 // use the stored value.
422 if (StoredValue) {
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000423 replaceLoadWithValue(L, StoredValue);
Chris Lattner95294b82011-01-14 19:36:13 +0000424 L->replaceAllUsesWith(StoredValue);
425 ReplacedLoads[L] = StoredValue;
426 } else {
427 LiveInLoads.push_back(L);
428 }
429 continue;
430 }
Benjamin Kramerdfedfeb2015-02-19 20:04:02 +0000431
432 if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
Chris Lattner95294b82011-01-14 19:36:13 +0000433 // If this is a store to an unrelated pointer, ignore it.
Cameron Zwarich843bc7d2011-05-24 03:10:43 +0000434 if (!isInstInList(SI, Insts)) continue;
Devang Patela3cbf522011-07-06 21:09:55 +0000435 updateDebugInfo(SI);
Cameron Zwarich843bc7d2011-05-24 03:10:43 +0000436
Chris Lattner95294b82011-01-14 19:36:13 +0000437 // Remember that this is the active value in the block.
Cameron Zwarich843bc7d2011-05-24 03:10:43 +0000438 StoredValue = SI->getOperand(0);
Chris Lattner95294b82011-01-14 19:36:13 +0000439 }
440 }
Fangrui Songf78650a2018-07-30 19:41:25 +0000441
Chris Lattner95294b82011-01-14 19:36:13 +0000442 // The last stored value that happened is the live-out for the block.
443 assert(StoredValue && "Already checked that there is a store in block");
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000444 SSA.AddAvailableValue(BB, StoredValue);
Chris Lattner95294b82011-01-14 19:36:13 +0000445 BlockUses.clear();
446 }
Fangrui Songf78650a2018-07-30 19:41:25 +0000447
Chris Lattner95294b82011-01-14 19:36:13 +0000448 // Okay, now we rewrite all loads that use live-in values in the loop,
449 // inserting PHI nodes as necessary.
Benjamin Kramerdfedfeb2015-02-19 20:04:02 +0000450 for (LoadInst *ALoad : LiveInLoads) {
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000451 Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent());
452 replaceLoadWithValue(ALoad, NewVal);
Chris Lattnerb4017762011-01-24 03:29:07 +0000453
454 // Avoid assertions in unreachable code.
455 if (NewVal == ALoad) NewVal = UndefValue::get(NewVal->getType());
Chris Lattner95294b82011-01-14 19:36:13 +0000456 ALoad->replaceAllUsesWith(NewVal);
457 ReplacedLoads[ALoad] = NewVal;
458 }
Fangrui Songf78650a2018-07-30 19:41:25 +0000459
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000460 // Allow the client to do stuff before we start nuking things.
461 doExtraRewritesBeforeFinalDeletion();
Fangrui Songf78650a2018-07-30 19:41:25 +0000462
Chris Lattner95294b82011-01-14 19:36:13 +0000463 // Now that everything is rewritten, delete the old instructions from the
464 // function. They should all be dead now.
Benjamin Kramerdfedfeb2015-02-19 20:04:02 +0000465 for (Instruction *User : Insts) {
Chris Lattner95294b82011-01-14 19:36:13 +0000466 // If this is a load that still has uses, then the load must have been added
467 // as a live value in the SSAUpdate data structure for a block (e.g. because
468 // the loaded value was stored later). In this case, we need to recursively
469 // propagate the updates until we get to the real value.
470 if (!User->use_empty()) {
471 Value *NewVal = ReplacedLoads[User];
472 assert(NewVal && "not a replaced load?");
Fangrui Songf78650a2018-07-30 19:41:25 +0000473
Chris Lattner95294b82011-01-14 19:36:13 +0000474 // Propagate down to the ultimate replacee. The intermediately loads
475 // could theoretically already have been deleted, so we don't want to
476 // dereference the Value*'s.
477 DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal);
478 while (RLI != ReplacedLoads.end()) {
479 NewVal = RLI->second;
480 RLI = ReplacedLoads.find(NewVal);
481 }
Fangrui Songf78650a2018-07-30 19:41:25 +0000482
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000483 replaceLoadWithValue(cast<LoadInst>(User), NewVal);
Chris Lattner95294b82011-01-14 19:36:13 +0000484 User->replaceAllUsesWith(NewVal);
485 }
Fangrui Songf78650a2018-07-30 19:41:25 +0000486
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000487 instructionDeleted(User);
Chris Lattner95294b82011-01-14 19:36:13 +0000488 User->eraseFromParent();
489 }
490}
Benjamin Kramerd00e94e2011-11-14 17:22:45 +0000491
492bool
493LoadAndStorePromoter::isInstInList(Instruction *I,
Eugene Zelenko286d5892017-10-11 21:41:43 +0000494 const SmallVectorImpl<Instruction *> &Insts)
Benjamin Kramerd00e94e2011-11-14 17:22:45 +0000495 const {
David Majnemer0d955d02016-08-11 22:21:41 +0000496 return is_contained(Insts, I);
Benjamin Kramerd00e94e2011-11-14 17:22:45 +0000497}