commit 336f6c4a90e7f5ee156bc9a339d80c7def5ddeff
author Jim Stichnoth <stichnot@chromium.org> Thu Oct 30 15:01:31 2014 -0700
committer Jim Stichnoth <stichnot@chromium.org> Thu Oct 30 15:01:31 2014 -0700
tree b2154b8e9808e4772069cad5b2964631e32c3cf5
parent 0506fc7299b3eed6d714e74f3f75d9dc6f888dcc

Subzero: Implementation of "advanced Phi lowering".

Delays Phi lowering until after register allocation.  This lets the Phi assignment order take register allocation into account and avoid creating false dependencies.

All edges that lead to Phi instructions are split, and the new node gets mov instructions in the correct topological order, using available physical registers as needed.

This lowering style is controllable under -O2 using -phi-edge-split (enabled by default).

The result is faster translation time (due to fewer temporaries leading to faster liveness analysis and register allocation) as well as better code quality (due to better register allocation and fewer phi-based assignments).

BUG= none
R=jvoung@chromium.org

Review URL: https://codereview.chromium.org/680733002

src/IceInst.h

diff --git a/src/IceInst.h b/src/IceInst.h
index 0a47e1a..e6edb4c 100644
--- a/src/IceInst.h
+++ b/src/IceInst.h
@@ -100,11 +100,27 @@
         "getTerminatorEdges() called on a non-terminator instruction");
     return NodeList();
   }
+  virtual bool isUnconditionalBranch() const { return false; }
+  // If the instruction is a branch-type instruction with OldNode as a
+  // target, repoint it to NewNode and return true, otherwise return
+  // false.  Only repoint one instance, even if the instruction has
+  // multiple instances of OldNode as a target.
+  virtual bool repointEdge(CfgNode *OldNode, CfgNode *NewNode) {
+    (void)OldNode;
+    (void)NewNode;
+    return false;
+  }
 
   virtual bool isSimpleAssign() const { return false; }
 
   void livenessLightweight(Cfg *Func, LivenessBV &Live);
-  void liveness(InstNumberT InstNumber, LivenessBV &Live, Liveness *Liveness,
+  // Calculates liveness for this instruction.  Returns true if this
+  // instruction is (tentatively) still live and should be retained,
+  // and false if this instruction is (tentatively) dead and should be
+  // deleted.  The decision is tentative until the liveness dataflow
+  // algorithm has converged, and then a separate pass permanently
+  // deletes dead instructions.
+  bool liveness(InstNumberT InstNumber, LivenessBV &Live, Liveness *Liveness,
                 LiveBeginEndMap *LiveBegin, LiveBeginEndMap *LiveEnd);
 
   // Get the number of native instructions that this instruction
@@ -304,6 +320,8 @@
     return getTargetFalse();
   }
   NodeList getTerminatorEdges() const override;
+  bool isUnconditionalBranch() const override { return isUnconditional(); }
+  bool repointEdge(CfgNode *OldNode, CfgNode *NewNode) override;
   void dump(const Cfg *Func) const override;
   static bool classof(const Inst *Inst) { return Inst->getKind() == Br; }
 
@@ -314,8 +332,8 @@
   InstBr(Cfg *Func, CfgNode *Target);
   ~InstBr() override {}
 
-  CfgNode *const TargetFalse; // Doubles as unconditional branch target
-  CfgNode *const TargetTrue;  // NULL if unconditional branch
+  CfgNode *TargetFalse; // Doubles as unconditional branch target
+  CfgNode *TargetTrue;  // NULL if unconditional branch
 };
 
 // Call instruction.  The call target is captured as getSrc(0), and
@@ -671,6 +689,7 @@
   }
   void addBranch(SizeT CaseIndex, uint64_t Value, CfgNode *Label);
   NodeList getTerminatorEdges() const override;
+  bool repointEdge(CfgNode *OldNode, CfgNode *NewNode) override;
   void dump(const Cfg *Func) const override;
   static bool classof(const Inst *Inst) { return Inst->getKind() == Switch; }