Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 1 | //===- 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 Carruth | 6bda14b | 2017-06-06 11:49:48 +0000 | [diff] [blame] | 14 | #include "llvm/Transforms/Utils/SSAUpdater.h" |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 15 | #include "llvm/ADT/DenseMap.h" |
Eugene Zelenko | 34c2327 | 2017-01-18 00:57:48 +0000 | [diff] [blame] | 16 | #include "llvm/ADT/STLExtras.h" |
Chandler Carruth | 6bda14b | 2017-06-06 11:49:48 +0000 | [diff] [blame] | 17 | #include "llvm/ADT/SmallVector.h" |
Chris Lattner | 7b70bef | 2011-07-18 01:43:58 +0000 | [diff] [blame] | 18 | #include "llvm/ADT/TinyPtrVector.h" |
Duncan Sands | 6370495 | 2010-11-16 17:41:24 +0000 | [diff] [blame] | 19 | #include "llvm/Analysis/InstructionSimplify.h" |
Eugene Zelenko | 34c2327 | 2017-01-18 00:57:48 +0000 | [diff] [blame] | 20 | #include "llvm/IR/BasicBlock.h" |
Chandler Carruth | 1305dc3 | 2014-03-04 11:45:46 +0000 | [diff] [blame] | 21 | #include "llvm/IR/CFG.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 22 | #include "llvm/IR/Constants.h" |
Eugene Zelenko | 34c2327 | 2017-01-18 00:57:48 +0000 | [diff] [blame] | 23 | #include "llvm/IR/DebugLoc.h" |
| 24 | #include "llvm/IR/Instruction.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 25 | #include "llvm/IR/Instructions.h" |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 26 | #include "llvm/IR/Module.h" |
Eugene Zelenko | 34c2327 | 2017-01-18 00:57:48 +0000 | [diff] [blame] | 27 | #include "llvm/IR/Use.h" |
| 28 | #include "llvm/IR/Value.h" |
| 29 | #include "llvm/IR/ValueHandle.h" |
| 30 | #include "llvm/Support/Casting.h" |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 31 | #include "llvm/Support/Debug.h" |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 32 | #include "llvm/Support/raw_ostream.h" |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 33 | #include "llvm/Transforms/Utils/SSAUpdaterImpl.h" |
Eugene Zelenko | 34c2327 | 2017-01-18 00:57:48 +0000 | [diff] [blame] | 34 | #include <cassert> |
| 35 | #include <utility> |
Devang Patel | a8e7411 | 2011-04-29 22:28:59 +0000 | [diff] [blame] | 36 | |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 37 | using namespace llvm; |
| 38 | |
Chandler Carruth | e96dd89 | 2014-04-21 22:55:11 +0000 | [diff] [blame] | 39 | #define DEBUG_TYPE "ssaupdater" |
| 40 | |
Eugene Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 41 | using AvailableValsTy = DenseMap<BasicBlock *, Value *>; |
| 42 | |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 43 | static AvailableValsTy &getAvailableVals(void *AV) { |
| 44 | return *static_cast<AvailableValsTy*>(AV); |
| 45 | } |
| 46 | |
Eugene Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 47 | SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode *> *NewPHI) |
Eugene Zelenko | 34c2327 | 2017-01-18 00:57:48 +0000 | [diff] [blame] | 48 | : InsertedPHIs(NewPHI) {} |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 49 | |
| 50 | SSAUpdater::~SSAUpdater() { |
Richard Smith | 257c5f2 | 2012-08-17 21:42:44 +0000 | [diff] [blame] | 51 | delete static_cast<AvailableValsTy*>(AV); |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 52 | } |
| 53 | |
Chris Lattner | 229907c | 2011-07-18 04:54:35 +0000 | [diff] [blame] | 54 | void SSAUpdater::Initialize(Type *Ty, StringRef Name) { |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 55 | if (!AV) |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 56 | AV = new AvailableValsTy(); |
| 57 | else |
| 58 | getAvailableVals(AV).clear(); |
Duncan Sands | 6778149 | 2010-09-02 08:14:03 +0000 | [diff] [blame] | 59 | ProtoType = Ty; |
| 60 | ProtoName = Name; |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 61 | } |
| 62 | |
Chris Lattner | 9c382ce | 2009-10-10 23:41:48 +0000 | [diff] [blame] | 63 | bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { |
| 64 | return getAvailableVals(AV).count(BB); |
| 65 | } |
| 66 | |
David Stenberg | c916385 | 2018-10-16 08:06:48 +0000 | [diff] [blame] | 67 | Value *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 Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 72 | void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { |
Craig Topper | e73658d | 2014-04-28 04:05:08 +0000 | [diff] [blame] | 73 | assert(ProtoType && "Need to initialize SSAUpdater"); |
Duncan Sands | 6778149 | 2010-09-02 08:14:03 +0000 | [diff] [blame] | 74 | assert(ProtoType == V->getType() && |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 75 | "All rewritten values must have the same type"); |
| 76 | getAvailableVals(AV)[BB] = V; |
| 77 | } |
| 78 | |
Bob Wilson | ca51425 | 2010-04-17 03:08:24 +0000 | [diff] [blame] | 79 | static bool IsEquivalentPHI(PHINode *PHI, |
Eugene Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 80 | SmallDenseMap<BasicBlock *, Value *, 8> &ValueMapping) { |
Bob Wilson | 7577e94 | 2010-01-27 22:01:02 +0000 | [diff] [blame] | 81 | 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 Lattner | e474a8d | 2009-10-10 22:41:58 +0000 | [diff] [blame] | 95 | Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { |
Chris Lattner | e474a8d | 2009-10-10 22:41:58 +0000 | [diff] [blame] | 96 | Value *Res = GetValueAtEndOfBlockInternal(BB); |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 97 | return Res; |
| 98 | } |
| 99 | |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 100 | Value *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 Wilson | ca51425 | 2010-04-17 03:08:24 +0000 | [diff] [blame] | 103 | if (!HasValueForBlock(BB)) |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 104 | return GetValueAtEndOfBlock(BB); |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 105 | |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 106 | // Otherwise, we have the hard case. Get the live-in values for each |
| 107 | // predecessor. |
Eugene Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 108 | SmallVector<std::pair<BasicBlock *, Value *>, 8> PredValues; |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 109 | Value *SingularValue = nullptr; |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 110 | |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 111 | // 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 Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 119 | |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 120 | // Compute SingularValue. |
| 121 | if (i == 0) |
| 122 | SingularValue = PredVal; |
| 123 | else if (PredVal != SingularValue) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 124 | SingularValue = nullptr; |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 125 | } |
| 126 | } else { |
| 127 | bool isFirstPred = true; |
Duncan P. N. Exon Smith | 6c99015 | 2014-07-21 17:06:51 +0000 | [diff] [blame] | 128 | for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { |
| 129 | BasicBlock *PredBB = *PI; |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 130 | Value *PredVal = GetValueAtEndOfBlock(PredBB); |
| 131 | PredValues.push_back(std::make_pair(PredBB, PredVal)); |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 132 | |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 133 | // Compute SingularValue. |
| 134 | if (isFirstPred) { |
| 135 | SingularValue = PredVal; |
| 136 | isFirstPred = false; |
| 137 | } else if (PredVal != SingularValue) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 138 | SingularValue = nullptr; |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 139 | } |
| 140 | } |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 141 | |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 142 | // If there are no predecessors, just return undef. |
| 143 | if (PredValues.empty()) |
Duncan Sands | 6778149 | 2010-09-02 08:14:03 +0000 | [diff] [blame] | 144 | return UndefValue::get(ProtoType); |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 145 | |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 146 | // Otherwise, if all the merged values are the same, just use it. |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 147 | if (SingularValue) |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 148 | return SingularValue; |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 149 | |
Bob Wilson | ca51425 | 2010-04-17 03:08:24 +0000 | [diff] [blame] | 150 | // 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 Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 153 | SmallDenseMap<BasicBlock *, Value *, 8> ValueMapping(PredValues.begin(), |
| 154 | PredValues.end()); |
Benjamin Kramer | c7fc81e | 2017-12-30 15:27:33 +0000 | [diff] [blame] | 155 | for (PHINode &SomePHI : BB->phis()) { |
| 156 | if (IsEquivalentPHI(&SomePHI, ValueMapping)) |
| 157 | return &SomePHI; |
Bob Wilson | ca51425 | 2010-04-17 03:08:24 +0000 | [diff] [blame] | 158 | } |
| 159 | } |
Bob Wilson | 7577e94 | 2010-01-27 22:01:02 +0000 | [diff] [blame] | 160 | |
Chris Lattner | 8fb07c5 | 2009-12-21 07:16:11 +0000 | [diff] [blame] | 161 | // Ok, we have no way out, insert a new one now. |
Jay Foad | 5213134 | 2011-03-30 11:28:46 +0000 | [diff] [blame] | 162 | PHINode *InsertedPHI = PHINode::Create(ProtoType, PredValues.size(), |
| 163 | ProtoName, &BB->front()); |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 164 | |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 165 | // Fill in all the predecessors of the PHI. |
Benjamin Kramer | dfedfeb | 2015-02-19 20:04:02 +0000 | [diff] [blame] | 166 | for (const auto &PredValue : PredValues) |
| 167 | InsertedPHI->addIncoming(PredValue.second, PredValue.first); |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 168 | |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 169 | // 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 Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 171 | if (Value *V = |
| 172 | SimplifyInstruction(InsertedPHI, BB->getModule()->getDataLayout())) { |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 173 | InsertedPHI->eraseFromParent(); |
Duncan Sands | 6370495 | 2010-11-16 17:41:24 +0000 | [diff] [blame] | 174 | return V; |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 175 | } |
Chris Lattner | 249265d | 2009-10-10 23:15:24 +0000 | [diff] [blame] | 176 | |
Eli Bendersky | f0ad360 | 2012-06-25 10:13:14 +0000 | [diff] [blame] | 177 | // 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 Patel | a8e7411 | 2011-04-29 22:28:59 +0000 | [diff] [blame] | 182 | |
Chris Lattner | 249265d | 2009-10-10 23:15:24 +0000 | [diff] [blame] | 183 | // If the client wants to know about all new instructions, tell it. |
| 184 | if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 185 | |
Nicola Zaghen | d34e60c | 2018-05-14 12:53:11 +0000 | [diff] [blame] | 186 | LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); |
Chris Lattner | 67cdd8b | 2009-10-10 23:00:11 +0000 | [diff] [blame] | 187 | return InsertedPHI; |
| 188 | } |
| 189 | |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 190 | void SSAUpdater::RewriteUse(Use &U) { |
| 191 | Instruction *User = cast<Instruction>(U.getUser()); |
Bob Wilson | ca51425 | 2010-04-17 03:08:24 +0000 | [diff] [blame] | 192 | |
Chris Lattner | 7f90368 | 2009-10-20 20:27:49 +0000 | [diff] [blame] | 193 | Value *V; |
| 194 | if (PHINode *UserPN = dyn_cast<PHINode>(User)) |
| 195 | V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); |
| 196 | else |
| 197 | V = GetValueInMiddleOfBlock(User->getParent()); |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 198 | |
Nadav Rotem | 8d80452 | 2012-08-13 23:06:54 +0000 | [diff] [blame] | 199 | // 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 Edwin | cf10ec9 | 2009-10-20 15:42:00 +0000 | [diff] [blame] | 204 | U.set(V); |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 205 | } |
| 206 | |
Chris Lattner | c3fb03e | 2010-08-29 04:54:06 +0000 | [diff] [blame] | 207 | void SSAUpdater::RewriteUseAfterInsertions(Use &U) { |
| 208 | Instruction *User = cast<Instruction>(U.getUser()); |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 209 | |
Chris Lattner | c3fb03e | 2010-08-29 04:54:06 +0000 | [diff] [blame] | 210 | Value *V; |
| 211 | if (PHINode *UserPN = dyn_cast<PHINode>(User)) |
| 212 | V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); |
| 213 | else |
| 214 | V = GetValueAtEndOfBlock(User->getParent()); |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 215 | |
Chris Lattner | c3fb03e | 2010-08-29 04:54:06 +0000 | [diff] [blame] | 216 | U.set(V); |
| 217 | } |
| 218 | |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 219 | namespace llvm { |
Eugene Zelenko | 34c2327 | 2017-01-18 00:57:48 +0000 | [diff] [blame] | 220 | |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 221 | template<> |
| 222 | class SSAUpdaterTraits<SSAUpdater> { |
| 223 | public: |
Eugene Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 224 | using BlkT = BasicBlock; |
| 225 | using ValT = Value *; |
| 226 | using PhiT = PHINode; |
| 227 | using BlkSucc_iterator = succ_iterator; |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 228 | |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 229 | 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 Carruth | c60fbe6 | 2012-06-20 08:39:30 +0000 | [diff] [blame] | 232 | 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 Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 243 | PHI_iterator &operator++() { ++idx; return *this; } |
Chandler Carruth | c60fbe6 | 2012-06-20 08:39:30 +0000 | [diff] [blame] | 244 | bool operator==(const PHI_iterator& x) const { return idx == x.idx; } |
| 245 | bool operator!=(const PHI_iterator& x) const { return !operator==(x); } |
Eugene Zelenko | 34c2327 | 2017-01-18 00:57:48 +0000 | [diff] [blame] | 246 | |
Chandler Carruth | c60fbe6 | 2012-06-20 08:39:30 +0000 | [diff] [blame] | 247 | 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 Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 253 | 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 Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 259 | SmallVectorImpl<BasicBlock *> *Preds) { |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 260 | // 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 Kramer | dfedfeb | 2015-02-19 20:04:02 +0000 | [diff] [blame] | 264 | Preds->append(SomePhi->block_begin(), SomePhi->block_end()); |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 265 | } else { |
Duncan P. N. Exon Smith | 6c99015 | 2014-07-21 17:06:51 +0000 | [diff] [blame] | 266 | for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) |
| 267 | Preds->push_back(*PI); |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 268 | } |
| 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 Sands | 6778149 | 2010-09-02 08:14:03 +0000 | [diff] [blame] | 274 | return UndefValue::get(Updater->ProtoType); |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 275 | } |
| 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 Foad | 5213134 | 2011-03-30 11:28:46 +0000 | [diff] [blame] | 281 | PHINode *PHI = PHINode::Create(Updater->ProtoType, NumPreds, |
| 282 | Updater->ProtoName, &BB->front()); |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 283 | 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 Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 299 | 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 Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 309 | return nullptr; |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 310 | } |
| 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 Zelenko | 34c2327 | 2017-01-18 00:57:48 +0000 | [diff] [blame] | 319 | } // end namespace llvm |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 320 | |
Chandler Carruth | 6b55dbe | 2013-07-28 22:00:33 +0000 | [diff] [blame] | 321 | /// 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 Lattner | e474a8d | 2009-10-10 22:41:58 +0000 | [diff] [blame] | 324 | Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 325 | AvailableValsTy &AvailableVals = getAvailableVals(AV); |
Bob Wilson | ca51425 | 2010-04-17 03:08:24 +0000 | [diff] [blame] | 326 | if (Value *V = AvailableVals[BB]) |
| 327 | return V; |
Duncan Sands | 0058c7b | 2009-10-16 15:20:13 +0000 | [diff] [blame] | 328 | |
Bob Wilson | d1b38e3 | 2010-05-04 23:18:19 +0000 | [diff] [blame] | 329 | SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); |
| 330 | return Impl.GetValue(BB); |
Chris Lattner | 60d4e69 | 2009-10-10 09:04:27 +0000 | [diff] [blame] | 331 | } |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 332 | |
| 333 | //===----------------------------------------------------------------------===// |
| 334 | // LoadAndStorePromoter Implementation |
| 335 | //===----------------------------------------------------------------------===// |
| 336 | |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 337 | LoadAndStorePromoter:: |
Eugene Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 338 | LoadAndStorePromoter(ArrayRef<const Instruction *> Insts, |
Devang Patel | a3cbf52 | 2011-07-06 21:09:55 +0000 | [diff] [blame] | 339 | SSAUpdater &S, StringRef BaseName) : SSA(S) { |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 340 | if (Insts.empty()) return; |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 341 | |
Pete Cooper | 41e0ee3 | 2015-05-13 01:12:16 +0000 | [diff] [blame] | 342 | const Value *SomeVal; |
| 343 | if (const LoadInst *LI = dyn_cast<LoadInst>(Insts[0])) |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 344 | SomeVal = LI; |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 345 | else |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 346 | 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 Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 353 | void LoadAndStorePromoter:: |
Eugene Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 354 | run(const SmallVectorImpl<Instruction *> &Insts) const { |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 355 | // 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 Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 358 | DenseMap<BasicBlock *, TinyPtrVector<Instruction *>> UsesByBlock; |
Benjamin Kramer | dfedfeb | 2015-02-19 20:04:02 +0000 | [diff] [blame] | 359 | |
| 360 | for (Instruction *User : Insts) |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 361 | UsesByBlock[User->getParent()].push_back(User); |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 362 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 363 | // 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 Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 366 | SmallVector<LoadInst *, 32> LiveInLoads; |
| 367 | DenseMap<Value *, Value *> ReplacedLoads; |
Benjamin Kramer | dfedfeb | 2015-02-19 20:04:02 +0000 | [diff] [blame] | 368 | |
| 369 | for (Instruction *User : Insts) { |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 370 | BasicBlock *BB = User->getParent(); |
Eugene Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 371 | TinyPtrVector<Instruction *> &BlockUses = UsesByBlock[BB]; |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 372 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 373 | // If this block has already been processed, ignore this repeat use. |
| 374 | if (BlockUses.empty()) continue; |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 375 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 376 | // 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 Zwarich | 843bc7d | 2011-05-24 03:10:43 +0000 | [diff] [blame] | 380 | if (StoreInst *SI = dyn_cast<StoreInst>(User)) { |
Devang Patel | a3cbf52 | 2011-07-06 21:09:55 +0000 | [diff] [blame] | 381 | updateDebugInfo(SI); |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 382 | SSA.AddAvailableValue(BB, SI->getOperand(0)); |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 383 | } else |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 384 | // 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 Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 389 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 390 | // Otherwise, check to see if this block is all loads. |
| 391 | bool HasStore = false; |
Benjamin Kramer | dfedfeb | 2015-02-19 20:04:02 +0000 | [diff] [blame] | 392 | for (Instruction *I : BlockUses) { |
| 393 | if (isa<StoreInst>(I)) { |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 394 | HasStore = true; |
| 395 | break; |
| 396 | } |
| 397 | } |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 398 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 399 | // 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 Kramer | dfedfeb | 2015-02-19 20:04:02 +0000 | [diff] [blame] | 403 | for (Instruction *I : BlockUses) |
| 404 | LiveInLoads.push_back(cast<LoadInst>(I)); |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 405 | BlockUses.clear(); |
| 406 | continue; |
| 407 | } |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 408 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 409 | // 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 Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 414 | Value *StoredValue = nullptr; |
Benjamin Kramer | dfedfeb | 2015-02-19 20:04:02 +0000 | [diff] [blame] | 415 | for (Instruction &I : *BB) { |
| 416 | if (LoadInst *L = dyn_cast<LoadInst>(&I)) { |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 417 | // If this is a load from an unrelated pointer, ignore it. |
| 418 | if (!isInstInList(L, Insts)) continue; |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 419 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 420 | // If we haven't seen a store yet, this is a live in use, otherwise |
| 421 | // use the stored value. |
| 422 | if (StoredValue) { |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 423 | replaceLoadWithValue(L, StoredValue); |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 424 | L->replaceAllUsesWith(StoredValue); |
| 425 | ReplacedLoads[L] = StoredValue; |
| 426 | } else { |
| 427 | LiveInLoads.push_back(L); |
| 428 | } |
| 429 | continue; |
| 430 | } |
Benjamin Kramer | dfedfeb | 2015-02-19 20:04:02 +0000 | [diff] [blame] | 431 | |
| 432 | if (StoreInst *SI = dyn_cast<StoreInst>(&I)) { |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 433 | // If this is a store to an unrelated pointer, ignore it. |
Cameron Zwarich | 843bc7d | 2011-05-24 03:10:43 +0000 | [diff] [blame] | 434 | if (!isInstInList(SI, Insts)) continue; |
Devang Patel | a3cbf52 | 2011-07-06 21:09:55 +0000 | [diff] [blame] | 435 | updateDebugInfo(SI); |
Cameron Zwarich | 843bc7d | 2011-05-24 03:10:43 +0000 | [diff] [blame] | 436 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 437 | // Remember that this is the active value in the block. |
Cameron Zwarich | 843bc7d | 2011-05-24 03:10:43 +0000 | [diff] [blame] | 438 | StoredValue = SI->getOperand(0); |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 439 | } |
| 440 | } |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 441 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 442 | // 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 Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 444 | SSA.AddAvailableValue(BB, StoredValue); |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 445 | BlockUses.clear(); |
| 446 | } |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 447 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 448 | // Okay, now we rewrite all loads that use live-in values in the loop, |
| 449 | // inserting PHI nodes as necessary. |
Benjamin Kramer | dfedfeb | 2015-02-19 20:04:02 +0000 | [diff] [blame] | 450 | for (LoadInst *ALoad : LiveInLoads) { |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 451 | Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent()); |
| 452 | replaceLoadWithValue(ALoad, NewVal); |
Chris Lattner | b401776 | 2011-01-24 03:29:07 +0000 | [diff] [blame] | 453 | |
| 454 | // Avoid assertions in unreachable code. |
| 455 | if (NewVal == ALoad) NewVal = UndefValue::get(NewVal->getType()); |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 456 | ALoad->replaceAllUsesWith(NewVal); |
| 457 | ReplacedLoads[ALoad] = NewVal; |
| 458 | } |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 459 | |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 460 | // Allow the client to do stuff before we start nuking things. |
| 461 | doExtraRewritesBeforeFinalDeletion(); |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 462 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 463 | // Now that everything is rewritten, delete the old instructions from the |
| 464 | // function. They should all be dead now. |
Benjamin Kramer | dfedfeb | 2015-02-19 20:04:02 +0000 | [diff] [blame] | 465 | for (Instruction *User : Insts) { |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 466 | // 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 Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 473 | |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 474 | // 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 Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 482 | |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 483 | replaceLoadWithValue(cast<LoadInst>(User), NewVal); |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 484 | User->replaceAllUsesWith(NewVal); |
| 485 | } |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 486 | |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 487 | instructionDeleted(User); |
Chris Lattner | 95294b8 | 2011-01-14 19:36:13 +0000 | [diff] [blame] | 488 | User->eraseFromParent(); |
| 489 | } |
| 490 | } |
Benjamin Kramer | d00e94e | 2011-11-14 17:22:45 +0000 | [diff] [blame] | 491 | |
| 492 | bool |
| 493 | LoadAndStorePromoter::isInstInList(Instruction *I, |
Eugene Zelenko | 286d589 | 2017-10-11 21:41:43 +0000 | [diff] [blame] | 494 | const SmallVectorImpl<Instruction *> &Insts) |
Benjamin Kramer | d00e94e | 2011-11-14 17:22:45 +0000 | [diff] [blame] | 495 | const { |
David Majnemer | 0d955d0 | 2016-08-11 22:21:41 +0000 | [diff] [blame] | 496 | return is_contained(Insts, I); |
Benjamin Kramer | d00e94e | 2011-11-14 17:22:45 +0000 | [diff] [blame] | 497 | } |