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 130 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
141 // --PlaceIndex and assert() statements before moving to the next | 141 // --PlaceIndex and assert() statements before moving to the next |
142 // node. | 142 // node. |
143 do { | 143 do { |
144 if (!Node->needsPlacement()) { | 144 if (!Node->needsPlacement()) { |
145 // Add to the end of the Placed list. | 145 // Add to the end of the Placed list. |
146 Placed.push_back(Node); | 146 Placed.push_back(Node); |
147 PlaceIndex[Node->getIndex()] = Placed.end(); | 147 PlaceIndex[Node->getIndex()] = Placed.end(); |
148 continue; | 148 continue; |
149 } | 149 } |
150 Node->setNeedsPlacement(false); | 150 Node->setNeedsPlacement(false); |
151 if (Node != getEntryNode() && Node->getInEdges().size() == 0) { | 151 if (Node != getEntryNode() && Node->getInEdges().empty()) { |
152 // The node has essentially been deleted since it is not a | 152 // The node has essentially been deleted since it is not a |
153 // successor of any other node. | 153 // successor of any other node. |
154 Unreachable.push_back(Node); | 154 Unreachable.push_back(Node); |
155 PlaceIndex[Node->getIndex()] = Unreachable.end(); | 155 PlaceIndex[Node->getIndex()] = Unreachable.end(); |
156 continue; | 156 continue; |
157 } | 157 } |
158 // Assume for now that the unplaced node is from edge-splitting | 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 | 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). | 160 // more than 1 in-edge if the predecessor node was contracted). |
161 // If this changes in the future, rethink the strategy. | 161 // If this changes in the future, rethink the strategy. |
162 assert(Node->getInEdges().size() >= 1); | 162 assert(Node->getInEdges().size() >= 1); |
163 assert(Node->getOutEdges().size() == 1); | 163 assert(Node->getOutEdges().size() == 1); |
164 | 164 |
165 // If it's a (non-critical) edge where the successor has a single | 165 // If it's a (non-critical) edge where the successor has a single |
166 // in-edge, then place it before the successor. | 166 // in-edge, then place it before the successor. |
167 CfgNode *Succ = Node->getOutEdges()[0]; | 167 CfgNode *Succ = Node->getOutEdges().front(); |
168 if (Succ->getInEdges().size() == 1 && | 168 if (Succ->getInEdges().size() == 1 && |
169 PlaceIndex[Succ->getIndex()] != NoPlace) { | 169 PlaceIndex[Succ->getIndex()] != NoPlace) { |
170 Placed.insert(PlaceIndex[Succ->getIndex()], Node); | 170 Placed.insert(PlaceIndex[Succ->getIndex()], Node); |
171 PlaceIndex[Node->getIndex()] = PlaceIndex[Succ->getIndex()]; | 171 PlaceIndex[Node->getIndex()] = PlaceIndex[Succ->getIndex()]; |
172 continue; | 172 continue; |
173 } | 173 } |
174 | 174 |
175 // Otherwise, place it after the (first) predecessor. | 175 // Otherwise, place it after the (first) predecessor. |
176 CfgNode *Pred = Node->getInEdges()[0]; | 176 CfgNode *Pred = Node->getInEdges().front(); |
177 auto PredPosition = PlaceIndex[Pred->getIndex()]; | 177 auto PredPosition = PlaceIndex[Pred->getIndex()]; |
178 // It shouldn't be the case that PredPosition==NoPlace, but if | 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 | 179 // that somehow turns out to be true, we just insert Node before |
180 // PredPosition=NoPlace=Placed.end() . | 180 // PredPosition=NoPlace=Placed.end() . |
181 if (PredPosition != NoPlace) | 181 if (PredPosition != NoPlace) |
182 ++PredPosition; | 182 ++PredPosition; |
183 Placed.insert(PredPosition, Node); | 183 Placed.insert(PredPosition, Node); |
184 PlaceIndex[Node->getIndex()] = PredPosition; | 184 PlaceIndex[Node->getIndex()] = PredPosition; |
185 } while (0); | 185 } while (0); |
186 | 186 |
187 --PlaceIndex[Node->getIndex()]; | 187 --PlaceIndex[Node->getIndex()]; |
188 assert(*PlaceIndex[Node->getIndex()] == Node); | 188 assert(*PlaceIndex[Node->getIndex()] == Node); |
189 } | 189 } |
190 | 190 |
191 // Reorder Nodes according to the built-up lists. | 191 // Reorder Nodes according to the built-up lists. |
192 SizeT Cur = 0; | 192 SizeT OldSize = Nodes.size(); |
Karl
2014/11/05 23:24:37
Note: One of the downsides to this is that size is
Jim Stichnoth
2014/11/05 23:39:45
In C++11, the complexity is constant.
| |
193 (void)OldSize; | |
Karl
2014/11/05 23:24:37
Why is this necessary?
Jim Stichnoth
2014/11/05 23:39:45
OldSize is only used in the assert, so otherwise y
| |
194 Nodes.clear(); | |
193 for (CfgNode *Node : Placed) | 195 for (CfgNode *Node : Placed) |
194 Nodes[Cur++] = Node; | 196 Nodes.push_back(Node); |
195 for (CfgNode *Node : Unreachable) | 197 for (CfgNode *Node : Unreachable) |
196 Nodes[Cur++] = Node; | 198 Nodes.push_back(Node); |
197 assert(Cur == Nodes.size()); | 199 assert(Nodes.size() == OldSize); |
198 } | 200 } |
199 | 201 |
200 void Cfg::doArgLowering() { | 202 void Cfg::doArgLowering() { |
201 TimerMarker T(TimerStack::TT_doArgLowering, this); | 203 TimerMarker T(TimerStack::TT_doArgLowering, this); |
202 getTarget()->lowerArguments(); | 204 getTarget()->lowerArguments(); |
203 } | 205 } |
204 | 206 |
205 void Cfg::doAddressOpt() { | 207 void Cfg::doAddressOpt() { |
206 TimerMarker T(TimerStack::TT_doAddressOpt, this); | 208 TimerMarker T(TimerStack::TT_doAddressOpt, this); |
207 for (CfgNode *Node : Nodes) | 209 for (CfgNode *Node : Nodes) |
(...skipping 253 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
461 } | 463 } |
462 } | 464 } |
463 // Print each basic block | 465 // Print each basic block |
464 for (CfgNode *Node : Nodes) | 466 for (CfgNode *Node : Nodes) |
465 Node->dump(this); | 467 Node->dump(this); |
466 if (getContext()->isVerbose(IceV_Instructions)) | 468 if (getContext()->isVerbose(IceV_Instructions)) |
467 Str << "}\n"; | 469 Str << "}\n"; |
468 } | 470 } |
469 | 471 |
470 } // end of namespace Ice | 472 } // end of namespace Ice |
OLD | NEW |