[llvm-dev] Update control flow graph when splitting a machine basic block?
章明 via llvm-dev
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
Friedman, Eli via llvm-dev
>
> 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
_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
章明 via llvm-dev
> 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.
Friedman, Eli via llvm-dev
>> 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.
the successors() accessor. That's what you should be using for any CFG
analysis.
> 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.
I don't think this actually has any impact in practice; I mean, I guess
it's an issue in theory, but in practice we don't stick branches into
the middle of basic blocks.
-Eli
--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project
_______________________________________________
章明 via llvm-dev
> Every MachineBasicBlock has a list of successors; you can access it with
> the successors() accessor. That's what you should be using for any CFG
> analysis.
I am aware of these methods of class MachineBasicBlock, which allows one to access a MachineBasicBlock's successors and predecessors in the CFG.
But the CFG itself may no longer be valid if a MachineBasicBlock is split between two control flow instructions.
The accessors of class MachineBasicBlock do not automatically update the CFG.
So there is no way to access the up-to-date CFG.
> I don't think this actually has any impact in practice; I mean, I guess
> it's an issue in theory, but in practice we don't stick branches into
> the middle of basic blocks.
I did not expect a branch in the middle of a basic block either, until yesterday LLVM Release 4.0.0 produced the following machine basic block before the pass ARMConstantIslands is run:
bb.1.if.end:
successors: %bb.3.for.body(0x80000000)
liveins: %r4
%r0 = tMOVr %r4, 14, _, debug-location !23
tBL 14, _, $__aeabi_i2d, csr_aapcs, implicit-def dead %lr, implicit %sp, implicit %r0, implicit-def %sp, implicit-def %r0, implicit-def %r1, debug-location !23
tBL 14, _, @sqrt, csr_aapcs, implicit-def dead %lr, implicit %sp, implicit %r0, implicit %r1, implicit-def %sp, implicit-def %r0, implicit-def %r1, debug-location !24
tBL 14, _, $__aeabi_d2iz, csr_aapcs, implicit-def dead %lr, implicit %sp, implicit %r0, implicit %r1, implicit-def %sp, implicit-def %r0, debug-location !25
DBG_VALUE 2, 0, !17, !18, debug-location !27
DBG_VALUE debug-use %r0, debug-use _, !16, !18, debug-location !26
tCMPi8 %r0, 2, 14, _, implicit-def %cpsr, debug-location !32
t2IT 11, 28, implicit-def %itstate
%r0 = tMOVi8 _, 1, 11, %cpsr, implicit %r0, implicit %itstate
tPOP_RET 11, %cpsr, def %r4, def %r6, def %r7, def %pc, implicit %r0, implicit %r4, implicit killed %itstate, debug-location !44
%r1 = t2MOVi 2, 14, _, _
t2B %bb.3.for.body, 14, _
Note that a terminator tPOP_RET is before a non-terminator t2MOVi.
The command line to produce this is as follows:
llc -mtriple=thumbv7m-none-none-eabi -mcpu=cortex-m3 -O1 -stop-before=arm-cp-islands -o prime-factorize.mir prime-factorize.ll
Attached are the input file prime-factorize.ll and output file prime-factorize.mir.
The machine basic block above violates my previous assumption that only terminators and debug instructions may appear after the first terminator in a machine basic block.
I don't know how "bad" this could be, i.e., how many non-terminators in a program could be generated between two terminators.
So I have to consider split such basic blocks before I could instrument the program with control flow checks.
I don't know whether this is a bug or not. If it is not a bug, this apparently isn't a purely theoretical issue.
Best regards!
Ming Zhang
Friedman, Eli via llvm-dev
It looks like what's happening is that IfConversion makes the return
conditional, then that gets merged with the following block. I mean, I
would say it's a bug in that there's a "terminator" in a position not at
the end of the block, but a return doesn't have any CFG successors, so
I'm not sure it has any practical effect.
I think we won't merge with the following block for an indirect branch
which is not a return.
-Eli
--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project
_______________________________________________
章明 via llvm-dev
> conditional, then that gets merged with the following block. I mean, I
> would say it's a bug in that there's a "terminator" in a position not at
> the end of the block, but a return doesn't have any CFG successors, so
> I'm not sure it has any practical effect.
>
> I think we won't merge with the following block for an indirect branch
> which is not a return.
I believe MachineBasicBlock::getFirstTerminator, MachineBasicBlock::getFirstInstrTerminator, and
Methods/functions that use these methods will break on a machine basic block like this,
although I have not tested these with such a machine basic block. I don't know whether
MachineBasicBlock::getFirstTerminator and MachineBasicBlock::getFirstInstrTerminator are
intended to be used in a late stage like just before code emission or not.
I am trying to circumvent this issue by splitting machine basic blocks, s.t. if
a machine basic block contains a terminator, only terminators or non-real instructions
like DBG_VALUE may come after the first terminator. This would probably also involve
updating the CFG. I'm trying to update the CFG by inspecting targets of terminators, but
I am not sure whether this approach is viable. My code for updating the CFG after splitting
a machine basic block is as follows. I intend to run the code before ARMConstantIslands.
Could you please give me some advice? Thank you!
// This function assumes the successors of the old machine basic
// block are correct. If the target of a terminator in a new machine basic
// block is not a successor of the old machine basic block, the target is not
// treated as a successor of the new machine basic block. If a successor of the
// old machine basic block is not the target of any of the terminators in the
// new machine basic blocks, the successor of the old machine basic block is
// conservatively treated as a common successor of all the new machine basic
// blocks.
// MBBBefore: New machine basic block before the split point.
// MBBAfter: New machine basic block after the split point.
// Successors: Successors of the old machine basic block.
// MF: Machine function that contains the new machine basic blocks and the
// successors of the old machine basic block.
void UpdateCFG(MachineBasicBlock &MBBBefore,
MachineBasicBlock &MBBAfter,
std::unordered_set<MachineBasicBlock *> &Successors,
MachineFunction &MF) {
const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
assert(TII && "The target instruction information must not be a null pointer.");
const MachineJumpTableInfo *MJTI = MF.getJumpTableInfo();
assert(MJTI && "The machine jump table information must not be a null pointer.");
const std::vector<MachineJumpTableEntry> &JumpTables = MJTI->getJumpTables();
SmallVector<MachineBasicBlock *, 2> MBBs = {&MBBBefore, &MBBAfter};
std::unordered_set<MachineBasicBlock *> RemainingSuccessors = Successors;
for (auto MBB : MBBs) {
assert(MBB && "A new machine basic block cannot be a null pointer.");
// Remove all successors from the new machine basic block.
for (auto SuccI = MBB->succ_begin(), SuccE = MBB->succ_end();
SuccI != SuccE;
SuccI++)
MBB->removeSuccessor(SuccI);
bool MayFallthrough = true;
// Iterate over all terminators of the new machine basic block.
// Note: MachineBasicBlock::getFirstTerminator and
// MachineBasicBlock::getFirstInstrTerminator seem to assume that every
// machine instructions after the first terminator is either a terminator or
// a debug instruction. This assumption does not always hold.
// We do not use MachineBasicBlock::terminators here, because it depends on
// MachineBasicBlock::getFirstTerminator.
for (auto MI = MBB->begin(), MIE = MBB->end(); MI != MIE; MI++) {
if (!MI->isTerminator())
continue;
// Determine the target of the terminator.
// We search for operands that are machine basic blocks or jump table
// indices.
// Returns and indirect branches are ignored, since their targets are not
// machine basic blocks.
for (auto Op = MI->operands_begin(), OpE = MI->operands_end();
Op != OpE;
Op++) {
// FIXME: Could a machine basic block operand of a terminator not be the target of the terminator?
// FIXME: Could a terminator other than jump table have more than one targets?
if (Op->isMBB()) {
// The operand is a machine basic block.
MachineBasicBlock *Target = Op->getMBB();
// If the possible target of the terminator is a successor of the old
// machine basic block, or if the terminator is in the new machine
// basic block before the split point and the operand is the new
// machine basic block after the split point, then treat the target of
// the terminator as a successor of the new basic block and remove it
// from the remaining successors.
if (Successors.count(Target) ||
(MBB == &MBBBefore && Target == &MBBAfter)) {
MBB->addSuccessor(Target);
RemainingSuccessors.erase(Target);
}
}
if (Op->isJTI()) {
// The operand is a jump table index.
unsigned JTI = Op->getIndex();
assert(JTI < JumpTables.size() &&
"The jump table index is out-of-range.");
const MachineJumpTableEntry &JT = JumpTables[JTI];
for (MachineBasicBlock *Target : JT.MBBs) {
// If the possible target of the terminator is a successor of the
// old machine basic block, then treat it as a successor of the new
// basic block and remove it from the remaining successors.
if (Successors.count(Target)) {
MBB->addSuccessor(Target);
RemainingSuccessors.erase(Target);
}
}
}
}
// If the terminator is an unconditional control flow barrier, then the
// machine basic block cannot fall through to its layout successor, and
// instructions after it cannot be executed.
// FIXME: Is this a correct way to determine whether an machine instruction may fall through?
if (MI->isBarrier() && !TII->isPredicated(*MI)) {
MayFallthrough = false;
break;
}
}
// If the new machine basic block may fall through to its layout successor,
// then treat the layout successor as a successor of the new machine basic
// block.
if (MayFallthrough) {
MachineFunction::iterator LayoutSuccessor = std::next(MBB->getIterator());
if (LayoutSuccessor != MF.end()) {
if ((MBB == &MBBBefore && &*LayoutSuccessor == &MBBAfter) ||
(MBB == &MBBAfter && Successors.count(&*LayoutSuccessor))) {
MBB->addSuccessor(&*LayoutSuccessor);
RemainingSuccessors.erase(&*LayoutSuccessor);
}
}
}
}
// Treat the remaining successors, i.e., successors of the old machine basic
// block that are not found to be targets of terminators in the new machine
// basic blocks, as common successors of all the new machine basic blocks.
for (auto MBB : MBBs) {
for (auto Succ : RemainingSuccessors)
MBB->addSuccessor(Succ);
Friedman, Eli via llvm-dev
>> It looks like what's happening is that IfConversion makes the return
>> conditional, then that gets merged with the following block. I mean, I
>> would say it's a bug in that there's a "terminator" in a position not at
>> the end of the block, but a return doesn't have any CFG successors, so
>> I'm not sure it has any practical effect.
>>
>> I think we won't merge with the following block for an indirect branch
>> which is not a return.
> I believe MachineBasicBlock::getFirstTerminator, MachineBasicBlock::getFirstInstrTerminator, and
> Methods/functions that use these methods will break on a machine basic block like this,
> although I have not tested these with such a machine basic block. I don't know whether
> MachineBasicBlock::getFirstTerminator and MachineBasicBlock::getFirstInstrTerminator are
> intended to be used in a late stage like just before code emission or not.
If you really want to prevent the merge, it's probably not hard. See the
handling for isReturn() in ARMBaseInstrInfo::analyzeBranch, which
intentionally ignores predicated return instructions. But it's probably
simpler from your perspective to do the same thing that analyzeBranch
does, and ignore predicated return instructions.
-Eli
--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project
_______________________________________________