llvm dev - May 2019 - [Pipeliner] MachinePipeliner TargetInstrInfo hooks need more information?

Hello,

I'm working on integrating the MachinePipeliner.cpp pass into our VLIW
backend, and so far we've managed to get it working with some nice
speedups.
Unlike Hexagon however, our backend doesn't generate hardware loop
instructions and so all our loops are a combination of induction
variables, comparisons and branches. So when it came to implementing
reduceLoopCount for our TargetInstrInfo, we found that we didn't have
enough information from analyzeLoop to reduce the loops. 

Currently the signatures look like this:

   bool analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst,
                    MachineInstr *&CmpInst)

   unsigned TargetInstrInfo::reduceLoopCount(MachineBasicBlock &MBB, 
         MachineInstr *IndVar,
         MachineInstr &Cmp,
         SmallVectorImpl<MachineOperand> &Cond,
         SmallVectorImpl<MachineInstr *> &PrevInsts,
         unsigned Iter,
         unsigned MaxIter) const

Since the condition operands for branching in our architecture are
found on the branch instruction and not the comparison instruction, we
weren't able to populate Cond in reduceLoopCount.

Furthermore, since some loops conditionally branched to exit the loop
whilst others conditionally branched to continue the loop, we sometimes
needed to invert these condition codes. (MachinePipeliner.cpp inserts
branches assuming that the Cond operands are the operands for *exiting*
the loop)

In the end we had to change the signatures to pass around a bit more
information:

    bool analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst,
                     MachineInstr *&CmpInst, MachineInstr *&BranchInst,
                     bool *BranchExits)
    
    unsigned reduceLoopCount(MachineBasicBlock &MBB,
        MachineInstr *IndVar,
        MachineInstr &Cmp,
        MachineInstr &Exit,
        bool BranchExits,
        SmallVectorImpl<MachineOperand> &Cond,
        SmallVectorImpl<MachineInstr *> &PrevInsts,
        unsigned Iter,
        unsigned MaxIter)

BranchInst allows us to get the operands required to pass back in Cond,
and BranchExits is set to true whenever the branch exits the loop, so
that we can then invert the condition if it doesn't exit the loop.

Would these changes be desirable upstream? As far as I'm aware Hexagon
doesn't use the IndVar instruction, and just passes along the hardware
loop instruction through CmpInst, so adapting it for this new API was
trivial.

Luke Lau
--------------------------------------------------------------
Intel Research and Development Ireland Limited
Registered in Ireland
Registered Office: Collinstown Industrial Park, Leixlip, County Kildare
Registered Number: 308263


This e-mail and any attachments may contain confidential material for the sole
use of the intended recipient(s). Any review or distribution by others is
strictly prohibited. If you are not the intended recipient, please contact the
sender and delete all copies.

Hi Luke,
The main why the pipeliner only looks for hardware loops on Hexagon is that a
hardware loop instruction requires that the iteration count has been computed
for the loop. In other words, if a loop has been converted to a hardware loop,
then there is a virtual register that holds the iteration count (or the
iteration count is a compile-time constant). For loops where the exit condition
is recalculated at each iteration, determining the iteration count may be
difficult (there is no equivalent of scalar evolution pass for MIR).
If your code can extend the functionality of the pipeliner to such loops, then
your contributions would certainly be welcome.

-Krzysztof

cc: Brendon, who wrote the pipeliner.

________________________________________
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Lau, Luke
via llvm-dev <llvm-dev at lists.llvm.org>
Sent: Friday, May 10, 2019 2:50 AM
To: llvm-dev at lists.llvm.org
Cc: Verma, Saurabh
Subject: [EXT] [llvm-dev] [Pipeliner] MachinePipeliner TargetInstrInfo hooks
need more information?

Hello,

I'm working on integrating the MachinePipeliner.cpp pass into our VLIW
backend, and so far we've managed to get it working with some nice
speedups.
Unlike Hexagon however, our backend doesn't generate hardware loop
instructions and so all our loops are a combination of induction
variables, comparisons and branches. So when it came to implementing
reduceLoopCount for our TargetInstrInfo, we found that we didn't have
enough information from analyzeLoop to reduce the loops.

Currently the signatures look like this:

   bool analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst,
                    MachineInstr *&CmpInst)

   unsigned TargetInstrInfo::reduceLoopCount(MachineBasicBlock &MBB,
         MachineInstr *IndVar,
         MachineInstr &Cmp,
         SmallVectorImpl<MachineOperand> &Cond,
         SmallVectorImpl<MachineInstr *> &PrevInsts,
         unsigned Iter,
         unsigned MaxIter) const

Since the condition operands for branching in our architecture are
found on the branch instruction and not the comparison instruction, we
weren't able to populate Cond in reduceLoopCount.

Furthermore, since some loops conditionally branched to exit the loop
whilst others conditionally branched to continue the loop, we sometimes
needed to invert these condition codes. (MachinePipeliner.cpp inserts
branches assuming that the Cond operands are the operands for *exiting*
the loop)

In the end we had to change the signatures to pass around a bit more
information:

    bool analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst,
                     MachineInstr *&CmpInst, MachineInstr *&BranchInst,
                     bool *BranchExits)

    unsigned reduceLoopCount(MachineBasicBlock &MBB,
        MachineInstr *IndVar,
        MachineInstr &Cmp,
        MachineInstr &Exit,
        bool BranchExits,
        SmallVectorImpl<MachineOperand> &Cond,
        SmallVectorImpl<MachineInstr *> &PrevInsts,
        unsigned Iter,
        unsigned MaxIter)

BranchInst allows us to get the operands required to pass back in Cond,
and BranchExits is set to true whenever the branch exits the loop, so
that we can then invert the condition if it doesn't exit the loop.

Would these changes be desirable upstream? As far as I'm aware Hexagon
doesn't use the IndVar instruction, and just passes along the hardware
loop instruction through CmpInst, so adapting it for this new API was
trivial.

Luke Lau
--------------------------------------------------------------
Intel Research and Development Ireland Limited
Registered in Ireland
Registered Office: Collinstown Industrial Park, Leixlip, County Kildare
Registered Number: 308263


This e-mail and any attachments may contain confidential material for the sole
use of the intended recipient(s). Any review or distribution by others is
strictly prohibited. If you are not the intended recipient, please contact the
sender and delete all copies.
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Hi Luke,

It would be great to see the pipeliner extended to work with non-hardware loops,
and I think it's reasonable, and expected, that the target hooks require
some changes to support these loops. I know other folks have worked on adding
this support, but that work hasn't been upstreamed. Once you submit a patch
for review, perhaps they can comment on the proposed changes.  I have a couple
of comments.

The values returned by analyzeLoop are target specific, so 'CmpInst'
doesn't have to be a compare instruction. I think it could be the branch
instruction in your architecture, if the compare is folded into the branch. The
value is used by the reduceLoopCount function. Perhaps we just need to rename
the variable? Or, does your architecture have both a compare and branch, and
both are needed?  The values in populated in Cond should be similar to how
similar branches are processed by analyzeBranch().  Your proposed change for the
loop exit direction looks good to me, since the existing code does assume that
the true condition branches to the top of the loop.

Thanks,
Brendon

-----Original Message-----
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Krzysztof
Parzyszek via llvm-dev
Sent: Saturday, May 11, 2019 12:55 PM
To: llvm-dev at lists.llvm.org
Cc: Brendon Cahoon <bcahoon at quicinc.com>
Subject: Re: [llvm-dev] [Pipeliner] MachinePipeliner TargetInstrInfo hooks need
more information?

Hi Luke,
The main why the pipeliner only looks for hardware loops on Hexagon is that a
hardware loop instruction requires that the iteration count has been computed
for the loop. In other words, if a loop has been converted to a hardware loop,
then there is a virtual register that holds the iteration count (or the
iteration count is a compile-time constant). For loops where the exit condition
is recalculated at each iteration, determining the iteration count may be
difficult (there is no equivalent of scalar evolution pass for MIR).
If your code can extend the functionality of the pipeliner to such loops, then
your contributions would certainly be welcome.

-Krzysztof

cc: Brendon, who wrote the pipeliner.

________________________________________
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Lau, Luke
via llvm-dev <llvm-dev at lists.llvm.org>
Sent: Friday, May 10, 2019 2:50 AM
To: llvm-dev at lists.llvm.org
Cc: Verma, Saurabh
Subject: [EXT] [llvm-dev] [Pipeliner] MachinePipeliner TargetInstrInfo hooks
need more information?

Hello,

I'm working on integrating the MachinePipeliner.cpp pass into our VLIW
backend, and so far we've managed to get it working with some nice speedups.
Unlike Hexagon however, our backend doesn't generate hardware loop
instructions and so all our loops are a combination of induction variables,
comparisons and branches. So when it came to implementing reduceLoopCount for
our TargetInstrInfo, we found that we didn't have enough information from
analyzeLoop to reduce the loops.

Currently the signatures look like this:

   bool analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst,
                    MachineInstr *&CmpInst)

   unsigned TargetInstrInfo::reduceLoopCount(MachineBasicBlock &MBB,
         MachineInstr *IndVar,
         MachineInstr &Cmp,
         SmallVectorImpl<MachineOperand> &Cond,
         SmallVectorImpl<MachineInstr *> &PrevInsts,
         unsigned Iter,
         unsigned MaxIter) const

Since the condition operands for branching in our architecture are found on the
branch instruction and not the comparison instruction, we weren't able to
populate Cond in reduceLoopCount.

Furthermore, since some loops conditionally branched to exit the loop whilst
others conditionally branched to continue the loop, we sometimes needed to
invert these condition codes. (MachinePipeliner.cpp inserts branches assuming
that the Cond operands are the operands for *exiting* the loop)

In the end we had to change the signatures to pass around a bit more
information:

    bool analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst,
                     MachineInstr *&CmpInst, MachineInstr *&BranchInst,
                     bool *BranchExits)

    unsigned reduceLoopCount(MachineBasicBlock &MBB,
        MachineInstr *IndVar,
        MachineInstr &Cmp,
        MachineInstr &Exit,
        bool BranchExits,
        SmallVectorImpl<MachineOperand> &Cond,
        SmallVectorImpl<MachineInstr *> &PrevInsts,
        unsigned Iter,
        unsigned MaxIter)

BranchInst allows us to get the operands required to pass back in Cond, and
BranchExits is set to true whenever the branch exits the loop, so that we can
then invert the condition if it doesn't exit the loop.

Would these changes be desirable upstream? As far as I'm aware Hexagon
doesn't use the IndVar instruction, and just passes along the hardware loop
instruction through CmpInst, so adapting it for this new API was trivial.

Luke Lau
--------------------------------------------------------------
Intel Research and Development Ireland Limited Registered in Ireland Registered
Office: Collinstown Industrial Park, Leixlip, County Kildare Registered Number:
308263


This e-mail and any attachments may contain confidential material for the sole
use of the intended recipient(s). Any review or distribution by others is
strictly prohibited. If you are not the intended recipient, please contact the
sender and delete all copies.
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev