From 61c6320b756f9d63ddc3a035634b14b25f5c5512 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=BCrgen=20R=C3=BChle?= <j-r@online.de>
Date: Sun, 12 Jul 2015 20:18:16 +0200
Subject: [PATCH] Prototype of a more highlevel graph modification api

---
 src/gallium/drivers/nouveau/codegen/nv50_ir.h      |  2 ++
 src/gallium/drivers/nouveau/codegen/nv50_ir_bb.cpp | 25 +++++++++++++++++++
 .../drivers/nouveau/codegen/nv50_ir_graph.cpp      | 29 ++++++++++++++++++++++
 .../drivers/nouveau/codegen/nv50_ir_graph.h        |  2 ++
 src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp | 29 +++++-----------------
 5 files changed, 64 insertions(+), 23 deletions(-)

diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir.h b/src/gallium/drivers/nouveau/codegen/nv50_ir.h
index 529dcb9..5311cb9 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir.h
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir.h
@@ -1216,6 +1216,8 @@ protected:
    bool err;
    Function *func;
    Program *prog;
+
+   BasicBlock *splitEdge(Graph::Edge *);
 };
 
 // =============================================================================
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_bb.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_bb.cpp
index fa8ee07..6033068 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_bb.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_bb.cpp
@@ -505,6 +505,31 @@ Pass::doRun(Function *func, bool ordered, bool skipPhi)
    return !err;
 }
 
+BasicBlock *
+Pass::splitEdge(Graph::Edge *e)
+{
+   BasicBlock *src = BasicBlock::get(e->getOrigin());
+   BasicBlock *trg = BasicBlock::get(e->getTarget());
+
+   BasicBlock *pn = new BasicBlock(func);
+
+   // add new edge from edge source to new bb
+   // Note: this will modify the outgoing edges of the edge's source
+   // TODO: check whether TREE is always correct; shouldn't it rather copy the edge's type?
+   src->cfg.attach(&pn->cfg, Graph::Edge::TREE /*e->getType()*/);
+
+   // modify the source's exit if necessary
+   assert(src->getExit()->op != OP_CALL);
+   if (src->getExit()->asFlow()->target.bb == trg)
+      src->getExit()->asFlow()->target.bb = pn;
+
+   // reuse the split edge as the outgoing edge of the new block in order
+   // to preserve the targets incident edge order
+   e->moveOrigin(&pn->cfg, Graph::Edge::FORWARD);
+
+   return pn;
+}
+
 void
 Function::printCFGraph(const char *filePath)
 {
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.cpp
index 23414d5..21cb4d9 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_graph.cpp
@@ -50,6 +50,35 @@ void Graph::insert(Node *node)
    size++;
 }
 
+void Graph::Edge::moveOrigin(Node *src, Type kind)
+{
+   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;
+
+   type = kind;
+}
+
 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..83dfc7b 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, Type newKind);
+
    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 898653c..e7da5d3 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
@@ -358,34 +358,17 @@ bool
 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;
-   }
+   BasicBlock *pb;
 
    // 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)) {
+         pb = splitEdge(ei.getEdge());
+      }
+ 
       if (!pb->isTerminated())
          pb->insertTail(new_FlowInstruction(func, OP_BRA, bb));
 
-- 
2.1.4