llvm/llvm/lib/Analysis/IVUsers.cpp

//===- IVUsers.cpp - Induction Variable Users -------------------*- 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 implements bookkeeping for "interesting" users of expressions
// computed from induction variables.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
usingnamespacellvm;

#define DEBUG_TYPE …

AnalysisKey IVUsersAnalysis::Key;

IVUsers IVUsersAnalysis::run(Loop &L, LoopAnalysisManager &AM,
                             LoopStandardAnalysisResults &AR) { … }

char IVUsersWrapperPass::ID = …;
INITIALIZE_PASS_BEGIN(IVUsersWrapperPass, "iv-users",
                      "Induction Variable Users", false, true)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_END(IVUsersWrapperPass, "iv-users", "Induction Variable Users",
                    false, true)

Pass *llvm::createIVUsersPass() { … }

/// isInteresting - Test whether the given expression is "interesting" when
/// used by the given expression, within the context of analyzing the
/// given loop.
static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
                          ScalarEvolution *SE, LoopInfo *LI) { … }

/// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
/// and now we need to decide whether the user should use the preinc or post-inc
/// value.  If this user should use the post-inc version of the IV, return true.
///
/// Choosing wrong here can break dominance properties (if we choose to use the
/// post-inc value when we cannot) or it can end up adding extra live-ranges to
/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
/// should use the post-inc value).
static bool IVUseShouldUsePostIncValue(Instruction *User, Value *Operand,
                                       const Loop *L, DominatorTree *DT) { … }

/// Inspect the specified instruction.  If it is a reducible SCEV, recursively
/// add its users to the IVUsesByStride set and return true.  Otherwise, return
/// false.
bool IVUsers::AddUsersIfInteresting(Instruction *I) { … }

IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) { … }

IVUsers::IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT,
                 ScalarEvolution *SE)
    : … { … }

void IVUsers::print(raw_ostream &OS, const Module *M) const { … }

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

void IVUsers::releaseMemory() { … }

IVUsersWrapperPass::IVUsersWrapperPass() : … { … }

void IVUsersWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

bool IVUsersWrapperPass::runOnLoop(Loop *L, LPPassManager &LPM) { … }

void IVUsersWrapperPass::print(raw_ostream &OS, const Module *M) const { … }

void IVUsersWrapperPass::releaseMemory() { … }

/// getReplacementExpr - Return a SCEV expression which computes the
/// value of the OperandValToReplace.
const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const { … }

/// getExpr - Return the expression for the use.
const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const { … }

static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) { … }

const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const { … }

void IVStrideUse::transformToPostInc(const Loop *L) { … }

void IVStrideUse::deleted() { … }