alias-aware scheduling

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

alias-aware scheduling

Dan Gohman
Hello,

I did a little experiment modifying LLVM to be able to use alias-analysis
information in scheduling so that independent memory operations may be
reordered.

Attached is a patch which implements this. I copied some routines from
DAGCombiner.cpp for using SDOperands with alias queries; it should
probably be factored out somewhere so the code can be shared. I
reorganized SelectionDAGLowering::getLoadFrom a little, to make it
simpler to use in other contexts.

Also, the patch fixes a bug where SelectionDAG::getLoad and
SelectionDAG::getStore were being called with the wrong arguments, with
a default argument helping to hide it.

I'm interested in any comments or feedback that people might have.

Dan

--
Dan Gohman, Cray Inc. <[hidden email]>

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

patch (12K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: alias-aware scheduling

Evan Cheng-2

On Dec 19, 2006, at 12:13 PM, Dan Gohman wrote:

> Hello,
>
> I did a little experiment modifying LLVM to be able to use alias-
> analysis
> information in scheduling so that independent memory operations may be
> reordered.

I am not sure if it is a good idea to do this at scheduling time.  
LLVM explicitly models control flows dependencies as chain operands.  
This eliminated the need to do a separate edge drawing pass before  
scheduling.

As you have seen there is transformations in dag combiner to  
eliminate the unnecessary chain operands. It's not turned on by  
default. Are you not getting satisfactory results by turning it on?

>
> Attached is a patch which implements this. I copied some routines from
> DAGCombiner.cpp for using SDOperands with alias queries; it should
> probably be factored out somewhere so the code can be shared. I
> reorganized SelectionDAGLowering::getLoadFrom a little, to make it
> simpler to use in other contexts.
>
> Also, the patch fixes a bug where SelectionDAG::getLoad and
> SelectionDAG::getStore were being called with the wrong arguments,  
> with
> a default argument helping to hide it.

Can you be more specific about what the bugs are?

Thanks,

Evan

>
> I'm interested in any comments or feedback that people might have.
>
> Dan
>
> --
> Dan Gohman, Cray Inc. <[hidden email]>
> <patch>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
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: alias-aware scheduling

Chris Lattner
On Tue, 19 Dec 2006, Evan Cheng wrote:
> As you have seen there is transformations in dag combiner to
> eliminate the unnecessary chain operands. It's not turned on by
> default. Are you not getting satisfactory results by turning it on?

The code in the dag combiner does some simple things, but doesn't yet make
use of the AliasAnalysis interface.  We haven't had a chance to pursue it
fully (been distracted with other things) but at the time it wasn't turned
on due to slow compile-time issues.  If the code was adequately throttled
back, I think this wouldn't be an issue.

Independent of approach though, I think it is best to do the
disambiguation before the scheduler.  This allows the dag combiner to take
advantage of information exposed by the disambiguation (e.g. redundant
loads get squashed, exposing arithmetic identities, etc).

Dan, what do you think of this idea?

-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
Reply | Threaded
Open this post in threaded view
|

Re: alias-aware scheduling

Dan Gohman
In reply to this post by Evan Cheng-2
On Tue, Dec 19, 2006 at 01:31:10PM -0800, Evan Cheng wrote:

>
> On Dec 19, 2006, at 12:13 PM, Dan Gohman wrote:
>
> > Hello,
> >
> > I did a little experiment modifying LLVM to be able to use alias-
> > analysis
> > information in scheduling so that independent memory operations may be
> > reordered.
>
> I am not sure if it is a good idea to do this at scheduling time.  
> LLVM explicitly models control flows dependencies as chain operands.  
> This eliminated the need to do a separate edge drawing pass before  
> scheduling.
>
> As you have seen there is transformations in dag combiner to  
> eliminate the unnecessary chain operands. It's not turned on by  
> default. Are you not getting satisfactory results by turning it on?

Oh, I see now that I misunderstood what the DAGCombiner was doing. The patch
I posted attempts to avoid unnecessary chain operands during the construction
of the DAG, while the DAGCombiner code works by cleaning up chain operands in
a separate pass. It looks like the end result is pretty similar.

> > Attached is a patch which implements this. I copied some routines from
> > DAGCombiner.cpp for using SDOperands with alias queries; it should
> > probably be factored out somewhere so the code can be shared. I
> > reorganized SelectionDAGLowering::getLoadFrom a little, to make it
> > simpler to use in other contexts.
> >
> > Also, the patch fixes a bug where SelectionDAG::getLoad and
> > SelectionDAG::getStore were being called with the wrong arguments,  
> > with
> > a default argument helping to hide it.
>
> Can you be more specific about what the bugs are?

Sure. SelectionDAG::getStore and getLoad are declared like this:

  SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr,
                    const Value *SV, int SVOffset, bool isVolatile=false);

  SDOperand getStore(SDOperand Chain, SDOperand Val, SDOperand Ptr,
                     const Value *SV, int SVOffset, bool isVolatile=false);

In SelectionDAGISel.cpp in SelectionDAGLowering::getLoadFrom and
SelectionDAGLowering::visitStore they are called like this:

    L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, isVolatile);

  DAG.setRoot(DAG.getStore(getRoot(), Src, Ptr, I.getOperand(1),
                           I.isVolatile()));

The isVolatile arguments are being passed to the SVOffset parameters.

Dan

--
Dan Gohman, Cray Inc. <[hidden email]>
_______________________________________________
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: alias-aware scheduling

Evan Cheng-2
>
>>> Attached is a patch which implements this. I copied some routines  
>>> from
>>> DAGCombiner.cpp for using SDOperands with alias queries; it should
>>> probably be factored out somewhere so the code can be shared. I
>>> reorganized SelectionDAGLowering::getLoadFrom a little, to make it
>>> simpler to use in other contexts.
>>>
>>> Also, the patch fixes a bug where SelectionDAG::getLoad and
>>> SelectionDAG::getStore were being called with the wrong arguments,
>>> with
>>> a default argument helping to hide it.
>>
>> Can you be more specific about what the bugs are?
>
> Sure. SelectionDAG::getStore and getLoad are declared like this:
>
>   SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr,
>                     const Value *SV, int SVOffset, bool  
> isVolatile=false);
>
>   SDOperand getStore(SDOperand Chain, SDOperand Val, SDOperand Ptr,
>                      const Value *SV, int SVOffset, bool  
> isVolatile=false);
>
> In SelectionDAGISel.cpp in SelectionDAGLowering::getLoadFrom and
> SelectionDAGLowering::visitStore they are called like this:
>
>     L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, isVolatile);
>
>   DAG.setRoot(DAG.getStore(getRoot(), Src, Ptr, I.getOperand(1),
>                            I.isVolatile()));
>
> The isVolatile arguments are being passed to the SVOffset parameters.

Ah, good catch. I'll fix this. Thanks.

Evan

>
> Dan
>
> --
> Dan Gohman, Cray Inc. <[hidden email]>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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