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 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 addOutEdge(CfgNode * Out)119 void addOutEdge(CfgNode *Out) { OutEdges.push_back(Out); } addInEdge(CfgNode * In)120 void addInEdge(CfgNode *In) { InEdges.push_back(In); } 121 void replaceInEdge(CfgNode *Old, CfgNode *New); removeAllOutEdges()122 void removeAllOutEdges() { OutEdges.clear(); } 123 void removeInEdge(CfgNode *In); 124 hasSingleOutEdge()125 bool hasSingleOutEdge() const { 126 return (getOutEdges().size() == 1 || getOutEdges()[0] == getOutEdges()[1]); 127 } 128 CfgNode *shortCircuit(); 129 getExternalData()130 inline void* getExternalData() const { return externalData; } setExternalData(void * data)131 inline void setExternalData(void* data) { externalData = data; } 132 133 private: CfgNode(Cfg * Func,SizeT Number)134 CfgNode(Cfg *Func, SizeT Number) 135 : Func(Func), Number(Number), NumberOrig(Number), 136 Name(NodeString::createWithoutString(Func)) {} 137 bool livenessValidateIntervals(Liveness *Liveness) const; 138 Cfg *const Func; 139 SizeT Number; /// invariant: Func->Nodes[Number]==this 140 const SizeT NumberOrig; /// used for name auto-generation 141 NodeString Name; 142 SizeT LoopNestDepth = 0; /// the loop nest depth of this node 143 bool HasReturn = false; /// does this block need an epilog? 144 bool NeedsPlacement = false; 145 bool NeedsAlignment = false; /// is sandboxing required? 146 InstNumberT InstCountEstimate = 0; /// rough instruction count estimate 147 NodeList InEdges; /// in no particular order 148 NodeList OutEdges; /// in no particular order 149 PhiList Phis; /// unordered set of phi instructions 150 InstList Insts; /// ordered list of non-phi instructions 151 152 /// External data can be set by an optimizer to compute and retain any 153 /// information related to the current node. All the memory used to 154 /// store this information must be managed by the optimizer. 155 void* externalData = nullptr; 156 }; 157 158 } // end of namespace Ice 159 160 #endif // SUBZERO_SRC_ICECFGNODE_H 161