Home | History | Annotate | Download | only in src 
      1 //===- subzero/src/IceLiveness.cpp - Liveness analysis implementation -----===//
      2 //
      3 //                        The Subzero Code Generator
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 ///
     10 /// \file
     11 /// \brief Provides some of the support for the Liveness class.
     12 
     13 /// In particular, it handles the sparsity representation of the mapping
     14 /// between Variables and CfgNodes. The idea is that since most variables are
     15 /// used only within a single basic block, we can partition the variables into
     16 /// "local" and "global" sets. Instead of sizing and indexing vectors according
     17 /// to Variable::Number, we create a mapping such that global variables are
     18 /// mapped to low indexes that are common across nodes, and local variables are
     19 /// mapped to a higher index space that is shared across nodes.
     20 ///
     21 //===----------------------------------------------------------------------===//
     22 
     23 #include "IceLiveness.h"
     24 
     25 #include "IceCfg.h"
     26 #include "IceCfgNode.h"
     27 #include "IceDefs.h"
     28 #include "IceInst.h"
     29 #include "IceOperand.h"
     30 
     31 namespace Ice {
     32 
     33 // Initializes the basic liveness-related data structures for full liveness
     34 // analysis (IsFullInit=true), or for incremental update after phi lowering
     35 // (IsFullInit=false). In the latter case, FirstNode points to the first node
     36 // added since starting phi lowering, and FirstVar points to the first Variable
     37 // added since starting phi lowering.
     38 void Liveness::initInternal(NodeList::const_iterator FirstNode,
     39                             VarList::const_iterator FirstVar, bool IsFullInit) {
     40   // Initialize most of the container sizes.
     41   SizeT NumVars = Func->getVariables().size();
     42   SizeT NumNodes = Func->getNumNodes();
     43   VariablesMetadata *VMetadata = Func->getVMetadata();
     44   Nodes.resize(NumNodes);
     45   VarToLiveMap.resize(NumVars);
     46 
     47   // Count the number of globals, and the number of locals for each block.
     48   SizeT TmpNumGlobals = 0;
     49   for (auto I = FirstVar, E = Func->getVariables().end(); I != E; ++I) {
     50     Variable *Var = *I;
     51     if (VMetadata->isMultiBlock(Var)) {
     52       ++TmpNumGlobals;
     53     } else if (VMetadata->isSingleBlock(Var)) {
     54       SizeT Index = VMetadata->getLocalUseNode(Var)->getIndex();
     55       ++Nodes[Index].NumLocals;
     56     }
     57   }
     58   if (IsFullInit)
     59     NumGlobals = TmpNumGlobals;
     60   else
     61     assert(TmpNumGlobals == 0);
     62 
     63   // Resize each LivenessNode::LiveToVarMap, and the global LiveToVarMap. Reset
     64   // the counts to 0.
     65   for (auto I = FirstNode, E = Func->getNodes().end(); I != E; ++I) {
     66     LivenessNode &N = Nodes[(*I)->getIndex()];
     67     N.LiveToVarMap.assign(N.NumLocals, nullptr);
     68     N.NumLocals = 0;
     69     N.NumNonDeadPhis = 0;
     70   }
     71   if (IsFullInit)
     72     LiveToVarMap.assign(NumGlobals, nullptr);
     73 
     74   // Initialize the bitmask of which variables to track.
     75   RangeMask.resize(NumVars);
     76   RangeMask.set(0, NumVars); // Track all variables by default.
     77 
     78   // Sort each variable into the appropriate LiveToVarMap. Set VarToLiveMap.
     79   // Set RangeMask correctly for each variable.
     80   TmpNumGlobals = 0;
     81   for (auto I = FirstVar, E = Func->getVariables().end(); I != E; ++I) {
     82     Variable *Var = *I;
     83     SizeT VarIndex = Var->getIndex();
     84     SizeT LiveIndex = InvalidLiveIndex;
     85     if (VMetadata->isMultiBlock(Var)) {
     86       LiveIndex = TmpNumGlobals++;
     87       LiveToVarMap[LiveIndex] = Var;
     88     } else if (VMetadata->isSingleBlock(Var)) {
     89       SizeT NodeIndex = VMetadata->getLocalUseNode(Var)->getIndex();
     90       LiveIndex = Nodes[NodeIndex].NumLocals++;
     91       Nodes[NodeIndex].LiveToVarMap[LiveIndex] = Var;
     92       LiveIndex += NumGlobals;
     93     }
     94     VarToLiveMap[VarIndex] = LiveIndex;
     95     if (LiveIndex == InvalidLiveIndex || Var->getIgnoreLiveness())
     96       RangeMask[VarIndex] = false;
     97   }
     98   assert(TmpNumGlobals == (IsFullInit ? NumGlobals : 0));
     99 
    100   // Fix up RangeMask for variables before FirstVar.
    101   for (auto I = Func->getVariables().begin(); I != FirstVar; ++I) {
    102     Variable *Var = *I;
    103     SizeT VarIndex = Var->getIndex();
    104     if (Var->getIgnoreLiveness() ||
    105         (!IsFullInit && !Var->hasReg() && !Var->mustHaveReg()))
    106       RangeMask[VarIndex] = false;
    107   }
    108 
    109   // Process each node.
    110   MaxLocals = 0;
    111   for (auto I = FirstNode, E = Func->getNodes().end(); I != E; ++I) {
    112     LivenessNode &Node = Nodes[(*I)->getIndex()];
    113     // NumLocals, LiveToVarMap already initialized
    114     Node.LiveIn.resize(NumGlobals);
    115     Node.LiveOut.resize(NumGlobals);
    116     // LiveBegin and LiveEnd are reinitialized before each pass over the block.
    117     MaxLocals = std::max(MaxLocals, Node.NumLocals);
    118   }
    119   ScratchBV.reserve(NumGlobals + MaxLocals);
    120 }
    121 
    122 void Liveness::init() {
    123   constexpr bool IsFullInit = true;
    124   NodeList::const_iterator FirstNode = Func->getNodes().begin();
    125   VarList::const_iterator FirstVar = Func->getVariables().begin();
    126   initInternal(FirstNode, FirstVar, IsFullInit);
    127 }
    128 
    129 void Liveness::initPhiEdgeSplits(NodeList::const_iterator FirstNode,
    130                                  VarList::const_iterator FirstVar) {
    131   constexpr bool IsFullInit = false;
    132   initInternal(FirstNode, FirstVar, IsFullInit);
    133 }
    134 
    135 Variable *Liveness::getVariable(SizeT LiveIndex, const CfgNode *Node) const {
    136   if (LiveIndex < NumGlobals)
    137     return LiveToVarMap[LiveIndex];
    138   SizeT NodeIndex = Node->getIndex();
    139   return Nodes[NodeIndex].LiveToVarMap[LiveIndex - NumGlobals];
    140 }
    141 
    142 } // end of namespace Ice
    143