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

//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// 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/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Pass.h"
#include <cassert>
#include <cstdint>
#include <memory>
#include <optional>
#include <utility>

namespace llvm {

class OverflowingBinaryOperator;
class AssumptionCache;
class BasicBlock;
class Constant;
class ConstantInt;
class DataLayout;
class DominatorTree;
class GEPOperator;
class LLVMContext;
class Loop;
class LoopInfo;
class raw_ostream;
class ScalarEvolution;
class SCEVAddRecExpr;
class SCEVUnknown;
class StructType;
class TargetLibraryInfo;
class Type;
enum SCEVTypes : unsigned short;

extern bool VerifySCEV;

/// 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 { … };

// Specialize FoldingSetTrait for SCEV to avoid needing to compute
// temporary FoldingSetNodeID values.
template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> { … };

inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { … }

/// 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 { … };

/// This class represents an assumption made using SCEV expressions which can
/// be checked at run-time.
class SCEVPredicate : public FoldingSetNode { … };

inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) { … }

// Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute
// temporary FoldingSetNodeID values.
template <>
struct FoldingSetTrait<SCEVPredicate> : DefaultFoldingSetTrait<SCEVPredicate> { … };

/// This class represents an assumption that the expression LHS Pred RHS
/// evaluates to true, and this can be checked at run-time.
class SCEVComparePredicate final : public SCEVPredicate { … };

/// This class represents an assumption made on an AddRec expression. Given an
/// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw
/// flags (defined below) in the first X iterations of the loop, where X is a
/// SCEV expression returned by getPredicatedBackedgeTakenCount).
///
/// Note that this does not imply that X is equal to the backedge taken
/// count. This means that if we have a nusw predicate for i32 {0,+,1} with a
/// predicated backedge taken count of X, we only guarantee that {0,+,1} has
/// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we
/// have more than X iterations.
class SCEVWrapPredicate final : public SCEVPredicate { … };

/// This class represents a composition of other SCEV predicates, and is the
/// class that most clients will interact with.  This is equivalent to a
/// logical "AND" of all the predicates in the union.
///
/// NB! Unlike other SCEVPredicate sub-classes this class does not live in the
/// ScalarEvolution::Preds folding set.  This is why the \c add function is sound.
class SCEVUnionPredicate final : public SCEVPredicate { … };

/// 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 { … };

/// Analysis pass that exposes the \c ScalarEvolution for a function.
class ScalarEvolutionAnalysis
    : public AnalysisInfoMixin<ScalarEvolutionAnalysis> { … };

/// Verifier pass for the \c ScalarEvolutionAnalysis results.
class ScalarEvolutionVerifierPass
    : public PassInfoMixin<ScalarEvolutionVerifierPass> { … };

/// Printer pass for the \c ScalarEvolutionAnalysis results.
class ScalarEvolutionPrinterPass
    : public PassInfoMixin<ScalarEvolutionPrinterPass> { … };

class ScalarEvolutionWrapperPass : public FunctionPass { … };

/// An interface layer with SCEV used to manage how we see SCEV expressions
/// for values in the context of existing predicates. We can add new
/// predicates, but we cannot remove them.
///
/// This layer has multiple purposes:
///   - provides a simple interface for SCEV versioning.
///   - guarantees that the order of transformations applied on a SCEV
///     expression for a single Value is consistent across two different
///     getSCEV calls. This means that, for example, once we've obtained
///     an AddRec expression for a certain value through expression
///     rewriting, we will continue to get an AddRec expression for that
///     Value.
///   - lowers the number of expression rewrites.
class PredicatedScalarEvolution { … };

template <> struct DenseMapInfo<ScalarEvolution::FoldID> { … };

} // end namespace llvm

#endif // LLVM_ANALYSIS_SCALAREVOLUTION_H