LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Utils - SSAUpdaterImpl.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 167 167 100.0 %
Date: 2018-05-20 00:06:23 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/Support/Allocator.h"
      21             : #include "llvm/Support/Debug.h"
      22             : #include "llvm/Support/raw_ostream.h"
      23             : 
      24             : #define DEBUG_TYPE "ssaupdater"
      25             : 
      26             : namespace llvm {
      27             : 
      28             : template<typename T> class SSAUpdaterTraits;
      29             : 
      30             : template<typename UpdaterT>
      31       14984 : class SSAUpdaterImpl {
      32             : private:
      33             :   UpdaterT *Updater;
      34             : 
      35             :   using Traits = SSAUpdaterTraits<UpdaterT>;
      36             :   using BlkT = typename Traits::BlkT;
      37             :   using ValT = typename Traits::ValT;
      38             :   using PhiT = typename Traits::PhiT;
      39             : 
      40             :   /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl.
      41             :   /// The predecessors of each block are cached here since pred_iterator is
      42             :   /// slow and we need to iterate over the blocks at least a few times.
      43             :   class BBInfo {
      44             :   public:
      45             :     // Back-pointer to the corresponding block.
      46             :     BlkT *BB;
      47             : 
      48             :     // Value to use in this block.
      49             :     ValT AvailableVal;
      50             : 
      51             :     // Block that defines the available value.
      52             :     BBInfo *DefBB;
      53             : 
      54             :     // Postorder number.
      55             :     int BlkNum = 0;
      56             : 
      57             :     // Immediate dominator.
      58             :     BBInfo *IDom = nullptr;
      59             : 
      60             :     // Number of predecessor blocks.
      61             :     unsigned NumPreds = 0;
      62             : 
      63             :     // Array[NumPreds] of predecessor blocks.
      64             :     BBInfo **Preds = nullptr;
      65             : 
      66             :     // Marker for existing PHIs that match.
      67             :     PhiT *PHITag = nullptr;
      68             : 
      69      100711 :     BBInfo(BlkT *ThisBB, ValT V)
      70      100711 :       : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {}
      71             :   };
      72             : 
      73             :   using AvailableValsTy = DenseMap<BlkT *, ValT>;
      74             : 
      75             :   AvailableValsTy *AvailableVals;
      76             : 
      77             :   SmallVectorImpl<PhiT *> *InsertedPHIs;
      78             : 
      79             :   using BlockListTy = SmallVectorImpl<BBInfo *>;
      80             :   using BBMapTy = DenseMap<BlkT *, BBInfo *>;
      81             : 
      82             :   BBMapTy BBMap;
      83             :   BumpPtrAllocator Allocator;
      84             : 
      85             : public:
      86       14984 :   explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
      87             :                           SmallVectorImpl<PhiT *> *Ins) :
      88       14984 :     Updater(U), AvailableVals(A), InsertedPHIs(Ins) {}
      89             : 
      90             :   /// GetValue - Check to see if AvailableVals has an entry for the specified
      91             :   /// BB and if so, return it.  If not, construct SSA form by first
      92             :   /// calculating the required placement of PHIs and then inserting new PHIs
      93             :   /// where needed.
      94       14984 :   ValT GetValue(BlkT *BB) {
      95             :     SmallVector<BBInfo *, 100> BlockList;
      96       14984 :     BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
      97             : 
      98             :     // Special case: bail out if BB is unreachable.
      99       14984 :     if (BlockList.size() == 0) {
     100           6 :       ValT V = Traits::GetUndefVal(BB, Updater);
     101          12 :       (*AvailableVals)[BB] = V;
     102           6 :       return V;
     103             :     }
     104             : 
     105       14978 :     FindDominators(&BlockList, PseudoEntry);
     106       14978 :     FindPHIPlacement(&BlockList);
     107       14978 :     FindAvailableVals(&BlockList);
     108             : 
     109       29956 :     return BBMap[BB]->DefBB->AvailableVal;
     110             :   }
     111             : 
     112             :   /// BuildBlockList - Starting from the specified basic block, traverse back
     113             :   /// through its predecessors until reaching blocks with known values.
     114             :   /// Create BBInfo structures for the blocks and append them to the block
     115             :   /// list.
     116       14984 :   BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
     117             :     SmallVector<BBInfo *, 10> RootList;
     118             :     SmallVector<BBInfo *, 64> WorkList;
     119             : 
     120       44952 :     BBInfo *Info = new (Allocator) BBInfo(BB, 0);
     121       29968 :     BBMap[BB] = Info;
     122       14984 :     WorkList.push_back(Info);
     123             : 
     124             :     // Search backward from BB, creating BBInfos along the way and stopping
     125             :     // when reaching blocks that define the value.  Record those defining
     126             :     // blocks on the RootList.
     127             :     SmallVector<BlkT *, 10> Preds;
     128       70412 :     while (!WorkList.empty()) {
     129       55428 :       Info = WorkList.pop_back_val();
     130             :       Preds.clear();
     131       55428 :       Traits::FindPredecessorBlocks(Info->BB, &Preds);
     132       55428 :       Info->NumPreds = Preds.size();
     133       55428 :       if (Info->NumPreds == 0)
     134          10 :         Info->Preds = nullptr;
     135             :       else
     136       55418 :         Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(
     137       55418 :             Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));
     138             : 
     139      219808 :       for (unsigned p = 0; p != Info->NumPreds; ++p) {
     140      164380 :         BlkT *Pred = Preds[p];
     141             :         // Check if BBMap already has a BBInfo for the predecessor block.
     142       82190 :         typename BBMapTy::value_type &BBMapBucket =
     143             :           BBMap.FindAndConstruct(Pred);
     144       93637 :         if (BBMapBucket.second) {
     145       11447 :           Info->Preds[p] = BBMapBucket.second;
     146       53193 :           continue;
     147             :         }
     148             : 
     149             :         // Create a new BBInfo for the predecessor.
     150       70743 :         ValT PredVal = AvailableVals->lookup(Pred);
     151      141486 :         BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
     152       70743 :         BBMapBucket.second = PredInfo;
     153       70743 :         Info->Preds[p] = PredInfo;
     154             : 
     155      101042 :         if (PredInfo->AvailableVal) {
     156       30299 :           RootList.push_back(PredInfo);
     157       30299 :           continue;
     158             :         }
     159       40444 :         WorkList.push_back(PredInfo);
     160             :       }
     161             :     }
     162             : 
     163             :     // Now that we know what blocks are backwards-reachable from the starting
     164             :     // block, do a forward depth-first traversal to assign postorder numbers
     165             :     // to those blocks.
     166             :     BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0);
     167             :     unsigned BlkNum = 1;
     168             : 
     169             :     // Initialize the worklist with the roots from the backward traversal.
     170       75582 :     while (!RootList.empty()) {
     171       30299 :       Info = RootList.pop_back_val();
     172       30299 :       Info->IDom = PseudoEntry;
     173       30299 :       Info->BlkNum = -1;
     174       30299 :       WorkList.push_back(Info);
     175             :     }
     176             : 
     177      186418 :     while (!WorkList.empty()) {
     178      171434 :       Info = WorkList.back();
     179             : 
     180      257151 :       if (Info->BlkNum == -2) {
     181             :         // All the successors have been handled; assign the postorder number.
     182       85717 :         Info->BlkNum = BlkNum++;
     183             :         // If not a root, put it on the BlockList.
     184       85717 :         if (!Info->AvailableVal)
     185       55418 :           BlockList->push_back(Info);
     186             :         WorkList.pop_back();
     187       85717 :         continue;
     188             :       }
     189             : 
     190             :       // Leave this entry on the worklist, but set its BlkNum to mark that its
     191             :       // successors have been put on the worklist.  When it returns to the top
     192             :       // the list, after handling its successors, it will be assigned a
     193             :       // number.
     194       85717 :       Info->BlkNum = -2;
     195             : 
     196             :       // Add unvisited successors to the work list.
     197             :       for (typename Traits::BlkSucc_iterator SI =
     198       85717 :              Traits::BlkSucc_begin(Info->BB),
     199      216875 :              E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {
     200      262042 :         BBInfo *SuccInfo = BBMap[*SI];
     201      131158 :         if (!SuccInfo || SuccInfo->BlkNum)
     202       75740 :           continue;
     203       55418 :         SuccInfo->BlkNum = -1;
     204       55418 :         WorkList.push_back(SuccInfo);
     205             :       }
     206             :     }
     207       14984 :     PseudoEntry->BlkNum = BlkNum;
     208       14984 :     return PseudoEntry;
     209             :   }
     210             : 
     211             :   /// IntersectDominators - This is the dataflow lattice "meet" operation for
     212             :   /// finding dominators.  Given two basic blocks, it walks up the dominator
     213             :   /// tree until it finds a common dominator of both.  It uses the postorder
     214             :   /// number of the blocks to determine how to do that.
     215             :   BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {
     216      118790 :     while (Blk1 != Blk2) {
     217      126544 :       while (Blk1->BlkNum < Blk2->BlkNum) {
     218       59658 :         Blk1 = Blk1->IDom;
     219       59658 :         if (!Blk1)
     220             :           return Blk2;
     221             :       }
     222      122225 :       while (Blk2->BlkNum < Blk1->BlkNum) {
     223       57243 :         Blk2 = Blk2->IDom;
     224       57243 :         if (!Blk2)
     225             :           return Blk1;
     226             :       }
     227             :     }
     228             :     return Blk1;
     229             :   }
     230             : 
     231             :   /// FindDominators - Calculate the dominator tree for the subset of the CFG
     232             :   /// corresponding to the basic blocks on the BlockList.  This uses the
     233             :   /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey
     234             :   /// and Kennedy, published in Software--Practice and Experience, 2001,
     235             :   /// 4:1-10.  Because the CFG subset does not include any edges leading into
     236             :   /// blocks that define the value, the results are not the usual dominator
     237             :   /// tree.  The CFG subset has a single pseudo-entry node with edges to a set
     238             :   /// of root nodes for blocks that define the value.  The dominators for this
     239             :   /// subset CFG are not the standard dominators but they are adequate for
     240             :   /// placing PHIs within the subset CFG.
     241       14978 :   void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
     242             :     bool Changed;
     243       30034 :     do {
     244             :       Changed = false;
     245             :       // Iterate over the list in reverse order, i.e., forward on CFG edges.
     246       30034 :       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     247       30034 :              E = BlockList->rend(); I != E; ++I) {
     248      111335 :         BBInfo *Info = *I;
     249             :         BBInfo *NewIDom = nullptr;
     250             : 
     251             :         // Iterate through the block's predecessors.
     252      441621 :         for (unsigned p = 0; p != Info->NumPreds; ++p) {
     253      165143 :           BBInfo *Pred = Info->Preds[p];
     254             : 
     255             :           // Treat an unreachable predecessor as a definition with 'undef'.
     256      165143 :           if (Pred->BlkNum == 0) {
     257           8 :             Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
     258           8 :             (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
     259           4 :             Pred->DefBB = Pred;
     260           4 :             Pred->BlkNum = PseudoEntry->BlkNum;
     261           4 :             PseudoEntry->BlkNum++;
     262             :           }
     263             : 
     264      165143 :           if (!NewIDom)
     265             :             NewIDom = Pred;
     266             :           else
     267             :             NewIDom = IntersectDominators(NewIDom, Pred);
     268             :         }
     269             : 
     270             :         // Check if the IDom value has changed.
     271      111335 :         if (NewIDom && NewIDom != Info->IDom) {
     272       55498 :           Info->IDom = NewIDom;
     273             :           Changed = true;
     274             :         }
     275             :       }
     276             :     } while (Changed);
     277       14978 :   }
     278             : 
     279             :   /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for
     280             :   /// any blocks containing definitions of the value.  If one is found, then
     281             :   /// the successor of Pred is in the dominance frontier for the definition,
     282             :   /// and this function returns true.
     283             :   bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {
     284      234866 :     for (; Pred != IDom; Pred = Pred->IDom) {
     285       72814 :       if (Pred->DefBB == Pred)
     286             :         return true;
     287             :     }
     288             :     return false;
     289             :   }
     290             : 
     291             :   /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers
     292             :   /// of the known definitions.  Iteratively add PHIs in the dom frontiers
     293             :   /// until nothing changes.  Along the way, keep track of the nearest
     294             :   /// dominating definitions for non-PHI blocks.
     295       14978 :   void FindPHIPlacement(BlockListTy *BlockList) {
     296             :     bool Changed;
     297       29956 :     do {
     298             :       Changed = false;
     299             :       // Iterate over the list in reverse order, i.e., forward on CFG edges.
     300       29956 :       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     301       29956 :              E = BlockList->rend(); I != E; ++I) {
     302      110836 :         BBInfo *Info = *I;
     303             : 
     304             :         // If this block already needs a PHI, there is nothing to do here.
     305      110836 :         if (Info->DefBB == Info)
     306       14523 :           continue;
     307             : 
     308             :         // Default to use the same def as the immediate dominator.
     309       96313 :         BBInfo *NewDefBB = Info->IDom->DefBB;
     310      303835 :         for (unsigned p = 0; p != Info->NumPreds; ++p) {
     311      236568 :           if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
     312             :             // Need a PHI here.
     313             :             NewDefBB = Info;
     314             :             break;
     315             :           }
     316             :         }
     317             : 
     318             :         // Check if anything changed.
     319       96313 :         if (NewDefBB != Info->DefBB) {
     320       55418 :           Info->DefBB = NewDefBB;
     321             :           Changed = true;
     322             :         }
     323             :       }
     324             :     } while (Changed);
     325       14978 :   }
     326             : 
     327             :   /// FindAvailableVal - If this block requires a PHI, first check if an
     328             :   /// existing PHI matches the PHI placement and reaching definitions computed
     329             :   /// earlier, and if not, create a new PHI.  Visit all the block's
     330             :   /// predecessors to calculate the available value for each one and fill in
     331             :   /// the incoming values for a new PHI.
     332       14978 :   void FindAvailableVals(BlockListTy *BlockList) {
     333             :     // Go through the worklist in forward order (i.e., backward through the CFG)
     334             :     // and check if existing PHIs can be used.  If not, create empty PHIs where
     335             :     // they are needed.
     336       55418 :     for (typename BlockListTy::iterator I = BlockList->begin(),
     337       70396 :            E = BlockList->end(); I != E; ++I) {
     338       55418 :       BBInfo *Info = *I;
     339             :       // Check if there needs to be a PHI in BB.
     340       55418 :       if (Info->DefBB != Info)
     341       40895 :         continue;
     342             : 
     343             :       // Look for an existing PHI.
     344       14523 :       FindExistingPHI(Info->BB, BlockList);
     345       14523 :       if (Info->AvailableVal)
     346          55 :         continue;
     347             : 
     348       14468 :       ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
     349       14468 :       Info->AvailableVal = PHI;
     350       28936 :       (*AvailableVals)[Info->BB] = PHI;
     351             :     }
     352             : 
     353             :     // Now go back through the worklist in reverse order to fill in the
     354             :     // arguments for any new PHIs added in the forward traversal.
     355       14978 :     for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     356       14978 :            E = BlockList->rend(); I != E; ++I) {
     357       55418 :       BBInfo *Info = *I;
     358             : 
     359       96313 :       if (Info->DefBB != Info) {
     360             :         // Record the available value at join nodes to speed up subsequent
     361             :         // uses of this SSAUpdater for the same value.
     362       40895 :         if (Info->NumPreds > 1)
     363       18260 :           (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
     364       81845 :         continue;
     365             :       }
     366             : 
     367             :       // Check if this block contains a newly added PHI.
     368       29046 :       PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
     369       14523 :       if (!PHI)
     370          55 :         continue;
     371             : 
     372             :       // Iterate through the block's predecessors.
     373       74894 :       for (unsigned p = 0; p != Info->NumPreds; ++p) {
     374       30213 :         BBInfo *PredInfo = Info->Preds[p];
     375       30213 :         BlkT *Pred = PredInfo->BB;
     376             :         // Skip to the nearest preceding definition.
     377       30213 :         if (PredInfo->DefBB != PredInfo)
     378             :           PredInfo = PredInfo->DefBB;
     379       30213 :         Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
     380             :       }
     381             : 
     382             :       LLVM_DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");
     383             : 
     384             :       // If the client wants to know about all new instructions, tell it.
     385       14468 :       if (InsertedPHIs) InsertedPHIs->push_back(PHI);
     386             :     }
     387       14978 :   }
     388             : 
     389             :   /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
     390             :   /// them match what is needed.
     391       14523 :   void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
     392       14553 :     for (auto &SomePHI : BB->phis()) {
     393       99319 :       if (CheckIfPHIMatches(&SomePHI)) {
     394          55 :         RecordMatchingPHIs(BlockList);
     395          55 :         break;
     396             :       }
     397             :       // Match failed: clear all the PHITag values.
     398      611347 :       for (typename BlockListTy::iterator I = BlockList->begin(),
     399      710611 :              E = BlockList->end(); I != E; ++I)
     400      611347 :         (*I)->PHITag = nullptr;
     401             :     }
     402       14523 :   }
     403             : 
     404             :   /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
     405             :   /// in the BBMap.
     406       99319 :   bool CheckIfPHIMatches(PhiT *PHI) {
     407             :     SmallVector<PhiT *, 20> WorkList;
     408       99319 :     WorkList.push_back(PHI);
     409             : 
     410             :     // Mark that the block containing this PHI has been visited.
     411      198638 :     BBMap[PHI->getParent()]->PHITag = PHI;
     412             : 
     413      102245 :     while (!WorkList.empty()) {
     414      100727 :       PHI = WorkList.pop_back_val();
     415             : 
     416             :       // Iterate through the PHI's incoming values.
     417             :       for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
     418      117571 :              E = Traits::PHI_end(PHI); I != E; ++I) {
     419             :         ValT IncomingVal = I.getIncomingValue();
     420      232216 :         BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
     421             :         // Skip to the nearest preceding definition.
     422      116108 :         if (PredInfo->DefBB != PredInfo)
     423             :           PredInfo = PredInfo->DefBB;
     424             : 
     425             :         // Check if it matches the expected value.
     426      116108 :         if (PredInfo->AvailableVal) {
     427       99399 :           if (IncomingVal == PredInfo->AvailableVal)
     428         611 :             continue;
     429       99264 :           return false;
     430             :         }
     431             : 
     432             :         // Check if the value is a PHI in the correct block.
     433       16709 :         PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
     434       16709 :         if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
     435             :           return false;
     436             : 
     437             :         // If this block has already been visited, check if this PHI matches.
     438       16549 :         if (PredInfo->PHITag) {
     439          21 :           if (IncomingPHIVal == PredInfo->PHITag)
     440          21 :             continue;
     441             :           return false;
     442             :         }
     443       16528 :         PredInfo->PHITag = IncomingPHIVal;
     444             : 
     445       16528 :         WorkList.push_back(IncomingPHIVal);
     446             :       }
     447             :     }
     448             :     return true;
     449             :   }
     450             : 
     451             :   /// RecordMatchingPHIs - For each PHI node that matches, record it in both
     452             :   /// the BBMap and the AvailableVals mapping.
     453          55 :   void RecordMatchingPHIs(BlockListTy *BlockList) {
     454         300 :     for (typename BlockListTy::iterator I = BlockList->begin(),
     455         355 :            E = BlockList->end(); I != E; ++I)
     456         300 :       if (PhiT *PHI = (*I)->PHITag) {
     457          61 :         BlkT *BB = PHI->getParent();
     458             :         ValT PHIVal = Traits::GetPHIValue(PHI);
     459         122 :         (*AvailableVals)[BB] = PHIVal;
     460         122 :         BBMap[BB]->AvailableVal = PHIVal;
     461             :       }
     462          55 :   }
     463             : };
     464             : 
     465             : } // end namespace llvm
     466             : 
     467             : #undef DEBUG_TYPE // "ssaupdater"
     468             : 
     469             : #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H

Generated by: LCOV version 1.13