SCCP and undef branches

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

SCCP and undef branches

Nick Lewycky
I found that "undef" was disappearing early into the optimization chain.
SCCP was the culprit, transforming:

  br bool undef, label %T, label %F

into

  br bool true, label %T, label %F

While that sounds like a great optimization, it shouldn't be happening
that early. I've put together a patch which modifies the behaviour of
SCCP so that it preserves undef in those cases.

I had to modify one of the regression tests which was trying to test
IPSCCP on global variables, but was uses undef and expecting the above
transformation to take place. I changed its global from undef to true,
and wrote a new testcase for the undef-related part.

Patch attached. Comments?

Nick Lewycky


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

sccp-branch-undef.patch (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: SCCP and undef branches

Daniel Berlin
Nick Lewycky wrote:

> I found that "undef" was disappearing early into the optimization chain.
> SCCP was the culprit, transforming:
>
>   br bool undef, label %T, label %F
>
> into
>
>   br bool true, label %T, label %F
>
> While that sounds like a great optimization, it shouldn't be happening
> that early.

Uh, why?
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: SCCP and undef branches

Nick Lewycky
Daniel Berlin wrote:

> Nick Lewycky wrote:
>
>>I found that "undef" was disappearing early into the optimization chain.
>>SCCP was the culprit, transforming:
>>
>>  br bool undef, label %T, label %F
>>
>>into
>>
>>  br bool true, label %T, label %F
>>
>>While that sounds like a great optimization, it shouldn't be happening
>>that early.
>
> Uh, why?

It might not always be optimal to replace undef with true at that point.
If the true branch does a lot of work, and the false branch is empty,
and the program is valid either way, you'd rather choose the false
branch. I admit that it's minor (undef isn't supposed to happen a whole
lot anyways), but we should be deciding this sort of thing at link time
where the behaviour of the two branches is guaranteed to be visible.

For some reason I thought that ADCE already did that sort of resolution
on 'br bool undef', but I seem to have mistested. Before anyone applies
this patch, you should probably wait for a patch to the ADCE so that it
removes 'br undef'. In practise, it'll just replace undef with true, so
until someone writes a better replacement, we'll end up par anyways.

Nick
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: SCCP and undef branches

Domagoj Babic
Hi,

Here's something I don't understand... How come that UNDEF can
appear as a branch condition at all? I just can't think of any ways.

If you write something like

fun() {
  int x;
  if (x > 100) {
     ...
  } else {
     ...
  }
}

LLVM generates a boolean temporary that compares (uninitialized)
value of x with 100.

Second, if it already can appear, isn't that a bug that should be
reported by the compiler?

Domagoj

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: SCCP and undef branches

Nick Lewycky
Domagoj Babic wrote:

> Here's something I don't understand... How come that UNDEF can
> appear as a branch condition at all? I just can't think of any ways.
>
> If you write something like
>
> fun() {
>   int x;
>   if (x > 100) {
>      ...
>   } else {
>      ...
>   }
> }
>
> LLVM generates a boolean temporary that compares (uninitialized)
> value of x with 100.

Firstly, "int x" generates an alloca of one int. The use of "x > 100"
then generates a load of that int. The instruction combiner detects that
it's an alloca+load with no intervening store, and replaces it with undef.

Then, the instruction combiner will try to constant fold the setgt
operation with undef, 100 as arguments. That folds into undef. So before
SCCP is run, your example does produce "if (undef)".

> Second, if it already can appear, isn't that a bug that should be
> reported by the compiler?

Almost. If that undef never executes, then there is no bug, but that
depends on run-time conditions. I suppose you could warn about it
anyways, or perhaps even replace such BBs with "unreachable" though that
might alarm too many users.

The right place to check for these sorts of things might be at link/JIT
time if undef usage can't be optimized away as dead code. I'm not sure
users are ready for their linker to be emitting those sorts of errors
though.

Nick
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: SCCP and undef branches

Chris Lattner
In reply to this post by Domagoj Babic
On Wed, 7 Jun 2006, Domagoj Babic wrote:
> Here's something I don't understand... How come that UNDEF can
> appear as a branch condition at all? I just can't think of any ways.

Lots of different ways, e.g.:

fun() {
   _Bool C;
   if (C) { ... }
}

> Second, if it already can appear, isn't that a bug that should be
> reported by the compiler?

That's up to the front-end.  If you turn on enough warnings you should get
one.

At the compiler level, they can occur due to unrealizable code paths (not
necessarily bugs in the user code), so it's useful for the optimizer to
take advantage of it.

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev