InductiveRangeCheckElimination.cpp | Explore in Territory

//===- InductiveRangeCheckElimination.cpp - -------------------------------===//
//
// 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 InductiveRangeCheckElimination pass splits a loop's iteration space into
// three disjoint ranges.  It does that in a way such that the loop running in
// the middle loop provably does not need range checks. As an example, it will
// convert
//
//   len = < known positive >
//   for (i = 0; i < n; i++) {
//     if (0 <= i && i < len) {
//       do_something();
//     } else {
//       throw_out_of_bounds();
//     }
//   }
//
// to
//
//   len = < known positive >
//   limit = smin(n, len)
//   // no first segment
//   for (i = 0; i < limit; i++) {
//     if (0 <= i && i < len) { // this check is fully redundant
//       do_something();
//     } else {
//       throw_out_of_bounds();
//     }
//   }
//   for (i = limit; i < n; i++) {
//     if (0 <= i && i < len) {
//       do_something();
//     } else {
//       throw_out_of_bounds();
//     }
//   }
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/PriorityWorklist.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopConstrainer.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <optional>
#include <utility>

usingnamespacellvm;
usingnamespacellvm::PatternMatch;

static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
                                        cl::init(64));

static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
                                       cl::init(false));

static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
                                      cl::init(false));

static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
                                             cl::Hidden, cl::init(false));

static cl::opt<unsigned> MinRuntimeIterations("irce-min-runtime-iterations",
                                              cl::Hidden, cl::init(10));

static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
                                                 cl::Hidden, cl::init(true));

static cl::opt<bool> AllowNarrowLatchCondition(
    "irce-allow-narrow-latch", cl::Hidden, cl::init(true),
    cl::desc("If set to true, IRCE may eliminate wide range checks in loops "
             "with narrow latch condition."));

static cl::opt<unsigned> MaxTypeSizeForOverflowCheck(
    "irce-max-type-size-for-overflow-check", cl::Hidden, cl::init(32),
    cl::desc(
        "Maximum size of range check type for which can be produced runtime "
        "overflow check of its limit's computation"));

static cl::opt<bool>
    PrintScaledBoundaryRangeChecks("irce-print-scaled-boundary-range-checks",
                                   cl::Hidden, cl::init(false));

#define DEBUG_TYPE …

namespace {

/// An inductive range check is conditional branch in a loop with
///
///  1. a very cold successor (i.e. the branch jumps to that successor very
///     rarely)
///
///  and
///
///  2. a condition that is provably true for some contiguous range of values
///     taken by the containing loop's induction variable.
///
class InductiveRangeCheck { … };

class InductiveRangeCheckElimination { … };

} // end anonymous namespace

/// Parse a single ICmp instruction, `ICI`, into a range check.  If `ICI` cannot
/// be interpreted as a range check, return false.  Otherwise set `Index` to the
/// SCEV being range checked, and set `End` to the upper or lower limit `Index`
/// is being range checked.
bool InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
                                              ScalarEvolution &SE,
                                              const SCEVAddRecExpr *&Index,
                                              const SCEV *&End) { … }

// Try to parse range check in the form of "IV vs Limit"
bool InductiveRangeCheck::parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS,
                                              ICmpInst::Predicate Pred,
                                              ScalarEvolution &SE,
                                              const SCEVAddRecExpr *&Index,
                                              const SCEV *&End) { … }

// Try to parse range check in the form of "IV - Offset vs Limit" or "Offset -
// IV vs Limit"
bool InductiveRangeCheck::reassociateSubLHS(
    Loop *L, Value *VariantLHS, Value *InvariantRHS, ICmpInst::Predicate Pred,
    ScalarEvolution &SE, const SCEVAddRecExpr *&Index, const SCEV *&End) { … }

void InductiveRangeCheck::extractRangeChecksFromCond(
    Loop *L, ScalarEvolution &SE, Use &ConditionUse,
    SmallVectorImpl<InductiveRangeCheck> &Checks,
    SmallPtrSetImpl<Value *> &Visited) { … }

void InductiveRangeCheck::extractRangeChecksFromBranch(
    BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
    SmallVectorImpl<InductiveRangeCheck> &Checks, bool &Changed) { … }

/// If the type of \p S matches with \p Ty, return \p S. Otherwise, return
/// signed or unsigned extension of \p S to type \p Ty.
static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE,
                                bool Signed) { … }

// Compute a safe set of limits for the main loop to run in -- effectively the
// intersection of `Range' and the iteration space of the original loop.
// Return std::nullopt if unable to compute the set of subranges.
static std::optional<LoopConstrainer::SubRanges>
calculateSubRanges(ScalarEvolution &SE, const Loop &L,
                   InductiveRangeCheck::Range &Range,
                   const LoopStructure &MainLoopStructure) { … }

/// Computes and returns a range of values for the induction variable (IndVar)
/// in which the range check can be safely elided.  If it cannot compute such a
/// range, returns std::nullopt.
std::optional<InductiveRangeCheck::Range>
InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
                                               const SCEVAddRecExpr *IndVar,
                                               bool IsLatchSigned) const { … }

static std::optional<InductiveRangeCheck::Range>
IntersectSignedRange(ScalarEvolution &SE,
                     const std::optional<InductiveRangeCheck::Range> &R1,
                     const InductiveRangeCheck::Range &R2) { … }

static std::optional<InductiveRangeCheck::Range>
IntersectUnsignedRange(ScalarEvolution &SE,
                       const std::optional<InductiveRangeCheck::Range> &R1,
                       const InductiveRangeCheck::Range &R2) { … }

PreservedAnalyses IRCEPass::run(Function &F, FunctionAnalysisManager &AM) { … }

bool
InductiveRangeCheckElimination::isProfitableToTransform(const Loop &L,
                                                        LoopStructure &LS) { … }

bool InductiveRangeCheckElimination::run(
    Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) { … }
llvm/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
