Add Om1 lowering with no optimizations

src/IceCfgNode.cpp

 //===- subzero/src/IceCfgNode.cpp - Basic block (node) implementation -----===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// 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.
 //
 //===----------------------------------------------------------------------===//
 
 #include "IceCfg.h"
 #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.
 IceString CfgNode::getName() const {
   if (!Name.empty())
     return Name;
   char buf[30];
   snprintf(buf, llvm::array_lengthof(buf), "__%u", getIndex());
   return buf;
 }
@@ skipping 20 matching lines @@
 // creating the InEdges list.
 void CfgNode::computePredecessors() {
   OutEdges = (*Insts.rbegin())->getTerminatorEdges();
   for (NodeList::const_iterator I = OutEdges.begin(), E = OutEdges.end();
        I != E; ++I) {
     CfgNode *Node = *I;
     Node->InEdges.push_back(this);
   }
 }
 
+// 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();
   if (Func->getContext()->isVerbose(IceV_Instructions)) {
     Str << getName() << ":\n";
   }
   // Dump list of predecessor nodes.
   if (Func->getContext()->isVerbose(IceV_Preds) && !InEdges.empty()) {
     Str << "    // preds = ";
     for (NodeList::const_iterator I = InEdges.begin(), E = InEdges.end();
@@ skipping 24 matching lines @@
          I != E; ++I) {
       if (I != OutEdges.begin())
         Str << ", ";
       Str << "%" << (*I)->getName();
     }
     Str << "\n";
   }
 }
 
 } // end of namespace Ice