llvm dev - Feb 2016 - Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")

Hal Finkel wrote:
 > That summary needs unnecessarily broad. So far we've learned that: a)
There are issues with atomics b) there are issues
 > with a safe-to-speculate attribute we don't yet have c) there might be
issues with folding undefs independent of the
 > previous two items, but we thus-far lack a concrete example. We don't
yet have enough information.


I don't have a good example for (c), but if you go by the textbook "is
a non-deterministic value" definition for undef then

   void foo() available_externally {
     %x = create_undef();
     if (%x) print("X");
   }

is just as problematic as the two atomic loads case.  This isn't a
good example though, since we can specify as part of `undef` s
semantics: "if the program has different observable behavior based on
undef's non-determinism, then it is undefined".  However, if we do
that, we'll get stuck in cases like

   // In C
   void foo() {
     int c;
     if (c) print("X");
     escape(&c);  // escape is an empty function
   }

which I think is not UB in C (is it?), but will boil down to the kind
of IR above.

-- Sanjoy

Couple of other examples:

  void @foo(i32* %ptr) available_externally {
    %discard = load i32, i32* %ptr
  }
  void bar() {
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) available_externally {
  }
  void bar() {
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) available_externally {
  }
  void bar() {
    call @foo(i32* undef) ;; non optimized @foo will crash
  }

  ;; Similar example if @foo was dividing something by an integer
  ;; argument

We've actually seen the above in our VM (though back then we
didn't realize that the problem was more general than the one
case above).

Another one involving `undef` (semantically same as "folding undef",
but different enough to state separately):

  void @foo(i32* %ptr) available_externally {
    store i32 undef, i32* %ptr
  }
  void bar() {
    %val = load i32, i32* %x
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) readonly available_externally {
  }
  void bar() {
    %val = load i32, i32* %x
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) readonly available_externally {
  }
  void bar() {
    call @foo(i32* %x)
    %val = load i32, i32* %x
  }

With a non-optimized @foo, %val can be garbage.


I'll also note we've not really had bug reports (that I'm aware of)
around this issue.  Given that, it is possible that this is a purely
theoretical problem.

-- Sanjoy

A couple things I recall from implementing this in Phoenix:

For LTO -- do your comdat folding as part of the up-front symbol resolution
before invoking the backend (saves compile time too). Then have the linker
ensure that the comdat from the LTO bundle is the winner in the final link step.
That way during LTO you know which method body is going to be in the final
image. May not be as easy in LLVM if you can't merge all the LTO objs into a
single massive obj like we did.

For non-LTO compiles: block bottom-up propagation of facts that depend on
optimization levels -- eg register kills and parameter usage summaries. Allow
other IP information to flow upwards, since at least in our world all
comdat-foldable definitions are supposed to be "equivalent". Requires
some discipline so you are confident you know how information is derived.

We would also error out if foldable definitions did not appear to be equivalent.
I think we at least wrote the code to do some sanity checking. Maybe we never
turned this bit on.

We had real bugs reported before we fixed this properly. One annoying one was
that the comdat winner picked by the linker depended in part on the file path to
the obj, so if you linked the program in different directories, you'd get
different final binaries, and some of them would crash.

-----Original Message-----
From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Sanjoy
Das via llvm-dev
Sent: Thursday, February 25, 2016 9:59 AM
To: Hal Finkel <hfinkel at anl.gov>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Possible soundness issue with available_externally
(split from "RFC: Add guard intrinsics")

Couple of other examples:

  void @foo(i32* %ptr) available_externally {
    %discard = load i32, i32* %ptr
  }
  void bar() {
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) available_externally {
  }
  void bar() {
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) available_externally {
  }
  void bar() {
    call @foo(i32* undef) ;; non optimized @foo will crash
  }

  ;; Similar example if @foo was dividing something by an integer
  ;; argument

We've actually seen the above in our VM (though back then we didn't
realize that the problem was more general than the one case above).

Another one involving `undef` (semantically same as "folding undef",
but different enough to state separately):

  void @foo(i32* %ptr) available_externally {
    store i32 undef, i32* %ptr
  }
  void bar() {
    %val = load i32, i32* %x
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) readonly available_externally {
  }
  void bar() {
    %val = load i32, i32* %x
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) readonly available_externally {
  }
  void bar() {
    call @foo(i32* %x)
    %val = load i32, i32* %x
  }

With a non-optimized @foo, %val can be garbage.


I'll also note we've not really had bug reports (that I'm aware of)
around this issue.  Given that, it is possible that this is a purely theoretical
problem.

-- Sanjoy
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7candya%40microsoft.com%7cf0dc286d1dc04d5daf9408d33e0d7a98%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=ZK9BbJxV6%2bcAQn%2ftdy3%2b%2fHyOA7BR5QclvKO1egIap0w%3d

> On 2016-Feb-25, at 08:33, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> 
> Hal Finkel wrote:
> > That summary needs unnecessarily broad. So far we've learned that:
a) There are issues with atomics b) there are issues
> > with a safe-to-speculate attribute we don't yet have c) there
might be issues with folding undefs independent of the
> > previous two items, but we thus-far lack a concrete example. We
don't yet have enough information.
> 
> 
> I don't have a good example for (c), but if you go by the textbook
"is
> a non-deterministic value" definition for undef then
> 
>  void foo() available_externally {
>    %x = create_undef();
>    if (%x) print("X");
>  }
> 
> is just as problematic as the two atomic loads case.  This isn't a
> good example though, since we can specify as part of `undef` s
> semantics: "if the program has different observable behavior based on
> undef's non-determinism, then it is undefined".  However, if we do
> that, we'll get stuck in cases like
> 
>  // In C
>  void foo() {
>    int c;
>    if (c) print("X");
>    escape(&c);  // escape is an empty function
>  }
> 
> which I think is not UB in C (is it?), but will boil down to the kind
> of IR above.
I'm pretty sure the `if (c)` is UB because it's branching on an
uninitialized
value, which could have a trap representation.

> 
> -- Sanjoy

On Thu, Feb 25, 2016 at 6:35 PM, Duncan P. N. Exon Smith
<dexonsmith at apple.com> wrote:
>>  // In C
>>  void foo() {
>>    int c;
>>    if (c) print("X");
>>    escape(&c);  // escape is an empty function
>>  }
>>
>> which I think is not UB in C (is it?), but will boil down to the kind
>> of IR above.
>
> I'm pretty sure the `if (c)` is UB because it's branching on an
uninitialized
> value, which could have a trap representation.
I am *way* out of my depth here, but what if 'c' was an 'unsigned
char' (and not an 'int')?  Wouldn't that prevent UB, since it is
escaped (cannot be a register variable), and is an 'unsigned char'
(doesn't have a trap representation)?

-- Sanjoy

Hi Sanjoy,

These are both very interesting examples, and demonstrate that the problems
extends beyond function attributes (encompassing dead-argument elimination,
etc.).

I'm beginning to think that the best solution, at least when optimizing for
speed, is the one that David Li suggested: we need to internalize functions that
have been optimized in certain ways (e.g. instructions with potential side
effects are removed). The trick here may be to be as intelligent about this as
possible to minimize the effect on code size. Maybe this is as easy as checking
whether isSafeToSpeculativelyExecute returns false on the deleted instruction?
Perhaps when optimizing for size, we need to forbid such deletions.

Thanks again,
Hal

----- Original Message -----
> From: "Sanjoy Das" <sanjoy at playingwithpointers.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Chandler Carruth" <chandlerc at google.com>,
"llvm-dev" <llvm-dev at lists.llvm.org>, "Philip
Reames"
> <listmail at philipreames.com>, "Duncan P. N. Exon Smith"
<dexonsmith at apple.com>
> Sent: Thursday, February 25, 2016 11:59:27 AM
> Subject: Re: [llvm-dev] Possible soundness issue with available_externally
(split from "RFC: Add guard intrinsics")
> 
> Couple of other examples:
> 
>   void @foo(i32* %ptr) available_externally {
>     %discard = load i32, i32* %ptr
>   }
>   void bar() {
>     call @foo(i32* %x)
>   }
> 
> ==>
> 
>   void @foo(i32* %ptr) available_externally {
>   }
>   void bar() {
>     call @foo(i32* %x)
>   }
> 
> ==>
> 
>   void @foo(i32* %ptr) available_externally {
>   }
>   void bar() {
>     call @foo(i32* undef) ;; non optimized @foo will crash
>   }
> 
>   ;; Similar example if @foo was dividing something by an integer
>   ;; argument
> 
> We've actually seen the above in our VM (though back then we
> didn't realize that the problem was more general than the one
> case above).
> 
> Another one involving `undef` (semantically same as "folding
undef",
> but different enough to state separately):
> 
>   void @foo(i32* %ptr) available_externally {
>     store i32 undef, i32* %ptr
>   }
>   void bar() {
>     %val = load i32, i32* %x
>     call @foo(i32* %x)
>   }
> 
> ==>
> 
>   void @foo(i32* %ptr) readonly available_externally {
>   }
>   void bar() {
>     %val = load i32, i32* %x
>     call @foo(i32* %x)
>   }
> 
> ==>
> 
>   void @foo(i32* %ptr) readonly available_externally {
>   }
>   void bar() {
>     call @foo(i32* %x)
>     %val = load i32, i32* %x
>   }
> 
> With a non-optimized @foo, %val can be garbage.
> 
> 
> I'll also note we've not really had bug reports (that I'm aware
of)
> around this issue.  Given that, it is possible that this is a purely
> theoretical problem.
> 
> -- Sanjoy
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On Thu, Feb 25, 2016 at 9:59 AM, Sanjoy Das
<sanjoy at playingwithpointers.com> wrote:
> Couple of other examples:
>
>   void @foo(i32* %ptr) available_externally {
>     %discard = load i32, i32* %ptr
>   }
>   void bar() {
>     call @foo(i32* %x)
>   }
>
> ==>
>
>   void @foo(i32* %ptr) available_externally {
>   }
>   void bar() {
>     call @foo(i32* %x)
>   }
>
> ==>
>
>   void @foo(i32* %ptr) available_externally {
>   }
>   void bar() {
>     call @foo(i32* undef) ;; non optimized @foo will crash
>   }
>
>   ;; Similar example if @foo was dividing something by an integer
>   ;; argument
>
> We've actually seen the above in our VM (though back then we
> didn't realize that the problem was more general than the one
> case above).
^ This particular case above is already fixed in DeadArgElim:

bool DAE::RemoveDeadArgumentsFromCallers(Function &Fn)
{
  // We cannot change the arguments if this TU does not define the function or
  // if the linker may choose a function body from another TU, even if the
  // nominal linkage indicates that other copies of the function have the same
  // semantics. In the below example, the dead load from %p may not have been
  // eliminated from the linker-chosen copy of f, so replacing %p with undef
  // in callers may introduce undefined behavior.
  //
  // define linkonce_odr void @f(i32* %p) {
  //   %v = load i32 %p
  //   ret void
  // }
  if (!Fn.isStrongDefinitionForLinker())
    return false;

-- Sanjoy