llvm dev - Jul 2014 - [LLVMdev] Telling the optimizer a value is always null at the start

How do I tell the optimizer that the (dereferenced) value of an i8**
parameter is NULL at the start so that it can eliminate the check?

I have code like:

       void test2(void** ex) {
         printf("go\n"); // does not change *ex
       }

       void call2(void** ex);

       void testeh(void** ex) {
         // I want to tell the optimizer *ex is null so it can eliminate the
first if below if test2 is inlined:
         test2(ex)
         if (*ex) return;
         printf("done")
       }

I tried with llvm.invariant.start/end but that doesn't seem to make any
difference, the icmp/br seems to stay. Can this be done with the current
optimizers?

My usecase is exception handling via an out parameter. The contract is  
that on entry ex always points to a stack position which value holds null.


; ModuleID = 'test.ll'
target datalayout = "e-m:w-p:32:32-i64:64-f80:32-n8:16:32-S32"
target triple = "i686-pc-windows-msvc"

@str1 = linkonce_odr unnamed_addr constant [3 x i8] c"go\00", align 1
@str2 = linkonce_odr unnamed_addr constant [5 x i8] c"done\00", align
1

define void @inlineeh(i8** nocapture readnone %ex) {
     %1 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([3 x
i8]* @str1, i32 0, i32 0))
     ret void
}

declare i32 @printf(i8* nocapture readonly, ...) #0

define void @testeh(i8** nocapture %ex) #0 {
     %1 = bitcast i8** %ex to i8*
     %2 = tail call {}* @llvm.invariant.start(i64 4, i8* %1)
     tail call void @llvm.invariant.end({}* %2, i64 4, i8* %1)
     %3 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([3 x
i8]* @str1, i32 0, i32 0))
     %4 = load i8** %ex, align 4
     %5 = icmp eq i8* %4, null
     br i1 %5, label %6, label %8

; <label>:6                                       ; preds = %0
     %7 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([5 x
i8]* @str2, i32 0, i32 0))
     br label %8

; <label>:8                                       ; preds = %0, %6
     ret void
}

declare void @llvm.invariant.end({}*, i64, i8* nocapture)
declare {}* @llvm.invariant.start(i64, i8* nocapture)




-- 
Carlo Kok
RemObjects Software

Hm, I don't know of an explicit way in the IR to do this.  If anyone 
else does, feel free to chime in.

One approach would be to add a branch at the beginning of the function 
to an unreachable block.  If you're testeh function started with:
if( *ex != null) llvm_unreachable();

You might get lucky and have the GVN or EarlyCSE propagate the null 
value.  You're going to run into pass ordering problems here though.  I 
suspect we'd drop the unreachable block before GVN runs. I looked at 
something like this previously: 
http://www.philipreames.com/Blog/2014/02/15/tweaking-llvm-to-exploit-assumex/

If you're willing to tolerate an extra branch at runtime, you could 
simply use a return in place of the unreachable.  That would definitely 
work (i.e. no pass ordering problem), but the compare and branch would 
be emitted at runtime.

Are you willing to extend the optimizer?  If so, adding a bit of 
metadata and the rules to propagate it in the optimizer would be pretty 
straight forward.  If you need this to work from C code (rather than 
IR), you'd also need to pass the information through clang.

Philip




On 07/10/2014 06:06 AM, Carlo Kok wrote:
> How do I tell the optimizer that the (dereferenced) value of an i8**
> parameter is NULL at the start so that it can eliminate the check?
>
> I have code like:
>
>       void test2(void** ex) {
>         printf("go\n"); // does not change *ex
>       }
>
>       void call2(void** ex);
>
>       void testeh(void** ex) {
>         // I want to tell the optimizer *ex is null so it can 
> eliminate the
> first if below if test2 is inlined:
>         test2(ex)
>         if (*ex) return;
>         printf("done")
>       }
>
> I tried with llvm.invariant.start/end but that doesn't seem to make any
> difference, the icmp/br seems to stay. Can this be done with the current
> optimizers?
>
> My usecase is exception handling via an out parameter. The contract is 
> that on entry ex always points to a stack position which value holds 
> null.
>
>
> ; ModuleID = 'test.ll'
> target datalayout = "e-m:w-p:32:32-i64:64-f80:32-n8:16:32-S32"
> target triple = "i686-pc-windows-msvc"
>
> @str1 = linkonce_odr unnamed_addr constant [3 x i8] c"go\00",
align 1
> @str2 = linkonce_odr unnamed_addr constant [5 x i8] c"done\00",
align 1
>
> define void @inlineeh(i8** nocapture readnone %ex) {
>     %1 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds 
> ([3 x
> i8]* @str1, i32 0, i32 0))
>     ret void
> }
>
> declare i32 @printf(i8* nocapture readonly, ...) #0
>
> define void @testeh(i8** nocapture %ex) #0 {
>     %1 = bitcast i8** %ex to i8*
>     %2 = tail call {}* @llvm.invariant.start(i64 4, i8* %1)
>     tail call void @llvm.invariant.end({}* %2, i64 4, i8* %1)
>     %3 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds 
> ([3 x
> i8]* @str1, i32 0, i32 0))
>     %4 = load i8** %ex, align 4
>     %5 = icmp eq i8* %4, null
>     br i1 %5, label %6, label %8
>
> ; <label>:6                                       ; preds = %0
>     %7 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds 
> ([5 x
> i8]* @str2, i32 0, i32 0))
>     br label %8
>
> ; <label>:8                                       ; preds = %0, %6
>     ret void
> }
>
> declare void @llvm.invariant.end({}*, i64, i8* nocapture)
> declare {}* @llvm.invariant.start(i64, i8* nocapture)
>
>
>
>

On Thu, Jul 10, 2014 at 11:29 AM, Philip Reames
<listmail at philipreames.com> wrote:
> Hm, I don't know of an explicit way in the IR to do this.  If anyone
else
> does, feel free to chime in.
>
> One approach would be to add a branch at the beginning of the function to
an
> unreachable block.  If you're testeh function started with:
> if( *ex != null) llvm_unreachable();
>
> You might get lucky and have the GVN or EarlyCSE propagate the null value.
> You're going to run into pass ordering problems here though.  I suspect
we'd
> drop the unreachable block before GVN runs.
Yep - SimplifyCFG does a great job of ripping branches to unreachable
out pretty early on.
> I looked at something like this
> previously:
>
http://www.philipreames.com/Blog/2014/02/15/tweaking-llvm-to-exploit-assumex/
>
> If you're willing to tolerate an extra branch at runtime, you could
simply
> use a return in place of the unreachable.  That would definitely work (i.e.
> no pass ordering problem), but the compare and branch would be emitted at
> runtime.
>
> Are you willing to extend the optimizer?  If so, adding a bit of metadata
> and the rules to propagate it in the optimizer would be pretty straight
> forward.  If you need this to work from C code (rather than IR), you'd
also
> need to pass the information through clang.
>
> Philip
>
>
>
>
>
> On 07/10/2014 06:06 AM, Carlo Kok wrote:
>>
>> How do I tell the optimizer that the (dereferenced) value of an i8**
>> parameter is NULL at the start so that it can eliminate the check?
>>
>> I have code like:
>>
>>       void test2(void** ex) {
>>         printf("go\n"); // does not change *ex
>>       }
>>
>>       void call2(void** ex);
>>
>>       void testeh(void** ex) {
>>         // I want to tell the optimizer *ex is null so it can eliminate
>> the
>> first if below if test2 is inlined:
>>         test2(ex)
>>         if (*ex) return;
>>         printf("done")
>>       }
>>
>> I tried with llvm.invariant.start/end but that doesn't seem to make
any
>> difference, the icmp/br seems to stay. Can this be done with the
current
>> optimizers?
>>
>> My usecase is exception handling via an out parameter. The contract is
>> that on entry ex always points to a stack position which value holds
null.
>>
>>
>> ; ModuleID = 'test.ll'
>> target datalayout =
"e-m:w-p:32:32-i64:64-f80:32-n8:16:32-S32"
>> target triple = "i686-pc-windows-msvc"
>>
>> @str1 = linkonce_odr unnamed_addr constant [3 x i8] c"go\00",
align 1
>> @str2 = linkonce_odr unnamed_addr constant [5 x i8]
c"done\00", align 1
>>
>> define void @inlineeh(i8** nocapture readnone %ex) {
>>     %1 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds
([3
>> x
>> i8]* @str1, i32 0, i32 0))
>>     ret void
>> }
>>
>> declare i32 @printf(i8* nocapture readonly, ...) #0
>>
>> define void @testeh(i8** nocapture %ex) #0 {
>>     %1 = bitcast i8** %ex to i8*
>>     %2 = tail call {}* @llvm.invariant.start(i64 4, i8* %1)
>>     tail call void @llvm.invariant.end({}* %2, i64 4, i8* %1)
>>     %3 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds
([3
>> x
>> i8]* @str1, i32 0, i32 0))
>>     %4 = load i8** %ex, align 4
>>     %5 = icmp eq i8* %4, null
>>     br i1 %5, label %6, label %8
>>
>> ; <label>:6                                       ; preds = %0
>>     %7 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds
([5
>> x
>> i8]* @str2, i32 0, i32 0))
>>     br label %8
>>
>> ; <label>:8                                       ; preds = %0,
%6
>>     ret void
>> }
>>
>> declare void @llvm.invariant.end({}*, i64, i8* nocapture)
>> declare {}* @llvm.invariant.start(i64, i8* nocapture)
>>
>>
>>
>>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev