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 ↗

(On Diff #19043)

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

6731 ↗

(On Diff #19043)

Space before Only.

6743 ↗

(On Diff #19043)

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 ↗

(On Diff #20320)

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 ↗

(On Diff #20320)

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 ↗

(On Diff #20320)

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

6561 ↗

(On Diff #20320)

I do agree about that.

[sebpop]

lib/Target/AArch64/AArch64ISelLowering.cpp

6540 ↗

(On Diff #20320)

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 isProfitableToHoist(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.
+  /// Not profitable if I and it's user can form a FMA instruction
+  /// because we prefer FMSUB/FMADD.
+  bool isProfitableToHoist(Instruction *I) const {
+    if (I->getOpcode() != Instruction::FMul)
+      return true;
+
+    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))
+      return false;
+
+    return true;
+  }
+
 private:
   const TargetMachine &TM;
   const DataLayout *DL;

lib/Analysis/TargetTransformInfo.cpp

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

     return false;
   }
 
+  bool isProfitableToHoist(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 isProfitableToHoist(Instruction *I) const override;
 
   /// @}
 };

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

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.isProfitableToHoist(I1) ||
+        !TTI.isProfitableToHoist(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
+}
+