[LSR] ignore profitable chain optimization when instruction number is the major cost

[shchenz]

Summary

isProfitableChain was added based on register number cost. But now, there are some targets like X86/PowerPC taking instruction number as the major cost.

So on these targets, isProfitableChain wrongly eliminates some LSRUse based on register number when collecting chains/LSRUses, these eliminated LSRUse may impact the instruction number a lot in later rate cost phase. Thus we will get a suboptimal loop code sequence.

This patch can make some cpu2017 benchmarks improve on PowerPC.

[steven.zhang]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3097

I am not familiar with the code logic. But it makes more sense to bail out here when the instruction is the major cost.

[shchenz]

add a new target hook isRegisterNumberMajorCost

[shchenz]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3097

agree with your concern here. return early always good for compiling time. But the logic here should be specific for isProfitableChain, it would make more sense to keep it inside isProfitableChain. For example what if we have more than one caller of isProfitableChain function?

[samparker]

llvm/include/llvm/Analysis/TargetTransformInfo.h

619 ↗

(On Diff #299547)

Probably a good idea to including LSR in the name, like the other queries.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

2841

This can potentially interfere with the calls to isProfitableLSRChainElement, which also isn't specifically interested in register uses. It will require more cycles to process but how about moving this to after the for loop below?

[shchenz]

update:
1: modify the new hook name
2: move it after isProfitableLSRChainElement

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

2841

good catch. Updated

[samparker]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

2876

This will still interfere because if any element in the chain is a ProfitableLSRChainElement, we should return true. So the major cost check should only be executing just before we start doing final cost calculation outside of the loop.

[shchenz]

update:
1: put new added hook after isProfitableLSRChainElement for real...

[samparker]

Having separate loops sounds good to me, but please remove the extra conditional before committing. Thanks.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

2865

You don't need this now :)

[shchenz]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

2865

seems we still need this? The following loop does not contain the first element in the chain.

// Return the first increment in the chain.
const_iterator begin() const {
  assert(!Incs.empty());
  return std::next(Incs.begin());
}
const_iterator end() const {
  return Incs.end();
}

[shchenz]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

2865

Ah, I know what you mean, we should change the loop in line 2865 to use Chain.Incs and thus we can delete the first one

[shchenz]

update:
1: merge header element checking into the new loop

[samparker]

Thanks!

[xbolva00]

Do you plan to post patch to use this hook for x86?

@RKSimon @craig.topper

[shchenz]

@jonpa @uweigand FYI as well for SystemZ. SystemZ does not take register number as major cost either.

[jonpa]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

2873

This seems unclear to me - should it be "If register number is *not* the...", or perhaps "*Only* if register..." ?

It would also be a bit more readable to me if the new hook was called "isNumRegsMajorCostOfLSR", since NumRegs is the name for that counter. (And the comment "number of registers").. but maybe that's just me...

[shchenz]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

2873

Appreciate the comments. Addressed in NFC patch https://reviews.llvm.org/rG00e573cadb2791804fd0859d0ee05b27b702e11e

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

static bool isProfitableChain(IVChain &Chain,
                               ScalarEvolution &SE,
                               const TargetTransformInfo &TTI) {
   if (StressIVChain)
     return true;
 
   if (!Chain.hasIncs())
     return false;
 
+  // If instruction is the major cost, we cannot benefit from this profitable
+  // chain which is based on register number.
+  if (InsnsCost.getNumOccurrences() > 0 && InsnsCost)
+    return false;
+
   if (!Users.empty()) {
     LLVM_DEBUG(dbgs() << "Chain: " << *Chain.Incs[0].UserInst << " users:\n";
                for (Instruction *Inst
                     : Users) { dbgs() << "  " << *Inst << "\n"; });
     return false;
   }
   assert(!Chain.Incs.empty() && "empty IV chains are not allowed");
 
   // The chain itself may require a register, so intialize cost to 1.
   int cost = 1;
 
   // A complete chain likely eliminates the need for keeping the original IV in
   // a register. LSR does not currently know how to form a complete chain unless
   // the header phi already exists.
   if (isa<PHINode>(Chain.tailUserInst())
       && SE.getSCEV(Chain.tailUserInst()) == Chain.Incs[0].IncExpr) {
     --cost;
   }
   const SCEV *LastIncExpr = nullptr;
   unsigned NumConstIncrements = 0;
   unsigned NumVarIncrements = 0;
   unsigned NumReusedIncrements = 0;
 
   if (TTI.isProfitableLSRChainElement(Chain.Incs[0].UserInst))
     return true;
 
   for (const IVInc &Inc : Chain) {
     if (TTI.isProfitableLSRChainElement(Inc.UserInst))
       return true;
 
     if (Inc.IncExpr->isZero())
       continue;
 
     // Incrementing by zero or some constant is neutral. We assume constants can
     // be folded into an addressing mode or an add's immediate operand.
     if (isa<SCEVConstant>(Inc.IncExpr)) {
       ++NumConstIncrements;
       continue;
     }
 
     if (Inc.IncExpr == LastIncExpr)
       ++NumReusedIncrements;
     else
for (PHINode &PN : L->getHeader()->phis()) {
     if (!SE.isSCEVable(PN.getType()))
       continue;
 
     Instruction *IncV =
         dyn_cast<Instruction>(PN.getIncomingValueForBlock(L->getLoopLatch()));
     if (IncV)
       ChainInstruction(&PN, IncV, ChainUsersVec);
   }
   // Remove any unprofitable chains.
   unsigned ChainIdx = 0;
   for (unsigned UsersIdx = 0, NChains = IVChainVec.size();
        UsersIdx < NChains; ++UsersIdx) {
     if (!isProfitableChain(IVChainVec[UsersIdx],
                            ChainUsersVec[UsersIdx].FarUsers, SE, TTI))
       continue;
     // Preserve the chain at UsesIdx.
     if (ChainIdx != UsersIdx)

llvm/test/CodeGen/PowerPC/lsr-profitable-chain.ll

 ; CHECK-NEXT:    std 25, -56(1) # 8-byte Folded Spill
 ; CHECK-NEXT:    std 26, -48(1) # 8-byte Folded Spill
 ; CHECK-NEXT:    std 27, -40(1) # 8-byte Folded Spill
 ; CHECK-NEXT:    std 28, -32(1) # 8-byte Folded Spill
 ; CHECK-NEXT:    std 29, -24(1) # 8-byte Folded Spill
 ; CHECK-NEXT:    std 30, -16(1) # 8-byte Folded Spill
 ; CHECK-NEXT:    bge 0, .LBB0_6
 ; CHECK-NEXT:  # %bb.1: # %.preheader
-; CHECK-NEXT:    mulld 11, 8, 5
-; CHECK-NEXT:    mulld 12, 9, 8
-; CHECK-NEXT:    sldi 0, 10, 3
-; CHECK-NEXT:    sldi 11, 11, 3
-; CHECK-NEXT:    sldi 12, 12, 3
-; CHECK-NEXT:    add 11, 3, 11
+; CHECK-NEXT:    addi 30, 5, 1
+; CHECK-NEXT:    addi 29, 5, 3
+; CHECK-NEXT:    addi 28, 5, 2
+; CHECK-NEXT:    mulld 12, 8, 5
+; CHECK-NEXT:    addi 3, 3, 16
+; CHECK-NEXT:    mulld 0, 9, 8
+; CHECK-NEXT:    sldi 11, 10, 3
+; CHECK-NEXT:    mulld 30, 8, 30
+; CHECK-NEXT:    mulld 29, 8, 29
+; CHECK-NEXT:    mulld 8, 8, 28
 ; CHECK-NEXT:    b .LBB0_3
 ; CHECK-NEXT:    .p2align 4
 ; CHECK-NEXT:  .LBB0_2:
 ; CHECK-NEXT:    add 5, 5, 9
-; CHECK-NEXT:    add 11, 11, 12
+; CHECK-NEXT:    add 12, 12, 0
+; CHECK-NEXT:    add 30, 30, 0
+; CHECK-NEXT:    add 29, 29, 0
+; CHECK-NEXT:    add 8, 8, 0
 ; CHECK-NEXT:    cmpd 5, 7
 ; CHECK-NEXT:    bge 0, .LBB0_6
 ; CHECK-NEXT:  .LBB0_3: # =>This Loop Header: Depth=1
 ; CHECK-NEXT:    # Child Loop BB0_5 Depth 2
-; CHECK-NEXT:    sub 30, 5, 10
-; CHECK-NEXT:    cmpd 6, 30
+; CHECK-NEXT:    sub 28, 5, 10
+; CHECK-NEXT:    cmpd 6, 28
 ; CHECK-NEXT:    bge 0, .LBB0_2
 ; CHECK-NEXT:  # %bb.4:
-; CHECK-NEXT:    addi 28, 5, 1
-; CHECK-NEXT:    addi 27, 5, 2
-; CHECK-NEXT:    addi 26, 5, 3
-; CHECK-NEXT:    mulld 29, 5, 8
-; CHECK-NEXT:    sldi 25, 6, 3
-; CHECK-NEXT:    mulld 28, 28, 8
-; CHECK-NEXT:    mulld 27, 27, 8
-; CHECK-NEXT:    mulld 26, 26, 8
-; CHECK-NEXT:    .p2align 5
-; CHECK-NEXT:  .LBB0_5: # Parent Loop BB0_3 Depth=1
-; CHECK-NEXT:    # => This Inner Loop Header: Depth=2
-; CHECK-NEXT:    lfdx 0, 4, 25
-; CHECK-NEXT:    lfdx 1, 11, 25
+; CHECK-NEXT:    add 26, 6, 12
+; CHECK-NEXT:    add 25, 6, 30
 ; CHECK-NEXT:    add 24, 6, 29
-; CHECK-NEXT:    mr 23, 3
-; CHECK-NEXT:    xsadddp 0, 0, 1
+; CHECK-NEXT:    add 23, 6, 8
+; CHECK-NEXT:    sldi 27, 6, 3
+; CHECK-NEXT:    sldi 26, 26, 3
+; CHECK-NEXT:    sldi 25, 25, 3
 ; CHECK-NEXT:    sldi 24, 24, 3
+; CHECK-NEXT:    sldi 23, 23, 3
+; CHECK-NEXT:    add 27, 4, 27
+; CHECK-NEXT:    add 26, 3, 26
+; CHECK-NEXT:    add 25, 3, 25
 ; CHECK-NEXT:    add 24, 3, 24
-; CHECK-NEXT:    lfd 1, 8(24)
+; CHECK-NEXT:    add 23, 3, 23
+; CHECK-NEXT:    .p2align 5
+; CHECK-NEXT:  .LBB0_5: # Parent Loop BB0_3 Depth=1
+; CHECK-NEXT:    # => This Inner Loop Header: Depth=2
+; CHECK-NEXT:    lfd 0, 0(27)
+; CHECK-NEXT:    lfd 1, -16(26)
+; CHECK-NEXT:    add 6, 6, 10
+; CHECK-NEXT:    cmpd 6, 28
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfd 1, 16(24)
+; CHECK-NEXT:    lfd 1, -8(26)
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfd 1, 24(24)
-; CHECK-NEXT:    add 24, 6, 28
-; CHECK-NEXT:    sldi 24, 24, 3
+; CHECK-NEXT:    lfd 1, 0(26)
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfdux 1, 23, 24
-; CHECK-NEXT:    add 24, 6, 27
-; CHECK-NEXT:    sldi 24, 24, 3
+; CHECK-NEXT:    lfd 1, 8(26)
+; CHECK-NEXT:    add 26, 26, 11
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfd 1, 8(23)
+; CHECK-NEXT:    lfd 1, -16(25)
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfd 1, 16(23)
+; CHECK-NEXT:    lfd 1, -8(25)
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfd 1, 24(23)
-; CHECK-NEXT:    mr 23, 3
-; CHECK-NEXT:    lfdux 2, 23, 24
-; CHECK-NEXT:    add 24, 6, 26
-; CHECK-NEXT:    add 6, 6, 10
-; CHECK-NEXT:    sldi 24, 24, 3
-; CHECK-NEXT:    cmpd 6, 30
+; CHECK-NEXT:    lfd 1, 0(25)
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfd 1, 8(23)
-; CHECK-NEXT:    xsadddp 0, 0, 2
+; CHECK-NEXT:    lfd 1, 8(25)
+; CHECK-NEXT:    add 25, 25, 11
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfd 1, 16(23)
+; CHECK-NEXT:    lfd 1, -16(23)
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfd 1, 24(23)
-; CHECK-NEXT:    mr 23, 3
+; CHECK-NEXT:    lfd 1, -8(23)
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfdux 1, 23, 24
+; CHECK-NEXT:    lfd 1, 0(23)
 ; CHECK-NEXT:    xsadddp 0, 0, 1
 ; CHECK-NEXT:    lfd 1, 8(23)
+; CHECK-NEXT:    add 23, 23, 11
+; CHECK-NEXT:    xsadddp 0, 0, 1
+; CHECK-NEXT:    lfd 1, -16(24)
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfd 1, 16(23)
+; CHECK-NEXT:    lfd 1, -8(24)
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    lfd 1, 24(23)
+; CHECK-NEXT:    lfd 1, 0(24)
+; CHECK-NEXT:    xsadddp 0, 0, 1
+; CHECK-NEXT:    lfd 1, 8(24)
+; CHECK-NEXT:    add 24, 24, 11
 ; CHECK-NEXT:    xsadddp 0, 0, 1
-; CHECK-NEXT:    stfdx 0, 4, 25
-; CHECK-NEXT:    add 25, 25, 0
+; CHECK-NEXT:    stfd 0, 0(27)
+; CHECK-NEXT:    add 27, 27, 11
 ; CHECK-NEXT:    blt 0, .LBB0_5
 ; CHECK-NEXT:    b .LBB0_2
 ; CHECK-NEXT:  .LBB0_6:
 ; CHECK-NEXT:    ld 30, -16(1) # 8-byte Folded Reload
 ; CHECK-NEXT:    ld 29, -24(1) # 8-byte Folded Reload
 ; CHECK-NEXT:    ld 28, -32(1) # 8-byte Folded Reload
 ; CHECK-NEXT:    ld 27, -40(1) # 8-byte Folded Reload
 ; CHECK-NEXT:    ld 26, -48(1) # 8-byte Folded Reload