LoopFuse.cpp | Explore in Territory

//===- LoopFuse.cpp - Loop Fusion Pass ------------------------------------===//
//
// 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
/// This file implements the loop fusion pass.
/// The implementation is largely based on the following document:
///
///       Code Transformations to Augment the Scope of Loop Fusion in a
///         Production Compiler
///       Christopher Mark Barton
///       MSc Thesis
///       https://webdocs.cs.ualberta.ca/~amaral/thesis/ChristopherBartonMSc.pdf
///
/// The general approach taken is to collect sets of control flow equivalent
/// loops and test whether they can be fused. The necessary conditions for
/// fusion are:
///    1. The loops must be adjacent (there cannot be any statements between
///       the two loops).
///    2. The loops must be conforming (they must execute the same number of
///       iterations).
///    3. The loops must be control flow equivalent (if one loop executes, the
///       other is guaranteed to execute).
///    4. There cannot be any negative distance dependencies between the loops.
/// If all of these conditions are satisfied, it is safe to fuse the loops.
///
/// This implementation creates FusionCandidates that represent the loop and the
/// necessary information needed by fusion. It then operates on the fusion
/// candidates, first confirming that the candidate is eligible for fusion. The
/// candidates are then collected into control flow equivalent sets, sorted in
/// dominance order. Each set of control flow equivalent candidates is then
/// traversed, attempting to fuse pairs of candidates in the set. If all
/// requirements for fusion are met, the two candidates are fused, creating a
/// new (fused) candidate which is then added back into the set to consider for
/// additional fusion.
///
/// This implementation currently does not make any modifications to remove
/// conditions for fusion. Code transformations to make loops conform to each of
/// the conditions for fusion are discussed in more detail in the document
/// above. These can be added to the current implementation in the future.
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/LoopFuse.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/CodeMoverUtils.h"
#include "llvm/Transforms/Utils/LoopPeel.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(FuseCounter, "Loops fused");
STATISTIC(NumFusionCandidates, "Number of candidates for loop fusion");
STATISTIC(InvalidPreheader, "Loop has invalid preheader");
STATISTIC(InvalidHeader, "Loop has invalid header");
STATISTIC(InvalidExitingBlock, "Loop has invalid exiting blocks");
STATISTIC(InvalidExitBlock, "Loop has invalid exit block");
STATISTIC(InvalidLatch, "Loop has invalid latch");
STATISTIC(InvalidLoop, "Loop is invalid");
STATISTIC(AddressTakenBB, "Basic block has address taken");
STATISTIC(MayThrowException, "Loop may throw an exception");
STATISTIC(ContainsVolatileAccess, "Loop contains a volatile access");
STATISTIC(NotSimplifiedForm, "Loop is not in simplified form");
STATISTIC(InvalidDependencies, "Dependencies prevent fusion");
STATISTIC(UnknownTripCount, "Loop has unknown trip count");
STATISTIC(UncomputableTripCount, "SCEV cannot compute trip count of loop");
STATISTIC(NonEqualTripCount, "Loop trip counts are not the same");
STATISTIC(NonAdjacent, "Loops are not adjacent");
STATISTIC(
    NonEmptyPreheader,
    "Loop has a non-empty preheader with instructions that cannot be moved");
STATISTIC(FusionNotBeneficial, "Fusion is not beneficial");
STATISTIC(NonIdenticalGuards, "Candidates have different guards");
STATISTIC(NonEmptyExitBlock, "Candidate has a non-empty exit block with "
                             "instructions that cannot be moved");
STATISTIC(NonEmptyGuardBlock, "Candidate has a non-empty guard block with "
                              "instructions that cannot be moved");
STATISTIC(NotRotated, "Candidate is not rotated");
STATISTIC(OnlySecondCandidateIsGuarded,
          "The second candidate is guarded while the first one is not");
STATISTIC(NumHoistedInsts, "Number of hoisted preheader instructions.");
STATISTIC(NumSunkInsts, "Number of hoisted preheader instructions.");

enum FusionDependenceAnalysisChoice { … };

static cl::opt<FusionDependenceAnalysisChoice> FusionDependenceAnalysis(
    "loop-fusion-dependence-analysis",
    cl::desc("Which dependence analysis should loop fusion use?"),
    cl::values(clEnumValN(FUSION_DEPENDENCE_ANALYSIS_SCEV, "scev",
                          "Use the scalar evolution interface"),
               clEnumValN(FUSION_DEPENDENCE_ANALYSIS_DA, "da",
                          "Use the dependence analysis interface"),
               clEnumValN(FUSION_DEPENDENCE_ANALYSIS_ALL, "all",
                          "Use all available analyses")),
    cl::Hidden, cl::init(FUSION_DEPENDENCE_ANALYSIS_ALL));

static cl::opt<unsigned> FusionPeelMaxCount(
    "loop-fusion-peel-max-count", cl::init(0), cl::Hidden,
    cl::desc("Max number of iterations to be peeled from a loop, such that "
             "fusion can take place"));

#ifndef NDEBUG
static cl::opt<bool>
    VerboseFusionDebugging("loop-fusion-verbose-debug",
                           cl::desc("Enable verbose debugging for Loop Fusion"),
                           cl::Hidden, cl::init(false));
#endif

namespace {
/// This class is used to represent a candidate for loop fusion. When it is
/// constructed, it checks the conditions for loop fusion to ensure that it
/// represents a valid candidate. It caches several parts of a loop that are
/// used throughout loop fusion (e.g., loop preheader, loop header, etc) instead
/// of continually querying the underlying Loop to retrieve these values. It is
/// assumed these will not change throughout loop fusion.
///
/// The invalidate method should be used to indicate that the FusionCandidate is
/// no longer a valid candidate for fusion. Similarly, the isValid() method can
/// be used to ensure that the FusionCandidate is still valid for fusion.
struct FusionCandidate { … };

struct FusionCandidateCompare { … };

LoopVector;

// Set of Control Flow Equivalent (CFE) Fusion Candidates, sorted in dominance
// order. Thus, if FC0 comes *before* FC1 in a FusionCandidateSet, then FC0
// dominates FC1 and FC1 post-dominates FC0.
// std::set was chosen because we want a sorted data structure with stable
// iterators. A subsequent patch to loop fusion will enable fusing non-adjacent
// loops by moving intervening code around. When this intervening code contains
// loops, those loops will be moved also. The corresponding FusionCandidates
// will also need to be moved accordingly. As this is done, having stable
// iterators will simplify the logic. Similarly, having an efficient insert that
// keeps the FusionCandidateSet sorted will also simplify the implementation.
FusionCandidateSet;
FusionCandidateCollection;

#if !defined(NDEBUG)
static llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                                     const FusionCandidate &FC) {
  if (FC.isValid())
    OS << FC.Preheader->getName();
  else
    OS << "<Invalid>";

  return OS;
}

static llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                                     const FusionCandidateSet &CandSet) {
  for (const FusionCandidate &FC : CandSet)
    OS << FC << '\n';

  return OS;
}

static void
printFusionCandidates(const FusionCandidateCollection &FusionCandidates) {
  dbgs() << "Fusion Candidates: \n";
  for (const auto &CandidateSet : FusionCandidates) {
    dbgs() << "*** Fusion Candidate Set ***\n";
    dbgs() << CandidateSet;
    dbgs() << "****************************\n";
  }
}
#endif

/// Collect all loops in function at the same nest level, starting at the
/// outermost level.
///
/// This data structure collects all loops at the same nest level for a
/// given function (specified by the LoopInfo object). It starts at the
/// outermost level.
struct LoopDepthTree { … };

#ifndef NDEBUG
static void printLoopVector(const LoopVector &LV) {
  dbgs() << "****************************\n";
  for (auto *L : LV)
    printLoop(*L, dbgs());
  dbgs() << "****************************\n";
}
#endif

struct LoopFuser { … };
} // namespace

PreservedAnalyses LoopFusePass::run(Function &F, FunctionAnalysisManager &AM) { … }
llvm/llvm/lib/Transforms/Scalar/LoopFuse.cpp
