[IR] allow fast-math-flags on phi of FP values

[spatel]

Summary

The changes here are based on the corresponding diffs for allowing FMF on 'select':
D61917

As discussed there, we want to have fast-math-flags be a property of an FP value because the alternative (having them on things like fcmp) leads to logical inconsistency such as:
https://bugs.llvm.org/show_bug.cgi?id=38086

The earlier patch for select made almost no practical difference because most unoptimized conditional code begins life as a phi (based on what I see in clang).
Similarly, I don't expect this patch to do much on its own either because SimplifyCFG promptly drops the flags when converting to select on a minimal example like:
https://bugs.llvm.org/show_bug.cgi?id=39535

But once we have this plumbing in place, we should be able to wire up the FMF propagation and start solving cases like that.

The change to RecurrenceDescriptor::AddReductionVar() is required to prevent a regression in a LoopVectorize test. We are intersecting the FMF of any FPMathOperator there, so if a phi is not properly annotated, new math instructions may not be either. Once we fix the propagation in SimplifyCFG, it may be safe to remove that hack.

[cameron.mcinally]

Maybe a dumb question, but what happens if two incoming PHI values have different FMFs set? Does the PHI's FMF override those? If so, is that safe?

[mcberg2017]

WRT divergent phi FMF, if you wanted to be pessimistic you could do an intersection(and), doing an inclusion(or) might include too much. Either way behavior would change. The intersection already has other prior context in FMF.

[spatel]

In D67564#1670055, @mcberg2017 wrote:

WRT divergent phi FMF, if you wanted to be pessimistic you could do an intersection(and), doing an inclusion(or) might include too much. Either way behavior would change. The intersection already has other prior context in FMF.

Right - we have places (like the IVDescriptors diff in this patch) that intersects FMF. Most IR has uniform FMF because it's set in the front-end and passed as-is through the optimizer. Ie, it takes an LTO scenario (with differing FP optimization flags on compiled modules) to see non-uniform FMF, so it's not that common (yet?).

I don't know of any places in the IR optimizer currently where we'd get this wrong by being too liberal. It's more likely -- as with the SimplifyCFG transform mentioned in the description -- that we lose FMF completely.

[cameron.mcinally]

LGTM

My confidence is somewhat low though...

[spatel]

In D67564#1671398, @cameron.mcinally wrote:

LGTM

Thanks!

My confidence is somewhat low though...

Sure, can someone else please take a look? (adding a few more potential reviewers from the earlier patch)

[spatel]

Ping - anyone want to issue a 2nd opinion/review?

[lebedev.ri]

I think this makes sense since select already has those attrs.
But what should happen for non-fp phi's? Do those flags make sense on e.g. i32 ?

[spatel]

In D67564#1679387, @lebedev.ri wrote:

I think this makes sense since select already has those attrs.
But what should happen for non-fp phi's? Do those flags make sense on e.g. i32 ?

Unless the definition of FPMathOperator is broken, we won't allow FMF on a non-FP type of phi/select.
Or are you asking if things like nsw/nuw/exact make sense on a phi with integer type? I haven't thought about that...
(We can't have both FMF and wrapping/exact flags simultaneously because the underlying implementation shares the bits of SubclassOptionalData.)

[lebedev.ri]

In D67564#1679431, @spatel wrote:

In D67564#1679387, @lebedev.ri wrote:

I think this makes sense since select already has those attrs.
But what should happen for non-fp phi's? Do those flags make sense on e.g. i32 ?

Unless the definition of FPMathOperator is broken, we won't allow FMF on a non-FP type of phi/select.

Yes, that was the question.

Or are you asking if things like nsw/nuw/exact make sense on a phi with integer type? I haven't thought about that...

No, that doesn't make sense. Those only make sense on actual instructions.

(We can't have both FMF and wrapping/exact flags simultaneously because the underlying implementation shares the bits of SubclassOptionalData.)

[jmolloy]

LGTM, sorry for the long latency.

llvm/trunk/docs/LangRef.rst

 '``phi``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      <result> = phi <ty> [ <val0>, <label0>], ...
+      <result> = phi [fast-math-flags] <ty> [ <val0>, <label0>], ...
 
 Overview:
 """""""""
 
 The '``phi``' instruction is used to implement the φ node in the SSA
 graph representing the function.
 
 Arguments:

 and the PHI instructions: i.e. PHI instructions must be first in a basic
 block.
 
 For the purposes of the SSA form, the use of each incoming value is
 deemed to occur on the edge from the corresponding predecessor block to
 the current block (but after any definition of an '``invoke``'
 instruction's return value on the same edge).
 
+The optional ``fast-math-flags`` marker indicates that the phi has one
+or more :ref:`fast-math-flags <fastmath>`. These are optimization hints
+to enable otherwise unsafe floating-point optimizations. Fast-math-flags
+are only valid for phis that return a floating-point scalar or vector
+type.
+
 Semantics:
 """"""""""
 
 At runtime, the '``phi``' instruction logically takes on the value
 specified by the pair corresponding to the predecessor basic block that
 executed just prior to the current block.
 
 Example:

llvm/trunk/include/llvm/IR/IRBuilder.h

   }
 
   //===--------------------------------------------------------------------===//
   // Instruction creation methods: Other Instructions
   //===--------------------------------------------------------------------===//
 
   PHINode *CreatePHI(Type *Ty, unsigned NumReservedValues,
                      const Twine &Name = "") {
-    return Insert(PHINode::Create(Ty, NumReservedValues), Name);
+    PHINode *Phi = PHINode::Create(Ty, NumReservedValues);
+    if (isa<FPMathOperator>(Phi))
+      Phi = cast<PHINode>(setFPAttrs(Phi, nullptr /* MDNode* */, FMF));
+    return Insert(Phi, Name);
   }
 
   CallInst *CreateCall(FunctionType *FTy, Value *Callee,
                        ArrayRef<Value *> Args = None, const Twine &Name = "",
                        MDNode *FPMathTag = nullptr) {
     CallInst *CI = CallInst::Create(FTy, Callee, Args, DefaultOperandBundles);
     if (isa<FPMathOperator>(CI))
       CI = cast<CallInst>(setFPAttrs(CI, FPMathTag, FMF));

llvm/trunk/include/llvm/IR/Operator.h

static bool classof(const Value *V) {
     if (auto *I = dyn_cast<Instruction>(V))
       Opcode = I->getOpcode();
     else if (auto *CE = dyn_cast<ConstantExpr>(V))
       Opcode = CE->getOpcode();
     else
       return false;
 
     switch (Opcode) {
+    // FIXME: To clean up and correct the semantics of fast-math-flags, FCmp
+    //        should not be treated as a math op, but the other opcodes should.
+    //        This would make things consistent with Select/PHI (FP value type
+    //        determines whether they are math ops and, therefore, capable of
+    //        having fast-math-flags).
     case Instruction::FCmp:
       return true;
     // non math FP Operators (no FMF)
     case Instruction::ExtractElement:
     case Instruction::ShuffleVector:
     case Instruction::InsertElement:
-    case Instruction::PHI:
       return false;
     default:
       return V->getType()->isFPOrFPVectorTy();
     }
   }
 };
 
 /// A helper template for defining operators for individual opcodes.

llvm/trunk/lib/Analysis/IVDescriptors.cpp

while (!Worklist.empty()) {
 
     // Any reduction instruction must be of one of the allowed kinds. We ignore
     // the starting value (the Phi or an AND instruction if the Phi has been
     // type-promoted).
     if (Cur != Start) {
       ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
       if (!ReduxDesc.isRecurrence())
         return false;
-      if (isa<FPMathOperator>(ReduxDesc.getPatternInst()))
+      // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
+      if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi)
         FMF &= ReduxDesc.getPatternInst()->getFastMathFlags();
     }
 
     bool IsASelect = isa<SelectInst>(Cur);
 
     // A conditional reduction operation must only have 2 or less uses in
     // VisitedInsts.
     if (IsASelect && (Kind == RK_FloatAdd || Kind == RK_FloatMult) &&

llvm/trunk/lib/AsmParser/LLParser.cpp

if (FMF.any()) {
       Inst->setFastMathFlags(FMF);
     }
     return 0;
   }
   case lltok::kw_va_arg:         return ParseVA_Arg(Inst, PFS);
   case lltok::kw_extractelement: return ParseExtractElement(Inst, PFS);
   case lltok::kw_insertelement:  return ParseInsertElement(Inst, PFS);
   case lltok::kw_shufflevector:  return ParseShuffleVector(Inst, PFS);
-  case lltok::kw_phi:            return ParsePHI(Inst, PFS);
+  case lltok::kw_phi: {
+    FastMathFlags FMF = EatFastMathFlagsIfPresent();
+    int Res = ParsePHI(Inst, PFS);
+    if (Res != 0)
+      return Res;
+    if (FMF.any()) {
+      if (!Inst->getType()->isFPOrFPVectorTy())
+        return Error(Loc, "fast-math-flags specified for phi without "
+                          "floating-point scalar or vector return type");
+      Inst->setFastMathFlags(FMF);
+    }
+    return 0;
+  }
   case lltok::kw_landingpad:     return ParseLandingPad(Inst, PFS);
   // Call.
   case lltok::kw_call:     return ParseCall(Inst, PFS, CallInst::TCK_None);
   case lltok::kw_tail:     return ParseCall(Inst, PFS, CallInst::TCK_Tail);
   case lltok::kw_musttail: return ParseCall(Inst, PFS, CallInst::TCK_MustTail);
   case lltok::kw_notail:   return ParseCall(Inst, PFS, CallInst::TCK_NoTail);
   // Memory.
   case lltok::kw_alloca:         return ParseAlloc(Inst, PFS);

llvm/trunk/lib/Bitcode/Reader/BitcodeReader.cpp

case bitc::FUNC_CODE_INST_CALLBR: {
       cast<CallBrInst>(I)->setAttributes(PAL);
       break;
     }
     case bitc::FUNC_CODE_INST_UNREACHABLE: // UNREACHABLE
       I = new UnreachableInst(Context);
       InstructionList.push_back(I);
       break;
     case bitc::FUNC_CODE_INST_PHI: { // PHI: [ty, val0,bb0, ...]
-      if (Record.size() < 1 || ((Record.size()-1)&1))
+      if (Record.size() < 1)
         return error("Invalid record");
+      // The first record specifies the type.
       FullTy = getFullyStructuredTypeByID(Record[0]);
       Type *Ty = flattenPointerTypes(FullTy);
       if (!Ty)
         return error("Invalid record");
 
-      PHINode *PN = PHINode::Create(Ty, (Record.size()-1)/2);
+      // Phi arguments are pairs of records of [value, basic block].
+      // There is an optional final record for fast-math-flags if this phi has a
+      // floating-point type.
+      size_t NumArgs = (Record.size() - 1) / 2;
+      if ((Record.size() - 1) % 2 == 1 && !Ty->isFloatingPointTy())
+        return error("Invalid record");
+
+      PHINode *PN = PHINode::Create(Ty, NumArgs);
       InstructionList.push_back(PN);
 
-      for (unsigned i = 0, e = Record.size()-1; i != e; i += 2) {
+      for (unsigned i = 0; i != NumArgs; i++) {
         Value *V;
         // With the new function encoding, it is possible that operands have
         // negative IDs (for forward references).  Use a signed VBR
         // representation to keep the encoding small.
         if (UseRelativeIDs)
-          V = getValueSigned(Record, 1+i, NextValueNo, Ty);
+          V = getValueSigned(Record, i * 2 + 1, NextValueNo, Ty);
         else
-          V = getValue(Record, 1+i, NextValueNo, Ty);
-        BasicBlock *BB = getBasicBlock(Record[2+i]);
+          V = getValue(Record, i * 2 + 1, NextValueNo, Ty);
+        BasicBlock *BB = getBasicBlock(Record[i * 2 + 2]);
         if (!V || !BB)
           return error("Invalid record");
         PN->addIncoming(V, BB);
       }
       I = PN;
+
+      // If there are an even number of records, the final record must be FMF.
+      if (Record.size() % 2 == 0) {
+        assert(isa<FPMathOperator>(I) && "Unexpected phi type");
+        FastMathFlags FMF = getDecodedFastMathFlags(Record[Record.size() - 1]);
+        if (FMF.any())
+          I->setFastMathFlags(FMF);
+      }
+
       break;
     }
 
     case bitc::FUNC_CODE_INST_LANDINGPAD:
     case bitc::FUNC_CODE_INST_LANDINGPAD_OLD: {
       // LANDINGPAD: [ty, val, val, num, (id0,val0 ...)?]
       unsigned Idx = 0;
       if (BitCode == bitc::FUNC_CODE_INST_LANDINGPAD) {

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

case Instruction::PHI: {
     // negative valued IDs.  This is most common for PHIs, so we use
     // signed VBRs.
     SmallVector<uint64_t, 128> Vals64;
     Vals64.push_back(VE.getTypeID(PN.getType()));
     for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
       pushValueSigned(PN.getIncomingValue(i), InstID, Vals64);
       Vals64.push_back(VE.getValueID(PN.getIncomingBlock(i)));
     }
+
+    uint64_t Flags = getOptimizationFlags(&I);
+    if (Flags != 0)
+      Vals64.push_back(Flags);
+
     // Emit a Vals64 vector and exit.
     Stream.EmitRecord(Code, Vals64, AbbrevToUse);
     Vals64.clear();
     return;
   }
 
   case Instruction::LandingPad: {
     const LandingPadInst &LP = cast<LandingPadInst>(I);

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

 }
 
 /// If we have a SelectInst that will likely profit from branch prediction,
 /// turn it into a branch.
 bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
   // If branch conversion isn't desirable, exit early.
   if (DisableSelectToBranch || OptSize || !TLI)
     return false;
-
+TLI->isSelectSupported(<#SelectSupportKind#>)
   // Find all consecutive select instructions that share the same condition.
   SmallVector<SelectInst *, 2> ASI;
   ASI.push_back(SI);
   for (BasicBlock::iterator It = ++BasicBlock::iterator(SI);
        It != SI->getParent()->end(); ++It) {
     SelectInst *I = dyn_cast<SelectInst>(&*It);
     if (I && SI->getCondition() == I->getCondition()) {
       ASI.push_back(I);

llvm/trunk/test/Bitcode/compatibility.ll

 define void @fastmathflags_vector_select(<2 x i1> %cond, <2 x double> %op1, <2 x double> %op2) {
   %f.nnan.nsz = select nnan nsz <2 x i1> %cond, <2 x double> %op1, <2 x double> %op2
   ; CHECK: %f.nnan.nsz = select nnan nsz <2 x i1> %cond, <2 x double> %op1, <2 x double> %op2
   %f.fast = select fast <2 x i1> %cond, <2 x double> %op1, <2 x double> %op2
   ; CHECK: %f.fast = select fast <2 x i1> %cond, <2 x double> %op1, <2 x double> %op2
   ret void
 }
 
+define void @fastmathflags_phi(i1 %cond, float %f1, float %f2, double %d1, double %d2, half %h1, half %h2) {
+entry:
+  br i1 %cond, label %L1, label %L2
+L1:
+  br label %exit
+L2:
+  br label %exit
+exit:
+  %p.nnan = phi nnan float [ %f1, %L1 ], [ %f2, %L2 ]
+  ; CHECK: %p.nnan = phi nnan float [ %f1, %L1 ], [ %f2, %L2 ]
+  %p.ninf = phi ninf double [ %d1, %L1 ], [ %d2, %L2 ]
+  ; CHECK: %p.ninf = phi ninf double [ %d1, %L1 ], [ %d2, %L2 ]
+  %p.contract = phi contract half [ %h1, %L1 ], [ %h2, %L2 ]
+  ; CHECK: %p.contract = phi contract half [ %h1, %L1 ], [ %h2, %L2 ]
+  %p.nsz.reassoc = phi reassoc nsz float [ %f1, %L1 ], [ %f2, %L2 ]
+  ; CHECK: %p.nsz.reassoc = phi reassoc nsz float [ %f1, %L1 ], [ %f2, %L2 ]
+  %p.fast = phi fast half [ %h2, %L1 ], [ %h1, %L2 ]
+  ; CHECK: %p.fast = phi fast half [ %h2, %L1 ], [ %h1, %L2 ]
+  ret void
+}
+
 ; Check various fast math flags and floating-point types on calls.
 
 declare float @fmf1()
 declare double @fmf2()
 declare <4 x double> @fmf3()
 
 ; CHECK-LABEL: fastMathFlagsForCalls(
 define void @fastMathFlagsForCalls(float %f, double %d1, <4 x double> %d2) {

llvm/trunk/unittests/IR/InstructionsTest.cpp

TEST(InstructionsTest, SkipDebug) {
   auto *Term = BB.getTerminator();
   EXPECT_EQ(Term, BB.begin()->getNextNonDebugInstruction());
   EXPECT_EQ(Term->getIterator(), skipDebugIntrinsics(BB.begin()));
 
   // After the terminator, there are no non-debug instructions.
   EXPECT_EQ(nullptr, Term->getNextNonDebugInstruction());
 }
 
-TEST(InstructionsTest, PhiIsNotFPMathOperator) {
+TEST(InstructionsTest, PhiMightNotBeFPMathOperator) {
   LLVMContext Context;
   IRBuilder<> Builder(Context);
   MDBuilder MDHelper(Context);
-  Instruction *I = Builder.CreatePHI(Builder.getDoubleTy(), 0);
+  Instruction *I = Builder.CreatePHI(Builder.getInt32Ty(), 0);
   EXPECT_FALSE(isa<FPMathOperator>(I));
   I->deleteValue();
+  Instruction *FP = Builder.CreatePHI(Builder.getDoubleTy(), 0);
+  EXPECT_TRUE(isa<FPMathOperator>(FP));
+  FP->deleteValue();
 }
 
 TEST(InstructionsTest, FNegInstruction) {
   LLVMContext Context;
   Type *FltTy = Type::getFloatTy(Context);
   Constant *One = ConstantFP::get(FltTy, 1.0);
   BinaryOperator *FAdd = BinaryOperator::CreateFAdd(One, One);
   FAdd->setHasNoNaNs(true);