LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Utils - SSAUpdaterImpl.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 190 190 100.0 %
Date: 2017-09-14 15:23:50 Functions: 15 16 93.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- SSAUpdaterImpl.h - SSA Updater Implementation -----------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file provides a template that implements the core algorithm for the
      11             : // SSAUpdater and MachineSSAUpdater.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
      16             : #define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
      17             : 
      18             : #include "llvm/ADT/DenseMap.h"
      19             : #include "llvm/ADT/SmallVector.h"
      20             : #include "llvm/IR/Instructions.h"
      21             : #include "llvm/IR/ValueHandle.h"
      22             : #include "llvm/Support/Allocator.h"
      23             : #include "llvm/Support/Debug.h"
      24             : 
      25             : #define DEBUG_TYPE "ssaupdater"
      26             : 
      27             : namespace llvm {
      28             : 
      29             : class CastInst;
      30             : class PHINode;
      31             : template<typename T> class SSAUpdaterTraits;
      32             : 
      33             : template<typename UpdaterT>
      34       30314 : class SSAUpdaterImpl {
      35             : private:
      36             :   UpdaterT *Updater;
      37             : 
      38             :   typedef SSAUpdaterTraits<UpdaterT> Traits;
      39             :   typedef typename Traits::BlkT BlkT;
      40             :   typedef typename Traits::ValT ValT;
      41             :   typedef typename Traits::PhiT PhiT;
      42             : 
      43             :   /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl.
      44             :   /// The predecessors of each block are cached here since pred_iterator is
      45             :   /// slow and we need to iterate over the blocks at least a few times.
      46             :   class BBInfo {
      47             :   public:
      48             :     BlkT *BB;          // Back-pointer to the corresponding block.
      49             :     ValT AvailableVal; // Value to use in this block.
      50             :     BBInfo *DefBB;     // Block that defines the available value.
      51             :     int BlkNum;        // Postorder number.
      52             :     BBInfo *IDom;      // Immediate dominator.
      53             :     unsigned NumPreds; // Number of predecessor blocks.
      54             :     BBInfo **Preds;    // Array[NumPreds] of predecessor blocks.
      55             :     PhiT *PHITag;      // Marker for existing PHIs that match.
      56             : 
      57       98629 :     BBInfo(BlkT *ThisBB, ValT V)
      58       68315 :       : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr), BlkNum(0),
      59      166944 :         IDom(nullptr), NumPreds(0), Preds(nullptr), PHITag(nullptr) {}
      60             :   };
      61             : 
      62             :   typedef DenseMap<BlkT*, ValT> AvailableValsTy;
      63             :   AvailableValsTy *AvailableVals;
      64             : 
      65             :   SmallVectorImpl<PhiT*> *InsertedPHIs;
      66             : 
      67             :   typedef SmallVectorImpl<BBInfo*> BlockListTy;
      68             :   typedef DenseMap<BlkT*, BBInfo*> BBMapTy;
      69             :   BBMapTy BBMap;
      70             :   BumpPtrAllocator Allocator;
      71             : 
      72             : public:
      73       15157 :   explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
      74             :                           SmallVectorImpl<PhiT*> *Ins) :
      75       45471 :     Updater(U), AvailableVals(A), InsertedPHIs(Ins) { }
      76             : 
      77             :   /// GetValue - Check to see if AvailableVals has an entry for the specified
      78             :   /// BB and if so, return it.  If not, construct SSA form by first
      79             :   /// calculating the required placement of PHIs and then inserting new PHIs
      80             :   /// where needed.
      81       15157 :   ValT GetValue(BlkT *BB) {
      82       30314 :     SmallVector<BBInfo*, 100> BlockList;
      83       15157 :     BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
      84             : 
      85             :     // Special case: bail out if BB is unreachable.
      86       15157 :     if (BlockList.size() == 0) {
      87          10 :       ValT V = Traits::GetUndefVal(BB, Updater);
      88          10 :       (*AvailableVals)[BB] = V;
      89           5 :       return V;
      90             :     }
      91             : 
      92       15152 :     FindDominators(&BlockList, PseudoEntry);
      93       15152 :     FindPHIPlacement(&BlockList);
      94       15152 :     FindAvailableVals(&BlockList);
      95             : 
      96       30304 :     return BBMap[BB]->DefBB->AvailableVal;
      97             :   }
      98             : 
      99             :   /// BuildBlockList - Starting from the specified basic block, traverse back
     100             :   /// through its predecessors until reaching blocks with known values.
     101             :   /// Create BBInfo structures for the blocks and append them to the block
     102             :   /// list.
     103       15157 :   BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
     104       30314 :     SmallVector<BBInfo*, 10> RootList;
     105       30314 :     SmallVector<BBInfo*, 64> WorkList;
     106             : 
     107       45471 :     BBInfo *Info = new (Allocator) BBInfo(BB, 0);
     108       30314 :     BBMap[BB] = Info;
     109       15157 :     WorkList.push_back(Info);
     110             : 
     111             :     // Search backward from BB, creating BBInfos along the way and stopping
     112             :     // when reaching blocks that define the value.  Record those defining
     113             :     // blocks on the RootList.
     114       15157 :     SmallVector<BlkT*, 10> Preds;
     115       68205 :     while (!WorkList.empty()) {
     116       53048 :       Info = WorkList.pop_back_val();
     117       53048 :       Preds.clear();
     118       53101 :       Traits::FindPredecessorBlocks(Info->BB, &Preds);
     119       53048 :       Info->NumPreds = Preds.size();
     120       53048 :       if (Info->NumPreds == 0)
     121           7 :         Info->Preds = nullptr;
     122             :       else
     123       53041 :         Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(
     124       53041 :             Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));
     125             : 
     126      211798 :       for (unsigned p = 0; p != Info->NumPreds; ++p) {
     127      158750 :         BlkT *Pred = Preds[p];
     128             :         // Check if BBMap already has a BBInfo for the predecessor block.
     129       79375 :         typename BBMapTy::value_type &BBMapBucket =
     130             :           BBMap.FindAndConstruct(Pred);
     131       90435 :         if (BBMapBucket.second) {
     132       11060 :           Info->Preds[p] = BBMapBucket.second;
     133       52544 :           continue;
     134             :         }
     135             : 
     136             :         // Create a new BBInfo for the predecessor.
     137      136630 :         ValT PredVal = AvailableVals->lookup(Pred);
     138      204945 :         BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
     139       68315 :         BBMapBucket.second = PredInfo;
     140       68315 :         Info->Preds[p] = PredInfo;
     141             : 
     142       98739 :         if (PredInfo->AvailableVal) {
     143       30424 :           RootList.push_back(PredInfo);
     144       30424 :           continue;
     145             :         }
     146       37891 :         WorkList.push_back(PredInfo);
     147             :       }
     148             :     }
     149             : 
     150             :     // Now that we know what blocks are backwards-reachable from the starting
     151             :     // block, do a forward depth-first traversal to assign postorder numbers
     152             :     // to those blocks.
     153       45471 :     BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0);
     154       15157 :     unsigned BlkNum = 1;
     155             : 
     156             :     // Initialize the worklist with the roots from the backward traversal.
     157       76005 :     while (!RootList.empty()) {
     158       30424 :       Info = RootList.pop_back_val();
     159       30424 :       Info->IDom = PseudoEntry;
     160       30424 :       Info->BlkNum = -1;
     161       30424 :       WorkList.push_back(Info);
     162             :     }
     163             : 
     164      182087 :     while (!WorkList.empty()) {
     165      333860 :       Info = WorkList.back();
     166             : 
     167      250395 :       if (Info->BlkNum == -2) {
     168             :         // All the successors have been handled; assign the postorder number.
     169       83465 :         Info->BlkNum = BlkNum++;
     170             :         // If not a root, put it on the BlockList.
     171       83465 :         if (!Info->AvailableVal)
     172       53041 :           BlockList->push_back(Info);
     173       83465 :         WorkList.pop_back();
     174       83465 :         continue;
     175             :       }
     176             : 
     177             :       // Leave this entry on the worklist, but set its BlkNum to mark that its
     178             :       // successors have been put on the worklist.  When it returns to the top
     179             :       // the list, after handling its successors, it will be assigned a
     180             :       // number.
     181       83465 :       Info->BlkNum = -2;
     182             : 
     183             :       // Add unvisited successors to the work list.
     184       83465 :       for (typename Traits::BlkSucc_iterator SI =
     185       83465 :              Traits::BlkSucc_begin(Info->BB),
     186      377516 :              E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {
     187      381115 :         BBInfo *SuccInfo = BBMap[*SI];
     188      127121 :         if (!SuccInfo || SuccInfo->BlkNum)
     189       74080 :           continue;
     190       53041 :         SuccInfo->BlkNum = -1;
     191       53041 :         WorkList.push_back(SuccInfo);
     192             :       }
     193             :     }
     194       15157 :     PseudoEntry->BlkNum = BlkNum;
     195       30314 :     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      117268 :     while (Blk1 != Blk2) {
     204      123254 :       while (Blk1->BlkNum < Blk2->BlkNum) {
     205       56919 :         Blk1 = Blk1->IDom;
     206       56919 :         if (!Blk1)
     207             :           return Blk2;
     208             :       }
     209      120269 :       while (Blk2->BlkNum < Blk1->BlkNum) {
     210       55925 :         Blk2 = Blk2->IDom;
     211       55925 :         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       15152 :   void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
     229             :     bool Changed;
     230       30386 :     do {
     231       30386 :       Changed = false;
     232             :       // Iterate over the list in reverse order, i.e., forward on CFG edges.
     233       30386 :       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     234      167322 :              E = BlockList->rend(); I != E; ++I) {
     235      106550 :         BBInfo *Info = *I;
     236      106550 :         BBInfo *NewIDom = nullptr;
     237             : 
     238             :         // Iterate through the block's predecessors.
     239      266024 :         for (unsigned p = 0; p != Info->NumPreds; ++p) {
     240      159474 :           BBInfo *Pred = Info->Preds[p];
     241             : 
     242             :           // Treat an unreachable predecessor as a definition with 'undef'.
     243      159474 :           if (Pred->BlkNum == 0) {
     244           4 :             Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
     245           4 :             (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
     246           2 :             Pred->DefBB = Pred;
     247           2 :             Pred->BlkNum = PseudoEntry->BlkNum;
     248           2 :             PseudoEntry->BlkNum++;
     249             :           }
     250             : 
     251      159474 :           if (!NewIDom)
     252             :             NewIDom = Pred;
     253             :           else
     254             :             NewIDom = IntersectDominators(NewIDom, Pred);
     255             :         }
     256             : 
     257             :         // Check if the IDom value has changed.
     258      106550 :         if (NewIDom && NewIDom != Info->IDom) {
     259       53125 :           Info->IDom = NewIDom;
     260       53125 :           Changed = true;
     261             :         }
     262             :       }
     263             :     } while (Changed);
     264       15152 :   }
     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      213830 :     for (; Pred != IDom; Pred = Pred->IDom) {
     272       66678 :       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       15152 :   void FindPHIPlacement(BlockListTy *BlockList) {
     283             :     bool Changed;
     284       30304 :     do {
     285       30304 :       Changed = false;
     286             :       // Iterate over the list in reverse order, i.e., forward on CFG edges.
     287       30304 :       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     288      166690 :              E = BlockList->rend(); I != E; ++I) {
     289      106082 :         BBInfo *Info = *I;
     290             : 
     291             :         // If this block already needs a PHI, there is nothing to do here.
     292      106082 :         if (Info->DefBB == Info)
     293       15160 :           continue;
     294             : 
     295             :         // Default to use the same def as the immediate dominator.
     296       90922 :         BBInfo *NewDefBB = Info->IDom->DefBB;
     297      186556 :         for (unsigned p = 0; p != Info->NumPreds; ++p) {
     298      221588 :           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       90922 :         if (NewDefBB != Info->DefBB) {
     307       53041 :           Info->DefBB = NewDefBB;
     308       53041 :           Changed = true;
     309             :         }
     310             :       }
     311             :     } while (Changed);
     312       15152 :   }
     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       15152 :   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       83345 :     for (typename BlockListTy::iterator I = BlockList->begin(),
     324       30304 :            E = BlockList->end(); I != E; ++I) {
     325       53041 :       BBInfo *Info = *I;
     326             :       // Check if there needs to be a PHI in BB.
     327       53041 :       if (Info->DefBB != Info)
     328       37881 :         continue;
     329             : 
     330             :       // Look for an existing PHI.
     331       15160 :       FindExistingPHI(Info->BB, BlockList);
     332       15160 :       if (Info->AvailableVal)
     333          45 :         continue;
     334             : 
     335       15115 :       ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
     336       15115 :       Info->AvailableVal = PHI;
     337       30230 :       (*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       15152 :     for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     343       83345 :            E = BlockList->rend(); I != E; ++I) {
     344       53041 :       BBInfo *Info = *I;
     345             : 
     346       90922 :       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       37881 :         if (Info->NumPreds > 1)
     350       16500 :           (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
     351       75807 :         continue;
     352             :       }
     353             : 
     354             :       // Check if this block contains a newly added PHI.
     355       30320 :       PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
     356       15160 :       if (!PHI)
     357          45 :         continue;
     358             : 
     359             :       // Iterate through the block's predecessors.
     360       78087 :       for (unsigned p = 0; p != Info->NumPreds; ++p) {
     361       31486 :         BBInfo *PredInfo = Info->Preds[p];
     362       31486 :         BlkT *Pred = PredInfo->BB;
     363             :         // Skip to the nearest preceding definition.
     364       31486 :         if (PredInfo->DefBB != PredInfo)
     365        3136 :           PredInfo = PredInfo->DefBB;
     366       62931 :         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       15115 :       if (InsertedPHIs) InsertedPHIs->push_back(PHI);
     373             :     }
     374       15152 :   }
     375             : 
     376             :   /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
     377             :   /// them match what is needed.
     378       15160 :   void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
     379       30320 :     for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end();
     380      113882 :          BBI != BBE; ++BBI) {
     381      212649 :       PhiT *SomePHI = Traits::InstrIsPHI(&*BBI);
     382             :       if (!SomePHI)
     383             :         break;
     384       98767 :       if (CheckIfPHIMatches(SomePHI)) {
     385          45 :         RecordMatchingPHIs(BlockList);
     386          45 :         break;
     387             :       }
     388             :       // Match failed: clear all the PHITag values.
     389      772326 :       for (typename BlockListTy::iterator I = BlockList->begin(),
     390      197444 :              E = BlockList->end(); I != E; ++I)
     391      574882 :         (*I)->PHITag = nullptr;
     392             :     }
     393       15160 :   }
     394             : 
     395             :   /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
     396             :   /// in the BBMap.
     397       98767 :   bool CheckIfPHIMatches(PhiT *PHI) {
     398      197534 :     SmallVector<PhiT*, 20> WorkList;
     399       98767 :     WorkList.push_back(PHI);
     400             : 
     401             :     // Mark that the block containing this PHI has been visited.
     402      197534 :     BBMap[PHI->getParent()]->PHITag = PHI;
     403             : 
     404      101543 :     while (!WorkList.empty()) {
     405      100110 :       PHI = WorkList.pop_back_val();
     406             : 
     407             :       // Iterate through the PHI's incoming values.
     408      200220 :       for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
     409      316037 :              E = Traits::PHI_end(PHI); I != E; ++I) {
     410      228858 :         ValT IncomingVal = I.getIncomingValue();
     411      343287 :         BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
     412             :         // Skip to the nearest preceding definition.
     413      114429 :         if (PredInfo->DefBB != PredInfo)
     414        4667 :           PredInfo = PredInfo->DefBB;
     415             : 
     416             :         // Check if it matches the expected value.
     417      114429 :         if (PredInfo->AvailableVal) {
     418       98261 :           if (IncomingVal == PredInfo->AvailableVal)
     419         543 :             continue;
     420       98722 :           return false;
     421             :         }
     422             : 
     423             :         // Check if the value is a PHI in the correct block.
     424       32336 :         PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
     425       16168 :         if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
     426             :           return false;
     427             : 
     428             :         // If this block has already been visited, check if this PHI matches.
     429       15451 :         if (PredInfo->PHITag) {
     430          31 :           if (IncomingPHIVal == PredInfo->PHITag)
     431          31 :             continue;
     432             :           return false;
     433             :         }
     434       15420 :         PredInfo->PHITag = IncomingPHIVal;
     435             : 
     436       15420 :         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          45 :   void RecordMatchingPHIs(BlockListTy *BlockList) {
     445         331 :     for (typename BlockListTy::iterator I = BlockList->begin(),
     446          90 :            E = BlockList->end(); I != E; ++I)
     447         241 :       if (PhiT *PHI = (*I)->PHITag) {
     448          47 :         BlkT *BB = PHI->getParent();
     449          47 :         ValT PHIVal = Traits::GetPHIValue(PHI);
     450          94 :         (*AvailableVals)[BB] = PHIVal;
     451          94 :         BBMap[BB]->AvailableVal = PHIVal;
     452             :       }
     453          45 :   }
     454             : };
     455             : 
     456             : } // end llvm namespace
     457             : 
     458             : #undef DEBUG_TYPE // "ssaupdater"
     459             : 
     460             : #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H

Generated by: LCOV version 1.13