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-07-13 00:08:38 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       16870 : 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      110776 :     BBInfo(BlkT *ThisBB, ValT V)
      70      110776 :       : 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       16870 :   explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
      87             :                           SmallVectorImpl<PhiT *> *Ins) :
      88       16870 :     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       16870 :   ValT GetValue(BlkT *BB) {
      95             :     SmallVector<BBInfo *, 100> BlockList;
      96       16870 :     BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
      97             : 
      98             :     // Special case: bail out if BB is unreachable.
      99       16870 :     if (BlockList.size() == 0) {
     100           6 :       ValT V = Traits::GetUndefVal(BB, Updater);
     101          12 :       (*AvailableVals)[BB] = V;
     102           6 :       return V;
     103             :     }
     104             : 
     105       16864 :     FindDominators(&BlockList, PseudoEntry);
     106       16864 :     FindPHIPlacement(&BlockList);
     107       16864 :     FindAvailableVals(&BlockList);
     108             : 
     109       33728 :     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       16870 :   BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
     117             :     SmallVector<BBInfo *, 10> RootList;
     118             :     SmallVector<BBInfo *, 64> WorkList;
     119             : 
     120       50610 :     BBInfo *Info = new (Allocator) BBInfo(BB, 0);
     121       33740 :     BBMap[BB] = Info;
     122       16870 :     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       77106 :     while (!WorkList.empty()) {
     129       60236 :       Info = WorkList.pop_back_val();
     130             :       Preds.clear();
     131       60236 :       Traits::FindPredecessorBlocks(Info->BB, &Preds);
     132       60236 :       Info->NumPreds = Preds.size();
     133       60236 :       if (Info->NumPreds == 0)
     134          12 :         Info->Preds = nullptr;
     135             :       else
     136       60224 :         Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(
     137       60224 :             Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));
     138             : 
     139      239862 :       for (unsigned p = 0; p != Info->NumPreds; ++p) {
     140      179626 :         BlkT *Pred = Preds[p];
     141             :         // Check if BBMap already has a BBInfo for the predecessor block.
     142       89813 :         typename BBMapTy::value_type &BBMapBucket =
     143             :           BBMap.FindAndConstruct(Pred);
     144      102590 :         if (BBMapBucket.second) {
     145       12777 :           Info->Preds[p] = BBMapBucket.second;
     146       59224 :           continue;
     147             :         }
     148             : 
     149             :         // Create a new BBInfo for the predecessor.
     150       77036 :         ValT PredVal = AvailableVals->lookup(Pred);
     151      154072 :         BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
     152       77036 :         BBMapBucket.second = PredInfo;
     153       77036 :         Info->Preds[p] = PredInfo;
     154             : 
     155      110706 :         if (PredInfo->AvailableVal) {
     156       33670 :           RootList.push_back(PredInfo);
     157       33670 :           continue;
     158             :         }
     159       43366 :         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       84210 :     while (!RootList.empty()) {
     171       33670 :       Info = RootList.pop_back_val();
     172       33670 :       Info->IDom = PseudoEntry;
     173       33670 :       Info->BlkNum = -1;
     174       33670 :       WorkList.push_back(Info);
     175             :     }
     176             : 
     177      204658 :     while (!WorkList.empty()) {
     178      187788 :       Info = WorkList.back();
     179             : 
     180      281682 :       if (Info->BlkNum == -2) {
     181             :         // All the successors have been handled; assign the postorder number.
     182       93894 :         Info->BlkNum = BlkNum++;
     183             :         // If not a root, put it on the BlockList.
     184       93894 :         if (!Info->AvailableVal)
     185       60224 :           BlockList->push_back(Info);
     186             :         WorkList.pop_back();
     187       93894 :         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       93894 :       Info->BlkNum = -2;
     195             : 
     196             :       // Add unvisited successors to the work list.
     197             :       for (typename Traits::BlkSucc_iterator SI =
     198       93894 :              Traits::BlkSucc_begin(Info->BB),
     199      237237 :              E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {
     200      286412 :         BBInfo *SuccInfo = BBMap[*SI];
     201      143343 :         if (!SuccInfo || SuccInfo->BlkNum)
     202       83119 :           continue;
     203       60224 :         SuccInfo->BlkNum = -1;
     204       60224 :         WorkList.push_back(SuccInfo);
     205             :       }
     206             :     }
     207       16870 :     PseudoEntry->BlkNum = BlkNum;
     208       16870 :     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      131786 :     while (Blk1 != Blk2) {
     217      139852 :       while (Blk1->BlkNum < Blk2->BlkNum) {
     218       65446 :         Blk1 = Blk1->IDom;
     219       65446 :         if (!Blk1)
     220             :           return Blk2;
     221             :       }
     222      135108 :       while (Blk2->BlkNum < Blk1->BlkNum) {
     223       62746 :         Blk2 = Blk2->IDom;
     224       62746 :         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       16864 :   void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
     242             :     bool Changed;
     243       33807 :     do {
     244             :       Changed = false;
     245             :       // Iterate over the list in reverse order, i.e., forward on CFG edges.
     246       33807 :       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     247       33807 :              E = BlockList->rend(); I != E; ++I) {
     248      120903 :         BBInfo *Info = *I;
     249             :         BBInfo *NewIDom = nullptr;
     250             : 
     251             :         // Iterate through the block's predecessors.
     252      481557 :         for (unsigned p = 0; p != Info->NumPreds; ++p) {
     253      180327 :           BBInfo *Pred = Info->Preds[p];
     254             : 
     255             :           // Treat an unreachable predecessor as a definition with 'undef'.
     256      180327 :           if (Pred->BlkNum == 0) {
     257          12 :             Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
     258          12 :             (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
     259           6 :             Pred->DefBB = Pred;
     260           6 :             Pred->BlkNum = PseudoEntry->BlkNum;
     261           6 :             PseudoEntry->BlkNum++;
     262             :           }
     263             : 
     264      180327 :           if (!NewIDom)
     265             :             NewIDom = Pred;
     266             :           else
     267             :             NewIDom = IntersectDominators(NewIDom, Pred);
     268             :         }
     269             : 
     270             :         // Check if the IDom value has changed.
     271      120903 :         if (NewIDom && NewIDom != Info->IDom) {
     272       60305 :           Info->IDom = NewIDom;
     273             :           Changed = true;
     274             :         }
     275             :       }
     276             :     } while (Changed);
     277       16864 :   }
     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      248836 :     for (; Pred != IDom; Pred = Pred->IDom) {
     285       77617 :       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       16864 :   void FindPHIPlacement(BlockListTy *BlockList) {
     296             :     bool Changed;
     297       33728 :     do {
     298             :       Changed = false;
     299             :       // Iterate over the list in reverse order, i.e., forward on CFG edges.
     300       33728 :       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     301       33728 :              E = BlockList->rend(); I != E; ++I) {
     302      120448 :         BBInfo *Info = *I;
     303             : 
     304             :         // If this block already needs a PHI, there is nothing to do here.
     305      120448 :         if (Info->DefBB == Info)
     306       16608 :           continue;
     307             : 
     308             :         // Default to use the same def as the immediate dominator.
     309      103840 :         BBInfo *NewDefBB = Info->IDom->DefBB;
     310      324260 :         for (unsigned p = 0; p != Info->NumPreds; ++p) {
     311      253636 :           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      103840 :         if (NewDefBB != Info->DefBB) {
     320       60224 :           Info->DefBB = NewDefBB;
     321             :           Changed = true;
     322             :         }
     323             :       }
     324             :     } while (Changed);
     325       16864 :   }
     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       16864 :   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       60224 :     for (typename BlockListTy::iterator I = BlockList->begin(),
     337       77088 :            E = BlockList->end(); I != E; ++I) {
     338       60224 :       BBInfo *Info = *I;
     339             :       // Check if there needs to be a PHI in BB.
     340       60224 :       if (Info->DefBB != Info)
     341       43616 :         continue;
     342             : 
     343             :       // Look for an existing PHI.
     344       16608 :       FindExistingPHI(Info->BB, BlockList);
     345       16608 :       if (Info->AvailableVal)
     346          56 :         continue;
     347             : 
     348       16552 :       ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
     349       16552 :       Info->AvailableVal = PHI;
     350       33104 :       (*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       16864 :     for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     356       16864 :            E = BlockList->rend(); I != E; ++I) {
     357       60224 :       BBInfo *Info = *I;
     358             : 
     359      103840 :       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       43616 :         if (Info->NumPreds > 1)
     363       19186 :           (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
     364       87288 :         continue;
     365             :       }
     366             : 
     367             :       // Check if this block contains a newly added PHI.
     368       33216 :       PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
     369       16608 :       if (!PHI)
     370          56 :         continue;
     371             : 
     372             :       // Iterate through the block's predecessors.
     373       85766 :       for (unsigned p = 0; p != Info->NumPreds; ++p) {
     374       34607 :         BBInfo *PredInfo = Info->Preds[p];
     375       34607 :         BlkT *Pred = PredInfo->BB;
     376             :         // Skip to the nearest preceding definition.
     377       34607 :         if (PredInfo->DefBB != PredInfo)
     378             :           PredInfo = PredInfo->DefBB;
     379       34607 :         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       16552 :       if (InsertedPHIs) InsertedPHIs->push_back(PHI);
     386             :     }
     387       16864 :   }
     388             : 
     389             :   /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
     390             :   /// them match what is needed.
     391       16608 :   void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
     392       16638 :     for (auto &SomePHI : BB->phis()) {
     393      102305 :       if (CheckIfPHIMatches(&SomePHI)) {
     394          56 :         RecordMatchingPHIs(BlockList);
     395          56 :         break;
     396             :       }
     397             :       // Match failed: clear all the PHITag values.
     398      632532 :       for (typename BlockListTy::iterator I = BlockList->begin(),
     399      734781 :              E = BlockList->end(); I != E; ++I)
     400      632532 :         (*I)->PHITag = nullptr;
     401             :     }
     402       16608 :   }
     403             : 
     404             :   /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
     405             :   /// in the BBMap.
     406      102305 :   bool CheckIfPHIMatches(PhiT *PHI) {
     407             :     SmallVector<PhiT *, 20> WorkList;
     408      102305 :     WorkList.push_back(PHI);
     409             : 
     410             :     // Mark that the block containing this PHI has been visited.
     411      204610 :     BBMap[PHI->getParent()]->PHITag = PHI;
     412             : 
     413      105229 :     while (!WorkList.empty()) {
     414      103711 :       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      121396 :              E = Traits::PHI_end(PHI); I != E; ++I) {
     419             :         ValT IncomingVal = I.getIncomingValue();
     420      239868 :         BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
     421             :         // Skip to the nearest preceding definition.
     422      119934 :         if (PredInfo->DefBB != PredInfo)
     423             :           PredInfo = PredInfo->DefBB;
     424             : 
     425             :         // Check if it matches the expected value.
     426      119934 :         if (PredInfo->AvailableVal) {
     427      101718 :           if (IncomingVal == PredInfo->AvailableVal)
     428         597 :             continue;
     429      102249 :           return false;
     430             :         }
     431             : 
     432             :         // Check if the value is a PHI in the correct block.
     433       18216 :         PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
     434       18216 :         if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
     435             :           return false;
     436             : 
     437             :         // If this block has already been visited, check if this PHI matches.
     438       17389 :         if (PredInfo->PHITag) {
     439           5 :           if (IncomingPHIVal == PredInfo->PHITag)
     440           5 :             continue;
     441             :           return false;
     442             :         }
     443       17384 :         PredInfo->PHITag = IncomingPHIVal;
     444             : 
     445       17384 :         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          56 :   void RecordMatchingPHIs(BlockListTy *BlockList) {
     454         302 :     for (typename BlockListTy::iterator I = BlockList->begin(),
     455         358 :            E = BlockList->end(); I != E; ++I)
     456         302 :       if (PhiT *PHI = (*I)->PHITag) {
     457          62 :         BlkT *BB = PHI->getParent();
     458             :         ValT PHIVal = Traits::GetPHIValue(PHI);
     459         124 :         (*AvailableVals)[BB] = PHIVal;
     460         124 :         BBMap[BB]->AvailableVal = PHIVal;
     461             :       }
     462          56 :   }
     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