[FPEnv Core 04/14] Skip constant folding to preserve FPEnv

[sdmitrouk]

Summary

Consider floating point environment flags when constant folding
expressions.

[scanon]

include/llvm/Analysis/ValueTracking.h

260

I think we should leave the one-sentence intro as-is to maximize readability; it's still correct with the new settings, AFAICT. Then let's add a paragraph to explain the floating-point-specific details:

"If KeepExceptions is true, then speculative execution of most floating-point operations will result in observably different floating-point exceptions being raised."

Worth noting: it's not obvious that KeepRounding fits the bill for isSafeToSpeculativelyExecute, but rounding-mode does change the observable exceptions by moving the overflow/underflow boundaries. However, that's just one small part of what you're trying to get at here with rounding, the larger part of which seems conceptually to be closer to "memory dependent" (except that the "memory" is floating-point control).

[majnemer]

include/llvm/IR/Constants.h

1073–1074

Why not accept an FastMathFlags instead?

lib/Analysis/ValueTracking.cpp

3284–3285

Unless I am mistaken, could you figure out these flags from V itself?

3290

const auto *

lib/IR/Constants.cpp

327–335

Why was this changed?

[sdmitrouk]

Updated text of comments, updated code to pass fast-math flags in several places, adjusted code according to review comments, updated tests which are affected by inversion of meaning of flags.

[sdmitrouk]

Revert questionable change in undef-label.ll (it shouldn't be here anyway), this also removes four tests that are now in D14067.

[mehdi_amini]

include/llvm/Analysis/ValueTracking.h

264

The KeepExceptions parameter is not clear to me, what would it be used for? (there is no use in this patch)

include/llvm/IR/Constants.h

1073

Document the new FMF parameter, especially how it differs from Flags, it is confusing right now.

Also, seeing multiple places where you need to explicitly add 0, nullptr, to be able to pass a FMF, it can be worthwhile to add an override that does not take Flags and OnlyIfReducedTy and forward to this one.

1202

Should it be allowed on non-FP operations? I could see it assert instead.

lib/Analysis/InstructionSimplify.cpp

3783 ↗

(On Diff #41912)

It this related to this patch or could this be committed separately?

lib/Analysis/ValueTracking.cpp

3313

You already tested for KeepExceptions at this scope.

lib/IR/ConstantFold.cpp

1185

I'd refactor the test with a named lambda defined before the switch.
That said the full switch could be refactored better already.

lib/IR/Constants.cpp

1874

You may want to assert that if FMF is supplied we have a Floating point Opcode?

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1214 ↗

(On Diff #41912)

Initialize closer to its use, there are multiple path that early return and don't need this.

lib/Transforms/InstCombine/InstructionCombining.cpp

215 ↗

(On Diff #41912)

No braces

[sdmitrouk]

Addressing review comments.

[sdmitrouk]

@joker.eph, thanks. Changed according to your comments, but tests on this revision don't pass... Can't reorder commits nicely due to changes of flags (now that default value FastMathFlags() is "bad" for incremental changes). Instead I'm leaving patches separated for review, but when committing will squash them to make tests pass on each revision.

include/llvm/Analysis/ValueTracking.h

264

It's left from one of previous versions, the one with function attributes. Removed.

include/llvm/IR/Constants.h

1073

Should be done, at least for this patch.

1208

Moved it to place where it's used (used to be two such places), changed type of argument and added an assert.

lib/Analysis/ValueTracking.cpp

3313

Accidentally applied stash to the next patch instead of this one.

lib/IR/ConstantFold.cpp

1187–1191

Changed it using Optional.

[mehdi_amini]

LGTM with the few nitpicks below.

include/llvm/Analysis/ValueTracking.h

264

It seems you left the doxygen change in?

lib/IR/ConstantFold.cpp

1214

sweet!

lib/Transforms/InstCombine/InstructionCombining.cpp

212 ↗

(On Diff #42225)

Keep the name FMF for consistency with everywhere else.

[sdmitrouk]

Address the nitpicks, thanks for noticing them.

[mehdi_amini]

include/llvm/IR/FastMathFlags.h

38 ↗

(On Diff #42270)

Shouldn't the default be NoExceptions | NoRounding ?

[mehdi_amini]

Thinking about it more we will never reach correctness without having the safe option by default.

[sdmitrouk]

include/llvm/IR/FastMathFlags.h

38 ↗

(On Diff #42270)

Well, it was initially, and it was easier then, but meaning of flags was changed after comments in D14067 partly to make default value all zeroes.

include/llvm/Analysis/ValueTracking.h

namespace llvm {
   /// dereferenceable at the specified instruction.
   bool isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
                                           const DataLayout &DL,
                                           const Instruction *CtxI = nullptr,
                                           const DominatorTree *DT = nullptr,
                                           const TargetLibraryInfo *TLI = nullptr);
 
   /// isSafeToSpeculativelyExecute - Return true if the instruction does not
-  /// have any effects besides calculating the result and does not have
-  /// undefined behavior.
+  /// have any effects besides calculating the result (in a way that doesn't
+  /// lose floating-point exceptions or precision when requested via
+  /// corresponding flags) and does not have undefined behavior.
   ///
   /// This method never returns true for an instruction that returns true for
   /// mayHaveSideEffects; however, this method also does some other checks in
   /// addition. It checks for undefined behavior, like dividing by zero or
   /// loading from an invalid pointer (but not for undefined results, like a
   /// shift with a shift amount larger than the width of the result). It checks
   /// for malloc and alloca because speculatively executing them might cause a
   /// memory leak. It also returns false for instructions related to control
   /// flow, specifically terminators and PHI nodes.
   ///
   /// If the CtxI is specified this method performs context-sensitive analysis
   /// and returns true if it is safe to execute the instruction immediately
   /// before the CtxI.
   ///
   /// If the CtxI is NOT specified this method only looks at the instruction
   /// itself and its operands, so if this method returns true, it is safe to
   /// move the instruction as long as the correct dominance relationships for
   /// the operands and users hold.
   ///
   /// This method can return true for instructions that read memory;
   /// for such instructions, moving them may change the resulting value.
   bool isSafeToSpeculativelyExecute(const Value *V,
                                     const Instruction *CtxI = nullptr,
                                     const DominatorTree *DT = nullptr,
-                                    const TargetLibraryInfo *TLI = nullptr);
+                                    const TargetLibraryInfo *TLI = nullptr,
+                                    bool KeepExceptions = false,
+                                    bool KeepRounding = false);
 
   /// Returns true if the result or effects of the given instructions \p I
   /// depend on or influence global memory.
   /// Memory dependence arises for example if the the instruction reads from
   /// memory or may produce effects or undefined behaviour. Memory dependent
   /// instructions generally cannot be reorderd with respect to other memory
   /// dependent instructions or moved into non-dominated basic blocks.
   /// Instructions which just compute a value based on the values of their

include/llvm/IR/Constants.h

public:
   static Constant *getSelect(Constant *C, Constant *V1, Constant *V2,
                              Type *OnlyIfReducedTy = nullptr);
 
   /// get - Return a binary or shift operator constant expression,
   /// folding if possible.
   ///
   /// \param OnlyIfReducedTy see \a getWithOperands() docs.
   static Constant *get(unsigned Opcode, Constant *C1, Constant *C2,
-                       unsigned Flags = 0, Type *OnlyIfReducedTy = nullptr);
+                       unsigned Flags = 0, Type *OnlyIfReducedTy = nullptr,
+                       bool KeepExceptions = false,
+                       bool KeepRounding = false);
 
   /// \brief Return an ICmp or FCmp comparison operator constant expression.
   ///
   /// \param OnlyIfReduced see \a getWithOperands() docs.
   static Constant *getCompare(unsigned short pred, Constant *C1, Constant *C2,
                               bool OnlyIfReduced = false);
 
   /// get* - Return some common constants without having to
public:
   /// would make it harder to remove ConstantExprs altogether.
   Instruction *getAsInstruction();
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const Value *V) {
     return V->getValueID() == ConstantExprVal;
   }
 
+  /// Evaluates floating point operation to examine how it could affect
+  /// floating-environment at run-time if it's not folded, does nothing for
+  /// non-FP operations.  Returns false for unsupported values, otherwise true
+  /// is returned and S is assigned status of the operation.
+  static bool getFPOpExceptions(const Value *V, APFloat::opStatus &S);
+
 private:
   // Shadow Value::setValueSubclassData with a private forwarding method so that
   // subclasses cannot accidentally use it.
   void setValueSubclassData(unsigned short D) {
     Value::setValueSubclassData(D);
   }
 };
 
 template <>
 struct OperandTraits<ConstantExpr> :
   public VariadicOperandTraits<ConstantExpr, 1> {
 };
 

lib/Analysis/ValueTracking.cpp

bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL,
                                     const DominatorTree *DT,
                                     const TargetLibraryInfo *TLI) {
   return isDereferenceableAndAlignedPointer(V, 1, DL, CtxI, DT, TLI);
 }
 
 bool llvm::isSafeToSpeculativelyExecute(const Value *V,
                                         const Instruction *CtxI,
                                         const DominatorTree *DT,
-                                        const TargetLibraryInfo *TLI) {
+                                        const TargetLibraryInfo *TLI,
+                                        bool KeepExceptions,
+                                        bool KeepRounding) {
   const Operator *Inst = dyn_cast<Operator>(V);
   if (!Inst)
     return false;
 
+  if (const FPMathOperator *MathOp = dyn_cast<FPMathOperator>(Inst)) {
+      KeepExceptions |= MathOp->hasKeepExceptions();
+      KeepRounding |= MathOp->hasKeepRounding();
+  }
+
   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
     if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i)))
       if (C->canTrap())
         return false;
 
   switch (Inst->getOpcode()) {
   default:
     return true;
+  case Instruction::FMul:
+  case Instruction::FAdd:
+  case Instruction::FSub:
+  case Instruction::FDiv:
+  case Instruction::FRem:
+    if (KeepExceptions || KeepRounding) {
+      APFloat::opStatus S;
+      if (!ConstantExpr::getFPOpExceptions(Inst, S))
+        return false;
+
+      if (KeepExceptions && S != APFloat::opOK)
+        return false;
+      if (KeepRounding && (S & APFloat::opInexact))
+        return false;
+    }
+    return true;
   case Instruction::UDiv:
   case Instruction::URem: {
     // x / y is undefined if y == 0.
     const APInt *V;
     if (match(Inst->getOperand(1), m_APInt(V)))
       return *V != 0;
     return false;
   }

lib/IR/ConstantFold.h

Constant *ConstantFoldInsertElementInstruction(Constant *Val, Constant *Elt,
                                                  Constant *Idx);
   Constant *ConstantFoldShuffleVectorInstruction(Constant *V1, Constant *V2,
                                                  Constant *Mask);
   Constant *ConstantFoldExtractValueInstruction(Constant *Agg,
                                                 ArrayRef<unsigned> Idxs);
   Constant *ConstantFoldInsertValueInstruction(Constant *Agg, Constant *Val,
                                                ArrayRef<unsigned> Idxs);
   Constant *ConstantFoldBinaryInstruction(unsigned Opcode, Constant *V1,
-                                          Constant *V2);
+                                          Constant *V2, bool KeepFPExceptions,
+                                          bool KeepFPRounding);
   Constant *ConstantFoldCompareInstruction(unsigned short predicate, 
                                            Constant *C1, Constant *C2);
   Constant *ConstantFoldGetElementPtr(Constant *C, bool inBounds,
                                       ArrayRef<Constant *> Idxs);
   Constant *ConstantFoldGetElementPtr(Constant *C, bool inBounds,
                                       ArrayRef<Value *> Idxs);
   Constant *ConstantFoldGetElementPtr(Type *Ty, Constant *C, bool inBounds,
                                       ArrayRef<Constant *> Idxs);
   Constant *ConstantFoldGetElementPtr(Type *Ty, Constant *C, bool inBounds,
                                       ArrayRef<Value *> Idxs);
 } // End llvm namespace
 
 #endif

lib/IR/ConstantFold.cpp

if (StructType *ST = dyn_cast<StructType>(Agg->getType()))
     return ConstantStruct::get(ST, Result);
   if (ArrayType *AT = dyn_cast<ArrayType>(Agg->getType()))
     return ConstantArray::get(AT, Result);
   return ConstantVector::get(Result);
 }
 
 
 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
-                                              Constant *C1, Constant *C2) {
+                                              Constant *C1, Constant *C2,
+                                              bool KeepExceptions,
+                                              bool KeepRounding) {
   // Handle UndefValue up front.
   if (isa<UndefValue>(C1) || isa<UndefValue>(C2)) {
     switch (Opcode) {
     case Instruction::Xor:
       if (isa<UndefValue>(C1) && isa<UndefValue>(C2))
         // Handle undef ^ undef -> 0 special case. This is a common
         // idiom (misuse).
         return Constant::getNullValue(C1->getType());
case Instruction::AShr:
       if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1))
         if (CE1->getOpcode() == Instruction::ZExt)  // Top bits known zero.
           return ConstantExpr::getLShr(C1, C2);
       break;
     }
   } else if (isa<ConstantInt>(C1)) {
     // If C1 is a ConstantInt and C2 is not, swap the operands.
     if (Instruction::isCommutative(Opcode))
-      return ConstantExpr::get(Opcode, C2, C1);
+      return ConstantExpr::get(Opcode, C2, C1, 0, nullptr, KeepExceptions,
+                               KeepRounding);
   }
 
   // At this point we know neither constant is an UndefValue.
   if (ConstantInt *CI1 = dyn_cast<ConstantInt>(C1)) {
     if (ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) {
       const APInt &C1V = CI1->getValue();
       const APInt &C2V = CI2->getValue();
       switch (Opcode) {
if (ConstantInt *CI1 = dyn_cast<ConstantInt>(C1)) {
     default:
       break;
     }
   } else if (ConstantFP *CFP1 = dyn_cast<ConstantFP>(C1)) {
     if (ConstantFP *CFP2 = dyn_cast<ConstantFP>(C2)) {
       APFloat C1V = CFP1->getValueAPF();
       APFloat C2V = CFP2->getValueAPF();
       APFloat C3V = C1V;  // copy for modification
+      APFloat::opStatus S;
       switch (Opcode) {
-      default:                   
+      default:
         break;
       case Instruction::FAdd:
-        (void)C3V.add(C2V, APFloat::rmNearestTiesToEven);
+        S = C3V.add(C2V, APFloat::rmNearestTiesToEven);
+        if ((KeepExceptions && S != APFloat::opOK) ||
+            (KeepRounding && (S & APFloat::opInexact)))
+          break;
         return ConstantFP::get(C1->getContext(), C3V);
       case Instruction::FSub:
-        (void)C3V.subtract(C2V, APFloat::rmNearestTiesToEven);
+        S = C3V.subtract(C2V, APFloat::rmNearestTiesToEven);
+        if ((KeepExceptions && S != APFloat::opOK) ||
+            (KeepRounding && (S & APFloat::opInexact)))
+          break;
         return ConstantFP::get(C1->getContext(), C3V);
       case Instruction::FMul:
-        (void)C3V.multiply(C2V, APFloat::rmNearestTiesToEven);
+        S = C3V.multiply(C2V, APFloat::rmNearestTiesToEven);
+        if ((KeepExceptions && S != APFloat::opOK) ||
+            (KeepRounding && (S & APFloat::opInexact)))
+          break;
         return ConstantFP::get(C1->getContext(), C3V);
       case Instruction::FDiv:
-        (void)C3V.divide(C2V, APFloat::rmNearestTiesToEven);
+        S = C3V.divide(C2V, APFloat::rmNearestTiesToEven);
+        if ((KeepExceptions && S != APFloat::opOK) ||
+            (KeepRounding && (S & APFloat::opInexact)))
+          break;
         return ConstantFP::get(C1->getContext(), C3V);
       case Instruction::FRem:
-        (void)C3V.mod(C2V);
+        S = C3V.mod(C2V);
+        if ((KeepExceptions && S != APFloat::opOK) ||
+            (KeepRounding && (S & APFloat::opInexact)))
+          break;
         return ConstantFP::get(C1->getContext(), C3V);
       }
     }
   } else if (VectorType *VTy = dyn_cast<VectorType>(C1->getType())) {
     // Perform elementwise folding.
     SmallVector<Constant*, 16> Result;
     Type *Ty = IntegerType::get(VTy->getContext(), 32);
     for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
       Constant *LHS =
         ConstantExpr::getExtractElement(C1, ConstantInt::get(Ty, i));
       Constant *RHS =
         ConstantExpr::getExtractElement(C2, ConstantInt::get(Ty, i));
-      
-      Result.push_back(ConstantExpr::get(Opcode, LHS, RHS));
+      Result.push_back(ConstantExpr::get(Opcode, LHS, RHS, 0, nullptr,
+                                         KeepExceptions, KeepRounding));
     }
-    
     return ConstantVector::get(Result);
   }
 
   if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) {
     // There are many possible foldings we could do here.  We should probably
     // at least fold add of a pointer with an integer into the appropriate
     // getelementptr.  This will improve alias analysis a bit.
 
     // Given ((a + b) + c), if (b + c) folds to something interesting, return
     // (a + (b + c)).
     if (Instruction::isAssociative(Opcode) && CE1->getOpcode() == Opcode) {
-      Constant *T = ConstantExpr::get(Opcode, CE1->getOperand(1), C2);
+      Constant *T = ConstantExpr::get(Opcode, CE1->getOperand(1), C2, 0,
+                                      nullptr, KeepExceptions, KeepRounding);
       if (!isa<ConstantExpr>(T) || cast<ConstantExpr>(T)->getOpcode() != Opcode)
-        return ConstantExpr::get(Opcode, CE1->getOperand(0), T);
+        return ConstantExpr::get(Opcode, CE1->getOperand(0), T, 0, nullptr,
+                                 KeepExceptions, KeepRounding);
     }
   } else if (isa<ConstantExpr>(C2)) {
     // If C2 is a constant expr and C1 isn't, flop them around and fold the
     // other way if possible.
     if (Instruction::isCommutative(Opcode))
-      return ConstantFoldBinaryInstruction(Opcode, C2, C1);
+      return ConstantFoldBinaryInstruction(Opcode, C2, C1, KeepExceptions,
+                                           KeepRounding);
   }
 
   // i1 can be simplified in many cases.
   if (C1->getType()->isIntegerTy(1)) {
     switch (Opcode) {
     case Instruction::Add:
     case Instruction::Sub:
       return ConstantExpr::getXor(C1, C2);

lib/IR/Constants.cpp

 static bool canTrapImpl(const Constant *C,
                         SmallPtrSetImpl<const ConstantExpr *> &NonTrappingOps) {
   assert(C->getType()->isFirstClassType() && "Cannot evaluate aggregate vals!");
   // The only thing that could possibly trap are constant exprs.
   const ConstantExpr *CE = dyn_cast<ConstantExpr>(C);
   if (!CE)
     return false;
 
   // ConstantExpr traps if any operands can trap.
   for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) {
     if (ConstantExpr *Op = dyn_cast<ConstantExpr>(CE->getOperand(i))) {
-      if (NonTrappingOps.insert(Op).second && canTrapImpl(Op, NonTrappingOps))
+      if (NonTrappingOps.insert(Op).second && canTrapImpl(Op, NonTrappingOps)) {
         return true;
       }
     }
+  }
 
   // Otherwise, only specific operations can trap.
   switch (CE->getOpcode()) {
   default:
     return false;
   case Instruction::UDiv:
   case Instruction::SDiv:
   case Instruction::FDiv:
   case Instruction::URem:
if (VectorType *VT = dyn_cast<VectorType>(DstTy)) {
       MidTy = VectorType::get(MidTy, VT->getNumElements());
     }
     C = getBitCast(C, MidTy);
   }
   return getFoldedCast(Instruction::AddrSpaceCast, C, DstTy, OnlyIfReduced);
 }
 
 Constant *ConstantExpr::get(unsigned Opcode, Constant *C1, Constant *C2,
-                            unsigned Flags, Type *OnlyIfReducedTy) {
+                            unsigned Flags, Type *OnlyIfReducedTy,
+                            bool KeepExceptions, bool KeepRounding) {
   // Check the operands for consistency first.
   assert(Opcode >= Instruction::BinaryOpsBegin &&
          Opcode <  Instruction::BinaryOpsEnd   &&
          "Invalid opcode in binary constant expression");
   assert(C1->getType() == C2->getType() &&
          "Operand types in binary constant expression should match");
 
 #ifndef NDEBUG
case Instruction::AShr:
     assert(C1->getType()->isIntOrIntVectorTy() &&
            "Tried to create a shift operation on a non-integer type!");
     break;
   default:
     break;
   }
 #endif
 
-  if (Constant *FC = ConstantFoldBinaryInstruction(Opcode, C1, C2))
+  if (Constant *FC = ConstantFoldBinaryInstruction(Opcode, C1, C2,
+                                                   KeepExceptions,
+                                                   KeepRounding)) {
     return FC;          // Fold a few common cases.
+  }
 
   if (OnlyIfReducedTy == C1->getType())
     return nullptr;
 
   Constant *ArgVec[] = { C1, C2 };
   ConstantExprKeyType Key(Opcode, ArgVec, 0, Flags);
 
   LLVMContextImpl *pImpl = C1->getContext().pImpl;
if (isa<OverflowingBinaryOperator>(BO)) {
       BO->setHasNoSignedWrap(SubclassOptionalData &
                              OverflowingBinaryOperator::NoSignedWrap);
     }
     if (isa<PossiblyExactOperator>(BO))
       BO->setIsExact(SubclassOptionalData & PossiblyExactOperator::IsExact);
     return BO;
   }
 }
+
+bool ConstantExpr::getFPOpExceptions(const Value *V, APFloat::opStatus &S) {
+  unsigned Opcode;
+  const User *U;
+  if (const Operator *Op = dyn_cast<Operator>(V)) {
+    U = Op;
+    Opcode = Op->getOpcode();
+  } if (const ConstantExpr *C = dyn_cast<ConstantExpr>(V)) {
+    U = C;
+    Opcode = C->getOpcode();
+  } else {
+    return false;
+  }
+
+  switch (Opcode) {
+  default:
+    return true;
+  case Instruction::FMul:
+  case Instruction::FAdd:
+  case Instruction::FSub:
+  case Instruction::FDiv:
+  case Instruction::FRem: {
+    ConstantFP *LHSC = dyn_cast<ConstantFP>(U->getOperand(0));
+    ConstantFP *RHSC = dyn_cast<ConstantFP>(U->getOperand(1));
+
+    if (!LHSC || !RHSC) {
+      return false;
+    }
+
+    APFloat LHS = LHSC->getValueAPF();
+    APFloat RHS = LHSC->getValueAPF();
+
+    switch (Opcode) {
+    case Instruction::FMul:
+      S = LHS.multiply(RHS, APFloat::rmNearestTiesToEven);
+      break;
+    case Instruction::FAdd:
+      S = LHS.add(RHS, APFloat::rmNearestTiesToEven);
+      break;
+    case Instruction::FSub:
+      S = LHS.subtract(RHS, APFloat::rmNearestTiesToEven);
+      break;
+    case Instruction::FDiv:
+      S = LHS.divide(RHS, APFloat::rmNearestTiesToEven);
+      break;
+    case Instruction::FRem:
+      S = LHS.mod(RHS);
+      break;
+    }
+
+    return true;
+  }
+  }
+}