Prevent hoisting fmul from THEN/ELSE to IF if there is fmsub/fmadd opportunity

[• hulx2000]

Summary

For the following code:

if (y == 0)

{
y = -x * a;
b = a;
}

else

{
y -= x * a;
a = b;
}

HoistThenElseCodeToIf in SimplifyCFG.cpp will hoist the multiply outside the THEN/ELSE, stopping the compiler from forming fmsub later, this is not always a wise thing to do because target that support fused instructions can't take advantage of it, on some target, fmsub/fmadd is more efficient than (fmul +fadd/fsub), plus, by looking at the code generated by gcc compiler, I can see gcc doesn't do that kind of hoisting and leading to better performance on SPEC benchmark which I was analyzing.

This patch is to teach HoistThenElseCodeToIf to stop doing that kind of hoisting by using a target hook that checks for fmadd/fmsub opportunites , that improved spec2006/soplex by 2% consistently on cortex-a57 core, no significant gain for other spec2000/spec2006 benchmarks.

[hfinkel]

include/llvm/Analysis/TargetTransformInfo.h

339

This name is pretty long. How about just isProfitableToHoist?

lib/Target/AArch64/AArch64ISelLowering.cpp

6726

I think you can make this the default implementation. PPC will want essentially the same implementation.

6731

Space before Only.

6743

Space after VT (you should probably run clang-format on the entire patch)

[• hulx2000]

make it default as Hal suggested, unit test remain under AArch64, whoever want to support other target please add test.

[hfinkel]

Adjusting for my comment below, LGTM.

include/llvm/Target/TargetLowering.h

27

You don't want enableAggressiveFMAFusion(VT) here. enableAggressiveFMAFusion(VT) affects whether we combine to form an FMA even when the fmul has more than one use, combine FMAs with other nodes to form multiple FMAs, whether we combine them through fpext nodes, etc. -- but it does not affect fusion legality (and, thus, whether a mul will be combined with a fsub/fadd to from an FMA).

[• hulx2000]

removed the check of enableAggressiveFMAFusion

[hfinkel]

LGTM.

[mcrosier]

Lawrence,
The patch does not apply cleanly to top of trunk. Please rebase and upload a new patch. Once complete, I'd be happy to commit the patch on your behalf.

Chad

[• hulx2000]

rebased patch

[mcrosier]

Committed in r230241.

[sebpop]

IMO this patch should not have been committed.

lib/Target/AArch64/AArch64ISelLowering.cpp

6540

I think that this is only avoiding a bigger issue, that is currently the instruction selection happens on a single basic block.
A better fix would be a machine pass that pairs multiplies with add/sub to form more FMAs.

6561

If both the multiply and the add/sub it feeds into can be hoisted, this code will still prevent multiplies to be hoisted.

[• hulx2000]

lib/Target/AArch64/AArch64ISelLowering.cpp

6540

Could you please explain what do you mean about avoiding a bigger issue?

6561

I do agree about that.

[sebpop]

lib/Target/AArch64/AArch64ISelLowering.cpp

6540

Instruction selection happens on a single basic block, and it cannot form FMAs across BBs. The long term solution is to have an instruction selection that can see further than a BB. Until then probably we could have an MI pass that matches FMAs across BB boundaries.

include/llvm/Analysis/TargetTransformInfo.h

                                  Type *Ty) const;
   virtual unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx,
                                  const APInt &Imm, Type *Ty) const;
+
+  /// \brief Return true if it is profitable to hoist instruction in the
+  /// then/else to before if.
+  virtual bool isProfitableToHoistThenElseCodeToIf(Instruction *I) const;
+
   /// @}
 
   /// \name Vector Target Information

include/llvm/Target/TargetLowering.h

     return LibcallCallingConvs[Call];
   }
 
+  /// Check if it is profitable to hoist instruction in then/else to if.
+  virtual bool isProfitableToHoistThenElseCodeToIf(Instruction *I) const  {
+    return true;
+  }
+
 private:
   const TargetMachine &TM;
   const DataLayout *DL;

lib/Analysis/TargetTransformInfo.cpp

   return PrevTTI->isTruncateFree(Ty1, Ty2);
 }
 
+bool
+TargetTransformInfo::isProfitableToHoistThenElseCodeToIf(Instruction *I) const {
+  return PrevTTI->isProfitableToHoistThenElseCodeToIf(I);
+}
+
 bool TargetTransformInfo::isTypeLegal(Type *Ty) const {
   return PrevTTI->isTypeLegal(Ty);
 }

     return false;
   }
 
+  bool isProfitableToHoistThenElseCodeToIf(Instruction *I) const override {
+    return true;
+  }
+
   bool isTypeLegal(Type *Ty) const override {
     return false;
   }

lib/CodeGen/BasicTargetTransformInfo.cpp

   unsigned getAddressComputationCost( Type *Ty, bool IsComplex) const override;
   unsigned getReductionCost(unsigned Opcode, Type *Ty,
                             bool IsPairwise) const override;
+  bool isProfitableToHoistThenElseCodeToIf(Instruction *I) const override;
 
   /// @}
 };

   return getTLI()->isTruncateFree(Ty1, Ty2);
 }
 
+bool BasicTTI::isProfitableToHoistThenElseCodeToIf(Instruction *I) const {
+  return getTLI()->isProfitableToHoistThenElseCodeToIf(I);
+}
+
 bool BasicTTI::isTypeLegal(Type *Ty) const {
   EVT T = getTLI()->getValueType(Ty);
   return getTLI()->isTypeLegal(T);

lib/Target/AArch64/AArch64ISelLowering.h

 #include "llvm/CodeGen/CallingConvLower.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/IR/CallingConv.h"
+#include "llvm/IR/Instruction.h"
 #include "llvm/Target/TargetLowering.h"
 
 namespace llvm {

   bool useLoadStackGuardNode() const override;
   TargetLoweringBase::LegalizeTypeAction
   getPreferredVectorAction(EVT VT) const override;
+  bool isProfitableToHoistThenElseCodeToIf(Instruction *I) const override;
 
 private:
   /// Subtarget - Keep a pointer to the AArch64Subtarget around so that we can

lib/Target/AArch64/AArch64ISelLowering.cpp

   return false;
 }
 
+/// IsProfitableToHoistThenElseCodeToIf - Not profitable if I and
+/// it's user can form a FMA instruction because we prefer FMSUB/FMADD.
+bool
+AArch64TargetLowering::isProfitableToHoistThenElseCodeToIf(Instruction *I)
+  const {
+  if (I->getOpcode() != Instruction::FMul)
+    return true;
+
+  //Only care one user case for now
+  if (I->getNumUses() != 1)
+    return true;
+
+  Instruction *User = I->user_back();
+
+  if (User &&
+      !(User->getOpcode() == Instruction::FSub ||
+        User->getOpcode() == Instruction::FAdd))
+    return true;
+
+  const TargetOptions &Options = getTargetMachine().Options;
+  EVT VT= getValueType(User->getOperand(0)->getType());
+
+  if (isFMAFasterThanFMulAndFAdd(VT) &&
+      isOperationLegalOrCustom(ISD::FMA, VT) &&
+      (Options.AllowFPOpFusion == FPOpFusion::Fast ||
+       Options.UnsafeFPMath || enableAggressiveFMAFusion(VT)))
+    return false;
+
+  return true;
+}
+
 const MCPhysReg *
 AArch64TargetLowering::getScratchRegisters(CallingConv::ID) const {
   // LR is a callee-save register, but we must treat it as clobbered by any call

lib/Transforms/Utils/SimplifyCFG.cpp

 /// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and
 /// BB2, hoist any common code in the two blocks up into the branch block.  The
 /// caller of this function guarantees that BI's block dominates BB1 and BB2.
-static bool HoistThenElseCodeToIf(BranchInst *BI, const DataLayout *DL) {
+static bool HoistThenElseCodeToIf(BranchInst *BI, const DataLayout *DL,
+                                  const TargetTransformInfo &TTI) {
   // This does very trivial matching, with limited scanning, to find identical
   // instructions in the two blocks.  In particular, we don't want to get into
   // O(M*N) situations here where M and N are the sizes of BB1 and BB2.  As

     if (isa<TerminatorInst>(I1))
       goto HoistTerminator;
 
+    if (!TTI.isProfitableToHoistThenElseCodeToIf(I1) ||
+        !TTI.isProfitableToHoistThenElseCodeToIf(I2))
+      return Changed;
+
     // For a normal instruction, we just move one to right before the branch,
     // then replace all uses of the other with the first.  Finally, we remove
     // the now redundant second instruction.

   // can hoist it up to the branching block.
   if (BI->getSuccessor(0)->getSinglePredecessor()) {
     if (BI->getSuccessor(1)->getSinglePredecessor()) {
-      if (HoistThenElseCodeToIf(BI, DL))
+      if (HoistThenElseCodeToIf(BI, DL, TTI))
         return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AC) | true;
     } else {
       // If Successor #1 has multiple preds, we may be able to conditionally

test/Transforms/SimplifyCFG/AArch64/lit.local.cfg

+config.suffixes = ['.ll']
+
+targets = set(config.root.targets_to_build.split())
+if not 'AArch64' in targets:
+    config.unsupported = True

test/Transforms/SimplifyCFG/AArch64/prefer-fma.ll

+; RUN: opt < %s -mtriple=aarch64-linux-gnu -simplifycfg -enable-unsafe-fp-math -S >%t
+; RUN: FileCheck %s < %t
+; ModuleID = 't.cc'
+
+; Function Attrs: nounwind
+define double @_Z3fooRdS_S_S_(double* dereferenceable(8) %x, double* dereferenceable(8) %y, double* dereferenceable(8) %a) #0 {
+entry:
+  %0 = load double* %y, align 8
+  %cmp = fcmp oeq double %0, 0.000000e+00
+  %1 = load double* %x, align 8
+  br i1 %cmp, label %if.then, label %if.else
+
+; fadd (const, (fmul x, y))
+if.then:                                          ; preds = %entry
+; CHECK-LABEL: if.then:
+; CHECK:   %3 = fmul fast double %1, %2
+; CHECK-NEXT:   %mul = fadd fast double 1.000000e+00, %3
+  %2 = load double* %a, align 8
+  %3 = fmul fast double %1, %2
+  %mul = fadd fast double 1.000000e+00, %3
+  store double %mul, double* %y, align 8
+  br label %if.end
+
+; fsub ((fmul x, y), z)
+if.else:                                          ; preds = %entry
+; CHECK-LABEL: if.else:
+; CHECK:   %mul1 = fmul fast double %1, %2
+; CHECK-NEXT:   %sub1 = fsub fast double %mul1, %0
+  %4 = load double* %a, align 8
+  %mul1 = fmul fast double %1, %4
+  %sub1 = fsub fast double %mul1, %0
+  store double %sub1, double* %y, align 8
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %5 = load double* %y, align 8
+  %cmp2 = fcmp oeq double %5, 2.000000e+00
+  %6 = load double* %x, align 8
+  br i1 %cmp2, label %if.then2, label %if.else2
+
+; fsub (x, (fmul y, z))
+if.then2:                                         ; preds = %entry
+; CHECK-LABEL: if.then2:
+; CHECK:   %7 = fmul fast double %5, 3.000000e+00
+; CHECK-NEXT:   %mul2 = fsub fast double %6, %7
+  %7 = load double* %a, align 8
+  %8 = fmul fast double %6, 3.0000000e+00
+  %mul2 = fsub fast double %7, %8
+  store double %mul2, double* %y, align 8
+  br label %if.end2
+
+; fsub (fneg((fmul x, y)), const)
+if.else2:                                         ; preds = %entry
+; CHECK-LABEL: if.else2:
+; CHECK:   %mul3 = fmul fast double %5, 3.000000e+00
+; CHECK-NEXT:   %neg = fsub fast double 0.000000e+00, %mul3
+; CHECK-NEXT:   %sub2 = fsub fast double %neg, 3.000000e+00
+  %mul3 = fmul fast double %6, 3.0000000e+00
+  %neg = fsub fast double 0.0000000e+00, %mul3
+  %sub2 = fsub fast double %neg, 3.0000000e+00
+  store double %sub2, double* %y, align 8
+  br label %if.end2
+
+if.end2:                                           ; preds = %if.else, %if.then
+  %9 = load double* %x, align 8
+  %10 = load double* %y, align 8
+  %add = fadd fast double %9, %10
+  %11 = load double* %a, align 8
+  %add2 = fadd fast double %add, %11
+  ret double %add2
+}
+