Index: src/IceCfgNode.cpp |
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp |
index fe8b70e0850b1274c4279991bd1ddb72675d2595..c00b2c77538a49faf6b7fe37af067b0fccda7094 100644 |
--- a/src/IceCfgNode.cpp |
+++ b/src/IceCfgNode.cpp |
@@ -7,8 +7,8 @@ |
// |
//===----------------------------------------------------------------------===// |
// |
-// This file implements the CfgNode class, including the |
-// complexities of instruction insertion and in-edge calculation. |
+// This file implements the CfgNode class, including the complexities |
+// of instruction insertion and in-edge calculation. |
// |
//===----------------------------------------------------------------------===// |
@@ -16,11 +16,12 @@ |
#include "IceCfgNode.h" |
#include "IceInst.h" |
#include "IceOperand.h" |
+#include "IceTargetLowering.h" |
namespace Ice { |
CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber, IceString Name) |
- : Func(Func), Number(LabelNumber), Name(Name) {} |
+ : Func(Func), Number(LabelNumber), Name(Name), HasReturn(false) {} |
// Returns the name the node was created with. If no name was given, |
// it synthesizes a (hopefully) unique name. |
@@ -61,8 +62,135 @@ void CfgNode::computePredecessors() { |
} |
} |
+// This does part 1 of Phi lowering, by creating a new dest variable |
+// for each Phi instruction, replacing the Phi instruction's dest with |
+// that variable, and adding an explicit assignment of the old dest to |
+// the new dest. For example, |
+// a=phi(...) |
+// changes to |
+// "a_phi=phi(...); a=a_phi". |
+// |
+// This is in preparation for part 2 which deletes the Phi |
+// instructions and appends assignment instructions to predecessor |
+// blocks. Note that this transformation preserves SSA form. |
+void CfgNode::placePhiLoads() { |
+ for (PhiList::iterator I = Phis.begin(), E = Phis.end(); I != E; ++I) { |
+ Inst *Inst = (*I)->lower(Func, this); |
+ Insts.insert(Insts.begin(), Inst); |
+ Inst->updateVars(this); |
+ } |
+} |
+ |
+// This does part 2 of Phi lowering. For each Phi instruction at each |
+// out-edge, create a corresponding assignment instruction, and add |
+// all the assignments near the end of this block. They need to be |
+// added before any branch instruction, and also if the block ends |
+// with a compare instruction followed by a branch instruction that we |
+// may want to fuse, it's better to insert the new assignments before |
+// the compare instruction. |
+// |
+// Note that this transformation takes the Phi dest variables out of |
+// SSA form, as there may be assignments to the dest variable in |
+// multiple blocks. |
+// |
+// TODO: Defer this pass until after register allocation, then split |
+// critical edges, add the assignments, and lower them. This should |
+// reduce the amount of shuffling at the end of each block. |
+void CfgNode::placePhiStores() { |
+ // Find the insertion point. TODO: After branch/compare fusing is |
+ // implemented, try not to insert Phi stores between the compare and |
+ // conditional branch instructions, otherwise the branch/compare |
+ // pattern matching may fail. However, the branch/compare sequence |
+ // will have to be broken if the compare result is read (by the |
+ // assignment) before it is written (by the compare). |
+ InstList::iterator InsertionPoint = Insts.end(); |
+ // Every block must end in a terminator instruction. |
+ assert(InsertionPoint != Insts.begin()); |
+ --InsertionPoint; |
+ // Confirm via assert() that InsertionPoint is a terminator |
+ // instruction. Calling getTerminatorEdges() on a non-terminator |
+ // instruction will cause an llvm_unreachable(). |
+ assert(((*InsertionPoint)->getTerminatorEdges(), true)); |
+ |
+ // Consider every out-edge. |
+ for (NodeList::const_iterator I1 = OutEdges.begin(), E1 = OutEdges.end(); |
+ I1 != E1; ++I1) { |
+ CfgNode *Target = *I1; |
+ // Consider every Phi instruction at the out-edge. |
+ for (PhiList::const_iterator I2 = Target->Phis.begin(), |
+ E2 = Target->Phis.end(); |
+ I2 != E2; ++I2) { |
+ Operand *Operand = (*I2)->getOperandForTarget(this); |
+ assert(Operand); |
+ Variable *Dest = (*I2)->getDest(); |
+ assert(Dest); |
+ InstAssign *NewInst = InstAssign::create(Func, Dest, Operand); |
+ // If Src is a variable, set the Src and Dest variables to |
+ // prefer each other for register allocation. |
+ if (Variable *Src = llvm::dyn_cast<Variable>(Operand)) { |
+ bool AllowOverlap = false; |
+ Dest->setPreferredRegister(Src, AllowOverlap); |
+ Src->setPreferredRegister(Dest, AllowOverlap); |
+ } |
+ Insts.insert(InsertionPoint, NewInst); |
+ NewInst->updateVars(this); |
+ } |
+ } |
+} |
+ |
+// Deletes the phi instructions after the loads and stores are placed. |
+void CfgNode::deletePhis() { |
+ for (PhiList::iterator I = Phis.begin(), E = Phis.end(); I != E; ++I) { |
+ (*I)->setDeleted(); |
+ } |
+} |
+ |
+// Drives the target lowering. Passes the current instruction and the |
+// next non-deleted instruction for target lowering. |
+void CfgNode::genCode() { |
+ TargetLowering *Target = Func->getTarget(); |
+ LoweringContext &Context = Target->getContext(); |
+ // Lower only the regular instructions. Defer the Phi instructions. |
+ Context.init(this); |
+ while (!Context.atEnd()) { |
+ InstList::iterator Orig = Context.getCur(); |
+ if (llvm::isa<InstRet>(*Orig)) |
+ setHasReturn(); |
+ Target->lower(); |
+ // Ensure target lowering actually moved the cursor. |
+ assert(Context.getCur() != Orig); |
+ } |
+} |
+ |
// ======================== Dump routines ======================== // |
+void CfgNode::emit(Cfg *Func) const { |
+ Func->setCurrentNode(this); |
+ Ostream &Str = Func->getContext()->getStrEmit(); |
+ if (Func->getEntryNode() == this) { |
+ Str << Func->getContext()->mangleName(Func->getFunctionName()) << ":\n"; |
+ } |
+ Str << getAsmName() << ":\n"; |
+ for (PhiList::const_iterator I = Phis.begin(), E = Phis.end(); I != E; ++I) { |
+ InstPhi *Inst = *I; |
+ if (Inst->isDeleted()) |
+ continue; |
+ // Emitting a Phi instruction should cause an error. |
+ Inst->emit(Func); |
+ } |
+ for (InstList::const_iterator I = Insts.begin(), E = Insts.end(); I != E; |
+ ++I) { |
+ Inst *Inst = *I; |
+ if (Inst->isDeleted()) |
+ continue; |
+ // Here we detect redundant assignments like "mov eax, eax" and |
+ // suppress them. |
+ if (Inst->isRedundantAssign()) |
+ continue; |
+ (*I)->emit(Func); |
+ } |
+} |
+ |
void CfgNode::dump(Cfg *Func) const { |
Func->setCurrentNode(this); |
Ostream &Str = Func->getContext()->getStrDump(); |