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 14d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/SSAUpdater.h" 1593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/ADT/DenseMap.h" 16840635741f132a9a10f052cbf3b21e14bc74835aChris Lattner#include "llvm/ADT/TinyPtrVector.h" 17cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands#include "llvm/Analysis/InstructionSimplify.h" 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/IR/Module.h" 2393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Support/Debug.h" 2493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Support/raw_ostream.h" 2540348e8d1ff564a23101d4fd37fe4dd03d9018abDevang Patel#include "llvm/Transforms/Utils/BasicBlockUtils.h" 26c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich#include "llvm/Transforms/Utils/Local.h" 274aad88d1fd88413029dd05255306b07cb19396eeBob Wilson#include "llvm/Transforms/Utils/SSAUpdaterImpl.h" 2840348e8d1ff564a23101d4fd37fe4dd03d9018abDevang Patel 2993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerusing namespace llvm; 3093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "ssaupdater" 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 3384bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilsontypedef DenseMap<BasicBlock*, Value*> AvailableValsTy; 3493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerstatic AvailableValsTy &getAvailableVals(void *AV) { 3593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return *static_cast<AvailableValsTy*>(AV); 3693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 3793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 38f5a1fb6b247611b92d9dec9476202b477661dbe8Chris LattnerSSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) 39dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : AV(nullptr), ProtoType(nullptr), ProtoName(), InsertedPHIs(NewPHI) {} 4093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 4193f3bcf7f323069e40d9abb950da73d437b6f7daChris LattnerSSAUpdater::~SSAUpdater() { 421cec7a05ee41725ec97b41608fe16d58c8c5b103Richard Smith delete static_cast<AvailableValsTy*>(AV); 4393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 4493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 45db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnervoid SSAUpdater::Initialize(Type *Ty, StringRef Name) { 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!AV) 4793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner AV = new AvailableValsTy(); 4893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner else 4993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner getAvailableVals(AV).clear(); 50fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands ProtoType = Ty; 51fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands ProtoName = Name; 5293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 5393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 540bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattnerbool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { 550bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner return getAvailableVals(AV).count(BB); 560bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner} 570bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner 5893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnervoid SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(ProtoType && "Need to initialize SSAUpdater"); 60fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands assert(ProtoType == V->getType() && 6193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner "All rewritten values must have the same type"); 6293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner getAvailableVals(AV)[BB] = V; 6393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 6493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 6584bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilsonstatic bool IsEquivalentPHI(PHINode *PHI, 662a6cbba2db261d2ee29a1373e195f95fd232e61bChris Lattner SmallDenseMap<BasicBlock*, Value*, 8> &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 815fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris LattnerValue *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { 825fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner Value *Res = GetValueAtEndOfBlockInternal(BB); 8393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner return Res; 8493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 8593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 861a8d4de397c360a76f1389d15e862eba265d71fdChris LattnerValue *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { 871a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // If there is no definition of the renamed variable in this block, just use 881a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // GetValueAtEndOfBlock to do our work. 8984bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson if (!HasValueForBlock(BB)) 901a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return GetValueAtEndOfBlock(BB); 91ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 921a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Otherwise, we have the hard case. Get the live-in values for each 931a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // predecessor. 941a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues; 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *SingularValue = nullptr; 96ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 971a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // We can get our predecessor info by walking the pred_iterator list, but it 981a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // is relatively slow. If we already have PHI nodes in this block, walk one 991a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // of them to get the predecessor list instead. 1001a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 1011a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 1021a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 1031a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *PredVal = GetValueAtEndOfBlock(PredBB); 1041a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PredValues.push_back(std::make_pair(PredBB, PredVal)); 105ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1061a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Compute SingularValue. 1071a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (i == 0) 1081a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = PredVal; 1091a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner else if (PredVal != SingularValue) 110dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SingularValue = nullptr; 1111a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1121a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } else { 1131a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner bool isFirstPred = true; 1141a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 1151a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner BasicBlock *PredBB = *PI; 1161a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *PredVal = GetValueAtEndOfBlock(PredBB); 1171a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner PredValues.push_back(std::make_pair(PredBB, PredVal)); 118ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1191a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Compute SingularValue. 1201a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (isFirstPred) { 1211a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner SingularValue = PredVal; 1221a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner isFirstPred = false; 1231a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } else if (PredVal != SingularValue) 124dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SingularValue = nullptr; 1251a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1261a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 127ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1281a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // If there are no predecessors, just return undef. 1291a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (PredValues.empty()) 130fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands return UndefValue::get(ProtoType); 131ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1321a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Otherwise, if all the merged values are the same, just use it. 133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (SingularValue) 1341a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return SingularValue; 135ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 13684bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson // Otherwise, we do need a PHI: check to see if we already have one available 13784bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson // in this block that produces the right value. 13884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson if (isa<PHINode>(BB->begin())) { 1392a6cbba2db261d2ee29a1373e195f95fd232e61bChris Lattner SmallDenseMap<BasicBlock*, Value*, 8> ValueMapping(PredValues.begin(), 1402a6cbba2db261d2ee29a1373e195f95fd232e61bChris Lattner PredValues.end()); 14184bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson PHINode *SomePHI; 14284bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson for (BasicBlock::iterator It = BB->begin(); 14384bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson (SomePHI = dyn_cast<PHINode>(It)); ++It) { 14484bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson if (IsEquivalentPHI(SomePHI, ValueMapping)) 14584bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson return SomePHI; 14684bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 14784bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 148e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson 1494c1e3da0cdd2fd0df5188dea1988beb8bf6a0dc6Chris Lattner // Ok, we have no way out, insert a new one now. 1503ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *InsertedPHI = PHINode::Create(ProtoType, PredValues.size(), 1513ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad ProtoName, &BB->front()); 152ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1531a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Fill in all the predecessors of the PHI. 154ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (const auto &PredValue : PredValues) 155ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InsertedPHI->addIncoming(PredValue.second, PredValue.first); 156ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1571a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // See if the PHI node can be merged to a single value. This can happen in 1581a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // loop cases when we get a PHI of itself and one other value. 1594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Value *V = 1604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar SimplifyInstruction(InsertedPHI, BB->getModule()->getDataLayout())) { 1611a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner InsertedPHI->eraseFromParent(); 162cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands return V; 1631a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 164f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner 165ccaddf47086742f62fb7fbf97f6509395f31b957Eli Bendersky // Set the DebugLoc of the inserted PHI, if available. 166ccaddf47086742f62fb7fbf97f6509395f31b957Eli Bendersky DebugLoc DL; 167ccaddf47086742f62fb7fbf97f6509395f31b957Eli Bendersky if (const Instruction *I = BB->getFirstNonPHI()) 168ccaddf47086742f62fb7fbf97f6509395f31b957Eli Bendersky DL = I->getDebugLoc(); 169ccaddf47086742f62fb7fbf97f6509395f31b957Eli Bendersky InsertedPHI->setDebugLoc(DL); 17040348e8d1ff564a23101d4fd37fe4dd03d9018abDevang Patel 171f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner // If the client wants to know about all new instructions, tell it. 172f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 173ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1741af40cacd4d162ffe9dfbafa1230e502e059be65David Greene DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 1751a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return InsertedPHI; 1761a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner} 1771a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 17893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnervoid SSAUpdater::RewriteUse(Use &U) { 17993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner Instruction *User = cast<Instruction>(U.getUser()); 18084bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 18188a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner Value *V; 18288a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner if (PHINode *UserPN = dyn_cast<PHINode>(User)) 18388a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 18488a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner else 18588a8624f8e104e1ba1ca21efa6ae23680b528a3eChris Lattner V = GetValueInMiddleOfBlock(User->getParent()); 186ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 1877b6783a03f16376e8e2d0d9791f090ef32727c8fNadav Rotem // Notify that users of the existing value that it is being replaced. 1887b6783a03f16376e8e2d0d9791f090ef32727c8fNadav Rotem Value *OldVal = U.get(); 1897b6783a03f16376e8e2d0d9791f090ef32727c8fNadav Rotem if (OldVal != V && OldVal->hasValueHandle()) 1907b6783a03f16376e8e2d0d9791f090ef32727c8fNadav Rotem ValueHandleBase::ValueIsRAUWd(OldVal, V); 1917b6783a03f16376e8e2d0d9791f090ef32727c8fNadav Rotem 192f993327e71d826dcb852929a78881569ef83374dTorok Edwin U.set(V); 19393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 19493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 195ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattnervoid SSAUpdater::RewriteUseAfterInsertions(Use &U) { 196ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner Instruction *User = cast<Instruction>(U.getUser()); 197ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner 198ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner Value *V; 199ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner if (PHINode *UserPN = dyn_cast<PHINode>(User)) 200ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 201ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner else 202ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner V = GetValueAtEndOfBlock(User->getParent()); 203ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner 204ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner U.set(V); 205ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner} 206ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner 2074aad88d1fd88413029dd05255306b07cb19396eeBob Wilsonnamespace llvm { 2084aad88d1fd88413029dd05255306b07cb19396eeBob Wilsontemplate<> 2094aad88d1fd88413029dd05255306b07cb19396eeBob Wilsonclass SSAUpdaterTraits<SSAUpdater> { 2104aad88d1fd88413029dd05255306b07cb19396eeBob Wilsonpublic: 2114aad88d1fd88413029dd05255306b07cb19396eeBob Wilson typedef BasicBlock BlkT; 2124aad88d1fd88413029dd05255306b07cb19396eeBob Wilson typedef Value *ValT; 2134aad88d1fd88413029dd05255306b07cb19396eeBob Wilson typedef PHINode PhiT; 2144aad88d1fd88413029dd05255306b07cb19396eeBob Wilson 2154aad88d1fd88413029dd05255306b07cb19396eeBob Wilson typedef succ_iterator BlkSucc_iterator; 2164aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); } 2174aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); } 2184aad88d1fd88413029dd05255306b07cb19396eeBob Wilson 219fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth class PHI_iterator { 220fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth private: 221fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth PHINode *PHI; 222fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth unsigned idx; 223fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth 224fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth public: 225fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth explicit PHI_iterator(PHINode *P) // begin iterator 226fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth : PHI(P), idx(0) {} 227fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth PHI_iterator(PHINode *P, bool) // end iterator 228fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth : PHI(P), idx(PHI->getNumIncomingValues()) {} 229fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth 230fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth PHI_iterator &operator++() { ++idx; return *this; } 231fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth bool operator==(const PHI_iterator& x) const { return idx == x.idx; } 232fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth bool operator!=(const PHI_iterator& x) const { return !operator==(x); } 233fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth Value *getIncomingValue() { return PHI->getIncomingValue(idx); } 234fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); } 235fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth }; 236fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth 237fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } 238fdc2d0faf321224393f1a5dbf05c3e3f88bb6e3eChandler Carruth static PHI_iterator PHI_end(PhiT *PHI) { 2394aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return PHI_iterator(PHI, true); 24084bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 24149c283fd3f8f81e04b84dc848981b4bf17b2d706Bob Wilson 2424aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds 2434aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// vector, set Info->NumPreds, and allocate space in Info->Preds. 2444aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static void FindPredecessorBlocks(BasicBlock *BB, 2454aad88d1fd88413029dd05255306b07cb19396eeBob Wilson SmallVectorImpl<BasicBlock*> *Preds) { 2464aad88d1fd88413029dd05255306b07cb19396eeBob Wilson // We can get our predecessor info by walking the pred_iterator list, 2474aad88d1fd88413029dd05255306b07cb19396eeBob Wilson // but it is relatively slow. If we already have PHI nodes in this 2484aad88d1fd88413029dd05255306b07cb19396eeBob Wilson // block, walk one of them to get the predecessor list instead. 2494aad88d1fd88413029dd05255306b07cb19396eeBob Wilson if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 250ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Preds->append(SomePhi->block_begin(), SomePhi->block_end()); 2514aad88d1fd88413029dd05255306b07cb19396eeBob Wilson } else { 2524aad88d1fd88413029dd05255306b07cb19396eeBob Wilson for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 2534aad88d1fd88413029dd05255306b07cb19396eeBob Wilson Preds->push_back(*PI); 25484bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 25584bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 25684bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 2574aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// GetUndefVal - Get an undefined value of the same type as the value 2584aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// being handled. 2594aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) { 260fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands return UndefValue::get(Updater->ProtoType); 26184bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 26284bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 2634aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// CreateEmptyPHI - Create a new PHI instruction in the specified block. 2644aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// Reserve space for the operands but do not fill them in yet. 2654aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds, 2664aad88d1fd88413029dd05255306b07cb19396eeBob Wilson SSAUpdater *Updater) { 2673ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *PHI = PHINode::Create(Updater->ProtoType, NumPreds, 2683ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad Updater->ProtoName, &BB->front()); 2694aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return PHI; 270a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson } 271a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson 2724aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// AddPHIOperand - Add the specified value as an operand of the PHI for 2734aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// the specified predecessor block. 2744aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) { 2754aad88d1fd88413029dd05255306b07cb19396eeBob Wilson PHI->addIncoming(Val, Pred); 27684bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 277ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 2784aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// InstrIsPHI - Check if an instruction is a PHI. 2794aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// 2804aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static PHINode *InstrIsPHI(Instruction *I) { 2814aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return dyn_cast<PHINode>(I); 282a0c6057061be055faa542d05b2213f2bd779e160Bob Wilson } 28345305d4ff6bff8dfe62228c68b3cb61bb2d7254fChris Lattner 2844aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// ValueIsPHI - Check if a value is a PHI. 2854aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// 2864aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) { 2874aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return dyn_cast<PHINode>(Val); 28884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 289ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 2904aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source 2914aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// operands, i.e., it was just added. 2924aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) { 2934aad88d1fd88413029dd05255306b07cb19396eeBob Wilson PHINode *PHI = ValueIsPHI(Val, Updater); 2944aad88d1fd88413029dd05255306b07cb19396eeBob Wilson if (PHI && PHI->getNumIncomingValues() == 0) 2954aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return PHI; 296dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 29784bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 29884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 2994aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// GetPHIValue - For the specified PHI instruction, return the value 3004aad88d1fd88413029dd05255306b07cb19396eeBob Wilson /// that it defines. 3014aad88d1fd88413029dd05255306b07cb19396eeBob Wilson static Value *GetPHIValue(PHINode *PHI) { 3024aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return PHI; 30384bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 3044aad88d1fd88413029dd05255306b07cb19396eeBob Wilson}; 30584bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 3064aad88d1fd88413029dd05255306b07cb19396eeBob Wilson} // End llvm namespace 307ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 308064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth/// Check to see if AvailableVals has an entry for the specified BB and if so, 309064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth/// return it. If not, construct SSA form by first calculating the required 310064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth/// placement of PHIs and then inserting new PHIs where needed. 3114aad88d1fd88413029dd05255306b07cb19396eeBob WilsonValue *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { 31284bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson AvailableValsTy &AvailableVals = getAvailableVals(AV); 3134aad88d1fd88413029dd05255306b07cb19396eeBob Wilson if (Value *V = AvailableVals[BB]) 3144aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return V; 3154aad88d1fd88413029dd05255306b07cb19396eeBob Wilson 3164aad88d1fd88413029dd05255306b07cb19396eeBob Wilson SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); 3174aad88d1fd88413029dd05255306b07cb19396eeBob Wilson return Impl.GetValue(BB); 31893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} 319a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 320a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner//===----------------------------------------------------------------------===// 321a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner// LoadAndStorePromoter Implementation 322a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner//===----------------------------------------------------------------------===// 323a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 324deaf55f69865bbc997a569c2a689ec5b0fbdefefChris LattnerLoadAndStorePromoter:: 3256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga NainarLoadAndStorePromoter(ArrayRef<const Instruction*> Insts, 326231a5ab746ca12000aa57208869a98f78781aa6bDevang Patel SSAUpdater &S, StringRef BaseName) : SSA(S) { 327a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner if (Insts.empty()) return; 328a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 3296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const Value *SomeVal; 3306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (const LoadInst *LI = dyn_cast<LoadInst>(Insts[0])) 331deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner SomeVal = LI; 332a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner else 333deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner SomeVal = cast<StoreInst>(Insts[0])->getOperand(0); 334deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner 335deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner if (BaseName.empty()) 336deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner BaseName = SomeVal->getName(); 337deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner SSA.Initialize(SomeVal->getType(), BaseName); 338deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner} 339deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner 340deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner 341deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattnervoid LoadAndStorePromoter:: 342deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattnerrun(const SmallVectorImpl<Instruction*> &Insts) const { 343a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 344a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // First step: bucket up uses of the alloca by the block they occur in. 345a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // This is important because we have to handle multiple defs/uses in a block 346a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // ourselves: SSAUpdater is purely for cross-block references. 347840635741f132a9a10f052cbf3b21e14bc74835aChris Lattner DenseMap<BasicBlock*, TinyPtrVector<Instruction*> > UsesByBlock; 348ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 349ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction *User : Insts) 350a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner UsesByBlock[User->getParent()].push_back(User); 351a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 352a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Okay, now we can iterate over all the blocks in the function with uses, 353a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // processing them. Keep track of which loads are loading a live-in value. 354a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Walk the uses in the use-list order to be determinstic. 355a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner SmallVector<LoadInst*, 32> LiveInLoads; 356a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner DenseMap<Value*, Value*> ReplacedLoads; 357ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 358ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction *User : Insts) { 359a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner BasicBlock *BB = User->getParent(); 360840635741f132a9a10f052cbf3b21e14bc74835aChris Lattner TinyPtrVector<Instruction*> &BlockUses = UsesByBlock[BB]; 361a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 362a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // If this block has already been processed, ignore this repeat use. 363a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner if (BlockUses.empty()) continue; 364a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 365a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Okay, this is the first use in the block. If this block just has a 366a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // single user in it, we can rewrite it trivially. 367a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner if (BlockUses.size() == 1) { 368a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // If it is a store, it is a trivial def of the value in the block. 369c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 370231a5ab746ca12000aa57208869a98f78781aa6bDevang Patel updateDebugInfo(SI); 371deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner SSA.AddAvailableValue(BB, SI->getOperand(0)); 372c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich } else 373a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Otherwise it is a load, queue it to rewrite as a live-in load. 374a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner LiveInLoads.push_back(cast<LoadInst>(User)); 375a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner BlockUses.clear(); 376a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner continue; 377a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 378a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 379a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Otherwise, check to see if this block is all loads. 380a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner bool HasStore = false; 381ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction *I : BlockUses) { 382ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (isa<StoreInst>(I)) { 383a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner HasStore = true; 384a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner break; 385a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 386a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 387a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 388a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // If so, we can queue them all as live in loads. We don't have an 389a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // efficient way to tell which on is first in the block and don't want to 390a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // scan large blocks, so just add all loads as live ins. 391a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner if (!HasStore) { 392ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction *I : BlockUses) 393ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LiveInLoads.push_back(cast<LoadInst>(I)); 394a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner BlockUses.clear(); 395a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner continue; 396a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 397a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 398a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Otherwise, we have mixed loads and stores (or just a bunch of stores). 399a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Since SSAUpdater is purely for cross-block values, we need to determine 400a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // the order of these instructions in the block. If the first use in the 401a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // block is a load, then it uses the live in value. The last store defines 402a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // the live out value. We handle this by doing a linear scan of the block. 403dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *StoredValue = nullptr; 404ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction &I : *BB) { 405ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (LoadInst *L = dyn_cast<LoadInst>(&I)) { 406a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // If this is a load from an unrelated pointer, ignore it. 407a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner if (!isInstInList(L, Insts)) continue; 408a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 409a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // If we haven't seen a store yet, this is a live in use, otherwise 410a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // use the stored value. 411a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner if (StoredValue) { 412deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner replaceLoadWithValue(L, StoredValue); 413a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner L->replaceAllUsesWith(StoredValue); 414a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner ReplacedLoads[L] = StoredValue; 415a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } else { 416a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner LiveInLoads.push_back(L); 417a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 418a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner continue; 419a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 420ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 421ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (StoreInst *SI = dyn_cast<StoreInst>(&I)) { 422a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // If this is a store to an unrelated pointer, ignore it. 423c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich if (!isInstInList(SI, Insts)) continue; 424231a5ab746ca12000aa57208869a98f78781aa6bDevang Patel updateDebugInfo(SI); 425c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich 426a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Remember that this is the active value in the block. 427c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich StoredValue = SI->getOperand(0); 428a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 429a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 430a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 431a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // The last stored value that happened is the live-out for the block. 432a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner assert(StoredValue && "Already checked that there is a store in block"); 433deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner SSA.AddAvailableValue(BB, StoredValue); 434a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner BlockUses.clear(); 435a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 436a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 437a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Okay, now we rewrite all loads that use live-in values in the loop, 438a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // inserting PHI nodes as necessary. 439ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (LoadInst *ALoad : LiveInLoads) { 440deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent()); 441deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner replaceLoadWithValue(ALoad, NewVal); 442867be59684afef29f058385c6618ec7753596ffcChris Lattner 443867be59684afef29f058385c6618ec7753596ffcChris Lattner // Avoid assertions in unreachable code. 444867be59684afef29f058385c6618ec7753596ffcChris Lattner if (NewVal == ALoad) NewVal = UndefValue::get(NewVal->getType()); 445a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner ALoad->replaceAllUsesWith(NewVal); 446a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner ReplacedLoads[ALoad] = NewVal; 447a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 448a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 449deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // Allow the client to do stuff before we start nuking things. 450deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner doExtraRewritesBeforeFinalDeletion(); 451deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner 452a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Now that everything is rewritten, delete the old instructions from the 453a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // function. They should all be dead now. 454ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction *User : Insts) { 455a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // If this is a load that still has uses, then the load must have been added 456a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // as a live value in the SSAUpdate data structure for a block (e.g. because 457a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // the loaded value was stored later). In this case, we need to recursively 458a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // propagate the updates until we get to the real value. 459a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner if (!User->use_empty()) { 460a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner Value *NewVal = ReplacedLoads[User]; 461a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner assert(NewVal && "not a replaced load?"); 462a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 463a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // Propagate down to the ultimate replacee. The intermediately loads 464a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // could theoretically already have been deleted, so we don't want to 465a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner // dereference the Value*'s. 466a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal); 467a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner while (RLI != ReplacedLoads.end()) { 468a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner NewVal = RLI->second; 469a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner RLI = ReplacedLoads.find(NewVal); 470a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 471a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 472deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner replaceLoadWithValue(cast<LoadInst>(User), NewVal); 473a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner User->replaceAllUsesWith(NewVal); 474a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 475a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner 476deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner instructionDeleted(User); 477a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner User->eraseFromParent(); 478a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner } 479a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner} 480aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer 481aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramerbool 482aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin KramerLoadAndStorePromoter::isInstInList(Instruction *I, 483aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer const SmallVectorImpl<Instruction*> &Insts) 484aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer const { 485aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer return std::find(Insts.begin(), Insts.end(), I) != Insts.end(); 486aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer} 487