Add Om1 lowering with no optimizations.
This adds infrastructure for low-level x86-32 instructions, and the target lowering patterns.
Practically no optimizations are performed. Optimizations to be introduced later include liveness analysis, dead-code elimination, global linear-scan register allocation, linear-scan based stack slot coalescing, and compare/branch fusing. One optimization that is present is simple coalescing of stack slots for variables that are only live within a single basic block.
There are also some fairly comprehensive cross tests. This testing infrastructure translates bitcode using both Subzero and llc, and a testing harness calls both versions with a variety of "interesting" inputs and compares the results. Specifically, Arithmetic, Icmp, Fcmp, and Cast instructions are tested this way, across all PNaCl primitive types.
BUG=
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/265703002
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index fe8b70e0..c00b2c7 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 @@
}
}
+// 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();
