[LLVMdev] [cfe-dev] Clang devirtualization proposal

Sanjoy Das sanjoy at playingwithpointers.com
Mon Aug 3 00:24:41 PDT 2015

On Sat, Aug 1, 2015 at 2:05 PM, Sanjoy Das
<sanjoy at playingwithpointers.com> wrote:
>> The trouble is that we want to express ideas like "at this call site, but
>> not others, I know that this call will not mutate state through this
>> pointer". We can't express that with the llvm type system we have today.
> Yes; to do that we'll effectively have to introduce some form of
> quantification.
> IOW: we'd have to have 4x the number of pointer types we have today --
> each pointer type should be quantifiable with `noaccess`, `read`,
> `write` and `readwrite` (the second one may not be very useful if we
> do not want to support memory with only `PROT_WRITE`).
> Functions and other consumers types would then have to be modified to
> allow universal (and other forms of?) quantification.  I should be able to
> write a function `@calc` of the type:

I'm not going to derail this thread further, except this one last mail
** (we can talk off list or on another thread if this looks
interesting to you): what I said about quantification won't work
directly -- we'll have problems with pointer comparison for starters.
For instance, if we have a function of type

forall $domain in { noaccess, read, write, readwrite }, forall
$domain2 in { noaccess, read, write, readwrite }: (i8* $domain, i8*
$domain2) -> i32

that wants to compare its first two arguments, then such a comparison
will be well typed only if both $domain and $domain2 are same.  In
other words, only 4 out of the sixteen possible instantiations will be
well typed, so the quantification is not really forall but something

But I don't see any direct, incremental way to make the current
function argument "readonly" consistent.  Semantically, we'd like to
say that programs that store through readonly *SSA values* are
undefined, but unless we track some extra information at runtime,
there is no way to tell if a store to a location happened through
readonly SSA value, or through a normal, read-write SSA value that
happened to evaluate to something that a readonly SSA value also
evaluates to.

For instance, here is another example that's problematic:

define void @f(i8* readonly %ro) {
 i8* %rw = some_computation()
 %ptr = select condition, %ro, %rw;

  ;; work

  *(%ptr) = 42

There is no way to know if the store has UB or not without keeping
track of condition till the store.  If the select was instead was
br-phi then we'd have to manufacture a value to keep track what %ptr
is.  Note that %rw can be == %ro, so you cannot just inspecting the
value of %ptr is not enough.

In fact, with readonly, I think mem2reg is also problematic:

define void @f(i8* readonly %ro) {
 %t = alloca
 store %ro to %t

 %ptr = load %t
  store 24 to %ptr

The store does not happen through the pointer argument, so the above
program is well defined.  But it becomes undefined after mem2reg
(unless it has special handling for this situation).

** it always is "one last mail" :)

-- Sanjoy

More information about the llvm-dev mailing list