SSAUpdater.cpp revision 49c283fd3f8f81e04b84dc848981b4bf17b2d706
193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===// 293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// The LLVM Compiler Infrastructure 493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// This file is distributed under the University of Illinois Open Source 693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// License. See LICENSE.TXT for details. 793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===----------------------------------------------------------------------===// 993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 1093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// This file implements the SSAUpdater class. 1193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 1293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===----------------------------------------------------------------------===// 1393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 1493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Transforms/Utils/SSAUpdater.h" 1593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Instructions.h" 1693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/ADT/DenseMap.h" 1793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Support/CFG.h" 1893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Support/Debug.h" 1949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson#include "llvm/Support/ValueHandle.h" 2093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Support/raw_ostream.h" 2193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerusing namespace llvm; 2293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 2349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilsontypedef DenseMap<BasicBlock*, TrackingVH<Value> > AvailableValsTy; 2449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilsontypedef std::vector<std::pair<BasicBlock*, TrackingVH<Value> > > 2549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfoTy; 2693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 2793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerstatic AvailableValsTy &getAvailableVals(void *AV) { 2893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return *static_cast<AvailableValsTy*>(AV); 2993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 3093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 3149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilsonstatic IncomingPredInfoTy &getIncomingPredInfo(void *IPI) { 3249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return *static_cast<IncomingPredInfoTy*>(IPI); 3393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 3493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 3593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 36f5a1fb6b247611b92d9dec9476202b477661dbe8Chris LattnerSSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) 3749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson : AV(0), PrototypeValue(0), IPI(0), InsertedPHIs(NewPHI) {} 3893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 3993f3bcf7f323069e40d9abb950da73d437b6f7daChris LattnerSSAUpdater::~SSAUpdater() { 4093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner delete &getAvailableVals(AV); 4149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson delete &getIncomingPredInfo(IPI); 4293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 4393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 4493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// Initialize - Reset this object to get ready for a new set of SSA 4593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// updates. ProtoValue is the value used to name PHI nodes. 4693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnervoid SSAUpdater::Initialize(Value *ProtoValue) { 4793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (AV == 0) 4893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner AV = new AvailableValsTy(); 4993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner else 5093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner getAvailableVals(AV).clear(); 5149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 5249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (IPI == 0) 5349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IPI = new IncomingPredInfoTy(); 5449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson else 5549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson getIncomingPredInfo(IPI).clear(); 5693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner PrototypeValue = ProtoValue; 5793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 5893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 590bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner/// HasValueForBlock - Return true if the SSAUpdater already has a value for 600bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner/// the specified block. 610bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattnerbool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { 620bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner return getAvailableVals(AV).count(BB); 630bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner} 640bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner 6593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// AddAvailableValue - Indicate that a rewritten value is available in the 6693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// specified block with the specified value. 6793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnervoid SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { 6893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner assert(PrototypeValue != 0 && "Need to initialize SSAUpdater"); 6993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner assert(PrototypeValue->getType() == V->getType() && 7093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner "All rewritten values must have the same type"); 7193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner getAvailableVals(AV)[BB] = V; 7293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 7393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 74e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson/// IsEquivalentPHI - Check if PHI has the same incoming value as specified 75e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson/// in ValueMapping for each predecessor block. 7649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilsonstatic bool IsEquivalentPHI(PHINode *PHI, 77e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson DenseMap<BasicBlock*, Value*> &ValueMapping) { 78e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson unsigned PHINumValues = PHI->getNumIncomingValues(); 79e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson if (PHINumValues != ValueMapping.size()) 80e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson return false; 81e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson 82e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson // Scan the phi to see if it matches. 83e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson for (unsigned i = 0, e = PHINumValues; i != e; ++i) 84e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson if (ValueMapping[PHI->getIncomingBlock(i)] != 85e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson PHI->getIncomingValue(i)) { 86e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson return false; 87e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson } 88e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson 89e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson return true; 90e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson} 91e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson 9249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson/// GetExistingPHI - Check if BB already contains a phi node that is equivalent 9349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson/// to the specified mapping from predecessor blocks to incoming values. 9449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilsonstatic Value *GetExistingPHI(BasicBlock *BB, 9549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson DenseMap<BasicBlock*, Value*> &ValueMapping) { 9649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson PHINode *SomePHI; 9749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson for (BasicBlock::iterator It = BB->begin(); 9849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson (SomePHI = dyn_cast<PHINode>(It)); ++It) { 9949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (IsEquivalentPHI(SomePHI, ValueMapping)) 10049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return SomePHI; 10149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson } 10249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return 0; 10349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson} 10449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 10549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson/// GetExistingPHI - Check if BB already contains an equivalent phi node. 10649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson/// The InputIt type must be an iterator over std::pair<BasicBlock*, Value*> 10749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson/// objects that specify the mapping from predecessor blocks to incoming values. 10849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilsontemplate<typename InputIt> 10949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilsonstatic Value *GetExistingPHI(BasicBlock *BB, const InputIt &I, 11049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson const InputIt &E) { 11149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Avoid create the mapping if BB has no phi nodes at all. 11249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (!isa<PHINode>(BB->begin())) 11349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return 0; 11449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson DenseMap<BasicBlock*, Value*> ValueMapping(I, E); 11549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return GetExistingPHI(BB, ValueMapping); 11649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson} 11749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 1181a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 1191a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// live at the end of the specified block. 1205fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris LattnerValue *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { 12149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); 1225fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner Value *Res = GetValueAtEndOfBlockInternal(BB); 12349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); 12493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return Res; 12593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 12693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 1271a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 1281a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// is live in the middle of the specified block. 1291a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 1301a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 1311a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// important case: if there is a definition of the rewritten value after the 1321a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 'use' in BB. Consider code like this: 1331a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 1341a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// X1 = ... 1351a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// SomeBB: 1361a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// use(X) 1371a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// X2 = ... 1381a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// br Cond, SomeBB, OutBB 1391a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 1401a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// In this case, there are two values (X1 and X2) added to the AvailableVals 1411a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// set by the client of the rewriter, and those values are both live out of 1421a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// their respective blocks. However, the use of X happens in the *middle* of 1431a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// a block. Because of this, we need to insert a new PHI node in SomeBB to 1441a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// merge the appropriate values, and this value isn't live out of the block. 1451a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 1461a8d4de397c360a76f1389d15e862eba265d71fdChris LattnerValue *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { 1471a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // If there is no definition of the renamed variable in this block, just use 1481a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // GetValueAtEndOfBlock to do our work. 14949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (!getAvailableVals(AV).count(BB)) 1501a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return GetValueAtEndOfBlock(BB); 151ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1521a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Otherwise, we have the hard case. Get the live-in values for each 1531a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // predecessor. 1541a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues; 1551a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *SingularValue = 0; 156ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1571a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // We can get our predecessor info by walking the pred_iterator list, but it 1581a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // is relatively slow. If we already have PHI nodes in this block, walk one 1591a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // of them to get the predecessor list instead. 1601a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 1611a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 1621a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 1631a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *PredVal = GetValueAtEndOfBlock(PredBB); 1641a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PredValues.push_back(std::make_pair(PredBB, PredVal)); 165ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1661a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Compute SingularValue. 1671a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (i == 0) 1681a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = PredVal; 1691a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner else if (PredVal != SingularValue) 1701a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = 0; 1711a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1721a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } else { 1731a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner bool isFirstPred = true; 1741a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 1751a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner BasicBlock *PredBB = *PI; 1761a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *PredVal = GetValueAtEndOfBlock(PredBB); 1771a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PredValues.push_back(std::make_pair(PredBB, PredVal)); 178ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1791a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Compute SingularValue. 1801a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (isFirstPred) { 1811a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = PredVal; 1821a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner isFirstPred = false; 1831a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } else if (PredVal != SingularValue) 1841a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = 0; 1851a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1861a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 187ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1881a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // If there are no predecessors, just return undef. 1891a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (PredValues.empty()) 1901a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return UndefValue::get(PrototypeValue->getType()); 191ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1921a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Otherwise, if all the merged values are the same, just use it. 1931a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (SingularValue != 0) 1941a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return SingularValue; 195ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 19649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Otherwise, we do need a PHI. 19749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (Value *ExistingPHI = GetExistingPHI(BB, PredValues.begin(), 19849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson PredValues.end())) 19949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return ExistingPHI; 200e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson 2014c1e3da0cdd2fd0df5188dea1988beb8bf6a0dc6Chris Lattner // Ok, we have no way out, insert a new one now. 2021a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(), 2031a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PrototypeValue->getName(), 2041a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner &BB->front()); 2051a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner InsertedPHI->reserveOperandSpace(PredValues.size()); 206ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 2071a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Fill in all the predecessors of the PHI. 2081a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 2091a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first); 210ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 2111a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // See if the PHI node can be merged to a single value. This can happen in 2121a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // loop cases when we get a PHI of itself and one other value. 2131a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (Value *ConstVal = InsertedPHI->hasConstantValue()) { 2141a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner InsertedPHI->eraseFromParent(); 2151a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return ConstVal; 2161a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 217f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner 218f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner // If the client wants to know about all new instructions, tell it. 219f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 220ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 2211af40cacd4d162ffe9dfbafa1230e502e059be65David Greene DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 2221a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return InsertedPHI; 2231a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner} 2241a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 22593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 22693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// which use their value in the corresponding predecessor. 22793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnervoid SSAUpdater::RewriteUse(Use &U) { 22893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner Instruction *User = cast<Instruction>(U.getUser()); 22949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 23088a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner Value *V; 23188a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner if (PHINode *UserPN = dyn_cast<PHINode>(User)) 23288a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 23388a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner else 23488a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner V = GetValueInMiddleOfBlock(User->getParent()); 235ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 236f993327e71d826dcb852929a78881569ef83374dTorok Edwin U.set(V); 23793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 23893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 23949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 2405fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry 2415fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner/// for the specified BB and if so, return it. If not, construct SSA form by 24249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson/// walking predecessors inserting PHI nodes as needed until we get to a block 24349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson/// where the value is available. 24449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson/// 2455fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris LattnerValue *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { 24693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner AvailableValsTy &AvailableVals = getAvailableVals(AV); 247ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 24849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Query AvailableVals by doing an insertion of null. 24949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson std::pair<AvailableValsTy::iterator, bool> InsertRes = 25049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson AvailableVals.insert(std::make_pair(BB, TrackingVH<Value>())); 25149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 25249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Handle the case when the insertion fails because we have already seen BB. 25349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (!InsertRes.second) { 25449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // If the insertion failed, there are two cases. The first case is that the 25549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // value is already available for the specified block. If we get this, just 25649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // return the value. 25749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (InsertRes.first->second != 0) 25849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return InsertRes.first->second; 25949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 26049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Otherwise, if the value we find is null, then this is the value is not 26149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // known but it is being computed elsewhere in our recursion. This means 26249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // that we have a cycle. Handle this by inserting a PHI node and returning 26349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // it. When we get back to the first instance of the recursion we will fill 26449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // in the PHI node. 26549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return InsertRes.first->second = 26649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson PHINode::Create(PrototypeValue->getType(), PrototypeValue->getName(), 26749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson &BB->front()); 26893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } 269ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 27049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Okay, the value isn't in the map and we just inserted a null in the entry 27149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // to indicate that we're processing the block. Since we have no idea what 27249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // value is in this block, we have to recurse through our predecessors. 27349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // 27449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // While we're walking our predecessors, we keep track of them in a vector, 27549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // then insert a PHI node in the end if we actually need one. We could use a 27649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // smallvector here, but that would take a lot of stack space for every level 27749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // of the recursion, just use IncomingPredInfo as an explicit stack. 27849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI); 27949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson unsigned FirstPredInfoEntry = IncomingPredInfo.size(); 28049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 28149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // As we're walking the predecessors, keep track of whether they are all 28249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // producing the same value. If so, this value will capture it, if not, it 28349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // will get reset to null. We distinguish the no-predecessor case explicitly 28449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // below. 28549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson TrackingVH<Value> ExistingValue; 28649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 28749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // We can get our predecessor info by walking the pred_iterator list, but it 28849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // is relatively slow. If we already have PHI nodes in this block, walk one 28949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // of them to get the predecessor list instead. 29049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 29149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 29249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 29349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson Value *PredVal = GetValueAtEndOfBlockInternal(PredBB); 29449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); 29549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 29649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Set ExistingValue to singular value from all predecessors so far. 29749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (i == 0) 29849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson ExistingValue = PredVal; 29949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson else if (PredVal != ExistingValue) 30049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson ExistingValue = 0; 30193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } 30249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson } else { 30349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson bool isFirstPred = true; 30449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 30549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson BasicBlock *PredBB = *PI; 30649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson Value *PredVal = GetValueAtEndOfBlockInternal(PredBB); 30749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); 308a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson 30949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Set ExistingValue to singular value from all predecessors so far. 31049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (isFirstPred) { 31149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson ExistingValue = PredVal; 31249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson isFirstPred = false; 31349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson } else if (PredVal != ExistingValue) 31449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson ExistingValue = 0; 31549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson } 316a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson } 317a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson 31849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // If there are no predecessors, then we must have found an unreachable block 31949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // just return 'undef'. Since there are no predecessors, InsertRes must not 32049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // be invalidated. 32149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (IncomingPredInfo.size() == FirstPredInfoEntry) 32249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return InsertRes.first->second = UndefValue::get(PrototypeValue->getType()); 32349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 32449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If 32549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson /// this block is involved in a loop, a no-entry PHI node will have been 32649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson /// inserted as InsertedVal. Otherwise, we'll still have the null we inserted 32749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson /// above. 32849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson TrackingVH<Value> &InsertedVal = AvailableVals[BB]; 32949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 33049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // If the predecessor values are not all the same, then check to see if there 33149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // is an existing PHI that can be used. 33249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (!ExistingValue) 33349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson ExistingValue = GetExistingPHI(BB, 33449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfo.begin()+FirstPredInfoEntry, 33549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfo.end()); 33649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 33749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // If there is an existing value we can use, then we don't need to insert a 33849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // PHI. This is the simple and common case. 33949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (ExistingValue) { 34049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // If a PHI node got inserted, replace it with the existing value and delete 34149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // it. 34249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (InsertedVal) { 34349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson PHINode *OldVal = cast<PHINode>(InsertedVal); 34449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Be careful about dead loops. These RAUW's also update InsertedVal. 34549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (InsertedVal != ExistingValue) 34649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson OldVal->replaceAllUsesWith(ExistingValue); 34749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson else 34849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson OldVal->replaceAllUsesWith(UndefValue::get(InsertedVal->getType())); 34949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson OldVal->eraseFromParent(); 35049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson } else { 35149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson InsertedVal = ExistingValue; 35249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson } 353ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 35449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Either path through the 'if' should have set InsertedVal -> ExistingVal. 35549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson assert((InsertedVal == ExistingValue || isa<UndefValue>(InsertedVal)) && 35649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson "RAUW didn't change InsertedVal to be ExistingValue"); 357a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson 35849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Drop the entries we added in IncomingPredInfo to restore the stack. 35949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, 36049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfo.end()); 36149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return ExistingValue; 362a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson } 363ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 36449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Otherwise, we do need a PHI: insert one now if we don't already have one. 36549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (InsertedVal == 0) 36649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson InsertedVal = PHINode::Create(PrototypeValue->getType(), 36749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson PrototypeValue->getName(), &BB->front()); 3687272b9200989be868f784210fb27f1935cc38036Bob Wilson 36949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson PHINode *InsertedPHI = cast<PHINode>(InsertedVal); 37049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson InsertedPHI->reserveOperandSpace(IncomingPredInfo.size()-FirstPredInfoEntry); 37145305d4ff6bff8dfe62228c68b3cb61bb2d7254fChris Lattner 37249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Fill in all the predecessors of the PHI. 37349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson for (IncomingPredInfoTy::iterator I = 37449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfo.begin()+FirstPredInfoEntry, 37549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson E = IncomingPredInfo.end(); I != E; ++I) 37649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson InsertedPHI->addIncoming(I->second, I->first); 377ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 37849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // Drop the entries we added in IncomingPredInfo to restore the stack. 37949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, 38049c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson IncomingPredInfo.end()); 381ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 38249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // See if the PHI node can be merged to a single value. This can happen in 38349c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // loop cases when we get a PHI of itself and one other value. 38449c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (Value *ConstVal = InsertedPHI->hasConstantValue()) { 38549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson InsertedPHI->replaceAllUsesWith(ConstVal); 38649c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson InsertedPHI->eraseFromParent(); 38749c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson InsertedVal = ConstVal; 38849c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson } else { 38949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 390ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 39149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson // If the client wants to know about all new instructions, tell it. 39249c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 39393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } 394ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 39549c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson return InsertedVal; 39693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 397