OLD | NEW |
1 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===// | 1 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===// |
2 // | 2 // |
3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 // | 9 // |
10 // This file implements the Cfg class, including constant pool | 10 // This file implements the Cfg class, including constant pool |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
109 for (CfgNode *Node : Nodes) | 109 for (CfgNode *Node : Nodes) |
110 Node->placePhiStores(); | 110 Node->placePhiStores(); |
111 } | 111 } |
112 | 112 |
113 void Cfg::deletePhis() { | 113 void Cfg::deletePhis() { |
114 TimerMarker T(TimerStack::TT_deletePhis, this); | 114 TimerMarker T(TimerStack::TT_deletePhis, this); |
115 for (CfgNode *Node : Nodes) | 115 for (CfgNode *Node : Nodes) |
116 Node->deletePhis(); | 116 Node->deletePhis(); |
117 } | 117 } |
118 | 118 |
| 119 void Cfg::advancedPhiLowering() { |
| 120 TimerMarker T(TimerStack::TT_advancedPhiLowering, this); |
| 121 // This splits edges and appends new nodes to the end of the node |
| 122 // list. This can invalidate iterators, so don't use an iterator. |
| 123 SizeT NumNodes = getNumNodes(); |
| 124 for (SizeT I = 0; I < NumNodes; ++I) |
| 125 Nodes[I]->advancedPhiLowering(); |
| 126 } |
| 127 |
| 128 // Find a reasonable placement for nodes that have not yet been |
| 129 // placed, while maintaining the same relative ordering among already |
| 130 // placed nodes. |
| 131 void Cfg::reorderNodes() { |
| 132 typedef std::list<CfgNode *> PlacedList; |
| 133 PlacedList Placed; // Nodes with relative placement locked down |
| 134 PlacedList Unreachable; // Unreachable nodes |
| 135 PlacedList::iterator NoPlace = Placed.end(); |
| 136 // Keep track of where each node has been tentatively placed so that |
| 137 // we can manage insertions into the middle. |
| 138 std::vector<PlacedList::iterator> PlaceIndex(Nodes.size(), NoPlace); |
| 139 for (CfgNode *Node : Nodes) { |
| 140 // The "do ... while(0);" construct is to factor out the |
| 141 // --PlaceIndex and assert() statements before moving to the next |
| 142 // node. |
| 143 do { |
| 144 if (!Node->needsPlacement()) { |
| 145 // Add to the end of the Placed list. |
| 146 Placed.push_back(Node); |
| 147 PlaceIndex[Node->getIndex()] = Placed.end(); |
| 148 continue; |
| 149 } |
| 150 Node->setNeedsPlacement(false); |
| 151 if (Node != getEntryNode() && Node->getInEdges().size() == 0) { |
| 152 // The node has essentially been deleted since it is not a |
| 153 // successor of any other node. |
| 154 Unreachable.push_back(Node); |
| 155 PlaceIndex[Node->getIndex()] = Unreachable.end(); |
| 156 continue; |
| 157 } |
| 158 // Assume for now that the unplaced node is from edge-splitting |
| 159 // and therefore has 1 in-edge and 1 out-edge (actually, possibly |
| 160 // more than 1 in-edge if the predecessor node was contracted). |
| 161 // If this changes in the future, rethink the strategy. |
| 162 assert(Node->getInEdges().size() >= 1); |
| 163 assert(Node->getOutEdges().size() == 1); |
| 164 |
| 165 // If it's a (non-critical) edge where the successor has a single |
| 166 // in-edge, then place it before the successor. |
| 167 CfgNode *Succ = Node->getOutEdges()[0]; |
| 168 if (Succ->getInEdges().size() == 1 && |
| 169 PlaceIndex[Succ->getIndex()] != NoPlace) { |
| 170 Placed.insert(PlaceIndex[Succ->getIndex()], Node); |
| 171 PlaceIndex[Node->getIndex()] = PlaceIndex[Succ->getIndex()]; |
| 172 continue; |
| 173 } |
| 174 |
| 175 // Otherwise, place it after the (first) predecessor. |
| 176 CfgNode *Pred = Node->getInEdges()[0]; |
| 177 auto PredPosition = PlaceIndex[Pred->getIndex()]; |
| 178 // It shouldn't be the case that PredPosition==NoPlace, but if |
| 179 // that somehow turns out to be true, we just insert Node before |
| 180 // PredPosition=NoPlace=Placed.end() . |
| 181 if (PredPosition != NoPlace) |
| 182 ++PredPosition; |
| 183 Placed.insert(PredPosition, Node); |
| 184 PlaceIndex[Node->getIndex()] = PredPosition; |
| 185 } while (0); |
| 186 |
| 187 --PlaceIndex[Node->getIndex()]; |
| 188 assert(*PlaceIndex[Node->getIndex()] == Node); |
| 189 } |
| 190 |
| 191 // Reorder Nodes according to the built-up lists. |
| 192 SizeT Cur = 0; |
| 193 for (CfgNode *Node : Placed) |
| 194 Nodes[Cur++] = Node; |
| 195 for (CfgNode *Node : Unreachable) |
| 196 Nodes[Cur++] = Node; |
| 197 assert(Cur == Nodes.size()); |
| 198 } |
| 199 |
119 void Cfg::doArgLowering() { | 200 void Cfg::doArgLowering() { |
120 TimerMarker T(TimerStack::TT_doArgLowering, this); | 201 TimerMarker T(TimerStack::TT_doArgLowering, this); |
121 getTarget()->lowerArguments(); | 202 getTarget()->lowerArguments(); |
122 } | 203 } |
123 | 204 |
124 void Cfg::doAddressOpt() { | 205 void Cfg::doAddressOpt() { |
125 TimerMarker T(TimerStack::TT_doAddressOpt, this); | 206 TimerMarker T(TimerStack::TT_doAddressOpt, this); |
126 for (CfgNode *Node : Nodes) | 207 for (CfgNode *Node : Nodes) |
127 Node->doAddressOpt(); | 208 Node->doAddressOpt(); |
128 } | 209 } |
(...skipping 161 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
290 // liveness inconsistencies. | 371 // liveness inconsistencies. |
291 void Cfg::deleteRedundantAssignments() { | 372 void Cfg::deleteRedundantAssignments() { |
292 for (CfgNode *Node : Nodes) { | 373 for (CfgNode *Node : Nodes) { |
293 // Ignore Phi instructions. | 374 // Ignore Phi instructions. |
294 for (Inst *I : Node->getInsts()) | 375 for (Inst *I : Node->getInsts()) |
295 if (I->isRedundantAssign()) | 376 if (I->isRedundantAssign()) |
296 I->setDeleted(); | 377 I->setDeleted(); |
297 } | 378 } |
298 } | 379 } |
299 | 380 |
| 381 void Cfg::contractEmptyNodes() { |
| 382 for (CfgNode *Node : Nodes) { |
| 383 Node->contractIfEmpty(); |
| 384 } |
| 385 } |
| 386 |
300 void Cfg::doBranchOpt() { | 387 void Cfg::doBranchOpt() { |
301 TimerMarker T(TimerStack::TT_doBranchOpt, this); | 388 TimerMarker T(TimerStack::TT_doBranchOpt, this); |
302 for (auto I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { | 389 for (auto I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
303 auto NextNode = I; | 390 auto NextNode = I; |
304 ++NextNode; | 391 ++NextNode; |
305 (*I)->doBranchOpt(NextNode == E ? NULL : *NextNode); | 392 (*I)->doBranchOpt(NextNode == E ? NULL : *NextNode); |
306 } | 393 } |
307 } | 394 } |
308 | 395 |
309 // ======================== Dump routines ======================== // | 396 // ======================== Dump routines ======================== // |
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
376 } | 463 } |
377 } | 464 } |
378 // Print each basic block | 465 // Print each basic block |
379 for (CfgNode *Node : Nodes) | 466 for (CfgNode *Node : Nodes) |
380 Node->dump(this); | 467 Node->dump(this); |
381 if (getContext()->isVerbose(IceV_Instructions)) | 468 if (getContext()->isVerbose(IceV_Instructions)) |
382 Str << "}\n"; | 469 Str << "}\n"; |
383 } | 470 } |
384 | 471 |
385 } // end of namespace Ice | 472 } // end of namespace Ice |
OLD | NEW |