194b5036ee6ba866e1702848855b6d687d1e70afaAlexey Samsonov//===-- SSAUpdaterImpl.h - SSA Updater Implementation -----------*- C++ -*-===// 29aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany// 39aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany// The LLVM Compiler Infrastructure 49aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany// 59aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany// This file is distributed under the University of Illinois Open Source 69aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany// License. See LICENSE.TXT for details. 79aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany// 89aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany//===----------------------------------------------------------------------===// 99aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany// 109aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany// This file provides a template that implements the core algorithm for the 110a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov// SSAUpdater and MachineSSAUpdater. 129aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany// 139aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany//===----------------------------------------------------------------------===// 149aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany 159aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H 16d865fecddccebf898ceed24d096fc58fb29a6e57Chandler Carruth#define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H 170a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov 189aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany#include "llvm/ADT/DenseMap.h" 199aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany#include "llvm/ADT/SmallVector.h" 209aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany#include "llvm/IR/ValueHandle.h" 210a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov#include "llvm/Support/Allocator.h" 220a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov#include "llvm/Support/Debug.h" 230a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov 240a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonovnamespace llvm { 250a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov 260a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov#define DEBUG_TYPE "ssaupdater" 27bfa45e11e52081c55294355f36fa547f163dcc67Dmitry Vyukov 28d51a1a10cba87be50e9ada9fa21337c387edb237Dmitry Vyukovclass CastInst; 290a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonovclass PHINode; 300a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonovtemplate<typename T> class SSAUpdaterTraits; 310a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov 3215503b0a4331c7f27f9cebc25e25c2e494f61cb9Alexey Samsonovtemplate<typename UpdaterT> 330a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonovclass SSAUpdaterImpl { 340a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonovprivate: 350a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov UpdaterT *Updater; 36d51a1a10cba87be50e9ada9fa21337c387edb237Dmitry Vyukov 37e2462f7461961925f7f20577352c01e867365d8bDmitry Vyukov typedef SSAUpdaterTraits<UpdaterT> Traits; 38e2462f7461961925f7f20577352c01e867365d8bDmitry Vyukov typedef typename Traits::BlkT BlkT; 39e2462f7461961925f7f20577352c01e867365d8bDmitry Vyukov typedef typename Traits::ValT ValT; 40e2462f7461961925f7f20577352c01e867365d8bDmitry Vyukov typedef typename Traits::PhiT PhiT; 41b1bd208bfa496391085056b1709542b80dcfb21eDmitry Vyukov 42bfa45e11e52081c55294355f36fa547f163dcc67Dmitry Vyukov /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl. 43d51a1a10cba87be50e9ada9fa21337c387edb237Dmitry Vyukov /// The predecessors of each block are cached here since pred_iterator is 440a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov /// slow and we need to iterate over the blocks at least a few times. 450a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov class BBInfo { 4615503b0a4331c7f27f9cebc25e25c2e494f61cb9Alexey Samsonov public: 470a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov BlkT *BB; // Back-pointer to the corresponding block. 480a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov ValT AvailableVal; // Value to use in this block. 490a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov BBInfo *DefBB; // Block that defines the available value. 5097daee89b35f6141db09aee612f0f377f754092fDmitry Vyukov int BlkNum; // Postorder number. 510a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov BBInfo *IDom; // Immediate dominator. 520a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov unsigned NumPreds; // Number of predecessor blocks. 532ea978704a794e536d2801affcc7f301092d75daAlexey Samsonov BBInfo **Preds; // Array[NumPreds] of predecessor blocks. 540a4c906dbc8f150657ddd4f19a7192b779f1d605Alexey Samsonov PhiT *PHITag; // Marker for existing PHIs that match. 55b1bd208bfa496391085056b1709542b80dcfb21eDmitry Vyukov 56e2462f7461961925f7f20577352c01e867365d8bDmitry Vyukov BBInfo(BlkT *ThisBB, ValT V) 579aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr), BlkNum(0), 58dd3a911e46b3f0416d60d9be5c84ccfc4b1c3aa8Alexey Samsonov IDom(nullptr), NumPreds(0), Preds(nullptr), PHITag(nullptr) {} 59bb19294a1195fb320047bace7732f15e85ac4da5Dmitry Vyukov }; 60dd3a911e46b3f0416d60d9be5c84ccfc4b1c3aa8Alexey Samsonov 61dd3a911e46b3f0416d60d9be5c84ccfc4b1c3aa8Alexey Samsonov typedef DenseMap<BlkT*, ValT> AvailableValsTy; 62dd3a911e46b3f0416d60d9be5c84ccfc4b1c3aa8Alexey Samsonov AvailableValsTy *AvailableVals; 63dd3a911e46b3f0416d60d9be5c84ccfc4b1c3aa8Alexey Samsonov 64dd3a911e46b3f0416d60d9be5c84ccfc4b1c3aa8Alexey Samsonov SmallVectorImpl<PhiT*> *InsertedPHIs; 65dd3a911e46b3f0416d60d9be5c84ccfc4b1c3aa8Alexey Samsonov 66dd3a911e46b3f0416d60d9be5c84ccfc4b1c3aa8Alexey Samsonov typedef SmallVectorImpl<BBInfo*> BlockListTy; 67dd3a911e46b3f0416d60d9be5c84ccfc4b1c3aa8Alexey Samsonov typedef DenseMap<BlkT*, BBInfo*> BBMapTy; 685af39e50366f1aacbebc284f572f08ad1ad07357Kostya Serebryany BBMapTy BBMap; 695af39e50366f1aacbebc284f572f08ad1ad07357Kostya Serebryany BumpPtrAllocator Allocator; 705af39e50366f1aacbebc284f572f08ad1ad07357Kostya Serebryany 715af39e50366f1aacbebc284f572f08ad1ad07357Kostya Serebryanypublic: 725af39e50366f1aacbebc284f572f08ad1ad07357Kostya Serebryany explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A, 739aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany SmallVectorImpl<PhiT*> *Ins) : 7415a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov Updater(U), AvailableVals(A), InsertedPHIs(Ins) { } 7515a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov 7615a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov /// GetValue - Check to see if AvailableVals has an entry for the specified 7715a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov /// BB and if so, return it. If not, construct SSA form by first 7815a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov /// calculating the required placement of PHIs and then inserting new PHIs 7915a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov /// where needed. 8015a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov ValT GetValue(BlkT *BB) { 8115a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov SmallVector<BBInfo*, 100> BlockList; 82230c3be6cdd094a187f48e27ba0961dbeee70344Alexey Samsonov BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList); 83230c3be6cdd094a187f48e27ba0961dbeee70344Alexey Samsonov 84230c3be6cdd094a187f48e27ba0961dbeee70344Alexey Samsonov // Special case: bail out if BB is unreachable. 85230c3be6cdd094a187f48e27ba0961dbeee70344Alexey Samsonov if (BlockList.size() == 0) { 86230c3be6cdd094a187f48e27ba0961dbeee70344Alexey Samsonov ValT V = Traits::GetUndefVal(BB, Updater); 87230c3be6cdd094a187f48e27ba0961dbeee70344Alexey Samsonov (*AvailableVals)[BB] = V; 88230c3be6cdd094a187f48e27ba0961dbeee70344Alexey Samsonov return V; 89230c3be6cdd094a187f48e27ba0961dbeee70344Alexey Samsonov } 90230c3be6cdd094a187f48e27ba0961dbeee70344Alexey Samsonov 9115a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov FindDominators(&BlockList, PseudoEntry); 9215a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov FindPHIPlacement(&BlockList); 9315a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov FindAvailableVals(&BlockList); 9415a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov 9515a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov return BBMap[BB]->DefBB->AvailableVal; 9615a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov } 9715a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov 9815a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov /// BuildBlockList - Starting from the specified basic block, traverse back 9915a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov /// through its predecessors until reaching blocks with known values. 10015a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov /// Create BBInfo structures for the blocks and append them to the block 10115a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov /// list. 10215a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) { 10315a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov SmallVector<BBInfo*, 10> RootList; 10415a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov SmallVector<BBInfo*, 64> WorkList; 10515a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov 10615a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov BBInfo *Info = new (Allocator) BBInfo(BB, 0); 10715a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov BBMap[BB] = Info; 10815a77612e0a89c1df444a2034e531c8968d0cedfAlexey Samsonov WorkList.push_back(Info); 109fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov 110fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov // Search backward from BB, creating BBInfos along the way and stopping 111fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov // when reaching blocks that define the value. Record those defining 112fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov // blocks on the RootList. 113fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov SmallVector<BlkT*, 10> Preds; 114fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov while (!WorkList.empty()) { 115fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov Info = WorkList.pop_back_val(); 116fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov Preds.clear(); 117fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov Traits::FindPredecessorBlocks(Info->BB, &Preds); 118fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov Info->NumPreds = Preds.size(); 119fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov if (Info->NumPreds == 0) 120fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov Info->Preds = nullptr; 121fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov else 122fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov Info->Preds = static_cast<BBInfo**> 123fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov (Allocator.Allocate(Info->NumPreds * sizeof(BBInfo*), 124fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov AlignOf<BBInfo*>::Alignment)); 125fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov 126fce5bd4cc29fddb5e8f0cb9c12df7c10187a991dDmitry Vyukov for (unsigned p = 0; p != Info->NumPreds; ++p) { 12745418d1ccb083cad3cb84e0b8184adfb85876fc5Alexey Samsonov BlkT *Pred = Preds[p]; 12845418d1ccb083cad3cb84e0b8184adfb85876fc5Alexey Samsonov // Check if BBMap already has a BBInfo for the predecessor block. 12945418d1ccb083cad3cb84e0b8184adfb85876fc5Alexey Samsonov typename BBMapTy::value_type &BBMapBucket = 1305759d92e99e2b7adcc46a8729f16023208dd8f37Kostya Serebryany BBMap.FindAndConstruct(Pred); 13145418d1ccb083cad3cb84e0b8184adfb85876fc5Alexey Samsonov if (BBMapBucket.second) { 13245418d1ccb083cad3cb84e0b8184adfb85876fc5Alexey Samsonov Info->Preds[p] = BBMapBucket.second; 1338c53e54ef9e713953ec9495e82e5c330b96e49f3Alexey Samsonov continue; 134c375657778e8a72d566e29951060b7eadc749b0dKostya Serebryany } 135c375657778e8a72d566e29951060b7eadc749b0dKostya Serebryany 1364c2ddda9ac80f94782b2b040208831233db578afKostya Serebryany // Create a new BBInfo for the predecessor. 1374c2ddda9ac80f94782b2b040208831233db578afKostya Serebryany ValT PredVal = AvailableVals->lookup(Pred); 138c375657778e8a72d566e29951060b7eadc749b0dKostya Serebryany BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal); 139c375657778e8a72d566e29951060b7eadc749b0dKostya Serebryany BBMapBucket.second = PredInfo; 140d7ed1f09f316628b2d981a1d8c2cf0f5af30e90eAlexey Samsonov Info->Preds[p] = PredInfo; 141c375657778e8a72d566e29951060b7eadc749b0dKostya Serebryany 142c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov if (PredInfo->AvailableVal) { 143c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov RootList.push_back(PredInfo); 144b46941a1d23012491a7a8a52718cacbde3c19ba1Alexey Samsonov continue; 145b46941a1d23012491a7a8a52718cacbde3c19ba1Alexey Samsonov } 1465af39e50366f1aacbebc284f572f08ad1ad07357Kostya Serebryany WorkList.push_back(PredInfo); 147c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov } 148c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov } 149c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov 150c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov // Now that we know what blocks are backwards-reachable from the starting 151c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov // block, do a forward depth-first traversal to assign postorder numbers 1525af39e50366f1aacbebc284f572f08ad1ad07357Kostya Serebryany // to those blocks. 153c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0); 154c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov unsigned BlkNum = 1; 155c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov 156c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov // Initialize the worklist with the roots from the backward traversal. 157c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov while (!RootList.empty()) { 158c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov Info = RootList.pop_back_val(); 159c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov Info->IDom = PseudoEntry; 160c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov Info->BlkNum = -1; 161c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov WorkList.push_back(Info); 162c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov } 163c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov 164c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov while (!WorkList.empty()) { 165c925697df6626bb0ea27ea96539bf0580f8f3d3dAlexey Samsonov Info = WorkList.back(); 16670e177e29c6f9ac987b65a79f6b4f3ebdabc75ccAlexey Samsonov 16770e177e29c6f9ac987b65a79f6b4f3ebdabc75ccAlexey Samsonov if (Info->BlkNum == -2) { 168b46941a1d23012491a7a8a52718cacbde3c19ba1Alexey Samsonov // All the successors have been handled; assign the postorder number. 1691b5ea8fbbef73f5d9b41dbb26a21b9a0f4d1445eKostya Serebryany Info->BlkNum = BlkNum++; 1701b5ea8fbbef73f5d9b41dbb26a21b9a0f4d1445eKostya Serebryany // If not a root, put it on the BlockList. 1711b5ea8fbbef73f5d9b41dbb26a21b9a0f4d1445eKostya Serebryany if (!Info->AvailableVal) 17280acccf4647c3482c3e3e6ae21e757ba580a5956Kostya Serebryany BlockList->push_back(Info); 17380acccf4647c3482c3e3e6ae21e757ba580a5956Kostya Serebryany WorkList.pop_back(); 1741b5ea8fbbef73f5d9b41dbb26a21b9a0f4d1445eKostya Serebryany continue; 1751b5ea8fbbef73f5d9b41dbb26a21b9a0f4d1445eKostya Serebryany } 1761b5ea8fbbef73f5d9b41dbb26a21b9a0f4d1445eKostya Serebryany 1771b5ea8fbbef73f5d9b41dbb26a21b9a0f4d1445eKostya Serebryany // Leave this entry on the worklist, but set its BlkNum to mark that its 1781b5ea8fbbef73f5d9b41dbb26a21b9a0f4d1445eKostya Serebryany // successors have been put on the worklist. When it returns to the top 1791b5ea8fbbef73f5d9b41dbb26a21b9a0f4d1445eKostya Serebryany // the list, after handling its successors, it will be assigned a 1801b5ea8fbbef73f5d9b41dbb26a21b9a0f4d1445eKostya Serebryany // number. 1813334e12d33261cb8f211f2f49f28ddfa027a40c3Evgeniy Stepanov Info->BlkNum = -2; 1823334e12d33261cb8f211f2f49f28ddfa027a40c3Evgeniy Stepanov 1833334e12d33261cb8f211f2f49f28ddfa027a40c3Evgeniy Stepanov // Add unvisited successors to the work list. 1843334e12d33261cb8f211f2f49f28ddfa027a40c3Evgeniy Stepanov for (typename Traits::BlkSucc_iterator SI = 1853334e12d33261cb8f211f2f49f28ddfa027a40c3Evgeniy Stepanov Traits::BlkSucc_begin(Info->BB), 1863334e12d33261cb8f211f2f49f28ddfa027a40c3Evgeniy Stepanov E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) { 1879aead37421a6e4bf43265e5195c6ac31fc519982Kostya Serebryany BBInfo *SuccInfo = BBMap[*SI]; 188 if (!SuccInfo || SuccInfo->BlkNum) 189 continue; 190 SuccInfo->BlkNum = -1; 191 WorkList.push_back(SuccInfo); 192 } 193 } 194 PseudoEntry->BlkNum = BlkNum; 195 return PseudoEntry; 196 } 197 198 /// IntersectDominators - This is the dataflow lattice "meet" operation for 199 /// finding dominators. Given two basic blocks, it walks up the dominator 200 /// tree until it finds a common dominator of both. It uses the postorder 201 /// number of the blocks to determine how to do that. 202 BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) { 203 while (Blk1 != Blk2) { 204 while (Blk1->BlkNum < Blk2->BlkNum) { 205 Blk1 = Blk1->IDom; 206 if (!Blk1) 207 return Blk2; 208 } 209 while (Blk2->BlkNum < Blk1->BlkNum) { 210 Blk2 = Blk2->IDom; 211 if (!Blk2) 212 return Blk1; 213 } 214 } 215 return Blk1; 216 } 217 218 /// FindDominators - Calculate the dominator tree for the subset of the CFG 219 /// corresponding to the basic blocks on the BlockList. This uses the 220 /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey 221 /// and Kennedy, published in Software--Practice and Experience, 2001, 222 /// 4:1-10. Because the CFG subset does not include any edges leading into 223 /// blocks that define the value, the results are not the usual dominator 224 /// tree. The CFG subset has a single pseudo-entry node with edges to a set 225 /// of root nodes for blocks that define the value. The dominators for this 226 /// subset CFG are not the standard dominators but they are adequate for 227 /// placing PHIs within the subset CFG. 228 void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) { 229 bool Changed; 230 do { 231 Changed = false; 232 // Iterate over the list in reverse order, i.e., forward on CFG edges. 233 for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(), 234 E = BlockList->rend(); I != E; ++I) { 235 BBInfo *Info = *I; 236 BBInfo *NewIDom = nullptr; 237 238 // Iterate through the block's predecessors. 239 for (unsigned p = 0; p != Info->NumPreds; ++p) { 240 BBInfo *Pred = Info->Preds[p]; 241 242 // Treat an unreachable predecessor as a definition with 'undef'. 243 if (Pred->BlkNum == 0) { 244 Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater); 245 (*AvailableVals)[Pred->BB] = Pred->AvailableVal; 246 Pred->DefBB = Pred; 247 Pred->BlkNum = PseudoEntry->BlkNum; 248 PseudoEntry->BlkNum++; 249 } 250 251 if (!NewIDom) 252 NewIDom = Pred; 253 else 254 NewIDom = IntersectDominators(NewIDom, Pred); 255 } 256 257 // Check if the IDom value has changed. 258 if (NewIDom && NewIDom != Info->IDom) { 259 Info->IDom = NewIDom; 260 Changed = true; 261 } 262 } 263 } while (Changed); 264 } 265 266 /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for 267 /// any blocks containing definitions of the value. If one is found, then 268 /// the successor of Pred is in the dominance frontier for the definition, 269 /// and this function returns true. 270 bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) { 271 for (; Pred != IDom; Pred = Pred->IDom) { 272 if (Pred->DefBB == Pred) 273 return true; 274 } 275 return false; 276 } 277 278 /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers 279 /// of the known definitions. Iteratively add PHIs in the dom frontiers 280 /// until nothing changes. Along the way, keep track of the nearest 281 /// dominating definitions for non-PHI blocks. 282 void FindPHIPlacement(BlockListTy *BlockList) { 283 bool Changed; 284 do { 285 Changed = false; 286 // Iterate over the list in reverse order, i.e., forward on CFG edges. 287 for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(), 288 E = BlockList->rend(); I != E; ++I) { 289 BBInfo *Info = *I; 290 291 // If this block already needs a PHI, there is nothing to do here. 292 if (Info->DefBB == Info) 293 continue; 294 295 // Default to use the same def as the immediate dominator. 296 BBInfo *NewDefBB = Info->IDom->DefBB; 297 for (unsigned p = 0; p != Info->NumPreds; ++p) { 298 if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) { 299 // Need a PHI here. 300 NewDefBB = Info; 301 break; 302 } 303 } 304 305 // Check if anything changed. 306 if (NewDefBB != Info->DefBB) { 307 Info->DefBB = NewDefBB; 308 Changed = true; 309 } 310 } 311 } while (Changed); 312 } 313 314 /// FindAvailableVal - If this block requires a PHI, first check if an 315 /// existing PHI matches the PHI placement and reaching definitions computed 316 /// earlier, and if not, create a new PHI. Visit all the block's 317 /// predecessors to calculate the available value for each one and fill in 318 /// the incoming values for a new PHI. 319 void FindAvailableVals(BlockListTy *BlockList) { 320 // Go through the worklist in forward order (i.e., backward through the CFG) 321 // and check if existing PHIs can be used. If not, create empty PHIs where 322 // they are needed. 323 for (typename BlockListTy::iterator I = BlockList->begin(), 324 E = BlockList->end(); I != E; ++I) { 325 BBInfo *Info = *I; 326 // Check if there needs to be a PHI in BB. 327 if (Info->DefBB != Info) 328 continue; 329 330 // Look for an existing PHI. 331 FindExistingPHI(Info->BB, BlockList); 332 if (Info->AvailableVal) 333 continue; 334 335 ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater); 336 Info->AvailableVal = PHI; 337 (*AvailableVals)[Info->BB] = PHI; 338 } 339 340 // Now go back through the worklist in reverse order to fill in the 341 // arguments for any new PHIs added in the forward traversal. 342 for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(), 343 E = BlockList->rend(); I != E; ++I) { 344 BBInfo *Info = *I; 345 346 if (Info->DefBB != Info) { 347 // Record the available value at join nodes to speed up subsequent 348 // uses of this SSAUpdater for the same value. 349 if (Info->NumPreds > 1) 350 (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal; 351 continue; 352 } 353 354 // Check if this block contains a newly added PHI. 355 PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater); 356 if (!PHI) 357 continue; 358 359 // Iterate through the block's predecessors. 360 for (unsigned p = 0; p != Info->NumPreds; ++p) { 361 BBInfo *PredInfo = Info->Preds[p]; 362 BlkT *Pred = PredInfo->BB; 363 // Skip to the nearest preceding definition. 364 if (PredInfo->DefBB != PredInfo) 365 PredInfo = PredInfo->DefBB; 366 Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred); 367 } 368 369 DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n"); 370 371 // If the client wants to know about all new instructions, tell it. 372 if (InsertedPHIs) InsertedPHIs->push_back(PHI); 373 } 374 } 375 376 /// FindExistingPHI - Look through the PHI nodes in a block to see if any of 377 /// them match what is needed. 378 void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) { 379 for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end(); 380 BBI != BBE; ++BBI) { 381 PhiT *SomePHI = Traits::InstrIsPHI(BBI); 382 if (!SomePHI) 383 break; 384 if (CheckIfPHIMatches(SomePHI)) { 385 RecordMatchingPHIs(BlockList); 386 break; 387 } 388 // Match failed: clear all the PHITag values. 389 for (typename BlockListTy::iterator I = BlockList->begin(), 390 E = BlockList->end(); I != E; ++I) 391 (*I)->PHITag = nullptr; 392 } 393 } 394 395 /// CheckIfPHIMatches - Check if a PHI node matches the placement and values 396 /// in the BBMap. 397 bool CheckIfPHIMatches(PhiT *PHI) { 398 SmallVector<PhiT*, 20> WorkList; 399 WorkList.push_back(PHI); 400 401 // Mark that the block containing this PHI has been visited. 402 BBMap[PHI->getParent()]->PHITag = PHI; 403 404 while (!WorkList.empty()) { 405 PHI = WorkList.pop_back_val(); 406 407 // Iterate through the PHI's incoming values. 408 for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI), 409 E = Traits::PHI_end(PHI); I != E; ++I) { 410 ValT IncomingVal = I.getIncomingValue(); 411 BBInfo *PredInfo = BBMap[I.getIncomingBlock()]; 412 // Skip to the nearest preceding definition. 413 if (PredInfo->DefBB != PredInfo) 414 PredInfo = PredInfo->DefBB; 415 416 // Check if it matches the expected value. 417 if (PredInfo->AvailableVal) { 418 if (IncomingVal == PredInfo->AvailableVal) 419 continue; 420 return false; 421 } 422 423 // Check if the value is a PHI in the correct block. 424 PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater); 425 if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB) 426 return false; 427 428 // If this block has already been visited, check if this PHI matches. 429 if (PredInfo->PHITag) { 430 if (IncomingPHIVal == PredInfo->PHITag) 431 continue; 432 return false; 433 } 434 PredInfo->PHITag = IncomingPHIVal; 435 436 WorkList.push_back(IncomingPHIVal); 437 } 438 } 439 return true; 440 } 441 442 /// RecordMatchingPHIs - For each PHI node that matches, record it in both 443 /// the BBMap and the AvailableVals mapping. 444 void RecordMatchingPHIs(BlockListTy *BlockList) { 445 for (typename BlockListTy::iterator I = BlockList->begin(), 446 E = BlockList->end(); I != E; ++I) 447 if (PhiT *PHI = (*I)->PHITag) { 448 BlkT *BB = PHI->getParent(); 449 ValT PHIVal = Traits::GetPHIValue(PHI); 450 (*AvailableVals)[BB] = PHIVal; 451 BBMap[BB]->AvailableVal = PHIVal; 452 } 453 } 454}; 455 456#undef DEBUG_TYPE // "ssaupdater" 457 458} // End llvm namespace 459 460#endif 461