Floating Point SCEV Analysis

[delena]

Summary

As we already discussed in llvm-dev forum http://lists.llvm.org/pipermail/llvm-dev/2016-May/099724.html
I'm working on FP SCEV analysis in order to enable loop vectorization with FP induction variables.
Trying to minimize the first patch, I implemented only simple cases. Once this patch is accepted, I continue to fill the gaps between integer and fp scevs.

this is the minimal test case I started from:
float fp_inc;

float x = init;
for (int i=0;i<N;i++){
  A[i] = x;
  x += fp_inc; // Loop invariant variable or constant
}

All optimizations and SCEV recurrence will come in the next patches.
I ran some tests to be sure that correctness is not broken.

[sanjoy]

Hi Elena,

I have made some minor comments inline, but I still stand by my earlier comment that we should do something like this as a last resort. As an initial step we should at least evaluate how far we can we can get on relevant workloads without teaching SCEV about floating point values at all.

../include/llvm/Analysis/ScalarEvolutionExpressions.h

286

What is the intent behind making SCEVFAddExpr and SCEVFMulExpr subclasses of SCEVNAryExpr? Does (a + b + c) represent ((a + b) + c) or (a + (b + c))?

../lib/Analysis/ScalarEvolution.cpp

1510

Note: getSExtValue will assert for integers that are large than 64 bits.

2561

Depending on how we define the associativity of an SCEVFAddExpr, this may or may not be valid.

2891

This is all duplicated code. If we go ahead with this, we should definitely common this with the integer version.

2911

I thought floating point in general isn't distributive?

[delena]

I still stand by my earlier comment that we should do something like this as a last resort.

It is very convenient way to answer all questions about FP variables that being changed and used inside loop.

../include/llvm/Analysis/ScalarEvolutionExpressions.h

286

I planned to use SCEVFAddExpr and SCEVFMulExpr to couple FP calculations, like it is done for integer operations.
for example: a + const1 + b + const2 = a + b + const3
or a * 0.0 = 0
If compiler supports FP reduction, it can support any FP simplification in this mode. I assume that fast-math should allow all these transformations.

../lib/Analysis/ScalarEvolution.cpp

1510

I'll fix. thank you.

2891

I thought about limitations in FP manipulations relatively to integer values. If fast-math allows all manipulations, we definitely can share the code.

[llvm-commits]

• msg-475-150.txt162 BDownload

[delena]

I implemented IV simplification for FP using FP SCEV. No the following loop is covered:

float x = init;
for (int i=0;i<N;i++){

A[i] = x;
x += fp_inc; // Loop invariant variable or constant

}

And the result is calculated as x = init + fp_inc*N

[sbaranga]

In D20695#446831, @delena wrote:

I implemented IV simplification for FP using FP SCEV. No the following loop is covered:

float x = init;
for (int i=0;i<N;i++){

A[i] = x;
x += fp_inc; // Loop invariant variable or constant

}

And the result is calculated as x = init + fp_inc*N

Hi Elena,

Replacing x with fp_inc*N should require fast-math - and it's not clear to me what fast-math allows.
If this is correct with fast-math, we should be able to use this to get the backedge taken count - which would be a good reason for doing this in SCEV.

I don't know if this has been established before, but the vectorization tests use FP re-association, so fast-math is also required there.

Thanks,
Silviu

[spatel]

In D20695#446877, @sbaranga wrote:

Replacing x with fp_inc*N should require fast-math - and it's not clear to me what fast-math allows.
If this is correct with fast-math, we should be able to use this to get the backedge taken count - which would be a good reason for doing this in SCEV.

I don't know if this has been established before, but the vectorization tests use FP re-association, so fast-math is also required there.

These are the same questions raised in PR27894:
https://llvm.org/bugs/show_bug.cgi?id=27894

An even simpler test case still raises questions if we support changes to the FP env:
https://llvm.org/bugs/show_bug.cgi?id=27899

[cc'ing @scanon for FP semantics questions]

[sanjoy]

In D20695#446877, @sbaranga wrote:

float x = init;
for (int i=0;i<N;i++){

A[i] = x;
x += fp_inc; // Loop invariant variable or constant

}

If this is correct with fast-math, we should be able to use this to
get the backedge taken count - which would be a good reason for doing
this in SCEV.

Shouldn't SCEV today be able to compute the backedge taken count of
the above loop (since the controlling induction variable is
integral)?

[sbaranga]

In D20695#447451, @sanjoy wrote:

In D20695#446877, @sbaranga wrote:

float x = init;
for (int i=0;i<N;i++){

A[i] = x;
x += fp_inc; // Loop invariant variable or constant

}

If this is correct with fast-math, we should be able to use this to
get the backedge taken count - which would be a good reason for doing
this in SCEV.

Shouldn't SCEV today be able to compute the backedge taken count of
the above loop (since the controlling induction variable is
integral)?

Hi Sanjoy,

For that loop, yes, SCEV should be able to figure out the backedge taken count today.

But using that reasoning I think we should be able to get the backedge taken count for the following loop (again, I don't know if this is actually correct):

float i = 0.f;
for (; i < N; i+=fp_inc) {}

This was something previously raised by Michael on the llvm-dev thread.

[delena]

In D20695#447673, @sbaranga wrote:

In D20695#447451, @sanjoy wrote:

In D20695#446877, @sbaranga wrote:

float x = init;
for (int i=0;i<N;i++){

A[i] = x;
x += fp_inc; // Loop invariant variable or constant

}

If this is correct with fast-math, we should be able to use this to
get the backedge taken count - which would be a good reason for doing
this in SCEV.

Shouldn't SCEV today be able to compute the backedge taken count of
the above loop (since the controlling induction variable is
integral)?

Hi Sanjoy,

For that loop, yes, SCEV should be able to figure out the backedge taken count today.

But using that reasoning I think we should be able to get the backedge taken count for the following loop (again, I don't know if this is actually correct):

float i = 0.f;
for (; i < N; i+=fp_inc) {}

This was something previously raised by Michael on the llvm-dev thread.

Yes, it is possible with FP SCEV. I implemented fp-range and backedge taken count calculation, but I don't want to put everything in this patch.
Community should also decide about the flag, whether it will be "-ffast-math" or something else.

[delena]

The FP SCEV concept is rejected.

../include/llvm/Analysis/ScalarEvolution.h

public:
 
     /// Return a SCEV expression for the full generality of the specified
     /// expression.
     const SCEV *getSCEV(Value *V);
 
     const SCEV *getConstant(ConstantInt *V);
     const SCEV *getConstant(const APInt& Val);
     const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
+    const SCEV *getFpConstant(ConstantFP *V);
+    const SCEV *getFpConstant(const APFloat& Val);
+    const SCEV *getFpConstant(Type *Ty, double V);
     const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty);
     const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty);
+    const SCEV *getSIToFPExpr(const SCEV *Op, Type *Ty);
     const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty);
     const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
     const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                            SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
     const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
                            SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
       SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
       return getAddExpr(Ops, Flags);
     }
     const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
                            SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
       SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
       return getAddExpr(Ops, Flags);
     }
+    const SCEV *getFAddExpr(SmallVectorImpl<const SCEV *> &Ops);
+    const SCEV *getFAddExpr(const SCEV *LHS, const SCEV *RHS) {
+      SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
+      return getFAddExpr(Ops);
+    }
+    const SCEV *getFAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2) {
+      SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
+      return getFAddExpr(Ops);
+    }
     const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
                            SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
     const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
                            SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
       SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
       return getMulExpr(Ops, Flags);
     }
     const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
                            SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
       SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
       return getMulExpr(Ops, Flags);
     }
+    const SCEV *getFMulExpr(SmallVectorImpl<const SCEV *> &Ops);
+    const SCEV *getFMulExpr(const SCEV *LHS, const SCEV *RHS) {
+      SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
+      return getFMulExpr(Ops);
+    }
+    const SCEV *getFMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2) {
+      SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
+      return getFMulExpr(Ops);
+    }
     const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
     const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
     const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step,
                               const Loop *L, SCEV::NoWrapFlags Flags);
     const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
                               const Loop *L, SCEV::NoWrapFlags Flags);
     const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
                               const Loop *L, SCEV::NoWrapFlags Flags) {
       SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
       return getAddRecExpr(NewOp, L, Flags);
     }
+    const SCEV *getFAddRecExpr(const SCEV *Start, const SCEV *Step,
+                               const Loop *L);
+    const SCEV *getFAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
+                               const Loop *L);
+    const SCEV *getFAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
+                               const Loop *L) {
+      SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
+      return getFAddRecExpr(NewOp, L);
+    }
     /// Returns an expression for a GEP
     ///
     /// \p PointeeType The type used as the basis for the pointer arithmetics
     /// \p BaseExpr The expression for the pointer operand.
     /// \p IndexExprs The expressions for the indices.
     /// \p InBounds Whether the GEP is in bounds.
     const SCEV *getGEPExpr(Type *PointeeType, const SCEV *BaseExpr,
                            const SmallVectorImpl<const SCEV *> &IndexExprs,
public:
     ///
     const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo);
 
     /// Return the SCEV object corresponding to -V.
     ///
     const SCEV *getNegativeSCEV(const SCEV *V,
                                 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
 
+    /// Return the FP SCEV object corresponding to -V.
+    ///
+    const SCEV *getNegativeFpSCEV(const SCEV *V);
+
     /// Return the SCEV object corresponding to ~V.
     ///
     const SCEV *getNotSCEV(const SCEV *V);
 
     /// Return LHS-RHS.  Minus is represented in SCEV as A+B*-1.
     const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
                              SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
 

../include/llvm/Analysis/ScalarEvolutionExpander.h

private:
     /// into the program.  The inserted code is inserted into the SCEVExpander's
     /// current insertion point. If a type is specified, the result will be
     /// expanded to have that type, with a cast if necessary.
     Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
 
     /// \brief Determine the most "relevant" loop for the given SCEV.
     const Loop *getRelevantLoop(const SCEV *);
 
-    Value *visitConstant(const SCEVConstant *S) {
+    Value *visitConstant(const SCEVIntOrFpConstant *S) {
       return S->getValue();
     }
 
     Value *visitTruncateExpr(const SCEVTruncateExpr *S);
 
     Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
 
     Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
private:
     Value *visitSMaxExpr(const SCEVSMaxExpr *S);
 
     Value *visitUMaxExpr(const SCEVUMaxExpr *S);
 
     Value *visitUnknown(const SCEVUnknown *S) {
       return S->getValue();
     }
 
+    Value *visitFAddExpr(const SCEVFAddExpr *S);
+
+    Value *visitFMulExpr(const SCEVFMulExpr *S);
+
+    Value *visitSintToFpExpr(const SCEVSintToFpExpr *S);
+
+    Value *visitFAddRecExpr(const SCEVFAddRecExpr *S);
+
     void rememberInstruction(Value *I);
 
     bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
 
     bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
 
     Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
     PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,

../include/llvm/Analysis/ScalarEvolutionExpressions.h

 namespace llvm {
   class ConstantInt;
   class ConstantRange;
   class DominatorTree;
 
   enum SCEVTypes {
     // These should be ordered in terms of increasing complexity to make the
     // folders simpler.
-    scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
-    scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr,
-    scUnknown, scCouldNotCompute
+    scConstant, scFpConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr,
+    scMulExpr, scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scSintToFp,
+    scFAddExpr, scFMulExpr, scFAddRecExpr, scUnknown, scCouldNotCompute
+  };
+
+  /// This class represents a constant integer or Fp value.
+  class SCEVIntOrFpConstant : public SCEV {
+    friend class ScalarEvolution;
+  protected:
+    Constant *V;
+    SCEVIntOrFpConstant(const FoldingSetNodeIDRef ID, SCEVTypes T, Constant *v) :
+      SCEV(ID, T), V(v) {
+    }
+  public:
+    Constant *getValue() const { return V; }
+
+    Type *getType() const { return V->getType(); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scConstant ||
+             S->getSCEVType() == scFpConstant;
+    }
   };
 
   /// This class represents a constant integer value.
-  class SCEVConstant : public SCEV {
+  class SCEVConstant : public SCEVIntOrFpConstant {
     friend class ScalarEvolution;
 
-    ConstantInt *V;
     SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) :
-      SCEV(ID, scConstant), V(v) {}
+      SCEVIntOrFpConstant(ID, scConstant, v) {
+    }
   public:
-    ConstantInt *getValue() const { return V; }
+    ConstantInt *getValue() const { return cast<ConstantInt>(V); }
     const APInt &getAPInt() const { return getValue()->getValue(); }
 
     Type *getType() const { return V->getType(); }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scConstant;
     }
   };
 
+  /// This class represents a constant floating point value.
+  class SCEVFpConstant : public SCEVIntOrFpConstant {
+    friend class ScalarEvolution;
+
+    SCEVFpConstant(const FoldingSetNodeIDRef ID, ConstantFP *v) :
+      SCEVIntOrFpConstant(ID, scFpConstant, v) {
+    }
+  public:
+    ConstantFP *getValue() const { return cast<ConstantFP>(V); }
+    const APFloat &getAPFloat() const { return getValue()->getValueAPF(); }
+
+    Type *getType() const { return V->getType(); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scFpConstant;
+    }
+  };
+
   /// This is the base class for unary cast operator classes.
   class SCEVCastExpr : public SCEV {
   protected:
     const SCEV *Op;
     Type *Ty;
 
     SCEVCastExpr(const FoldingSetNodeIDRef ID,
                  unsigned SCEVTy, const SCEV *op, Type *ty);
 
   public:
     const SCEV *getOperand() const { return Op; }
     Type *getType() const { return Ty; }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scTruncate ||
              S->getSCEVType() == scZeroExtend ||
-             S->getSCEVType() == scSignExtend;
+             S->getSCEVType() == scSignExtend ||
+             S->getSCEVType() == scSintToFp;
     }
   };
 
   /// This class represents a truncation of an integer value to a
   /// smaller integer value.
   class SCEVTruncateExpr : public SCEVCastExpr {
     friend class ScalarEvolution;
 
     SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
                      const SCEV *op, Type *ty);
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scTruncate;
     }
   };
 
+  /// This class represents a signed int to FP conversion
+  class SCEVSintToFpExpr : public SCEVCastExpr {
+    friend class ScalarEvolution;
+
+    SCEVSintToFpExpr(const FoldingSetNodeIDRef ID,
+                       const SCEV *op, Type *ty);
+
+  public:
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scSintToFp;
+    }
+  };
+
   /// This class represents a zero extension of a small integer value
   /// to a larger integer value.
   class SCEVZeroExtendExpr : public SCEVCastExpr {
     friend class ScalarEvolution;
 
     SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
                        const SCEV *op, Type *ty);
 
public:
     }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scAddExpr ||
              S->getSCEVType() == scMulExpr ||
              S->getSCEVType() == scSMaxExpr ||
              S->getSCEVType() == scUMaxExpr ||
-             S->getSCEVType() == scAddRecExpr;
+             S->getSCEVType() == scAddRecExpr ||
+             S->getSCEVType() == scFAddRecExpr ||
+             S->getSCEVType() == scFAddExpr ||
+             S->getSCEVType() == scFMulExpr;
     }
   };
 
   /// This node is the base class for n'ary commutative operators.
   class SCEVCommutativeExpr : public SCEVNAryExpr {
   protected:
     SCEVCommutativeExpr(const FoldingSetNodeIDRef ID,
                         enum SCEVTypes T, const SCEV *const *O, size_t N)
       : SCEVNAryExpr(ID, T, O, N) {}
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scAddExpr ||
              S->getSCEVType() == scMulExpr ||
              S->getSCEVType() == scSMaxExpr ||
-             S->getSCEVType() == scUMaxExpr;
+             S->getSCEVType() == scUMaxExpr ||
+             S->getSCEVType() == scFAddExpr ||
+             S->getSCEVType() == scFMulExpr;
     }
 
     /// Set flags for a non-recurrence without clearing previously set flags.
     void setNoWrapFlags(NoWrapFlags Flags) {
       SubclassData |= Flags;
     }
   };
 
public:
     }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scAddExpr;
     }
   };
 
+  /// This node represents an addition of some number of FP SCEVs.
+  class SCEVFAddExpr : public SCEVCommutativeExpr {
+    friend class ScalarEvolution;
+
+    SCEVFAddExpr(const FoldingSetNodeIDRef ID,
+                 const SCEV *const *O, size_t N)
+                 : SCEVCommutativeExpr(ID, scFAddExpr, O, N) {
+    }
+
+  public:
+    Type *getType() const {
+      // Use the type of the last operand, which is likely to be a pointer
+      // type, if there is one. This doesn't usually matter, but it can help
+      // reduce casts when the expressions are expanded.
+      return getOperand(getNumOperands() - 1)->getType();
+    }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scFAddExpr;
+    }
+  };
+
 
   /// This node represents multiplication of some number of SCEVs.
   class SCEVMulExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
     SCEVMulExpr(const FoldingSetNodeIDRef ID,
                 const SCEV *const *O, size_t N)
       : SCEVCommutativeExpr(ID, scMulExpr, O, N) {
     }
 
   public:
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scMulExpr;
     }
   };
 
+  /// This node represents multiplication of some number of FP SCEVs.
+  class SCEVFMulExpr : public SCEVCommutativeExpr {
+    friend class ScalarEvolution;
+
+    SCEVFMulExpr(const FoldingSetNodeIDRef ID,
+                const SCEV *const *O, size_t N)
+                : SCEVCommutativeExpr(ID, scFMulExpr, O, N) {
+    }
+
+  public:
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scFMulExpr;
+    }
+  };
 
   /// This class represents a binary unsigned division operation.
   class SCEVUDivExpr : public SCEV {
     friend class ScalarEvolution;
 
     const SCEV *LHS;
     const SCEV *RHS;
     SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
public:
     }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scUDivExpr;
     }
   };
 
+  /// This node represents a polynomial recurrence.
+  /// All operands of a recurrent expression are required to be loop invariant.
+  class SCEVRecExpr : public SCEVNAryExpr {
+    const Loop *L;
+  protected:
+    SCEVRecExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T,
+      const SCEV *const *O, size_t N, const Loop *l)
+      : SCEVNAryExpr(ID, T, O, N), L(l) {
+    }
+
+  public:
+    const SCEV *getStart() const { return Operands[0]; }
+    const Loop *getLoop() const { return L; }
+
+    /// Return true if this represents an expression
+    /// A + B*x where A and B are loop invariant values.
+    bool isAffine() const {
+      // We know that the start value is invariant.  This expression is thus
+      // affine iff the step is also invariant.
+      return getNumOperands() == 2;
+    }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scAddRecExpr ||
+        S->getSCEVType() == scFAddRecExpr;
+    }
+  };
 
   /// This node represents a polynomial recurrence on the trip count
   /// of the specified loop.  This is the primary focus of the
   /// ScalarEvolution framework; all the other SCEV subclasses are
   /// mostly just supporting infrastructure to allow SCEVAddRecExpr
   /// expressions to be created and analyzed.
   ///
   /// All operands of an AddRec are required to be loop invariant.
   ///
-  class SCEVAddRecExpr : public SCEVNAryExpr {
+  class SCEVAddRecExpr : public SCEVRecExpr {
     friend class ScalarEvolution;
 
-    const Loop *L;
-
     SCEVAddRecExpr(const FoldingSetNodeIDRef ID,
                    const SCEV *const *O, size_t N, const Loop *l)
-      : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {}
+                   : SCEVRecExpr(ID, scAddRecExpr, O, N, l) {}
 
   public:
-    const SCEV *getStart() const { return Operands[0]; }
-    const Loop *getLoop() const { return L; }
 
     /// Constructs and returns the recurrence indicating how much this
     /// expression steps by.  If this is a polynomial of degree N, it
     /// returns a chrec of degree N-1.  We cannot determine whether
     /// the step recurrence has self-wraparound.
     const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
       if (isAffine()) return getOperand(1);
       return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
                                                            op_end()),
                               getLoop(), FlagAnyWrap);
     }
 
-    /// Return true if this represents an expression A + B*x where A
-    /// and B are loop invariant values.
-    bool isAffine() const {
-      // We know that the start value is invariant.  This expression is thus
-      // affine iff the step is also invariant.
-      return getNumOperands() == 2;
-    }
-
     /// Return true if this represents an expression A + B*x + C*x^2
     /// where A, B and C are loop invariant values.  This corresponds
     /// to an addrec of the form {L,+,M,+,N}
     bool isQuadratic() const {
       return getNumOperands() == 3;
     }
 
     /// Set flags for a recurrence without clearing any previously set flags.
public:
     }
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const SCEV *S) {
       return S->getSCEVType() == scAddRecExpr;
     }
   };
 
+  /// This node represents a polynomial recurrence
+  /// of FP induction variable of the specified loop.
+  ///
+  /// All operands of an FAddRec are required to be loop invariant.
+  class SCEVFAddRecExpr : public SCEVRecExpr {
+    friend class ScalarEvolution;
+
+    SCEVFAddRecExpr(const FoldingSetNodeIDRef ID,
+                    const SCEV *const *O, size_t N, const Loop *l)
+                    : SCEVRecExpr(ID, scFAddRecExpr, O, N, l) {
+    }
+
+  public:
+    const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
+      if (isAffine()) return getOperand(1);
+      return SE.getFAddRecExpr(SmallVector<const SCEV *, 3>(op_begin() + 1,
+                               op_end()), getLoop());
+    }
+
+    /// Return the value of this chain of recurrences at the specified
+    /// iteration number.
+    const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
+
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scFAddRecExpr;
+    }
+  };
+
   /// This class represents a signed maximum selection.
   class SCEVSMaxExpr : public SCEVCommutativeExpr {
     friend class ScalarEvolution;
 
     SCEVSMaxExpr(const FoldingSetNodeIDRef ID,
                  const SCEV *const *O, size_t N)
       : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) {
       // Max never overflows.
namespace llvm {
 
   /// This class defines a simple visitor class that may be used for
   /// various SCEV analysis purposes.
   template<typename SC, typename RetVal=void>
   struct SCEVVisitor {
     RetVal visit(const SCEV *S) {
       switch (S->getSCEVType()) {
       case scConstant:
-        return ((SC*)this)->visitConstant((const SCEVConstant*)S);
+      case scFpConstant:
+        return ((SC*)this)->visitConstant((const SCEVIntOrFpConstant*)S);
       case scTruncate:
         return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
       case scZeroExtend:
         return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
       case scSignExtend:
         return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
+      case scSintToFp:
+        return ((SC*)this)->visitSintToFpExpr((const SCEVSintToFpExpr*)S);
       case scAddExpr:
         return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
+      case scFAddExpr:
+        return ((SC*)this)->visitFAddExpr((const SCEVFAddExpr*)S);
       case scMulExpr:
         return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
+      case scFMulExpr:
+        return ((SC*)this)->visitFMulExpr((const SCEVFMulExpr*)S);
       case scUDivExpr:
         return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
       case scAddRecExpr:
         return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
+      case scFAddRecExpr:
+        return ((SC*)this)->visitFAddRecExpr((const SCEVFAddRecExpr*)S);
       case scSMaxExpr:
         return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
       case scUMaxExpr:
         return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
       case scUnknown:
         return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
       case scCouldNotCompute:
         return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
public:
 
     void visitAll(const SCEV *Root) {
       push(Root);
       while (!Worklist.empty() && !Visitor.isDone()) {
         const SCEV *S = Worklist.pop_back_val();
 
         switch (S->getSCEVType()) {
         case scConstant:
+        case scFpConstant:
         case scUnknown:
           break;
         case scTruncate:
         case scZeroExtend:
         case scSignExtend:
+        case scSintToFp:
           push(cast<SCEVCastExpr>(S)->getOperand());
           break;
         case scAddExpr:
+        case scFAddExpr:
         case scMulExpr:
+        case scFMulExpr:
         case scSMaxExpr:
         case scUMaxExpr:
         case scAddRecExpr:
-    for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
-      push(Op);
+        case scFAddRecExpr:
+          for (const auto *Op : cast<SCEVNAryExpr>(S)->operands())
+            push(Op);
           break;
         case scUDivExpr: {
           const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
           push(UDiv->getLHS());
           push(UDiv->getRHS());
           break;
         }
         case scCouldNotCompute:
namespace llvm {
   /// Recursively visits a SCEV expression and re-writes it.
   template<typename SC>
   class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
   protected:
     ScalarEvolution &SE;
   public:
     SCEVRewriteVisitor(ScalarEvolution &SE) : SE(SE) {}
 
-    const SCEV *visitConstant(const SCEVConstant *Constant) {
+    const SCEV *visitConstant(const SCEVIntOrFpConstant *Constant) {
       return Constant;
     }
 
     const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
       return SE.getTruncateExpr(Operand, Expr->getType());
     }
 
     const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
       return SE.getZeroExtendExpr(Operand, Expr->getType());
     }
 
     const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
       return SE.getSignExtendExpr(Operand, Expr->getType());
     }
 
+    const SCEV *visitSintToFpExpr(const SCEVSintToFpExpr *Expr) {
+      const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
+      return SE.getSIToFPExpr(Operand, Expr->getType());
+    }
+
     const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
       SmallVector<const SCEV *, 2> Operands;
       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
         Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
       return SE.getAddExpr(Operands);
     }
 
+    const SCEV *visitFAddExpr(const SCEVFAddExpr *Expr) {
+      SmallVector<const SCEV *, 2> Operands;
+      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
+        Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
+      return SE.getFAddExpr(Operands);
+    }
+
     const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
       SmallVector<const SCEV *, 2> Operands;
       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
         Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
       return SE.getMulExpr(Operands);
     }
 
+    const SCEV *visitFMulExpr(const SCEVFMulExpr *Expr) {
+      SmallVector<const SCEV *, 2> Operands;
+      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
+        Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
+      return SE.getFMulExpr(Operands);
+    }
+
     const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
       return SE.getUDivExpr(((SC*)this)->visit(Expr->getLHS()),
                             ((SC*)this)->visit(Expr->getRHS()));
     }
 
     const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
       SmallVector<const SCEV *, 2> Operands;
       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
         Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
       return SE.getAddRecExpr(Operands, Expr->getLoop(),
                               Expr->getNoWrapFlags());
     }
 
+    const SCEV *visitFAddRecExpr(const SCEVFAddRecExpr *Expr) {
+      SmallVector<const SCEV *, 2> Operands;
+      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
+        Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
+      return SE.getFAddRecExpr(Operands, Expr->getLoop());
+    }
+
     const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
       SmallVector<const SCEV *, 2> Operands;
       for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
         Operands.push_back(((SC*)this)->visit(Expr->getOperand(i)));
       return SE.getSMaxExpr(Operands);
     }
 
     const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {

../include/llvm/Transforms/Utils/LoopUtils.h

 
 /// A struct for saving information about induction variables.
 class InductionDescriptor {
 public:
   /// This enum represents the kinds of inductions that we support.
   enum InductionKind {
     IK_NoInduction,  ///< Not an induction variable.
     IK_IntInduction, ///< Integer induction variable. Step = C.
-    IK_PtrInduction  ///< Pointer induction var. Step = C / sizeof(elem).
+    IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
+    IK_FpInduction   ///< Floating point induction variable.
   };
 
 public:
   /// Default constructor - creates an invalid induction.
   InductionDescriptor()
       : StartValue(nullptr), IK(IK_NoInduction), Step(nullptr) {}
 
   /// Get the consecutive direction. Returns:
public:
   /// the induction descriptor \p D will contain the data describing this
   /// induction. If by some other means the caller has a better SCEV
   /// expression for \p Phi than the one returned by the ScalarEvolution
   /// analysis, it can be passed through \p Expr.
   static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
                              InductionDescriptor &D,
                              const SCEV *Expr = nullptr);
 
+  /// Returns true if \p Phi is a floating point induction.
+  /// If \p Phi is an induction, the induction descriptor \p D will contain 
+  /// the data describing this induction.
+  static bool isFpInductionPHI(PHINode *Phi, ScalarEvolution *SE,
+                               InductionDescriptor &D);
+
   /// Returns true if \p Phi is an induction, in the context associated with
   /// the run-time predicate of PSE. If \p Assume is true, this can add further
   /// SCEV predicates to \p PSE in order to prove that \p Phi is an induction.
   /// If \p Phi is an induction, \p D will contain the data describing this
   /// induction.
   static bool isInductionPHI(PHINode *Phi, PredicatedScalarEvolution &PSE,
                              InductionDescriptor &D, bool Assume = false);
 

../lib/Analysis/IVUsers.cpp

bool IVUsers::AddUsersImpl(Instruction *I,
                            SmallPtrSetImpl<Loop*> &SimpleLoopNests) {
   const DataLayout &DL = I->getModule()->getDataLayout();
 
   // Add this IV user to the Processed set before returning false to ensure that
   // all IV users are members of the set. See IVUsers::isIVUserOrOperand.
   if (!Processed.insert(I).second)
     return true;    // Instruction already handled.
 
-  if (!SE->isSCEVable(I->getType()))
+  if (!SE->isSCEVable(I->getType()) || I->getType()->isFloatingPointTy())
     return false;   // Void and FP expressions cannot be reduced.
 
   // IVUsers is used by LSR which assumes that all SCEV expressions are safe to
   // pass to SCEVExpander. Expressions are not safe to expand if they represent
   // operations that are not safe to speculate, namely integer division.
   if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I))
     return false;
 

../lib/Analysis/ScalarEvolution.cpp

void SCEV::dump() const {
   dbgs() << '\n';
 }
 
 void SCEV::print(raw_ostream &OS) const {
   switch (static_cast<SCEVTypes>(getSCEVType())) {
   case scConstant:
     cast<SCEVConstant>(this)->getValue()->printAsOperand(OS, false);
     return;
+  case scFpConstant:
+    cast<SCEVFpConstant>(this)->getValue()->printAsOperand(OS, false);
+    return;
   case scTruncate: {
     const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(this);
     const SCEV *Op = Trunc->getOperand();
     OS << "(trunc " << *Op->getType() << " " << *Op << " to "
        << *Trunc->getType() << ")";
     return;
   }
   case scZeroExtend: {
     const SCEVZeroExtendExpr *ZExt = cast<SCEVZeroExtendExpr>(this);
     const SCEV *Op = ZExt->getOperand();
     OS << "(zext " << *Op->getType() << " " << *Op << " to "
        << *ZExt->getType() << ")";
     return;
   }
   case scSignExtend: {
     const SCEVSignExtendExpr *SExt = cast<SCEVSignExtendExpr>(this);
     const SCEV *Op = SExt->getOperand();
     OS << "(sext " << *Op->getType() << " " << *Op << " to "
        << *SExt->getType() << ")";
     return;
   }
+  case scSintToFp: {
+    const SCEVSintToFpExpr *SintToFp = cast<SCEVSintToFpExpr>(this);
+    const SCEV *Op = SintToFp->getOperand();
+    OS << "(sitofp " << *Op->getType() << " " << *Op << " to "
+      << *SintToFp->getType() << ")";
+    return;
+  }
   case scAddRecExpr: {
     const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(this);
     OS << "{" << *AR->getOperand(0);
     for (unsigned i = 1, e = AR->getNumOperands(); i != e; ++i)
       OS << ",+," << *AR->getOperand(i);
     OS << "}<";
     if (AR->hasNoUnsignedWrap())
       OS << "nuw><";
     if (AR->hasNoSignedWrap())
       OS << "nsw><";
     if (AR->hasNoSelfWrap() &&
         !AR->getNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)))
       OS << "nw><";
     AR->getLoop()->getHeader()->printAsOperand(OS, /*PrintType=*/false);
     OS << ">";
     return;
   }
+  case scFAddRecExpr: {
+    const SCEVFAddRecExpr *AR = cast<SCEVFAddRecExpr>(this);
+    OS << "{" << *AR->getOperand(0);
+    for (unsigned i = 1, e = AR->getNumOperands(); i != e; ++i)
+      OS << ",+," << *AR->getOperand(i);
+    OS << "}<";
+    AR->getLoop()->getHeader()->printAsOperand(OS, /*PrintType=*/false);
+    OS << ">";
+    return;
+  }
   case scAddExpr:
   case scMulExpr:
+  case scFAddExpr:
+  case scFMulExpr:
   case scUMaxExpr:
   case scSMaxExpr: {
     const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(this);
     const char *OpStr = nullptr;
     switch (NAry->getSCEVType()) {
+    case scFAddExpr:
     case scAddExpr: OpStr = " + "; break;
+    case scFMulExpr:
     case scMulExpr: OpStr = " * "; break;
     case scUMaxExpr: OpStr = " umax "; break;
     case scSMaxExpr: OpStr = " smax "; break;
     }
     OS << "(";
     for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
          I != E; ++I) {
       OS << **I;
case scCouldNotCompute:
     return;
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
 Type *SCEV::getType() const {
   switch (static_cast<SCEVTypes>(getSCEVType())) {
   case scConstant:
-    return cast<SCEVConstant>(this)->getType();
+  case scFpConstant:
+    return cast<SCEVIntOrFpConstant>(this)->getType();
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
+  case scSintToFp:
     return cast<SCEVCastExpr>(this)->getType();
+  case scFAddRecExpr:
   case scAddRecExpr:
   case scMulExpr:
+  case scFMulExpr:
   case scUMaxExpr:
   case scSMaxExpr:
     return cast<SCEVNAryExpr>(this)->getType();
   case scAddExpr:
     return cast<SCEVAddExpr>(this)->getType();
+  case scFAddExpr:
+    return cast<SCEVFAddExpr>(this)->getType();
   case scUDivExpr:
     return cast<SCEVUDivExpr>(this)->getType();
   case scUnknown:
     return cast<SCEVUnknown>(this)->getType();
   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
   }
   llvm_unreachable("Unknown SCEV kind!");

 
 SCEVCouldNotCompute::SCEVCouldNotCompute() :
   SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {}
 
 bool SCEVCouldNotCompute::classof(const SCEV *S) {
   return S->getSCEVType() == scCouldNotCompute;
 }
 
+const SCEV *ScalarEvolution::getFpConstant(ConstantFP *V) {
+  FoldingSetNodeID ID;
+  ID.AddInteger(scFpConstant);
+  ID.AddPointer(V);
+  void *IP = nullptr;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+    return S;
+  SCEV *S = new (SCEVAllocator)SCEVFpConstant(ID.Intern(SCEVAllocator), V);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
+}
+
 const SCEV *ScalarEvolution::getConstant(ConstantInt *V) {
   FoldingSetNodeID ID;
   ID.AddInteger(scConstant);
   ID.AddPointer(V);
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V);
   UniqueSCEVs.InsertNode(S, IP);
   return S;
 }
 
 const SCEV *ScalarEvolution::getConstant(const APInt &Val) {
   return getConstant(ConstantInt::get(getContext(), Val));
 }
 
 const SCEV *
 ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool isSigned) {
   IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty));
   return getConstant(ConstantInt::get(ITy, V, isSigned));
 }
 
+const SCEV *ScalarEvolution::getFpConstant(Type *Ty, double Value) {
+  return getFpConstant(cast<ConstantFP>(ConstantFP::get(Ty, Value)));
+}
+
+const SCEV *ScalarEvolution::getFpConstant(const APFloat &Val) {
+  return getFpConstant(ConstantFP::get(getContext(), Val));
+}
+
 SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID,
                            unsigned SCEVTy, const SCEV *op, Type *ty)
   : SCEV(ID, SCEVTy), Op(op), Ty(ty) {}
 
+SCEVSintToFpExpr::SCEVSintToFpExpr(const FoldingSetNodeIDRef ID,
+                                   const SCEV *op, Type *ty)
+  : SCEVCastExpr(ID, scSintToFp, op, ty) {
+  assert(Op->getType()->isIntegerTy() && ty->isFloatingPointTy() &&
+         "Unexpected type for sitofp operation");
+}
+
 SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
                                    const SCEV *op, Type *ty)
   : SCEVCastExpr(ID, scTruncate, op, ty) {
   assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
          "Cannot truncate non-integer value!");
 }
 
case scConstant: {
       const APInt &LA = LC->getAPInt();
       const APInt &RA = RC->getAPInt();
       unsigned LBitWidth = LA.getBitWidth(), RBitWidth = RA.getBitWidth();
       if (LBitWidth != RBitWidth)
         return (int)LBitWidth - (int)RBitWidth;
       return LA.ult(RA) ? -1 : 1;
     }
 
+    case scFpConstant:
+      // Return 1 because analysis of FP expressions is not implemented yet.
+      return 1;
+
+    case scFAddRecExpr:
     case scAddRecExpr: {
-      const SCEVAddRecExpr *LA = cast<SCEVAddRecExpr>(LHS);
-      const SCEVAddRecExpr *RA = cast<SCEVAddRecExpr>(RHS);
+      const SCEVRecExpr *LA = cast<SCEVRecExpr>(LHS);
+      const SCEVRecExpr *RA = cast<SCEVRecExpr>(RHS);
 
       // Compare addrec loop depths.
       const Loop *LLoop = LA->getLoop(), *RLoop = RA->getLoop();
       if (LLoop != RLoop) {
         unsigned LDepth = LLoop->getLoopDepth(),
           RDepth = RLoop->getLoopDepth();
         if (LDepth != RDepth)
           return (int)LDepth - (int)RDepth;
       }
 
       // Addrec complexity grows with operand count.
       unsigned LNumOps = LA->getNumOperands(), RNumOps = RA->getNumOperands();
       if (LNumOps != RNumOps)
         return (int)LNumOps - (int)RNumOps;
 
       // Lexicographically compare.
       for (unsigned i = 0; i != LNumOps; ++i) {
         long X = compare(LA->getOperand(i), RA->getOperand(i));
         if (X != 0)
           return X;
       }
 
       return 0;
     }
-
     case scAddExpr:
     case scMulExpr:
     case scSMaxExpr:
-    case scUMaxExpr: {
+    case scUMaxExpr:
+    case scFAddExpr:
+    case scFMulExpr: {
       const SCEVNAryExpr *LC = cast<SCEVNAryExpr>(LHS);
       const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS);
 
       // Lexicographically compare n-ary expressions.
       unsigned LNumOps = LC->getNumOperands(), RNumOps = RC->getNumOperands();
       if (LNumOps != RNumOps)
         return (int)LNumOps - (int)RNumOps;
 
case scUDivExpr: {
       long X = compare(LC->getLHS(), RC->getLHS());
       if (X != 0)
         return X;
       return compare(LC->getRHS(), RC->getRHS());
     }
 
     case scTruncate:
     case scZeroExtend:
-    case scSignExtend: {
+    case scSignExtend:
+    case scSintToFp: {
       const SCEVCastExpr *LC = cast<SCEVCastExpr>(LHS);
       const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS);
 
       // Compare cast expressions by operand.
       return compare(LC->getOperand(), RC->getOperand());
     }
 
     case scCouldNotCompute:
public:
   void visitTruncateExpr(const SCEVTruncateExpr *Numerator) {}
   void visitZeroExtendExpr(const SCEVZeroExtendExpr *Numerator) {}
   void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {}
   void visitUDivExpr(const SCEVUDivExpr *Numerator) {}
   void visitSMaxExpr(const SCEVSMaxExpr *Numerator) {}
   void visitUMaxExpr(const SCEVUMaxExpr *Numerator) {}
   void visitUnknown(const SCEVUnknown *Numerator) {}
   void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {}
-
-  void visitConstant(const SCEVConstant *Numerator) {
+  void visitFMulExpr(const SCEVFMulExpr *Numerator) {}
+  void visitFAddExpr(const SCEVFAddExpr *Numerator) {}
+  void visitFAddRecExpr(const SCEVFAddRecExpr *Numerator) {}
+  void visitSintToFpExpr(const SCEVSintToFpExpr *Numerator) {}
+
+  void visitConstant(const SCEVIntOrFpConstant *ConstNumerator) {
+    const SCEVConstant *Numerator = dyn_cast<SCEVConstant>(ConstNumerator);
+    if (!Numerator)
+      return;
     if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
       APInt NumeratorVal = Numerator->getAPInt();
       APInt DenominatorVal = D->getAPInt();
       uint32_t NumeratorBW = NumeratorVal.getBitWidth();
       uint32_t DenominatorBW = DenominatorVal.getBitWidth();
 
       if (NumeratorBW > DenominatorBW)
         DenominatorVal = DenominatorVal.sext(NumeratorBW);
for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
     if (isa<SCEVCouldNotCompute>(Coeff))
       return Coeff;
 
     Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff));
   }
   return Result;
 }
 
+const SCEV *SCEVFAddRecExpr::evaluateAtIteration(const SCEV *It,
+                                                 ScalarEvolution &SE) const {
+  const SCEV *Result = getStart();
+  for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
+    Result = SE.getFAddExpr(Result, SE.getFMulExpr(getOperand(i),
+                            SE.getSIToFPExpr(It, Result->getType())));
+  }
+  return Result;
+}
+
 //===----------------------------------------------------------------------===//
 //                    SCEV Expression folder implementations
 //===----------------------------------------------------------------------===//
 
 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op,
                                              Type *Ty) {
   assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
          "This is not a truncating conversion!");
if (PreAR && PreAR->getNoWrapFlags(WrapType)) {  // proves (2)
       if (Limit && isKnownPredicate(Pred, PreAR, Limit))  // proves (1)
         return true;
     }
   }
 
   return false;
 }
 
+const SCEV *ScalarEvolution::getSIToFPExpr(const SCEV *Op,
+                                           Type *Ty) {
+  Ty = getEffectiveSCEVType(Ty);
+
+  // Before doing any expensive analysis, check to see if we've already
+  // computed a SCEV for this Op and Ty.
+  FoldingSetNodeID ID;
+  ID.AddInteger(scSintToFp);
+  ID.AddPointer(Op);
+  ID.AddPointer(Ty);
+  void *IP = nullptr;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+    return S;
+
+  // for (int X = 0; X < 100; ++X) { float Y = (float)X; }
+
+  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op)) {
+    if (AR->isAffine()) {
+      const SCEV *Start = AR->getStart();
+      const SCEV *Step = AR->getStepRecurrence(*this);
+
+      const Loop *L = AR->getLoop();
+      const SCEV *StartFP = nullptr;
+      // Convert integer constants to float just here.
+      if (Start->getSCEVType() == scConstant) {
+        APInt ConstStart = cast<SCEVConstant>(Start)->getAPInt();
+        if (ConstStart.isSignedIntN(64))
+          StartFP = getFpConstant(Ty, (double)ConstStart.getSExtValue());
+        else if (ConstStart.isIntN(64))
+          StartFP = getFpConstant(Ty, (double)ConstStart.getZExtValue());
+      }
+      if (!StartFP)
+        StartFP = getSIToFPExpr(Start, Ty);
+
+      const SCEV *StepFP;
+      if (Step->getSCEVType() == scConstant) {
+        int64_t IntVal = cast<SCEVConstant>(Step)->getAPInt().getSExtValue();
+        StepFP = getFpConstant(Ty, (double)IntVal);
+      } else
+        StepFP = getSIToFPExpr(Step, Ty);
+
+      return getFAddRecExpr(StartFP, StepFP, L);
+    }
+  } else if (auto C = dyn_cast<SCEVConstant>(Op)) {
+    int64_t IntVal = C->getAPInt().getSExtValue();
+    return getFpConstant(Ty, (double)IntVal);
+  } else if (auto AddExpr = dyn_cast<SCEVAddExpr>(Op)) {
+    SmallVector<const SCEV *, 8> Ops;
+    for (auto Op : AddExpr->operands())
+      Ops.push_back(getSIToFPExpr(Op, Ty));
+    return getFAddExpr(Ops);
+  }
+  SCEV *S = new (SCEVAllocator)SCEVSintToFpExpr(ID.Intern(SCEVAllocator),
+                                                Op, Ty);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
+}
+
 const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op,
                                                Type *Ty) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
   Ty = getEffectiveSCEVType(Ty);
 
if (!S) {
     S = new (SCEVAllocator) SCEVAddExpr(ID.Intern(SCEVAllocator),
                                         O, Ops.size());
     UniqueSCEVs.InsertNode(S, IP);
   }
   S->setNoWrapFlags(Flags);
   return S;
 }
 
+const SCEV *ScalarEvolution::getFAddExpr(SmallVectorImpl<const SCEV *> &Ops) {
+  assert(!Ops.empty() && "Cannot get empty add!");
+  if (Ops.size() == 1) return Ops[0];
+
+  // Sort by complexity, this groups all similar expression types together.
+  GroupByComplexity(Ops, &LI);
+
+  // If there are any constants, fold them together.
+  unsigned Idx = 0;
+  if (const SCEVFpConstant *LHSC = dyn_cast<SCEVFpConstant>(Ops[0])) {
+    ++Idx;
+    assert(Idx < Ops.size());
+    while (const SCEVFpConstant *RHSC = dyn_cast<SCEVFpConstant>(Ops[Idx])) {
+      // We found two constants, fold them together!
+      Ops[0] = getFpConstant(LHSC->getAPFloat() + RHSC->getAPFloat());
+      if (Ops.size() == 2)
+        return Ops[0];
+      Ops.erase(Ops.begin() + 1);  // Erase the folded element
+      LHSC = cast<SCEVFpConstant>(Ops[0]);
+    }
+
+    // If we are left with a constant zero being added, strip it off.
+    if (LHSC->getValue()->isZero()) {
+      Ops.erase(Ops.begin());
+      --Idx;
+    }
+
+    if (Ops.size() == 1)
+      return Ops[0];
+  }
+
+
+  // Skip past any other cast SCEVs.
+  while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scFAddExpr)
+    ++Idx;
+
+  // If there are add operands they would be next.
+  if (Idx < Ops.size()) {
+    bool DeletedAdd = false;
+    while (const SCEVFAddExpr *Add = dyn_cast<SCEVFAddExpr>(Ops[Idx])) {
+      // If we have an add, expand the add operands onto the end of the operands
+      // list.
+      Ops.erase(Ops.begin() + Idx);
+      Ops.append(Add->op_begin(), Add->op_end());
+      DeletedAdd = true;
+    }
+
+    // If we deleted at least one add, we added operands to the end of the list,
+    // and they are not necessarily sorted.  Recurse to resort and resimplify
+    // any operands we just acquired.
+    if (DeletedAdd)
+      return getFAddExpr(Ops);
+  }
+
+  // FIXME: folding FAddRecExpr is not implemented yet.
+
+  // Check to see if we already have FAddExpr, otherwise create a new one.
+  FoldingSetNodeID ID;
+  ID.AddInteger(scFAddExpr);
+  for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+    ID.AddPointer(Ops[i]);
+  void *IP = nullptr;
+  SCEVFAddExpr *S =
+    static_cast<SCEVFAddExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
+  if (!S) {
+    const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
+    std::uninitialized_copy(Ops.begin(), Ops.end(), O);
+    S = new (SCEVAllocator)SCEVFAddExpr(ID.Intern(SCEVAllocator),
+                                       O, Ops.size());
+    UniqueSCEVs.InsertNode(S, IP);
+  }
+  return S;
+}
+
+
 static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow) {
   uint64_t k = i*j;
   if (j > 1 && k / j != i) Overflow = true;
   return k;
 }
 
 /// Compute the result of "n choose k", the binomial coefficient.  If an
 /// intermediate computation overflows, Overflow will be set and the return will

 
 /// Determine if any of the operands in this SCEV are a constant or if
 /// any of the add or multiply expressions in this SCEV contain a constant.
 static bool containsConstantSomewhere(const SCEV *StartExpr) {
   SmallVector<const SCEV *, 4> Ops;
   Ops.push_back(StartExpr);
   while (!Ops.empty()) {
     const SCEV *CurrentExpr = Ops.pop_back_val();
-    if (isa<SCEVConstant>(*CurrentExpr))
+    if (isa<SCEVIntOrFpConstant>(*CurrentExpr))
       return true;
 
-    if (isa<SCEVAddExpr>(*CurrentExpr) || isa<SCEVMulExpr>(*CurrentExpr)) {
+    if (isa<SCEVAddExpr>(*CurrentExpr) || isa<SCEVMulExpr>(*CurrentExpr) ||
+        isa<SCEVFAddExpr>(*CurrentExpr) || isa<SCEVFMulExpr>(*CurrentExpr)) {
       const auto *CurrentNAry = cast<SCEVNAryExpr>(CurrentExpr);
       Ops.append(CurrentNAry->op_begin(), CurrentNAry->op_end());
     }
   }
   return false;
 }
 
 /// Get a canonical multiply expression, or something simpler if possible.
 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
                                         SCEV::NoWrapFlags Flags) {
   assert(Flags == maskFlags(Flags, SCEV::FlagNUW | SCEV::FlagNSW) &&
          "only nuw or nsw allowed");
   assert(!Ops.empty() && "Cannot get empty mul!");
+  assert(!Ops[0]->getType()->isFloatingPointTy() &&
+         "SCEVMulExpr operands should be integer");
+
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
     assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
            "SCEVMulExpr operand types don't match!");
 #endif
 
if (!S) {
     S = new (SCEVAllocator) SCEVMulExpr(ID.Intern(SCEVAllocator),
                                         O, Ops.size());
     UniqueSCEVs.InsertNode(S, IP);
   }
   S->setNoWrapFlags(Flags);
   return S;
 }
 
+const SCEV *ScalarEvolution::getFMulExpr(SmallVectorImpl<const SCEV *> &Ops) {
+
+  assert(!Ops.empty() && "Cannot get empty mul!");
+  assert(Ops[0]->getType()->isFloatingPointTy() &&
+         "SCEVFMulExpr operands should be FP");
+
+  if (Ops.size() == 1) return Ops[0];
+#ifndef NDEBUG
+  Type *ETy = Ops[0]->getType();
+  for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+    assert(Ops[i]->getType() == ETy &&
+           "SCEVFMulExpr operand types don't match!");
+#endif
+
+  // Sort by complexity, this groups all similar expression types together.
+  GroupByComplexity(Ops, &LI);
+
+  // If there are any constants, fold them together.
+  unsigned Idx = 0;
+  if (const SCEVFpConstant *LHSC = dyn_cast<SCEVFpConstant>(Ops[0])) {
+
+    // C1*(C2+V) -> C1*C2 + C1*V
+    if (Ops.size() == 2)
+      if (const SCEVFAddExpr *Add = dyn_cast<SCEVFAddExpr>(Ops[1]))
+        // If any of Add's ops are Adds or Muls with a constant,
+        // apply this transformation as well.
+        if (Add->getNumOperands() == 2)
+          if (containsConstantSomewhere(Add))
+            return getFAddExpr(getFMulExpr(LHSC, Add->getOperand(0)),
+                               getFMulExpr(LHSC, Add->getOperand(1)));
+
+    ++Idx;
+    while (const SCEVFpConstant *RHSC = dyn_cast<SCEVFpConstant>(Ops[Idx])) {
+      // We found two constants, fold them together!
+      ConstantFP *Fold =
+        ConstantFP::get(getContext(), LHSC->getAPFloat() * RHSC->getAPFloat());
+      Ops[0] = getFpConstant(Fold);
+      Ops.erase(Ops.begin() + 1);  // Erase the folded element
+      if (Ops.size() == 1)
+        return Ops[0];
+      LHSC = cast<SCEVFpConstant>(Ops[0]);
+    }
+
+    // If we are left with a constant one being multiplied, strip it off.
+    ConstantFP *Op0Val = cast<SCEVFpConstant>(Ops[0])->getValue();
+    if (Op0Val->isExactlyValue(1.0)) {
+      Ops.erase(Ops.begin());
+      --Idx;
+    } else if (Op0Val->isZero())
+      // If we have a multiply of zero, it will always be zero.
+      return Ops[0];
+
+    if (Ops.size() == 1)
+      return Ops[0];
+  }
+
+  // Skip over the add expression until we get to a multiply.
+  while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scFMulExpr)
+    ++Idx;
+
+  // If there are mul operands inline them all into this expression.
+  if (Idx < Ops.size()) {
+    bool DeletedMul = false;
+    while (const SCEVFMulExpr *Mul = dyn_cast<SCEVFMulExpr>(Ops[Idx])) {
+      // If we have an mul, expand the mul operands onto the end of the operands
+      // list.
+      Ops.erase(Ops.begin() + Idx);
+      Ops.append(Mul->op_begin(), Mul->op_end());
+      DeletedMul = true;
+    }
+
+    // If we deleted at least one mul, we added operands to the end of the list,
+    // and they are not necessarily sorted.  Recurse to resort and resimplify
+    // any operands we just acquired.
+    if (DeletedMul)
+      return getFMulExpr(Ops);
+  }
+
+  FoldingSetNodeID ID;
+  ID.AddInteger(scFMulExpr);
+  for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+    ID.AddPointer(Ops[i]);
+  void *IP = nullptr;
+  SCEVFMulExpr *S =
+    static_cast<SCEVFMulExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
+  if (!S) {
+    const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
+    std::uninitialized_copy(Ops.begin(), Ops.end(), O);
+    S = new (SCEVAllocator)SCEVFMulExpr(ID.Intern(SCEVAllocator),
+                                        O, Ops.size());
+    UniqueSCEVs.InsertNode(S, IP);
+  }
+  return S;
+}
+
 /// Get a canonical unsigned division expression, or something simpler if
 /// possible.
 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
   assert(getEffectiveSCEVType(LHS->getType()) ==
          getEffectiveSCEVType(RHS->getType()) &&
          "SCEVUDivExpr operand types don't match!");
 
if (Mul->getOperand(i) == RHS) {
       Operands.append(Mul->op_begin() + i + 1, Mul->op_end());
       return getMulExpr(Operands);
     }
   }
 
   return getUDivExpr(LHS, RHS);
 }
 
+const SCEV *ScalarEvolution::getFAddRecExpr(const SCEV *Start, const SCEV *Step,
+                                            const Loop *L) {
+  // FIXME: nesting of FAddRecExpr should be implemented
+  SmallVector<const SCEV *, 4> Operands;
+  Operands.push_back(Start);
+  Operands.push_back(Step);
+  return getFAddRecExpr(Operands, L);
+}
+
+const SCEV *
+ScalarEvolution::getFAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
+                                const Loop *L) {
+  if (Operands.size() == 1)
+    return Operands[0];
+
+  // FIXME: nesting of FAddRecExpr should be implemented
+  FoldingSetNodeID ID;
+  ID.AddInteger(scFAddRecExpr);
+  for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+    ID.AddPointer(Operands[i]);
+  ID.AddPointer(L);
+  void *IP = nullptr;
+  SCEVFAddRecExpr *S =
+    static_cast<SCEVFAddRecExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
+  if (!S) {
+    const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Operands.size());
+    std::uninitialized_copy(Operands.begin(), Operands.end(), O);
+    S = new (SCEVAllocator)SCEVFAddRecExpr(ID.Intern(SCEVAllocator),
+                                           O, Operands.size(), L);
+    UniqueSCEVs.InsertNode(S, IP);
+  }
+  return S;
+}
+
 /// Get an add recurrence expression for the specified loop.  Simplify the
 /// expression as much as possible.
 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step,
                                            const Loop *L,
                                            SCEV::NoWrapFlags Flags) {
   SmallVector<const SCEV *, 4> Operands;
   Operands.push_back(Start);
   if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))

 //===----------------------------------------------------------------------===//
 //            Basic SCEV Analysis and PHI Idiom Recognition Code
 //
 
 /// Test if values of the given type are analyzable within the SCEV
 /// framework. This primarily includes integer types, and it can optionally
 /// include pointer types if the ScalarEvolution class has access to
 /// target-specific information.
+/// Now we add Half, Float, Double to this set.
 bool ScalarEvolution::isSCEVable(Type *Ty) const {
-  // Integers and pointers are always SCEVable.
-  return Ty->isIntegerTy() || Ty->isPointerTy();
+  return Ty->isIntegerTy() || Ty->isPointerTy() || Ty->isFloatTy() ||
+    Ty->isDoubleTy() || Ty->isHalfTy();
 }
 
 /// Return the size in bits of the specified type, for which isSCEVable must
 /// return true.
 uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const {
   assert(isSCEVable(Ty) && "Type is not SCEVable!");
   return getDataLayout().getTypeSizeInBits(Ty);
 }
 
 /// Return a type with the same bitwidth as the given type and which represents
 /// how SCEV will treat the given type, for which isSCEVable must return
 /// true. For pointer types, this is the pointer-sized integer type.
 Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const {
   assert(isSCEVable(Ty) && "Type is not SCEVable!");
 
-  if (Ty->isIntegerTy())
+  if (Ty->isIntegerTy() || Ty->isFloatTy() || Ty->isDoubleTy() ||
+      Ty->isHalfTy())
     return Ty;
 
   // The only other support type is pointer.
   assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!");
   return getDataLayout().getIntPtrType(Ty);
 }
 
 const SCEV *ScalarEvolution::getCouldNotCompute() {
   return CouldNotCompute.get();
 }
 
 
 bool ScalarEvolution::checkValidity(const SCEV *S) const {
   // Helper class working with SCEVTraversal to figure out if a SCEV contains
   // a SCEVUnknown with null value-pointer. FindInvalidSCEVUnknown::FindOne
   // is set iff if find such SCEVUnknown.
   //
   struct FindInvalidSCEVUnknown {
     bool FindOne;
     FindInvalidSCEVUnknown() { FindOne = false; }
     bool follow(const SCEV *S) {
       switch (static_cast<SCEVTypes>(S->getSCEVType())) {
       case scConstant:
+      case scFpConstant:
         return false;
       case scUnknown:
         if (!cast<SCEVUnknown>(S)->getValue())
           FindOne = true;
         return false;
       default:
         return true;
       }
struct FindAddRecurrence {
   bool FoundOne;
   FindAddRecurrence() : FoundOne(false) {}
 
   bool follow(const SCEV *S) {
     switch (static_cast<SCEVTypes>(S->getSCEVType())) {
     case scAddRecExpr:
       FoundOne = true;
     case scConstant:
+    case scFpConstant:
     case scUnknown:
     case scCouldNotCompute:
       return false;
     default:
       return true;
     }
   }
   bool isDone() const { return FoundOne; }
return getConstant(
                cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
 
   Type *Ty = V->getType();
   Ty = getEffectiveSCEVType(Ty);
   return getMulExpr(
       V, getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty))), Flags);
 }
 
+/// Return a FP SCEV corresponding to -V = -1*V
+const SCEV *ScalarEvolution::getNegativeFpSCEV(const SCEV *V) {
+  if (const SCEVFpConstant *VC = dyn_cast<SCEVFpConstant>(V))
+    return getFpConstant(cast<ConstantFP>(ConstantExpr::getFNeg(VC->getValue())));
+
+  Type *Ty = V->getType();
+  return getFMulExpr(V,
+                     getFpConstant(cast<ConstantFP>(ConstantFP::get(Ty, -1.0))));
+}
+
 /// Return a SCEV corresponding to ~V = -1-V
 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) {
   if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
     return getConstant(
                 cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
 
   Type *Ty = V->getType();
   Ty = getEffectiveSCEVType(Ty);
static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) {
   case Instruction::Add:
   case Instruction::Sub:
   case Instruction::Mul:
   case Instruction::UDiv:
   case Instruction::And:
   case Instruction::Or:
   case Instruction::AShr:
   case Instruction::Shl:
+  case Instruction::FAdd:
+  case Instruction::FSub:
+  case Instruction::FMul:
     return BinaryOp(Op);
 
   case Instruction::Xor:
     if (auto *RHSC = dyn_cast<ConstantInt>(Op->getOperand(1)))
       // If the RHS of the xor is a signbit, then this is just an add.
       // Instcombine turns add of signbit into xor as a strength reduction step.
       if (RHSC->getValue().isSignBit())
         return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1));
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
           // overflow.
           if (auto *BEInst = dyn_cast<Instruction>(BEValueV))
             if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L))
               (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
 
           return PHISCEV;
         }
       }
-    } else {
+    } else if (const SCEVFAddExpr *Add = dyn_cast<SCEVFAddExpr>(BEValue)) {
+      unsigned FoundIndex = Add->getNumOperands();
+      for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
+        if (Add->getOperand(i) == SymbolicName)
+          if (FoundIndex == e) {
+            FoundIndex = i;
+            break;
+          }
+
+      if (FoundIndex != Add->getNumOperands()) {
+        // Create an add with everything but the specified operand.
+        SmallVector<const SCEV *, 8> Ops;
+        for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
+          if (i != FoundIndex)
+            Ops.push_back(Add->getOperand(i));
+        const SCEV *Accum = getFAddExpr(Ops);
+        const SCEV *StartVal = getSCEV(StartValueV);
+        const SCEV *PHISCEV = getFAddRecExpr(StartVal, Accum, L);
+
+        // Okay, for the entire analysis of this edge we assumed the PHI
+        // to be symbolic.  We now need to go back and purge all of the
+        // entries for the scalars that use the symbolic expression.
+        forgetSymbolicName(PN, SymbolicName);
+        ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV;
+        // We don't know how to expand FAddRecExpr to PHI.
+        // So we map FAddRecExpr to PHI and do not modify it
+        ExprValueMap[PHISCEV].insert(PN);
+        return PHISCEV;
+      }
+    } else if (!PN->getType()->isFloatingPointTy()) {
       // Otherwise, this could be a loop like this:
       //     i = 0;  for (j = 1; ..; ++j) { ....  i = j; }
       // In this case, j = {1,+,1}  and BEValue is j.
       // Because the other in-value of i (0) fits the evolution of BEValue
       // i really is an addrec evolution.
       //
       // We can generalize this saying that i is the shifted value of BEValue
       // by one iteration:
bool setUnavailable() {
       Available = false;
       return false;
     }
 
     bool follow(const SCEV *S) {
       switch (S->getSCEVType()) {
       case scConstant: case scTruncate: case scZeroExtend: case scSignExtend:
       case scAddExpr: case scMulExpr: case scUMaxExpr: case scSMaxExpr:
+      case scFpConstant: case scSintToFp: case scFAddExpr: case scFMulExpr:
         // These expressions are available if their operand(s) is/are.
         return true;
 
-      case scAddRecExpr: {
+      case scAddRecExpr:
+      case scFAddRecExpr: {
         // We allow add recurrences that are on the loop BB is in, or some
         // outer loop.  This guarantees availability because the value of the
         // add recurrence at BB is simply the "current" value of the induction
         // variable.  We can relax this in the future; for instance an add
         // recurrence on a sibling dominating loop is also available at BB.
-        const auto *ARLoop = cast<SCEVAddRecExpr>(S)->getLoop();
+        const auto *ARLoop = cast<SCEVRecExpr>(S)->getLoop();
         if (L && (ARLoop == L || ARLoop->contains(L)))
           return true;
 
         return setUnavailable();
       }
 
       case scUnknown: {
         // For SCEVUnknown, we check for simple dominance.
const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
 
   return nullptr;
 }
 
 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
   if (const SCEV *S = createAddRecFromPHI(PN))
     return S;
 
+  // FIXME: All further attempts to create SCEV for FP PHI should be
+  // implemented.
+  if (PN->getType()->isFloatingPointTy())
+    return getUnknown(PN);
+
   if (const SCEV *S = createNodeFromSelectLikePHI(PN))
     return S;
 
   // If the PHI has a single incoming value, follow that value, unless the
   // PHI's incoming blocks are in a different loop, in which case doing so
   // risks breaking LCSSA form. Instcombine would normally zap these, but
   // it doesn't have DominatorTree information, so it may miss cases.
   if (Value *V = SimplifyInstruction(PN, getDataLayout(), &TLI, &DT, &AC))
const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Instruction *I,
   if (auto *CI = dyn_cast<ConstantInt>(Cond))
     return getSCEV(CI->isOne() ? TrueVal : FalseVal);
 
   // Try to match some simple smax or umax patterns.
   auto *ICI = dyn_cast<ICmpInst>(Cond);
   if (!ICI)
     return getUnknown(I);
 
+  // Fmax and Fmin may also be implemented in the future.
+  if (I->getType()->isFloatingPointTy())
+    return getUnknown(I);
+
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
 
   switch (ICI->getPredicate()) {
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_SLE:
     std::swap(LHS, RHS);
   // fall through
if (Instruction *I = dyn_cast<Instruction>(V)) {
     // Don't attempt to analyze instructions in blocks that aren't
     // reachable. Such instructions don't matter, and they aren't required
     // to obey basic rules for definitions dominating uses which this
     // analysis depends on.
     if (!DT.isReachableFromEntry(I->getParent()))
       return getUnknown(V);
   } else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
     return getConstant(CI);
+  else if (ConstantFP *CI = dyn_cast<ConstantFP>(V))
+    return getFpConstant(CI);
   else if (isa<ConstantPointerNull>(V))
     return getZero(V->getType());
   else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
     return GA->isInterposable() ? getUnknown(V) : getSCEV(GA->getAliasee());
   else if (!isa<ConstantExpr>(V))
     return getUnknown(V);
 
   Operator *U = cast<Operator>(V);
case Instruction::Mul: {
         }
 
         MulOps.push_back(getSCEV(BO->RHS));
         auto NewBO = MatchBinaryOp(BO->LHS, DT);
         if (!NewBO || NewBO->Opcode != Instruction::Mul) {
           MulOps.push_back(getSCEV(BO->LHS));
           break;
         }
-  BO = NewBO;
+        BO = NewBO;
       } while (true);
 
       return getMulExpr(MulOps);
     }
     case Instruction::UDiv:
       return getUDivExpr(getSCEV(BO->LHS), getSCEV(BO->RHS));
     case Instruction::Sub: {
       SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
case Instruction::AShr:
             if (Amt == BitWidth)
               return getSCEV(L->getOperand(0)); // shift by zero --> noop
             return getSignExtendExpr(
                 getTruncateExpr(getSCEV(L->getOperand(0)),
                                 IntegerType::get(getContext(), Amt)),
                 BO->LHS->getType());
           }
       break;
+    case Instruction::FAdd: {
+      // The simple thing to do would be to just call getSCEV on both operands
+      // and call getFAddExpr with the result. However if we're looking at a
+      // bunch of things all added together, this can be quite inefficient,
+      // because it leads to N-1 getFAddExpr calls for N ultimate operands.
+      // Instead, gather up all the operands and make a single getFAddExpr call.
+      // LLVM IR canonical form means we need only traverse the left operands.
+      SmallVector<const SCEV *, 4> AddOps;
+      do {
+        if (BO->Op)
+          if (auto *OpSCEV = getExistingSCEV(BO->Op)) {
+            AddOps.push_back(OpSCEV);
+            break;
+          }
+        if (BO->Opcode == Instruction::FSub)
+          AddOps.push_back(getNegativeSCEV(getSCEV(BO->RHS)));
+        else
+          AddOps.push_back(getSCEV(BO->RHS));
+
+        auto NewBO = MatchBinaryOp(BO->LHS, DT);
+        if (!NewBO || (NewBO->Opcode != Instruction::FAdd &&
+          NewBO->Opcode != Instruction::FSub)) {
+          AddOps.push_back(getSCEV(BO->LHS));
+          break;
+        }
+        BO = NewBO;
+      } while (true);
+
+      return getFAddExpr(AddOps);
+    }
+    case Instruction::FSub:
+      return getFAddExpr(getSCEV(BO->LHS), getNegativeFpSCEV(getSCEV(BO->RHS)));
+    case Instruction::FMul: {
+      SmallVector<const SCEV *, 4> MulOps;
+      do {
+        if (BO->Op)
+          if (auto *OpSCEV = getExistingSCEV(BO->Op)) {
+            MulOps.push_back(OpSCEV);
+            break;
+          }
+
+        MulOps.push_back(getSCEV(BO->RHS));
+        auto NewBO = MatchBinaryOp(BO->LHS, DT);
+        if (!NewBO || NewBO->Opcode != Instruction::FMul) {
+          MulOps.push_back(getSCEV(BO->LHS));
+          break;
+        }
+        BO = NewBO;
+      } while (true);
+
+      return getFMulExpr(MulOps);
+    }
     }
   }
 
   switch (U->getOpcode()) {
   case Instruction::Trunc:
     return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
 
   case Instruction::ZExt:
     return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
 
   case Instruction::SExt:
     return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
 
   case Instruction::BitCast:
-    // BitCasts are no-op casts so we just eliminate the cast.
-    if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType()))
+    // SCEV propagation for BitCasts from "integer" to "float" and back 
+    // is not supported right now.
+    // All other bitcasts are just eliminated.
+    if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) {
+      if (U->getType()->isFloatingPointTy() !=
+          U->getOperand(0)->getType()->isFloatingPointTy())
+        return getUnknown(V);
       return getSCEV(U->getOperand(0));
+    }
     break;
 
+  case Instruction::SIToFP:
+    return getSIToFPExpr(getSCEV(U->getOperand(0)), U->getType());
+
   // It's tempting to handle inttoptr and ptrtoint as no-ops, however this can
   // lead to pointer expressions which cannot safely be expanded to GEPs,
   // because ScalarEvolution doesn't respect the GEP aliasing rules when
   // simplifying integer expressions.
 
   case Instruction::GetElementPtr:
     return createNodeForGEP(cast<GEPOperator>(U));
 
ExitLimit EL =
         computeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB, ControlsExit);
     if (EL.hasFullInfo() || !AllowPredicates)
       return EL;
 
     // Try again, but use SCEV predicates this time.
     return computeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB, ControlsExit,
                                     /*AllowPredicates=*/true);
   }
+  // We do not try to compute exit limit from FP compare.
 
   // Check for a constant condition. These are normally stripped out by
   // SimplifyCFG, but ScalarEvolution may be used by a pass which wishes to
   // preserve the CFG and is temporarily leaving constant conditions
   // in place.
   if (ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
     if (L->contains(FBB) == !CI->getZExtValue())
       // The backedge is always taken.

 /// This builds up a Constant using the ConstantExpr interface.  That way, we
 /// will return Constants for objects which aren't represented by a
 /// SCEVConstant, because SCEVConstant is restricted to ConstantInt.
 /// Returns NULL if the SCEV isn't representable as a Constant.
 static Constant *BuildConstantFromSCEV(const SCEV *V) {
   switch (static_cast<SCEVTypes>(V->getSCEVType())) {
     case scCouldNotCompute:
     case scAddRecExpr:
+    case scFAddRecExpr:
       break;
     case scConstant:
-      return cast<SCEVConstant>(V)->getValue();
+    case scFpConstant:
+      return cast<SCEVIntOrFpConstant>(V)->getValue();
     case scUnknown:
       return dyn_cast<Constant>(cast<SCEVUnknown>(V)->getValue());
     case scSignExtend: {
       const SCEVSignExtendExpr *SS = cast<SCEVSignExtendExpr>(V);
       if (Constant *CastOp = BuildConstantFromSCEV(SS->getOperand()))
         return ConstantExpr::getSExt(CastOp, SS->getType());
       break;
     }
     case scZeroExtend: {
       const SCEVZeroExtendExpr *SZ = cast<SCEVZeroExtendExpr>(V);
       if (Constant *CastOp = BuildConstantFromSCEV(SZ->getOperand()))
         return ConstantExpr::getZExt(CastOp, SZ->getType());
       break;
     }
     case scTruncate: {
       const SCEVTruncateExpr *ST = cast<SCEVTruncateExpr>(V);
       if (Constant *CastOp = BuildConstantFromSCEV(ST->getOperand()))
         return ConstantExpr::getTrunc(CastOp, ST->getType());
       break;
     }
+    case scSintToFp: {
+      const SCEVSintToFpExpr *SF = cast<SCEVSintToFpExpr>(V);
+      if (Constant *CastOp = BuildConstantFromSCEV(SF->getOperand()))
+        return ConstantExpr::getSIToFP(CastOp, SF->getType());
+      break;
+    }
+    case scFAddExpr: {
+      const SCEVFAddExpr *SA = cast<SCEVFAddExpr>(V);
+      if (Constant *C = BuildConstantFromSCEV(SA->getOperand(0))) {
+        for (unsigned i = 1, e = SA->getNumOperands(); i != e; ++i) {
+          Constant *C2 = BuildConstantFromSCEV(SA->getOperand(i));
+          if (!C2) return nullptr;
+          C = ConstantExpr::getAdd(C, C2);
+        }
+        return C;
+      }
+      break;
+    }
     case scAddExpr: {
       const SCEVAddExpr *SA = cast<SCEVAddExpr>(V);
       if (Constant *C = BuildConstantFromSCEV(SA->getOperand(0))) {
         if (PointerType *PTy = dyn_cast<PointerType>(C->getType())) {
           unsigned AS = PTy->getAddressSpace();
           Type *DestPtrTy = Type::getInt8PtrTy(C->getContext(), AS);
           C = ConstantExpr::getBitCast(C, DestPtrTy);
         }
case scMulExpr: {
           Constant *C2 = BuildConstantFromSCEV(SM->getOperand(i));
           if (!C2 || C2->getType()->isPointerTy()) return nullptr;
           C = ConstantExpr::getMul(C, C2);
         }
         return C;
       }
       break;
     }
+    case scFMulExpr: {
+      const SCEVFMulExpr *SM = cast<SCEVFMulExpr>(V);
+      if (Constant *C = BuildConstantFromSCEV(SM->getOperand(0))) {
+        for (unsigned i = 1, e = SM->getNumOperands(); i != e; ++i) {
+          Constant *C2 = BuildConstantFromSCEV(SM->getOperand(i));
+          if (!C2)
+            return nullptr;
+          C = ConstantExpr::getFMul(C, C2);
+        }
+        return C;
+      }
+      break;
+    }
     case scUDivExpr: {
       const SCEVUDivExpr *SU = cast<SCEVUDivExpr>(V);
       if (Constant *LHS = BuildConstantFromSCEV(SU->getLHS()))
         if (Constant *RHS = BuildConstantFromSCEV(SU->getRHS()))
           if (LHS->getType() == RHS->getType())
             return ConstantExpr::getUDiv(LHS, RHS);
       break;
     }
     case scSMaxExpr:
     case scUMaxExpr:
       break; // TODO: smax, umax.
   }
   return nullptr;
 }
 
 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
-  if (isa<SCEVConstant>(V)) return V;
+
+  if (isa<SCEVIntOrFpConstant>(V))
+    return V;
 
   // If this instruction is evolved from a constant-evolving PHI, compute the
   // exit value from the loop without using SCEVs.
   if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
     if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
       const Loop *LI = this->LI[I->getParent()];
       if (LI && LI->getParentLoop() == L)  // Looking for loop exit value.
         if (PHINode *PN = dyn_cast<PHINode>(I))
for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
         if (isa<SCEVAddExpr>(Comm))
           return getAddExpr(NewOps);
         if (isa<SCEVMulExpr>(Comm))
           return getMulExpr(NewOps);
         if (isa<SCEVSMaxExpr>(Comm))
           return getSMaxExpr(NewOps);
         if (isa<SCEVUMaxExpr>(Comm))
           return getUMaxExpr(NewOps);
+        if (isa<SCEVFAddExpr>(Comm))
+          return getFAddExpr(NewOps);
+        if (isa<SCEVFMulExpr>(Comm))
+          return getFMulExpr(NewOps);
         llvm_unreachable("Unknown commutative SCEV type!");
       }
     }
     // If we got here, all operands are loop invariant.
     return Comm;
   }
 
   if (const SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
if (!AddRec->getLoop()->contains(L)) {
       if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
 
       // Then, evaluate the AddRec.
       return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
     }
 
     return AddRec;
   }
+  if (const SCEVFAddRecExpr *AddRec = dyn_cast<SCEVFAddRecExpr>(V)) {
+    // First, attempt to evaluate each operand.
+    // Avoid performing the look-up in the common case where the specified
+    // expression has no loop-variant portions.
+    for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
+      const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
+      if (OpAtScope == AddRec->getOperand(i))
+        continue;
+
+      // Okay, at least one of these operands is loop variant but might be
+      // foldable.  Build a new instance of the folded commutative expression.
+      SmallVector<const SCEV *, 8> NewOps(AddRec->op_begin(),
+                                          AddRec->op_begin() + i);
+      NewOps.push_back(OpAtScope);
+      for (++i; i != e; ++i)
+        NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L));
+
+      const SCEV *FoldedRec = getFAddRecExpr(NewOps, AddRec->getLoop());
+      AddRec = dyn_cast<SCEVFAddRecExpr>(FoldedRec);
+      // The addrec may be folded to a nonrecurrence, for example, if the
+      // induction variable is multiplied by zero after constant folding. Go
+      // ahead and return the folded value.
+      if (!AddRec)
+        return FoldedRec;
+      break;
+    }
+
+    // If the scope is outside the addrec's loop, evaluate it by using the
+    // loop exit value of the addrec.
+    if (!AddRec->getLoop()->contains(L)) {
+      // To evaluate this recurrence, we need to know how many times the AddRec
+      // loop iterates.  Compute this now.
+      const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
+      if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
+
+      // Then, evaluate the AddRec.
+      return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
+    }
+
+    return AddRec;
+  }
 
   if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
     const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
     if (Op == Cast->getOperand())
       return Cast;  // must be loop invariant
     return getZeroExtendExpr(Op, Cast->getType());
   }
 
   if (const SCEVSignExtendExpr *Cast = dyn_cast<SCEVSignExtendExpr>(V)) {
     const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
     if (Op == Cast->getOperand())
       return Cast;  // must be loop invariant
     return getSignExtendExpr(Op, Cast->getType());
   }
 
   if (const SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) {
     const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
     if (Op == Cast->getOperand())
       return Cast;  // must be loop invariant
     return getTruncateExpr(Op, Cast->getType());
   }
 
+  if (const SCEVFAddRecExpr *FAddRec = dyn_cast<SCEVFAddRecExpr>(V)) {
+    // First, attempt to evaluate each operand.
+    // Avoid performing the look-up in the common case where the specified
+    // expression has no loop-variant portions.
+    for (unsigned i = 0, e = FAddRec->getNumOperands(); i != e; ++i) {
+      const SCEV *OpAtScope = getSCEVAtScope(FAddRec->getOperand(i), L);
+      if (OpAtScope == FAddRec->getOperand(i))
+        continue;
+
+      // Okay, at least one of these operands is loop variant but might be
+      // foldable.  Build a new instance of the folded commutative expression.
+      SmallVector<const SCEV *, 8> NewOps(FAddRec->op_begin(),
+                                          FAddRec->op_begin() + i);
+      NewOps.push_back(OpAtScope);
+      for (++i; i != e; ++i)
+        NewOps.push_back(getSCEVAtScope(FAddRec->getOperand(i), L));
+
+      const SCEV *FoldedRec = getFAddRecExpr(NewOps, FAddRec->getLoop());
+      FAddRec = dyn_cast<SCEVFAddRecExpr>(FoldedRec);
+      // The addrec may be folded to a nonrecurrence, for example, if the
+      // induction variable is multiplied by zero after constant folding. Go
+      // ahead and return the folded value.
+      if (!FAddRec)
+        return FoldedRec;
+      break;
+    }
+    return FAddRec;
+  }
+
+  if (const SCEVSintToFpExpr *Cast = dyn_cast<SCEVSintToFpExpr>(V)) {
+    const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
+    if (Op == Cast->getOperand())
+      return Cast;  // must be loop invariant
+    return getSIToFPExpr(Op, Cast->getType());
+  }
+
   llvm_unreachable("Unknown SCEV type!");
 }
 
 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
   return getSCEVAtScope(getSCEV(V), L);
 }
 
 /// Finds the minimum unsigned root of the following equation:
void ScalarEvolution::print(raw_ostream &OS) const {
   // observable from outside the class though, so casting away the
   // const isn't dangerous.
   ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
 
   OS << "Classifying expressions for: ";
   F.printAsOperand(OS, /*PrintType=*/false);
   OS << "\n";
   for (Instruction &I : instructions(F))
-    if (isSCEVable(I.getType()) && !isa<CmpInst>(I)) {
+    // FIXME: FP SCEV print should be implemented
+    if (isSCEVable(I.getType()) && !isa<CmpInst>(I) &&
+        !I.getType()->isFloatingPointTy()) {
       OS << I << '\n';
       OS << "  -->  ";
       const SCEV *SV = SE.getSCEV(&I);
       SV->print(OS);
       if (!isa<SCEVCouldNotCompute>(SV)) {
         OS << " U: ";
         SE.getUnsignedRange(SV).print(OS);
         OS << " S: ";
ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) {
   }
   return D;
 }
 
 ScalarEvolution::LoopDisposition
 ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) {
   switch (static_cast<SCEVTypes>(S->getSCEVType())) {
   case scConstant:
+  case scFpConstant:
     return LoopInvariant;
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
+  case scSintToFp:
     return getLoopDisposition(cast<SCEVCastExpr>(S)->getOperand(), L);
+  case scFAddRecExpr:
   case scAddRecExpr: {
-    const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
+    const SCEVRecExpr *AR = cast<SCEVRecExpr>(S);
 
     // If L is the addrec's loop, it's computable.
     if (AR->getLoop() == L)
       return LoopComputable;
 
     // Add recurrences are never invariant in the function-body (null loop).
     if (!L)
       return LoopVariant;
for (auto *Op : AR->operands())
       if (!isLoopInvariant(Op, L))
         return LoopVariant;
 
     // Otherwise it's loop-invariant.
     return LoopInvariant;
   }
   case scAddExpr:
   case scMulExpr:
+  case scFAddExpr:
+  case scFMulExpr:
   case scUMaxExpr:
   case scSMaxExpr: {
     bool HasVarying = false;
     for (auto *Op : cast<SCEVNAryExpr>(S)->operands()) {
       LoopDisposition D = getLoopDisposition(Op, L);
       if (D == LoopVariant)
         return LoopVariant;
       if (D == LoopComputable)
ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) {
   }
   return D;
 }
 
 ScalarEvolution::BlockDisposition
 ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) {
   switch (static_cast<SCEVTypes>(S->getSCEVType())) {
   case scConstant:
+  case scFpConstant:
     return ProperlyDominatesBlock;
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
+  case scSintToFp:
     return getBlockDisposition(cast<SCEVCastExpr>(S)->getOperand(), BB);
-  case scAddRecExpr: {
+  case scFAddRecExpr:
+  case scAddRecExpr:
+    if (auto AR = dyn_cast<SCEVRecExpr>(S)) {
       // This uses a "dominates" query instead of "properly dominates" query
       // to test for proper dominance too, because the instruction which
       // produces the addrec's value is a PHI, and a PHI effectively properly
       // dominates its entire containing block.
-    const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
       if (!DT.dominates(AR->getLoop()->getHeader(), BB))
         return DoesNotDominateBlock;
-  }
+    } else if (!DT.dominates(cast<SCEVRecExpr>(AR)->getLoop()->getHeader(),
+                             BB))
+      return DoesNotDominateBlock;
   // FALL THROUGH into SCEVNAryExpr handling.
   case scAddExpr:
+  case scFAddExpr:
   case scMulExpr:
+  case scFMulExpr:
   case scUMaxExpr:
   case scSMaxExpr: {
     const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
     bool Proper = true;
     for (const SCEV *NAryOp : NAry->operands()) {
       BlockDisposition D = getBlockDisposition(NAryOp, BB);
       if (D == DoesNotDominateBlock)
         return DoesNotDominateBlock;
PredicatedScalarEvolution::PredicatedScalarEvolution(
   for (auto I = Init.FlagsMap.begin(), E = Init.FlagsMap.end(); I != E; ++I)
     FlagsMap.insert(*I);
 }
 
 void PredicatedScalarEvolution::print(raw_ostream &OS, unsigned Depth) const {
   // For each block.
   for (auto *BB : L.getBlocks())
     for (auto &I : *BB) {
-      if (!SE.isSCEVable(I.getType()))
+      if (!SE.isSCEVable(I.getType()) || I.getType()->isFloatingPointTy())
         continue;
 
       auto *Expr = SE.getSCEV(&I);
       auto II = RewriteMap.find(Expr);
 
       if (II == RewriteMap.end())
         continue;
 

../lib/Analysis/ScalarEvolutionExpander.cpp

 /// getRelevantLoop - Get the most relevant loop associated with the given
 /// expression, according to PickMostRelevantLoop.
 const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {
   // Test whether we've already computed the most relevant loop for this SCEV.
   auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr));
   if (!Pair.second)
     return Pair.first->second;
 
-  if (isa<SCEVConstant>(S))
+  if (isa<SCEVIntOrFpConstant>(S))
     // A constant has no relevant loops.
     return nullptr;
   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
     if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))
       return Pair.first->second = SE.LI.getLoopFor(I->getParent());
     // A non-instruction has no relevant loops.
     return nullptr;
   }
   if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) {
     const Loop *L = nullptr;
-    if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
+    if (const SCEVRecExpr *AR = dyn_cast<SCEVRecExpr>(S))
       L = AR->getLoop();
     for (const SCEV *Op : N->operands())
       L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);
     return RelevantLoops[N] = L;
   }
   if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) {
     const Loop *Result = getRelevantLoop(C->getOperand());
     return RelevantLoops[C] = Result;
if (!Sum) {
       Sum = InsertBinop(Instruction::Add, Sum, W);
       ++I;
     }
   }
 
   return Sum;
 }
 
+Value *SCEVExpander::visitFAddExpr(const SCEVFAddExpr *S) {
+  
+  // Collect all the add operands in a loop, along with their associated loops.
+  // Iterate in reverse so that constants are emitted last, all else equal, and
+  // so that pointer operands are inserted first, which the code below relies on
+  // to form more involved GEPs.
+  SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
+  for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(S->op_end()),
+       E(S->op_begin()); I != E; ++I)
+       OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
+
+  // Sort by loop. Use a stable sort so that constants follow non-constants and
+  // pointer operands precede non-pointer operands.
+  std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(SE.DT));
+
+  // Emit instructions to add all the operands. Hoist as much as possible
+  // out of loops, and form meaningful getelementptrs where possible.
+  Value *Sum = nullptr;
+  for (const auto &I : OpsAndLoops) {
+    const SCEV *Op = I.second;
+    if (!Sum)
+      // This is the first operand. Just expand it.
+      Sum = expand(Op);
+    else
+      // A simple add.
+      Sum = InsertBinop(Instruction::FAdd, Sum, expandCodeFor(Op));
+  }
+  return Sum;
+}
+
 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
 
   // Collect all the mul operands in a loop, along with their associated loops.
   // Iterate in reverse so that constants are emitted last, all else equal.
   SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
   for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()),
        E(S->op_begin()); I != E; ++I)
if (!Prod) {
         Prod = InsertBinop(Instruction::Mul, Prod, W);
       }
     }
   }
 
   return Prod;
 }
 
+Value *SCEVExpander::visitFMulExpr(const SCEVFMulExpr *S) {
+
+  // Collect all the mul operands in a loop, along with their associated loops.
+  // Iterate in reverse so that constants are emitted last, all else equal.
+  SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
+  for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()),
+       E(S->op_begin()); I != E; ++I)
+       OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
+
+  // Sort by loop. Use a stable sort so that constants follow non-constants.
+  std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(SE.DT));
+
+  Value *Prod = nullptr;
+  for (const auto &I : OpsAndLoops) {
+    const SCEV *Op = I.second;
+    if (!Prod)
+      // This is the first operand. Just expand it.
+      Prod = expand(Op);
+    else
+      // A simple fmul.
+      Prod = InsertBinop(Instruction::FMul, Prod, expandCodeFor(Op));
+  }
+
+  return Prod;
+}
+
 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
 
   Value *LHS = expandCodeFor(S->getLHS(), Ty);
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
     const APInt &RHS = SC->getAPInt();
     if (RHS.isPowerOf2())
       return InsertBinop(Instruction::LShr, LHS,
if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
                                  expandCodeFor(PostLoopOffset, IntTy));
       rememberInstruction(Result);
     }
   }
 
   return Result;
 }
 
+Value *SCEVExpander::visitFAddRecExpr(const SCEVFAddRecExpr *S) {
+  llvm_unreachable("FAddRecExpr should be mapped to an existing phi node");
+}
+
 Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
   if (!CanonicalMode) return expandAddRecExprLiterally(S);
 
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
   const Loop *L = S->getLoop();
 
   // First check for an existing canonical IV in a suitable type.
   PHINode *CanonicalIV = nullptr;
Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
   Value *V = expandCodeFor(S->getOperand(),
                            SE.getEffectiveSCEVType(S->getOperand()->getType()));
   Value *I = Builder.CreateSExt(V, Ty);
   rememberInstruction(I);
   return I;
 }
 
+Value *SCEVExpander::visitSintToFpExpr(const SCEVSintToFpExpr *S) {
+  Type *Ty = SE.getEffectiveSCEVType(S->getType());
+  Value *V = expandCodeFor(S->getOperand(),
+                           SE.getEffectiveSCEVType(S->getOperand()->getType()));
+  Value *I = Builder.CreateSIToFP(V, Ty);
+  rememberInstruction(I);
+  return I;
+}
+
 Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
   Type *Ty = LHS->getType();
   for (int i = S->getNumOperands()-2; i >= 0; --i) {
     // In the case of mixed integer and pointer types, do the
     // rest of the comparisons as integer.
     if (S->getOperand(i)->getType() != Ty) {
       Ty = SE.getEffectiveSCEVType(Ty);
unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
   // Process phis from wide to narrow. Map wide phis to their truncation
   // so narrow phis can reuse them.
   for (PHINode *Phi : Phis) {
     auto SimplifyPHINode = [&](PHINode *PN) -> Value * {
       if (Value *V = SimplifyInstruction(PN, DL, &SE.TLI, &SE.DT, &SE.AC))
         return V;
       if (!SE.isSCEVable(PN->getType()))
         return nullptr;
-      auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
+      auto *Const = dyn_cast<SCEVIntOrFpConstant>(SE.getSCEV(PN));
       if (!Const)
         return nullptr;
       return Const->getValue();
     };
 
     // Fold constant phis. They may be congruent to other constant phis and
     // would confuse the logic below that expects proper IVs.
     if (Value *V = SimplifyPHINode(Phi)) {
       if (V->getType() != Phi->getType())
         continue;
       Phi->replaceAllUsesWith(V);
       DeadInsts.emplace_back(Phi);
       ++NumElim;
       DEBUG_WITH_TYPE(DebugType, dbgs()
                       << "INDVARS: Eliminated constant iv: " << *Phi << '\n');
       continue;
     }
 
-    if (!SE.isSCEVable(Phi->getType()))
+    if (!SE.isSCEVable(Phi->getType()) || Phi->getType()->isFloatingPointTy())
       continue;
 
     PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
     if (!OrigPhiRef) {
       OrigPhiRef = Phi;
       if (Phi->getType()->isIntegerTy() && TTI &&
           TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
         // This phi can be freely truncated to the narrowest phi type. Map the
bool SCEVExpander::isHighCostExpansionHelper(
   // then consider the expression cheap.
   if (At && findExistingExpansion(S, At, L) != nullptr)
     return false;
 
   // Zero/One operand expressions
   switch (S->getSCEVType()) {
   case scUnknown:
   case scConstant:
+  case scFpConstant:
     return false;
   case scTruncate:
     return isHighCostExpansionHelper(cast<SCEVTruncateExpr>(S)->getOperand(),
                                      L, At, Processed);
   case scZeroExtend:
     return isHighCostExpansionHelper(cast<SCEVZeroExtendExpr>(S)->getOperand(),
                                      L, At, Processed);
   case scSignExtend:
     return isHighCostExpansionHelper(cast<SCEVSignExtendExpr>(S)->getOperand(),
                                      L, At, Processed);
+  case scSintToFp:
+    return isHighCostExpansionHelper(cast<SCEVSintToFpExpr>(S)->getOperand(),
+                                     L, At, Processed);
   }
 
   if (!Processed.insert(S).second)
     return false;
 
   if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
     // If the divisor is a power of two and the SCEV type fits in a native
     // integer, consider the division cheap irrespective of whether it occurs in

../lib/Transforms/Scalar/IndVarSimplify.cpp

while ((PN = dyn_cast<PHINode>(BBI++))) {
             !isSafeToExpand(ExitValue, *SE))
           continue;
 
         // Computing the value outside of the loop brings no benefit if :
         //  - it is definitely used inside the loop in a way which can not be
         //    optimized away.
         //  - no use outside of the loop can take advantage of hoisting the
         //    computation out of the loop
-        if (ExitValue->getSCEVType()>=scMulExpr) {
+        if ((!ExitValue->getType()->isFloatingPointTy() &&
+            ExitValue->getSCEVType()>=scMulExpr) ||
+            ExitValue->getSCEVType() >= scFMulExpr) {
           unsigned NumHardInternalUses = 0;
           unsigned NumSoftExternalUses = 0;
           unsigned NumUses = 0;
           for (auto IB = Inst->user_begin(), IE = Inst->user_end();
                IB != IE && NumUses <= 6; ++IB) {
             Instruction *UseInstr = cast<Instruction>(*IB);
             unsigned Opc = UseInstr->getOpcode();
             NumUses++;
const SCEVAddRecExpr* WidenIV::getExtendedOperandRecurrence(NarrowIVDefUse DU) {
   return AddRec;
 }
 
 /// Is this instruction potentially interesting for further simplification after
 /// widening it's type? In other words, can the extend be safely hoisted out of
 /// the loop with SCEV reducing the value to a recurrence on the same loop. If
 /// so, return the sign or zero extended recurrence. Otherwise return NULL.
 const SCEVAddRecExpr *WidenIV::getWideRecurrence(Instruction *NarrowUse) {
-  if (!SE->isSCEVable(NarrowUse->getType()))
+  if (!SE->isSCEVable(NarrowUse->getType()) ||
+      NarrowUse->getType()->isFloatingPointTy())
     return nullptr;
 
   const SCEV *NarrowExpr = SE->getSCEV(NarrowUse);
   if (SE->getTypeSizeInBits(NarrowExpr->getType())
       >= SE->getTypeSizeInBits(WideType)) {
     // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
     // index. So don't follow this use.
     return nullptr;

../lib/Transforms/Utils/LoopUtils.cpp

assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
          "StartValue is not an integer for integer induction");
 
   // Check the Step Value. It should be non-zero integer value.
   assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&
          "Step value is zero");
 
   assert((IK != IK_PtrInduction || getConstIntStepValue()) &&
          "Step value should be constant for pointer induction");
-  assert(Step->getType()->isIntegerTy() && "StepValue is not an integer");
+  assert(((IK != IK_PtrInduction && IK != IK_IntInduction) ||
+         Step->getType()->isIntegerTy()) && "StepValue is not an integer");
+
+  assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&
+         "StepValue is not FP for FpInduction");
 }
 
 int InductionDescriptor::getConsecutiveDirection() const {
   ConstantInt *ConstStep = getConstIntStepValue();
   if (ConstStep && (ConstStep->isOne() || ConstStep->isMinusOne()))
     return ConstStep->getSExtValue();
   return 0;
 }
case IK_PtrInduction: {
     assert(Index->getType() == Step->getType() &&
            "Index type does not match StepValue type");
     assert(isa<SCEVConstant>(Step) &&
            "Expected constant step for pointer induction");
     const SCEV *S = SE->getMulExpr(SE->getSCEV(Index), Step);
     Index = Exp.expandCodeFor(S, Index->getType(), &*B.GetInsertPoint());
     return B.CreateGEP(nullptr, StartValue, Index);
   }
+  case IK_FpInduction: {
+    assert(Index->getType() == Step->getType() &&
+           "Index type does not match StepValue type");
+    assert(Step->getType()->isFloatingPointTy() && "Expected FP Step value");
+    const SCEV *S = SE->getFAddExpr(SE->getSCEV(StartValue),
+                                    SE->getFMulExpr(Step, SE->getSCEV(Index)));
+    return Exp.expandCodeFor(S, nullptr, &*B.GetInsertPoint());
+  }
   case IK_NoInduction:
     return nullptr;
   }
   llvm_unreachable("invalid enum");
 }
 
+bool InductionDescriptor::isFpInductionPHI(PHINode *Phi, ScalarEvolution *SE,
+                                           InductionDescriptor &D) {
+
+  // Here we only handle FP induction variables.
+  assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
+
+  // Check that the PHI is consecutive.
+  const SCEV *PhiScev = SE->getSCEV(Phi);
+  const SCEVFAddRecExpr *AR = dyn_cast<SCEVFAddRecExpr>(PhiScev);
+
+  if (!AR) {
+    DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
+    return false;
+  }
+
+  assert(AR->getLoop()->getHeader() == Phi->getParent() &&
+         "PHI is an AddRec for a different loop?!");
+  Value *StartValue =
+    Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
+  const SCEV *Step = AR->getStepRecurrence(*SE);
+
+  // The Step should be loop invariant for induction variables
+  if (!SE->isLoopInvariant(Step, AR->getLoop()))
+    return false;
+  D = InductionDescriptor(StartValue, IK_FpInduction, Step);
+  return true;
+}
+
 bool InductionDescriptor::isInductionPHI(PHINode *Phi,
                                          PredicatedScalarEvolution &PSE,
                                          InductionDescriptor &D,
                                          bool Assume) {
   Type *PhiTy = Phi->getType();
-  // We only handle integer and pointer inductions variables.
-  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
+
+  // Handle integer and pointer inductions variables.
+  // Now we handle also FP induction but not trying to make a
+  // recurrent expression from the PHI node in-place.
+
+  if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() &&
+      !PhiTy->isFloatTy() && !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())
     return false;
 
+  if (PhiTy->isFloatingPointTy())
+    return isFpInductionPHI(Phi, PSE.getSE(), D);
+
   const SCEV *PhiScev = PSE.getSCEV(Phi);
-  const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
 
+  const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
   // We need this expression to be an AddRecExpr.
   if (Assume && !AR)
     AR = PSE.getAsAddRec(Phi);
 
   if (!AR) {
     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
     return false;
   }

../lib/Transforms/Utils/SimplifyIndVar.cpp

 /// instructions in-place during analysis. Rather than rewriting induction
 /// variables bottom-up from their users, it transforms a chain of IVUsers
 /// top-down, updating the IR only when it encounters a clear optimization
 /// opportunity.
 ///
 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
 ///
 void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
-  if (!SE->isSCEVable(CurrIV->getType()))
+  if (!SE->isSCEVable(CurrIV->getType()) &&
+      !CurrIV->getType()->isFloatingPointTy())
     return;
 
   // Instructions processed by SimplifyIndvar for CurrIV.
   SmallPtrSet<Instruction*,16> Simplified;
 
   // Use-def pairs if IV users waiting to be processed for CurrIV.
   SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
 

../lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::widenInductionVariable(const InductionDescriptor &II,
 
   VecInd->addIncoming(SteppedStart, LoopVectorPreHeader);
   VecInd->addIncoming(LastInduction, LoopVectorBody);
 }
 
 Value *InnerLoopVectorizer::getStepVector(Value *Val, int StartIdx,
                                           Value *Step) {
   assert(Val->getType()->isVectorTy() && "Must be a vector");
-  assert(Val->getType()->getScalarType()->isIntegerTy() &&
-         "Elem must be an integer");
+  assert((Val->getType()->getScalarType()->isIntegerTy() ||
+          Val->getType()->getScalarType()->isFloatingPointTy()) &&
+         "Induction Step must be an integer or FP");
   assert(Step->getType() == Val->getType()->getScalarType() &&
          "Step has wrong type");
   // Create the types.
   Type *ITy = Val->getType()->getScalarType();
   VectorType *Ty = cast<VectorType>(Val->getType());
   int VLen = Ty->getNumElements();
   SmallVector<Constant *, 8> Indices;
 
+  bool IsInteger = Step->getType()->isIntegerTy();
+
   // Create a vector of consecutive numbers from zero to VF.
   for (int i = 0; i < VLen; ++i)
-    Indices.push_back(ConstantInt::get(ITy, StartIdx + i));
+    IsInteger ?
+     Indices.push_back(ConstantInt::get(ITy, StartIdx + i)) :
+     Indices.push_back(ConstantFP::get(ITy, (double)(StartIdx + i)));
 
   // Add the consecutive indices to the vector value.
   Constant *Cv = ConstantVector::get(Indices);
   assert(Cv->getType() == Val->getType() && "Invalid consecutive vec");
   Step = Builder.CreateVectorSplat(VLen, Step);
   assert(Step->getType() == Val->getType() && "Invalid step vec");
+
+  if (IsInteger) {
     // FIXME: The newly created binary instructions should contain nsw/nuw flags,
     // which can be found from the original scalar operations.
     Step = Builder.CreateMul(Cv, Step);
     return Builder.CreateAdd(Val, Step, "induction");
   }
+  // FP induction
+  Step = Builder.CreateFMul(Cv, Step);
+  return Builder.CreateFAdd(Val, Step, "induction");
+}
 
 int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) {
   assert(Ptr->getType()->isPointerTy() && "Unexpected non-ptr");
   auto *SE = PSE.getSE();
   // Make sure that the pointer does not point to structs.
   if (Ptr->getType()->getPointerElementType()->isAggregateType())
     return 0;
 
for (I = List->begin(), E = List->end(); I != E; ++I) {
     PHINode *BCResumeVal = PHINode::Create(
         OrigPhi->getType(), 3, "bc.resume.val", ScalarPH->getTerminator());
     Value *EndValue;
     if (OrigPhi == OldInduction) {
       // We know what the end value is.
       EndValue = CountRoundDown;
     } else {
       IRBuilder<> B(LoopBypassBlocks.back()->getTerminator());
-      Value *CRD = B.CreateSExtOrTrunc(CountRoundDown,
-                                       II.getStep()->getType(), "cast.crd");
+      Value *CRD;
+      if (II.getStep()->getType()->isIntegerTy())
+        CRD = B.CreateSExtOrTrunc(CountRoundDown, II.getStep()->getType(),
+                                  "cast.crd");
+      else
+        CRD = B.CreateCast(Instruction::SIToFP, CountRoundDown,
       const DataLayout &DL = OrigLoop->getHeader()->getModule()->getDataLayout();
       EndValue = II.transform(B, CRD, PSE.getSE(), DL);
       EndValue->setName("ind.end");
     }
 
     // The new PHI merges the original incoming value, in case of a bypass,
     // or the value at the end of the vectorized loop.
     BCResumeVal->addIncoming(EndValue, MiddleBlock);
if (P != OldInduction || VF == 1) {
         Entry[part] = getStepVector(Broadcasted, VF * part, II.getStep());
     } else {
       // Instead of re-creating the vector IV by splatting the scalar IV
       // in each iteration, we can make a new independent vector IV.
       widenInductionVariable(II, Entry);
     }
     return;
   }
+  case InductionDescriptor::IK_FpInduction: {
+    assert(P->getType() == II.getStartValue()->getType() &&
+            "Types must match");
+    // Handle other induction variables that are now based on the
+    // canonical one.
+    Value *V = Induction;
+    if (P != OldInduction) {
+      V = Builder.CreateCast(Instruction::SIToFP, Induction, P->getType());
+      V = II.transform(Builder, V, PSE.getSE(), DL);
+      V->setName("fp.offset.idx");
+    }
+    Value *Broadcasted = getBroadcastInstrs(V);
+    // After broadcasting the induction variable we need to make the vector
+    // consecutive by adding 0, 1, 2, etc.
+    for (unsigned part = 0; part < UF; ++part)
+      Entry[part] = getStepVector(Broadcasted, VF * part, II.getStep());
+    return;
+  }
   case InductionDescriptor::IK_PtrInduction:
     // Handle the pointer induction variable case.
     assert(P->getType()->isPointerTy() && "Unexpected type.");
     // This is the normalized GEP that starts counting at zero.
     Value *PtrInd = Induction;
     PtrInd = Builder.CreateSExtOrTrunc(PtrInd, II.getStep()->getType());
     // This is the vector of results. Notice that we don't generate
     // vector geps because scalar geps result in better code.

 
 bool LoopVectorizationLegality::addInductionPhi(PHINode *Phi,
                                                 InductionDescriptor ID) {
   Inductions[Phi] = ID;
   Type *PhiTy = Phi->getType();
   const DataLayout &DL = Phi->getModule()->getDataLayout();
 
   // Get the widest type.
+  if (!PhiTy->isFloatingPointTy()) {
     if (!WidestIndTy)
       WidestIndTy = convertPointerToIntegerType(DL, PhiTy);
     else
       WidestIndTy = getWiderType(DL, PhiTy, WidestIndTy);
+  }
 
   // Int inductions are special because we only allow one IV.
   if (ID.getKind() == InductionDescriptor::IK_IntInduction &&
       ID.getConstIntStepValue() &&
       ID.getConstIntStepValue()->isOne() &&
       isa<Constant>(ID.getStartValue()) &&
       cast<Constant>(ID.getStartValue())->isNullValue()) {
 
Value *StepValue = Exp.expandCodeFor(StepSCEV, StepSCEV->getType(),
                                        &*Builder.GetInsertPoint());
   return getStepVector(Val, StartIdx, StepValue);
 }
 
 Value *InnerLoopUnroller::getStepVector(Value *Val, int StartIdx, Value *Step) {
   // When unrolling and the VF is 1, we only need to add a simple scalar.
   Type *ITy = Val->getType();
   assert(!ITy->isVectorTy() && "Val must be a scalar");
+
+  if (Val->getType()->isFloatingPointTy()) {
+    Constant *C = ConstantFP::get(ITy, (double)StartIdx);
+    return Builder.CreateFAdd(Val, Builder.CreateFMul(C, Step), "induction");
+  }
   Constant *C = ConstantInt::get(ITy, StartIdx);
   return Builder.CreateAdd(Val, Builder.CreateMul(C, Step), "induction");
 }

../test/Transforms/IndVarSimplify/floating-point-iv.ll

 
 exit:
   ret void
 
 ; CHECK-LABEL: @test5(
 ; CHECK: icmp slt i32 {{.*}}, 0
 ; CHECK-NEXT: br i1
 }
+
+
+;float @fp_iv_simplify(float start, int N) {
+;  int i=0;
+;  float res = start;
+;  for (; i< N; i++) {
+;    res += (float)0.1;
+;  }
+;  return res;
+;}
+
+; CHECK-LABEL: @fp_iv_simplify(
+; CHECK: for.body.preheader:
+; CHECK:  %[[N:.*]] = sitofp i32 %{{.*}} to float
+; CHECK:  %[[MUL_RES:.*]] = fmul float %[[N]], 0x3FB99999A0000000
+; CHECK: for.end.loopexit:
+; CHECK: fadd float %start, %[[MUL_RES]]
+
+
+define float @fp_iv_simplify(float %start, i32 %N) {
+entry:
+  %cmp2 = icmp sgt i32 %N, 0
+  br i1 %cmp2, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %res.04 = phi float [ %add, %for.body ], [ %start, %for.body.preheader ]
+  %i.03 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]
+  %add = fadd float %res.04, 0x3FB99999A0000000
+  %inc = add nsw i32 %i.03, 1
+  %cmp = icmp slt i32 %inc, %N
+  br i1 %cmp, label %for.body, label %for.end.loopexit
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  %res.0.lcssa = phi float [ %start, %entry ], [ %add, %for.end.loopexit ]
+  ret float %res.0.lcssa
+}

../test/Transforms/LoopVectorize/float-induction.ll

+; RUN: opt < %s  -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -dce -instcombine -S | FileCheck %s
+
+
+; CHECK-LABEL: @fp_iv_loop1(
+; CHECK: %[[FP_INC:.*]] = load float, float* @fp_inc, align 4
+; CHECK: %[[FP_INC_NEG:.*]] = fsub float -0.000000e+00, %[[FP_INC]]
+; CHECK: vector.body:
+; CHECK:  %[[VAR1:.*]] = insertelement <4 x float> undef, float %[[FP_INC_NEG]], i32 0
+; CHECK:  %[[VAR2:.*]] = shufflevector <4 x float> %[[VAR1]], <4 x float> undef, <4 x i32> zeroinitializer
+; CHECK:  fmul <4 x float> %[[VAR2]], <float 0.000000e+00, float 1.000000e+00, float 2.000000e+00, float 3.000000e+00>
+; CHECK:  store <4 x float>
+
+@fp_inc = common global float 0.000000e+00, align 4
+
+;void fp_iv_loop1(float init, float * __restrict__ A, int N) {
+;  float x = init;
+;  for (int i=0; i < N; ++i) {
+;    A[i] = x;
+;    x -= fp_inc;
+;  }
+;}
+
+define void @fp_iv_loop1(float %init, float* noalias nocapture %A, i32 %N) #0 {
+entry:
+  %cmp4 = icmp sgt i32 %N, 0
+  br i1 %cmp4, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  %0 = load float, float* @fp_inc, align 4
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %indvars.iv = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]
+  %x.05 = phi float [ %init, %for.body.lr.ph ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv
+  store float %x.05, float* %arrayidx, align 4
+  %add = fsub float %x.05, %0
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %N
+  br i1 %exitcond, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  ret void
+}
+
+;void fp_iv_loop2(float init, float * __restrict__ A, int N) {
+;  float x = init;
+;  for (int i=0; i < N; ++i) {
+;    A[i] = x;
+;    x += 0.5;
+;  }
+;}
+
+; CHECK-LABEL: @fp_iv_loop2(
+; CHECK: vector.body
+; CHECK:  %[[index:.*]] = phi i64 [ 0, %vector.ph ]
+; CHECK: sitofp i64 %[[index]] to float
+; CHECK: %[[VAR1:.*]] = fmul float {{.*}}, 5.000000e-01
+; CHECK: %[[VAR2:.*]] = fadd float %[[VAR1]]
+; CHECK:  insertelement <4 x float> undef, float %[[VAR2]], i32 0
+; CHECK:  shufflevector <4 x float> {{.*}}, <4 x float> undef, <4 x i32> zeroinitializer
+; CHECK:  fadd <4 x float> {{.*}}, <float 0.000000e+00, float 5.000000e-01, float 1.000000e+00, float 1.500000e+00>
+; CHECK:  store <4 x float> 
+
+define void @fp_iv_loop2(float %init, float* noalias nocapture %A, i32 %N) #0 {
+entry:
+  %cmp4 = icmp sgt i32 %N, 0
+  br i1 %cmp4, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
+  %x.06 = phi float [ %conv1, %for.body ], [ %init, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv
+  store float %x.06, float* %arrayidx, align 4
+  %conv1 = fadd float %x.06, 5.000000e-01
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %N
+  br i1 %exitcond, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  ret void
+}
+
+;void fp_iv_loop3(float init, float * __restrict__ A, float * __restrict__ B, float * __restrict__ C, int N) {
+;  int i = 0;
+;  float x = init;
+;  float y = 0.1;
+;  for (; i < N; ++i) {
+;    A[i] = x;
+;    x += fp_inc;
+;    y -= 0.5;
+;    B[i] = x + y;
+;    C[i] = y;
+;  }
+;}
+; CHECK-LABEL: @fp_iv_loop3(
+; CHECK: vector.body
+; CHECK:  %[[index:.*]] = phi i64 [ 0, %vector.ph ]
+; CHECK: sitofp i64 %[[index]] to float
+; CHECK: %[[VAR1:.*]] = fmul float {{.*}}, -5.000000e-01
+; CHECK: %[[VAR2:.*]] = fadd float %[[VAR1]]
+; CHECK:  insertelement <4 x float> undef, float %[[VAR2]], i32 0
+; CHECK:  shufflevector <4 x float> {{.*}}, <4 x float> undef, <4 x i32> zeroinitializer
+; CHECK:  fadd <4 x float> {{.*}}, <float -0.000000e+00, float -5.000000e-01, float -1.000000e+00, float -1.500000e+00>
+; CHECK:  store <4 x float>
+
+define void @fp_iv_loop3(float %init, float* noalias nocapture %A, float* noalias nocapture %B, float* noalias nocapture %C, i32 %N) #0 {
+entry:
+  %cmp9 = icmp sgt i32 %N, 0
+  br i1 %cmp9, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  %0 = load float, float* @fp_inc, align 4
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %indvars.iv = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]
+  %y.012 = phi float [ 0x3FB99999A0000000, %for.body.lr.ph ], [ %conv1, %for.body ]
+  %x.011 = phi float [ %init, %for.body.lr.ph ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv
+  store float %x.011, float* %arrayidx, align 4
+  %add = fadd float %x.011, %0
+  %conv1 = fadd float %y.012, -5.000000e-01
+  %add2 = fadd float %conv1, %add
+  %arrayidx4 = getelementptr inbounds float, float* %B, i64 %indvars.iv
+  store float %add2, float* %arrayidx4, align 4
+  %arrayidx6 = getelementptr inbounds float, float* %C, i64 %indvars.iv
+  store float %conv1, float* %arrayidx6, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %N
+  br i1 %exitcond, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:                                 
+  br label %for.end
+
+for.end: 
+  ret void
+}