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.cpp

diff --git a/src/IceInst.cpp b/src/IceInst.cpp
index c9eb95e..70b54b6 100644
--- a/src/IceInst.cpp
+++ b/src/IceInst.cpp
@@ -135,12 +135,12 @@
   }
 }
 
-void Inst::liveness(InstNumberT InstNumber, LivenessBV &Live,
+bool Inst::liveness(InstNumberT InstNumber, LivenessBV &Live,
                     Liveness *Liveness, LiveBeginEndMap *LiveBegin,
                     LiveBeginEndMap *LiveEnd) {
   assert(!isDeleted());
   if (llvm::isa<InstFakeKill>(this))
-    return;
+    return true;
 
   Dead = false;
   if (Dest) {
@@ -158,7 +158,7 @@
     }
   }
   if (Dead)
-    return;
+    return false;
   // Phi arguments only get added to Live in the predecessor node, but
   // we still need to update LiveRangesEnded.
   bool IsPhi = llvm::isa<InstPhi>(this);
@@ -202,6 +202,7 @@
       }
     }
   }
+  return true;
 }
 
 InstAlloca::InstAlloca(Cfg *Func, Operand *ByteCount, uint32_t AlignInBytes,
@@ -261,6 +262,17 @@
   return OutEdges;
 }
 
+bool InstBr::repointEdge(CfgNode *OldNode, CfgNode *NewNode) {
+  if (TargetFalse == OldNode) {
+    TargetFalse = NewNode;
+    return true;
+  } else if (TargetTrue == OldNode) {
+    TargetTrue = NewNode;
+    return true;
+  }
+  return false;
+}
+
 InstCast::InstCast(Cfg *Func, OpKind CastKind, Variable *Dest, Operand *Source)
     : InstHighLevel(Func, Inst::Cast, 1, Dest), CastKind(CastKind) {
   addSource(Source);
@@ -410,6 +422,20 @@
   return OutEdges;
 }
 
+bool InstSwitch::repointEdge(CfgNode *OldNode, CfgNode *NewNode) {
+  if (LabelDefault == OldNode) {
+    LabelDefault = NewNode;
+    return true;
+  }
+  for (SizeT I = 0; I < NumCases; ++I) {
+    if (Labels[I] == OldNode) {
+      Labels[I] = NewNode;
+      return true;
+    }
+  }
+  return false;
+}
+
 InstUnreachable::InstUnreachable(Cfg *Func)
     : InstHighLevel(Func, Inst::Unreachable, 0, NULL) {}