LLVM IR nested phi instruction

Question

im working on a my own programming language. Im currently generating the code in LLVM IR. I got a question on nested If statement with phi. So lets say I have this in my language :

 if n < 0 then print("n < 0") else if 100 < n then print("100") else print("\n")

I generated this in llvm ir :

; If ; ObjectIdentifier %15 = load %struct.Main*, %struct.Main** %2 %16 = getelementptr inbounds %struct.Main, %struct.Main* %15, i32 0, i32 1 %17 = load i32, i32* %16 ; VarValue %18 = alloca i32 store i32 0, i32* %18 %19 = load i32, i32* %18 ; Lower %20 = icmp slt i32 %17, %19 br i1 %20, label %condIf1, label %condElse1 condIf1: ; Call Method %21 = load %struct.Main*, %struct.Main** %2 %22 = getelementptr inbounds %struct.Main, %struct.Main* %21, i32 0, i32 0 ; Arguments ; VarValue %23 = alloca [6 x i8] store [6 x i8] c"n < 0\00", [6 x i8]* %23 %24 = bitcast [6 x i8]* %23 to i8* %25 = call %struct.IO* @IO_print(%struct.IO* %22, i8* %24) br label %condEnd1 condElse1: ; If ; VarValue %26 = alloca i32 store i32 100, i32* %26 %27 = load i32, i32* %26 ; ObjectIdentifier %28 = load %struct.Main*, %struct.Main** %2 %29 = getelementptr inbounds %struct.Main, %struct.Main* %28, i32 0, i32 1 %30 = load i32, i32* %29 ; Lower %31 = icmp slt i32 %27, %30 br i1 %31, label %condIf2, label %condElse2 condIf2: ; Call Method %32 = load %struct.Main*, %struct.Main** %2 %33 = getelementptr inbounds %struct.Main, %struct.Main* %32, i32 0, i32 0 ; Arguments ; VarValue %34 = alloca [8 x i8] store [8 x i8] c"n > 100\00", [8 x i8]* %34 %35 = bitcast [8 x i8]* %34 to i8* %36 = call %struct.IO* @IO_print(%struct.IO* %33, i8* %35) br label %condEnd2 condElse2: ; Call Method %37 = load %struct.Main*, %struct.Main** %2 %38 = getelementptr inbounds %struct.Main, %struct.Main* %37, i32 0, i32 0 ; Arguments ; VarValue %39 = alloca [2 x i8] store [2 x i8] c"\0a\00", [2 x i8]* %39 %40 = bitcast [2 x i8]* %39 to i8* %41 = call %struct.IO* @IO_print(%struct.IO* %38, i8* %40) br label %condEnd2 condEnd2: %42 = phi %struct.IO* [%36, %condIf2], [%41, %condElse2] br label %condEnd1 condEnd1: %43 = phi %struct.IO* [%25, %condIf1], [%43, %condElse1]

Everything compiled, but i get those errors :

 PHI node entries do not match predecessors! %43 = phi %struct.IO* [ %25, %condIf1 ], [ %42, %condElse1 ] label %condElse1 label %condEnd2 Instruction does not dominate all uses! %42 = phi %struct.IO* [ %36, %condIf2 ], [ %41, %condElse2 ] %43 = phi %struct.IO* [ %25, %condIf1 ], [ %42, %condElse1 ]

I can't figure out exactly what is the problem with the phi. Do you have any hint on how to solve this issue or use something else then phi ? Thank you !

My LLVM is a bit rusty :). Before I try to answer, why is the definition of %43 in the generated code and the error message different? are you sure this is not a typo — knightrider
– knightrider, Commented Aug 20, 2018 at 15:48
@knightrider Youre right. I was doing some test after the initial error message. I put it back like it should be — MaxThom
– MaxThom, Commented Aug 20, 2018 at 19:49

sepp2k · Accepted Answer · 2018-08-20 15:48:17Z

condEnd1: %43 = phi %struct.IO* [%25, %condIf1], [%test, %condElse1]

The predecessors of condEnd1 (i.e. the blocks that jump to condEnd1) are condIf1 and condEnd2, not condElse1 (that's what the error message is telling you). A phi node should list all of the block's predecessor and no other blocks because it's saying "if you jumped here from block foo, use value bar" and that only makes sense if foo is a block that can actually jump to the block that the phi node is in.

Further %test isn't available in the block %condElse1 (%condElse1 does not contain the definition of %test, nor do all control flow paths to %condElse1 go through the block that does), so if %condElse1 were a predecessor, you wouldn't be allowed to take the value of %test when jumping from there.

Both of these can be fixed by replacing %condElse1 with %condEnd2 in the phi. %condEnd2 is actually a predecessor of condEnd1 and it contains the definition of %test.

As for alternatives to using phi nodes:

A common way to represent local variables is to allocate stack space for each variable using alloca at the beginning of the function and then writing and reading from that memory when you need the value. This way you'd have one register per variable to store the variable's address, which would be defined in the first block of the function and thus dominate the entire function, and then, each time you work with a variable, temporary registers that don't outlive the current block. So there'd be no need for phi nodes.

In cases where the variables' addresses are never used, LLVM's mem2reg phase would rewrite this to the version using registers and phi nodes, so you'll get the same optimizability and performance, but don't have to transform everything to SSA form yourself.

Thank you, your answer solved my issue. I decided to stay with phi and I manage to generate the good labels.

Collectives™ on Stack Overflow

LLVM IR nested phi instruction

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related