[llvm-dev] the root cause is CP, was: A tagged architecture, the elephant in the undef / poison room

[Peter Lawrence via llvm-dev]

> On Jun 16, 2017, at 8:23 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote:
> 
> Hi Peter,
> 
> On Tue, Jun 13, 2017 at 10:27 AM, Peter Lawrence via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>> Here’s what seems to really be going on
>> 
>>        “undef”  ===  models an uninitialized register,  but
> 
> No, it specifically does not.  You yourself have mentioned the reason
> many times -- every "read" of undef returns a new value, which is
> different from, say, %rax with garbage in it.
> 


Sanjoy,
            You’ve hit the nail on the head !, but I don’t think we’ve correctly
identified the root cause of the problem yet.

Rather the problem is with how we incorrectly cse and copy-propagate it:
	x = undef
	if (x == x)
	—————>    this is an illegal copy-propagation   —————>
	if (undef == undef)

If you don’t believe this is illegal then we end up with the absurdity of the
function-inlining example [1], and the argument against the function-inlining
example is so compelling that John decided to drop out of the argument,
IE he gave up because it is indefensible.

Apparently this copy-propagation has been justified by thinking of "undef"
as an IR "constant” and that any optimization you can do to a “constant”
can also be done to “undef” without further thought.

Instead each ‘undef’ should be thought of as a live on entry register, IE an
incoming argument physical register, and “x = undef” cannot be optimized
any more than “x = PhysReg0”, in particular multiple uses of X does not mean
multiple incoming argument registers, and separate instances of “undef”
cannot be equated any more than distinct incoming argument registers.

To the argument that this may create unnecessary register pressure I say
that is a register allocator issue not an IR issue, the register allocator can
and should figure this out and do the right thing.


Peter Lawrence.


[1. this function *always* executes statement S,
	F(a) {
	   If (a == a) S;
	}
   but in llvm if you inline it and “a” happens to be “undef” then nothing can
   be said about whether statement S is executed.  This is indefensible.]










>>        “poison”  ===  turns the entire IR into a tagged architecture
>> 
>> 
>> Is this really the way to go ?
>> 
>> It seems like a odd choice given that none of our current targets
>> are tagged architectures, all of this tagged IR has to somehow be
>> reduced back down to normal target machine instructions.
> 
> No architecture (that I know of) supports PHI nodes either, yet they
> are an enormously useful concept.  Comparing LLVM IR to machine ISAs
> is a mistake -- the mid level IR should be evaluated in terms of how
> well it can do what it is supposed to do, which is enable mid level
> optimizations.  There's a reason why we don't use MCInsts all the way
> through.
> 
> Thanks!
> -- Sanjoy