[Beignet] [PATCH 4/4] GBE: One simple redundant instruction elimination.

[Zhigang Gong]

For some reason, after register allocation, we may translate
the following instruction series:

ADD %8, %7, 4
MOV %99, 0
MOV %10, %5
SAMPLE %8,%99,%10  %12,%13,%14,%15

ADD %8, %7, 8
MOV %100, 0
MOV %10, %5
SAMPLE %8,%100,%10  %16,%17,%18,%19
......

to:

add $8, $7, 4
mov $9, 0
mov $10, $5
send $8, $12

add $8, $7, 8
mov $9, 0
mov $10, $5
send $8, $16
...

You can see that the second mov $9, 0 is a redundant instruction
which could be removed.

This patch is to analyze this type case and remove all the subsequent
redundant movs.

Signed-off-by: Zhigang Gong <zhigang.gong at intel.com>
---
 backend/src/backend/gen_insn_scheduling.cpp | 46 +++++++++++++++++++++++++++++
 1 file changed, 46 insertions(+)

diff --git a/backend/src/backend/gen_insn_scheduling.cpp b/backend/src/backend/gen_insn_scheduling.cpp
index 58ab69f..76a9ce5 100644
--- a/backend/src/backend/gen_insn_scheduling.cpp
+++ b/backend/src/backend/gen_insn_scheduling.cpp
@@ -166,6 +166,8 @@ namespace gbe
     void addDependency(ScheduleDAGNode *node0, uint32_t index, DepMode m);
     /*! Add a new dependency "node located at index depends on node0" */
     void addDependency(uint32_t index, ScheduleDAGNode *node0, DepMode m);
+    /*! Check whether an instruction is redundant. */
+    bool isRedundant(ScheduleDAGNode *node0);
     /*! No dependency for null registers and immediate */
     INLINE bool ignoreDependency(GenRegister reg) const {
       if (reg.file == GEN_IMMEDIATE_VALUE)
@@ -466,6 +468,48 @@ namespace gbe
     }
   }
 
+  bool DependencyTracker::isRedundant(ScheduleDAGNode *node0) {
+    if (scheduler.policy != POST_ALLOC)
+      return false;
+    if (node0->insn.opcode != SEL_OP_MOV ||
+        node0->insn.src(0).file != GEN_IMMEDIATE_VALUE)
+      return false;
+    if  (node0->insn.state.predicate != GEN_PREDICATE_NONE)
+      return false;
+
+    const uint32_t index = this->getIndex(node0->insn.dst(0));
+    ScheduleDAGNode *node1 = nodes[index];
+    if (node1 == NULL)
+      return false;
+
+    const GenRegister physical0 = scheduler.ctx.ra->genReg(node0->insn.dst(0));
+    const GenRegister physical1 = scheduler.ctx.ra->genReg(node1->insn.dst(0));
+    if (physical0.nr != physical1.nr || physical0.subnr != physical1.subnr ||
+        node0->insn.state.predicate != node1->insn.state.predicate ||
+        node0->insn.state.noMask != node1->insn.state.noMask)
+      return false;
+
+    if (node1->insn.opcode == node0->insn.opcode &&
+        node1->insn.src(0).file == node0->insn.src(0).file &&
+        node1->insn.src(0).type == node0->insn.src(0).type) {
+
+        if ((node0->insn.src(0).type == GEN_TYPE_DF ||
+             node0->insn.src(0).type == GEN_TYPE_L) &&
+             node0->insn.src(0).value.i64 == node1->insn.src(0).value.i64)
+          return true;
+        if ((node0->insn.src(0).type == GEN_TYPE_UD ||
+             node0->insn.src(0).type == GEN_TYPE_D ||
+             node0->insn.src(0).type == GEN_TYPE_UW ||
+             node0->insn.src(0).type == GEN_TYPE_W ||
+             node0->insn.src(0).type == GEN_TYPE_UB ||
+             node0->insn.src(0).type == GEN_TYPE_B ||
+             node0->insn.src(0).type == GEN_TYPE_F) &&
+             node0->insn.src(0).value.ud == node1->insn.src(0).value.ud)
+          return true;
+    }
+    return false;
+  }
+
   int32_t SelectionScheduler::buildDAG(SelectionBlock &bb) {
     nodePool.rewind();
     listPool.rewind();
@@ -477,6 +521,8 @@ namespace gbe
     for (auto &insn : bb.insnList) {
       // Create a new node for this instruction
       ScheduleDAGNode *node = this->newScheduleDAGNode(insn);
+      if (tracker.isRedundant(node))
+        continue;
       tracker.insnNodes[insnNum++] = node;
 
       // read-after-write in registers
-- 
1.8.3.2