Open quaternic opened 3 days ago
It seems the infinite loop is there (BranchFolding.cpp
)
bool MadeChangeThisIteration = true;
while (MadeChangeThisIteration) {
MadeChangeThisIteration = TailMergeBlocks(MF);
// No need to clean up if tail merging does not change anything after the
// block placement.
if (!AfterBlockPlacement || MadeChangeThisIteration)
MadeChangeThisIteration |= OptimizeBranches(MF);
if (EnableHoistCommonCode)
MadeChangeThisIteration |= HoistCommonCode(MF);
MadeChange |= MadeChangeThisIteration;
}
The part in OptimizeBlock
that will always change the MachineFunction
:
// Okay, there is no really great place to put this block. If, however,
// the block before this one would be a fall-through if this block were
// removed, move this block to the end of the function. There is no real
// advantage in "falling through" to an EH block, so we don't want to
// perform this transformation for that case.
//
// Also, Windows EH introduced the possibility of an arbitrary number of
// successors to a given block. The analyzeBranch call does not consider
// exception handling and so we can get in a state where a block
// containing a call is followed by multiple EH blocks that would be
// rotated infinitely at the end of the function if the transformation
// below were performed for EH "FallThrough" blocks. Therefore, even if
// that appears not to be happening anymore, we should assume that it is
// possible and not remove the "!FallThrough()->isEHPad" condition below.
MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;
SmallVector<MachineOperand, 4> PrevCond;
if (FallThrough != MF.end() &&
!FallThrough->isEHPad() &&
!TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
PrevBB.isSuccessor(&*FallThrough)) {
MBB->moveAfter(&MF.back());
MadeChange = true;
return MadeChange;
}
No need for three blocks the problem appears with two too:
define void @test() {
start:
br label %bb1
bb1:
callbr void asm "", "!i,!i"()
to label %bb1 [label %bb2, label %bb3]
bb2:
br label %bb1
bb3:
br label %bb1
}
The infinite loop keeps swapping the two blocks.
The MIR output before branch-folder
pass (generated with llc --stop-before=branch-folder
, to run it it llc -x mir %s
)
--- |
; ModuleID = 'faulty2.ll'
source_filename = "faulty2.ll"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
define i32 @test() {
start:
br label %basic_block_callbr
basic_block_callbr: ; preds = %basic_block_B, %basic_block_A, %basic_block_callbr, %start
callbr void asm "", "!i,!i"()
to label %basic_block_callbr [label %basic_block_A, label %basic_block_B]
basic_block_A: ; preds = %basic_block_callbr
br label %basic_block_callbr
basic_block_B: ; preds = %basic_block_callbr
br label %basic_block_callbr
}
...
---
name: test
alignment: 16
exposesReturnsTwice: false
legalized: false
regBankSelected: false
selected: false
failedISel: false
tracksRegLiveness: true
hasWinCFI: false
callsEHReturn: false
callsUnwindInit: false
hasEHCatchret: false
hasEHScopes: false
hasEHFunclets: false
isOutlined: false
debugInstrRef: true
failsVerification: false
tracksDebugUserValues: true
registers: []
liveins: []
frameInfo:
isFrameAddressTaken: false
isReturnAddressTaken: false
hasStackMap: false
hasPatchPoint: false
stackSize: 0
offsetAdjustment: 0
maxAlignment: 1
adjustsStack: false
hasCalls: false
stackProtector: ''
functionContext: ''
maxCallFrameSize: 0
cvBytesOfCalleeSavedRegisters: 0
hasOpaqueSPAdjustment: false
hasVAStart: false
hasMustTailInVarArgFunc: false
hasTailCall: false
isCalleeSavedInfoValid: true
localFrameSize: 0
savePoint: ''
restorePoint: ''
fixedStack: []
stack: []
entry_values: []
callSites: []
debugValueSubstitutions: []
constants: []
machineFunctionInfo:
amxProgModel: None
body: |
bb.0.start:
successors: %bb.1(0x80000000)
bb.1.basic_block_callbr:
successors: %bb.1(0x80000000), %bb.2(0x00000000), %bb.3(0x00000000)
INLINEASM_BR &"", 0 /* attdialect */, 13 /* imm */, %bb.2, 13 /* imm */, %bb.3
JMP_1 %bb.1
bb.2.basic_block_A (machine-block-address-taken, inlineasm-br-indirect-target):
successors: %bb.1(0x80000000)
JMP_1 %bb.1
bb.3.basic_block_B (machine-block-address-taken, inlineasm-br-indirect-target):
successors: %bb.1(0x80000000)
JMP_1 %bb.1
...
First I want to point out that the result of TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true)
don't take into account the indirect targets. It returns the result as if the block jumps unconditionally to %bb.1
.
The comment mentions the same thing with EHPad
blocks, thus I think the code don't take into account the indirect target blocks. One fix is to add a && !FallThrough->isInlineAsmBrIndirectTarget()
.
This is corroborated with the timing between:
EHPad
(2016): ff6a1edfa8e (Avoid infinite loops in branch folding)callbr
(2018): https://lists.llvm.org/pipermail/llvm-dev/2018-October/127239.html
llc hangs on this reduced example:
Example backtrace:
in which number 6 is the function that never returns. (I don't have a more recent version on hand locally, but trunk does time out as well on https://godbolt.org/z/xn1PGhbdG)
Reduced from the original Rust code: https://rust.godbolt.org/z/snGq3raxc