[LLVMdev] alias set collapse and LICM

[Hal Finkel]

[+Danny]

----- Original Message -----
> From: "Sanjoy Das" <sanjoy at playingwithpointers.com>
> To: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Cc: "Philip Reames" <listmail at philipreames.com>, "Hal Finkel" <hfinkel at anl.gov>, "Chandler Carruth"
> <chandlerc at google.com>
> Sent: Monday, April 27, 2015 4:58:09 PM
> Subject: alias set collapse and LICM
> 
> I'm current facing an issue related to AliasSetTracker/LICM: the
> transitive closure of the alias sets is materially more conservative
> than individual aliasing queries and this conservatism leads to
> generally worse optimization in LICM.
> 
> For instance, consider this module:
> 
> declare i32 @only_reads() readonly
> declare void @escape(i32*, i32*, i32*)
> 
> define void @f(i32 %count) {
>  entry:
>   %a = alloca i32
>   %b = alloca i32
>   %c = alloca i32
>   call void @escape(i32* %a, i32* %b, i32* %c)
>   %enter = icmp sle i32 0, %count
>   br i1 %enter, label %loop, label %exit
> 
>  loop:
>   %idx = phi i32 [ 0, %entry ], [ %idx.inc, %loop ]
>   %idx.inc = add i32 %idx, 1
>   %take.be = icmp slt i32 %idx, %count
> 
>   %a.load = load i32, i32* %a
>   store i32 %a.load, i32* %b
> 
>   %v = call i32 @only_reads()
>   store i32 %v, i32* %c
> 
>   br i1 %take.be, label %loop, label %exit
> 
>  exit:
>   ret void
> }
> 
> BasicAA knows that %a, %b and %c are all pairwise NoAlias, and given
> that, LICM should be able to hoist `%a.load` out of the loop.  That
> does not happen because the read only call to `@only_reads` collapses
> the alias sets for %a, %b and %c into one and so as far as LICM is
> concerned, they all alias each other.  The store to `%b` now
> "clobbers" `%a.load`.

Each alias set currently keeps track of its AccessType (Ref/Mod/ModRef). Maybe we should not collapse Ref access sets with Mod ones?

 -Hal

> 
> One potential fix is to do N^2 alias queries (every mem operation in
> the loop with every other mem operation) before hoisting a load, but
> I
> suspect AliasSetTracker exists mainly to make LICM faster than N^2,
> so
> I'm ruling this solution out.
> 
> The solution I like: have LICM create two AliasSetTracker
> objects.  The first one tracks all memory operations, as the alias
> set
> tracker object does now.  The second one only tracks mods.  When
> hoisting a load we check if any alias set in the mod tracker aliases
> the load location -- if not, the load is okay to hoist to the
> preheader from the data dependence point of view.  In the worst case,
> this is 2x more (than now) work for building the alias sets and no
> more
> extra work when checking if we can hoist a load.
> 
> Before I dive into implementing this, I have a few questions:
> 
>  * is this even the right problem to solve?  Or should I look at
>  other
>    passes for this optimization?
> 
>  * do you think this will be too expensive?  If so, does it make
>  sense
>    to do this only on -O3?`
> 
> -- Sanjoy
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory