SSAUpdater.cpp revision 4aad88d1fd88413029dd05255306b07cb19396ee
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 1484bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson#define DEBUG_TYPE "ssaupdater" 1593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Instructions.h" 1693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/ADT/DenseMap.h" 1784bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson#include "llvm/Support/AlignOf.h" 1884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson#include "llvm/Support/Allocator.h" 1993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Support/CFG.h" 2093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Support/Debug.h" 2193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Support/raw_ostream.h" 224aad88d1fd88413029dd05255306b07cb19396eeBob Wilson#include "llvm/Transforms/Utils/SSAUpdater.h" 234aad88d1fd88413029dd05255306b07cb19396eeBob Wilson#include "llvm/Transforms/Utils/SSAUpdaterImpl.h" 2493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerusing namespace llvm; 2593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 2684bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilsontypedef DenseMap<BasicBlock*, Value*> AvailableValsTy; 2793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerstatic AvailableValsTy &getAvailableVals(void *AV) { 2893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return *static_cast<AvailableValsTy*>(AV); 2993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 3093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 31f5a1fb6b247611b92d9dec9476202b477661dbe8Chris LattnerSSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) 324aad88d1fd88413029dd05255306b07cb19396eeBob Wilson : AV(0), PrototypeValue(0), InsertedPHIs(NewPHI) {} 3393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 3493f3bcf7f323069e40d9abb950da73d437b6f7daChris LattnerSSAUpdater::~SSAUpdater() { 3593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner delete &getAvailableVals(AV); 3693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 3793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 3893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// Initialize - Reset this object to get ready for a new set of SSA 3993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// updates. ProtoValue is the value used to name PHI nodes. 4093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnervoid SSAUpdater::Initialize(Value *ProtoValue) { 4193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (AV == 0) 4293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner AV = new AvailableValsTy(); 4393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner else 4493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner getAvailableVals(AV).clear(); 4593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner PrototypeValue = ProtoValue; 4693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 4793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 480bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner/// HasValueForBlock - Return true if the SSAUpdater already has a value for 490bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner/// the specified block. 500bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattnerbool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { 510bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner return getAvailableVals(AV).count(BB); 520bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner} 530bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner 5493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// AddAvailableValue - Indicate that a rewritten value is available in the 5593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// specified block with the specified value. 5693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnervoid SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { 5793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner assert(PrototypeValue != 0 && "Need to initialize SSAUpdater"); 5893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner assert(PrototypeValue->getType() == V->getType() && 5993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner "All rewritten values must have the same type"); 6093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner getAvailableVals(AV)[BB] = V; 6193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 6293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 63e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson/// IsEquivalentPHI - Check if PHI has the same incoming value as specified 64e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson/// in ValueMapping for each predecessor block. 6584bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilsonstatic bool IsEquivalentPHI(PHINode *PHI, 66e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson DenseMap<BasicBlock*, Value*> &ValueMapping) { 67e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson unsigned PHINumValues = PHI->getNumIncomingValues(); 68e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson if (PHINumValues != ValueMapping.size()) 69e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson return false; 70e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson 71e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson // Scan the phi to see if it matches. 72e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson for (unsigned i = 0, e = PHINumValues; i != e; ++i) 73e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson if (ValueMapping[PHI->getIncomingBlock(i)] != 74e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson PHI->getIncomingValue(i)) { 75e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson return false; 76e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson } 77e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson 78e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson return true; 79e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson} 80e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson 811a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 821a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// live at the end of the specified block. 835fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris LattnerValue *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { 845fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner Value *Res = GetValueAtEndOfBlockInternal(BB); 8593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return Res; 8693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 8793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 881a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 891a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// is live in the middle of the specified block. 901a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 911a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 921a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// important case: if there is a definition of the rewritten value after the 931a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 'use' in BB. Consider code like this: 941a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 951a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// X1 = ... 961a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// SomeBB: 971a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// use(X) 981a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// X2 = ... 991a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// br Cond, SomeBB, OutBB 1001a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 1011a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// In this case, there are two values (X1 and X2) added to the AvailableVals 1021a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// set by the client of the rewriter, and those values are both live out of 1031a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// their respective blocks. However, the use of X happens in the *middle* of 1041a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// a block. Because of this, we need to insert a new PHI node in SomeBB to 1051a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// merge the appropriate values, and this value isn't live out of the block. 1061a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 1071a8d4de397c360a76f1389d15e862eba265d71fdChris LattnerValue *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { 1081a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // If there is no definition of the renamed variable in this block, just use 1091a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // GetValueAtEndOfBlock to do our work. 11084bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson if (!HasValueForBlock(BB)) 1111a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return GetValueAtEndOfBlock(BB); 112ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1131a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Otherwise, we have the hard case. Get the live-in values for each 1141a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // predecessor. 1151a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues; 1161a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *SingularValue = 0; 117ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1181a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // We can get our predecessor info by walking the pred_iterator list, but it 1191a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // is relatively slow. If we already have PHI nodes in this block, walk one 1201a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // of them to get the predecessor list instead. 1211a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 1221a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 1231a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 1241a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *PredVal = GetValueAtEndOfBlock(PredBB); 1251a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PredValues.push_back(std::make_pair(PredBB, PredVal)); 126ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1271a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Compute SingularValue. 1281a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (i == 0) 1291a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = PredVal; 1301a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner else if (PredVal != SingularValue) 1311a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = 0; 1321a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1331a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } else { 1341a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner bool isFirstPred = true; 1351a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 1361a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner BasicBlock *PredBB = *PI; 1371a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *PredVal = GetValueAtEndOfBlock(PredBB); 1381a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PredValues.push_back(std::make_pair(PredBB, PredVal)); 139ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1401a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Compute SingularValue. 1411a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (isFirstPred) { 1421a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = PredVal; 1431a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner isFirstPred = false; 1441a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } else if (PredVal != SingularValue) 1451a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = 0; 1461a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1471a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 148ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1491a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // If there are no predecessors, just return undef. 1501a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (PredValues.empty()) 1511a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return UndefValue::get(PrototypeValue->getType()); 152ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1531a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Otherwise, if all the merged values are the same, just use it. 1541a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (SingularValue != 0) 1551a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return SingularValue; 156ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 15784bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson // Otherwise, we do need a PHI: check to see if we already have one available 15884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson // in this block that produces the right value. 15984bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson if (isa<PHINode>(BB->begin())) { 16084bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson DenseMap<BasicBlock*, Value*> ValueMapping(PredValues.begin(), 16184bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson PredValues.end()); 16284bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson PHINode *SomePHI; 16384bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson for (BasicBlock::iterator It = BB->begin(); 16484bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson (SomePHI = dyn_cast<PHINode>(It)); ++It) { 16584bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson if (IsEquivalentPHI(SomePHI, ValueMapping)) 16684bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson return SomePHI; 16784bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 16884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 169e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson 1704c1e3da0cdd2fd0df5188dea1988beb8bf6a0dc6Chris Lattner // Ok, we have no way out, insert a new one now. 1711a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(), 1721a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PrototypeValue->getName(), 1731a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner &BB->front()); 1741a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner InsertedPHI->reserveOperandSpace(PredValues.size()); 175ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1761a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Fill in all the predecessors of the PHI. 1771a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 1781a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first); 179ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1801a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // See if the PHI node can be merged to a single value. This can happen in 1811a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // loop cases when we get a PHI of itself and one other value. 1821a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (Value *ConstVal = InsertedPHI->hasConstantValue()) { 1831a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner InsertedPHI->eraseFromParent(); 1841a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return ConstVal; 1851a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 186f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner 187f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner // If the client wants to know about all new instructions, tell it. 188f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 189ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1901af40cacd4d162ffe9dfbafa1230e502e059be65David Greene DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 1911a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return InsertedPHI; 1921a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner} 1931a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 19493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 19593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// which use their value in the corresponding predecessor. 19693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnervoid SSAUpdater::RewriteUse(Use &U) { 19793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner Instruction *User = cast<Instruction>(U.getUser()); 19884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 19988a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner Value *V; 20088a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner if (PHINode *UserPN = dyn_cast<PHINode>(User)) 20188a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 20288a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner else 20388a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner V = GetValueInMiddleOfBlock(User->getParent()); 204ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 205f993327e71d826dcb852929a78881569ef83374dTorok Edwin U.set(V); 20693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 20793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 2084aad88d1fd88413029dd05255306b07cb19396eeBob Wilson/// PHIiter - Iterator for PHI operands. This is used for the PHI_iterator 2094aad88d1fd88413029dd05255306b07cb19396eeBob Wilson/// in the SSAUpdaterImpl template. 2104aad88d1fd88413029dd05255306b07cb19396eeBob Wilsonnamespace { 2114aad88d1fd88413029dd05255306b07cb19396eeBob Wilson class PHIiter { 2124aad88d1fd88413029dd05255306b07cb19396eeBob Wilson private: 2134aad88d1fd88413029dd05255306b07cb19396eeBob Wilson PHINode *PHI; 2144aad88d1fd88413029dd05255306b07cb19396eeBob Wilson unsigned idx; 2154aad88d1fd88413029dd05255306b07cb19396eeBob Wilson 2164aad88d1fd88413029dd05255306b07cb19396eeBob Wilson public: 2174aad88d1fd88413029dd05255306b07cb19396eeBob Wilson explicit PHIiter(PHINode *P) // begin iterator 2184aad88d1fd88413029dd05255306b07cb19396eeBob Wilson : PHI(P), idx(0) {} 2194aad88d1fd88413029dd05255306b07cb19396eeBob Wilson PHIiter(PHINode *P, bool) // end iterator 2204aad88d1fd88413029dd05255306b07cb19396eeBob Wilson : PHI(P), idx(PHI->getNumIncomingValues()) {} 2214aad88d1fd88413029dd05255306b07cb19396eeBob Wilson 2224aad88d1fd88413029dd05255306b07cb19396eeBob Wilson PHIiter &operator++() { ++idx; return *this; } 2234aad88d1fd88413029dd05255306b07cb19396eeBob Wilson bool operator==(const PHIiter& x) const { return idx == x.idx; } 2244aad88d1fd88413029dd05255306b07cb19396eeBob Wilson bool operator!=(const PHIiter& x) const { return !operator==(x); } 2254aad88d1fd88413029dd05255306b07cb19396eeBob Wilson Value *getIncomingValue() { return PHI->getIncomingValue(idx); } 2264aad88d1fd88413029dd05255306b07cb19396eeBob Wilson BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); } 2274aad88d1fd88413029dd05255306b07cb19396eeBob Wilson }; 22884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson} 22984bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 2304aad88d1fd88413029dd05255306b07cb19396eeBob Wilson/// SSAUpdaterTraits<SSAUpdater> - Traits for the SSAUpdaterImpl template, 2314aad88d1fd88413029dd05255306b07cb19396eeBob Wilson/// specialized for SSAUpdater. 2324aad88d1fd88413029dd05255306b07cb19396eeBob Wilsonnamespace llvm { 2334aad88d1fd88413029dd05255306b07cb19396eeBob Wilsontemplate<> 2344aad88d1fd88413029dd05255306b07cb19396eeBob Wilsonclass SSAUpdaterTraits<SSAUpdater> { 2354aad88d1fd88413029dd05255306b07cb19396eeBob Wilsonpublic: 2364aad88d1fd88413029dd05255306b07cb19396eeBob Wilson typedef BasicBlock BlkT; 2374aad88d1fd88413029dd05255306b07cb19396eeBob Wilson typedef Value *ValT; 2384aad88d1fd88413029dd05255306b07cb19396eeBob Wilson typedef PHINode PhiT; 2394aad88d1fd88413029dd05255306b07cb19396eeBob Wilson 2404aad88d1fd88413029dd05255306b07cb19396eeBob Wilson typedef succ_iterator BlkSucc_iterator; 2414aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); } 2424aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); } 2434aad88d1fd88413029dd05255306b07cb19396eeBob Wilson 2444aad88d1fd88413029dd05255306b07cb19396eeBob Wilson typedef PHIiter PHI_iterator; 2454aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } 2464aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static inline PHI_iterator PHI_end(PhiT *PHI) { 2474aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return PHI_iterator(PHI, true); 24884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 24949c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 2504aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds 2514aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// vector, set Info->NumPreds, and allocate space in Info->Preds. 2524aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static void FindPredecessorBlocks(BasicBlock *BB, 2534aad88d1fd88413029dd05255306b07cb19396eeBob Wilson SmallVectorImpl<BasicBlock*> *Preds) { 2544aad88d1fd88413029dd05255306b07cb19396eeBob Wilson // We can get our predecessor info by walking the pred_iterator list, 2554aad88d1fd88413029dd05255306b07cb19396eeBob Wilson // but it is relatively slow. If we already have PHI nodes in this 2564aad88d1fd88413029dd05255306b07cb19396eeBob Wilson // block, walk one of them to get the predecessor list instead. 2574aad88d1fd88413029dd05255306b07cb19396eeBob Wilson if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 2584aad88d1fd88413029dd05255306b07cb19396eeBob Wilson for (unsigned PI = 0, E = SomePhi->getNumIncomingValues(); PI != E; ++PI) 2594aad88d1fd88413029dd05255306b07cb19396eeBob Wilson Preds->push_back(SomePhi->getIncomingBlock(PI)); 2604aad88d1fd88413029dd05255306b07cb19396eeBob Wilson } else { 2614aad88d1fd88413029dd05255306b07cb19396eeBob Wilson for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 2624aad88d1fd88413029dd05255306b07cb19396eeBob Wilson Preds->push_back(*PI); 26384bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 26484bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 26584bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 2664aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// GetUndefVal - Get an undefined value of the same type as the value 2674aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// being handled. 2684aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) { 2694aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return UndefValue::get(Updater->PrototypeValue->getType()); 27084bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 27184bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 2724aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// CreateEmptyPHI - Create a new PHI instruction in the specified block. 2734aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// Reserve space for the operands but do not fill them in yet. 2744aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds, 2754aad88d1fd88413029dd05255306b07cb19396eeBob Wilson SSAUpdater *Updater) { 2764aad88d1fd88413029dd05255306b07cb19396eeBob Wilson PHINode *PHI = PHINode::Create(Updater->PrototypeValue->getType(), 2774aad88d1fd88413029dd05255306b07cb19396eeBob Wilson Updater->PrototypeValue->getName(), 2784aad88d1fd88413029dd05255306b07cb19396eeBob Wilson &BB->front()); 2794aad88d1fd88413029dd05255306b07cb19396eeBob Wilson PHI->reserveOperandSpace(NumPreds); 2804aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return PHI; 281a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson } 282a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson 2834aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// AddPHIOperand - Add the specified value as an operand of the PHI for 2844aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// the specified predecessor block. 2854aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) { 2864aad88d1fd88413029dd05255306b07cb19396eeBob Wilson PHI->addIncoming(Val, Pred); 28784bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 288ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 2894aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// InstrIsPHI - Check if an instruction is a PHI. 2904aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// 2914aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static PHINode *InstrIsPHI(Instruction *I) { 2924aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return dyn_cast<PHINode>(I); 293a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson } 29445305d4ff6bff8dfe62228c68b3cb61bb2d7254fChris Lattner 2954aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// ValueIsPHI - Check if a value is a PHI. 2964aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// 2974aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) { 2984aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return dyn_cast<PHINode>(Val); 29984bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 300ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 3014aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source 3024aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// operands, i.e., it was just added. 3034aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) { 3044aad88d1fd88413029dd05255306b07cb19396eeBob Wilson PHINode *PHI = ValueIsPHI(Val, Updater); 3054aad88d1fd88413029dd05255306b07cb19396eeBob Wilson if (PHI && PHI->getNumIncomingValues() == 0) 3064aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return PHI; 3074aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return 0; 30884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 30984bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 3104aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// GetPHIValue - For the specified PHI instruction, return the value 3114aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// that it defines. 3124aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static Value *GetPHIValue(PHINode *PHI) { 3134aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return PHI; 31484bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 3154aad88d1fd88413029dd05255306b07cb19396eeBob Wilson}; 31684bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 3174aad88d1fd88413029dd05255306b07cb19396eeBob Wilson} // End llvm namespace 318ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 3194aad88d1fd88413029dd05255306b07cb19396eeBob Wilson/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry 3204aad88d1fd88413029dd05255306b07cb19396eeBob Wilson/// for the specified BB and if so, return it. If not, construct SSA form by 3214aad88d1fd88413029dd05255306b07cb19396eeBob Wilson/// first calculating the required placement of PHIs and then inserting new 3224aad88d1fd88413029dd05255306b07cb19396eeBob Wilson/// PHIs where needed. 3234aad88d1fd88413029dd05255306b07cb19396eeBob WilsonValue *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { 32484bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson AvailableValsTy &AvailableVals = getAvailableVals(AV); 3254aad88d1fd88413029dd05255306b07cb19396eeBob Wilson if (Value *V = AvailableVals[BB]) 3264aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return V; 3274aad88d1fd88413029dd05255306b07cb19396eeBob Wilson 3284aad88d1fd88413029dd05255306b07cb19396eeBob Wilson SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); 3294aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return Impl.GetValue(BB); 33093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 331