llvm dev - Nov 2017 - Update control flow graph when splitting a machine basic block?

Hi, there!




There are situations where a machine basic block has to be split into two
machine basic blocks, e.g., to place a constant pool entry or to fix a
conditional branch so that its target is within its range
(https://reviews.llvm.org/D38918).




However, it doesn't appear to be straightforward how the control flow graph
should be updated when a machine basic block is split, especially when the split
point is between two branches. In this case, in order to determine the
successors of each of the two machine basic block, one needs to know the target
of each terminator. If we ignore indirect branches whose targets are not known
at compile-time, I wonder whether something like the following is viable or not:




empty mbb.successors

fallthrough = true

for each terminator i in machine basic block mbb

do

    if i is control flow barrier and i is not predicable            // Is this
the correct way to determine whether an instruction may fall through?

        fallthrough = false

        break                                          // Instructions after the
first non-predicable barrier cannot be executed, right?

    fi

    ignore operands of i if i is a return

    for each operand o of i

    do

        if o is a machine basic block                // Can an instruction other
than a jump table instruction target multiple machine basic blocks?

            add o to mbb.successors

        fi

        if o is a jump table index

            add all machine basic blocks in the jump table to mbb.successors

        fi

    done

done

if fallthrough == true

    add the layout successor to mbb.successors, if one exists

fi




Am I missing something?

Please give me some advice.

Thank you!




Ming Zhang
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171110/54df5286/attachment.html>

On 11/10/2017 4:33 AM, 章明 via llvm-dev wrote:
>
> Hi, there!
>
>
> There are situations where a machine basic block has to be split into 
> two machine basic blocks, e.g., to place a constant pool entry or to 
> fix a conditional branch so that its target is within its range 
> (https://reviews.llvm.org/D38918).
>
The right way to update the CFG very much depends on how you're 
transforming it.
> However, it doesn't appear to be straightforward how the control flow 
> graph should be updated when a machine basic block is split, 
> especially when the split point is between two branches.In this case, 
> in order to determine the successors of each of the two machine basic 
> block, one needs to know the target of each terminator. If we ignore 
> indirect branches whose targets are not known at compile-time, I 
> wonder whether something like the following is viable or not:
>
Your pseudo-code looks similar to ARMBaseInstrInfo::analyzeBranch.

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

> The right way to update the CFG very much depends on how you're 
> transforming it.
I would like to export the CFG for control flow checking.
Theoretically, it should be possible for a compiler to know every target of
every control flow instruction, except for computed targets that are not known
at compile-time.
When a machine basic block is split between two branches, as shown below:

BB:                 ; Old machine basic block shortened by the split
    ...
    branch to A
------------------- ; Split here
BB':                ; New machine basic block created by the split
    branch to B
    ...

BB' is a successor of BB (if there is no control flow barrier near the end
of BB).
In addition, targets of terminators like A should be added to the set of
successors of BB and possibly removed from the set of successors of BB'.
It is not always safe to remove B from the successors of BB', because A and
B may be the same machine basic block.

If edges in the CFG are interpreted as possible control flow transfers, rather
than definite control flow transfers, the most conservative way to update the
CFG might be:
1) Let BB' have all successors of the original machine basic block before
the split.
2) Add BB' and all successors of BB' to the set of successors of BB.
However, this introduce false control flow transfers into the CFG. False control
flow transfers are harmful to control flow checking, because different basic
blocks have to be assigned the same signature, which is called aliasing.

To update the CFG without introducing any false control flow transfers, one
needs to determine the target(s) of each terminator.
That is what I desire. I am not quite familiar with LLVM, so I am asking whether
it is possible to achieve that with the current LLVM API.
> Your pseudo-code looks similar to ARMBaseInstrInfo::analyzeBranch.
ARMBaseInstrInfo::analyzeBranch also attempts to determine targets of
terminators.
However, that method is not adequate to achieve what I desire, because it only
works for simple conditional/unconditional branches. When it sees something
else, e.g., a jump table, it simply reports that the machine basic block cannot
be analyzed.