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: create(Cfg * Func,SizeT Number)31 static CfgNode *create(Cfg *Func, SizeT Number) { 32 return new (Func->allocate<CfgNode>()) CfgNode(Func, Number); 33 } 34 getCfg()35 Cfg *getCfg() const { return Func; } 36 37 /// Access the label number and name for this node. getIndex()38 SizeT getIndex() const { return Number; } resetIndex(SizeT NewNumber)39 void resetIndex(SizeT NewNumber) { Number = NewNumber; } getName()40 std::string getName() const { 41 if (Name.hasStdString()) 42 return Name.toString(); 43 return "__" + std::to_string(NumberOrig); 44 } setName(const std::string & NewName)45 void setName(const std::string &NewName) { 46 if (NewName.empty()) 47 return; 48 Name = NodeString::createWithString(Func, NewName); 49 } getAsmName()50 std::string getAsmName() const { 51 return ".L" + Func->getFunctionName() + "$" + getName(); 52 } 53 incrementLoopNestDepth()54 void incrementLoopNestDepth() { ++LoopNestDepth; } setLoopNestDepth(SizeT NewDepth)55 void setLoopNestDepth(SizeT NewDepth) { LoopNestDepth = NewDepth; } getLoopNestDepth()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. setHasReturn()60 void setHasReturn() { HasReturn = true; } getHasReturn()61 bool getHasReturn() const { return HasReturn; } 62 setNeedsPlacement(bool Value)63 void setNeedsPlacement(bool Value) { NeedsPlacement = Value; } needsPlacement()64 bool needsPlacement() const { return NeedsPlacement; } 65 setNeedsAlignment()66 void setNeedsAlignment() { NeedsAlignment = true; } needsAlignment()67 bool needsAlignment() const { return NeedsAlignment; } 68 69 /// \name Access predecessor and successor edge lists. 70 /// @{ getInEdges()71 const NodeList &getInEdges() const { return InEdges; } getOutEdges()72 const NodeList &getOutEdges() const { return OutEdges; } 73 /// @} 74 75 /// \name Manage the instruction list. 76 /// @{ getInsts()77 InstList &getInsts() { return Insts; } getPhis()78 PhiList &getPhis() { return Phis; } getInsts()79 const InstList &getInsts() const { return Insts; } getPhis()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(). getInstCountEstimate()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 genCode(); 106 void livenessLightweight(); 107 bool liveness(Liveness *Liveness); 108 void livenessAddIntervals(Liveness *Liveness, InstNumberT FirstInstNum, 109 InstNumberT LastInstNum); 110 void contractIfEmpty(); 111 void doBranchOpt(const CfgNode *NextNode); 112 void emit(Cfg *Func) const; 113 void emitIAS(Cfg *Func) const; 114 void dump(Cfg *Func) const; 115 116 void profileExecutionCount(VariableDeclaration *Var); 117 addOutEdge(CfgNode * Out)118 void addOutEdge(CfgNode *Out) { OutEdges.push_back(Out); } addInEdge(CfgNode * In)119 void addInEdge(CfgNode *In) { InEdges.push_back(In); } 120 void replaceInEdge(CfgNode *Old, CfgNode *New); removeAllOutEdges()121 void removeAllOutEdges() { OutEdges.clear(); } 122 void removeInEdge(CfgNode *In); 123 hasSingleOutEdge()124 bool hasSingleOutEdge() const { 125 return (getOutEdges().size() == 1 || getOutEdges()[0] == getOutEdges()[1]); 126 } 127 CfgNode *shortCircuit(); 128 getExternalData()129 inline void *getExternalData() const { return externalData; } setExternalData(void * data)130 inline void setExternalData(void *data) { externalData = data; } 131 132 private: CfgNode(Cfg * Func,SizeT Number)133 CfgNode(Cfg *Func, SizeT Number) 134 : Func(Func), Number(Number), NumberOrig(Number), 135 Name(NodeString::createWithoutString(Func)) {} 136 bool livenessValidateIntervals(Liveness *Liveness) const; 137 Cfg *const Func; 138 SizeT Number; /// invariant: Func->Nodes[Number]==this 139 const SizeT NumberOrig; /// used for name auto-generation 140 NodeString Name; 141 SizeT LoopNestDepth = 0; /// the loop nest depth of this node 142 bool HasReturn = false; /// does this block need an epilog? 143 bool NeedsPlacement = false; 144 bool NeedsAlignment = false; /// is sandboxing required? 145 InstNumberT InstCountEstimate = 0; /// rough instruction count estimate 146 NodeList InEdges; /// in no particular order 147 NodeList OutEdges; /// in no particular order 148 PhiList Phis; /// unordered set of phi instructions 149 InstList Insts; /// ordered list of non-phi instructions 150 151 /// External data can be set by an optimizer to compute and retain any 152 /// information related to the current node. All the memory used to 153 /// store this information must be managed by the optimizer. 154 void *externalData = nullptr; 155 }; 156 157 } // end of namespace Ice 158 159 #endif // SUBZERO_SRC_ICECFGNODE_H 160