[V2] GBE: optimize phi elimination.

Submitted by Song, Ruiling on July 6, 2015, 6:39 a.m.

Details

Message ID 1436164797-5238-1-git-send-email-ruiling.song@intel.com
State New
Headers show

Not browsing as part of any series.

Commit Message

Song, Ruiling July 6, 2015, 6:39 a.m.
This is special optimization for below situation:

bb1:
    ...
bb2:
    x = phi [x1, bb1], [x2, bb2]
    x2 = x+1;
after de-ssa:
bb2:
    mov x, x-copy
    add x2, x, 1
    mov x-copy, x2
obviously x2, x-copy and x2 can be mapped to same virtual register.

v2:
only coaleasce if the source register comes from insn def.
add check "if (phiDef->empty()) continue;" to skip no-def phiDef.

Signed-off-by: Ruiling Song <ruiling.song@intel.com>
---
 backend/src/llvm/llvm_gen_backend.cpp | 70 ++++++++++++++++++++++++++++++++++-
 1 file changed, 68 insertions(+), 2 deletions(-)

Patch hide | download patch | download mbox

diff --git a/backend/src/llvm/llvm_gen_backend.cpp b/backend/src/llvm/llvm_gen_backend.cpp
index 37c9e7b..0ec113d 100644
--- a/backend/src/llvm/llvm_gen_backend.cpp
+++ b/backend/src/llvm/llvm_gen_backend.cpp
@@ -2156,6 +2156,9 @@  namespace gbe
     // between phi and phiCopy live range. If there is no point that
     // phi & phiCopy are both alive, then we can optimize off the move
     // from phiCopy to phi, and use phiCopy directly instead of phi.
+    // right now, the algorithm is still very conservative, we need to do
+    // aggressive coaleasing for the moves added during phi elimination.
+
     using namespace ir;
     ir::FunctionDAG *dag = new ir::FunctionDAG(liveness);
 
@@ -2167,6 +2170,13 @@  namespace gbe
       const ir::UseSet *phiUse = dag->getRegUse(phi);
       const DefSet *phiDef = dag->getRegDef(phi);
       bool isOpt = true;
+
+      // FIXME, I find under some situation, the phiDef maybe null, seems a bug when building FunctionDAg.
+      // need fix it there.
+      if (phiDef->empty()) continue;
+
+      const ir::BasicBlock *phiDefBB = (*phiDef->begin())->getInstruction()->getParent();
+
       for (auto &x : *phiCopyDef) {
         const ir::Instruction * phiCopyDefInsn = x->getInstruction();
         const ir::BasicBlock *bb = phiCopyDefInsn->getParent();
@@ -2177,6 +2187,63 @@  namespace gbe
           isOpt = false;
           break;
         }
+
+        const ir::Register phiCopySrc = phiCopyDefInsn->getSrc(0);
+        const ir::UseSet *phiCopySrcUse = dag->getRegUse(phiCopySrc);
+        const ir::DefSet *phiCopySrcDef = dag->getRegDef(phiCopySrc);
+        // non-ssa value. skip opt on such kind of value
+        if (phiCopySrcDef->size() > 1) break;
+        // we can only coalesce instruction dest
+        if ((*(phiCopySrcDef->begin()))->getType() != ValueDef::DEF_INSN_DST) break;
+
+        const ir::Instruction *phiCopySrcDefInsn = (*(phiCopySrcDef->begin()))->getInstruction();
+        if(bb == phiDefBB && bb == phiCopySrcDefInsn->getParent()) {
+          // phiCopy, phiCopySrc defined in same basicblock as phi
+          // try to coalease phiCopy and phiCopySrc first.
+          // consider below situation:
+          // bb1:
+          //    ...
+          // bb2:
+          //    x = phi [x1, bb1], [x2, bb2]
+          //    x2 = x+1;
+          // after de-ssa:
+          // bb2:
+          //    mov x, x-copy
+          //    add x2, x, 1
+          //    mov x-copy, x2
+          //  obviously x2, x-copy and x2 can be mapped to same virtual register
+
+          ir::BasicBlock::const_iterator iter = ir::BasicBlock::const_iterator(phiCopySrcDefInsn);
+          ir::BasicBlock::const_iterator iterE = bb->end();
+          // check no use of phi in this basicblock between [phiCopySrc def, bb end]
+          bool phiPhiCopySrcInterfere = false;
+          while (iter != iterE) {
+            const ir::Instruction *insn = iter.node();
+            // check phiUse
+            for (unsigned i = 0; i < insn->getSrcNum(); i++) {
+              ir::Register src = insn->getSrc(i);
+              if (src == phi) {
+                phiPhiCopySrcInterfere = true; break;
+              }
+            }
+            ++iter;
+          }
+          if (!phiPhiCopySrcInterfere) {
+            // phiCopy source can be coaleased with phiCopy
+            const_cast<Instruction *>(phiCopyDefInsn)->remove();
+
+            for (auto &s : *phiCopySrcDef) {
+              const Instruction *phiSrcDefInsn = s->getInstruction();
+              replaceDst(const_cast<Instruction *>(phiSrcDefInsn), phiCopySrc, phiCopy);
+            }
+
+            for (auto &s : *phiCopySrcUse) {
+              const Instruction *phiSrcUseInsn = s->getInstruction();
+              replaceSrc(const_cast<Instruction *>(phiSrcUseInsn), phiCopySrc, phiCopy);
+            }
+          }
+        }
+
         // If phi is used in the same BB that define the phiCopy,
         // we need carefully check the liveness of phi & phiCopy.
         // Make sure their live ranges do not interfere.
@@ -2206,8 +2273,7 @@  namespace gbe
         }
       }
 
-      // [MOV phi, phiCopy;] can be removed. So we remove it
-      // and replace phi uses with phiCopy
+      // coalease phi and phiCopy 
       if (isOpt) {
         for (auto &x : *phiDef) {
           const_cast<Instruction *>(x->getInstruction())->remove();

Comments

LGTM, will push it later, thanks.

> -----Original Message-----

> From: Beignet [mailto:beignet-bounces@lists.freedesktop.org] On Behalf Of

> Ruiling Song

> Sent: Monday, July 6, 2015 14:40

> To: beignet@lists.freedesktop.org

> Cc: Song, Ruiling

> Subject: [Beignet] [PATCH V2] GBE: optimize phi elimination.

> 

> This is special optimization for below situation:

> 

> bb1:

>     ...

> bb2:

>     x = phi [x1, bb1], [x2, bb2]

>     x2 = x+1;

> after de-ssa:

> bb2:

>     mov x, x-copy

>     add x2, x, 1

>     mov x-copy, x2

> obviously x2, x-copy and x2 can be mapped to same virtual register.

> 

> v2:

> only coaleasce if the source register comes from insn def.

> add check "if (phiDef->empty()) continue;" to skip no-def phiDef.

> 

> Signed-off-by: Ruiling Song <ruiling.song@intel.com>

> ---

>  backend/src/llvm/llvm_gen_backend.cpp | 70

> ++++++++++++++++++++++++++++++++++-

>  1 file changed, 68 insertions(+), 2 deletions(-)

> 

> diff --git a/backend/src/llvm/llvm_gen_backend.cpp

> b/backend/src/llvm/llvm_gen_backend.cpp

> index 37c9e7b..0ec113d 100644

> --- a/backend/src/llvm/llvm_gen_backend.cpp

> +++ b/backend/src/llvm/llvm_gen_backend.cpp

> @@ -2156,6 +2156,9 @@ namespace gbe

>      // between phi and phiCopy live range. If there is no point that

>      // phi & phiCopy are both alive, then we can optimize off the move

>      // from phiCopy to phi, and use phiCopy directly instead of phi.

> +    // right now, the algorithm is still very conservative, we need to do

> +    // aggressive coaleasing for the moves added during phi elimination.

> +

>      using namespace ir;

>      ir::FunctionDAG *dag = new ir::FunctionDAG(liveness);

> 

> @@ -2167,6 +2170,13 @@ namespace gbe

>        const ir::UseSet *phiUse = dag->getRegUse(phi);

>        const DefSet *phiDef = dag->getRegDef(phi);

>        bool isOpt = true;

> +

> +      // FIXME, I find under some situation, the phiDef maybe null, seems a

> bug when building FunctionDAg.

> +      // need fix it there.

> +      if (phiDef->empty()) continue;

> +

> +      const ir::BasicBlock *phiDefBB =

> + (*phiDef->begin())->getInstruction()->getParent();

> +

>        for (auto &x : *phiCopyDef) {

>          const ir::Instruction * phiCopyDefInsn = x->getInstruction();

>          const ir::BasicBlock *bb = phiCopyDefInsn->getParent(); @@ -2177,6

> +2187,63 @@ namespace gbe

>            isOpt = false;

>            break;

>          }

> +

> +        const ir::Register phiCopySrc = phiCopyDefInsn->getSrc(0);

> +        const ir::UseSet *phiCopySrcUse = dag->getRegUse(phiCopySrc);

> +        const ir::DefSet *phiCopySrcDef = dag->getRegDef(phiCopySrc);

> +        // non-ssa value. skip opt on such kind of value

> +        if (phiCopySrcDef->size() > 1) break;

> +        // we can only coalesce instruction dest

> +        if ((*(phiCopySrcDef->begin()))->getType() !=

> + ValueDef::DEF_INSN_DST) break;

> +

> +        const ir::Instruction *phiCopySrcDefInsn = (*(phiCopySrcDef-

> >begin()))->getInstruction();

> +        if(bb == phiDefBB && bb == phiCopySrcDefInsn->getParent()) {

> +          // phiCopy, phiCopySrc defined in same basicblock as phi

> +          // try to coalease phiCopy and phiCopySrc first.

> +          // consider below situation:

> +          // bb1:

> +          //    ...

> +          // bb2:

> +          //    x = phi [x1, bb1], [x2, bb2]

> +          //    x2 = x+1;

> +          // after de-ssa:

> +          // bb2:

> +          //    mov x, x-copy

> +          //    add x2, x, 1

> +          //    mov x-copy, x2

> +          //  obviously x2, x-copy and x2 can be mapped to same virtual

> + register

> +

> +          ir::BasicBlock::const_iterator iter =

> ir::BasicBlock::const_iterator(phiCopySrcDefInsn);

> +          ir::BasicBlock::const_iterator iterE = bb->end();

> +          // check no use of phi in this basicblock between [phiCopySrc def, bb

> end]

> +          bool phiPhiCopySrcInterfere = false;

> +          while (iter != iterE) {

> +            const ir::Instruction *insn = iter.node();

> +            // check phiUse

> +            for (unsigned i = 0; i < insn->getSrcNum(); i++) {

> +              ir::Register src = insn->getSrc(i);

> +              if (src == phi) {

> +                phiPhiCopySrcInterfere = true; break;

> +              }

> +            }

> +            ++iter;

> +          }

> +          if (!phiPhiCopySrcInterfere) {

> +            // phiCopy source can be coaleased with phiCopy

> +            const_cast<Instruction *>(phiCopyDefInsn)->remove();

> +

> +            for (auto &s : *phiCopySrcDef) {

> +              const Instruction *phiSrcDefInsn = s->getInstruction();

> +              replaceDst(const_cast<Instruction *>(phiSrcDefInsn), phiCopySrc,

> phiCopy);

> +            }

> +

> +            for (auto &s : *phiCopySrcUse) {

> +              const Instruction *phiSrcUseInsn = s->getInstruction();

> +              replaceSrc(const_cast<Instruction *>(phiSrcUseInsn), phiCopySrc,

> phiCopy);

> +            }

> +          }

> +        }

> +

>          // If phi is used in the same BB that define the phiCopy,

>          // we need carefully check the liveness of phi & phiCopy.

>          // Make sure their live ranges do not interfere.

> @@ -2206,8 +2273,7 @@ namespace gbe

>          }

>        }

> 

> -      // [MOV phi, phiCopy;] can be removed. So we remove it

> -      // and replace phi uses with phiCopy

> +      // coalease phi and phiCopy

>        if (isOpt) {

>          for (auto &x : *phiDef) {

>            const_cast<Instruction *>(x->getInstruction())->remove();

> --

> 2.3.6

> 

> _______________________________________________

> Beignet mailing list

> Beignet@lists.freedesktop.org

> http://lists.freedesktop.org/mailman/listinfo/beignet