Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 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 | //===----------------------------------------------------------------------===// |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 9 | /// |
| 10 | /// \file |
Jim Stichnoth | 92a6e5b | 2015-12-02 16:52:44 -0800 | [diff] [blame] | 11 | /// \brief Declares the CfgNode class, which represents a single basic block as |
| 12 | /// its instruction list, in-edge list, and out-edge list. |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 13 | /// |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 14 | //===----------------------------------------------------------------------===// |
| 15 | |
| 16 | #ifndef SUBZERO_SRC_ICECFGNODE_H |
| 17 | #define SUBZERO_SRC_ICECFGNODE_H |
| 18 | |
| 19 | #include "IceDefs.h" |
Jim Stichnoth | 607e9f0 | 2014-11-06 13:32:05 -0800 | [diff] [blame] | 20 | #include "IceInst.h" // InstList traits |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 21 | #include "IceStringPool.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 22 | |
| 23 | namespace Ice { |
| 24 | |
| 25 | class CfgNode { |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 26 | CfgNode() = delete; |
Jim Stichnoth | 7b451a9 | 2014-10-15 14:39:23 -0700 | [diff] [blame] | 27 | CfgNode(const CfgNode &) = delete; |
| 28 | CfgNode &operator=(const CfgNode &) = delete; |
| 29 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 30 | public: |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 31 | static CfgNode *create(Cfg *Func, SizeT Number) { |
| 32 | return new (Func->allocate<CfgNode>()) CfgNode(Func, Number); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 33 | } |
| 34 | |
Jim Stichnoth | 5bff61c | 2015-10-28 09:26:00 -0700 | [diff] [blame] | 35 | Cfg *getCfg() const { return Func; } |
| 36 | |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 37 | /// Access the label number and name for this node. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 38 | SizeT getIndex() const { return Number; } |
Jim Stichnoth | 69d3f9c | 2015-03-23 10:33:38 -0700 | [diff] [blame] | 39 | void resetIndex(SizeT NewNumber) { Number = NewNumber; } |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 40 | std::string getName() const { |
| 41 | if (Name.hasStdString()) |
| 42 | return Name.toString(); |
| 43 | return "__" + std::to_string(NumberOrig); |
| 44 | } |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 45 | void setName(const std::string &NewName) { |
| 46 | if (NewName.empty()) |
| 47 | return; |
| 48 | Name = NodeString::createWithString(Func, NewName); |
Karl Schimpf | c132b76 | 2014-09-11 09:43:47 -0700 | [diff] [blame] | 49 | } |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 50 | std::string getAsmName() const { |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 51 | return ".L" + Func->getFunctionName() + "$" + getName(); |
| 52 | } |
| 53 | |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 54 | void incrementLoopNestDepth() { ++LoopNestDepth; } |
| 55 | void setLoopNestDepth(SizeT NewDepth) { LoopNestDepth = NewDepth; } |
| 56 | SizeT getLoopNestDepth() const { return LoopNestDepth; } |
| 57 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 58 | /// The HasReturn flag indicates that this node contains a return instruction |
| 59 | /// and therefore needs an epilog. |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 60 | void setHasReturn() { HasReturn = true; } |
| 61 | bool getHasReturn() const { return HasReturn; } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 62 | |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 63 | void setNeedsPlacement(bool Value) { NeedsPlacement = Value; } |
| 64 | bool needsPlacement() const { return NeedsPlacement; } |
| 65 | |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 66 | void setNeedsAlignment() { NeedsAlignment = true; } |
| 67 | bool needsAlignment() const { return NeedsAlignment; } |
| 68 | |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 69 | /// \name Access predecessor and successor edge lists. |
| 70 | /// @{ |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 71 | const NodeList &getInEdges() const { return InEdges; } |
| 72 | const NodeList &getOutEdges() const { return OutEdges; } |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 73 | /// @} |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 74 | |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 75 | /// \name Manage the instruction list. |
| 76 | /// @{ |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 77 | InstList &getInsts() { return Insts; } |
Jim Stichnoth | 98712a3 | 2014-10-24 10:59:02 -0700 | [diff] [blame] | 78 | PhiList &getPhis() { return Phis; } |
Jim Stichnoth | b9a8472 | 2016-08-01 13:18:36 -0700 | [diff] [blame] | 79 | const InstList &getInsts() const { return Insts; } |
| 80 | const PhiList &getPhis() const { return Phis; } |
Eric Holk | 085bdae | 2016-04-18 15:08:19 -0700 | [diff] [blame] | 81 | void appendInst(Inst *Instr); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 82 | void renumberInstructions(); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 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(). |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 86 | InstNumberT getInstCountEstimate() const { return InstCountEstimate; } |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 87 | /// @} |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 88 | |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 89 | /// \name Manage predecessors and successors. |
| 90 | /// @{ |
| 91 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 92 | /// Add a predecessor edge to the InEdges list for each of this node's |
| 93 | /// successors. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 94 | void computePredecessors(); |
Jim Stichnoth | 69d3f9c | 2015-03-23 10:33:38 -0700 | [diff] [blame] | 95 | void computeSuccessors(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 96 | CfgNode *splitIncomingEdge(CfgNode *Pred, SizeT InEdgeIndex); |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 97 | /// @} |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 98 | |
David Sehr | 263ac52 | 2016-04-04 10:11:08 -0700 | [diff] [blame] | 99 | void enforcePhiConsistency(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 100 | void placePhiLoads(); |
| 101 | void placePhiStores(); |
| 102 | void deletePhis(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 103 | void advancedPhiLowering(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 104 | void doAddressOpt(); |
Qining Lu | aee5fa8 | 2015-08-20 14:59:03 -0700 | [diff] [blame] | 105 | void doNopInsertion(RandomNumberGenerator &RNG); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 106 | void genCode(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 107 | void livenessLightweight(); |
| 108 | bool liveness(Liveness *Liveness); |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 109 | void livenessAddIntervals(Liveness *Liveness, InstNumberT FirstInstNum, |
| 110 | InstNumberT LastInstNum); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 111 | void contractIfEmpty(); |
Jim Stichnoth | ff9c706 | 2014-09-18 04:50:49 -0700 | [diff] [blame] | 112 | void doBranchOpt(const CfgNode *NextNode); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 113 | void emit(Cfg *Func) const; |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 114 | void emitIAS(Cfg *Func) const; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 115 | void dump(Cfg *Func) const; |
| 116 | |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 117 | void profileExecutionCount(VariableDeclaration *Var); |
| 118 | |
Eric Holk | 16f8061 | 2016-04-04 17:07:42 -0700 | [diff] [blame] | 119 | void addOutEdge(CfgNode *Out) { OutEdges.push_back(Out); } |
| 120 | void addInEdge(CfgNode *In) { InEdges.push_back(In); } |
Manasij Mukherjee | 45f51a2 | 2016-06-27 16:12:37 -0700 | [diff] [blame] | 121 | void replaceInEdge(CfgNode *Old, CfgNode *New); |
| 122 | void removeAllOutEdges() { OutEdges.clear(); } |
| 123 | void removeInEdge(CfgNode *In); |
Eric Holk | 16f8061 | 2016-04-04 17:07:42 -0700 | [diff] [blame] | 124 | |
| 125 | bool hasSingleOutEdge() const { |
| 126 | return (getOutEdges().size() == 1 || getOutEdges()[0] == getOutEdges()[1]); |
| 127 | } |
Manasij Mukherjee | 45f51a2 | 2016-06-27 16:12:37 -0700 | [diff] [blame] | 128 | CfgNode *shortCircuit(); |
Eric Holk | 16f8061 | 2016-04-04 17:07:42 -0700 | [diff] [blame] | 129 | |
Alexis Hetu | 932640b | 2018-06-20 15:35:53 -0400 | [diff] [blame] | 130 | inline void* getExternalData() const { return externalData; } |
| 131 | inline void setExternalData(void* data) { externalData = data; } |
| 132 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 133 | private: |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 134 | CfgNode(Cfg *Func, SizeT Number) |
| 135 | : Func(Func), Number(Number), NumberOrig(Number), |
| 136 | Name(NodeString::createWithoutString(Func)) {} |
Jim Stichnoth | 318f4cd | 2015-10-01 21:02:37 -0700 | [diff] [blame] | 137 | bool livenessValidateIntervals(Liveness *Liveness) const; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 138 | Cfg *const Func; |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 139 | SizeT Number; /// invariant: Func->Nodes[Number]==this |
| 140 | const SizeT NumberOrig; /// used for name auto-generation |
Jim Stichnoth | 467ffe5 | 2016-03-29 15:01:06 -0700 | [diff] [blame] | 141 | NodeString Name; |
| 142 | SizeT LoopNestDepth = 0; /// the loop nest depth of this node |
| 143 | bool HasReturn = false; /// does this block need an epilog? |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 144 | bool NeedsPlacement = false; |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame] | 145 | bool NeedsAlignment = false; /// is sandboxing required? |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 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 |
Alexis Hetu | 932640b | 2018-06-20 15:35:53 -0400 | [diff] [blame] | 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; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 156 | }; |
| 157 | |
| 158 | } // end of namespace Ice |
| 159 | |
| 160 | #endif // SUBZERO_SRC_ICECFGNODE_H |