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 |
11 // management. | 11 // management. |
12 // | 12 // |
13 //===----------------------------------------------------------------------===// | 13 //===----------------------------------------------------------------------===// |
14 | 14 |
15 #include "IceCfg.h" | 15 #include "IceCfg.h" |
16 #include "IceCfgNode.h" | 16 #include "IceCfgNode.h" |
17 #include "IceDefs.h" | 17 #include "IceDefs.h" |
18 #include "IceInst.h" | 18 #include "IceInst.h" |
| 19 #include "IceLiveness.h" |
19 #include "IceOperand.h" | 20 #include "IceOperand.h" |
20 #include "IceTargetLowering.h" | 21 #include "IceTargetLowering.h" |
21 | 22 |
22 namespace Ice { | 23 namespace Ice { |
23 | 24 |
24 Cfg::Cfg(GlobalContext *Ctx) | 25 Cfg::Cfg(GlobalContext *Ctx) |
25 : Ctx(Ctx), FunctionName(""), ReturnType(IceType_void), | 26 : Ctx(Ctx), FunctionName(""), ReturnType(IceType_void), |
26 IsInternalLinkage(false), HasError(false), ErrorMessage(""), Entry(NULL), | 27 IsInternalLinkage(false), HasError(false), ErrorMessage(""), Entry(NULL), |
27 NextInstNumber(1), | 28 NextInstNumber(1), Live(NULL), |
28 Target(TargetLowering::createLowering(Ctx->getTargetArch(), this)), | 29 Target(TargetLowering::createLowering(Ctx->getTargetArch(), this)), |
29 CurrentNode(NULL) {} | 30 CurrentNode(NULL) {} |
30 | 31 |
31 Cfg::~Cfg() {} | 32 Cfg::~Cfg() {} |
32 | 33 |
33 void Cfg::setError(const IceString &Message) { | 34 void Cfg::setError(const IceString &Message) { |
34 HasError = true; | 35 HasError = true; |
35 ErrorMessage = Message; | 36 ErrorMessage = Message; |
36 Ctx->getStrDump() << "ICE translation error: " << ErrorMessage << "\n"; | 37 Ctx->getStrDump() << "ICE translation error: " << ErrorMessage << "\n"; |
37 } | 38 } |
(...skipping 17 matching lines...) Expand all Loading... |
55 void Cfg::addArg(Variable *Arg) { | 56 void Cfg::addArg(Variable *Arg) { |
56 Arg->setIsArg(this); | 57 Arg->setIsArg(this); |
57 Args.push_back(Arg); | 58 Args.push_back(Arg); |
58 } | 59 } |
59 | 60 |
60 // Returns whether the stack frame layout has been computed yet. This | 61 // Returns whether the stack frame layout has been computed yet. This |
61 // is used for dumping the stack frame location of Variables. | 62 // is used for dumping the stack frame location of Variables. |
62 bool Cfg::hasComputedFrame() const { return getTarget()->hasComputedFrame(); } | 63 bool Cfg::hasComputedFrame() const { return getTarget()->hasComputedFrame(); } |
63 | 64 |
64 void Cfg::translate() { | 65 void Cfg::translate() { |
65 Ostream &Str = Ctx->getStrDump(); | |
66 if (hasError()) | 66 if (hasError()) |
67 return; | 67 return; |
68 | 68 |
69 if (Ctx->isVerbose()) { | 69 dump("Initial CFG"); |
70 Str << "================ Initial CFG ================\n"; | |
71 dump(); | |
72 } | |
73 | 70 |
74 Timer T_translate; | 71 Timer T_translate; |
75 // The set of translation passes and their order are determined by | 72 // The set of translation passes and their order are determined by |
76 // the target. | 73 // the target. |
77 getTarget()->translate(); | 74 getTarget()->translate(); |
78 T_translate.printElapsedUs(getContext(), "translate()"); | 75 T_translate.printElapsedUs(getContext(), "translate()"); |
79 | 76 |
80 if (Ctx->isVerbose()) { | 77 dump("Final output"); |
81 Str << "================ Final output ================\n"; | |
82 dump(); | |
83 } | |
84 } | 78 } |
85 | 79 |
86 void Cfg::computePredecessors() { | 80 void Cfg::computePredecessors() { |
87 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { | 81 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
88 (*I)->computePredecessors(); | 82 (*I)->computePredecessors(); |
89 } | 83 } |
90 } | 84 } |
91 | 85 |
| 86 void Cfg::renumberInstructions() { |
| 87 NextInstNumber = 1; |
| 88 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
| 89 (*I)->renumberInstructions(); |
| 90 } |
| 91 } |
| 92 |
92 // placePhiLoads() must be called before placePhiStores(). | 93 // placePhiLoads() must be called before placePhiStores(). |
93 void Cfg::placePhiLoads() { | 94 void Cfg::placePhiLoads() { |
94 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { | 95 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
95 (*I)->placePhiLoads(); | 96 (*I)->placePhiLoads(); |
96 } | 97 } |
97 } | 98 } |
98 | 99 |
99 // placePhiStores() must be called after placePhiLoads(). | 100 // placePhiStores() must be called after placePhiLoads(). |
100 void Cfg::placePhiStores() { | 101 void Cfg::placePhiStores() { |
101 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { | 102 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
102 (*I)->placePhiStores(); | 103 (*I)->placePhiStores(); |
103 } | 104 } |
104 } | 105 } |
105 | 106 |
106 void Cfg::deletePhis() { | 107 void Cfg::deletePhis() { |
107 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { | 108 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
108 (*I)->deletePhis(); | 109 (*I)->deletePhis(); |
109 } | 110 } |
110 } | 111 } |
111 | 112 |
| 113 void Cfg::doAddressOpt() { |
| 114 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
| 115 (*I)->doAddressOpt(); |
| 116 } |
| 117 } |
| 118 |
112 void Cfg::genCode() { | 119 void Cfg::genCode() { |
113 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { | 120 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
114 (*I)->genCode(); | 121 (*I)->genCode(); |
115 } | 122 } |
116 } | 123 } |
117 | 124 |
118 // Compute the stack frame layout. | 125 // Compute the stack frame layout. |
119 void Cfg::genFrame() { | 126 void Cfg::genFrame() { |
120 getTarget()->addProlog(Entry); | 127 getTarget()->addProlog(Entry); |
121 // TODO: Consider folding epilog generation into the final | 128 // TODO: Consider folding epilog generation into the final |
122 // emission/assembly pass to avoid an extra iteration over the node | 129 // emission/assembly pass to avoid an extra iteration over the node |
123 // list. Or keep a separate list of exit nodes. | 130 // list. Or keep a separate list of exit nodes. |
124 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { | 131 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
125 CfgNode *Node = *I; | 132 CfgNode *Node = *I; |
126 if (Node->getHasReturn()) | 133 if (Node->getHasReturn()) |
127 getTarget()->addEpilog(Node); | 134 getTarget()->addEpilog(Node); |
128 } | 135 } |
129 } | 136 } |
130 | 137 |
| 138 // This is a lightweight version of live-range-end calculation. Marks |
| 139 // the last use of only those variables whose definition and uses are |
| 140 // completely with a single block. It is a quick single pass and |
| 141 // doesn't need to iterate until convergence. |
| 142 void Cfg::livenessLightweight() { |
| 143 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
| 144 (*I)->livenessLightweight(); |
| 145 } |
| 146 } |
| 147 |
| 148 void Cfg::liveness(LivenessMode Mode) { |
| 149 Live.reset(new Liveness(this, Mode)); |
| 150 Live->init(); |
| 151 // Initialize with all nodes needing to be processed. |
| 152 llvm::BitVector NeedToProcess(Nodes.size(), true); |
| 153 while (NeedToProcess.any()) { |
| 154 // Iterate in reverse topological order to speed up convergence. |
| 155 for (NodeList::reverse_iterator I = Nodes.rbegin(), E = Nodes.rend(); |
| 156 I != E; ++I) { |
| 157 CfgNode *Node = *I; |
| 158 if (NeedToProcess[Node->getIndex()]) { |
| 159 NeedToProcess[Node->getIndex()] = false; |
| 160 bool Changed = Node->liveness(getLiveness()); |
| 161 if (Changed) { |
| 162 // If the beginning-of-block liveness changed since the last |
| 163 // iteration, mark all in-edges as needing to be processed. |
| 164 const NodeList &InEdges = Node->getInEdges(); |
| 165 for (NodeList::const_iterator I1 = InEdges.begin(), |
| 166 E1 = InEdges.end(); |
| 167 I1 != E1; ++I1) { |
| 168 CfgNode *Pred = *I1; |
| 169 NeedToProcess[Pred->getIndex()] = true; |
| 170 } |
| 171 } |
| 172 } |
| 173 } |
| 174 } |
| 175 if (Mode == Liveness_Intervals) { |
| 176 // Reset each variable's live range. |
| 177 for (VarList::const_iterator I = Variables.begin(), E = Variables.end(); |
| 178 I != E; ++I) { |
| 179 if (Variable *Var = *I) |
| 180 Var->resetLiveRange(); |
| 181 } |
| 182 } |
| 183 // Collect timing for just the portion that constructs the live |
| 184 // range intervals based on the end-of-live-range computation, for a |
| 185 // finer breakdown of the cost. |
| 186 Timer T_liveRange; |
| 187 // Make a final pass over instructions to delete dead instructions |
| 188 // and build each Variable's live range. |
| 189 for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
| 190 (*I)->livenessPostprocess(Mode, getLiveness()); |
| 191 } |
| 192 if (Mode == Liveness_Intervals) { |
| 193 // Special treatment for live in-args. Their liveness needs to |
| 194 // extend beyond the beginning of the function, otherwise an arg |
| 195 // whose only use is in the first instruction will end up having |
| 196 // the trivial live range [1,1) and will *not* interfere with |
| 197 // other arguments. So if the first instruction of the method is |
| 198 // "r=arg1+arg2", both args may be assigned the same register. |
| 199 for (SizeT I = 0; I < Args.size(); ++I) { |
| 200 Variable *Arg = Args[I]; |
| 201 if (!Live->getLiveRange(Arg).isEmpty()) { |
| 202 // Add live range [-1,0) with weight 0. TODO: Here and below, |
| 203 // use better symbolic constants along the lines of |
| 204 // Inst::NumberDeleted and Inst::NumberSentinel instead of -1 |
| 205 // and 0. |
| 206 Live->addLiveRange(Arg, -1, 0, 0); |
| 207 } |
| 208 // Do the same for i64 args that may have been lowered into i32 |
| 209 // Lo and Hi components. |
| 210 Variable *Lo = Arg->getLo(); |
| 211 if (Lo && !Live->getLiveRange(Lo).isEmpty()) |
| 212 Live->addLiveRange(Lo, -1, 0, 0); |
| 213 Variable *Hi = Arg->getHi(); |
| 214 if (Hi && !Live->getLiveRange(Hi).isEmpty()) |
| 215 Live->addLiveRange(Hi, -1, 0, 0); |
| 216 } |
| 217 // Copy Liveness::LiveRanges into individual variables. TODO: |
| 218 // Remove Variable::LiveRange and redirect to |
| 219 // Liveness::LiveRanges. TODO: make sure Variable weights |
| 220 // are applied properly. |
| 221 SizeT NumVars = Variables.size(); |
| 222 for (SizeT i = 0; i < NumVars; ++i) { |
| 223 Variable *Var = Variables[i]; |
| 224 Var->setLiveRange(Live->getLiveRange(Var)); |
| 225 if (Var->getWeight().isInf()) |
| 226 Var->setLiveRangeInfiniteWeight(); |
| 227 } |
| 228 T_liveRange.printElapsedUs(getContext(), "live range construction"); |
| 229 dump(); |
| 230 } |
| 231 } |
| 232 |
| 233 // Traverse every Variable of every Inst and verify that it |
| 234 // appears within the Variable's computed live range. |
| 235 bool Cfg::validateLiveness() const { |
| 236 bool Valid = true; |
| 237 Ostream &Str = Ctx->getStrDump(); |
| 238 for (NodeList::const_iterator I1 = Nodes.begin(), E1 = Nodes.end(); I1 != E1; |
| 239 ++I1) { |
| 240 CfgNode *Node = *I1; |
| 241 InstList &Insts = Node->getInsts(); |
| 242 for (InstList::const_iterator I2 = Insts.begin(), E2 = Insts.end(); |
| 243 I2 != E2; ++I2) { |
| 244 Inst *Inst = *I2; |
| 245 if (Inst->isDeleted()) |
| 246 continue; |
| 247 if (llvm::isa<InstFakeKill>(Inst)) |
| 248 continue; |
| 249 InstNumberT InstNumber = Inst->getNumber(); |
| 250 Variable *Dest = Inst->getDest(); |
| 251 if (Dest) { |
| 252 // TODO: This instruction should actually begin Dest's live |
| 253 // range, so we could probably test that this instruction is |
| 254 // the beginning of some segment of Dest's live range. But |
| 255 // this wouldn't work with non-SSA temporaries during |
| 256 // lowering. |
| 257 if (!Dest->getLiveRange().containsValue(InstNumber)) { |
| 258 Valid = false; |
| 259 Str << "Liveness error: inst " << Inst->getNumber() << " dest "; |
| 260 Dest->dump(this); |
| 261 Str << " live range " << Dest->getLiveRange() << "\n"; |
| 262 } |
| 263 } |
| 264 for (SizeT I = 0; I < Inst->getSrcSize(); ++I) { |
| 265 Operand *Src = Inst->getSrc(I); |
| 266 SizeT NumVars = Src->getNumVars(); |
| 267 for (SizeT J = 0; J < NumVars; ++J) { |
| 268 const Variable *Var = Src->getVar(J); |
| 269 if (!Var->getLiveRange().containsValue(InstNumber)) { |
| 270 Valid = false; |
| 271 Str << "Liveness error: inst " << Inst->getNumber() << " var "; |
| 272 Var->dump(this); |
| 273 Str << " live range " << Var->getLiveRange() << "\n"; |
| 274 } |
| 275 } |
| 276 } |
| 277 } |
| 278 } |
| 279 return Valid; |
| 280 } |
| 281 |
131 // ======================== Dump routines ======================== // | 282 // ======================== Dump routines ======================== // |
132 | 283 |
133 void Cfg::emit() { | 284 void Cfg::emit() { |
134 Ostream &Str = Ctx->getStrEmit(); | 285 Ostream &Str = Ctx->getStrEmit(); |
135 Timer T_emit; | 286 Timer T_emit; |
136 if (!Ctx->testAndSetHasEmittedFirstMethod()) { | 287 if (!Ctx->testAndSetHasEmittedFirstMethod()) { |
137 // Print a helpful command for assembling the output. | 288 // Print a helpful command for assembling the output. |
138 // TODO: have the Target emit the header | 289 // TODO: have the Target emit the header |
139 // TODO: need a per-file emit in addition to per-CFG | 290 // TODO: need a per-file emit in addition to per-CFG |
140 Str << "# $LLVM_BIN_PATH/llvm-mc" | 291 Str << "# $LLVM_BIN_PATH/llvm-mc" |
(...skipping 10 matching lines...) Expand all Loading... |
151 Str << "\t.type\t" << MangledName << ",@function\n"; | 302 Str << "\t.type\t" << MangledName << ",@function\n"; |
152 } | 303 } |
153 for (NodeList::const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; | 304 for (NodeList::const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; |
154 ++I) { | 305 ++I) { |
155 (*I)->emit(this); | 306 (*I)->emit(this); |
156 } | 307 } |
157 Str << "\n"; | 308 Str << "\n"; |
158 T_emit.printElapsedUs(Ctx, "emit()"); | 309 T_emit.printElapsedUs(Ctx, "emit()"); |
159 } | 310 } |
160 | 311 |
161 void Cfg::dump() { | 312 // Dumps the IR with an optional introductory message. |
| 313 void Cfg::dump(const IceString &Message) { |
| 314 if (!Ctx->isVerbose()) |
| 315 return; |
162 Ostream &Str = Ctx->getStrDump(); | 316 Ostream &Str = Ctx->getStrDump(); |
| 317 if (!Message.empty()) |
| 318 Str << "================ " << Message << " ================\n"; |
163 setCurrentNode(getEntryNode()); | 319 setCurrentNode(getEntryNode()); |
164 // Print function name+args | 320 // Print function name+args |
165 if (getContext()->isVerbose(IceV_Instructions)) { | 321 if (getContext()->isVerbose(IceV_Instructions)) { |
166 Str << "define "; | 322 Str << "define "; |
167 if (getInternal()) | 323 if (getInternal()) |
168 Str << "internal "; | 324 Str << "internal "; |
169 Str << ReturnType << " @" << getFunctionName() << "("; | 325 Str << ReturnType << " @" << getFunctionName() << "("; |
170 for (SizeT i = 0; i < Args.size(); ++i) { | 326 for (SizeT i = 0; i < Args.size(); ++i) { |
171 if (i > 0) | 327 if (i > 0) |
172 Str << ", "; | 328 Str << ", "; |
173 Str << Args[i]->getType() << " "; | 329 Str << Args[i]->getType() << " "; |
174 Args[i]->dump(this); | 330 Args[i]->dump(this); |
175 } | 331 } |
176 Str << ") {\n"; | 332 Str << ") {\n"; |
177 } | 333 } |
178 setCurrentNode(NULL); | 334 setCurrentNode(NULL); |
| 335 if (getContext()->isVerbose(IceV_Liveness)) { |
| 336 // Print summary info about variables |
| 337 for (VarList::const_iterator I = Variables.begin(), E = Variables.end(); |
| 338 I != E; ++I) { |
| 339 Variable *Var = *I; |
| 340 Str << "//" |
| 341 << " multiblock=" << Var->isMultiblockLife() << " " |
| 342 << " weight=" << Var->getWeight() << " "; |
| 343 Var->dump(this); |
| 344 Str << " LIVE=" << Var->getLiveRange() << "\n"; |
| 345 } |
| 346 } |
179 // Print each basic block | 347 // Print each basic block |
180 for (NodeList::const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; | 348 for (NodeList::const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; |
181 ++I) { | 349 ++I) { |
182 (*I)->dump(this); | 350 (*I)->dump(this); |
183 } | 351 } |
184 if (getContext()->isVerbose(IceV_Instructions)) { | 352 if (getContext()->isVerbose(IceV_Instructions)) { |
185 Str << "}\n"; | 353 Str << "}\n"; |
186 } | 354 } |
187 } | 355 } |
188 | 356 |
189 } // end of namespace Ice | 357 } // end of namespace Ice |
OLD | NEW |