Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1 | //===- subzero/src/IceCfg.cpp - Control flow graph 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 | // This file implements the Cfg class, including constant pool |
| 11 | // management. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "IceCfg.h" |
| 16 | #include "IceCfgNode.h" |
Jim Stichnoth | 989a703 | 2014-08-08 10:13:44 -0700 | [diff] [blame] | 17 | #include "IceClFlags.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 18 | #include "IceDefs.h" |
| 19 | #include "IceInst.h" |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 20 | #include "IceLiveness.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 21 | #include "IceOperand.h" |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 22 | #include "IceTargetLowering.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 23 | |
| 24 | namespace Ice { |
| 25 | |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 26 | thread_local const Cfg *Cfg::CurrentCfg = nullptr; |
Jim Stichnoth | 31c9559 | 2014-12-19 12:51:35 -0800 | [diff] [blame] | 27 | |
| 28 | ArenaAllocator *getCurrentCfgAllocator() { |
| 29 | return Cfg::getCurrentCfgAllocator(); |
| 30 | } |
| 31 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 32 | Cfg::Cfg(GlobalContext *Ctx) |
| 33 | : Ctx(Ctx), FunctionName(""), ReturnType(IceType_void), |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 34 | IsInternalLinkage(false), HasError(false), FocusedTiming(false), |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 35 | ErrorMessage(""), Entry(nullptr), NextInstNumber(Inst::NumberInitial), |
Jim Stichnoth | 31c9559 | 2014-12-19 12:51:35 -0800 | [diff] [blame] | 36 | Allocator(new ArenaAllocator()), Live(nullptr), |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 37 | Target(TargetLowering::createLowering(Ctx->getTargetArch(), this)), |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 38 | VMetadata(new VariablesMetadata(this)), |
| 39 | TargetAssembler( |
| 40 | TargetLowering::createAssembler(Ctx->getTargetArch(), this)), |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 41 | CurrentNode(nullptr) { |
Karl Schimpf | 6fcbddd | 2014-11-06 09:49:24 -0800 | [diff] [blame] | 42 | assert(!Ctx->isIRGenerationDisabled() && |
| 43 | "Attempt to build cfg when IR generation disabled"); |
| 44 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 45 | |
Jim Stichnoth | 31c9559 | 2014-12-19 12:51:35 -0800 | [diff] [blame] | 46 | Cfg::~Cfg() { |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 47 | // TODO(stichnot,kschimpf): Set CurrentCfg=nullptr in the dtor for |
Jim Stichnoth | 31c9559 | 2014-12-19 12:51:35 -0800 | [diff] [blame] | 48 | // safety. This can't be done currently because the translator |
| 49 | // manages the Cfg by creating a new Cfg (which sets CurrentCfg to |
| 50 | // the new value), then deleting the old Cfg (which would then reset |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 51 | // CurrentCfg to nullptr). |
Jim Stichnoth | 31c9559 | 2014-12-19 12:51:35 -0800 | [diff] [blame] | 52 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 53 | |
| 54 | void Cfg::setError(const IceString &Message) { |
| 55 | HasError = true; |
| 56 | ErrorMessage = Message; |
| 57 | Ctx->getStrDump() << "ICE translation error: " << ErrorMessage << "\n"; |
| 58 | } |
| 59 | |
Jim Stichnoth | 668a7a3 | 2014-12-10 15:32:25 -0800 | [diff] [blame] | 60 | CfgNode *Cfg::makeNode() { |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 61 | SizeT LabelIndex = Nodes.size(); |
Jim Stichnoth | 668a7a3 | 2014-12-10 15:32:25 -0800 | [diff] [blame] | 62 | CfgNode *Node = CfgNode::create(this, LabelIndex); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 63 | Nodes.push_back(Node); |
| 64 | return Node; |
| 65 | } |
| 66 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 67 | void Cfg::addArg(Variable *Arg) { |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 68 | Arg->setIsArg(); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 69 | Args.push_back(Arg); |
| 70 | } |
| 71 | |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 72 | void Cfg::addImplicitArg(Variable *Arg) { |
| 73 | Arg->setIsImplicitArg(); |
| 74 | ImplicitArgs.push_back(Arg); |
| 75 | } |
| 76 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 77 | // Returns whether the stack frame layout has been computed yet. This |
| 78 | // is used for dumping the stack frame location of Variables. |
| 79 | bool Cfg::hasComputedFrame() const { return getTarget()->hasComputedFrame(); } |
| 80 | |
| 81 | void Cfg::translate() { |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 82 | if (hasError()) |
| 83 | return; |
Jim Stichnoth | 1c44d81 | 2014-12-08 14:57:52 -0800 | [diff] [blame] | 84 | if (ALLOW_DUMP) { |
| 85 | const IceString &TimingFocusOn = getContext()->getFlags().TimingFocusOn; |
| 86 | if (TimingFocusOn == "*" || TimingFocusOn == getFunctionName()) { |
| 87 | setFocusedTiming(); |
| 88 | getContext()->resetTimer(GlobalContext::TSK_Default); |
| 89 | getContext()->setTimerName(GlobalContext::TSK_Default, getFunctionName()); |
| 90 | } |
Jim Stichnoth | d14b1a0 | 2014-10-08 08:28:36 -0700 | [diff] [blame] | 91 | } |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 92 | TimerMarker T(TimerStack::TT_translate, this); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 93 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 94 | dump("Initial CFG"); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 95 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 96 | // The set of translation passes and their order are determined by |
| 97 | // the target. |
| 98 | getTarget()->translate(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 99 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 100 | dump("Final output"); |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 101 | if (getFocusedTiming()) |
| 102 | getContext()->dumpTimers(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 103 | } |
| 104 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 105 | void Cfg::computePredecessors() { |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 106 | for (CfgNode *Node : Nodes) |
| 107 | Node->computePredecessors(); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 108 | } |
| 109 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 110 | void Cfg::renumberInstructions() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 111 | TimerMarker T(TimerStack::TT_renumberInstructions, this); |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 112 | NextInstNumber = Inst::NumberInitial; |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 113 | for (CfgNode *Node : Nodes) |
| 114 | Node->renumberInstructions(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 115 | } |
| 116 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 117 | // placePhiLoads() must be called before placePhiStores(). |
| 118 | void Cfg::placePhiLoads() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 119 | TimerMarker T(TimerStack::TT_placePhiLoads, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 120 | for (CfgNode *Node : Nodes) |
| 121 | Node->placePhiLoads(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 122 | } |
| 123 | |
| 124 | // placePhiStores() must be called after placePhiLoads(). |
| 125 | void Cfg::placePhiStores() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 126 | TimerMarker T(TimerStack::TT_placePhiStores, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 127 | for (CfgNode *Node : Nodes) |
| 128 | Node->placePhiStores(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 129 | } |
| 130 | |
| 131 | void Cfg::deletePhis() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 132 | TimerMarker T(TimerStack::TT_deletePhis, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 133 | for (CfgNode *Node : Nodes) |
| 134 | Node->deletePhis(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 135 | } |
| 136 | |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 137 | void Cfg::advancedPhiLowering() { |
| 138 | TimerMarker T(TimerStack::TT_advancedPhiLowering, this); |
| 139 | // This splits edges and appends new nodes to the end of the node |
| 140 | // list. This can invalidate iterators, so don't use an iterator. |
| 141 | SizeT NumNodes = getNumNodes(); |
| 142 | for (SizeT I = 0; I < NumNodes; ++I) |
| 143 | Nodes[I]->advancedPhiLowering(); |
| 144 | } |
| 145 | |
| 146 | // Find a reasonable placement for nodes that have not yet been |
| 147 | // placed, while maintaining the same relative ordering among already |
| 148 | // placed nodes. |
| 149 | void Cfg::reorderNodes() { |
| 150 | typedef std::list<CfgNode *> PlacedList; |
| 151 | PlacedList Placed; // Nodes with relative placement locked down |
| 152 | PlacedList Unreachable; // Unreachable nodes |
| 153 | PlacedList::iterator NoPlace = Placed.end(); |
| 154 | // Keep track of where each node has been tentatively placed so that |
| 155 | // we can manage insertions into the middle. |
| 156 | std::vector<PlacedList::iterator> PlaceIndex(Nodes.size(), NoPlace); |
| 157 | for (CfgNode *Node : Nodes) { |
| 158 | // The "do ... while(0);" construct is to factor out the |
| 159 | // --PlaceIndex and assert() statements before moving to the next |
| 160 | // node. |
| 161 | do { |
| 162 | if (!Node->needsPlacement()) { |
| 163 | // Add to the end of the Placed list. |
| 164 | Placed.push_back(Node); |
| 165 | PlaceIndex[Node->getIndex()] = Placed.end(); |
| 166 | continue; |
| 167 | } |
| 168 | Node->setNeedsPlacement(false); |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 169 | if (Node != getEntryNode() && Node->getInEdges().empty()) { |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 170 | // The node has essentially been deleted since it is not a |
| 171 | // successor of any other node. |
| 172 | Unreachable.push_back(Node); |
| 173 | PlaceIndex[Node->getIndex()] = Unreachable.end(); |
| 174 | continue; |
| 175 | } |
| 176 | // Assume for now that the unplaced node is from edge-splitting |
| 177 | // and therefore has 1 in-edge and 1 out-edge (actually, possibly |
| 178 | // more than 1 in-edge if the predecessor node was contracted). |
| 179 | // If this changes in the future, rethink the strategy. |
| 180 | assert(Node->getInEdges().size() >= 1); |
| 181 | assert(Node->getOutEdges().size() == 1); |
| 182 | |
| 183 | // If it's a (non-critical) edge where the successor has a single |
| 184 | // in-edge, then place it before the successor. |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 185 | CfgNode *Succ = Node->getOutEdges().front(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 186 | if (Succ->getInEdges().size() == 1 && |
| 187 | PlaceIndex[Succ->getIndex()] != NoPlace) { |
| 188 | Placed.insert(PlaceIndex[Succ->getIndex()], Node); |
| 189 | PlaceIndex[Node->getIndex()] = PlaceIndex[Succ->getIndex()]; |
| 190 | continue; |
| 191 | } |
| 192 | |
| 193 | // Otherwise, place it after the (first) predecessor. |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 194 | CfgNode *Pred = Node->getInEdges().front(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 195 | auto PredPosition = PlaceIndex[Pred->getIndex()]; |
| 196 | // It shouldn't be the case that PredPosition==NoPlace, but if |
| 197 | // that somehow turns out to be true, we just insert Node before |
| 198 | // PredPosition=NoPlace=Placed.end() . |
| 199 | if (PredPosition != NoPlace) |
| 200 | ++PredPosition; |
| 201 | Placed.insert(PredPosition, Node); |
| 202 | PlaceIndex[Node->getIndex()] = PredPosition; |
| 203 | } while (0); |
| 204 | |
| 205 | --PlaceIndex[Node->getIndex()]; |
| 206 | assert(*PlaceIndex[Node->getIndex()] == Node); |
| 207 | } |
| 208 | |
| 209 | // Reorder Nodes according to the built-up lists. |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 210 | SizeT OldSize = Nodes.size(); |
| 211 | (void)OldSize; |
| 212 | Nodes.clear(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 213 | for (CfgNode *Node : Placed) |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 214 | Nodes.push_back(Node); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 215 | for (CfgNode *Node : Unreachable) |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 216 | Nodes.push_back(Node); |
| 217 | assert(Nodes.size() == OldSize); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 218 | } |
| 219 | |
Matt Wala | 45a0623 | 2014-07-09 16:33:22 -0700 | [diff] [blame] | 220 | void Cfg::doArgLowering() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 221 | TimerMarker T(TimerStack::TT_doArgLowering, this); |
Matt Wala | 45a0623 | 2014-07-09 16:33:22 -0700 | [diff] [blame] | 222 | getTarget()->lowerArguments(); |
| 223 | } |
| 224 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 225 | void Cfg::doAddressOpt() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 226 | TimerMarker T(TimerStack::TT_doAddressOpt, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 227 | for (CfgNode *Node : Nodes) |
| 228 | Node->doAddressOpt(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 229 | } |
| 230 | |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 231 | void Cfg::doNopInsertion() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 232 | TimerMarker T(TimerStack::TT_doNopInsertion, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 233 | for (CfgNode *Node : Nodes) |
| 234 | Node->doNopInsertion(); |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 235 | } |
| 236 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 237 | void Cfg::genCode() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 238 | TimerMarker T(TimerStack::TT_genCode, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 239 | for (CfgNode *Node : Nodes) |
| 240 | Node->genCode(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 241 | } |
| 242 | |
| 243 | // Compute the stack frame layout. |
| 244 | void Cfg::genFrame() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 245 | TimerMarker T(TimerStack::TT_genFrame, this); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 246 | getTarget()->addProlog(Entry); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 247 | for (CfgNode *Node : Nodes) |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 248 | if (Node->getHasReturn()) |
| 249 | getTarget()->addEpilog(Node); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 250 | } |
| 251 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 252 | // This is a lightweight version of live-range-end calculation. Marks |
| 253 | // the last use of only those variables whose definition and uses are |
| 254 | // completely with a single block. It is a quick single pass and |
| 255 | // doesn't need to iterate until convergence. |
| 256 | void Cfg::livenessLightweight() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 257 | TimerMarker T(TimerStack::TT_livenessLightweight, this); |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 258 | getVMetadata()->init(VMK_Uses); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 259 | for (CfgNode *Node : Nodes) |
| 260 | Node->livenessLightweight(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 261 | } |
| 262 | |
| 263 | void Cfg::liveness(LivenessMode Mode) { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 264 | TimerMarker T(TimerStack::TT_liveness, this); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 265 | Live.reset(new Liveness(this, Mode)); |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 266 | getVMetadata()->init(VMK_Uses); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 267 | Live->init(); |
| 268 | // Initialize with all nodes needing to be processed. |
| 269 | llvm::BitVector NeedToProcess(Nodes.size(), true); |
| 270 | while (NeedToProcess.any()) { |
| 271 | // Iterate in reverse topological order to speed up convergence. |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 272 | for (auto I = Nodes.rbegin(), E = Nodes.rend(); I != E; ++I) { |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 273 | CfgNode *Node = *I; |
| 274 | if (NeedToProcess[Node->getIndex()]) { |
| 275 | NeedToProcess[Node->getIndex()] = false; |
| 276 | bool Changed = Node->liveness(getLiveness()); |
| 277 | if (Changed) { |
| 278 | // If the beginning-of-block liveness changed since the last |
| 279 | // iteration, mark all in-edges as needing to be processed. |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 280 | for (CfgNode *Pred : Node->getInEdges()) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 281 | NeedToProcess[Pred->getIndex()] = true; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 282 | } |
| 283 | } |
| 284 | } |
| 285 | } |
| 286 | if (Mode == Liveness_Intervals) { |
| 287 | // Reset each variable's live range. |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 288 | for (Variable *Var : Variables) |
| 289 | Var->resetLiveRange(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 290 | } |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 291 | // Make a final pass over each node to delete dead instructions, |
| 292 | // collect the first and last instruction numbers, and add live |
| 293 | // range segments for that node. |
| 294 | for (CfgNode *Node : Nodes) { |
| 295 | InstNumberT FirstInstNum = Inst::NumberSentinel; |
| 296 | InstNumberT LastInstNum = Inst::NumberSentinel; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame^] | 297 | for (Inst &I : Node->getPhis()) { |
| 298 | I.deleteIfDead(); |
| 299 | if (Mode == Liveness_Intervals && !I.isDeleted()) { |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 300 | if (FirstInstNum == Inst::NumberSentinel) |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame^] | 301 | FirstInstNum = I.getNumber(); |
| 302 | assert(I.getNumber() > LastInstNum); |
| 303 | LastInstNum = I.getNumber(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 304 | } |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 305 | } |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame^] | 306 | for (Inst &I : Node->getInsts()) { |
| 307 | I.deleteIfDead(); |
| 308 | if (Mode == Liveness_Intervals && !I.isDeleted()) { |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 309 | if (FirstInstNum == Inst::NumberSentinel) |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame^] | 310 | FirstInstNum = I.getNumber(); |
| 311 | assert(I.getNumber() > LastInstNum); |
| 312 | LastInstNum = I.getNumber(); |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 313 | } |
| 314 | } |
| 315 | if (Mode == Liveness_Intervals) { |
| 316 | // Special treatment for live in-args. Their liveness needs to |
| 317 | // extend beyond the beginning of the function, otherwise an arg |
| 318 | // whose only use is in the first instruction will end up having |
| 319 | // the trivial live range [2,2) and will *not* interfere with |
| 320 | // other arguments. So if the first instruction of the method |
| 321 | // is "r=arg1+arg2", both args may be assigned the same |
| 322 | // register. This is accomplished by extending the entry |
| 323 | // block's instruction range from [2,n) to [1,n) which will |
| 324 | // transform the problematic [2,2) live ranges into [1,2). |
| 325 | if (FirstInstNum == Inst::NumberInitial) |
| 326 | FirstInstNum = Inst::NumberExtended; |
| 327 | Node->livenessAddIntervals(getLiveness(), FirstInstNum, LastInstNum); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 328 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 329 | } |
| 330 | } |
| 331 | |
| 332 | // Traverse every Variable of every Inst and verify that it |
| 333 | // appears within the Variable's computed live range. |
| 334 | bool Cfg::validateLiveness() const { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 335 | TimerMarker T(TimerStack::TT_validateLiveness, this); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 336 | bool Valid = true; |
| 337 | Ostream &Str = Ctx->getStrDump(); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 338 | for (CfgNode *Node : Nodes) { |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 339 | Inst *FirstInst = nullptr; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame^] | 340 | for (Inst &Inst : Node->getInsts()) { |
| 341 | if (Inst.isDeleted()) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 342 | continue; |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 343 | if (FirstInst == nullptr) |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame^] | 344 | FirstInst = &Inst; |
| 345 | InstNumberT InstNumber = Inst.getNumber(); |
| 346 | if (Variable *Dest = Inst.getDest()) { |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 347 | if (!Dest->getIgnoreLiveness()) { |
| 348 | bool Invalid = false; |
| 349 | const bool IsDest = true; |
| 350 | if (!Dest->getLiveRange().containsValue(InstNumber, IsDest)) |
| 351 | Invalid = true; |
| 352 | // Check that this instruction actually *begins* Dest's live |
| 353 | // range, by checking that Dest is not live in the previous |
| 354 | // instruction. As a special exception, we don't check this |
| 355 | // for the first instruction of the block, because a Phi |
| 356 | // temporary may be live at the end of the previous block, |
| 357 | // and if it is also assigned in the first instruction of |
| 358 | // this block, the adjacent live ranges get merged. |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame^] | 359 | if (static_cast<class Inst *>(&Inst) != FirstInst && |
| 360 | !Inst.isDestNonKillable() && |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 361 | Dest->getLiveRange().containsValue(InstNumber - 1, IsDest)) |
| 362 | Invalid = true; |
| 363 | if (Invalid) { |
| 364 | Valid = false; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame^] | 365 | Str << "Liveness error: inst " << Inst.getNumber() << " dest "; |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 366 | Dest->dump(this); |
| 367 | Str << " live range " << Dest->getLiveRange() << "\n"; |
| 368 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 369 | } |
| 370 | } |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame^] | 371 | for (SizeT I = 0; I < Inst.getSrcSize(); ++I) { |
| 372 | Operand *Src = Inst.getSrc(I); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 373 | SizeT NumVars = Src->getNumVars(); |
| 374 | for (SizeT J = 0; J < NumVars; ++J) { |
| 375 | const Variable *Var = Src->getVar(J); |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 376 | const bool IsDest = false; |
| 377 | if (!Var->getIgnoreLiveness() && |
| 378 | !Var->getLiveRange().containsValue(InstNumber, IsDest)) { |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 379 | Valid = false; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame^] | 380 | Str << "Liveness error: inst " << Inst.getNumber() << " var "; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 381 | Var->dump(this); |
| 382 | Str << " live range " << Var->getLiveRange() << "\n"; |
| 383 | } |
| 384 | } |
| 385 | } |
| 386 | } |
| 387 | } |
| 388 | return Valid; |
| 389 | } |
| 390 | |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 391 | void Cfg::contractEmptyNodes() { |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 392 | // If we're decorating the asm output with register liveness info, |
| 393 | // this information may become corrupted or incorrect after |
| 394 | // contracting nodes that contain only redundant assignments. As |
| 395 | // such, we disable this pass when DecorateAsm is specified. This |
| 396 | // may make the resulting code look more branchy, but it should have |
| 397 | // no effect on the register assignments. |
| 398 | if (Ctx->getFlags().DecorateAsm) |
| 399 | return; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 400 | for (CfgNode *Node : Nodes) { |
| 401 | Node->contractIfEmpty(); |
| 402 | } |
| 403 | } |
| 404 | |
Jim Stichnoth | ff9c706 | 2014-09-18 04:50:49 -0700 | [diff] [blame] | 405 | void Cfg::doBranchOpt() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 406 | TimerMarker T(TimerStack::TT_doBranchOpt, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 407 | for (auto I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
| 408 | auto NextNode = I; |
Jim Stichnoth | ff9c706 | 2014-09-18 04:50:49 -0700 | [diff] [blame] | 409 | ++NextNode; |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 410 | (*I)->doBranchOpt(NextNode == E ? nullptr : *NextNode); |
Jim Stichnoth | ff9c706 | 2014-09-18 04:50:49 -0700 | [diff] [blame] | 411 | } |
| 412 | } |
| 413 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 414 | // ======================== Dump routines ======================== // |
| 415 | |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 416 | void Cfg::emitTextHeader(const IceString &MangledName) { |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 417 | // Note: Still used by emit IAS. |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 418 | Ostream &Str = Ctx->getStrEmit(); |
| 419 | Str << "\t.text\n"; |
| 420 | if (Ctx->getFlags().FunctionSections) |
| 421 | Str << "\t.section\t.text." << MangledName << ",\"ax\",@progbits\n"; |
| 422 | if (!getInternal() || Ctx->getFlags().DisableInternal) { |
| 423 | Str << "\t.globl\t" << MangledName << "\n"; |
| 424 | Str << "\t.type\t" << MangledName << ",@function\n"; |
| 425 | } |
Jan Voung | 08c3bcd | 2014-12-01 17:55:16 -0800 | [diff] [blame] | 426 | Assembler *Asm = getAssembler<Assembler>(); |
| 427 | Str << "\t.p2align " << Asm->getBundleAlignLog2Bytes() << ",0x"; |
| 428 | for (uint8_t I : Asm->getNonExecBundlePadding()) |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 429 | Str.write_hex(I); |
| 430 | Str << "\n"; |
| 431 | Str << MangledName << ":\n"; |
| 432 | } |
| 433 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 434 | void Cfg::emit() { |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 435 | if (!ALLOW_DUMP) |
| 436 | return; |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 437 | TimerMarker T(TimerStack::TT_emit, this); |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 438 | if (Ctx->getFlags().DecorateAsm) { |
| 439 | renumberInstructions(); |
| 440 | getVMetadata()->init(VMK_Uses); |
| 441 | liveness(Liveness_Basic); |
| 442 | dump("After recomputing liveness for -decorate-asm"); |
| 443 | } |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 444 | Ostream &Str = Ctx->getStrEmit(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 445 | if (!Ctx->testAndSetHasEmittedFirstMethod()) { |
| 446 | // Print a helpful command for assembling the output. |
| 447 | // TODO: have the Target emit the header |
| 448 | // TODO: need a per-file emit in addition to per-CFG |
| 449 | Str << "# $LLVM_BIN_PATH/llvm-mc" |
| 450 | << " -arch=x86" |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 451 | << " -filetype=obj" |
| 452 | << " -o=MyObj.o" |
| 453 | << "\n\n"; |
| 454 | } |
Jim Stichnoth | 989a703 | 2014-08-08 10:13:44 -0700 | [diff] [blame] | 455 | IceString MangledName = getContext()->mangleName(getFunctionName()); |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 456 | emitTextHeader(MangledName); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 457 | for (CfgNode *Node : Nodes) |
| 458 | Node->emit(this); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 459 | Str << "\n"; |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 460 | } |
| 461 | |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 462 | void Cfg::emitIAS() { |
| 463 | TimerMarker T(TimerStack::TT_emit, this); |
| 464 | assert(!Ctx->getFlags().DecorateAsm); |
| 465 | IceString MangledName = getContext()->mangleName(getFunctionName()); |
Jan Voung | 08c3bcd | 2014-12-01 17:55:16 -0800 | [diff] [blame] | 466 | if (!Ctx->getFlags().UseELFWriter) |
| 467 | emitTextHeader(MangledName); |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 468 | for (CfgNode *Node : Nodes) |
| 469 | Node->emitIAS(this); |
Jan Voung | 08c3bcd | 2014-12-01 17:55:16 -0800 | [diff] [blame] | 470 | // Now write the function to the file and track. |
| 471 | if (Ctx->getFlags().UseELFWriter) { |
| 472 | getAssembler<Assembler>()->alignFunction(); |
| 473 | // TODO(jvoung): Transfer remaining fixups too. They may need their |
| 474 | // offsets adjusted. |
| 475 | Ctx->getObjectWriter()->writeFunctionCode( |
| 476 | MangledName, getInternal(), getAssembler<Assembler>()->getBufferView()); |
| 477 | } else { |
| 478 | getAssembler<Assembler>()->emitIASBytes(Ctx); |
| 479 | } |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 480 | } |
| 481 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 482 | // Dumps the IR with an optional introductory message. |
| 483 | void Cfg::dump(const IceString &Message) { |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 484 | if (!ALLOW_DUMP) |
| 485 | return; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 486 | if (!Ctx->isVerbose()) |
| 487 | return; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 488 | Ostream &Str = Ctx->getStrDump(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 489 | if (!Message.empty()) |
| 490 | Str << "================ " << Message << " ================\n"; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 491 | setCurrentNode(getEntryNode()); |
| 492 | // Print function name+args |
| 493 | if (getContext()->isVerbose(IceV_Instructions)) { |
| 494 | Str << "define "; |
Jim Stichnoth | 088b2be | 2014-10-23 12:02:08 -0700 | [diff] [blame] | 495 | if (getInternal() && !Ctx->getFlags().DisableInternal) |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 496 | Str << "internal "; |
Karl Schimpf | df6f9d1 | 2014-10-20 14:09:00 -0700 | [diff] [blame] | 497 | Str << ReturnType << " @" << Ctx->mangleName(getFunctionName()) << "("; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 498 | for (SizeT i = 0; i < Args.size(); ++i) { |
| 499 | if (i > 0) |
| 500 | Str << ", "; |
| 501 | Str << Args[i]->getType() << " "; |
| 502 | Args[i]->dump(this); |
| 503 | } |
| 504 | Str << ") {\n"; |
| 505 | } |
Jim Stichnoth | 800dab2 | 2014-09-20 12:25:02 -0700 | [diff] [blame] | 506 | resetCurrentNode(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 507 | if (getContext()->isVerbose(IceV_Liveness)) { |
| 508 | // Print summary info about variables |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 509 | for (Variable *Var : Variables) { |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 510 | Str << "// multiblock="; |
| 511 | if (getVMetadata()->isTracked(Var)) |
| 512 | Str << getVMetadata()->isMultiBlock(Var); |
| 513 | else |
| 514 | Str << "?"; |
| 515 | Str << " weight=" << Var->getWeight() << " "; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 516 | Var->dump(this); |
| 517 | Str << " LIVE=" << Var->getLiveRange() << "\n"; |
| 518 | } |
| 519 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 520 | // Print each basic block |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 521 | for (CfgNode *Node : Nodes) |
| 522 | Node->dump(this); |
| 523 | if (getContext()->isVerbose(IceV_Instructions)) |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 524 | Str << "}\n"; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 525 | } |
| 526 | |
| 527 | } // end of namespace Ice |