`phi` instruction may crash your `lli`

2016-10-19

While writing a programming language compiled into LLVM IR, I encountered this SEGV of the lli command:

% lli a.ll
0  libLLVMSupport.dylib      0x00000001071a445d llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 43
1  libLLVMSupport.dylib      0x00000001071a3c79 llvm::sys::RunSignalHandlers() + 44
2  libLLVMSupport.dylib      0x00000001071a48c6 SignalHandler(int) + 165
3  libsystem_platform.dylib  0x00007fff9496452a _sigtramp + 26
4  libsystem_platform.dylib  0x00007fff594141d8 _sigtramp + 3299540168
5  libLLVMSelectionDAG.dylib 0x0000000107065b17 llvm::SelectionDAGBuilder::HandlePHINodesInSuccessorBlocks(llvm::BasicBlock const*) + 391
6  libLLVMSelectionDAG.dylib 0x0000000107065939 llvm::SelectionDAGBuilder::visit(llvm::Instruction const&) + 39
7  libLLVMSelectionDAG.dylib 0x000000010709a815 llvm::SelectionDAGISel::SelectBasicBlock(llvm::ilist_iterator<llvm::Instruction const>, llvm::ilist_iterator<llvm::Instruction const>, bool&) + 33
8  libLLVMSelectionDAG.dylib 0x000000010709a6c5 llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) + 1299
9  libLLVMSelectionDAG.dylib 0x0000000107099916 llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) + 1270
10 libLLVMX86CodeGen.dylib   0x000000010733d9e6 (anonymous namespace)::X86DAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) + 20
11 libLLVMCodeGen.dylib      0x00000001068d6854 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) + 96
12 libLLVMCore.dylib         0x0000000106bbe077 llvm::FPPassManager::runOnFunction(llvm::Function&) + 285
13 libLLVMCore.dylib         0x0000000106bbe229 llvm::FPPassManager::runOnModule(llvm::Module&) + 41
14 libLLVMCore.dylib         0x0000000106bbe549 llvm::legacy::PassManagerImpl::run(llvm::Module&) + 567
15 libLLVMMCJIT.dylib        0x0000000106e56be5 llvm::MCJIT::emitObject(llvm::Module*) + 173
16 libLLVMMCJIT.dylib        0x0000000106e56ddd llvm::MCJIT::generateCodeForModule(llvm::Module*) + 213
17 libLLVMMCJIT.dylib        0x0000000106e57174 llvm::MCJIT::finalizeObject() + 248
18 lli                       0x00000001067f1f6b main + 7347
19 libdyld.dylib             0x00007fff852f15ad start + 1
20 libdyld.dylib             0x0000000000000002 start + 2060511830
Stack dump:
0.      Program arguments: lli a.ll
1.      Running pass 'Function Pass Manager' on module 'a.ll'.
2.      Running pass 'X86 DAG->DAG Instruction Selection' on function '@main'
zsh: segmentation fault  lli a.ll

Misuse of phi instraction was the cause of this SEGV.

Wrong pattern

Here is a example Kareido program with nested for loop:

extern i32 putchar(i32);
for (i; 1 ... 3; 1) {
  for (j; 1 ... 3; 1) {
    putchar(65 + i + j);
  }
}

And this is a "bad" translation to LLVM IR, which crashes lli.

declare i32 @putchar(i32)
define i32 @main() {
  br label %For2
For2:
  %reg1 = fadd double 0.0, 1.0
  %reg2 = fadd double 0.0, 3.0
  %reg3 = fadd double 0.0, 1.0
  br label %Loop2
Loop2:
  %i = phi double [%reg1, %For2], [%fori2, %ForBody2]
  %forc2 = fcmp oge double %i, %reg2
  br i1 %forc2, label %EndFor2, label %ForBody2
ForBody2:
  br label %For1
For1:
  %reg4 = fadd double 0.0, 1.0
  %reg5 = fadd double 0.0, 3.0
  %reg6 = fadd double 0.0, 1.0
  br label %Loop1
Loop1:
  %j = phi double [%reg4, %For1], [%fori1, %ForBody1]
  %forc1 = fcmp oge double %j, %reg5
  br i1 %forc1, label %EndFor1, label %ForBody1
ForBody1:
  %reg7 = fadd double 0.0, 65.0
  %reg8 = fadd double %reg7, %i
  %reg9 = fadd double %reg8, %j
  %reg10 = fptosi double %reg9 to i32
  %reg11 = call i32 @putchar(i32 %reg10)
  %reg12 = sitofp i32 %reg11 to double
  %fori1 = fadd double %j, %reg6
  br label %Loop1
EndFor1:
  %fori2 = fadd double %i, %reg3
  br label %Loop2
EndFor2:
  ret i32 0
}

Reason

This phi instruction is wrong because the "incoming value" %fori2 is not defined in the block %ForBody2.

%i = phi double [1.0, %For2], [%fori2, %ForBody2]

Fix

Thanksfully, fixing it is very easy. Here is a "correct" translation with a new label ForInc2, which is the argument of phi and contains definition of %fori2.

declare i32 @putchar(i32)
define i32 @main() {
  br label %For2
For2:
  %reg1 = fadd double 0.0, 1.0
  %reg2 = fadd double 0.0, 3.0
  %reg3 = fadd double 0.0, 1.0
  br label %Loop2
Loop2:
  %i = phi double [%reg1, %For2], [%fori2, %ForInc2]
  %forc2 = fcmp oge double %i, %reg2
  br i1 %forc2, label %EndFor2, label %ForBody2
ForBody2:
  br label %For1
For1:
  %reg4 = fadd double 0.0, 1.0
  %reg5 = fadd double 0.0, 3.0
  %reg6 = fadd double 0.0, 1.0
  br label %Loop1
Loop1:
  %j = phi double [%reg4, %For1], [%fori1, %ForInc1]
  %forc1 = fcmp oge double %j, %reg5
  br i1 %forc1, label %EndFor1, label %ForBody1
ForBody1:
  %reg7 = fadd double 0.0, 65.0
  %reg8 = fadd double %reg7, %i
  %reg9 = fadd double %reg8, %j
  %reg10 = fptosi double %reg9 to i32
  %reg11 = call i32 @putchar(i32 %reg10)
  %reg12 = sitofp i32 %reg11 to double
  br label %ForInc1
ForInc1:
  %fori1 = fadd double %j, %reg6
  br label %Loop1
EndFor1:
  br label %ForInc2
ForInc2:
  %fori2 = fadd double %i, %reg3
  br label %Loop2
EndFor2:
  ret i32 0
}

yhara.jp

`phi` instruction may crash your `lli`

Wrong pattern

Reason

Fix

More posts

Posts

Articles

Category

Ads

About