From b8ba33bd49c6b73f5686793cd461fc7f57756a53 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=BCrgen=20R=C3=BChle?= <j-r@online.de>
Date: Sun, 7 Jun 2015 18:21:09 +0200
Subject: [PATCH 2/2] nv50: fix edge reordering breakage in PhiMovesPass

The nv50 SSA representation depends on a strict correspondence between
order of phi node parameters and basic block inbound edges.

One (the only?) place where this is relevant is the PhiMovesPass that
creates additional moves for phi parameters at the end of the
corresponding flow branch. In some circumstances it splits the incoming
edge to create a new basic block to hold the moves.

Currently this logic destroys the ordering of inbound edges on which
the code 10 lines below depends:-)

This commit tries to minimize side effects caused by edge splitting,
especially keeping the order of inbound edges intact. This allows
to eliminate the extra loops. A more correct fix is probably to
remove the dependency of edge ordering.

Note that I neither have a clue of C++ nor of Mesa, but this fixes
post processing shaders used by several games (Costume Quest,
Eidolon, Lifeless Planet) running in WINE on NVA5 for me. Actually
this is the last significant problem (besides performance) I see on
NVA5.
---
 .../drivers/nouveau/codegen/nv50_ir_graph.cpp      | 27 ++++++++++++++++
 .../drivers/nouveau/codegen/nv50_ir_graph.h        |  2 ++
 src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp | 37 +++++++++-------------
 3 files changed, 44 insertions(+), 22 deletions(-)

diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.cpp
index 23414d5..9536a39 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.cpp
@@ -50,6 +50,33 @@ void Graph::insert(Node *node)
    size++;
 }
 
+void Graph::Edge::moveOrigin(Node *src)
+{
+   assert(src);
+
+   if (origin) {
+      prev[0]->next[0] = next[0];
+      next[0]->prev[0] = prev[0];
+      if (origin->out == this)
+         origin->out = (next[0] == this) ? NULL : next[0];
+
+      --origin->outCount;
+   }
+
+   origin = src;
+   if (origin->out) {
+      next[0] = origin->out;
+      prev[0] = origin->out->prev[0];
+      prev[0]->next[0] = this;
+      next[0]->prev[0] = this;
+   } else {
+      next[0] = this;
+      prev[0] = this;
+   }
+   origin->out = this;
+   ++origin->outCount;
+}
+
 void Graph::Edge::unlink()
 {
    if (origin) {
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.h b/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.h
index b0981ff..84b5576 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.h
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.h
@@ -59,6 +59,8 @@ public:
       inline Type getType() const { return type; }
       const char *typeStr() const;
 
+      void moveOrigin(Node *src);
+
    private:
       Node *origin;
       Node *target;
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
index 83d2282..073b42c 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
@@ -360,32 +360,25 @@ RegAlloc::PhiMovesPass::visit(BasicBlock *bb)
    Instruction *phi, *mov;
    BasicBlock *pb, *pn;
 
-   std::stack<BasicBlock *> stack;
-
-   for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) {
-      pb = BasicBlock::get(ei.getNode());
-      assert(pb);
-      if (needNewElseBlock(bb, pb))
-         stack.push(pb);
-   }
-   while (!stack.empty()) {
-      pb = stack.top();
-      pn = new BasicBlock(func);
-      stack.pop();
-
-      pb->cfg.detach(&bb->cfg);
-      pb->cfg.attach(&pn->cfg, Graph::Edge::TREE);
-      pn->cfg.attach(&bb->cfg, Graph::Edge::FORWARD);
-
-      assert(pb->getExit()->op != OP_CALL);
-      if (pb->getExit()->asFlow()->target.bb == bb)
-         pb->getExit()->asFlow()->target.bb = pn;
-   }
-
    // insert MOVs (phi->src(j) should stem from j-th in-BB)
    int j = 0;
    for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) {
       pb = BasicBlock::get(ei.getNode());
+      assert(pb);
+      if (needNewElseBlock(bb, pb)) {
+         pn = new BasicBlock(func);
+
+         // !!The ordering of bb's incident edges must not change!!
+         ei.getEdge()->moveOrigin(&pn->cfg);
+         pb->cfg.attach(&pn->cfg, Graph::Edge::TREE);
+
+         assert(pb->getExit()->op != OP_CALL);
+         if (pb->getExit()->asFlow()->target.bb == bb)
+            pb->getExit()->asFlow()->target.bb = pn;
+
+         pb = pn;
+      }
+ 
       if (!pb->isTerminated())
          pb->insertTail(new_FlowInstruction(func, OP_BRA, bb));
 
-- 
2.1.4