File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/lib/Analysis

usr / src / contrib / llvm-project / llvm / lib / Analysis /

📁 ..
📄 AliasAnalysis.cpp(33.55 KB)
📄 AliasAnalysisEvaluator.cpp(15.64 KB)
📄 AliasAnalysisSummary.cpp(3.49 KB)
📄 AliasAnalysisSummary.h(10.17 KB)
📄 AliasSetTracker.cpp(25.86 KB)
📄 Analysis.cpp(5.29 KB)
📄 AssumeBundleQueries.cpp(7.96 KB)
📄 AssumptionCache.cpp(10.94 KB)
📄 BasicAliasAnalysis.cpp(85.81 KB)
📄 BlockFrequencyInfo.cpp(12.39 KB)
📄 BlockFrequencyInfoImpl.cpp(28.6 KB)
📄 BranchProbabilityInfo.cpp(43.48 KB)
📄 CFG.cpp(9.9 KB)
📄 CFGPrinter.cpp(11.2 KB)
📄 CFLAndersAliasAnalysis.cpp(33.01 KB)
📄 CFLGraph.h(21.23 KB)
📄 CFLSteensAliasAnalysis.cpp(13.24 KB)
📄 CGSCCPassManager.cpp(31.2 KB)
📄 CallGraph.cpp(12.86 KB)
📄 CallGraphSCCPass.cpp(26.31 KB)
📄 CallPrinter.cpp(9.48 KB)
📄 CaptureTracking.cpp(15.38 KB)
📄 CmpInstAnalysis.cpp(4.63 KB)
📄 CodeMetrics.cpp(6.99 KB)
📄 ConstantFolding.cpp(105.15 KB)
📄 CostModel.cpp(3.87 KB)
📄 DDG.cpp(11.29 KB)
📄 Delinearization.cpp(4.49 KB)
📄 DemandedBits.cpp(16.27 KB)
📄 DependenceAnalysis.cpp(150.78 KB)
📄 DependenceGraphBuilder.cpp(19.24 KB)
📄 DivergenceAnalysis.cpp(15.59 KB)
📄 DomPrinter.cpp(9.67 KB)
📄 DomTreeUpdater.cpp(15.21 KB)
📄 DominanceFrontier.cpp(3.2 KB)
📄 EHPersonalities.cpp(5.89 KB)
📄 GlobalsModRef.cpp(41 KB)
📄 GuardUtils.cpp(3.27 KB)
📄 HeatUtils.cpp(2.85 KB)
📄 IVDescriptors.cpp(42.28 KB)
📄 IVUsers.cpp(16.12 KB)
📄 IndirectCallPromotionAnalysis.cpp(4.33 KB)
📄 InlineAdvisor.cpp(15.28 KB)
📄 InlineCost.cpp(99.47 KB)
📄 InlineFeaturesAnalysis.cpp(1.59 KB)
📄 InlineSizeEstimatorAnalysis.cpp(10.95 KB)
📄 InstCount.cpp(2.45 KB)
📄 InstructionPrecedenceTracking.cpp(4.8 KB)
📄 InstructionSimplify.cpp(216.91 KB)
📄 Interval.cpp(1.78 KB)
📄 IntervalPartition.cpp(4.5 KB)
📄 LazyBlockFrequencyInfo.cpp(2.81 KB)
📄 LazyBranchProbabilityInfo.cpp(2.96 KB)
📄 LazyCallGraph.cpp(67.33 KB)
📄 LazyValueInfo.cpp(76.38 KB)
📄 LegacyDivergenceAnalysis.cpp(14.82 KB)
📄 Lint.cpp(29.07 KB)
📄 Loads.cpp(20.6 KB)
📄 LoopAccessAnalysis.cpp(88.02 KB)
📄 LoopAnalysisManager.cpp(6.6 KB)
📄 LoopCacheAnalysis.cpp(23.53 KB)
📄 LoopInfo.cpp(37.15 KB)
📄 LoopNestAnalysis.cpp(10.62 KB)
📄 LoopPass.cpp(12.89 KB)
📄 LoopUnrollAnalyzer.cpp(7.26 KB)
📄 MLInlineAdvisor.cpp(11.36 KB)
📄 MemDepPrinter.cpp(5.13 KB)
📄 MemDerefPrinter.cpp(2.53 KB)
📄 MemoryBuiltins.cpp(41.14 KB)
📄 MemoryDependenceAnalysis.cpp(69.89 KB)
📄 MemoryLocation.cpp(7.92 KB)
📄 MemorySSA.cpp(90.16 KB)
📄 MemorySSAUpdater.cpp(57.9 KB)
📄 ModuleDebugInfoPrinter.cpp(4.02 KB)
📄 ModuleSummaryAnalysis.cpp(38.13 KB)
📄 MustExecute.cpp(31.18 KB)
📄 ObjCARCAliasAnalysis.cpp(5.81 KB)
📄 ObjCARCAnalysisUtils.cpp(1.07 KB)
📄 ObjCARCInstKind.cpp(23.15 KB)
📄 OptimizationRemarkEmitter.cpp(4.23 KB)
📄 PHITransAddr.cpp(16.05 KB)
📄 PhiValues.cpp(8.4 KB)
📄 PostDominators.cpp(3.59 KB)
📄 ProfileSummaryInfo.cpp(18.07 KB)
📄 PtrUseVisitor.cpp(1.28 KB)
📄 RegionInfo.cpp(6.5 KB)
📄 RegionPass.cpp(9.23 KB)
📄 RegionPrinter.cpp(8.61 KB)
📄 ReleaseModeModelRunner.cpp(2.83 KB)
📄 ScalarEvolution.cpp(475.26 KB)
📄 ScalarEvolutionAliasAnalysis.cpp(5.96 KB)
📄 ScalarEvolutionDivision.cpp(7.51 KB)
📄 ScalarEvolutionNormalization.cpp(4.59 KB)
📄 ScopedNoAliasAA.cpp(7.38 KB)
📄 StackLifetime.cpp(12.22 KB)
📄 StackSafetyAnalysis.cpp(31.81 KB)
📄 StratifiedSets.h(18.67 KB)
📄 SyncDependenceAnalysis.cpp(12.97 KB)
📄 SyntheticCountsUtils.cpp(3.81 KB)
📄 TFUtils.cpp(8.99 KB)
📄 TargetLibraryInfo.cpp(58.98 KB)
📄 TargetTransformInfo.cpp(48.15 KB)
📄 Trace.cpp(1.8 KB)
📄 TypeBasedAliasAnalysis.cpp(26.04 KB)
📄 TypeMetadataUtils.cpp(5.93 KB)
📄 VFABIDemangling.cpp(16.46 KB)
📄 ValueLattice.cpp(1.19 KB)
📄 ValueLatticeUtils.cpp(1.53 KB)
📄 ValueTracking.cpp(243.08 KB)
📄 VectorUtils.cpp(48.57 KB)
📁 models

Editing: 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/Statistic.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ValueTracking.h"

using namespace llvm;

#define DEBUG_TYPE "loopnest"
#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)
    : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
  for (Loop *L : breadth_first(&Root))
    Loops.push_back(L);
}

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

bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
                                  ScalarEvolution &SE) {
  assert(!OuterLoop.getSubLoops().empty() && "Outer loop should have subloops");
  assert(InnerLoop.getParentLoop() && "Inner loop should have a parent");
  LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()
                    << "' and '" << InnerLoop.getName()
                    << "' are perfectly nested.\n");

// Determine whether the loops structure satisfies the following requirements:
  //  - 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.
  if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {
    LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");
    return false;
  }

// Bail out if we cannot retrieve the outer loop bounds.
  auto OuterLoopLB = OuterLoop.getBounds(SE);
  if (OuterLoopLB == None) {
    LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
                      << OuterLoop << "\n";);
    return false;
  }

// Identify the outer loop latch comparison instruction.
  const BasicBlock *Latch = OuterLoop.getLoopLatch();
  assert(Latch && "Expecting a valid loop latch");
  const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
  assert(BI && BI->isConditional() &&
         "Expecting loop latch terminator to be a branch instruction");

const CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
  DEBUG_WITH_TYPE(
      VerboseDebug, if (OuterLoopLatchCmp) {
        dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
               << "\n";
      });

// Identify the inner loop guard instruction.
  BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch();
  const CmpInst *InnerLoopGuardCmp =
      (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr;

DEBUG_WITH_TYPE(
      VerboseDebug, if (InnerLoopGuardCmp) {
        dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp
               << "\n";
      });

// Determine whether instructions in a basic block are one of:
  //  - the inner loop guard comparison
  //  - the outer loop latch comparison
  //  - the outer loop induction variable increment
  //  - a phi node, a cast or a branch
  auto containsOnlySafeInstructions = [&](const BasicBlock &BB) {
    return llvm::all_of(BB, [&](const Instruction &I) {
      bool isAllowed = isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) ||
                       isa<BranchInst>(I);
      if (!isAllowed) {
        DEBUG_WITH_TYPE(VerboseDebug, {
          dbgs() << "Instruction: " << I << "\nin basic block: " << BB
                 << " is considered unsafe.\n";
        });
        return false;
      }

// The only binary instruction allowed is the outer loop step instruction,
      // the only comparison instructions allowed are the inner loop guard
      // compare instruction and the outer loop latch compare instruction.
      if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||
          (isa<CmpInst>(I) && &I != OuterLoopLatchCmp &&
           &I != InnerLoopGuardCmp)) {
        DEBUG_WITH_TYPE(VerboseDebug, {
          dbgs() << "Instruction: " << I << "\nin basic block:" << BB
                 << "is unsafe.\n";
        });
        return false;
      }
      return true;
    });
  };

// Check the code surrounding the inner loop for instructions that are deemed
  // unsafe.
  const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
  const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
  const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();

if (!containsOnlySafeInstructions(*OuterLoopHeader) ||
      !containsOnlySafeInstructions(*OuterLoopLatch) ||
      (InnerLoopPreHeader != OuterLoopHeader &&
       !containsOnlySafeInstructions(*InnerLoopPreHeader)) ||
      !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) {
    LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "
                         "unsafe\n";);
    return false;
  }

LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"
                    << InnerLoop.getName() << "' are perfectly nested.\n");

return true;
}

SmallVector<LoopVectorTy, 4>
LoopNest::getPerfectLoops(ScalarEvolution &SE) const {
  SmallVector<LoopVectorTy, 4> LV;
  LoopVectorTy PerfectNest;

for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) {
    if (PerfectNest.empty())
      PerfectNest.push_back(L);

auto &SubLoops = L->getSubLoops();
    if (SubLoops.size() == 1 && arePerfectlyNested(*L, *SubLoops.front(), SE)) {
      PerfectNest.push_back(SubLoops.front());
    } else {
      LV.push_back(PerfectNest);
      PerfectNest.clear();
    }
  }

return LV;
}

unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) {
  LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '"
                    << Root.getName() << "'\n");

const Loop *CurrentLoop = &Root;
  const auto *SubLoops = &CurrentLoop->getSubLoops();
  unsigned CurrentDepth = 1;

while (SubLoops->size() == 1) {
    const Loop *InnerLoop = SubLoops->front();
    if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) {
      LLVM_DEBUG({
        dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName()
               << "' is not perfectly nested with loop '"
               << InnerLoop->getName() << "'\n";
      });
      break;
    }

CurrentLoop = InnerLoop;
    SubLoops = &CurrentLoop->getSubLoops();
    ++CurrentDepth;
  }

return CurrentDepth;
}

static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
                                ScalarEvolution &SE) {
  // The inner loop must be the only outer loop's child.
  if ((OuterLoop.getSubLoops().size() != 1) ||
      (InnerLoop.getParentLoop() != &OuterLoop))
    return false;

// We expect loops in normal form which have a preheader, header, latch...
  if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())
    return false;

const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
  const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
  const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
  const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch();
  const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock();

// We expect rotated loops. The inner loop should have a single exit block.
  if (OuterLoop.getExitingBlock() != OuterLoopLatch ||
      InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)
    return false;

// Ensure the only branch that may exist between the loops is the inner loop
  // guard.
  if (OuterLoopHeader != InnerLoopPreHeader) {
    const BranchInst *BI =
        dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());

if (!BI || BI != InnerLoop.getLoopGuardBranch())
      return false;

// The successors of the inner loop guard should be the inner loop
    // preheader and the outer loop latch.
    for (const BasicBlock *Succ : BI->successors()) {
      if (Succ == InnerLoopPreHeader)
        continue;
      if (Succ == OuterLoopLatch)
        continue;

DEBUG_WITH_TYPE(VerboseDebug, {
        dbgs() << "Inner loop guard successor " << Succ->getName()
               << " doesn't lead to inner loop preheader or "
                  "outer loop latch.\n";
      });
      return false;
    }
  }

// Ensure the inner loop exit block leads to the outer loop latch.
  if (InnerLoopExit->getSingleSuccessor() != OuterLoopLatch) {
    DEBUG_WITH_TYPE(
        VerboseDebug,
        dbgs() << "Inner loop exit block " << *InnerLoopExit
               << " does not directly lead to the outer loop latch.\n";);
    return false;
  }

return true;
}

raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) {
  OS << "IsPerfect=";
  if (LN.getMaxPerfectDepth() == LN.getNestDepth())
    OS << "true";
  else
    OS << "false";
  OS << ", Depth=" << LN.getNestDepth();
  OS << ", OutermostLoop: " << LN.getOutermostLoop().getName();
  OS << ", Loops: ( ";
  for (const Loop *L : LN.getLoops())
    OS << L->getName() << " ";
  OS << ")";

return OS;
}

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

PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
                                           LoopStandardAnalysisResults &AR,
                                           LPMUpdater &U) {
  if (auto LN = LoopNest::getLoopNest(L, AR.SE))
    OS << *LN << "\n";

return PreservedAnalyses::all();
}

003 File Manager

Editing: LoopNestAnalysis.cpp

Upload File

Create Folder