precondition suggestion to LLVM

Hi all,
Is there any way to tell LLVM some additional information about the variables in the code in order to make better optimization?
For example, if my function has a certain precondition (such as x>0) then it will be possible to better optimize the code given that information (which the compiler does not know).
I am new in this field and I don’t know if there are ways to tell the compiler preconditions (such as by using some preprocessing directives).
Thank you in advance,
Niko Zarzani

Hi Niko,

Do you mean branch prediction, i.e. __builtin_expect [1]? Many
compilers support it, I think clang (LLVM's C/C++ frontend) is among
them.

- D.

[1] http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

Clang+LLVM support __builtin_expect *when used directly inside of a
conditional*. This last is an important constraint.

Another way of thinking about it is that Clang+LLVM supports
expressing control flow biases and optimizes based on them. However,
there is no direct support for expressing value range biases or
optimizing based on them. This is largely due to the overall lack of
value range biasing and asserting support in the IR of LLVM.

While __builtin_expect can in theory be used to encode value range
biases, we see it overwhelmingly more often used to express control
flow biases, and that has been the focus of LLVM's profile-guided
optimization efforts.

You may want to check this out:

http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-October/053924.html

and also

http://llvm.org/PR810

- xi

I think that the __builtin_expect() can only to give hints for better performing branch predicitions.
I was thinking about another kind of situation. Usually if I have a function like this (this is only a simple example):

int foo(int x, int y){

if (x > 0 and y>0){
return x*y;
}
else {
return 0;
}

}

and the compiler knows that the precondition of the function are (x > 0 && y>0) then it can compile it by simply consider it:

int foo(int x, int y){

return x*y;

}

I know it could be dangerous because maybe it will not handle unexpected behavior, but I was wondering if by using some directive like a:

#pragma assert( (x > 0 && y>0) ) /* I know it does not exist pragma assert */

maybe by knowing it the compiler may skip branches or optimize computations (for example if the precondition tell that x==0, and there is a sum or multiplication with x as an operand it can simplify them) in the function code.

Thank you for helping me,

Niko Zarzani

Thank you, it was what I really was searching for :slight_smile:

However, I don’t know if I well understood. I’ve find this link in the second link which seemed what i was looking for: http://nondot.org/sabre/LLVMNotes/BuiltinUnreachable.txt .
If I put around the code block (inside my function with precondition (x>0 && y>0)) a contruct like that that use __builtin_unreachable:

int foo(int x, int y){

if(x>0 && y>0){
…function codeblock…
}
{
__builtin_unreachable ();
}

}

I can get the optimization without really having a branch jump in the machine code?
Thank you again,

Niko Zarzani

Thank you, it was what I really was searching for :slight_smile:

However, I don't know if I well understood. I've find this link in the
second link which seemed what i was looking for:
http://nondot.org/sabre/LLVMNotes/BuiltinUnreachable.txt .
If I put around the code block (inside my function with precondition (x>0 &&
>0)) a contruct like that that use __builtin_unreachable:

int foo(int x, int y){

   if(x>0 && y>0){
       ...function codeblock...
   }
   {
      __builtin_unreachable ();
   }

}

I can get the optimization without really having a branch jump in the
machine code?

In theory, yes - in practice, we eliminate unreachable blocks too
early for any real optimization to occur on the basis of this branch
to unreachable. More details here:
http://llvm.org/bugs/show_bug.cgi?id=810

Niko,

There are a number of folks interested in similar things, but to my knowledge nothing has been added to LLVM to explicitly support this use case (yet). Using an unreachable instruction is a good starting point, but as mentioned by David, we prune these too early at this point in time.

If you're interested, I've got a hacky implementation which works around the problem by inserting a dummy function, running all passes, dropping the dummy function, and rerunning optimizations. I just posted the code on github[1], but - fair warning - this is basically untested at this point. I've run a couple of toy examples, but that's about it.

Yours,
Philip Reames

[1] https://github.com/preames/llvm-assume-hack

(Apologies if anyone gets duplicates. Resending as 4.5 hours after sending, I haven't seen this come through.)

Niko,

There are a number of folks interested in similar things, but to my knowledge nothing has been added to LLVM to explicitly support this use case (yet). Using an unreachable instruction is a good starting point, but as mentioned by David, we prune these too early at this point in time.

If you're interested, I've got a hacky implementation which works around the problem by inserting a dummy function, running all passes, dropping the dummy function, and rerunning optimizations. I just posted the code on github[1], but - fair warning - this is basically untested at this point. I've run a couple of toy examples, but that's about it.

Yours,
Philip Reames

[1] https://github.com/preames/llvm-assume-hack