alias-aware scheduling

Project Infrastructure LLVM Dev List Archives
1

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

patch (11.8 KB)

2

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

3

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

4

> 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

5

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