[llvm-dev] {ARM} IfConversion does not detect BX instruction as a branch

[Gaël Jobin via llvm-dev]

I took a look at 3.9 and 4.0 code. Now, here's what I understood: 

 	* The IfConversion in 3.9 is interesting as it checks
_IsBrAnalyzable()_ for TrueBB and FalseBB before calling
_removeBranch()_.
 	* The comments and code of _analyzeBranch()_ and _removeBranch()_ are
clear to me now. My previous fix inside removeBranch() was definitely
not correct.
 	* Based on the comments (for example : "a join block may not be
present") and the code, a diamond does not have to be a complete
diamond. The TailBB is not mandatory.

Conclusion: My case should be supported then.  

_IfConvertDiamondCommon() _support different scenarios for a given
EntryBB. A quick summary: 

 	* FalseBB and TrueBB contains both an analyzable branch.
_SkipUnconditionalBranches=true_ meaning the branches are not checked if
they are identical. _ValidDiamond()_ checks that they end up on the same
TailBB. If TailBB is either nullptr or not the same for both TrueBB and
FalseBB, the diamond is not valid. _IfConvertDiamondCommon()_ is called
with removeBranch=true. Branches are successfully removed in both
blocks, thus common instructions are correctly removed based on Dups2
value. At the end, TailBB is merged or a conditional branch is inserted.
IfConversion successful.
 	* FalseBB not analyzable and TrueBB analyzable or inversely (inducing
a different branch instruction). _ValidDiamond()_ is going to fail since
FalseBB/TrueBB.TrueBB will be equal to nullptr for the not analyzable
one hence _TT =! FT _will trigger. 

	* FalseBB and TrueBB both not analyzable (indirect branch for example
on ARM). So _SkipUnconditionalBranches=false._ 

 	* If the branches are not identical, _CountDuplicatedInstruction_ will
set Dups2 to 0_. _Then_ IfConvertDiamondCommon()_ is called with
removeBranch=false. The _removeBranch()_ on TrueBB/BBI1 will silently
fail. TrueBB will be predicated completely (branch instruction
included). FalseBB on the other hand will be predicated excluding the
branch instruction (due to the loop on DI2 when removeBranch=false).
IfConversion successful.

	* If the branches are identical. _CountDuplicatedInstruction_ will set
Dups2 accordingly. 

 	* If there's no common instruction, same behaviour as in 3.1
 	* If there's some common instructions, this is my case !

In my case: The EntryBB is analyzable but TrueBB/FalseBB are not
(_AnalyzeBranches()_). TrueBB/FalseBB instructions can be predicated
(_ScanInstruction()_. _feasibleDiamond()_). TrueBB/FalseBB cannot
_SkipUnconditionalBranches_ (_ValidDiamond()_).
_CountDuplicatedInstruction()_ compute Dups1=0 as there's no common
instructions found at the beginning and Dups2=1 as it found one common
instruction at the end. During their computation, neither debug
instructions (_skipDebugInstructionsForward()_) nor branch instructions
(_TIB->isBranch()_) are counted. We note that because TrueBB and FalseBB
are not analyzable, _CountDuplicatedInstruction()_ also ensure that the
branch instruction is exactly the same in both blocks. If not, it would
not fail but simply set Dups2 to 0. 

Now when the blocks are prepared to be merged in
_IfConvertDiamondCommon()_, _removeBranch()_ fails silently on TrueBB
(BBI1) as indirect branches are not supported. Hence the erasing of the
common instructions based on Dups2=1 value will produce an invalid block
because it will remove the branch instead of the actual common
instruction. 

In the patch below, I manually delete the branch if and only if they are
identical in both block TrueBB/FalseBB. I also removed the call to
_verifySameBranchInstructions()_ as the blocks do not have to have
identical branch as explained in point 3.1 above. Works fine

> diff --git a/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp
> index ff840536617..8b8f4e67242 100644
> --- a/lib/CodeGen/IfConversion.cpp
> +++ b/lib/CodeGen/IfConversion.cpp
> @@ -1781,14 +1747,25 @@ bool IfConverter::IfConvertDiamondCommon(
> BBI.BB->splice(BBI.BB->end(), &MBB1, MBB1.begin(), DI1);
> MBB2.erase(MBB2.begin(), DI2);
> 
> -   // The branches have been checked to match, so it is safe to remove the branch
> -   // in BB1 and rely on the copy in BB2
> -#ifndef NDEBUG
> -   // Unanalyzable branches must match exactly. Check that now.
> -   if (!BBI1->IsBrAnalyzable)
> -       verifySameBranchInstructions(&MBB1, &MBB2);
> -#endif
> -    BBI1->NonPredSize -= TII->removeBranch(*BBI1->BB);
> +   // When analyzable, the branches have been checked to match, so it is safe to
> +   // remove the branch in BB1 and rely on the copy in BB2
> +   // For non-analyzable, remove branch only if they are identical
> +   if(BBI1->IsBrAnalyzable)
> +       BBI1->NonPredSize -= TII->removeBranch(*BBI1->BB);
> +   else {
> +       DI1 = BBI1->BB->end();
> +       DI2 = BBI2->BB->end();
> +       do {
> +           --DI1;
> +       }while(!DI1->isBranch() && DI1 != BBI1->BB->begin());
> +       do {
> +           --DI2;
> +       }while(!DI2->isBranch() && DI2 != BBI2->BB->begin());
> + 
> +       if(DI1->isIdenticalTo(*DI2))
> +           DI1->eraseFromParent();
> +       }
> +
> // Remove duplicated instructions.
> DI1 = MBB1.end();
> for (unsigned i = 0; i != NumDups2; ) {
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171012/53ec6b3f/attachment-0001.html>