[LLVMdev] [cfe-dev] Clang devirtualization proposal

[Sanjoy Das]

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
else.

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