Loop optimisation with identical counters

[David Peixotto]

On Nov 5, 2010, at 7:55 PM, Roman Leshchinskiy wrote:

> On 06/11/2010, at 00:28, David Peixotto wrote:
> 
>> Yes, the LLVM code has Sp, Hp, Base all annotated as noalias. I believe that Sp, Hp, and Base should never alias, but a (boxed) R1 should always alias with either Sp or Hp. I had a hard time determining exactly how LLVM uses the noalias annotation, but playing with opt -print-alias-sets I saw that Sp was a MayAlias with the pointers derived from R1. I would guess that casting an int to a pointer (like we do for R1) makes that pointer MayAlias with everything regardless of the noalias annotation.
> 
> Are you sure about R1 aliasing Sp? AFAIK, R1 points to a closure on the heap, not to a stack location. That is, it can alias pointers on the stack or Hp but it can't alias the Sp itself. I don't think Sp can be aliased by anything outside of the garbage collector.
> 
> Perhaps we shouldn't mark Hp as noalias, though.

Well, I'm not sure about R1 aliasing with Sp. I thought that there could be some cases where closures are allocated on the stack, but I could be wrong. I think the stack should still be reachable by the garbage collector though. Can someone more familiar with GHC internals say whether R1 could point to the stack as well as the heap?

> 
>>> But shouldn't it just promote stack locations to registers?
>> 
>> Yes, LLVM can and will promote the stack locations to registers, but since it doesn't know that Sp is really a stack, it is difficult for it to tell when it can avoid the writes back to the stack even though *we* know they will not be visible once the function call returns.
> 
> Right, I meant GHC stack locations. Let me rephrase my question: shouldn't it just promote array locations to registers?

Yes, it should promote array locations to (virtual) registers. I was mentioning the stack because I was thinking of something like this:

x = Sp[0]
x = x + 1
Sp[0] = x
Sp = Sp - 4
return x

where x is a stack allocated parameter. LLVM has no way to know that the write back to the stack (Sp[0] = x) is redundant because it sees Sp as an arbitrary pointer. We know that write is redundant because the stack space is dealloacated before returning x.

> 
>> It may profitable to write our own alias analysis pass for LLVM that encodes our knowledge of what can alias in the GHC world view. It wouldn't be useful for other LLVM clients, but might be a good option for us.
> 
> Actually, I think our aliasing properties should be fairly close to those of, say, Java. I wonder how LLVM deals with those.

That's a good question. I don't think LLVM supports type-based alias analysis which makes it much easier to disambiguate pointers in the Java world. Perhaps type information could help the GHC back end with alias analysis as well.

> 
>> Yeah, I'm generally very impressed with what LLVM is able to do with the code from GHC. Any help we can give it will just make it that much better!
> 
> I have to say I'm slightly disappointed with what LLVM does with tight loops generated by GHC. That's not necessarily LLVM's fault, you are quite right that we should probably give it more information.
> 

Yes, the more that Haskell loops look like the kind of loops that LLVM is accustomed to seeing the better it should be at optimizing them.

-David