IVDescriptors.cpp | Explore in Territory

//===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- 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
//
//===----------------------------------------------------------------------===//
//
// This file "describes" induction and recurrence variables.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/DemandedBits.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/KnownBits.h"

usingnamespacellvm;
usingnamespacellvm::PatternMatch;

#define DEBUG_TYPE …

bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
                                        SmallPtrSetImpl<Instruction *> &Set) { … }

bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurKind Kind) { … }

bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurKind Kind) { … }

/// Determines if Phi may have been type-promoted. If Phi has a single user
/// that ANDs the Phi with a type mask, return the user. RT is updated to
/// account for the narrower bit width represented by the mask, and the AND
/// instruction is added to CI.
static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
                                   SmallPtrSetImpl<Instruction *> &Visited,
                                   SmallPtrSetImpl<Instruction *> &CI) { … }

/// Compute the minimal bit width needed to represent a reduction whose exit
/// instruction is given by Exit.
static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit,
                                                     DemandedBits *DB,
                                                     AssumptionCache *AC,
                                                     DominatorTree *DT) { … }

/// Collect cast instructions that can be ignored in the vectorizer's cost
/// model, given a reduction exit value and the minimal type in which the
// reduction can be represented. Also search casts to the recurrence type
// to find the minimum width used by the recurrence.
static void collectCastInstrs(Loop *TheLoop, Instruction *Exit,
                              Type *RecurrenceType,
                              SmallPtrSetImpl<Instruction *> &Casts,
                              unsigned &MinWidthCastToRecurTy) { … }

// Check if a given Phi node can be recognized as an ordered reduction for
// vectorizing floating point operations without unsafe math.
static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst,
                                  Instruction *Exit, PHINode *Phi) { … }

bool RecurrenceDescriptor::AddReductionVar(
    PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF,
    RecurrenceDescriptor &RedDes, DemandedBits *DB, AssumptionCache *AC,
    DominatorTree *DT, ScalarEvolution *SE) { … }

// We are looking for loops that do something like this:
//   int r = 0;
//   for (int i = 0; i < n; i++) {
//     if (src[i] > 3)
//       r = 3;
//   }
// where the reduction value (r) only has two states, in this example 0 or 3.
// The generated LLVM IR for this type of loop will be like this:
//   for.body:
//     %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ]
//     ...
//     %cmp = icmp sgt i32 %5, 3
//     %spec.select = select i1 %cmp, i32 3, i32 %r
//     ...
// In general we can support vectorization of loops where 'r' flips between
// any two non-constants, provided they are loop invariant. The only thing
// we actually care about at the end of the loop is whether or not any lane
// in the selected vector is different from the start value. The final
// across-vector reduction after the loop simply involves choosing the start
// value if nothing changed (0 in the example above) or the other selected
// value (3 in the example above).
RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isAnyOfPattern(Loop *Loop, PHINode *OrigPhi,
                                     Instruction *I, InstDesc &Prev) { … }

RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isMinMaxPattern(Instruction *I, RecurKind Kind,
                                      const InstDesc &Prev) { … }

/// Returns true if the select instruction has users in the compare-and-add
/// reduction pattern below. The select instruction argument is the last one
/// in the sequence.
///
/// %sum.1 = phi ...
/// ...
/// %cmp = fcmp pred %0, %CFP
/// %add = fadd %0, %sum.1
/// %sum.2 = select %cmp, %add, %sum.1
RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isConditionalRdxPattern(RecurKind Kind, Instruction *I) { … }

RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isRecurrenceInstr(Loop *L, PHINode *OrigPhi,
                                        Instruction *I, RecurKind Kind,
                                        InstDesc &Prev, FastMathFlags FuncFMF) { … }

bool RecurrenceDescriptor::hasMultipleUsesOf(
    Instruction *I, SmallPtrSetImpl<Instruction *> &Insts,
    unsigned MaxNumUses) { … }

bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
                                          RecurrenceDescriptor &RedDes,
                                          DemandedBits *DB, AssumptionCache *AC,
                                          DominatorTree *DT,
                                          ScalarEvolution *SE) { … }

bool RecurrenceDescriptor::isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop,
                                                  DominatorTree *DT) { … }

unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) { … }

SmallVector<Instruction *, 4>
RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const { … }

InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
                                         const SCEV *Step, BinaryOperator *BOp,
                                         SmallVectorImpl<Instruction *> *Casts)
    : … { … }

ConstantInt *InductionDescriptor::getConstIntStepValue() const { … }

bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
                                           ScalarEvolution *SE,
                                           InductionDescriptor &D) { … }

/// This function is called when we suspect that the update-chain of a phi node
/// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts,
/// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime
/// predicate P under which the SCEV expression for the phi can be the
/// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the
/// cast instructions that are involved in the update-chain of this induction.
/// A caller that adds the required runtime predicate can be free to drop these
/// cast instructions, and compute the phi using \p AR (instead of some scev
/// expression with casts).
///
/// For example, without a predicate the scev expression can take the following
/// form:
///      (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)
///
/// It corresponds to the following IR sequence:
/// %for.body:
///   %x = phi i64 [ 0, %ph ], [ %add, %for.body ]
///   %casted_phi = "ExtTrunc i64 %x"
///   %add = add i64 %casted_phi, %step
///
/// where %x is given in \p PN,
/// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate,
/// and the IR sequence that "ExtTrunc i64 %x" represents can take one of
/// several forms, for example, such as:
///   ExtTrunc1:    %casted_phi = and  %x, 2^n-1
/// or:
///   ExtTrunc2:    %t = shl %x, m
///                 %casted_phi = ashr %t, m
///
/// If we are able to find such sequence, we return the instructions
/// we found, namely %casted_phi and the instructions on its use-def chain up
/// to the phi (not including the phi).
static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE,
                                    const SCEVUnknown *PhiScev,
                                    const SCEVAddRecExpr *AR,
                                    SmallVectorImpl<Instruction *> &CastInsts) { … }

bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
                                         PredicatedScalarEvolution &PSE,
                                         InductionDescriptor &D, bool Assume) { … }

bool InductionDescriptor::isInductionPHI(
    PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
    InductionDescriptor &D, const SCEV *Expr,
    SmallVectorImpl<Instruction *> *CastsToIgnore) { … }
llvm/llvm/lib/Analysis/IVDescriptors.cpp
