llvm dev - Jul 2020 - question on analyzeBranch and getFallThrough

I am working on a back end for an architecture whose jump via table instruction
includes the range check. If the index is out of range, the jump table 
instruction just falls through.  I implemented a pass to remove the range check 
generated before the jump table instruction because it is superfluous.
This causes as assertion in MachineBlockPlacement.cpp:
       assert((!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond) ||
               !PrevBB->canFallThrough()) &&
              "Unexpected block with un-analyzable fallthrough!");

The method MachineBasicBlock::getFallThrough() uses TII->analyzeBranch().
Using analyze branch there doesn't appear to be anyway to signify that a
branch
is not a simple conditional or a simple indirect but rather a combination of 
the two -- it conditionally branches indirect or falls through.

Is there a way to express this with analyzeBranch?

Can I override the method getFallThough?

Is there a way to annotate a basic block to indicate in can fall through?
It would seem this would save a lot of calls to analyzeBranck.

Any other ideas?

Thanks,
Brian

On Thu, Jul 9, 2020 at 5:32 PM Bagel via llvm-dev <llvm-dev at
lists.llvm.org>
wrote:
> I am working on a back end for an architecture whose jump via table
> instruction
> includes the range check. If the index is out of range, the jump table
> instruction just falls through.  I implemented a pass to remove the range
> check
> generated before the jump table instruction because it is superfluous.
> This causes as assertion in MachineBlockPlacement.cpp:
>        assert((!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond) ||
>                !PrevBB->canFallThrough()) &&
>               "Unexpected block with un-analyzable
fallthrough!");

This should not be possible, because blocks which might fall-through and
where analyzeBranch said "i dunno" were placed into
the BlocksWithUnanalyzableExits set, checked right before that assert.

> The method MachineBasicBlock::getFallThrough() uses
TII->analyzeBranch().
Using analyze branch there doesn't appear to be anyway to signify that
a
> branch
> is not a simple conditional or a simple indirect but rather a combination
> of
> the two -- it conditionally branches indirect or falls through.
>
analyzeBranch should be returning "I dunno" (aka true) for this block,
in
which case getFallThrough should indicate that the block might fall
through. The only other reason getFallThrough wouldn't return a block, is
if your block successors are incorrect, or if the last instruction in the
block (maybe your jump table instruction) is incorrectly marked as
"isBarrier = 1", despite being able to continue.

Is there a way to express this with analyzeBranch?
>
> Can I override the method getFallThough?
>
> Is there a way to annotate a basic block to indicate in can fall through?
> It would seem this would save a lot of calls to analyzeBranck

I'm working on a change to do this, but that's independent to your
issue.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200711/a570f06f/attachment.html>

Excellent diagnosis!  I had marked the jump table instruction "isBarrier =
1".
When I removed that, no assertion.

Thanks for the quick fix,
Brian

On 7/11/20 8:16 PM, James Y Knight wrote:
> 
> 
> On Thu, Jul 9, 2020 at 5:32 PM Bagel via llvm-dev <llvm-dev at
lists.llvm.org
> <mailto:llvm-dev at lists.llvm.org>> wrote:
> 
>     I am working on a back end for an architecture whose jump via table
instruction
>     includes the range check. If the index is out of range, the jump table
>     instruction just falls through.  I implemented a pass to remove the
range
>     check
>     generated before the jump table instruction because it is superfluous.
>     This causes as assertion in MachineBlockPlacement.cpp:
>             assert((!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond) ||
>                     !PrevBB->canFallThrough()) &&
>                    "Unexpected block with un-analyzable
fallthrough!");
> 
> 
> This should not be possible, because blocks which might fall-through and
where
> analyzeBranch said "i dunno" were placed into
the BlocksWithUnanalyzableExits
> set, checked right before that assert.
> 
>     The method MachineBasicBlock::getFallThrough() uses
TII->analyzeBranch().
> 
>     Using analyze branch there doesn't appear to be anyway to signify
that a
>     branch
>     is not a simple conditional or a simple indirect but rather a
combination of
>     the two -- it conditionally branches indirect or falls through.
> 
> 
> analyzeBranch should be returning "I dunno" (aka true) for this
block, in which
> case getFallThrough should indicate that the block might fall through. The
only
> other reason getFallThrough wouldn't return a block, is if your block 
> successors are incorrect, or if the last instruction in the block (maybe
your
> jump table instruction) is incorrectly marked as "isBarrier = 1",
despite being
> able to continue.
> 
>     Is there a way to express this with analyzeBranch?
> 
>     Can I override the method getFallThough?
> 
>     Is there a way to annotate a basic block to indicate in can fall
through?
>     It would seem this would save a lot of calls to analyzeBranck
> 
> 
> I'm working on a change to do this, but that's independent to your
issue.
>

Are you sure that if analyzeBranch returns true (i dunno) the block following 
(in layout) will never get moved.  I have the case where:
   bb0: JT    - jump table instruction which can fall through
   bb1:       - the fall through block that JT may fall through
   bb2:       - some block that JT may branch to
And a later pass reorders the blocks:
   bb0:
   bb2:
   bb1:
perhaps because in bb0's successors, bb2 had a higher probability that bb1.

How can I ensure that bb1 always follows bb0 in layout?

Thanks,
brian

On 7/11/20 8:16 PM, James Y Knight wrote:
> 
> 
> On Thu, Jul 9, 2020 at 5:32 PM Bagel via llvm-dev <llvm-dev at
lists.llvm.org
> <mailto:llvm-dev at lists.llvm.org>> wrote:
> 
>     I am working on a back end for an architecture whose jump via table
instruction
>     includes the range check. If the index is out of range, the jump table
>     instruction just falls through.  I implemented a pass to remove the
range
>     check
>     generated before the jump table instruction because it is superfluous.
>     This causes as assertion in MachineBlockPlacement.cpp:
>             assert((!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond) ||
>                     !PrevBB->canFallThrough()) &&
>                    "Unexpected block with un-analyzable
fallthrough!");
> 
> 
> This should not be possible, because blocks which might fall-through and
where
> analyzeBranch said "i dunno" were placed into
the BlocksWithUnanalyzableExits
> set, checked right before that assert.
> 
>     The method MachineBasicBlock::getFallThrough() uses
TII->analyzeBranch().
> 
>     Using analyze branch there doesn't appear to be anyway to signify
that a
>     branch
>     is not a simple conditional or a simple indirect but rather a
combination of
>     the two -- it conditionally branches indirect or falls through.
> 
> 
> analyzeBranch should be returning "I dunno" (aka true) for this
block, in which
> case getFallThrough should indicate that the block might fall through. The
only
> other reason getFallThrough wouldn't return a block, is if your block 
> successors are incorrect, or if the last instruction in the block (maybe
your
> jump table instruction) is incorrectly marked as "isBarrier = 1",
despite being
> able to continue.
> 
>     Is there a way to express this with analyzeBranch?
> 
>     Can I override the method getFallThough?
> 
>     Is there a way to annotate a basic block to indicate in can fall
through?
>     It would seem this would save a lot of calls to analyzeBranck
> 
> 
> I'm working on a change to do this, but that's independent to your
issue.
>