SSAUpdater.cpp revision ed90342d8ae0756305219e0f01e03e77599ebb41
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" 1993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Support/ValueHandle.h" 2093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Support/raw_ostream.h" 2193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerusing namespace llvm; 2293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 2393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnertypedef DenseMap<BasicBlock*, TrackingVH<Value> > AvailableValsTy; 2493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnertypedef std::vector<std::pair<BasicBlock*, TrackingVH<Value> > > 2593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner IncomingPredInfoTy; 2693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 2793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerstatic AvailableValsTy &getAvailableVals(void *AV) { 2893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return *static_cast<AvailableValsTy*>(AV); 2993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 3093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 3193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerstatic IncomingPredInfoTy &getIncomingPredInfo(void *IPI) { 3293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return *static_cast<IncomingPredInfoTy*>(IPI); 3393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 3493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 3593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 36f5a1fb6b247611b92d9dec9476202b477661dbe8Chris LattnerSSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) 37f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner : AV(0), PrototypeValue(0), IPI(0), InsertedPHIs(NewPHI) {} 3893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 3993f3bcf7f323069e40d9abb950da73d437b6f7daChris LattnerSSAUpdater::~SSAUpdater() { 4093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner delete &getAvailableVals(AV); 4193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 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(); 51ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 5293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (IPI == 0) 5393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner IPI = new IncomingPredInfoTy(); 5493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner else 5593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 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 741a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 751a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// live at the end of the specified block. 765fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris LattnerValue *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { 7793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); 785fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner Value *Res = GetValueAtEndOfBlockInternal(BB); 7993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner assert(getIncomingPredInfo(IPI).empty() && "Unexpected Internal State"); 8093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return Res; 8193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 8293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 831a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 841a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// is live in the middle of the specified block. 851a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 861a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 871a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// important case: if there is a definition of the rewritten value after the 881a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 'use' in BB. Consider code like this: 891a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 901a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// X1 = ... 911a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// SomeBB: 921a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// use(X) 931a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// X2 = ... 941a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// br Cond, SomeBB, OutBB 951a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 961a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// In this case, there are two values (X1 and X2) added to the AvailableVals 971a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// set by the client of the rewriter, and those values are both live out of 981a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// their respective blocks. However, the use of X happens in the *middle* of 991a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// a block. Because of this, we need to insert a new PHI node in SomeBB to 1001a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// merge the appropriate values, and this value isn't live out of the block. 1011a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner/// 1021a8d4de397c360a76f1389d15e862eba265d71fdChris LattnerValue *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { 1031a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // If there is no definition of the renamed variable in this block, just use 1041a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // GetValueAtEndOfBlock to do our work. 1051a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (!getAvailableVals(AV).count(BB)) 1061a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return GetValueAtEndOfBlock(BB); 107ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1081a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Otherwise, we have the hard case. Get the live-in values for each 1091a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // predecessor. 1101a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues; 1111a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *SingularValue = 0; 112ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1131a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // We can get our predecessor info by walking the pred_iterator list, but it 1141a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // is relatively slow. If we already have PHI nodes in this block, walk one 1151a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // of them to get the predecessor list instead. 1161a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 1171a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 1181a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 1191a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *PredVal = GetValueAtEndOfBlock(PredBB); 1201a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PredValues.push_back(std::make_pair(PredBB, PredVal)); 121ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1221a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Compute SingularValue. 1231a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (i == 0) 1241a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = PredVal; 1251a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner else if (PredVal != SingularValue) 1261a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = 0; 1271a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1281a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } else { 1291a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner bool isFirstPred = true; 1301a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 1311a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner BasicBlock *PredBB = *PI; 1321a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *PredVal = GetValueAtEndOfBlock(PredBB); 1331a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PredValues.push_back(std::make_pair(PredBB, PredVal)); 134ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1351a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Compute SingularValue. 1361a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (isFirstPred) { 1371a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = PredVal; 1381a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner isFirstPred = false; 1391a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } else if (PredVal != SingularValue) 1401a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = 0; 1411a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1421a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 143ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1441a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // If there are no predecessors, just return undef. 1451a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (PredValues.empty()) 1461a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return UndefValue::get(PrototypeValue->getType()); 147ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1481a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Otherwise, if all the merged values are the same, just use it. 1491a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (SingularValue != 0) 1501a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return SingularValue; 151ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1521a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Otherwise, we do need a PHI: insert one now. 1531a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(), 1541a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PrototypeValue->getName(), 1551a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner &BB->front()); 1561a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner InsertedPHI->reserveOperandSpace(PredValues.size()); 157ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1581a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Fill in all the predecessors of the PHI. 1591a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 1601a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first); 161ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1621a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // See if the PHI node can be merged to a single value. This can happen in 1631a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // loop cases when we get a PHI of itself and one other value. 1641a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (Value *ConstVal = InsertedPHI->hasConstantValue()) { 1651a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner InsertedPHI->eraseFromParent(); 1661a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return ConstVal; 1671a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 168f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner 169f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner // If the client wants to know about all new instructions, tell it. 170f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 171ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1721a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner DEBUG(errs() << " Inserted PHI: " << *InsertedPHI << "\n"); 1731a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return InsertedPHI; 1741a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner} 1751a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 17693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 17793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// which use their value in the corresponding predecessor. 17893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnervoid SSAUpdater::RewriteUse(Use &U) { 17993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner Instruction *User = cast<Instruction>(U.getUser()); 18093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner BasicBlock *UseBB = User->getParent(); 18193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (PHINode *UserPN = dyn_cast<PHINode>(User)) 18293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner UseBB = UserPN->getIncomingBlock(U); 183ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1841a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner U.set(GetValueInMiddleOfBlock(UseBB)); 18593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 18693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 18793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 1885fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry 1895fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner/// for the specified BB and if so, return it. If not, construct SSA form by 1905fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner/// walking predecessors inserting PHI nodes as needed until we get to a block 1915fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner/// where the value is available. 19293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// 1935fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris LattnerValue *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { 19493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner AvailableValsTy &AvailableVals = getAvailableVals(AV); 195ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 19693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Query AvailableVals by doing an insertion of null. 19793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner std::pair<AvailableValsTy::iterator, bool> InsertRes = 19893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner AvailableVals.insert(std::make_pair(BB, WeakVH())); 199ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 20093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Handle the case when the insertion fails because we have already seen BB. 20193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (!InsertRes.second) { 20293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // If the insertion failed, there are two cases. The first case is that the 20393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // value is already available for the specified block. If we get this, just 20493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // return the value. 20593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (InsertRes.first->second != 0) 20693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return InsertRes.first->second; 207ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 20893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Otherwise, if the value we find is null, then this is the value is not 20993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // known but it is being computed elsewhere in our recursion. This means 21093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // that we have a cycle. Handle this by inserting a PHI node and returning 21193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // it. When we get back to the first instance of the recursion we will fill 21293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // in the PHI node. 21393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return InsertRes.first->second = 21493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner PHINode::Create(PrototypeValue->getType(), PrototypeValue->getName(), 21593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner &BB->front()); 21693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } 217ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 21893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Okay, the value isn't in the map and we just inserted a null in the entry 21993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // to indicate that we're processing the block. Since we have no idea what 22093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // value is in this block, we have to recurse through our predecessors. 22193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // 22293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // While we're walking our predecessors, we keep track of them in a vector, 22393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // then insert a PHI node in the end if we actually need one. We could use a 22493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // smallvector here, but that would take a lot of stack space for every level 22593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // of the recursion, just use IncomingPredInfo as an explicit stack. 22693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI); 22793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner unsigned FirstPredInfoEntry = IncomingPredInfo.size(); 228ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 22993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // As we're walking the predecessors, keep track of whether they are all 23093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // producing the same value. If so, this value will capture it, if not, it 23193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // will get reset to null. We distinguish the no-predecessor case explicitly 23293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // below. 23393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner TrackingVH<Value> SingularValue; 234ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 23593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // We can get our predecessor info by walking the pred_iterator list, but it 23693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // is relatively slow. If we already have PHI nodes in this block, walk one 23793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // of them to get the predecessor list instead. 23893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 23993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 24093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 2415fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner Value *PredVal = GetValueAtEndOfBlockInternal(PredBB); 24293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); 243ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 24493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Compute SingularValue. 24593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (i == 0) 24693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner SingularValue = PredVal; 24793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner else if (PredVal != SingularValue) 24893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner SingularValue = 0; 24993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } 25093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } else { 25193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner bool isFirstPred = true; 25293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 25393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner BasicBlock *PredBB = *PI; 2545fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner Value *PredVal = GetValueAtEndOfBlockInternal(PredBB); 25593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal)); 256ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 25793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Compute SingularValue. 25893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (isFirstPred) { 25993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner SingularValue = PredVal; 26093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner isFirstPred = false; 26193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } else if (PredVal != SingularValue) 26293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner SingularValue = 0; 26393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } 26493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } 265ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 26693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // If there are no predecessors, then we must have found an unreachable block 26793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // just return 'undef'. Since there are no predecessors, InsertRes must not 26893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // be invalidated. 26993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (IncomingPredInfo.size() == FirstPredInfoEntry) 27093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return InsertRes.first->second = UndefValue::get(PrototypeValue->getType()); 271ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 27293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If 27393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// this block is involved in a loop, a no-entry PHI node will have been 27493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// inserted as InsertedVal. Otherwise, we'll still have the null we inserted 27593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// above. 27693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner TrackingVH<Value> &InsertedVal = AvailableVals[BB]; 277ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 27893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // If all the predecessor values are the same then we don't need to insert a 27993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // PHI. This is the simple and common case. 28093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (SingularValue) { 28193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // If a PHI node got inserted, replace it with the singlar value and delete 28293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // it. 28393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (InsertedVal) { 28493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner PHINode *OldVal = cast<PHINode>(InsertedVal); 28593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Be careful about dead loops. These RAUW's also update InsertedVal. 28693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (InsertedVal != SingularValue) 28793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner OldVal->replaceAllUsesWith(SingularValue); 28893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner else 28993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner OldVal->replaceAllUsesWith(UndefValue::get(InsertedVal->getType())); 29093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner OldVal->eraseFromParent(); 29193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } else { 29293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner InsertedVal = SingularValue; 29393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } 294ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 29593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Drop the entries we added in IncomingPredInfo to restore the stack. 29693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, 29793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner IncomingPredInfo.end()); 29893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return InsertedVal; 29993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } 300ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 30193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Otherwise, we do need a PHI: insert one now if we don't already have one. 30293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (InsertedVal == 0) 30393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner InsertedVal = PHINode::Create(PrototypeValue->getType(), 30493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner PrototypeValue->getName(), &BB->front()); 305ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 30693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner PHINode *InsertedPHI = cast<PHINode>(InsertedVal); 30793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner InsertedPHI->reserveOperandSpace(IncomingPredInfo.size()-FirstPredInfoEntry); 308ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 30993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Fill in all the predecessors of the PHI. 310f9920fabac126d52d6b7443b676a64e032b970bfChris Lattner for (IncomingPredInfoTy::iterator I = 311f9920fabac126d52d6b7443b676a64e032b970bfChris Lattner IncomingPredInfo.begin()+FirstPredInfoEntry, 312f9920fabac126d52d6b7443b676a64e032b970bfChris Lattner E = IncomingPredInfo.end(); I != E; ++I) 31393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner InsertedPHI->addIncoming(I->second, I->first); 314ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 31593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // Drop the entries we added in IncomingPredInfo to restore the stack. 31693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry, 31793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner IncomingPredInfo.end()); 318ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 31993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // See if the PHI node can be merged to a single value. This can happen in 32093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner // loop cases when we get a PHI of itself and one other value. 32193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner if (Value *ConstVal = InsertedPHI->hasConstantValue()) { 32293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner InsertedPHI->replaceAllUsesWith(ConstVal); 32393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner InsertedPHI->eraseFromParent(); 32493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner InsertedVal = ConstVal; 32593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } else { 32693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner DEBUG(errs() << " Inserted PHI: " << *InsertedPHI << "\n"); 327ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 328f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner // If the client wants to know about all new instructions, tell it. 329f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 33093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner } 331ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 33293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return InsertedVal; 33393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 334