LLVMVerifyFunction fails: Instruction does not dominate all uses

[genericptr]

I have a function which is failing LLVMVerifyFunction with the following error:

Instruction does not dominate all uses!
  %self = alloca ptr, align 8
  %l_deref_self = load ptr, ptr %self, align 8

What is wrong here? Everything seems to be used in the order as it was declared and there is no branching so which instruction is not dominating? I’ve gotten that error before and it was always about breaks and branching so I’m very confused here.

I can post the entire module but it’s failing LLVMVerifyFunction so I don’t think it’s relevant.

Thanks!

define void @Nested(ptr dereferenceable(1) %0) {
entry:
  %proc = alloca %TProc, align 8
  %self = alloca ptr, align 8
  store ptr %0, ptr %self, align 8
  %1 = load ptr, ptr %self, align 8
  %Ttest_3_Capturer_x = getelementptr inbounds %Ttest_3_Capturer, ptr %1, i32 0, i32 0
  %alloc_temp = alloca %TProc, align 8
  store ptr @IncBy, ptr %alloc_temp, align 8
  %2 = load %TProc, ptr %alloc_temp, align 8
  store %TProc %2, ptr %proc, align 8
  %TProc_data = getelementptr inbounds %TProc, ptr %proc, i32 0, i32 1
  %l_deref_self = load ptr, ptr %self, align 8
  store ptr %l_deref_self, ptr %TProc_data, align 8
  %TProc_kind = getelementptr inbounds %TProc, ptr %proc, i32 0, i32 2
  store i8 2, ptr %TProc_kind, align 1
  br label %return

return:                                           ; preds = %entry
  ret void
}

[TNorthover]

The name @Nested suggests there might be an outer function around with values having the same names. Could it be complaining about a %self = alloca ptr in a different function? That is, the load’s operand refers to a Value not in the same function.

That kind of issue can be a bit tricky to work out because when you print the module everything looks fine, it’s the internal C++ datastructures that are messed up. Which actually makes for a reasonable test: if you can run the printed module through opt --verify (forcing a reparse) and there are no errors you may well have one of these.

[genericptr]

@TNorthover

The name @Nested suggests there might be an outer function around with values having the same names. Could it be complaining about a %self = alloca ptr in a different function? That is, the load’s operand refers to a Value not in the same function.

yes I’m playing with some capturing ideas. Did the alloc not survive the nested procedures? I thought LLVM kept it alive?

Yes, if I take the IR and run it through llc it works, so I’m confused about that too. Is the IR wrong or am I using the builder functions wrong?

; ModuleID = 'test'
source_filename = "test"

%Ttest_3_Capturer = type { i8 }
%TProc = type { ptr, ptr, i8 }

declare i32 @printf(ptr %0, ...)

declare ptr @malloc(i64 %0)

declare ptr @alloca(i64 %0)

declare void @free(ptr %0)

declare ptr @memcpy(ptr %0, ptr %1, i64 %2)

declare ptr @memset(ptr %0, i32 %1, i64 %2)

declare void @halt(i32 %0)

define void @test_3() {
entry:
  %capturer = alloca %Ttest_3_Capturer, align 8
  call void @Nested(ptr %capturer)
  br label %return

return:                                           ; preds = %entry
  ret void
}

define i64 @main() {
entry:
  call void @test_3()
  br label %return

return:                                           ; preds = %entry
  ret i64 0
}

define void @Nested(ptr dereferenceable(1) %0) {
entry:
  %proc = alloca %TProc, align 8
  %self = alloca ptr, align 8
  store ptr %0, ptr %self, align 8
  %1 = load ptr, ptr %self, align 8
  %Ttest_3_Capturer_x = getelementptr inbounds %Ttest_3_Capturer, ptr %1, i32 0, i32 0
  %alloc_temp = alloca %TProc, align 8
  store ptr @IncBy, ptr %alloc_temp, align 8
  %2 = load %TProc, ptr %alloc_temp, align 8
  store %TProc %2, ptr %proc, align 8
  %TProc_data = getelementptr inbounds %TProc, ptr %proc, i32 0, i32 1
  %l_deref_self = load ptr, ptr %self, align 8
  store ptr %l_deref_self, ptr %TProc_data, align 8
  %TProc_kind = getelementptr inbounds %TProc, ptr %proc, i32 0, i32 2
  store i8 2, ptr %TProc_kind, align 1
  br label %return

return:                                           ; preds = %entry
  ret void
}

define void @IncBy(ptr dereferenceable(1) %0, i8 %1) {
entry:
  %self = alloca ptr, align 8
  store ptr %0, ptr %self, align 8
  %v = alloca i8, align 1
  store i8 %1, ptr %v, align 1
  %l_deref_self = load ptr, ptr %self, align 8
  %Ttest_3_Capturer_x = getelementptr inbounds %Ttest_3_Capturer, ptr %l_deref_self, i32 0, i32 0
  %l_deref_self1 = load ptr, ptr %self, align 8
  %Ttest_3_Capturer_x2 = getelementptr inbounds %Ttest_3_Capturer, ptr %l_deref_self1, i32 0, i32 0
  %2 = load i8, ptr %Ttest_3_Capturer_x2, align 1
  %r_load_v = load i8, ptr %v, align 1
  %add_tmp = add i8 %2, %r_load_v
  store i8 %add_tmp, ptr %Ttest_3_Capturer_x, align 1
  br label %return

return:                                           ; preds = %entry
  ret void
}

[TNorthover]

@genericptr

yes I’m playing with some capturing ideas. Did the alloc not survive the nested procedures? I thought LLVM kept it alive?

Yes, the storage is alive but you can’t automatically refer to the alloca in the nested function, you have to pass along a pointer to access it. I think you’ve already got this right though, what you do in @test_3 is exactly it.

Is the IR wrong or am I using the builder functions wrong?

This seems more likely. I don’t exactly know your code, but when you call getSelfAlloca() (or whatever you’ve called it to get the %self), make sure the value returned is in the function you’re expecting (cast it to an Instruction * if it’s not already, and look at getParent()->getParent()).

It looks like it may be giving you the one in @IncBy when you’re actually CodeGenerating @Nested.

[genericptr]

@TNorthover

Yes, the storage is alive but you can’t automatically refer to the alloca in the nested function, you have to pass along a pointer to access it. I think you’ve already got this right though, what you do in @test_3 is exactly it.

I think I got this idea from using Godbolt and looking at C output. They seem to always create a local copy of the parameters but maybe since i’m using ptr dereferenceable(1) I should be using the ptr directly? I will play with that idea some later and see what happens. I seem to remember I was getting unexpected behavior by accessing the parameter directly but I may be mistaken.

@TNorthover

That kind of issue can be a bit tricky to work out because when you print the module everything looks fine, it’s the internal C++ datastructures that are messed up. Which actually makes for a reasonable test: if you can run the printed module through opt --verify (forcing a reparse) and there are no errors you may well have one of these.

I had this thought also since llc doesn’t complain and it would be very useful to edit the IR directly and be able to verify like the C API does. Do you mean passing the IR directly like this? Doesn’t seem to work for me (/opt/homebrew/opt/llvm@16/bin/opt).

ir_tests$ opt --verify scratch_pad.ll
The `opt -passname` syntax for the new pass manager is not supported, please use `opt -passes=<pipeline>` (or the `-p` alias for a more concise version).
See https://llvm.org/docs/NewPassManager.html#invoking-opt for more details on the pass pipeline syntax.

[TNorthover]

@genericptr

They seem to always create a local copy of the parameters but maybe since i’m using ptr dereferenceable(1) I should be using the ptr directly?

No, I think what you’ve got there is fine. Clang creates allocas for everything because it makes generating the IR simpler: instead of reasoning about where changing a variable can reach to and then inserting phi instructions at all the right places it just stores the new value to an alloca and lets LLVM optimizations remove them & tidy things up.

Do you mean passing the IR directly like this? Doesn’t seem to work for me (/opt/homebrew/opt/llvm@16/bin/opt).

Ah, sorry. I did mean exactly that but things have changed in LLVM since I last did it (not even that recently). You actually want opt --passes=verify scratch_pad.ll (which I’d expect to not print any error messages for your code because it’s the internal data structures that seem broken, not the textual representation of that IR).

[genericptr]

@TNorthover

Ah, sorry. I did mean exactly that but things have changed in LLVM since I last did it (not even that recently). You actually want opt --passes=verify scratch_pad.ll (which I’d expect to not print any error messages for your code because it’s the internal data structures that seem broken, not the textual representation of that IR).

Still no luck. scratch_pad.ll is the module in IR, not bitcode so the error doesnt’ make sense to me.

ir_tests$ opt --passes=verify scratch_pad.ll
WARNING: You're attempting to print out a bitcode file.
This is inadvisable as it may cause display problems. If
you REALLY want to taste LLVM bitcode first-hand, you
can force output with the `-f' option.

But wait, the data structures are messed up? So you can create valid IR via the C API but the data structures are broken so the verify function fails? Is that a bug or am I doing something wrong with my usage of API?

[TNorthover]

OK, to simplify a bit I think your module is roughly:

define void @Nested() {
  %self.Nested = alloca ptr
  %l_deref_self = load ptr, ptr %self.IncBy
  ret void
}

define void @RetBy() {
  %self.IncBy = alloca ptr
  ret void
}

but the problem is being hidden because both %self.Nested and %self.IncBy are just called %self.

When you print the module and read it back in with opt --passes=verify it doesn’t complain (as you’re seeing) because it correctly associates the %self load with the one allocated in the same function.

But when you created the IR with the C API you passed a pointer into LLVMBuildLoad2, and that was from the wrong function (I think).

[genericptr]

@TNorthover

But when you created the IR with the C API you passed a pointer into LLVMBuildLoad2, and that was from the wrong function (I think).

Ok so the IR is correct so I shouldn’t be looking there is what I’m hearing but rather at the LLVMBuildLoad2 calls? I’m gonna have to spend some more serious time to debug this since I’m not 100% following this conflict with %self could be.

[genericptr]

I think I know what you mean. The LLVMValueRef saved on %capturer is not the same LLVMValueRef which is referenced from %0 in @Nested. I didn’t give any consideration to whether those variables actually matched, just that they were able to produce the correct IR, in this case store ptr %0, ptr %self, align 8.

So when ever I use the value of %self it’s not the same value ref as was created in @test_3. I thought the values were transient and just meant to build the IR but you seem to be saying I need to make sure they are passed along to other functions. Is that correct?

define void @test_3() {
entry:
  %capturer = alloca %Ttest_3_Capturer, align 8
  call void @Nested(ptr %capturer)
  ...
}


define void @Nested(ptr dereferenceable(1) %0) {
entry:
  %self = alloca ptr, align 8
  store ptr %0, ptr %self, align 8
  ...
}

[TNorthover]

I may be misunderstanding, but that last post seems to be going the wrong way. I disagree with most of it.

I didn’t give any consideration to whether those variables actually matched, just that they were able to produce the correct IR

This and one or two earlier comments make me think you might be giving more weight to LLVM names (e.g. %self) than they deserve. The names are only there to help human readability, if you don’t provide one LLVM will make up its own (like %0).

In fact a good exercise might be to run your code after calling LLVMContextSetDiscardValueNames(..., true). That’ll make LLVM just ignore any names like “self” you give it and make up its own. Your code should manage just fine (if not, that’s a very good place to start looking for problems).

Mostly things will get a bit harder to read, but it’ll show what arguments LLVM thinks you’re giving it, and might make this problem more obvious.

[genericptr]

@TNorthover

In fact a good exercise might be to run your code after calling LLVMContextSetDiscardValueNames(..., true). That’ll make LLVM just ignore any names like “self” you give it and make up its own. Your code should manage just fine (if not, that’s a very good place to start looking for problems).

Ok thanks for your clarification. I turned off the names as you suggested and indeed I do see some strange things.

The fact @IncB has no %2 and @Nested has no %1 suggests that the scope in @test_3 is surviving into the nested functions and I do need to reference that same value instead of loading %0 every time. If that’s true not sure what the parameter is even used for though…

Do you see what’s wrong here?

; ModuleID = 'test'
source_filename = "test"

%Ttest_3_Capturer = type { i8 }
%TProc = type { ptr, ptr, i8 }

declare i32 @printf(ptr %0, ...)

declare ptr @malloc(i64 %0)

declare ptr @alloca(i64 %0)

declare void @free(ptr %0)

declare ptr @memcpy(ptr %0, ptr %1, i64 %2)

declare ptr @memset(ptr %0, i32 %1, i64 %2)

declare void @halt(i32 %0)

define void @test_3() {
  %1 = alloca %Ttest_3_Capturer, align 8
  call void @Nested(ptr %1)
  br label %2

2:                                                ; preds = %0
  ret void
}

define i64 @main() {
  call void @test_3()
  br label %1

1:                                                ; preds = %0
  ret i64 0
}

define void @Nested(ptr dereferenceable(1) %0) {
  %2 = alloca %TProc, align 8
  %3 = alloca ptr, align 8
  store ptr %0, ptr %3, align 8
  %4 = load ptr, ptr %3, align 8
  %5 = getelementptr inbounds %Ttest_3_Capturer, ptr %4, i32 0, i32 0
  %6 = alloca %TProc, align 8
  store ptr @IncBy, ptr %6, align 8
  %7 = load %TProc, ptr %6, align 8
  store %TProc %7, ptr %2, align 8
  %8 = getelementptr inbounds %TProc, ptr %2, i32 0, i32 1
  %9 = load ptr, ptr %3, align 8
  store ptr %9, ptr %8, align 8
  %10 = getelementptr inbounds %TProc, ptr %2, i32 0, i32 2
  store i8 2, ptr %10, align 1
  br label %11

11:                                               ; preds = %1
  ret void
}

define void @IncBy(ptr dereferenceable(1) %0, i8 %1) {
  %3 = alloca ptr, align 8
  store ptr %0, ptr %3, align 8
  %4 = alloca i8, align 1
  store i8 %1, ptr %4, align 1
  %5 = load ptr, ptr %3, align 8
  %6 = getelementptr inbounds %Ttest_3_Capturer, ptr %5, i32 0, i32 0
  %7 = load ptr, ptr %3, align 8
  %8 = getelementptr inbounds %Ttest_3_Capturer, ptr %7, i32 0, i32 0
  %9 = load i8, ptr %8, align 1
  %10 = load i8, ptr %4, align 1
  %11 = add i8 %9, %10
  store i8 %11, ptr %6, align 1
  br label %12

12:                                               ; preds = %2
  ret void
}

[TNorthover]

@genericptr

The fact @IncB has no %2 and @Nested has no %1

Ah, I’m afraid that’s a slightly weird quirk of how LLVM IR is printed. Both of those are the entry basic block of the respective function. For some reason we don’t print the 2: for the entry block of a function.

the scope in @test_3 is surviving into the nested functions and I do need to reference that same value instead of loading %0 every time.

Definitely not, to both of those.

Do you see what’s wrong here?

Annoyingly both allocas still get assigned %3 so the bug I suspect has happened can still remain hidden.

[genericptr]

@TNorthover

Definitely not, to both of those.

Ok I think I see what’s happening. I DID pass the wrong value from another function! I would have never figured that out on my own. Thank you so much.