OLD | NEW |
1 //===- subzero/src/IceCfgNode.cpp - Basic block (node) implementation -----===// | 1 //===- subzero/src/IceCfgNode.cpp - Basic block (node) 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 CfgNode class, including the | 10 // This file implements the CfgNode class, including the complexities |
11 // complexities of instruction insertion and in-edge calculation. | 11 // of instruction insertion and in-edge calculation. |
12 // | 12 // |
13 //===----------------------------------------------------------------------===// | 13 //===----------------------------------------------------------------------===// |
14 | 14 |
15 #include "IceCfg.h" | 15 #include "IceCfg.h" |
16 #include "IceCfgNode.h" | 16 #include "IceCfgNode.h" |
17 #include "IceInst.h" | 17 #include "IceInst.h" |
18 #include "IceOperand.h" | 18 #include "IceOperand.h" |
| 19 #include "IceTargetLowering.h" |
19 | 20 |
20 namespace Ice { | 21 namespace Ice { |
21 | 22 |
22 CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber, IceString Name) | 23 CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber, IceString Name) |
23 : Func(Func), Number(LabelNumber), Name(Name) {} | 24 : Func(Func), Number(LabelNumber), Name(Name), HasReturn(false) {} |
24 | 25 |
25 // Returns the name the node was created with. If no name was given, | 26 // Returns the name the node was created with. If no name was given, |
26 // it synthesizes a (hopefully) unique name. | 27 // it synthesizes a (hopefully) unique name. |
27 IceString CfgNode::getName() const { | 28 IceString CfgNode::getName() const { |
28 if (!Name.empty()) | 29 if (!Name.empty()) |
29 return Name; | 30 return Name; |
30 char buf[30]; | 31 char buf[30]; |
31 snprintf(buf, llvm::array_lengthof(buf), "__%u", getIndex()); | 32 snprintf(buf, llvm::array_lengthof(buf), "__%u", getIndex()); |
32 return buf; | 33 return buf; |
33 } | 34 } |
(...skipping 20 matching lines...) Expand all Loading... |
54 // creating the InEdges list. | 55 // creating the InEdges list. |
55 void CfgNode::computePredecessors() { | 56 void CfgNode::computePredecessors() { |
56 OutEdges = (*Insts.rbegin())->getTerminatorEdges(); | 57 OutEdges = (*Insts.rbegin())->getTerminatorEdges(); |
57 for (NodeList::const_iterator I = OutEdges.begin(), E = OutEdges.end(); | 58 for (NodeList::const_iterator I = OutEdges.begin(), E = OutEdges.end(); |
58 I != E; ++I) { | 59 I != E; ++I) { |
59 CfgNode *Node = *I; | 60 CfgNode *Node = *I; |
60 Node->InEdges.push_back(this); | 61 Node->InEdges.push_back(this); |
61 } | 62 } |
62 } | 63 } |
63 | 64 |
| 65 // This does part 1 of Phi lowering, by creating a new dest variable |
| 66 // for each Phi instruction, replacing the Phi instruction's dest with |
| 67 // that variable, and adding an explicit assignment of the old dest to |
| 68 // the new dest. For example, |
| 69 // a=phi(...) |
| 70 // changes to |
| 71 // "a_phi=phi(...); a=a_phi". |
| 72 // |
| 73 // This is in preparation for part 2 which deletes the Phi |
| 74 // instructions and appends assignment instructions to predecessor |
| 75 // blocks. Note that this transformation preserves SSA form. |
| 76 void CfgNode::placePhiLoads() { |
| 77 for (PhiList::iterator I = Phis.begin(), E = Phis.end(); I != E; ++I) { |
| 78 Inst *Inst = (*I)->lower(Func, this); |
| 79 Insts.insert(Insts.begin(), Inst); |
| 80 Inst->updateVars(this); |
| 81 } |
| 82 } |
| 83 |
| 84 // This does part 2 of Phi lowering. For each Phi instruction at each |
| 85 // out-edge, create a corresponding assignment instruction, and add |
| 86 // all the assignments near the end of this block. They need to be |
| 87 // added before any branch instruction, and also if the block ends |
| 88 // with a compare instruction followed by a branch instruction that we |
| 89 // may want to fuse, it's better to insert the new assignments before |
| 90 // the compare instruction. |
| 91 // |
| 92 // Note that this transformation takes the Phi dest variables out of |
| 93 // SSA form, as there may be assignments to the dest variable in |
| 94 // multiple blocks. |
| 95 // |
| 96 // TODO: Defer this pass until after register allocation, then split |
| 97 // critical edges, add the assignments, and lower them. This should |
| 98 // reduce the amount of shuffling at the end of each block. |
| 99 void CfgNode::placePhiStores() { |
| 100 // Find the insertion point. TODO: After branch/compare fusing is |
| 101 // implemented, try not to insert Phi stores between the compare and |
| 102 // conditional branch instructions, otherwise the branch/compare |
| 103 // pattern matching may fail. However, the branch/compare sequence |
| 104 // will have to be broken if the compare result is read (by the |
| 105 // assignment) before it is written (by the compare). |
| 106 InstList::iterator InsertionPoint = Insts.end(); |
| 107 // Every block must end in a terminator instruction. |
| 108 assert(InsertionPoint != Insts.begin()); |
| 109 --InsertionPoint; |
| 110 // Confirm via assert() that InsertionPoint is a terminator |
| 111 // instruction. Calling getTerminatorEdges() on a non-terminator |
| 112 // instruction will cause an llvm_unreachable(). |
| 113 assert(((*InsertionPoint)->getTerminatorEdges(), true)); |
| 114 |
| 115 // Consider every out-edge. |
| 116 for (NodeList::const_iterator I1 = OutEdges.begin(), E1 = OutEdges.end(); |
| 117 I1 != E1; ++I1) { |
| 118 CfgNode *Target = *I1; |
| 119 // Consider every Phi instruction at the out-edge. |
| 120 for (PhiList::const_iterator I2 = Target->Phis.begin(), |
| 121 E2 = Target->Phis.end(); |
| 122 I2 != E2; ++I2) { |
| 123 Operand *Operand = (*I2)->getOperandForTarget(this); |
| 124 assert(Operand); |
| 125 Variable *Dest = (*I2)->getDest(); |
| 126 assert(Dest); |
| 127 InstAssign *NewInst = InstAssign::create(Func, Dest, Operand); |
| 128 // If Src is a variable, set the Src and Dest variables to |
| 129 // prefer each other for register allocation. |
| 130 if (Variable *Src = llvm::dyn_cast<Variable>(Operand)) { |
| 131 bool AllowOverlap = false; |
| 132 Dest->setPreferredRegister(Src, AllowOverlap); |
| 133 Src->setPreferredRegister(Dest, AllowOverlap); |
| 134 } |
| 135 Insts.insert(InsertionPoint, NewInst); |
| 136 NewInst->updateVars(this); |
| 137 } |
| 138 } |
| 139 } |
| 140 |
| 141 // Deletes the phi instructions after the loads and stores are placed. |
| 142 void CfgNode::deletePhis() { |
| 143 for (PhiList::iterator I = Phis.begin(), E = Phis.end(); I != E; ++I) { |
| 144 (*I)->setDeleted(); |
| 145 } |
| 146 } |
| 147 |
| 148 // Drives the target lowering. Passes the current instruction and the |
| 149 // next non-deleted instruction for target lowering. |
| 150 void CfgNode::genCode() { |
| 151 TargetLowering *Target = Func->getTarget(); |
| 152 LoweringContext &Context = Target->getContext(); |
| 153 // Lower only the regular instructions. Defer the Phi instructions. |
| 154 Context.init(this); |
| 155 while (!Context.atEnd()) { |
| 156 InstList::iterator Orig = Context.getCur(); |
| 157 if (llvm::isa<InstRet>(*Orig)) |
| 158 setHasReturn(); |
| 159 Target->lower(); |
| 160 // Ensure target lowering actually moved the cursor. |
| 161 assert(Context.getCur() != Orig); |
| 162 } |
| 163 } |
| 164 |
64 // ======================== Dump routines ======================== // | 165 // ======================== Dump routines ======================== // |
65 | 166 |
| 167 void CfgNode::emit(Cfg *Func) const { |
| 168 Func->setCurrentNode(this); |
| 169 Ostream &Str = Func->getContext()->getStrEmit(); |
| 170 if (Func->getEntryNode() == this) { |
| 171 Str << Func->getContext()->mangleName(Func->getFunctionName()) << ":\n"; |
| 172 } |
| 173 Str << getAsmName() << ":\n"; |
| 174 for (PhiList::const_iterator I = Phis.begin(), E = Phis.end(); I != E; ++I) { |
| 175 InstPhi *Inst = *I; |
| 176 if (Inst->isDeleted()) |
| 177 continue; |
| 178 // Emitting a Phi instruction should cause an error. |
| 179 Inst->emit(Func); |
| 180 } |
| 181 for (InstList::const_iterator I = Insts.begin(), E = Insts.end(); I != E; |
| 182 ++I) { |
| 183 Inst *Inst = *I; |
| 184 if (Inst->isDeleted()) |
| 185 continue; |
| 186 // Here we detect redundant assignments like "mov eax, eax" and |
| 187 // suppress them. |
| 188 if (Inst->isRedundantAssign()) |
| 189 continue; |
| 190 (*I)->emit(Func); |
| 191 } |
| 192 } |
| 193 |
66 void CfgNode::dump(Cfg *Func) const { | 194 void CfgNode::dump(Cfg *Func) const { |
67 Func->setCurrentNode(this); | 195 Func->setCurrentNode(this); |
68 Ostream &Str = Func->getContext()->getStrDump(); | 196 Ostream &Str = Func->getContext()->getStrDump(); |
69 if (Func->getContext()->isVerbose(IceV_Instructions)) { | 197 if (Func->getContext()->isVerbose(IceV_Instructions)) { |
70 Str << getName() << ":\n"; | 198 Str << getName() << ":\n"; |
71 } | 199 } |
72 // Dump list of predecessor nodes. | 200 // Dump list of predecessor nodes. |
73 if (Func->getContext()->isVerbose(IceV_Preds) && !InEdges.empty()) { | 201 if (Func->getContext()->isVerbose(IceV_Preds) && !InEdges.empty()) { |
74 Str << " // preds = "; | 202 Str << " // preds = "; |
75 for (NodeList::const_iterator I = InEdges.begin(), E = InEdges.end(); | 203 for (NodeList::const_iterator I = InEdges.begin(), E = InEdges.end(); |
(...skipping 24 matching lines...) Expand all Loading... |
100 I != E; ++I) { | 228 I != E; ++I) { |
101 if (I != OutEdges.begin()) | 229 if (I != OutEdges.begin()) |
102 Str << ", "; | 230 Str << ", "; |
103 Str << "%" << (*I)->getName(); | 231 Str << "%" << (*I)->getName(); |
104 } | 232 } |
105 Str << "\n"; | 233 Str << "\n"; |
106 } | 234 } |
107 } | 235 } |
108 | 236 |
109 } // end of namespace Ice | 237 } // end of namespace Ice |
OLD | NEW |