Home | History | Annotate | Download | only in src 
      1 //===- subzero/src/IceCfgNode.h - Control flow graph node -------*- C++ -*-===//
      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 Declares the CfgNode class, which represents a single basic block as
     12 /// its instruction list, in-edge list, and out-edge list.
     13 ///
     14 //===----------------------------------------------------------------------===//
     15 
     16 #ifndef SUBZERO_SRC_ICECFGNODE_H
     17 #define SUBZERO_SRC_ICECFGNODE_H
     18 
     19 #include "IceDefs.h"
     20 #include "IceInst.h" // InstList traits
     21 #include "IceStringPool.h"
     22 
     23 namespace Ice {
     24 
     25 class CfgNode {
     26   CfgNode() = delete;
     27   CfgNode(const CfgNode &) = delete;
     28   CfgNode &operator=(const CfgNode &) = delete;
     29 
     30 public:
     31   static CfgNode *create(Cfg *Func, SizeT Number) {
     32     return new (Func->allocate<CfgNode>()) CfgNode(Func, Number);
     33   }
     34 
     35   Cfg *getCfg() const { return Func; }
     36 
     37   /// Access the label number and name for this node.
     38   SizeT getIndex() const { return Number; }
     39   void resetIndex(SizeT NewNumber) { Number = NewNumber; }
     40   std::string getName() const {
     41     if (Name.hasStdString())
     42       return Name.toString();
     43     return "__" + std::to_string(NumberOrig);
     44   }
     45   void setName(const std::string &NewName) {
     46     if (NewName.empty())
     47       return;
     48     Name = NodeString::createWithString(Func, NewName);
     49   }
     50   std::string getAsmName() const {
     51     return ".L" + Func->getFunctionName() + "$" + getName();
     52   }
     53 
     54   void incrementLoopNestDepth() { ++LoopNestDepth; }
     55   void setLoopNestDepth(SizeT NewDepth) { LoopNestDepth = NewDepth; }
     56   SizeT getLoopNestDepth() const { return LoopNestDepth; }
     57 
     58   /// The HasReturn flag indicates that this node contains a return instruction
     59   /// and therefore needs an epilog.
     60   void setHasReturn() { HasReturn = true; }
     61   bool getHasReturn() const { return HasReturn; }
     62 
     63   void setNeedsPlacement(bool Value) { NeedsPlacement = Value; }
     64   bool needsPlacement() const { return NeedsPlacement; }
     65 
     66   void setNeedsAlignment() { NeedsAlignment = true; }
     67   bool needsAlignment() const { return NeedsAlignment; }
     68 
     69   /// \name Access predecessor and successor edge lists.
     70   /// @{
     71   const NodeList &getInEdges() const { return InEdges; }
     72   const NodeList &getOutEdges() const { return OutEdges; }
     73   /// @}
     74 
     75   /// \name Manage the instruction list.
     76   /// @{
     77   InstList &getInsts() { return Insts; }
     78   PhiList &getPhis() { return Phis; }
     79   const InstList &getInsts() const { return Insts; }
     80   const PhiList &getPhis() const { return Phis; }
     81   void appendInst(Inst *Instr);
     82   void renumberInstructions();
     83   /// Rough and generally conservative estimate of the number of instructions in
     84   /// the block. It is updated when an instruction is added, but not when
     85   /// deleted. It is recomputed during renumberInstructions().
     86   InstNumberT getInstCountEstimate() const { return InstCountEstimate; }
     87   /// @}
     88 
     89   /// \name Manage predecessors and successors.
     90   /// @{
     91 
     92   /// Add a predecessor edge to the InEdges list for each of this node's
     93   /// successors.
     94   void computePredecessors();
     95   void computeSuccessors();
     96   CfgNode *splitIncomingEdge(CfgNode *Pred, SizeT InEdgeIndex);
     97   /// @}
     98 
     99   void enforcePhiConsistency();
    100   void placePhiLoads();
    101   void placePhiStores();
    102   void deletePhis();
    103   void advancedPhiLowering();
    104   void doAddressOpt();
    105   void doNopInsertion(RandomNumberGenerator &RNG);
    106   void genCode();
    107   void livenessLightweight();
    108   bool liveness(Liveness *Liveness);
    109   void livenessAddIntervals(Liveness *Liveness, InstNumberT FirstInstNum,
    110                             InstNumberT LastInstNum);
    111   void contractIfEmpty();
    112   void doBranchOpt(const CfgNode *NextNode);
    113   void emit(Cfg *Func) const;
    114   void emitIAS(Cfg *Func) const;
    115   void dump(Cfg *Func) const;
    116 
    117   void profileExecutionCount(VariableDeclaration *Var);
    118 
    119   void addOutEdge(CfgNode *Out) { OutEdges.push_back(Out); }
    120   void addInEdge(CfgNode *In) { InEdges.push_back(In); }
    121   void replaceInEdge(CfgNode *Old, CfgNode *New);
    122   void removeAllOutEdges() { OutEdges.clear(); }
    123   void removeInEdge(CfgNode *In);
    124 
    125   bool hasSingleOutEdge() const {
    126     return (getOutEdges().size() == 1 || getOutEdges()[0] == getOutEdges()[1]);
    127   }
    128   CfgNode *shortCircuit();
    129 
    130 private:
    131   CfgNode(Cfg *Func, SizeT Number)
    132       : Func(Func), Number(Number), NumberOrig(Number),
    133         Name(NodeString::createWithoutString(Func)) {}
    134   bool livenessValidateIntervals(Liveness *Liveness) const;
    135   Cfg *const Func;
    136   SizeT Number;           /// invariant: Func->Nodes[Number]==this
    137   const SizeT NumberOrig; /// used for name auto-generation
    138   NodeString Name;
    139   SizeT LoopNestDepth = 0; /// the loop nest depth of this node
    140   bool HasReturn = false;  /// does this block need an epilog?
    141   bool NeedsPlacement = false;
    142   bool NeedsAlignment = false;       /// is sandboxing required?
    143   InstNumberT InstCountEstimate = 0; /// rough instruction count estimate
    144   NodeList InEdges;                  /// in no particular order
    145   NodeList OutEdges;                 /// in no particular order
    146   PhiList Phis;                      /// unordered set of phi instructions
    147   InstList Insts;                    /// ordered list of non-phi instructions
    148 };
    149 
    150 } // end of namespace Ice
    151 
    152 #endif // SUBZERO_SRC_ICECFGNODE_H
    153