LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Utils - SSAUpdaterImpl.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 157 162 96.9 %
Date: 2018-10-20 13:21:21 Functions: 15 20 75.0 %
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       25607 : 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      179370 :     BBInfo(BlkT *ThisBB, ValT V)
      70       25607 :       : 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       25607 :   explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
      87             :                           SmallVectorImpl<PhiT *> *Ins) :
      88       25607 :     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       25607 :   ValT GetValue(BlkT *BB) {
      95             :     SmallVector<BBInfo *, 100> BlockList;
      96       25607 :     BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
      97             : 
      98             :     // Special case: bail out if BB is unreachable.
      99       25607 :     if (BlockList.size() == 0) {
     100           6 :       ValT V = Traits::GetUndefVal(BB, Updater);
     101           6 :       (*AvailableVals)[BB] = V;
     102           6 :       return V;
     103             :     }
     104             : 
     105       25601 :     FindDominators(&BlockList, PseudoEntry);
     106       25601 :     FindPHIPlacement(&BlockList);
     107       25601 :     FindAvailableVals(&BlockList);
     108             : 
     109       25601 :     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       25607 :   BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
     117             :     SmallVector<BBInfo *, 10> RootList;
     118             :     SmallVector<BBInfo *, 64> WorkList;
     119             : 
     120       25607 :     BBInfo *Info = new (Allocator) BBInfo(BB, 0);
     121       25607 :     BBMap[BB] = Info;
     122       25607 :     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      130585 :     while (!WorkList.empty()) {
     129      104978 :       Info = WorkList.pop_back_val();
     130             :       Preds.clear();
     131      104978 :       Traits::FindPredecessorBlocks(Info->BB, &Preds);
     132      104978 :       Info->NumPreds = Preds.size();
     133      104978 :       if (Info->NumPreds == 0)
     134          13 :         Info->Preds = nullptr;
     135             :       else
     136      104965 :         Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(
     137             :             Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));
     138             : 
     139      261312 :       for (unsigned p = 0; p != Info->NumPreds; ++p) {
     140      156334 :         BlkT *Pred = Preds[p];
     141             :         // Check if BBMap already has a BBInfo for the predecessor block.
     142      156334 :         typename BBMapTy::value_type &BBMapBucket =
     143             :           BBMap.FindAndConstruct(Pred);
     144      156334 :         if (BBMapBucket.second) {
     145       28178 :           Info->Preds[p] = BBMapBucket.second;
     146       76963 :           continue;
     147             :         }
     148             : 
     149             :         // Create a new BBInfo for the predecessor.
     150      256312 :         ValT PredVal = AvailableVals->lookup(Pred);
     151      128156 :         BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
     152      128156 :         BBMapBucket.second = PredInfo;
     153      128156 :         Info->Preds[p] = PredInfo;
     154             : 
     155      128156 :         if (PredInfo->AvailableVal) {
     156       48785 :           RootList.push_back(PredInfo);
     157       48785 :           continue;
     158             :         }
     159       79371 :         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       74392 :     while (!RootList.empty()) {
     171       48785 :       Info = RootList.pop_back_val();
     172       48785 :       Info->IDom = PseudoEntry;
     173       48785 :       Info->BlkNum = -1;
     174       48785 :       WorkList.push_back(Info);
     175             :     }
     176             : 
     177      333107 :     while (!WorkList.empty()) {
     178      307500 :       Info = WorkList.back();
     179             : 
     180      307500 :       if (Info->BlkNum == -2) {
     181             :         // All the successors have been handled; assign the postorder number.
     182      153750 :         Info->BlkNum = BlkNum++;
     183             :         // If not a root, put it on the BlockList.
     184      153750 :         if (!Info->AvailableVal)
     185      104965 :           BlockList->push_back(Info);
     186             :         WorkList.pop_back();
     187      153750 :         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      153750 :       Info->BlkNum = -2;
     195             : 
     196             :       // Add unvisited successors to the work list.
     197             :       for (typename Traits::BlkSucc_iterator SI =
     198      153750 :              Traits::BlkSucc_begin(Info->BB),
     199      390360 :              E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {
     200      236610 :         BBInfo *SuccInfo = BBMap[*SI];
     201      236610 :         if (!SuccInfo || SuccInfo->BlkNum)
     202      131645 :           continue;
     203      104965 :         SuccInfo->BlkNum = -1;
     204      104965 :         WorkList.push_back(SuccInfo);
     205             :       }
     206             :     }
     207       25607 :     PseudoEntry->BlkNum = BlkNum;
     208       25607 :     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           0 :   BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {
     216      212389 :     while (Blk1 != Blk2) {
     217      223447 :       while (Blk1->BlkNum < Blk2->BlkNum) {
     218      109982 :         Blk1 = Blk1->IDom;
     219      109982 :         if (!Blk1)
     220           0 :           return Blk2;
     221             :       }
     222      220992 :       while (Blk2->BlkNum < Blk1->BlkNum) {
     223      111988 :         Blk2 = Blk2->IDom;
     224      111988 :         if (!Blk2)
     225           0 :           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       25601 :   void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
     242             :     bool Changed;
     243       51399 :     do {
     244             :       Changed = false;
     245             :       // Iterate over the list in reverse order, i.e., forward on CFG edges.
     246             :       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     247      262416 :              E = BlockList->rend(); I != E; ++I) {
     248      211017 :         BBInfo *Info = *I;
     249             :         BBInfo *NewIDom = nullptr;
     250             : 
     251             :         // Iterate through the block's predecessors.
     252      525419 :         for (unsigned p = 0; p != Info->NumPreds; ++p) {
     253      314402 :           BBInfo *Pred = Info->Preds[p];
     254             : 
     255             :           // Treat an unreachable predecessor as a definition with 'undef'.
     256      314402 :           if (Pred->BlkNum == 0) {
     257           7 :             Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
     258           7 :             (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
     259           7 :             Pred->DefBB = Pred;
     260           7 :             Pred->BlkNum = PseudoEntry->BlkNum;
     261           7 :             PseudoEntry->BlkNum++;
     262             :           }
     263             : 
     264      314402 :           if (!NewIDom)
     265             :             NewIDom = Pred;
     266             :           else
     267             :             NewIDom = IntersectDominators(NewIDom, Pred);
     268             :         }
     269             : 
     270             :         // Check if the IDom value has changed.
     271      211017 :         if (NewIDom && NewIDom != Info->IDom) {
     272      105178 :           Info->IDom = NewIDom;
     273             :           Changed = true;
     274             :         }
     275             :       }
     276             :     } while (Changed);
     277       25601 :   }
     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           0 :   bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {
     284      374793 :     for (; Pred != IDom; Pred = Pred->IDom) {
     285      156994 :       if (Pred->DefBB == Pred)
     286           0 :         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       25601 :   void FindPHIPlacement(BlockListTy *BlockList) {
     296             :     bool Changed;
     297       51202 :     do {
     298             :       Changed = false;
     299             :       // Iterate over the list in reverse order, i.e., forward on CFG edges.
     300             :       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     301      261132 :              E = BlockList->rend(); I != E; ++I) {
     302      209930 :         BBInfo *Info = *I;
     303             : 
     304             :         // If this block already needs a PHI, there is nothing to do here.
     305      209930 :         if (Info->DefBB == Info)
     306             :           continue;
     307             : 
     308             :         // Default to use the same def as the immediate dominator.
     309      187421 :         BBInfo *NewDefBB = Info->IDom->DefBB;
     310      405220 :         for (unsigned p = 0; p != Info->NumPreds; ++p) {
     311      480616 :           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      187421 :         if (NewDefBB != Info->DefBB) {
     320      104965 :           Info->DefBB = NewDefBB;
     321             :           Changed = true;
     322             :         }
     323             :       }
     324             :     } while (Changed);
     325       25601 :   }
     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       25601 :   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      104965 :     for (typename BlockListTy::iterator I = BlockList->begin(),
     337      130566 :            E = BlockList->end(); I != E; ++I) {
     338      104965 :       BBInfo *Info = *I;
     339             :       // Check if there needs to be a PHI in BB.
     340      104965 :       if (Info->DefBB != Info)
     341             :         continue;
     342             : 
     343             :       // Look for an existing PHI.
     344       22509 :       FindExistingPHI(Info->BB, BlockList);
     345       22509 :       if (Info->AvailableVal)
     346             :         continue;
     347             : 
     348       22118 :       ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
     349       22118 :       Info->AvailableVal = PHI;
     350       22118 :       (*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             :     for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
     356      130566 :            E = BlockList->rend(); I != E; ++I) {
     357      104965 :       BBInfo *Info = *I;
     358             : 
     359      104965 :       if (Info->DefBB != Info) {
     360             :         // Record the available value to speed up subsequent uses of this
     361             :         // SSAUpdater for the same value.
     362       82456 :         (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
     363       82847 :         continue;
     364             :       }
     365             : 
     366             :       // Check if this block contains a newly added PHI.
     367       22509 :       PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
     368       22509 :       if (!PHI)
     369             :         continue;
     370             : 
     371             :       // Iterate through the block's predecessors.
     372       68664 :       for (unsigned p = 0; p != Info->NumPreds; ++p) {
     373       46546 :         BBInfo *PredInfo = Info->Preds[p];
     374       46546 :         BlkT *Pred = PredInfo->BB;
     375             :         // Skip to the nearest preceding definition.
     376       46546 :         if (PredInfo->DefBB != PredInfo)
     377             :           PredInfo = PredInfo->DefBB;
     378       46546 :         Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
     379             :       }
     380             : 
     381             :       LLVM_DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");
     382             : 
     383             :       // If the client wants to know about all new instructions, tell it.
     384       22118 :       if (InsertedPHIs) InsertedPHIs->push_back(PHI);
     385             :     }
     386       25601 :   }
     387             : 
     388             :   /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
     389             :   /// them match what is needed.
     390       22509 :   void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
     391      173190 :     for (auto &SomePHI : BB->phis()) {
     392      128606 :       if (CheckIfPHIMatches(&SomePHI)) {
     393         391 :         RecordMatchingPHIs(BlockList);
     394         391 :         break;
     395             :       }
     396             :       // Match failed: clear all the PHITag values.
     397     1011981 :       for (typename BlockListTy::iterator I = BlockList->begin(),
     398     1140196 :              E = BlockList->end(); I != E; ++I)
     399     1011981 :         (*I)->PHITag = nullptr;
     400             :     }
     401       22509 :   }
     402             : 
     403             :   /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
     404             :   /// in the BBMap.
     405      128606 :   bool CheckIfPHIMatches(PhiT *PHI) {
     406             :     SmallVector<PhiT *, 20> WorkList;
     407      128606 :     WorkList.push_back(PHI);
     408             : 
     409             :     // Mark that the block containing this PHI has been visited.
     410      128606 :     BBMap[PHI->getParent()]->PHITag = PHI;
     411             : 
     412      130473 :     while (!WorkList.empty()) {
     413      130082 :       PHI = WorkList.pop_back_val();
     414             : 
     415             :       // Iterate through the PHI's incoming values.
     416             :       for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
     417      149259 :              E = Traits::PHI_end(PHI); I != E; ++I) {
     418             :         ValT IncomingVal = I.getIncomingValue();
     419      147392 :         BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
     420             :         // Skip to the nearest preceding definition.
     421      147392 :         if (PredInfo->DefBB != PredInfo)
     422             :           PredInfo = PredInfo->DefBB;
     423             : 
     424             :         // Check if it matches the expected value.
     425      147392 :         if (PredInfo->AvailableVal) {
     426      124480 :           if (IncomingVal == PredInfo->AvailableVal)
     427        1517 :             continue;
     428      128215 :           return false;
     429             :         }
     430             : 
     431             :         // Check if the value is a PHI in the correct block.
     432       22912 :         PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
     433       22912 :         if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
     434             :           return false;
     435             : 
     436             :         // If this block has already been visited, check if this PHI matches.
     437       17708 :         if (PredInfo->PHITag) {
     438          48 :           if (IncomingPHIVal == PredInfo->PHITag)
     439             :             continue;
     440             :           return false;
     441             :         }
     442       17660 :         PredInfo->PHITag = IncomingPHIVal;
     443             : 
     444       17660 :         WorkList.push_back(IncomingPHIVal);
     445             :       }
     446             :     }
     447             :     return true;
     448             :   }
     449             : 
     450             :   /// RecordMatchingPHIs - For each PHI node that matches, record it in both
     451             :   /// the BBMap and the AvailableVals mapping.
     452         391 :   void RecordMatchingPHIs(BlockListTy *BlockList) {
     453        2510 :     for (typename BlockListTy::iterator I = BlockList->begin(),
     454        2901 :            E = BlockList->end(); I != E; ++I)
     455        2510 :       if (PhiT *PHI = (*I)->PHITag) {
     456         560 :         BlkT *BB = PHI->getParent();
     457             :         ValT PHIVal = Traits::GetPHIValue(PHI);
     458         560 :         (*AvailableVals)[BB] = PHIVal;
     459         560 :         BBMap[BB]->AvailableVal = PHIVal;
     460             :       }
     461         391 :   }
     462             : };
     463             : 
     464             : } // end namespace llvm
     465             : 
     466             : #undef DEBUG_TYPE // "ssaupdater"
     467             : 
     468             : #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H

Generated by: LCOV version 1.13