user-guided speculative precomputation? (my wacky ia64 idea)

[Duraid Madina]

Daniel Jacobowitz wrote:
> On Tue, Apr 06, 2004 at 09:52:51PM -0400, James Morrison wrote:
> 
>>Duraid Madina <duraid@octopus.com.au> writes:
>>
>>>This #pragma would be added to code such as (taken from
>>>http://www.intel.com/technology/itj/2002/volume06issue01/art03_specprecomp/p06_xeon.htm
>>>)
>>>
>>>{
>>>	n = NodeArray[0];
>>>	while(n && remaining)
>>>	{
>>>		doSomeWork();
>>>#pragma delinquent_load
>>>		n->i = n->next->j + n->next->k + n->next->l;
>>>		n = n->next;
>>>		remaining--;
>>>	}
>>>}
>>>
>>
>> I'm not sure if I should be scared by this example or put it up to lazyness.
>>However, n is going to be compared each time we go through the loop even
>>though it is only supposed to be tested once.  If n is ever 0 at the top of
>>the loop, after executing the loop, then a segfault would have already occured.
>>I don't suppose it's possible to optimize this, is it?
> 
> 
> Eh, you're incorrect.  Note the n = n->next at the bottom of the loop.

The code isn't clean (stick if()s in or whatever makes you happy), the 
point is just to demonstrate the kind of pointer thrashing code that 
speculative precomputation attacks which OoO does not. Which leads me to 
wonder:

> In general, if the circumstance you're describing had actually occured
> in this example - yes, I believe that at least tree-ssa or lno could
> optimize this.  There would be a non-null marker on the dereferenced
> pointer, which would reach a PHI at the top of the loop.

What exactly would tree-ssa or lno _do_? Are there opportunities to 
insert prefetches (I mean loads for the purpose of bringing stuff into 
cache ahead of time, not deliberate prefetch opcodes) far enough before 
the accesses? You'd want to be at least hundreds of cycles ahead here, 
perhaps >300 or so.

Basically, duplicating pointer computation and reads seems to be a big 
win if you can do it far enough in advance (and if it is localised 
enough that you don't blow out your instruction cache). It seems that 
such code is not uncommon in "the real world". And while it has the 
biggest impact on in-order machines such as current Itanium CPUs, there 
are times (as described in the HPCA paper) where OoO and spec. pre-comp 
are actually complementary, so it could be a worthwhile optimization to 
think about at the tree-ssa level, and applicable to a number of 
different architectures.

Any comments? I'm no GCC expert so I'd be very glad to hear from those 
who are..

	Duraid