<commit_before>//===-- InductiveRangeCheckElimination.cpp - ------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
// 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/ADT/Optional.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include <array>

using namespace llvm;

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<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
                                          cl::Hidden, cl::init(10));

#define DEBUG_TYPE "irce"

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 {
  // Classifies a range check
  enum RangeCheckKind : unsigned {
    // Range check of the form "0 <= I".
    RANGE_CHECK_LOWER = 1,

    // Range check of the form "I < L" where L is known positive.
    RANGE_CHECK_UPPER = 2,

    // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER
    // conditions.
    RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER,

    // Unrecognized range check condition.
    RANGE_CHECK_UNKNOWN = (unsigned)-1
  };

  static const char *rangeCheckKindToStr(RangeCheckKind);

  const SCEV *Offset;
  const SCEV *Scale;
  Value *Length;
  BranchInst *Branch;
  RangeCheckKind Kind;

  static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
                                            ScalarEvolution &SE, Value *&Index,
                                            Value *&Length);

  static InductiveRangeCheck::RangeCheckKind
  parseRangeCheck(Loop *L, ScalarEvolution &SE, Value *Condition,
                  const SCEV *&Index, Value *&UpperLimit);

  InductiveRangeCheck() :
    Offset(nullptr), Scale(nullptr), Length(nullptr), Branch(nullptr) { }

public:
  const SCEV *getOffset() const { return Offset; }
  const SCEV *getScale() const { return Scale; }
  Value *getLength() const { return Length; }

  void print(raw_ostream &OS) const {
    OS << "InductiveRangeCheck:\n";
    OS << "  Kind: " << rangeCheckKindToStr(Kind) << "\n";
    OS << "  Offset: ";
    Offset->print(OS);
    OS << "  Scale: ";
    Scale->print(OS);
    OS << "  Length: ";
    if (Length)
      Length->print(OS);
    else
      OS << "(null)";
    OS << "\n  Branch: ";
    getBranch()->print(OS);
    OS << "\n";
  }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  void dump() {
    print(dbgs());
  }
#endif

  BranchInst *getBranch() const { return Branch; }

  /// Represents an signed integer range [Range.getBegin(), Range.getEnd()).  If
  /// R.getEnd() sle R.getBegin(), then R denotes the empty range.

  class Range {
    const SCEV *Begin;
    const SCEV *End;

  public:
    Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
      assert(Begin->getType() == End->getType() && "ill-typed range!");
    }

    Type *getType() const { return Begin->getType(); }
    const SCEV *getBegin() const { return Begin; }
    const SCEV *getEnd() const { return End; }
  };

  typedef SpecificBumpPtrAllocator<InductiveRangeCheck> AllocatorTy;

  /// This is the value the condition of the branch needs to evaluate to for the
  /// branch to take the hot successor (see (1) above).
  bool getPassingDirection() { return true; }

  /// Computes a range for the induction variable (IndVar) in which the range
  /// check is redundant and can be constant-folded away.  The induction
  /// variable is not required to be the canonical {0,+,1} induction variable.
  Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
                                            const SCEVAddRecExpr *IndVar,
                                            IRBuilder<> &B) const;

  /// Create an inductive range check out of BI if possible, else return
  /// nullptr.
  static InductiveRangeCheck *create(AllocatorTy &Alloc, BranchInst *BI,
                                     Loop *L, ScalarEvolution &SE,
                                     BranchProbabilityInfo &BPI);
};

class InductiveRangeCheckElimination : public LoopPass {
  InductiveRangeCheck::AllocatorTy Allocator;

public:
  static char ID;
  InductiveRangeCheckElimination() : LoopPass(ID) {
    initializeInductiveRangeCheckEliminationPass(
        *PassRegistry::getPassRegistry());
  }

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequired<LoopInfoWrapperPass>();
    AU.addRequiredID(LoopSimplifyID);
    AU.addRequiredID(LCSSAID);
    AU.addRequired<ScalarEvolutionWrapperPass>();
    AU.addRequired<BranchProbabilityInfoWrapperPass>();
  }

  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
};

char InductiveRangeCheckElimination::ID = 0;
}

INITIALIZE_PASS(InductiveRangeCheckElimination, "irce",
                "Inductive range check elimination", false, false)

const char *InductiveRangeCheck::rangeCheckKindToStr(
    InductiveRangeCheck::RangeCheckKind RCK) {
  switch (RCK) {
  case InductiveRangeCheck::RANGE_CHECK_UNKNOWN:
    return "RANGE_CHECK_UNKNOWN";

  case InductiveRangeCheck::RANGE_CHECK_UPPER:
    return "RANGE_CHECK_UPPER";

  case InductiveRangeCheck::RANGE_CHECK_LOWER:
    return "RANGE_CHECK_LOWER";

  case InductiveRangeCheck::RANGE_CHECK_BOTH:<commit_msg>[IRCE] Add INITIALIZE_PASS_DEPENDENCY invocations.<commit_after>//===-- InductiveRangeCheckElimination.cpp - ------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
// 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/ADT/Optional.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include <array>

using namespace llvm;

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<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
                                          cl::Hidden, cl::init(10));

#define DEBUG_TYPE "irce"

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 {
  // Classifies a range check
  enum RangeCheckKind : unsigned {
    // Range check of the form "0 <= I".
    RANGE_CHECK_LOWER = 1,

    // Range check of the form "I < L" where L is known positive.
    RANGE_CHECK_UPPER = 2,

    // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER
    // conditions.
    RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER,

    // Unrecognized range check condition.
    RANGE_CHECK_UNKNOWN = (unsigned)-1
  };

  static const char *rangeCheckKindToStr(RangeCheckKind);

  const SCEV *Offset;
  const SCEV *Scale;
  Value *Length;
  BranchInst *Branch;
  RangeCheckKind Kind;

  static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
                                            ScalarEvolution &SE, Value *&Index,
                                            Value *&Length);

  static InductiveRangeCheck::RangeCheckKind
  parseRangeCheck(Loop *L, ScalarEvolution &SE, Value *Condition,
                  const SCEV *&Index, Value *&UpperLimit);

  InductiveRangeCheck() :
    Offset(nullptr), Scale(nullptr), Length(nullptr), Branch(nullptr) { }

public:
  const SCEV *getOffset() const { return Offset; }
  const SCEV *getScale() const { return Scale; }
  Value *getLength() const { return Length; }

  void print(raw_ostream &OS) const {
    OS << "InductiveRangeCheck:\n";
    OS << "  Kind: " << rangeCheckKindToStr(Kind) << "\n";
    OS << "  Offset: ";
    Offset->print(OS);
    OS << "  Scale: ";
    Scale->print(OS);
    OS << "  Length: ";
    if (Length)
      Length->print(OS);
    else
      OS << "(null)";
    OS << "\n  Branch: ";
    getBranch()->print(OS);
    OS << "\n";
  }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  void dump() {
    print(dbgs());
  }
#endif

  BranchInst *getBranch() const { return Branch; }

  /// Represents an signed integer range [Range.getBegin(), Range.getEnd()).  If
  /// R.getEnd() sle R.getBegin(), then R denotes the empty range.

  class Range {
    const SCEV *Begin;
    const SCEV *End;

  public:
    Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
      assert(Begin->getType() == End->getType() && "ill-typed range!");
    }

    Type *getType() const { return Begin->getType(); }
    const SCEV *getBegin() const { return Begin; }
    const SCEV *getEnd() const { return End; }
  };

  typedef SpecificBumpPtrAllocator<InductiveRangeCheck> AllocatorTy;

  /// This is the value the condition of the branch needs to evaluate to for the
  /// branch to take the hot successor (see (1) above).
  bool getPassingDirection() { return true; }

  /// Computes a range for the induction variable (IndVar) in which the range
  /// check is redundant and can be constant-folded away.  The induction
  /// variable is not required to be the canonical {0,+,1} induction variable.
  Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
                                            const SCEVAddRecExpr *IndVar,
                                            IRBuilder<> &B) const;

  /// Create an inductive range check out of BI if possible, else return
  /// nullptr.
  static InductiveRangeCheck *create(AllocatorTy &Alloc, BranchInst *BI,
                                     Loop *L, ScalarEvolution &SE,
                                     BranchProbabilityInfo &BPI);
};

class InductiveRangeCheckElimination : public LoopPass {
  InductiveRangeCheck::AllocatorTy Allocator;

public:
  static char ID;
  InductiveRangeCheckElimination() : LoopPass(ID) {
    initializeInductiveRangeCheckEliminationPass(
        *PassRegistry::getPassRegistry());
  }

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequired<LoopInfoWrapperPass>();
    AU.addRequiredID(LoopSimplifyID);
    AU.addRequiredID(LCSSAID);
    AU.addRequired<ScalarEvolutionWrapperPass>();
    AU.addRequired<BranchProbabilityInfoWrapperPass>();
  }

  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
};

char InductiveRangeCheckElimination::ID = 0;
}

INITIALIZE_PASS_BEGIN(InductiveRangeCheckElimination, "irce",
                      "Inductive range check elimination", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(LCSSA)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
INITIALIZE_PASS_END(InductiveRangeCheckElimination, "irce",
                    "Inductive range check elimination", false, false)

const char *InductiveRangeCheck::rangeCheckKindToStr(
    InductiveRangeCheck::RangeCheckKind RCK) {
  switch (RCK) {
  case InductiveRangeCheck::RANGE_CHECK_UNKNOWN:
    return "RANGE_CHECK_UNKNOWN";

  case InductiveRangeCheck::RANGE_CHECK_UPPER:
    return "RANGE_CHECK_UPPER";

  case InductiveRangeCheck::RANGE_CHECK_LOWER:
    return "RANGE_CHECK_LOWER";

  case InductiveRangeCheck::RANGE_CHECK_BOTH:
{'fraction_non_alphanumeric': 0.14688528662815975, 'fraction_numerical': 0.002360101857027514, 'mean_word_length': 2.6645425580336823, 'pattern_counts': {'":': 0, '<': 91, '<?xml version=': 0, '>': 43, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1560397', 'n_tokens_mistral': 5075, 'n_tokens_neox': 4882, 'n_words': 1253}