[Reassociate] [PowerPC] stop common out mul factors if fma is preferred on target

[shchenz]

Summary

For the case A * B + A * C, now, reassociate pass(function OptimizeAdd) will change it to A * (B + C) to save one mul as A is a common mul factor .

But transformation like above has no benefit at all on PowerPC target. In fact, if target prefers fma, it generates worse IR.

Because on PowerPC target:
A * B + A * C can be generated as fma(fmul(A,B), A, C);
A * (B + C) can be generated as fmul(A, fadd(B, C));

fma, fmul, fadd, fsub all have same latency on PowerPC arch, so no cpu cycle benefit.
Reducing number of mul also makes number of fma reduce. So this is not a benefit transformation on PowerPC.

This patch tries to bail out this opt early to expose more fma folding opportunities and save some compile time on PowerPC target.

[lebedev.ri]

(can you please maybe spellcheck both the patch description and the wording within the patch? it is really hard to read)

I'm not really sure this is the way forward.

1. This is a target-agnostic pass, it we add arbitrary restrictions it will likely miss some intended transforms
2. As usual, just preventing some transform is not the solution, because you can still have "bad" input that will still be lowered badly

IOW,

1. why not reverse this, as usual, in DAGCombine
2. this needs something like D67383 Tree-Height-Reduction, i guess, for more general reverse transform

[shchenz]

In D85504#2202000, @lebedev.ri wrote:

(can you please maybe spellcheck both the patch description and the wording within the patch? it is really hard to read)

Done

I'm not really sure this is the way forward.

1. This is a target-agnostic pass, it we add arbitrary restrictions it will likely miss some intended transforms

Could you be more specific? I verified this change on PowerPC for some benchmarks, no degradation found.

2. As usual, just preventing some transform is not the solution, because you can still have "bad" input that will still be lowered badly

Agree. But if we know that one transformation has no benefit at all or it has a negative impact on some specific targets, should we stop the transformation on these targets? Reversing the transformations back in later pass will make compiler spend compiling time both on the harmful transformations and on the reversed transformations? also I am worried about the feasibility of reversing this "complex" transformation in later pass like DAGCombine...

[lebedev.ri]

I'm not sure why i'm added as a reviewer on this patch, i don't work on ppc, i never used it, and i never really worked on that pass.

In D85504#2202066, @shchenz wrote:

In D85504#2202000, @lebedev.ri wrote:

(can you please maybe spellcheck both the patch description and the wording within the patch? it is really hard to read)

Done

I'm not really sure this is the way forward.

1. This is a target-agnostic pass, it we add arbitrary restrictions it will likely miss some intended transforms

Could you be more specific? I verified this change on PowerPC for some benchmarks, no degradation found.

Perhaps something like a*b * c*d + e*f * c*d, surely it should be (a*b + e*f) * c * d,
but won't this patch keep it as a*b*c*d + e*f*c*d?

2. As usual, just preventing some transform is not the solution, because you can still have "bad" input that will still be lowered badly

Agree. But if we know that one transformation has no benefit at all or it has a negative impact on some specific targets, should we stop the transformation on these targets? Reversing the transformations back in later pass will make compiler spend compiling time both on the harmful transformations and on the reversed transformations? also I am worried about the feasibility of reversing this "complex" transformation in later pass like DAGCombine...

llvm/lib/Transforms/Scalar/Reassociate.cpp

1500

So we also prevent the transform for integers now?
But there's no FMA for them?

[shchenz]

Good catch for the a*b * c*d + e*f * c*d case, Roman. That's a degradation after this patch. Thanks for your good review. ^-^

[spatel]

The reassociate pass (like instcombine) is supposed to be a target-independent canonicalization pass:

  // This pass reassociates commutative expressions in an order that is designed
  // to promote better constant propagation, GCSE, LICM, PRE, etc.

So it's intentionally avoiding using TTI/TLI and trying not to do all forms of reassociation. As Roman mentioned, see D67383 as an example of a possible TTI-aware reassociation pass.

So either we need to reverse this in DAGCombine and/or PPC-specific codegen, or we need to make an argument that the canonicalization does not make sense in general (for FP only?).

[nemanjai]

There seems to be some (weak) correlation between this and https://reviews.llvm.org/D84309 which I am reworking to remove it from canonicalization. It may be worth looking into whether we can catch both issues in CGP.

[shchenz]

Thanks @spatel @nemanjai for your comments. So it should be a common-sense that we should not add TTI/TLI hook inside Reassociate Pass which was already kindly pointed out by @lebedev.ri . I have learned this now ^_^.
I will investigate all the suggested places to do the reversal (DAGCombine, other PPC specific pass or CGP) later.

[shchenz]

we will use other solution for this issue.

llvm/include/llvm/Analysis/TargetTransformInfo.h

public:
   /// Ty2. e.g. On x86 it's free to truncate a i32 value in register EAX to i16
   /// by referencing its sub-register AX.
   bool isTruncateFree(Type *Ty1, Type *Ty2) const;
 
   /// Return true if it is profitable to hoist instruction in the
   /// then/else to before if.
   bool isProfitableToHoist(Instruction *I) const;
 
+  /// Return true if it is profitable to generate fma instructions.
+  bool isProfitableToGenerateFMA(Instruction *I) const;
+
   bool useAA() const;
 
   /// Return true if this type is legal.
   bool isTypeLegal(Type *Ty) const;
 
   /// Return true if switches should be turned into lookup tables for the
   /// target.
   bool shouldBuildLookupTables() const;
public:
   virtual bool hasVolatileVariant(Instruction *I, unsigned AddrSpace) = 0;
   virtual bool prefersVectorizedAddressing() = 0;
   virtual int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                    int64_t BaseOffset, bool HasBaseReg,
                                    int64_t Scale, unsigned AddrSpace) = 0;
   virtual bool LSRWithInstrQueries() = 0;
   virtual bool isTruncateFree(Type *Ty1, Type *Ty2) = 0;
   virtual bool isProfitableToHoist(Instruction *I) = 0;
+  virtual bool isProfitableToGenerateFMA(Instruction *I) = 0;
   virtual bool useAA() = 0;
   virtual bool isTypeLegal(Type *Ty) = 0;
   virtual bool shouldBuildLookupTables() = 0;
   virtual bool shouldBuildLookupTablesForConstant(Constant *C) = 0;
   virtual bool useColdCCForColdCall(Function &F) = 0;
   virtual unsigned getScalarizationOverhead(VectorType *Ty,
                                             const APInt &DemandedElts,
                                             bool Insert, bool Extract) = 0;
public:
   }
   bool LSRWithInstrQueries() override { return Impl.LSRWithInstrQueries(); }
   bool isTruncateFree(Type *Ty1, Type *Ty2) override {
     return Impl.isTruncateFree(Ty1, Ty2);
   }
   bool isProfitableToHoist(Instruction *I) override {
     return Impl.isProfitableToHoist(I);
   }
+  bool isProfitableToGenerateFMA(Instruction *I) override {
+    return Impl.isProfitableToGenerateFMA(I);
+  }
   bool useAA() override { return Impl.useAA(); }
   bool isTypeLegal(Type *Ty) override { return Impl.isTypeLegal(Ty); }
   bool shouldBuildLookupTables() override {
     return Impl.shouldBuildLookupTables();
   }
   bool shouldBuildLookupTablesForConstant(Constant *C) override {
     return Impl.shouldBuildLookupTablesForConstant(C);
   }

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
     return -1;
   }
 
   bool LSRWithInstrQueries() { return false; }
 
   bool isTruncateFree(Type *Ty1, Type *Ty2) { return false; }
 
   bool isProfitableToHoist(Instruction *I) { return true; }
+  bool isProfitableToGenerateFMA(Instruction *I) { return false; }
 
   bool useAA() { return false; }
 
   bool isTypeLegal(Type *Ty) { return false; }
 
   bool shouldBuildLookupTables() { return true; }
   bool shouldBuildLookupTablesForConstant(Constant *C) { return true; }
 

llvm/include/llvm/CodeGen/BasicTTIImpl.h

public:
   bool isTruncateFree(Type *Ty1, Type *Ty2) {
     return getTLI()->isTruncateFree(Ty1, Ty2);
   }
 
   bool isProfitableToHoist(Instruction *I) {
     return getTLI()->isProfitableToHoist(I);
   }
 
+  bool isProfitableToGenerateFMA(Instruction *I) {
+    return getTLI()->isProfitableToGenerateFMA(I);
+  }
+
   bool useAA() const { return getST()->useAA(); }
 
   bool isTypeLegal(Type *Ty) {
     EVT VT = getTLI()->getValueType(DL, Ty);
     return getTLI()->isTypeLegal(VT);
   }
 
   int getGEPCost(Type *PointeeType, const Value *Ptr,

llvm/include/llvm/CodeGen/TargetLowering.h

virtual bool allowTruncateForTailCall(Type *FromTy, Type *ToTy) const {
     return false;
   }
 
   virtual bool isTruncateFree(EVT FromVT, EVT ToVT) const {
     return false;
   }
 
   virtual bool isProfitableToHoist(Instruction *I) const { return true; }
+  virtual bool isProfitableToGenerateFMA(Instruction *I) const { return false; }
 
   /// Return true if the extension represented by \p I is free.
   /// Unlikely the is[Z|FP]ExtFree family which is based on types,
   /// this method can use the context provided by \p I to decide
   /// whether or not \p I is free.
   /// This method extends the behavior of the is[Z|FP]ExtFree family.
   /// In other words, if is[Z|FP]Free returns true, then this method
   /// returns true as well. The converse is not true.

llvm/include/llvm/Transforms/Scalar/Reassociate.h

 // (starting at 2), which effectively gives values in deep loops higher rank
 // than values not in loops.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
 #define LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
 
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
 #include <deque>
 
 namespace llvm {
 
 class APInt;
 class BasicBlock;
struct PairMapValue {
     bool isValid() const { return Value1 && Value2; }
   };
   DenseMap<std::pair<Value *, Value *>, PairMapValue> PairMap[NumBinaryOps];
 
   bool MadeChange;
 
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
+  bool runImpl(Function &F, const TargetTransformInfo *TTI);
 
 private:
   void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
   unsigned getRank(Value *V);
   void canonicalizeOperands(Instruction *I);
   void ReassociateExpression(BinaryOperator *I);
   void RewriteExprTree(BinaryOperator *I,
                        SmallVectorImpl<reassociate::ValueEntry> &Ops);
private:
   Value *RemoveFactorFromExpression(Value *V, Value *Factor);
   void EraseInst(Instruction *I);
   void RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts);
   void OptimizeInst(Instruction *I);
   Instruction *canonicalizeNegFPConstantsForOp(Instruction *I, Instruction *Op,
                                                Value *OtherOp);
   Instruction *canonicalizeNegFPConstants(Instruction *I);
   void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT);
+  const TargetTransformInfo *TTI;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H

llvm/lib/Analysis/TargetTransformInfo.cpp

 bool TargetTransformInfo::isTruncateFree(Type *Ty1, Type *Ty2) const {
   return TTIImpl->isTruncateFree(Ty1, Ty2);
 }
 
 bool TargetTransformInfo::isProfitableToHoist(Instruction *I) const {
   return TTIImpl->isProfitableToHoist(I);
 }
 
+bool TargetTransformInfo::isProfitableToGenerateFMA(Instruction *I) const {
+  return TTIImpl->isProfitableToGenerateFMA(I);
+}
+
 bool TargetTransformInfo::useAA() const { return TTIImpl->useAA(); }
 
 bool TargetTransformInfo::isTypeLegal(Type *Ty) const {
   return TTIImpl->isTypeLegal(Ty);
 }
 
 bool TargetTransformInfo::shouldBuildLookupTables() const {
   return TTIImpl->shouldBuildLookupTables();

llvm/lib/Target/PowerPC/PPCISelLowering.h

public:
     bool isFMAFasterThanFMulAndFAdd(const Function &F, Type *Ty) const override;
 
     /// isProfitableToHoist - Check if it is profitable to hoist instruction
     /// \p I to its dominator block.
     /// For example, it is not profitable if \p I and it's only user can form a
     /// FMA instruction, because Powerpc prefers FMADD.
     bool isProfitableToHoist(Instruction *I) const override;
 
+    bool isProfitableToGenerateFMA(Instruction *I) const override;
+
     const MCPhysReg *getScratchRegisters(CallingConv::ID CC) const override;
 
     // Should we expand the build vector with shuffles?
     bool
     shouldExpandBuildVectorWithShuffles(EVT VT,
                                         unsigned DefinedValues) const override;
 
     /// createFastISel - This method returns a target-specific FastISel object,

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

case Instruction::Load: {
     return false;
   }
   default:
     return true;
   }
   return true;
 }
 
+bool PPCTargetLowering::isProfitableToGenerateFMA(Instruction *I) const {
+  const TargetOptions &Options = getTargetMachine().Options;
+  const Function *F = I->getFunction();
+  const DataLayout &DL = F->getParent()->getDataLayout();
+  Type *Ty = I->getOperand(0)->getType();
+
+  return isFMAFasterThanFMulAndFAdd(*F, Ty) &&
+         isOperationLegalOrCustom(ISD::FMA, getValueType(DL, Ty)) &&
+         (Options.AllowFPOpFusion == FPOpFusion::Fast || Options.UnsafeFPMath);
+}
+
 const MCPhysReg *
 PPCTargetLowering::getScratchRegisters(CallingConv::ID) const {
   // LR is a callee-save register, but we must treat it as clobbered by any call
   // site. Hence we include LR in the scratch registers, which are in turn added
   // as implicit-defs for stackmaps and patchpoints. The same reasoning applies
   // to CTR, which is used by any indirect call.
   static const MCPhysReg ScratchRegs[] = {
     PPC::X12, PPC::LR8, PPC::CTR8, 0

llvm/lib/Transforms/Scalar/Reassociate.cpp

if (!match(TheOp, m_Neg(m_Value(X))) && !match(TheOp, m_Not(m_Value(X))) &&
       continue;
 
     unsigned FoundX = FindInOperandList(Ops, i, X);
     if (FoundX == i)
       continue;
 
     // Remove X and -X from the operand list.
     if (Ops.size() == 2 &&
         (match(TheOp, m_Neg(m_Value())) || match(TheOp, m_FNeg(m_Value()))))
       return Constant::getNullValue(X->getType());
 
     // Remove X and ~X from the operand list.
     if (Ops.size() == 2 && match(TheOp, m_Not(m_Value())))
       return Constant::getAllOnesValue(X->getType());
 
     Ops.erase(Ops.begin()+i);
     if (i < FoundX)
       --FoundX;
     else
       --i;   // Need to back up an extra one.
     Ops.erase(Ops.begin()+FoundX);
     ++NumAnnihil;
     --i;     // Revisit element.
     e -= 2;  // Removed two elements.
 
     // if X and ~X we append -1 to the operand list.
     if (match(TheOp, m_Not(m_Value()))) {
       Value *V = Constant::getAllOnesValue(X->getType());
       Ops.insert(Ops.end(), ValueEntry(getRank(V), V));
       e += 1;
     }
   }
 
+  // On some target, add-mul operation is more preferable, common out mul factor
+  // has no gain at all and breaks the add-mul folding, so bail out early.
+  if (TTI->isProfitableToGenerateFMA(I))
+    return nullptr;
+
   // Scan the operand list, checking to see if there are any common factors
   // between operands.  Consider something like A*A+A*B*C+D.  We would like to
   // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies.
   // To efficiently find this, we count the number of times a factor occurs
   // for any ADD operands that are MULs.
   DenseMap<Value*, unsigned> FactorOccurrences;
 
   // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4)
for (Instruction &I : *BI) {
             ++res.first->second.Score;
           }
         }
       }
     }
   }
 }
 
-PreservedAnalyses ReassociatePass::run(Function &F, FunctionAnalysisManager &) {
+bool ReassociatePass::runImpl(Function &F, const TargetTransformInfo *_TTI) {
   // Get the functions basic blocks in Reverse Post Order. This order is used by
   // BuildRankMap to pre calculate ranks correctly. It also excludes dead basic
   // blocks (it has been seen that the analysis in this pass could hang when
   // analysing dead basic blocks).
   ReversePostOrderTraversal<Function *> RPOT(&F);
 
   // Calculate the rank map for F.
   BuildRankMap(F, RPOT);
 
   // Build the pair map before running reassociate.
   // Technically this would be more accurate if we did it after one round
   // of reassociation, but in practice it doesn't seem to help much on
   // real-world code, so don't waste the compile time running reassociate
   // twice.
   // If a user wants, they could expicitly run reassociate twice in their
   // pass pipeline for further potential gains.
   // It might also be possible to update the pair map during runtime, but the
   // overhead of that may be large if there's many reassociable chains.
   BuildPairMap(RPOT);
 
   MadeChange = false;
+  TTI = _TTI;
 
   // Traverse the same blocks that were analysed by BuildRankMap.
   for (BasicBlock *BI : RPOT) {
     assert(RankMap.count(&*BI) && "BB should be ranked.");
     // Optimize every instruction in the basic block.
     for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;)
       if (isInstructionTriviallyDead(&*II)) {
         EraseInst(&*II++);
bool ReassociatePass::runImpl(Function &F, const TargetTransformInfo *_TTI) {
   }
 
   // We are done with the rank map and pair map.
   RankMap.clear();
   ValueRankMap.clear();
   for (auto &Entry : PairMap)
     Entry.clear();
 
-  if (MadeChange) {
+  return MadeChange;
+
+}
+
+PreservedAnalyses ReassociatePass::run(Function &F,
+                                       FunctionAnalysisManager &AM) {
+  const TargetTransformInfo *TTI = &AM.getResult<TargetIRAnalysis>(F);
+
+  if (runImpl(F, TTI)) {
     PreservedAnalyses PA;
     PA.preserveSet<CFGAnalyses>();
     PA.preserve<AAManager>();
     PA.preserve<BasicAA>();
     PA.preserve<GlobalsAA>();
     return PA;
   }
 
public:
 
     ReassociateLegacyPass() : FunctionPass(ID) {
       initializeReassociateLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
       if (skipFunction(F))
         return false;
+      const TargetTransformInfo *TTI =
+          &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 
-      FunctionAnalysisManager DummyFAM;
-      auto PA = Impl.run(F, DummyFAM);
-      return !PA.areAllPreserved();
+      return Impl.runImpl(F, TTI);
     }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       AU.addPreserved<AAResultsWrapperPass>();
       AU.addPreserved<BasicAAWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
+      AU.addRequired<TargetTransformInfoWrapperPass>();
     }
   };
 
 } // end anonymous namespace
 
 char ReassociateLegacyPass::ID = 0;
 
 INITIALIZE_PASS(ReassociateLegacyPass, "reassociate",
                 "Reassociate expressions", false, false)
 
 // Public interface to the Reassociate pass
 FunctionPass *llvm::createReassociatePass() {
   return new ReassociateLegacyPass();
 }

llvm/test/Transforms/Reassociate/PowerPC/lit.local.cfg

+if not 'PowerPC' in config.root.targets:
+    config.unsupported = True

llvm/test/Transforms/Reassociate/PowerPC/prefer-fma.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -reassociate -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-n32:64"
+target triple = "powerpc64le-unknown-linux-gnu"
+
+; check that on PowerPC target, we don't do mul factor commoning optimization.
+
+; a * b + a * c -> a * (b + c) has no gain on PowerPC.
+; before transform: a * b + a * c -> fma(a*b, a, c)
+; after transform:  a * (b + c) -> fmul(a, b + c)
+; fma, fmul, fadd are all have same latency on PowerPC.
+define double @foo(double %0, double %1, double %2) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:    [[TMP4:%.*]] = fmul double [[TMP0:%.*]], [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = fmul double [[TMP0]], [[TMP2:%.*]]
+; CHECK-NEXT:    [[TMP6:%.*]] = fadd double [[TMP4]], [[TMP5]]
+; CHECK-NEXT:    ret double [[TMP6]]
+;
+  %4 = fmul double %0, %1
+  %5 = fmul double %0, %2
+  %6 = fadd double %4, %5
+  ret double %6
+}
+
+; a + 1.47 * b - 1.47 * c + 2.47 * d - 2.47 * e -> a + 1.47 * (b - c) + 2.47 * (d - e) also has no gain.
+; before transform: fma( fma( fma( fma(a, 1.47, b), -1.47, c), -2.47, d), 2.47, e)
+; after transform: fma( fma(a, 1.47, sub(b, c)), 2.47, sub(d, e))
+; fma fmul, fsub all have same latency on PowerPC. Also we lose the folding opportunity for fma.
+define double @fmaChain(double %0, double %1, double %2, double %3, double %4) {
+; CHECK-LABEL: @fmaChain(
+; CHECK-NEXT:    [[TMP6:%.*]] = fmul double [[TMP1:%.*]], 1.470000e+00
+; CHECK-NEXT:    [[TMP7:%.*]] = fadd double [[TMP0:%.*]], [[TMP6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = fmul double [[TMP2:%.*]], 1.470000e+00
+; CHECK-NEXT:    [[TMP9:%.*]] = fsub double [[TMP7]], [[TMP8]]
+; CHECK-NEXT:    [[TMP10:%.*]] = fmul double [[TMP3:%.*]], 2.470000e+00
+; CHECK-NEXT:    [[TMP11:%.*]] = fadd double [[TMP9]], [[TMP10]]
+; CHECK-NEXT:    [[TMP12:%.*]] = fmul double [[TMP4:%.*]], 2.470000e+00
+; CHECK-NEXT:    [[TMP13:%.*]] = fsub double [[TMP11]], [[TMP12]]
+; CHECK-NEXT:    ret double [[TMP13]]
+;
+  %6 = fmul double %1, 1.470000e+00
+  %7 = fadd double %6, %0
+  %8 = fmul double %2, 1.470000e+00
+  %9 = fsub double %7, %8
+  %10 = fmul double %3, 2.470000e+00
+  %11 = fadd double %9, %10
+  %12 = fmul double %4, 2.470000e+00
+  %13 = fsub double %11, %12
+  ret double %13
+}