[Beignet] [PATCH 2/3] add basic structure for selection IR optimization

[Guo Yejun]

The idea is that many optimzations can be done at selection IR level,
which is nearly ISA-like *before* physical register allocation. The
optimization here can help to reduce register use/spill.

It is hard to do the optimzation in late ASM stage since the ASM
instructions are encoded without structured information in current
implementation. It is also not good to move the optimization to early
stage, we'll lose much optimization opportunity in early stage.

The idea expects that selection IR is almost ISA-like, trying to avoid
optimization opportunity lose as far as possible. It means that we'd
better do as much as possible at selection IR stage, instead of ASM
generation stage. We can go in this direction in future development.

>From implementation perspective, since the class gbe::Selection is
already heavy, add new classes in new .cpp file to decouple them.

There are two levels of optimization, basic block level and global
level. The peephole optimization such as local copy propagation can
be done at basic block level, the dead code elimination can be done
at global level. We can introduce more optimizations here.

The optimization can be controlled by env variable OCL_OPTIMIZE_SEL_IR

Signed-off-by: Guo Yejun <yejun.guo at intel.com>
---
 backend/src/CMakeLists.txt                         |  1 +
 backend/src/backend/gen_context.cpp                |  3 +
 backend/src/backend/gen_insn_selection.cpp         |  1 +
 backend/src/backend/gen_insn_selection.hpp         |  5 ++
 .../src/backend/gen_insn_selection_optimize.cpp    | 67 ++++++++++++++++++++++
 5 files changed, 77 insertions(+)
 create mode 100644 backend/src/backend/gen_insn_selection_optimize.cpp

diff --git a/backend/src/CMakeLists.txt b/backend/src/CMakeLists.txt
index ef95910..f26cc8b 100644
--- a/backend/src/CMakeLists.txt
+++ b/backend/src/CMakeLists.txt
@@ -99,6 +99,7 @@ set (GBE_SRC
     backend/gen/gen_mesa_disasm.c
     backend/gen_insn_selection.cpp
     backend/gen_insn_selection.hpp
+    backend/gen_insn_selection_optimize.cpp
     backend/gen_insn_scheduling.cpp
     backend/gen_insn_scheduling.hpp
     backend/gen_insn_selection_output.cpp
diff --git a/backend/src/backend/gen_context.cpp b/backend/src/backend/gen_context.cpp
index 075307d..a71941f 100644
--- a/backend/src/backend/gen_context.cpp
+++ b/backend/src/backend/gen_context.cpp
@@ -2300,10 +2300,13 @@ namespace gbe
   }
 
   BVAR(OCL_OUTPUT_SEL_IR, false);
+  BVAR(OCL_OPTIMIZE_SEL_IR, true);
   bool GenContext::emitCode(void) {
     GenKernel *genKernel = static_cast<GenKernel*>(this->kernel);
     buildPatchList();
     sel->select();
+    if (OCL_OPTIMIZE_SEL_IR)
+      sel->optimize();
     if (OCL_OUTPUT_SEL_IR)
       outputSelectionIR(*this, this->sel);
     schedulePreRegAllocation(*this, *this->sel);
diff --git a/backend/src/backend/gen_insn_selection.cpp b/backend/src/backend/gen_insn_selection.cpp
index ab00269..ecd071e 100644
--- a/backend/src/backend/gen_insn_selection.cpp
+++ b/backend/src/backend/gen_insn_selection.cpp
@@ -2067,6 +2067,7 @@ namespace gbe
     this->blockList = NULL;
     this->opaque = GBE_NEW(Selection::Opaque, ctx);
     this->opaque->setSlowByteGather(true);
+    opt_features = 0;
   }
 
   Selection75::Selection75(GenContext &ctx) : Selection(ctx) {
diff --git a/backend/src/backend/gen_insn_selection.hpp b/backend/src/backend/gen_insn_selection.hpp
index ffc79e1..86542b0 100644
--- a/backend/src/backend/gen_insn_selection.hpp
+++ b/backend/src/backend/gen_insn_selection.hpp
@@ -266,6 +266,11 @@ namespace gbe
     class Opaque;
     /*! Created and destroyed in cpp */
     Opaque *opaque;
+
+    /* optimize at selection IR level */
+    void optimize(void);
+    uint32_t opt_features;
+
     /*! Use custom allocators */
     GBE_CLASS(Selection);
   };
diff --git a/backend/src/backend/gen_insn_selection_optimize.cpp b/backend/src/backend/gen_insn_selection_optimize.cpp
new file mode 100644
index 0000000..c82fbe5
--- /dev/null
+++ b/backend/src/backend/gen_insn_selection_optimize.cpp
@@ -0,0 +1,67 @@
+
+#include "backend/gen_insn_selection.hpp"
+#include "backend/gen_context.hpp"
+#include "ir/function.hpp"
+#include "ir/liveness.hpp"
+#include "ir/profile.hpp"
+#include "sys/cvar.hpp"
+#include "sys/vector.hpp"
+#include <algorithm>
+#include <climits>
+#include <map>
+
+namespace gbe
+{
+
+  class SelOptimizer
+  {
+  public:
+    SelOptimizer(uint32_t features) : features(features) {}
+    virtual void run() = 0;
+    virtual ~SelOptimizer() {}
+  protected:
+    uint32_t features;
+  };
+
+  class SelBasicBlockOptimizer : public SelOptimizer
+  {
+  public:
+    SelBasicBlockOptimizer(uint32_t features, SelectionBlock &bb) : SelOptimizer(features), bb(bb) {}
+    ~SelBasicBlockOptimizer() {}
+    virtual void run();
+
+  private:
+    SelectionBlock &bb;
+    static const size_t MaxTries = 1;   //the times for optimization
+  };
+
+  void SelBasicBlockOptimizer::run()
+  {
+
+  }
+
+  class SelGlobalOptimizer : public SelOptimizer
+  {
+  public:
+    SelGlobalOptimizer(uint32_t features) : SelOptimizer(features) {}
+    ~SelGlobalOptimizer() {}
+    virtual void run();
+  };
+
+  void SelGlobalOptimizer::run()
+  {
+
+  }
+
+  void Selection::optimize()
+  {
+    //do basic block level optimization
+    for (SelectionBlock &block : *blockList) {
+      SelBasicBlockOptimizer bbopt(opt_features, block);
+      bbopt.run();
+    }
+
+    //do global optimization
+
+  }
+} /* namespace gbe */
-- 
1.9.1