[Beignet] [PATCH 02/18] GBE: Remove BBs if it only has a label instruction.

[Zhigang Gong]

I noticed that we already called createCFGSimplificationPass several times
before the createGenPass.
It seems that it's not enough, we still need to add one more exactly before
the createGenPass(unit).

I will add the extra pass to this patch. But I still prefer to have this
patch in. It's the last chance to
prevent such a bb to be passed to the backend, and it just check each BB's
last insn which is very cheap.

Any further comment?

> -----Original Message-----
> From: Beignet [mailto:beignet-bounces at lists.freedesktop.org] On Behalf Of
> Song, Ruiling
> Sent: Thursday, April 3, 2014 9:57 AM
> To: Gong, Zhigang; beignet at lists.freedesktop.org
> Cc: Gong, Zhigang
> Subject: Re: [Beignet] [PATCH 02/18] GBE: Remove BBs if it only has a
label
> instruction.
> 
> In fact, llvm has a pass to remove or merge BBs.
> Simply add passes.add(createCFGSimplificationPass()); before
> passes.add(createGenPass(unit)); will get rid of those BBs in llvm IR.
> See whether it can solve the issue you met.
> 
> Thanks!
> Ruiling
> -----Original Message-----
> From: Beignet [mailto:beignet-bounces at lists.freedesktop.org] On Behalf Of
> Zhigang Gong
> Sent: Friday, March 28, 2014 3:11 PM
> To: beignet at lists.freedesktop.org
> Cc: Gong, Zhigang
> Subject: [Beignet] [PATCH 02/18] GBE: Remove BBs if it only has a label
> instruction.
> 
> Signed-off-by: Zhigang Gong <zhigang.gong at intel.com>
> ---
>  backend/src/ir/context.cpp  |  3 +-
>  backend/src/ir/function.cpp | 75
> +++++++++++++++++++++++++++++++++++++++++++++
>  backend/src/ir/function.hpp |  4 +++
>  3 files changed, 81 insertions(+), 1 deletion(-)
> 
> diff --git a/backend/src/ir/context.cpp b/backend/src/ir/context.cpp index
> 15d3b0a..0fd6803 100644
> --- a/backend/src/ir/context.cpp
> +++ b/backend/src/ir/context.cpp
> @@ -75,7 +75,8 @@ namespace ir {
>      // Remove all returns and insert one unique return block at the end
of the
>      // function
>      lowerReturn(unit, fn->getName());
> -
> +    // Remove empty labels at first
> +    fn->removeEmptyLabels();
>      // Properly order labels and compute the CFG, it's needed by
> FunctionArgumentLower
>      fn->sortLabels();
>      fn->computeCFG();
> diff --git a/backend/src/ir/function.cpp b/backend/src/ir/function.cpp
index
> a6aecb5..7ea3b1a 100644
> --- a/backend/src/ir/function.cpp
> +++ b/backend/src/ir/function.cpp
> @@ -64,6 +64,81 @@ namespace ir {
>      loops.push_back(GBE_NEW(Loop, bbs, exits));
>    }
> 
> +  void Function::removeBlock(BasicBlock *BB) {
> +    GBE_ASSERTM(BB->begin() == BB->end(), "BB to be removed is not
> empty");
> +    if (BB->getPrevBlock() != NULL && BB->getNextBlock() != NULL) {
> +      BB->getPrevBlock()->nextBlock = BB->getNextBlock();
> +      BB->getNextBlock()->prevBlock = BB->getPrevBlock();
> +    }
> +    for(auto it = blocks.begin(); it != blocks.end(); it++) {
> +      if (*it == BB) {
> +        blocks.erase(it);
> +        break;
> +      }
> +    }
> +  }
> +
> +  void Function::removeEmptyLabels(void) {
> +    // Empty label map, we map the removed label to the next label.
> +    map<LabelIndex, LabelIndex> labelMap;
> +    map<LabelIndex, LabelIndex> revLabelMap;
> +    foreachBlock([&](BasicBlock &BB) {
> +      Instruction * insn = BB.getLastInstruction();
> +      if (insn->getOpcode() == OP_LABEL) {
> +        const LabelIndex index = BB.getLabelIndex();
> +        const LabelIndex next = LabelIndex(((uint16_t)index) + 1);
> +        labelMap.insert(std::make_pair(index, next));
> +        auto needFixIt = revLabelMap.find(index);
> +        if (needFixIt != revLabelMap.end()) {
> +          // Fix up the previous map with the new next label.
> +          labelMap.erase(needFixIt->second);
> +          labelMap.insert(std::make_pair(needFixIt->second, next));
> +        }
> +        revLabelMap.insert(std::make_pair(next, index));
> +        insn->remove();
> +        removeBlock(&BB);
> +      }
> +    });
> +
> +    // fix labels for loops
> +    for (auto &x : loops) {
> +      for (auto &y : x->bbs) {
> +        if (labelMap.find(y) != labelMap.end())
> +          y = labelMap.find(y)->second;
> +      }
> +
> +      for (auto &z : x->exits) {
> +        if (labelMap.find(z.first) != labelMap.end())
> +          z.first = labelMap.find(z.first)->second;
> +        if (labelMap.find(z.second) != labelMap.end())
> +          z.second = labelMap.find(z.second)->second;
> +      }
> +    }
> +
> +
> +    // Patch all branch instructions with the new labels
> +    foreachInstruction([&](Instruction &insn) {
> +      if (insn.getOpcode() != OP_BRA)
> +        return;
> +
> +      // Get the current branch instruction
> +      BranchInstruction &bra = cast<BranchInstruction>(insn);
> +      const LabelIndex index = bra.getLabelIndex();
> +      if (labelMap.find(index) == labelMap.end())
> +        return;
> +      const LabelIndex newIndex = labelMap.find(index)->second;
> +
> +      // Insert the patched branch instruction
> +      if (bra.isPredicated() == true) {
> +        const Instruction newBra = BRA(newIndex,
> bra.getPredicateIndex());
> +        newBra.replace(&insn);
> +      } else {
> +        const Instruction newBra = BRA(newIndex);
> +        newBra.replace(&insn);
> +      }
> +    });
> +  }
> +
>    void Function::sortLabels(void) {
>      uint32_t last = 0;
> 
> diff --git a/backend/src/ir/function.hpp b/backend/src/ir/function.hpp
index
> 03aeaeb..ad4773e 100644
> --- a/backend/src/ir/function.hpp
> +++ b/backend/src/ir/function.hpp
> @@ -281,6 +281,10 @@ namespace ir {
>      void computeCFG(void);
>      /*! Sort labels in increasing orders (top block has the smallest
label) */
>      void sortLabels(void);
> +    /*! Remove empty block. */
> +    void removeBlock(BasicBlock *BB);
> +    /*! Remove empty Label. */
> +    void removeEmptyLabels(void);
>      /*! Get the pointer family */
>      RegisterFamily getPointerFamily(void) const;
>      /*! Number of registers in the register file */
> --
> 1.8.3.2
> 
> _______________________________________________
> Beignet mailing list
> Beignet at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/beignet
> _______________________________________________
> Beignet mailing list
> Beignet at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/beignet