[LLVMdev] Helping the optimizer along (__assume)

[Matthijs Kooijman]

Hi all,

I've been thinking about this issue as well, since I'm working with a
architecture that can do hardware based loops, but only when the loop count is
more than some minimal value. To probably use this, we need some way for the
code to specify that a loop variable has a minimum value.

> Can't you implement __builtin_assume(cond) to codegen to something like:
> 
> 	%cond = i1 ...
> 	br i1 %cond, label %always, label %never
> never:
> 	unreachable
> always:

I've looked into an approach like this as well, but it doesn't quite work. My
approach wasn't to use an unreachable, but simply a return (IIRC). However,
the problems I saw were as follows:
 * If the optimizers are smart enough to actually verify that your assertion
   holds (ie, %cond is provably true), the branch is removed alltogether (or
	 at least %cond is simplified and replaced by true).
	 
	 Now, you might say that if the optimizers are smart enough to prove the
	 condition true, they shouldn't need the assertion in the first place.
	 However, it usually requires quite some reasoning to prove the condition,
	 which is often done in incremental step (sometimes even by different
	 passes).

	 Moreover, not all passes do the same complicated reasoning to prove some
	 property, even though they might benefit from the conclusions. We don't
	 want all passes to do this either, since drawing the same conclusions over
	 and over again is pointless.

	 Also, the code might want to make some assertions which are not provably
	 true, (ie, preconditions on external functions can't be proven until after
	 linking), but can lead to significant optimizations.

 * If the optimizers are not smart enough to verify the assertion, modeling
   such an assertion with a conditional branch instruction will leave the
	 branch instruction in place, and you wil end up with a branch instruction
	 in the resulting code.

The above shows that using normal branches for marking assumptions is not a
very usable strategy. The example above tries to mark the branch as a special
branch by putting in an unreachable instruction. While this should prevent the
branch from showing up in the resulting code, as pointed out the branch gets
eliminated way too early.

One could think of making a new "codegen-unreachable" instruction, which is
counted as unreachable only just before or at codegen. This would help the
branch to stay alive longer, so the optimization passes can use the info it
encodes. However, this still allows the branch to be removed when the
condition can be proven somewhere along the way.

So, to really be able to encode this data, one could think of having an
"assume" intrinsic, i.e.:

	%cond = i1 ...
	call void @llvm.assume( i1 %cond )

Optimization passes won't just delete this, but we could teach codegen that
this intrinsic is not generated into any code. However, this still doesn't
completely solve the problem indicated at the first point above. If %cond is
provably true, we will end up with 

	call void @llvm.assume( i1 true )

which is quite pointless.

I can see two ways of fixing this.
 * Don't use normal IR in the encoding of assumptions, i.e.:

		call void @llvm.assume( [ 7 x i8 ] "p != 0" )

	(Not sure if this is proper IR for encoding a string, but well..)

	The main downside here is that you are limited in which assumptions you can
	encode, which have to be defined quite clearly. On the other hand, when
	encoding using IR, you can encode almost everything, but optimizations will
	still be able to understand a limited amount of it.

	Another downside here is that it is harder to keep assumptions correct when
	the code is transformed.
 * Mark the instructions used for assumptions explicitely, so they won't get
   modified, i.e.:

		%cond = immutable icmp ne i32 %p, 0
		call void @llvm.assume( i1 %cond )

	This probably has lots of other problems (such as preventing other
	transformations from taking place and needing updates to almost every
	optimization pass we have), but seems like it could work.

Are there any other suggestions for solutions? I don't quite like either one
of the two I proposed, but can't think of any others just now.

Gr.

Matthijs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20081023/f4cae1d3/attachment.sig>