[LLVMdev] [Proposal] Speculative execution of function calls

[Kuperstein, Michael M]

Hello,

Chris requested I start a fresh discussion on this, so, here goes. The previous iterations can be found here (and in follow-ups):

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130722/182590.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-July/064047.html

Cutting to the chase, the goal is to enhance llvm::isSafeToSpeculativelyExecute() to support call instructions.
isSafeToSpeculativelyExecute() is a query that, basically, determines whether it is safe to move an instruction that is executed conditionally into an unconditional context. One common use-case is hoisting loop-invariant instructions out of loops, during loop-invariant code motion.
For example:

int foo(int a, int b, int n)
{
  int sum = 0;
  for(int i = 0; i < n; ++i)
 {
    int temp = a + b;
    sum += temp;
  }
}

Can be transformed into:

int foo(int a, int b, int n)
{
  int sum = 0;
  int temp = a + b;
  for(int i = 0; i < n; ++i)
 {
    sum += temp;
  }
}

Because hoisting the addition is safe.
However, code that looks like this is more problematic:

int bar(int a);

int foo(int n)
{
  int sum = 0;
  for(int i = 0; i < n; ++i)
 {
    int temp = bar(n);
    sum += temp;
  }
}

May not, in general, be transformed into
int foo_bad(int n)
{
  int sum = 0;
  int temp = bar(n);
  for(int i = 0; i < n; ++i)
 {
    sum += temp;
  }
}

The first issue is that bar() may have side effects, in which case this transformation is clearly unsafe.
Unfortunately, even if bar() is marked "readnone, nounwind", this is still not a safe transformation. The problem is that the loop is not guaranteed to have even a single iteration, and even readnone functions may not always be safe to call.
So, if bar() is defined like this:

int bar(int a)
{
  while(a != 0) {}
  return a;
}

Then foo(0) is safe, but foo_bad(0) is an infinite loop.

Similarly, if bar() is defined as:
int bar(int a)
{
  return 1000 / a;
}

Then foo(0) is safe, but foo_bad(0) has undefined behavior.

Unfortunately, right now, there is no way to specify that a function call IS safe to execute under any circumstances. Because of this, llvm::isSafeToSpeculativelyExecute() simply returns false for all Call instructions, except calls to some intrinsics which are special-cased, and are hard-coded into the function.
What I would like to see instead is a function attribute - or a set of function attributes - that would allow isSafeToSpeculativelyExecute() to infer that it may return "true" for a given function call.
This has two main uses:

1)      Intrinsics, including target-dependent intrinsics, can be marked with this attribute - hopefully a lot of intrinsics that do not have explicit side effects and do not rely on global state that is not currently modeled by "readnone" (e.g. rounding mode) will also not have any of the other issues.

2)      DSL Frontends (e.g. OpenCL, my specific domain) will be able to mark library functions they know are safe.
(The optimizer marking user functions as safe seems, to me, like a less likely case)

I see two ways to approach this:

a)      Define a new attribute that says, specifically, that a function is safe to execute speculatively ("speculatable").

b)      Try to define a set of orthogonal attributes that, when all of them are specified, ensure speculative execution is safe, and then add the missing ones.

Option (b) sounds better in theory, but I find it problematic for two reasons - it's not clear both what the precise requirements  for safety are (right now, "I know it when I see it", and I'm not sure I want to set it in stone), and what the granularity of these orthogonal attributes should be. For example, {readnone, nounwind, halting, welldefined} sounds like a good start, but I'm not sure whether "welldefined" is not too much of a catch-all, or whether this set is, in fact, exhaustive. So I'm more inclined towards (a).

I'm attaching a patch that implements option (a) (the same patch from llvm-commits), but feel free to tell me it's rubbish. :-)

Thanks,
   Michael
---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130731/8fabb37c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: speculatable.diff
Type: application/octet-stream
Size: 23140 bytes
Desc: speculatable.diff
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130731/8fabb37c/attachment.obj>