llvm/llvm/lib/Analysis/LoopNestAnalysis.cpp

//===- LoopNestAnalysis.cpp - Loop Nest Analysis --------------------------==//
//
// 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
//
//===----------------------------------------------------------------------===//
///
/// \file
/// The implementation for the loop nest analysis.
///
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LoopNestAnalysis.h"
#include "llvm/ADT/BreadthFirstIterator.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/Analysis/ValueTracking.h"

usingnamespacellvm;

#define DEBUG_TYPE …
#ifndef NDEBUG
static const char *VerboseDebug = DEBUG_TYPE "-verbose";
#endif

/// Determine whether the loops structure violates basic requirements for
/// perfect nesting:
///  - the inner loop should be the outer loop's only child
///  - the outer loop header should 'flow' into the inner loop preheader
///    or jump around the inner loop to the outer loop latch
///  - if the inner loop latch exits the inner loop, it should 'flow' into
///    the outer loop latch.
/// Returns true if the loop structure satisfies the basic requirements and
/// false otherwise.
static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
                                ScalarEvolution &SE);

//===----------------------------------------------------------------------===//
// LoopNest implementation
//

LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)
    : … { … }

std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
                                                ScalarEvolution &SE) { … }

static CmpInst *getOuterLoopLatchCmp(const Loop &OuterLoop) { … }

static CmpInst *getInnerLoopGuardCmp(const Loop &InnerLoop) { … }

static bool checkSafeInstruction(const Instruction &I,
                                 const CmpInst *InnerLoopGuardCmp,
                                 const CmpInst *OuterLoopLatchCmp,
                                 std::optional<Loop::LoopBounds> OuterLoopLB) { … }

bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
                                  ScalarEvolution &SE) { … }

LoopNest::LoopNestEnum LoopNest::analyzeLoopNestForPerfectNest(
    const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) { … }

LoopNest::InstrVectorTy LoopNest::getInterveningInstructions(
    const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) { … }

SmallVector<LoopVectorTy, 4>
LoopNest::getPerfectLoops(ScalarEvolution &SE) const { … }

unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) { … }

const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From,
                                                const BasicBlock *End,
                                                bool CheckUniquePred) { … }

static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
                                ScalarEvolution &SE) { … }

AnalysisKey LoopNestAnalysis::Key;

raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) { … }

//===----------------------------------------------------------------------===//
// LoopNestPrinterPass implementation
//

PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
                                           LoopStandardAnalysisResults &AR,
                                           LPMUpdater &U) { … }