path: root/include/llvm/Analysis/ScalarEvolution.h

//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// The ScalarEvolution class is an LLVM pass which can be used to analyze and
// categorize scalar expressions in loops.  It specializes in recognizing
// general induction variables, representing them with the abstract and opaque
// SCEV class.  Given this analysis, trip counts of loops and other important
// properties can be obtained.
//
// This analysis is primarily useful for induction variable substitution and
// strength reduction.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
#define LLVM_ANALYSIS_SCALAREVOLUTION_H

#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Operator.h"
#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/DataTypes.h"
#include "llvm/Support/ValueHandle.h"
#include <map>

namespace llvm {
  class APInt;
  class Constant;
  class ConstantInt;
  class DominatorTree;
  class Type;
  class ScalarEvolution;
  class DataLayout;
  class TargetLibraryInfo;
  class LLVMContext;
  class Loop;
  class LoopInfo;
  class Operator;
  class SCEVUnknown;
  class SCEV;
  template<> struct FoldingSetTrait<SCEV>;

  /// SCEV - This class represents an analyzed expression in the program.  These
  /// are opaque objects that the client is not allowed to do much with
  /// directly.
  ///
  class SCEV : public FoldingSetNode {
    friend struct FoldingSetTrait<SCEV>;

    /// FastID - A reference to an Interned FoldingSetNodeID for this node.
    /// The ScalarEvolution's BumpPtrAllocator holds the data.
    FoldingSetNodeIDRef FastID;

    // The SCEV baseclass this node corresponds to
    const unsigned short SCEVType;

  protected:
    /// SubclassData - This field is initialized to zero and may be used in
    /// subclasses to store miscellaneous information.
    unsigned short SubclassData;

  private:
    SCEV(const SCEV &) LLVM_DELETED_FUNCTION;
    void operator=(const SCEV &) LLVM_DELETED_FUNCTION;

  public:
    /// NoWrapFlags are bitfield indices into SubclassData.
    ///
    /// Add and Mul expressions may have no-unsigned-wrap <NUW> or
    /// no-signed-wrap <NSW> properties, which are derived from the IR
    /// operator. NSW is a misnomer that we use to mean no signed overflow or
    /// underflow.
    ///
    /// AddRec expression may have a no-self-wraparound <NW> property if the
    /// result can never reach the start value. This property is independent of
    /// the actual start value and step direction. Self-wraparound is defined
    /// purely in terms of the recurrence's loop, step size, and
    /// bitwidth. Formally, a recurrence with no self-wraparound satisfies:
    /// abs(step) * max-iteration(loop) <= unsigned-max(bitwidth).
    ///
    /// Note that NUW and NSW are also valid properties of a recurrence, and
    /// either implies NW. For convenience, NW will be set for a recurrence
    /// whenever either NUW or NSW are set.
    enum NoWrapFlags { FlagAnyWrap = 0,          // No guarantee.
                       FlagNW      = (1 << 0),   // No self-wrap.
                       FlagNUW     = (1 << 1),   // No unsigned wrap.
                       FlagNSW     = (1 << 2),   // No signed wrap.
                       NoWrapMask  = (1 << 3) -1 };

    explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) :
      FastID(ID), SCEVType(SCEVTy), SubclassData(0) {}

    unsigned getSCEVType() const { return SCEVType; }

    /// getType - Return the LLVM type of this SCEV expression.
    ///
    Type *getType() const;

    /// isZero - Return true if the expression is a constant zero.
    ///
    bool isZero() const;

    /// isOne - Return true if the expression is a constant one.
    ///
    bool isOne() const;

    /// isAllOnesValue - Return true if the expression is a constant
    /// all-ones value.
    ///
    bool isAllOnesValue() const;

    /// isNonConstantNegative - Return true if the specified scev is negated,
    /// but not a constant.
    bool isNonConstantNegative() const;

    /// print - Print out the internal representation of this scalar to the
    /// specified stream.  This should really only be used for debugging
    /// purposes.
    void print(raw_ostream &OS) const;

    /// dump - This method is used for debugging.
    ///
    void dump() const;
  };

  // Specialize FoldingSetTrait for SCEV to avoid needing to compute
  // temporary FoldingSetNodeID values.
  template<> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
    static void Profile(const SCEV &X, FoldingSetNodeID& ID) {
      ID = X.FastID;
    }
    static bool Equals(const SCEV &X, const FoldingSetNodeID &ID,
                       unsigned IDHash, FoldingSetNodeID &TempID) {
      return ID == X.FastID;
    }
    static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
      return X.FastID.ComputeHash();
    }
  };

  inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
    S.print(OS);
    return OS;
  }

  /// SCEVCouldNotCompute - An object of this class is returned by queries that
  /// could not be answered.  For example, if you ask for the number of
  /// iterations of a linked-list traversal loop, you will get one of these.
  /// None of the standard SCEV operations are valid on this class, it is just a
  /// marker.
  struct SCEVCouldNotCompute : public SCEV {
    SCEVCouldNotCompute();

    /// Methods for support type inquiry through isa, cast, and dyn_cast:
    static bool classof(const SCEV *S);
  };

  /// ScalarEvolution - This class is the main scalar evolution driver.  Because
  /// client code (intentionally) can't do much with the SCEV objects directly,
  /// they must ask this class for services.
  ///
  class ScalarEvolution : public FunctionPass {
  public:
    /// LoopDisposition - An enum describing the relationship between a
    /// SCEV and a loop.
    enum LoopDisposition {
      LoopVariant,    ///< The SCEV is loop-variant (unknown).
      LoopInvariant,  ///< The SCEV is loop-invariant.
      LoopComputable  ///< The SCEV varies predictably with the loop.
    };

    /// BlockDisposition - An enum describing the relationship between a
    /// SCEV and a basic block.
    enum BlockDisposition {
      DoesNotDominateBlock,  ///< The SCEV does not dominate the block.
      DominatesBlock,        ///< The SCEV dominates the block.
      ProperlyDominatesBlock ///< The SCEV properly dominates the block.
    };

    /// Convenient NoWrapFlags manipulation that hides enum casts and is
    /// visible in the ScalarEvolution name space.
    static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask) {
      return (SCEV::NoWrapFlags)(Flags & Mask);
    }
    static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags