[Beignet] [PATCH] GBE: Optimize extraLiveOut register info.

Ruiling Song ruiling.song at intel.com
Thu Jun 2 02:21:14 UTC 2016


extraLiveout anlysis is used to detect registers defined in loop and
used out-of the loop. Previous logic may also include registers defined
BEFORE loop and live-through loop as extraLiveout, which is not accurate.
As the extraLiveout registers will be forced as non-uniform, which may
waste some register space. Excluding registers that are defined before loop
while used out-of loop will make such registers get correct uniform/non-uniform
information. This would benefit some gemm cl kernel.

also fix a small issue: do intersection when the exit-block has more
than one predecessors.

Signed-off-by: Ruiling Song <ruiling.song at intel.com>
---
 backend/src/ir/function.cpp           |  4 ++--
 backend/src/ir/function.hpp           |  7 ++++---
 backend/src/ir/liveness.cpp           | 25 +++++++++++++++++++++---
 backend/src/llvm/llvm_gen_backend.cpp | 36 ++++++-----------------------------
 4 files changed, 34 insertions(+), 38 deletions(-)

diff --git a/backend/src/ir/function.cpp b/backend/src/ir/function.cpp
index 3b7891b..4112f06 100644
--- a/backend/src/ir/function.cpp
+++ b/backend/src/ir/function.cpp
@@ -62,8 +62,8 @@ namespace ir {
     return unit.getPointerFamily();
   }
 
-  void Function::addLoop(const vector<LabelIndex> &bbs, const vector<std::pair<LabelIndex, LabelIndex>> &exits) {
-    loops.push_back(GBE_NEW(Loop, bbs, exits));
+  void Function::addLoop(LabelIndex preheader, const vector<LabelIndex> &bbs, const vector<std::pair<LabelIndex, LabelIndex>> &exits) {
+    loops.push_back(GBE_NEW(Loop, preheader, bbs, exits));
   }
 
   void Function::checkEmptyLabels(void) {
diff --git a/backend/src/ir/function.hpp b/backend/src/ir/function.hpp
index 5785bee..6a90767 100644
--- a/backend/src/ir/function.hpp
+++ b/backend/src/ir/function.hpp
@@ -273,8 +273,9 @@ namespace ir {
   struct Loop : public NonCopyable
   {
   public:
-    Loop(const vector<LabelIndex> &in, const vector<std::pair<LabelIndex, LabelIndex>> &exit) :
-    bbs(in), exits(exit) {}
+    Loop(LabelIndex pre, const vector<LabelIndex> &in, const vector<std::pair<LabelIndex, LabelIndex>> &exit) :
+    preheader(pre), bbs(in), exits(exit) {}
+    LabelIndex preheader;
     vector<LabelIndex> bbs;
     vector<std::pair<LabelIndex, LabelIndex>> exits;
     GBE_STRUCT(Loop);
@@ -522,7 +523,7 @@ namespace ir {
     /*! Push stack size. */
     INLINE void pushStackSize(uint32_t step) { this->stackSize += step; }
     /*! add the loop info for later liveness analysis */
-    void addLoop(const vector<LabelIndex> &bbs, const vector<std::pair<LabelIndex, LabelIndex>> &exits);
+    void addLoop(LabelIndex preheader, const vector<LabelIndex> &bbs, const vector<std::pair<LabelIndex, LabelIndex>> &exits);
     INLINE const vector<Loop * > &getLoops() { return loops; }
     vector<BasicBlock *> &getBlocks() { return blocks; }
     /*! Get surface starting address register from bti */
diff --git a/backend/src/ir/liveness.cpp b/backend/src/ir/liveness.cpp
index d48f067..4a89a73 100644
--- a/backend/src/ir/liveness.cpp
+++ b/backend/src/ir/liveness.cpp
@@ -217,19 +217,38 @@ namespace ir {
     if(loops.size() == 0) return;
 
     for (auto l : loops) {
+      const BasicBlock &preheader = fn.getBlock(l->preheader);
+      BlockInfo *preheaderInfo = liveness[&preheader];
       for (auto x : l->exits) {
         const BasicBlock &a = fn.getBlock(x.first);
         const BasicBlock &b = fn.getBlock(x.second);
         BlockInfo * exiting = liveness[&a];
         BlockInfo * exit = liveness[&b];
         std::vector<Register> toExtend;
+        std::vector<Register> toExtendCand;
 
-        if(b.getPredecessorSet().size() > 1) {
+        if(b.getPredecessorSet().size() <= 1) {
+          // the exits only have one predecessor
           for (auto p : exit->upwardUsed)
-            toExtend.push_back(p);
+            toExtendCand.push_back(p);
         } else {
-          std::set_intersection(exiting->liveOut.begin(), exiting->liveOut.end(), exit->upwardUsed.begin(), exit->upwardUsed.end(), std::back_inserter(toExtend));
+          // the exits have more than one predecessors
+          std::set_intersection(exiting->liveOut.begin(),
+                                exiting->liveOut.end(),
+                                exit->upwardUsed.begin(),
+                                exit->upwardUsed.end(),
+                                std::back_inserter(toExtendCand));
         }
+        // toExtendCand may contain some virtual register defined before loop,
+        // which need to be excluded. Because what we need is registers defined
+        // in the loop. Such kind of registers must be in live-out of the loop's
+        // preheader. So we do the subtraction here.
+        std::set_difference(toExtendCand.begin(),
+                            toExtendCand.end(),
+                            preheaderInfo->liveOut.begin(),
+                            preheaderInfo->liveOut.end(),
+                            std::back_inserter(toExtend));
+
         if (toExtend.size() == 0) continue;
         for(auto r : toExtend)
           extentRegs.insert(r);
diff --git a/backend/src/llvm/llvm_gen_backend.cpp b/backend/src/llvm/llvm_gen_backend.cpp
index acad1b2..0b44f24 100644
--- a/backend/src/llvm/llvm_gen_backend.cpp
+++ b/backend/src/llvm/llvm_gen_backend.cpp
@@ -2737,35 +2737,6 @@ namespace gbe
     std::vector<std::pair<Loop*, int>> lp;
 
     findAllLoops(LI, lp);
-#if GBE_DEBUG
-    // check two loops' interference
-    for(unsigned int i = 0; i < lp.size(); i++) {
-        SmallVector<Loop::Edge, 8> exitBBs;
-        lp[i].first->getExitEdges(exitBBs);
-
-      const std::vector<BasicBlock*> &inBBs = lp[i].first->getBlocks();
-      std::vector<ir::LabelIndex> bbs1;
-      for(auto x : inBBs) {
-        bbs1.push_back(labelMap[x]);
-      }
-      std::sort(bbs1.begin(), bbs1.end());
-      for(unsigned int j = i+1; j < lp.size(); j++) {
-        if(! lp[i].first->contains(lp[j].first)) {
-          const std::vector<BasicBlock*> &inBBs2 = lp[j].first->getBlocks();
-          std::vector<ir::LabelIndex> bbs2;
-          std::vector<ir::LabelIndex> bbs3;
-
-          for(auto x : inBBs2) {
-            bbs2.push_back(labelMap[x]);
-          }
-
-          std::sort(bbs2.begin(), bbs2.end());
-          std::set_intersection(bbs1.begin(), bbs1.end(), bbs2.begin(), bbs2.end(), std::back_inserter(bbs3));
-          GBE_ASSERT(bbs3.size() < 1);
-        }
-      }
-    }
-#endif
 
     for (auto loop : lp) {
       loopBBs.clear();
@@ -2776,6 +2747,11 @@ namespace gbe
         GBE_ASSERT(labelMap.find(b) != labelMap.end());
         loopBBs.push_back(labelMap[b]);
       }
+      BasicBlock *preheader = loop.first->getLoopPreheader();
+      ir::LabelIndex preheaderBB(0);
+      if (preheader) {
+        preheaderBB = labelMap[preheader];
+      }
 
       SmallVector<Loop::Edge, 8> exitBBs;
       loop.first->getExitEdges(exitBBs);
@@ -2784,7 +2760,7 @@ namespace gbe
         GBE_ASSERT(labelMap.find(b.second) != labelMap.end());
         loopExits.push_back(std::make_pair(labelMap[b.first], labelMap[b.second]));
       }
-      fn.addLoop(loopBBs, loopExits);
+      fn.addLoop(preheaderBB, loopBBs, loopExits);
     }
   }
 
-- 
2.4.1



More information about the Beignet mailing list