Google Git Google Git
Sign in
llvm/llvm-project/refs/heads/users/void/array-bounds-accessed/./llvm/lib/Transforms/Scalar/LoopInterchange.cpp
blob: 1d384f40607f626d267ffc3b21f048aa01a09f46 [file] [edit]
//===- LoopInterchange.cpp - Loop interchange 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
//
//===----------------------------------------------------------------------===//
//
// This Pass handles loop interchange transform.
// This pass interchanges loops to provide a more cache-friendly memory access
// patterns.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar/LoopInterchange.h"
#include "ScalarOptions.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/LoopCacheAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopNestAnalysis.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
using namespace llvm;
#define DEBUG_TYPE "loop-interchange"
STATISTIC(LoopsInterchanged, "Number of loops interchanged");
namespace {
using LoopVector = SmallVector<Loop *, 8>;
/// A list of direction vectors. Each entry represents a direction vector
/// corresponding to one or more dependencies existing in the loop nest. The
/// length of all direction vectors is equal and is N + 1, where N is the depth
/// of the loop nest. The first N elements correspond to the dependency
/// direction of each N loops. The last one indicates whether this entry is
/// forward dependency ('<') or not ('*'). The term "forward" aligns with what
/// is defined in LoopAccessAnalysis.
// TODO: Check if we can use a sparse matrix here.
using CharMatrix = std::vector<std::vector<char>>;
} // end anonymous namespace
constexpr LoopInterchangeRule DefaultProfitabilities[] = {
LoopInterchangeRule::PerInstrOrderCost,
LoopInterchangeRule::ForVectorization};
#ifndef NDEBUG
static bool noDuplicateRulesAndIgnore(ArrayRef<LoopInterchangeRule> Rules) {
SmallSet<LoopInterchangeRule, 4> Set;
for (LoopInterchangeRule Rule : Rules) {
if (!Set.insert(Rule).second)
return false;
if (Rule == LoopInterchangeRule::Ignore)
return false;
}
return true;
}
static void printDepMatrix(CharMatrix &DepMatrix) {
for (auto &Row : DepMatrix) {
// Drop the last element because it is a flag indicating whether this is
// forward dependency or not, which doesn't affect the legality check.
for (char D : drop_end(Row))
LLVM_DEBUG(dbgs() << D << " ");
LLVM_DEBUG(dbgs() << "\n");
}
}
/// Return true if \p Src appears before \p Dst in the same basic block.
/// Precondition: \p Src and \Dst are distinct instructions within the same
/// basic block.
static bool inThisOrder(const Instruction *Src, const Instruction *Dst) {
assert(Src->getParent() == Dst->getParent() && Src != Dst &&
"Expected Src and Dst to be different instructions in the same BB");
bool FoundSrc = false;
for (const Instruction &I : *(Src->getParent())) {
if (&I == Src) {
FoundSrc = true;
continue;
}
if (&I == Dst)
return FoundSrc;
}
llvm_unreachable("Dst not found");
}
#endif
static bool populateDependencyMatrix(const ScalarOptions &Opts,
CharMatrix &DepMatrix, unsigned Level,
Loop *L, DependenceInfo *DI,
ScalarEvolution *SE,
OptimizationRemarkEmitter *ORE) {
using ValueVector = SmallVector<Value *, 16>;
ValueVector MemInstr;
unsigned NumInsts = 0;
// For each block.
for (BasicBlock *BB : L->blocks()) {
// Scan the BB and collect legal loads and stores.
for (Instruction &I : *BB) {
NumInsts++;
if (auto *Ld = dyn_cast<LoadInst>(&I)) {
if (!Ld->isSimple())
return false;
MemInstr.push_back(&I);
} else if (auto *St = dyn_cast<StoreInst>(&I)) {
if (!St->isSimple())
return false;
MemInstr.push_back(&I);
}
}
}
// To populate the dependence matrix, we perform dependence test for each pair
// of memory instructions, which has O(NumMemInstr^2) complexity. This implies
// that even if the number of memory instructions is small, the analysis can
// still be expensive if the most of the instructions in the loop are memory
// instructions. On the other hand, if the number of memory instructions is
// not small, but the loop is large (i.e., it contains many non-memory
// instructions), the analysis can still be affordable.
unsigned NumMemInstr = MemInstr.size();
LLVM_DEBUG(dbgs() << "Found " << NumMemInstr
<< " Loads and Stores to analyze\n");
if (static_cast<uint64_t>(Opts.loop_interchange_max_mem_instr_ratio) *
NumInsts <
static_cast<uint64_t>(NumMemInstr) * NumMemInstr) {
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLoop",
L->getStartLoc(), L->getHeader())
<< "Number of loads/stores exceeded, the supported maximum can be "
"increased with option -loop-interchange-max-mem-instr-ratio.";
});
return false;
}
ValueVector::iterator I, IE, J, JE;
// Manage direction vectors that are already seen. Map each direction vector
// to an index of DepMatrix at which it is stored.
StringMap<unsigned> Seen;
for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
for (J = I, JE = MemInstr.end(); J != JE; ++J) {
std::vector<char> Dep;
Instruction *Src = cast<Instruction>(*I);
Instruction *Dst = cast<Instruction>(*J);
// Ignore Input dependencies.
if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
continue;
// Track Output, Flow, and Anti dependencies.
if (auto D = DI->depends(Src, Dst)) {
assert(D->isOrdered() && "Expected an output, flow or anti dep.");
// If the direction vector is negative, normalize it to
// make it non-negative.
if (D->normalize(SE))
LLVM_DEBUG(dbgs() << "Negative dependence vector normalized.\n");
LLVM_DEBUG(StringRef DepType =
D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
dbgs() << "Found " << DepType
<< " dependency between Src and Dst\n"
<< " Src:" << *Src << "\n Dst:" << *Dst << '\n');
unsigned Levels = D->getLevels();
char Direction;
for (unsigned II = 1; II <= Levels; ++II) {
// `DVEntry::LE` is converted to `*`. This is because `LE` means `<`
// or `=`, for which we don't have an equivalent representation, so
// that the conservative approximation is necessary. The same goes for
// `DVEntry::GE`.
// TODO: Use of fine-grained expressions allows for more accurate
// analysis.
unsigned Dir = D->getDirection(II);
if (Dir == Dependence::DVEntry::LT)
Direction = '<';
else if (Dir == Dependence::DVEntry::GT)
Direction = '>';
else if (Dir == Dependence::DVEntry::EQ)
Direction = '=';
else
Direction = '*';
Dep.push_back(Direction);
}
// If the Dependence object doesn't have any information, fill the
// dependency vector with '*'.
if (D->isConfused()) {
assert(Dep.empty() && "Expected empty dependency vector");
Dep.assign(L->getLoopDepth() + Level - 1, '*');
}
while (Dep.size() < L->getLoopDepth() + Level - 1) {
Dep.push_back('I');
}
// Dependence analysis reports levels for the full enclosing loop nest.
// Keep only the suffix that corresponds to the selected perfect
// subnest.
if (Dep.size() > Level)
Dep.erase(Dep.begin(), Dep.end() - Level);
// If all the elements of any direction vector have only '*', legality
// can't be proven. Exit early to save compile time.
if (all_of(Dep, equal_to('*'))) {
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
L->getStartLoc(), L->getHeader())
<< "All loops have dependencies in all directions.";
});
return false;
}
// Test whether the dependency is forward or not.
bool IsKnownForward = true;
if (Src->getParent() != Dst->getParent()) {
// In general, when Src and Dst are in different BBs, the execution
// order of them within a single iteration is not guaranteed. Treat
// conservatively as not-forward dependency in this case.
IsKnownForward = false;
} else {
// Src and Dst are in the same BB. If they are the different
// instructions, Src should appear before Dst in the BB as they are
// stored to MemInstr in that order.
assert((Src == Dst || inThisOrder(Src, Dst)) &&
"Unexpected instructions");
// If the Dependence object is reversed (due to normalization), it
// represents the dependency from Dst to Src, meaning it is a backward
// dependency. Otherwise it should be a forward dependency.
bool IsReversed = D->getSrc() != Src;
if (IsReversed)
IsKnownForward = false;
}
// Initialize the last element. Assume forward dependencies only; it
// will be updated later if there is any non-forward dependency.
Dep.push_back('<');
// The last element should express the "summary" among one or more
// direction vectors whose first N elements are the same (where N is
// the depth of the loop nest). Hence we exclude the last element from
// the Seen map.
auto [Ite, Inserted] = Seen.try_emplace(
StringRef(Dep.data(), Dep.size() - 1), DepMatrix.size());
// Make sure we only add unique entries to the dependency matrix.
if (Inserted)
DepMatrix.push_back(Dep);
// If we cannot prove that this dependency is forward, change the last
// element of the corresponding entry. Since a `[... *]` dependency
// includes a `[... <]` dependency, we do not need to keep both and
// change the existing entry instead.
if (!IsKnownForward)
DepMatrix[Ite->second].back() = '*';
}
}
}
return true;
}
// A loop is moved from index 'from' to an index 'to'. Update the Dependence
// matrix by exchanging the two columns.
static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
unsigned ToIndx) {
for (auto &Row : DepMatrix)
std::swap(Row[ToIndx], Row[FromIndx]);
}
// Check if a direction vector is lexicographically positive. Return true if it
// is positive, nullopt if it is "zero", otherwise false.
// [Theorem] A permutation of the loops in a perfect nest is legal if and only
// if the direction matrix, after the same permutation is applied to its
// columns, has no ">" direction as the leftmost non-"=" direction in any row.
static std::optional<bool>
isLexicographicallyPositive(ArrayRef<char> DV, unsigned Begin, unsigned End) {
for (unsigned char Direction : DV.slice(Begin, End - Begin)) {
if (Direction == '<')
return true;
if (Direction == '>' || Direction == '*')
return false;
}
return std::nullopt;
}
// Checks if it is legal to interchange 2 loops.
static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
unsigned InnerLoopId,
unsigned OuterLoopId) {
unsigned NumRows = DepMatrix.size();
std::vector<char> Cur;
// For each row check if it is valid to interchange.
for (unsigned Row = 0; Row < NumRows; ++Row) {
// Create temporary DepVector check its lexicographical order
// before and after swapping OuterLoop vs InnerLoop
Cur = DepMatrix[Row];
// If the surrounding loops already ensure that the direction vector is
// lexicographically positive, nothing within the loop will be able to break
// the dependence. In such a case we can skip the subsequent check.
if (isLexicographicallyPositive(Cur, 0, OuterLoopId) == true)
continue;
// Check if the direction vector is lexicographically positive (or zero)
// for both before/after exchanged. Ignore the last element because it
// doesn't affect the legality.
if (isLexicographicallyPositive(Cur, OuterLoopId, Cur.size() - 1) == false)
return false;
std::swap(Cur[InnerLoopId], Cur[OuterLoopId]);
if (isLexicographicallyPositive(Cur, OuterLoopId, Cur.size() - 1) == false)
return false;
}
return true;
}
static void populateWorklist(Loop &L, LoopVector &LoopList) {
LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
<< L.getHeader()->getParent()->getName() << " Loop: %"
<< L.getHeader()->getName() << '\n');
assert(LoopList.empty() && "LoopList should initially be empty!");
Loop *CurrentLoop = &L;
const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
while (!Vec->empty()) {
// The current loop has multiple subloops in it hence it is not tightly
// nested.
// Discard all loops above it added into Worklist.
if (Vec->size() != 1) {
LoopList = {};
return;
}
LoopList.push_back(CurrentLoop);
CurrentLoop = Vec->front();
Vec = &CurrentLoop->getSubLoops();
}
LoopList.push_back(CurrentLoop);
}
static bool hasSupportedLoopDepth(const ScalarOptions &Opts,
ArrayRef<Loop *> LoopList,
OptimizationRemarkEmitter &ORE) {
unsigned LoopNestDepth = LoopList.size();
if (LoopNestDepth < Opts.loop_interchange_min_loop_nest_depth ||
LoopNestDepth > Opts.loop_interchange_max_loop_nest_depth) {
LLVM_DEBUG(dbgs() << "Unsupported depth of loop nest " << LoopNestDepth
<< ", the supported range is ["
<< Opts.loop_interchange_min_loop_nest_depth << ", "
<< Opts.loop_interchange_max_loop_nest_depth << "].\n");
Loop *OuterLoop = LoopList.front();
ORE.emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLoopNestDepth",
OuterLoop->getStartLoc(),
OuterLoop->getHeader())
<< "Unsupported depth of loop nest, the supported range is ["
<< std::to_string(Opts.loop_interchange_min_loop_nest_depth)
<< ", "
<< std::to_string(Opts.loop_interchange_max_loop_nest_depth)
<< "].\n";
});
return false;
}
return true;
}
static bool isComputableLoopNest(ScalarEvolution *SE,
ArrayRef<Loop *> LoopList) {
for (Loop *L : LoopList) {
const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(ExitCountOuter)) {
LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
return false;
}
if (L->getNumBackEdges() != 1) {
LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
return false;
}
if (!L->getExitingBlock()) {
LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
return false;
}
}
return true;
}
namespace {
/// LoopInterchangeLegality checks if it is legal to interchange the loop.
class LoopInterchangeLegality {
public:
LoopInterchangeLegality(const ScalarOptions &Opts, Loop *Outer, Loop *Inner,
ScalarEvolution *SE, OptimizationRemarkEmitter *ORE,
DominatorTree *DT)
: Opts(Opts), OuterLoop(Outer), InnerLoop(Inner), SE(SE), DT(DT),
ORE(ORE) {}
/// Check if the loops can be interchanged.
bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
CharMatrix &DepMatrix);
/// Check if the loop structure is understood. We do not handle triangular
/// loops for now.
bool isLoopStructureUnderstood();
bool currentLimitations();
const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
return OuterInnerReductions;
}
const ArrayRef<PHINode *> getInnerLoopInductions() const {
return InnerLoopInductions;
}
ArrayRef<Instruction *> getHasNoWrapReductions() const {
return HasNoWrapReductions;
}
ArrayRef<Instruction *> getHasNoInfInsts() const { return HasNoInfInsts; }
/// Record reductions in the inner loop. Currently supported reductions:
/// - initialized from a constant.
/// - reduction PHI node has only one user.
/// - located in the innermost loop.
struct InnerReduction {
/// The reduction itself.
PHINode *Reduction;
Value *Init;
Value *Next;
/// The Lcssa PHI.
PHINode *LcssaPhi;
/// Store reduction result into memory object.
StoreInst *LcssaStore;
/// The memory Location.
Value *MemRef;
Type *ElemTy;
};
ArrayRef<InnerReduction> getInnerReductions() const {
return InnerReductions;
}
private:
bool tightlyNested(Loop *Outer, Loop *Inner);
bool containsUnsafeInstructions(BasicBlock *BB, Instruction *Skip);
/// Traverse all PHI nodes in the header of each loop in the loop nest
/// starting from \p OuterLoop, and perform the following checks:
///
/// - Identify induction variables in the child loop of \p OuterLoop.
/// - Check for reductions across the inner loop and \p OuterLoop.
/// - Detect unsupported PHI nodes.
///
/// Return false if any unsupported PHI node is found or if no induction
/// variable is found in the child loop of \p OuterLoop. Otherwise return
/// true.
bool checkInductionsAndReductions(Loop *OuterLoop);
/// Detect and record the reduction of the inner loop. Add them to
/// InnerReductions.
///
/// innerloop:
/// Re = phi<0.0, Next>
/// Next = Re op ...
/// OuterLoopLatch:
/// Lcssa = phi<Next> ; lcssa phi
/// store Lcssa, MemRef ; LcssaStore
///
bool isInnerReduction(Loop *L, PHINode *Phi,
SmallVectorImpl<Instruction *> &HasNoWrapInsts);
const ScalarOptions &Opts;
Loop *OuterLoop;
Loop *InnerLoop;
ScalarEvolution *SE;
DominatorTree *DT;
/// Interface to emit optimization remarks.
OptimizationRemarkEmitter *ORE;
/// Set of reduction PHIs taking part of a reduction across the inner and
/// outer loop.
SmallPtrSet<PHINode *, 4> OuterInnerReductions;
/// Set of inner loop induction PHIs
SmallVector<PHINode *, 8> InnerLoopInductions;
/// Hold instructions that have nuw/nsw flags and involved in reductions,
/// like integer addition/multiplication. Those flags must be dropped when
/// interchanging the loops.
SmallVector<Instruction *, 4> HasNoWrapReductions;
/// Hold instructions that have ninf flags and involved in reductions. Those
/// flags must be dropped when interchanging the loops.
SmallVector<Instruction *, 4> HasNoInfInsts;
/// Vector of reductions in the inner loop.
SmallVector<InnerReduction, 8> InnerReductions;
};
/// Manages information utilized by the profitability check for cache. The main
/// purpose of this class is to delay the computation of CacheCost until it is
/// actually needed.
class CacheCostManager {
Loop *OutermostLoop;
LoopStandardAnalysisResults *AR;
DependenceInfo *DI;
/// CacheCost for \ref OutermostLoop. Once it is computed, it is cached. Note
/// that the result can be nullptr.
std::optional<std::unique_ptr<CacheCost>> CC;
/// Maps each loop to an index representing the optimal position within the
/// loop-nest, as determined by the cache cost analysis.
DenseMap<const Loop *, unsigned> CostMap;
void computeIfUnitinialized();
public:
CacheCostManager(Loop *OutermostLoop, LoopStandardAnalysisResults *AR,
DependenceInfo *DI)
: OutermostLoop(OutermostLoop), AR(AR), DI(DI) {}
CacheCost *getCacheCost();
const DenseMap<const Loop *, unsigned> &getCostMap();
};
/// LoopInterchangeProfitability checks if it is profitable to interchange the
/// loop.
class LoopInterchangeProfitability {
public:
LoopInterchangeProfitability(const ScalarOptions &Opts, Loop *Outer,
Loop *Inner, ScalarEvolution *SE,
OptimizationRemarkEmitter *ORE)
: Opts(Opts), OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
/// Check if the loop interchange is profitable.
bool isProfitable(const Loop *InnerLoop, const Loop *OuterLoop,
unsigned InnerLoopId, unsigned OuterLoopId,
CharMatrix &DepMatrix, CacheCostManager &CCM);
private:
int getInstrOrderCost();
std::optional<bool> isProfitablePerLoopCacheAnalysis(
const DenseMap<const Loop *, unsigned> &CostMap, CacheCost *CC);
std::optional<bool> isProfitablePerInstrOrderCost();
std::optional<bool> isProfitableForVectorization(unsigned InnerLoopId,
unsigned OuterLoopId,
CharMatrix &DepMatrix);
const ScalarOptions &Opts;
Loop *OuterLoop;
Loop *InnerLoop;
/// Scev analysis.
ScalarEvolution *SE;
/// Interface to emit optimization remarks.
OptimizationRemarkEmitter *ORE;
};
/// LoopInterchangeTransform interchanges the loop.
class LoopInterchangeTransform {
public:
LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
LoopInfo *LI, DominatorTree *DT,
const LoopInterchangeLegality &LIL)
: OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), LIL(LIL) {}
/// Interchange OuterLoop and InnerLoop.
void transform(ArrayRef<Instruction *> DropNoWrapInsts,
ArrayRef<Instruction *> DropNoInfInsts);
void reduction2Memory();
void restructureLoops(Loop *NewInner, Loop *NewOuter,
BasicBlock *OrigInnerPreHeader,
BasicBlock *OrigOuterPreHeader);
void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
private:
void adjustLoopBranches();
Loop *OuterLoop;
Loop *InnerLoop;
/// Scev analysis.
ScalarEvolution *SE;
LoopInfo *LI;
DominatorTree *DT;
const LoopInterchangeLegality &LIL;
};
struct LoopInterchange {
const ScalarOptions &Opts;
ScalarEvolution *SE = nullptr;
LoopInfo *LI = nullptr;
DependenceInfo *DI = nullptr;
DominatorTree *DT = nullptr;
LoopStandardAnalysisResults *AR = nullptr;
/// Interface to emit optimization remarks.
OptimizationRemarkEmitter *ORE;
LoopInterchange(const ScalarOptions &Opts, ScalarEvolution *SE, LoopInfo *LI,
DependenceInfo *DI, DominatorTree *DT,
LoopStandardAnalysisResults *AR,
OptimizationRemarkEmitter *ORE)
: Opts(Opts), SE(SE), LI(LI), DI(DI), DT(DT), AR(AR), ORE(ORE) {}
bool run(Loop *L) {
if (L->getParentLoop())
return false;
SmallVector<Loop *, 8> LoopList;
populateWorklist(*L, LoopList);
return processLoopList(LoopList);
}
/// Consider below kernel:
/// for(int i=0; i<n; i++){ // Loop 1
/// for(int j=0; j<m; j++){ // Loop 2
/// for(int r=0; r<m; r++){ // Loop 3
/// // Do something
/// }
/// }
/// for(int k=0; k<p; k++){ // Loop 4
/// for(int l=0; l<p; l++){ // Loop 5
/// // Do something
/// }
/// }
/// }
/// Then collectPerfectNests() will return:
/// - [Loop2, Loop3]
/// - [Loop4, Loop5]
static SmallVector<SmallVector<Loop *, 8>, 4>
collectPerfectNests(LoopNest &LN) {
SmallVector<SmallVector<Loop *, 8>, 4> LoopLists;
for (Loop *L : LN.getLoops()) {
if (!L->isInnermost())
continue;
SmallVector<Loop *, 8> LoopList;
Loop *Current = L;
while (true) {
LoopList.push_back(Current);
Loop *Parent = Current->getParentLoop();
if (!Parent || Parent->getSubLoops().size() != 1)
break;
Current = Parent;
}
std::reverse(LoopList.begin(), LoopList.end());
if (LoopList.size() >= 2)
LoopLists.push_back(std::move(LoopList));
}
return LoopLists;
}
bool run(LoopNest &LN) {
SmallVector<SmallVector<Loop *, 8>, 4> LoopLists = collectPerfectNests(LN);
if (LoopLists.empty()) {
LLVM_DEBUG(dbgs() << "No Valid candidates for loop interchange.\n");
return false;
}
bool Changed = false;
for (SmallVector<Loop *, 8> &LoopList : LoopLists) {
// Ensure minimum depth of the loop nest to do the interchange.
if (!hasSupportedLoopDepth(Opts, LoopList, *ORE))
continue;
// Ensure computable loop nest.
if (!isComputableLoopNest(&AR->SE, LoopList)) {
LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
continue;
}
Changed |= processLoopList(LoopList);
}
return Changed;
}
unsigned selectLoopForInterchange(ArrayRef<Loop *> LoopList) {
// TODO: Add a better heuristic to select the loop to be interchanged based
// on the dependence matrix. Currently we select the innermost loop.
return LoopList.size() - 1;
}
bool processLoopList(SmallVectorImpl<Loop *> &LoopList) {
bool Changed = false;
// Ensure proper loop nest depth.
assert(hasSupportedLoopDepth(Opts, LoopList, *ORE) &&
"Unsupported depth of loop nest.");
unsigned LoopNestDepth = LoopList.size();
LLVM_DEBUG({
dbgs() << "Processing LoopList of size = " << LoopNestDepth
<< " containing the following loops:\n";
for (auto *L : LoopList) {
dbgs() << " - ";
L->print(dbgs());
}
});
CharMatrix DependencyMatrix;
Loop *OuterMostLoop = *(LoopList.begin());
if (!populateDependencyMatrix(Opts, DependencyMatrix, LoopNestDepth,
OuterMostLoop, DI, SE, ORE)) {
LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
return false;
}
LLVM_DEBUG(dbgs() << "Dependency matrix before interchange:\n";
printDepMatrix(DependencyMatrix));
// Get the Outermost loop exit.
BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
if (!LoopNestExit) {
LLVM_DEBUG(dbgs() << "OuterMostLoop '" << OuterMostLoop->getName()
<< "' needs an unique exit block");
return false;
}
unsigned SelecLoopId = selectLoopForInterchange(LoopList);
CacheCostManager CCM(LoopList[0], AR, DI);
// We try to achieve the globally optimal memory access for the loopnest,
// and do interchange based on a bubble-sort fasion. We start from
// the innermost loop, move it outwards to the best possible position
// and repeat this process.
for (unsigned j = SelecLoopId; j > 0; j--) {
bool ChangedPerIter = false;
for (unsigned i = SelecLoopId; i > SelecLoopId - j; i--) {
bool Interchanged =
processLoop(LoopList, i, i - 1, DependencyMatrix, CCM);
ChangedPerIter |= Interchanged;
Changed |= Interchanged;
}
// Early abort if there was no interchange during an entire round of
// moving loops outwards.
if (!ChangedPerIter)
break;
}
return Changed;
}
bool processLoop(SmallVectorImpl<Loop *> &LoopList, unsigned InnerLoopId,
unsigned OuterLoopId,
std::vector<std::vector<char>> &DependencyMatrix,
CacheCostManager &CCM) {
Loop *OuterLoop = LoopList[OuterLoopId];
Loop *InnerLoop = LoopList[InnerLoopId];
LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId
<< " and OuterLoopId = " << OuterLoopId << "\n");
LoopInterchangeLegality LIL(Opts, OuterLoop, InnerLoop, SE, ORE, DT);
if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
LLVM_DEBUG(dbgs() << "Cannot prove legality, not interchanging loops '"
<< OuterLoop->getName() << "' and '"
<< InnerLoop->getName() << "'\n");
return false;
}
LLVM_DEBUG(dbgs() << "Loops '" << OuterLoop->getName() << "' and '"
<< InnerLoop->getName()
<< "' are legal to interchange\n");
LoopInterchangeProfitability LIP(Opts, OuterLoop, InnerLoop, SE, ORE);
if (!LIP.isProfitable(InnerLoop, OuterLoop, InnerLoopId, OuterLoopId,
DependencyMatrix, CCM)) {
LLVM_DEBUG(dbgs() << "Interchanging loops '" << OuterLoop->getName()
<< "' and '" << InnerLoop->getName()
<< "' not profitable.\n");
return false;
}
ORE->emit([&]() {
return OptimizationRemark(DEBUG_TYPE, "Interchanged",
InnerLoop->getStartLoc(),
InnerLoop->getHeader())
<< "Loop interchanged with enclosing loop.";
});
LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LIL);
LIT.transform(LIL.getHasNoWrapReductions(), LIL.getHasNoInfInsts());
LLVM_DEBUG(dbgs() << "Loops interchanged: outer loop '"
<< OuterLoop->getName() << "' and inner loop '"
<< InnerLoop->getName() << "'\n");
LoopsInterchanged++;
llvm::formLCSSARecursively(*OuterLoop, *DT, LI, SE);
// Loops interchanged, update LoopList accordingly.
std::swap(LoopList[OuterLoopId], LoopList[InnerLoopId]);
// Update the DependencyMatrix
interChangeDependencies(DependencyMatrix, InnerLoopId, OuterLoopId);
LLVM_DEBUG(dbgs() << "Dependency matrix after interchange:\n";
printDepMatrix(DependencyMatrix));
return true;
}
};
} // end anonymous namespace
bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB,
Instruction *Skip) {
return any_of(*BB, [Skip](const Instruction &I) {
if (&I == Skip)
return false;
return I.mayHaveSideEffects() || I.mayReadFromMemory();
});
}
static FreezeInst *findFreezeInReNestedBlocks(Loop *OuterLoop,
Loop *InnerLoop) {
// adjustLoopBranches swaps the preheader bodies after changing their loop
// roles, so the original outer-preheader body remains outside the new outer
// loop and retains its execution count.
BasicBlock *Blocks[] = {
OuterLoop->getHeader(),
OuterLoop->getLoopLatch(),
InnerLoop->getLoopPreheader(),
InnerLoop->getExitBlock(),
};
for (BasicBlock *BB : Blocks)
if (BB)
for (Instruction &I : *BB)
if (auto *Freeze = dyn_cast<FreezeInst>(&I))
return Freeze;
return nullptr;
}
static FreezeInst *
findFreezeInInnerLatchCloneSet(Loop *InnerLoop,
ArrayRef<PHINode *> InnerLoopInductions) {
// Mirror the latch-condition and induction-update operand closure cloned by
// MoveInstructions in LoopInterchangeTransform::transform.
SmallSetVector<Instruction *, 8> Worklist;
auto IsDirectInnerLoopBlock = [InnerLoop](BasicBlock *BB) {
return InnerLoop->contains(BB) &&
none_of(InnerLoop->getSubLoops(),
[BB](Loop *SubLoop) { return SubLoop->contains(BB); });
};
auto *LatchBranch =
dyn_cast<CondBrInst>(InnerLoop->getLoopLatch()->getTerminator());
if (LatchBranch)
if (auto *Condition = dyn_cast<Instruction>(LatchBranch->getCondition()))
Worklist.insert(Condition);
for (PHINode *Induction : InnerLoopInductions) {
auto *Incoming = dyn_cast<Instruction>(
Induction->getIncomingValueForBlock(InnerLoop->getLoopLatch()));
if (Incoming && !is_contained(InnerLoopInductions, Incoming))
Worklist.insert(Incoming);
}
for (unsigned I = 0; I < Worklist.size(); ++I) {
Instruction *Current = Worklist[I];
if (auto *Freeze = dyn_cast<FreezeInst>(Current))
return Freeze;
for (Value *Operand : Current->operands()) {
auto *OperandI = dyn_cast<Instruction>(Operand);
if (!OperandI || !IsDirectInnerLoopBlock(OperandI->getParent()) ||
is_contained(InnerLoopInductions, OperandI))
continue;
Worklist.insert(OperandI);
}
}
return nullptr;
}
bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
LLVM_DEBUG(dbgs() << "Checking if loops '" << OuterLoop->getName()
<< "' and '" << InnerLoop->getName()
<< "' are tightly nested\n");
// In a perfectly nested loop the outer header branches only into the inner
// loop. If it can also reach the outer latch, it conditionally guards the
// inner loop (an imperfect nest), so the inner loop runs on only a subset of
// the outer iterations. Interchanging such a nest would run the inner loop on
// every outer iteration, including the guarded-off ones, which is illegal
// when the inner loop relies on the guard to terminate (e.g. an eq/ne exit
// whose trip count is degenerate once the guard is false). Reject by allowing
// the outer header to branch only into the inner loop.
//
// TODO: This is conservative. A guarded nest is still safe to interchange
// when the inner loop has a computable trip count that is empty exactly when
// the guard is false, e.g.:
// for (i = 0; i < N; i++)
// if (M > 0) // loop-invariant guard
// for (j = 0; j < M; j++) // empty when M <= 0
// A[j][i] = ...;
// Interchanging is legal here because the inner loop runs zero times on the
// guarded-off iterations.
for (BasicBlock *Succ : successors(OuterLoopHeader))
if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader())
return false;
LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
// The inner loop reduction pattern requires storing the LCSSA PHI in
// the OuterLoop Latch. Therefore, when reduction2Memory is enabled, skip
// that store during checks.
Instruction *Skip = nullptr;
assert(InnerReductions.size() <= 1 &&
"So far we only support at most one reduction.");
if (InnerReductions.size() == 1)
Skip = InnerReductions[0].LcssaStore;
// We do not have any basic block in between now make sure the outer header
// and outer loop latch doesn't contain any unsafe instructions.
if (containsUnsafeInstructions(OuterLoopHeader, Skip) ||
containsUnsafeInstructions(OuterLoopLatch, Skip))
return false;
// Also make sure the inner loop preheader does not contain any unsafe
// instructions. Note that all instructions in the preheader will be moved to
// the outer loop header when interchanging.
if (InnerLoopPreHeader != OuterLoopHeader &&
containsUnsafeInstructions(InnerLoopPreHeader, Skip))
return false;
BasicBlock *InnerLoopExit = InnerLoop->getExitBlock();
// Ensure the inner loop exit block flows to the outer loop latch possibly
// through empty blocks.
const BasicBlock &SuccInner =
LoopNest::skipEmptyBlockUntil(InnerLoopExit, OuterLoopLatch);
if (&SuccInner != OuterLoopLatch) {
LLVM_DEBUG(dbgs() << "Inner loop exit block " << *InnerLoopExit
<< " does not lead to the outer loop latch.\n";);
return false;
}
// The inner loop exit block does flow to the outer loop latch and not some
// other BBs, now make sure it contains safe instructions, since it will be
// moved into the (new) inner loop after interchange.
if (containsUnsafeInstructions(InnerLoopExit, Skip))
return false;
LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
// We have a perfect loop nest.
return true;
}
bool LoopInterchangeLegality::isLoopStructureUnderstood() {
BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
for (PHINode *InnerInduction : InnerLoopInductions) {
unsigned Num = InnerInduction->getNumOperands();
for (unsigned i = 0; i < Num; ++i) {
Value *Val = InnerInduction->getOperand(i);
if (isa<Constant>(Val))
continue;
Instruction *I = dyn_cast<Instruction>(Val);
if (!I)
return false;
// TODO: Handle triangular loops.
// e.g. for(int i=0;i<N;i++)
// for(int j=i;j<N;j++)
unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
InnerLoopPreheader &&
!OuterLoop->isLoopInvariant(I)) {
return false;
}
}
}
// TODO: Handle triangular loops of another form.
// e.g. for(int i=0;i<N;i++)
// for(int j=0;j<i;j++)
// or,
// for(int i=0;i<N;i++)
// for(int j=0;j*i<N;j++)
BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
CondBrInst *InnerLoopLatchBI =
dyn_cast<CondBrInst>(InnerLoopLatch->getTerminator());
if (!InnerLoopLatchBI)
return false;
CmpInst *InnerLoopCmp = dyn_cast<CmpInst>(InnerLoopLatchBI->getCondition());
if (!InnerLoopCmp)
return false;
Value *Op0 = InnerLoopCmp->getOperand(0);
Value *Op1 = InnerLoopCmp->getOperand(1);
// LHS and RHS of the inner loop exit condition, e.g.,
// in "for(int j=0;j<i;j++)", LHS is j and RHS is i.
Value *Left = nullptr;
Value *Right = nullptr;
// Check if V only involves inner loop induction variable.
// Return true if V is InnerInduction, or a cast from
// InnerInduction, or a binary operator that involves
// InnerInduction and a constant.
std::function<bool(Value *)> IsPathToInnerIndVar;
IsPathToInnerIndVar = [this, &IsPathToInnerIndVar](const Value *V) -> bool {
if (llvm::is_contained(InnerLoopInductions, V))
return true;
if (isa<Constant>(V))
return true;
const Instruction *I = dyn_cast<Instruction>(V);
if (!I)
return false;
if (isa<CastInst>(I))
return IsPathToInnerIndVar(I->getOperand(0));
if (isa<BinaryOperator>(I))
return IsPathToInnerIndVar(I->getOperand(0)) &&
IsPathToInnerIndVar(I->getOperand(1));
return false;
};
// In case of multiple inner loop indvars, it is okay if LHS and RHS
// are both inner indvar related variables.
if (IsPathToInnerIndVar(Op0) && IsPathToInnerIndVar(Op1))
return true;
// Otherwise we check if the cmp instruction compares an inner indvar
// related variable (Left) with a outer loop invariant (Right).
if (IsPathToInnerIndVar(Op0) && !isa<Constant>(Op0)) {
Left = Op0;
Right = Op1;
} else if (IsPathToInnerIndVar(Op1) && !isa<Constant>(Op1)) {
Left = Op1;
Right = Op0;
}
if (Left == nullptr)
return false;
const SCEV *S = SE->getSCEV(Right);
if (!SE->isLoopInvariant(S, OuterLoop))
return false;
return true;
}
// If SV is a LCSSA PHI node with a single incoming value, return the incoming
// value.
static Value *followLCSSA(Value *SV) {
PHINode *PHI = dyn_cast<PHINode>(SV);
if (!PHI)
return SV;
if (PHI->getNumIncomingValues() != 1)
return SV;
return followLCSSA(PHI->getIncomingValue(0));
}
static bool checkReductionKind(Loop *L, PHINode *PHI,
SmallVectorImpl<Instruction *> &HasNoWrapInsts,
SmallVectorImpl<Instruction *> &HasNoInfInsts) {
RecurrenceDescriptor RD;
if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD)) {
// Detect floating point reduction only when it can be reordered.
if (RD.getExactFPMathInst() != nullptr)
return false;
// The extra uses of a reduction phi outside of its reduction chain make
// the order in which the elements are visited observable.
if (RD.hasUsesOutsideReductionChain())
return false;
RecurKind RK = RD.getRecurrenceKind();
switch (RK) {
case RecurKind::Or:
case RecurKind::And:
case RecurKind::Xor:
case RecurKind::SMin:
case RecurKind::SMax:
case RecurKind::UMin:
case RecurKind::UMax:
return true;
// Interchanging the loops that contain AnyOf reduction is not always legal.
// Especially, when the result value of the AnyOf is not loop-invariant with
// respect to the outer loop, interchanging may change the semantics. The
// following is an example of such case:
// int A = {{ 1, 0 }, { 0, 1 }};
// int red = 0;
// for (int i = 0; i < 2; i++)
// for (int j = 0; j < 2; j++)
// red = (A[j][i] == 0) ? i + 1 : red;
//
// TODO: We may be able to support interchanging loops with AnyOf reduction
// by checking the operand of the reduction is loop-invariant with respect
// to the outer loop as well.
case RecurKind::AnyOf:
return false;
// Changing the order of floating-point operations may alter the results. If
// a certain instruction has the ninf flag, it means that reordering can
// produce a poison value, which may lead to undefined behavior. To prevent
// this, we must drop the ninf flags if we decide to apply the
// transformation.
case RecurKind::FAdd:
case RecurKind::FMul:
case RecurKind::FMin:
case RecurKind::FMax:
case RecurKind::FMinimum:
case RecurKind::FMaximum:
case RecurKind::FMinimumNum:
case RecurKind::FMaximumNum:
case RecurKind::FMulAdd:
for (Instruction *I : RD.getReductionOpChain(PHI, L))
if (isa<FPMathOperator>(I) && I->hasNoInfs())
HasNoInfInsts.push_back(I);
return true;
// Change the order of integer addition/multiplication may change the
// semantics. Consider the following case:
//
// int A[2][2] = {{ INT_MAX, INT_MAX }, { INT_MIN, INT_MIN }};
// int sum = 0;
// for (int i = 0; i < 2; i++)
// for (int j = 0; j < 2; j++)
// sum += A[j][i];
//
// If the above loops are exchanged, the addition will cause an
// overflow. To prevent this, we must drop the nuw/nsw flags from the
// addition/multiplication instructions when we actually exchanges the
// loops.
case RecurKind::Add:
case RecurKind::Mul: {
unsigned OpCode = RecurrenceDescriptor::getOpcode(RK);
SmallVector<Instruction *, 4> Ops = RD.getReductionOpChain(PHI, L);
// Bail out when we fail to collect reduction instructions chain.
if (Ops.empty())
return false;
for (Instruction *I : Ops) {
assert(I->getOpcode() == OpCode &&
"Expected the instruction to be the reduction operation");
(void)OpCode;
// If the instruction has nuw/nsw flags, we must drop them when the
// transformation is actually performed.
if (I->hasNoSignedWrap() || I->hasNoUnsignedWrap())
HasNoWrapInsts.push_back(I);
}
return true;
}
default:
return false;
}
} else
return false;
}
// Check V's users to see if it is involved in a reduction in L.
static PHINode *
findInnerReductionPhi(Loop *L, Value *V,
SmallVectorImpl<Instruction *> &HasNoWrapInsts,
SmallVectorImpl<Instruction *> &HasNoInfInsts) {
// Reduction variables cannot be constants.
if (isa<Constant>(V))
return nullptr;
for (Value *User : V->users()) {
if (PHINode *PHI = dyn_cast<PHINode>(User)) {
if (PHI->getNumIncomingValues() == 1)
continue;
if (checkReductionKind(L, PHI, HasNoWrapInsts, HasNoInfInsts))
return PHI;
else
return nullptr;
}
}
return nullptr;
}
bool LoopInterchangeLegality::isInnerReduction(
Loop *L, PHINode *Phi, SmallVectorImpl<Instruction *> &HasNoWrapInsts) {
// Only support reduction2Mem when the loop nest to be interchanged is
// the innermost two loops.
if (!L->isInnermost()) {
LLVM_DEBUG(dbgs() << "Only supported when the loop is the innermost.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
L->getStartLoc(), L->getHeader())
<< "Only supported when the loop is the innermost.";
});
return false;
}
if (Phi->getNumIncomingValues() != 2)
return false;
Value *Init = Phi->getIncomingValueForBlock(L->getLoopPreheader());
Value *Next = Phi->getIncomingValueForBlock(L->getLoopLatch());
// So far only supports constant initial value.
if (!isa<Constant>(Init)) {
LLVM_DEBUG(
dbgs()
<< "Only supported for the reduction with a constant initial value.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
L->getStartLoc(), L->getHeader())
<< "Only supported for the reduction with a constant initial "
"value.";
});
return false;
}
// The reduction result must live in the inner loop.
if (Instruction *I = dyn_cast<Instruction>(Next)) {
BasicBlock *BB = I->getParent();
if (!L->contains(BB))
return false;
}
// The reduction should have only one user.
if (!Phi->hasOneUser())
return false;
// Check the reduction kind.
if (!checkReductionKind(L, Phi, HasNoWrapInsts, HasNoInfInsts))
return false;
// Find lcssa_phi in OuterLoop's Latch
BasicBlock *ExitBlock = L->getExitBlock();
if (!ExitBlock)
return false;
PHINode *Lcssa = NULL;
for (auto *U : Next->users()) {
if (auto *P = dyn_cast<PHINode>(U)) {
if (P == Phi)
continue;
if (Lcssa == NULL && P->getParent() == ExitBlock &&
P->getIncomingValueForBlock(L->getLoopLatch()) == Next)
Lcssa = P;
else
return false;
} else
return false;
}
if (!Lcssa)
return false;
if (!Lcssa->hasOneUser()) {
LLVM_DEBUG(dbgs() << "Only supported when the reduction is used once in "
"the outer loop.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
L->getStartLoc(), L->getHeader())
<< "Only supported when the reduction is used once in the outer "
"loop.";
});
return false;
}
StoreInst *LcssaStore =
dyn_cast<StoreInst>(Lcssa->getUniqueUndroppableUser());
if (!LcssaStore || LcssaStore->getParent() != ExitBlock)
return false;
Value *MemRef = LcssaStore->getOperand(1);
Type *ElemTy = LcssaStore->getOperand(0)->getType();
// LcssaStore stores the reduction result in BB.
// When the reduction is initialized from a constant value, we need to load
// from the memory object into the target basic block of the inner loop. This
// means the memory reference was used prematurely. So we must ensure that the
// memory reference does not dominate the target basic block.
// TODO: Move the memory reference definition into the loop header.
if (!DT->dominates(dyn_cast<Instruction>(MemRef), L->getHeader())) {
LLVM_DEBUG(dbgs() << "Only supported when memory reference dominate "
"the inner loop.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
L->getStartLoc(), L->getHeader())
<< "Only supported when memory reference dominate the inner "
"loop.";
});
return false;
}
// Found a reduction in the inner loop.
InnerReduction SR;
SR.Reduction = Phi;
SR.Init = Init;
SR.Next = Next;
SR.LcssaPhi = Lcssa;
SR.LcssaStore = LcssaStore;
SR.MemRef = MemRef;
SR.ElemTy = ElemTy;
InnerReductions.push_back(SR);
return true;
}
bool LoopInterchangeLegality::checkInductionsAndReductions(Loop *OuterLoop) {
auto ChildLoop = [](Loop *L) {
assert(L->getSubLoops().size() <= 1 &&
"Expect at most one child loop for now.");
return L->getSubLoops().empty() ? nullptr : L->getSubLoops().front();
};
Loop *InnerLoop = ChildLoop(OuterLoop);
for (Loop *CurLoop = OuterLoop; CurLoop; CurLoop = ChildLoop(CurLoop)) {
for (PHINode &PHI : CurLoop->getHeader()->phis()) {
InductionDescriptor ID;
if (InductionDescriptor::isInductionPHI(&PHI, CurLoop, SE, ID)) {
if (CurLoop == InnerLoop) {
const SCEV *Step = ID.getStep();
if (!SE->isLoopInvariant(Step, OuterLoop))
return false;
InnerLoopInductions.push_back(&PHI);
}
continue;
}
if (CurLoop == OuterLoop) {
// PHIs in inner loops need to be part of a reduction in the outer loop,
if (PHI.getNumIncomingValues() != 2) {
LLVM_DEBUG(dbgs() << "Only PHI nodes in the outer loop header with 2 "
"incoming values are supported.\n");
return false;
}
// Check if we have a PHI node in the outer loop that has a reduction
// result from the inner loop as an incoming value.
Value *V = followLCSSA(
PHI.getIncomingValueForBlock(OuterLoop->getLoopLatch()));
PHINode *InnerRedPhi = findInnerReductionPhi(
InnerLoop, V, HasNoWrapReductions, HasNoInfInsts);
// Reject if PHI has users other than InnerRedPhi. The typical case is
// as follows:
//
// o.header:
// %red.o = phi [ 0, ... ], [ %red.next, %o.latch ]
// br label %i.header
//
// i.header:
// %red.i = phi [ %red.o, %o.header ], [ %red.next, %i.latch ]
// br label %i.body
//
// i.body:
// store %red.o to %mem
// ...
//
if (!InnerRedPhi ||
!llvm::is_contained(InnerRedPhi->incoming_values(), &PHI) ||
!all_of(PHI.users(),
[InnerRedPhi](User *U) { return U == InnerRedPhi; })) {
LLVM_DEBUG(
dbgs()
<< "Failed to recognize PHI as an induction or reduction.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
OuterLoop->getStartLoc(),
OuterLoop->getHeader())
<< "Only outer loops with induction or reduction PHI nodes "
"can be interchanged currently.";
});
return false;
}
OuterInnerReductions.insert(&PHI);
OuterInnerReductions.insert(InnerRedPhi);
} else {
if (OuterInnerReductions.count(&PHI)) {
LLVM_DEBUG(dbgs() << "Found a reduction across the outer loop.\n");
} else if (Opts.loop_interchange_reduction_to_mem &&
isInnerReduction(CurLoop, &PHI, HasNoWrapReductions)) {
LLVM_DEBUG(dbgs() << "Found a reduction in the inner loop: \n"
<< PHI << '\n');
} else {
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
CurLoop->getStartLoc(),
CurLoop->getHeader())
<< "Only inner loops with induction or reduction PHI nodes "
"can be interchanged currently.";
});
return false;
}
}
}
// For now we only support at most one reduction.
if (InnerReductions.size() > 1) {
LLVM_DEBUG(dbgs() << "Only supports at most one reduction.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
CurLoop->getStartLoc(),
CurLoop->getHeader())
<< "Only supports at most one reduction.";
});
return false;
}
}
return !InnerLoopInductions.empty();
}
// This function indicates the current limitations in the transform as a result
// of which we do not proceed.
bool LoopInterchangeLegality::currentLimitations() {
BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
// transform currently expects the loop latches to also be the exiting
// blocks.
if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
!isa<CondBrInst>(InnerLoopLatch->getTerminator()) ||
!isa<CondBrInst>(OuterLoop->getLoopLatch()->getTerminator())) {
LLVM_DEBUG(
dbgs() << "Loops where the latch is not the exiting block are not"
<< " supported currently.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
OuterLoop->getStartLoc(),
OuterLoop->getHeader())
<< "Loops where the latch is not the exiting block cannot be"
" interchange currently.";
});
return true;
}
// TODO: Triangular loops are not handled for now.
if (!isLoopStructureUnderstood()) {
LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
InnerLoop->getStartLoc(),
InnerLoop->getHeader())
<< "Inner loop structure not understood currently.";
});
return true;
}
// Currently, we do not support loops that have a predecessor entering the
// loop via an indirectbr.
for (Loop *L : {OuterLoop, InnerLoop}) {
BasicBlock *Header = L->getHeader();
for (BasicBlock *Pred : predecessors(Header)) {
if (L->contains(Pred))
continue;
if (isa<IndirectBrInst>(Pred->getTerminator())) {
LLVM_DEBUG(
dbgs() << "Indirect branch found in the loop predecessor.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "IndirectBranchPreheader",
L->getStartLoc(), L->getHeader())
<< "Indirect branch found in the loop predecessor.";
});
return true;
}
}
}
// Currently, we do not support loops where the inner loop header has
// duplicate successors.
SmallPtrSet<BasicBlock *, 2> InnerLoopHeaderSuccs;
for (BasicBlock *Succ : successors(InnerLoop->getHeader()))
if (!InnerLoopHeaderSuccs.insert(Succ).second)
return true;
return false;
}
/// We currently only support LCSSA PHI nodes in the inner loop exit if their
/// users are either of the following:
///
/// - Reduction PHIs
/// - PHIs outside the outer loop
/// - PHIs belonging to the latch of the outer loop
///
/// These conditions mean that we are only interested in the final value after
/// the inner loop.
static bool
areInnerLoopExitPHIsSupported(Loop *OuterL, Loop *InnerL,
SmallPtrSetImpl<PHINode *> &Reductions,
PHINode *LcssaReduction) {
BasicBlock *InnerExit = InnerL->getUniqueExitBlock();
for (PHINode &PHI : InnerExit->phis()) {
// The reduction LCSSA PHI will have only one incoming block, which comes
// from the loop latch.
if (PHI.getNumIncomingValues() > 1)
return false;
// The reduction LCSSA PHI's store user is rewritten by reduction2Memory();
// skip its user-check but keep validating the remaining LCSSA PHIs.
if (&PHI == LcssaReduction)
continue;
if (any_of(PHI.users(), [&Reductions, OuterL](User *U) {
PHINode *PN = dyn_cast<PHINode>(U);
if (!PN)
return true;
if (Reductions.count(PN))
return false;
BasicBlock *PB = PN->getParent();
if (!OuterL->contains(PB))
return false;
return PB != OuterL->getLoopLatch();
}))
return false;
}
return true;
}
// We currently support LCSSA PHI nodes in the outer loop exit, if their
// incoming values do not come from the outer loop latch or if the
// outer loop latch has a single predecessor. In that case, the value will
// be available if both the inner and outer loop conditions are true, which
// will still be true after interchanging. If we have multiple predecessor,
// that may not be the case, e.g. because the outer loop latch may be executed
// if the inner loop is not executed.
static bool areOuterLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
for (PHINode &PHI : LoopNestExit->phis()) {
for (Value *Incoming : PHI.incoming_values()) {
Instruction *IncomingI = dyn_cast<Instruction>(Incoming);
if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
continue;
// The incoming value is defined in the outer loop latch. Currently we
// only support that in case the outer loop latch has a single predecessor.
// This guarantees that the outer loop latch is executed if and only if
// the inner loop is executed (because tightlyNested() guarantees that the
// outer loop header only branches to the inner loop or the outer loop
// latch).
// FIXME: We could weaken this logic and allow multiple predecessors,
// if the values are produced outside the loop latch. We would need
// additional logic to update the PHI nodes in the exit block as
// well.
if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
return false;
}
}
return true;
}
/// The transform partially clones the inner loop's latch block, but PHI nodes
/// cannot be cloned this way. This function follows the instruction trees that
/// would be cloned and checks whether any PHI node other than the induction
/// PHIs feeds them. If such a PHI is found, the interchange is rejected.
///
/// TODO: This check strongly depends on the current implementation of the
/// transform. Ideally, the transform should be able to handle such PHI nodes in
/// the inner loop latch.
static bool areInnerLoopLatchPHIsSupported(Loop *InnerLoop,
ArrayRef<PHINode *> InductionPHIs) {
BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
// Seed the worklist with the roots of the use-def chains the transform
// clones: the latch's exit condition and the incoming values of the induction
// PHIs from the latch.
SmallSetVector<Instruction *, 8> Worklist;
if (auto *LatchBI = dyn_cast<CondBrInst>(InnerLoopLatch->getTerminator()))
if (auto *CondI = dyn_cast<Instruction>(LatchBI->getCondition()))
Worklist.insert(CondI);
for (PHINode *InductionPHI : InductionPHIs) {
if (auto *IncomingI = dyn_cast<Instruction>(
InductionPHI->getIncomingValueForBlock(InnerLoopLatch)))
if (!is_contained(InductionPHIs, IncomingI))
Worklist.insert(IncomingI);
}
// Bail if a PHI node other than the induction PHIs feeds the cloned
// instructions, walking the operand trees within the inner loop.
SmallPtrSet<Instruction *, 4> InductionPHISet(InductionPHIs.begin(),
InductionPHIs.end());
for (unsigned I = 0; I < Worklist.size(); ++I) {
Instruction *Cur = Worklist[I];
if (isa<PHINode>(Cur) && !InductionPHISet.contains(Cur))
return false;
for (Value *Op : Cur->operands())
if (auto *OpI = dyn_cast<Instruction>(Op))
if (InnerLoop->contains(OpI))
Worklist.insert(OpI);
}
return true;
}
bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
unsigned OuterLoopId,
CharMatrix &DepMatrix) {
if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
<< " and OuterLoopId = " << OuterLoopId
<< " due to dependence\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
InnerLoop->getStartLoc(),
InnerLoop->getHeader())
<< "Cannot interchange loops due to dependences.";
});
return false;
}
// Check if outer and inner loop contain legal instructions only.
for (auto *BB : OuterLoop->blocks())
for (Instruction &I : *BB) {
// Loads and stores are checked separately, so we can skip them here.
if (isa<LoadInst, StoreInst, PseudoProbeInst>(&I))
continue;
// We cannot ignore potential memory reads, e.g., loads inside the called
// function.
if (!I.mayHaveSideEffects() && !I.mayReadFromMemory())
continue;
LLVM_DEBUG(
dbgs()
<< "Loops contain instructions that cannot be safely interchanged\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsafeInst",
I.getDebugLoc(), I.getParent())
<< "Cannot interchange loops due to instruction that is "
"potentially unsafe to interchange.";
});
return false;
}
if (!checkInductionsAndReductions(OuterLoop)) {
LLVM_DEBUG(dbgs() << "Failed to find inner loop inductions or found "
"unsupported reductions.\n");
return false;
}
if (!areInnerLoopLatchPHIsSupported(InnerLoop, InnerLoopInductions)) {
LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop latch.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerLatchPHI",
InnerLoop->getStartLoc(),
InnerLoop->getHeader())
<< "Cannot interchange loops because unsupported PHI nodes found "
"in inner loop latch.";
});
return false;
}
FreezeInst *Freeze = findFreezeInReNestedBlocks(OuterLoop, InnerLoop);
if (!Freeze)
Freeze = findFreezeInInnerLatchCloneSet(InnerLoop, InnerLoopInductions);
if (Freeze) {
LLVM_DEBUG(dbgs() << "Interchange would re-nest or duplicate freeze\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsafeInst",
Freeze->getDebugLoc(),
Freeze->getParent())
<< "Cannot interchange loops because re-nesting or duplicating "
"freeze may change its sampling behavior.";
});
return false;
}
// TODO: The loops could not be interchanged due to current limitations in the
// transform module.
if (currentLimitations()) {
LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
return false;
}
// Check if the loops are tightly nested.
if (!tightlyNested(OuterLoop, InnerLoop)) {
LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
InnerLoop->getStartLoc(),
InnerLoop->getHeader())
<< "Cannot interchange loops because they are not tightly "
"nested.";
});
return false;
}
// The LCSSA PHI for the reduction has passed checks before; its user
// is a store instruction.
PHINode *LcssaReduction = nullptr;
assert(InnerReductions.size() <= 1 &&
"So far we only support at most one reduction.");
if (InnerReductions.size() == 1)
LcssaReduction = InnerReductions[0].LcssaPhi;
if (!areInnerLoopExitPHIsSupported(OuterLoop, InnerLoop, OuterInnerReductions,
LcssaReduction)) {
LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop exit.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
InnerLoop->getStartLoc(),
InnerLoop->getHeader())
<< "Found unsupported PHI node in loop exit.";
});
return false;
}
if (!areOuterLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
OuterLoop->getStartLoc(),
OuterLoop->getHeader())
<< "Found unsupported PHI node in loop exit.";
});
return false;
}
if (any_of(OuterLoop->getLoopLatch()->phis(),
[](PHINode &PHI) { return PHI.getNumIncomingValues() != 1; })) {
LLVM_DEBUG(dbgs() << "Only outer loop latch PHI nodes with one incoming "
"value are supported.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLatchPHI",
OuterLoop->getStartLoc(),
OuterLoop->getHeader())
<< "Only outer loop latch PHI nodes with one incoming value are "
"supported.";
});
return false;
}
// Regarding def-use chains that begin at an LCSSA PHI in the inner loop exit
// and end at any instruction in the outer loop latch, we currently support
// only the case where the chain contains only PHI nodes. Since we already
// call `tightlyNested()`, we know that if there is a def-use chain that we
// don't support (i.e., a chain that contains a non-PHI user), then the
// non-PHI user must be in the outer loop latch.
if (InnerLoop->getExitBlock() != OuterLoop->getLoopLatch())
for (PHINode &PHI : OuterLoop->getLoopLatch()->phis())
if (any_of(PHI.users(), [](const User *U) { return !isa<PHINode>(U); })) {
LLVM_DEBUG(dbgs() << "Outer loop latch PHI has a non-PHI user.\n");
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLatchPHI",
OuterLoop->getStartLoc(),
OuterLoop->getHeader())
<< "Cannot interchange loops because an outer loop latch PHI "
"node has a non-PHI user.";
});
return false;
}
return true;
}
void CacheCostManager::computeIfUnitinialized() {
if (CC.has_value())
return;
LLVM_DEBUG(dbgs() << "Compute CacheCost.\n");
CC = CacheCost::getCacheCost(*OutermostLoop, *AR, *DI);
// Obtain the loop vector returned from loop cache analysis beforehand,
// and put each <Loop, index> pair into a map for constant time query
// later. Indices in loop vector reprsent the optimal order of the
// corresponding loop, e.g., given a loopnest with depth N, index 0
// indicates the loop should be placed as the outermost loop and index N
// indicates the loop should be placed as the innermost loop.
//
// For the old pass manager CacheCost would be null.
if (*CC != nullptr)
for (const auto &[Idx, Cost] : enumerate((*CC)->getLoopCosts()))
CostMap[Cost.first] = Idx;
}
CacheCost *CacheCostManager::getCacheCost() {
computeIfUnitinialized();
return CC->get();
}
const DenseMap<const Loop *, unsigned> &CacheCostManager::getCostMap() {
computeIfUnitinialized();
return CostMap;
}
/// If \S contains an affine addrec for \p L, return the step recurrence of it.
/// If \S is loop invariant with respect to \p L, return nullptr. Otherwise,
/// return std::nullopt, which indicates we cannot determine the coefficient of
/// the addrec for \p L in \S.
/// TODO: Handle more complex cases. Maybe using SCEVTraversal is a good way to
/// do that.
static std::optional<const SCEV *>
getAddRecCoefficient(ScalarEvolution &SE, const SCEV *S, const Loop *L) {
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
if (!AR) {
if (SE.isLoopInvariant(S, L))
return nullptr;
return std::nullopt;
}
if (!AR->isAffine()) {
LLVM_DEBUG(dbgs() << "Unexpected non-affine addrec\n");
return std::nullopt;
}
std::optional<const SCEV *> Coeff =
getAddRecCoefficient(SE, AR->getStart(), L);
if (!Coeff.has_value())
return std::nullopt;
if (AR->getLoop() == L) {
assert(!*Coeff && "Found more than one addrec for the same loop");
Coeff = AR->getStepRecurrence(SE);
}
return Coeff;
}
int LoopInterchangeProfitability::getInstrOrderCost() {
SmallPtrSet<const SCEV *, 4> GoodBasePtrs, BadBasePtrs;
for (BasicBlock *BB : InnerLoop->blocks()) {
for (Instruction &Ins : *BB) {
if (!isa<LoadInst, StoreInst>(&Ins))
continue;
const SCEV *Access = SE->getSCEV(getLoadStorePointerOperand(&Ins));
const SCEV *BasePtr = SE->getPointerBase(Access);
std::optional<const SCEV *> OuterCoeff =
getAddRecCoefficient(*SE, Access, OuterLoop);
std::optional<const SCEV *> InnerCoeff =
getAddRecCoefficient(*SE, Access, InnerLoop);
if (!OuterCoeff.has_value() || !*OuterCoeff || !InnerCoeff.has_value() ||
!*InnerCoeff)
continue;
// This heuristic assumes that a smaller step recurrence implies that the
// induction variable corresponding to the loop is used in the inner
// dimension of the array. Placing such a loop in the inner position would
// be beneficial in terms of locality. If the array access is of the form
// like `A[3*i + 2*j]`, this heuristic may lead to an unprofitable
// interchange, but we expect such cases to be rare.
const SCEV *OuterStep = SE->getAbsExpr(*OuterCoeff, /*IsNSW=*/false);
const SCEV *InnerStep = SE->getAbsExpr(*InnerCoeff, /*IsNSW=*/false);
// If we find the inner induction after an outer induction e.g.
//
// for(int i=0;i<N;i++)
// for(int j=0;j<N;j++)
// A[i][j] = A[i-1][j-1]+k;
//
//
// then it is a good order. If we find the outer induction after an inner
// induction e.g.
//
// for(int i=0;i<N;i++)
// for(int j=0;j<N;j++)
// A[j][i] = A[j-1][i-1]+k;
//
// then it is a bad order.
//
// To avoid counting the same base pointers multiple times, we deduplicate
// them by using a set of base pointers.
if (SE->isKnownPredicate(ICmpInst::ICMP_SLT, InnerStep, OuterStep))
GoodBasePtrs.insert(BasePtr);
else if (SE->isKnownPredicate(ICmpInst::ICMP_SLT, OuterStep, InnerStep))
BadBasePtrs.insert(BasePtr);
}
}
int GoodOrder = GoodBasePtrs.size();
int BadOrder = BadBasePtrs.size();
return GoodOrder - BadOrder;
}
std::optional<bool>
LoopInterchangeProfitability::isProfitablePerLoopCacheAnalysis(
const DenseMap<const Loop *, unsigned> &CostMap, CacheCost *CC) {
// This is the new cost model returned from loop cache analysis.
// A smaller index means the loop should be placed an outer loop, and vice
// versa.
auto InnerLoopIt = CostMap.find(InnerLoop);
if (InnerLoopIt == CostMap.end())
return std::nullopt;
auto OuterLoopIt = CostMap.find(OuterLoop);
if (OuterLoopIt == CostMap.end())
return std::nullopt;
if (CC->getLoopCost(*OuterLoop) == CC->getLoopCost(*InnerLoop))
return std::nullopt;
unsigned InnerIndex = InnerLoopIt->second;
unsigned OuterIndex = OuterLoopIt->second;
LLVM_DEBUG(dbgs() << "InnerIndex = " << InnerIndex
<< ", OuterIndex = " << OuterIndex << "\n");
assert(InnerIndex != OuterIndex && "CostMap should assign unique "
"numbers to each loop");
return std::optional<bool>(InnerIndex < OuterIndex);
}
std::optional<bool>
LoopInterchangeProfitability::isProfitablePerInstrOrderCost() {
// Legacy cost model: this is rough cost estimation algorithm. It counts the
// good and bad order of induction variables in the instruction and allows
// reordering if number of bad orders is more than good.
int Cost = getInstrOrderCost();
LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
if (Cost < 0 && Cost < Opts.loop_interchange_threshold)
return std::optional<bool>(true);
return std::nullopt;
}
/// Return true if we can vectorize the loop specified by \p LoopId.
static bool canVectorize(const CharMatrix &DepMatrix, unsigned LoopId) {
for (const auto &Dep : DepMatrix) {
char Dir = Dep[LoopId];
char DepType = Dep.back();
assert((DepType == '<' || DepType == '*') &&
"Unexpected element in dependency vector");
// There are no loop-carried dependencies.
if (Dir == '=' || Dir == 'I')
continue;
// DepType being '<' means that this direction vector represents a forward
// dependency. In principle, a loop with '<' direction can be vectorized in
// this case.
if (Dir == '<' && DepType == '<')
continue;
// We cannot prove that the loop is vectorizable.
return false;
}
return true;
}
std::optional<bool> LoopInterchangeProfitability::isProfitableForVectorization(
unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix) {
// If the outer loop cannot be vectorized, it is not profitable to move this
// to inner position.
if (!canVectorize(DepMatrix, OuterLoopId))
return false;
// If the inner loop cannot be vectorized but the outer loop can be, then it
// is profitable to interchange to enable inner loop parallelism.
if (!canVectorize(DepMatrix, InnerLoopId))
return true;
// If both the inner and the outer loop can be vectorized, it is necessary to
// check the cost of each vectorized loop for profitability decision. At this
// time we do not have a cost model to estimate them, so return nullopt.
// TODO: Estimate the cost of vectorized loop when both the outer and the
// inner loop can be vectorized.
return std::nullopt;
}
bool LoopInterchangeProfitability::isProfitable(
const Loop *InnerLoop, const Loop *OuterLoop, unsigned InnerLoopId,
unsigned OuterLoopId, CharMatrix &DepMatrix, CacheCostManager &CCM) {
// Do not consider loops with a backedge that isn't taken, e.g. an
// unconditional branch true/false, as candidates for interchange.
// TODO: when interchange is forced, we should probably also allow
// interchange for these loops, and thus this logic should be moved just
// below the cost-model ignore check below. But this check is done first
// to avoid the issue in #163954.
const SCEV *InnerBTC = SE->getBackedgeTakenCount(InnerLoop);
const SCEV *OuterBTC = SE->getBackedgeTakenCount(OuterLoop);
if (InnerBTC && InnerBTC->isZero()) {
LLVM_DEBUG(dbgs() << "Inner loop back-edge isn't taken, rejecting "
"single iteration loop\n");
return false;
}
if (OuterBTC && OuterBTC->isZero()) {
LLVM_DEBUG(dbgs() << "Outer loop back-edge isn't taken, rejecting "
"single iteration loop\n");
return false;
}
ArrayRef<LoopInterchangeRule> Profitabilities =
Opts.loop_interchange_profitabilities;
if (Profitabilities.empty())
Profitabilities = DefaultProfitabilities;
// Return true if interchange is forced and the cost-model ignored.
if (Profitabilities.size() == 1 &&
Profitabilities[0] == LoopInterchangeRule::Ignore)
return true;
assert(noDuplicateRulesAndIgnore(Profitabilities) &&
"Duplicate rules and option 'ignore' are not allowed");
// isProfitable() is structured to avoid endless loop interchange. If the
// highest priority rule (isProfitablePerLoopCacheAnalysis by default) could
// decide the profitability then, profitability check will stop and return the
// analysis result. If it failed to determine it (e.g., cache analysis failed
// to analyze the loopnest due to delinearization issues) then go ahead the
// second highest priority rule (isProfitablePerInstrOrderCost by default).
// Likewise, if it failed to analysis the profitability then only, the last
// rule (isProfitableForVectorization by default) will decide.
std::optional<bool> shouldInterchange;
for (LoopInterchangeRule RT : Profitabilities) {
switch (RT) {
case LoopInterchangeRule::PerLoopCacheAnalysis: {
CacheCost *CC = CCM.getCacheCost();
const DenseMap<const Loop *, unsigned> &CostMap = CCM.getCostMap();
shouldInterchange = isProfitablePerLoopCacheAnalysis(CostMap, CC);
break;
}
case LoopInterchangeRule::PerInstrOrderCost:
shouldInterchange = isProfitablePerInstrOrderCost();
break;
case LoopInterchangeRule::ForVectorization:
shouldInterchange =
isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
break;
case LoopInterchangeRule::Ignore:
llvm_unreachable("Option 'ignore' is not supported with other options");
break;
}
// If this rule could determine the profitability, don't call subsequent
// rules.
if (shouldInterchange.has_value())
break;
}
if (!shouldInterchange.has_value()) {
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
InnerLoop->getStartLoc(),
InnerLoop->getHeader())
<< "Insufficient information to calculate the cost of loop for "
"interchange.";
});
return false;
} else if (!shouldInterchange.value()) {
ORE->emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
InnerLoop->getStartLoc(),
InnerLoop->getHeader())
<< "Interchanging loops is not considered to improve cache "
"locality nor vectorization.";
});
return false;
}
return true;
}
void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
Loop *InnerLoop) {
for (Loop *L : *OuterLoop)
if (L == InnerLoop) {
OuterLoop->removeChildLoop(L);
return;
}
llvm_unreachable("Couldn't find loop");
}
/// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
/// new inner and outer loop after interchanging: NewInner is the original
/// outer loop and NewOuter is the original inner loop.
///
/// Before interchanging, we have the following structure
/// Outer preheader
// Outer header
// Inner preheader
// Inner header
// Inner body
// Inner latch
// outer bbs
// Outer latch
//
// After interchanging:
// Inner preheader
// Inner header
// Outer preheader
// Outer header
// Inner body
// outer bbs
// Outer latch
// Inner latch
void LoopInterchangeTransform::restructureLoops(
Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
BasicBlock *OrigOuterPreHeader) {
Loop *OuterLoopParent = OuterLoop->getParentLoop();
// The original inner loop preheader moves from the new inner loop to
// the parent loop, if there is one.
NewInner->removeBlockFromLoop(OrigInnerPreHeader);
LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
// Switch the loop levels.
removeChildLoop(NewInner, NewOuter);
// Replace NewInner with NewOuter in place, preserving sibling order.
LI->replaceLoop(NewInner, NewOuter);
while (!NewOuter->isInnermost())
NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
NewOuter->addChildLoop(NewInner);
// BBs from the original inner loop.
SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
// Add BBs from the original outer loop to the original inner loop (excluding
// BBs already in inner loop)
for (BasicBlock *BB : NewInner->blocks())
if (LI->getLoopFor(BB) == NewInner)
NewOuter->addBlockEntry(BB);
// Now remove inner loop header and latch from the new inner loop and move
// other BBs (the loop body) to the new inner loop.
BasicBlock *OuterHeader = NewOuter->getHeader();
BasicBlock *OuterLatch = NewOuter->getLoopLatch();
for (BasicBlock *BB : OrigInnerBBs) {
// Nothing will change for BBs in child loops.
if (LI->getLoopFor(BB) != NewOuter)
continue;
// Remove the new outer loop header and latch from the new inner loop.
if (BB == OuterHeader || BB == OuterLatch)
NewInner->removeBlockFromLoop(BB);
else
LI->changeLoopFor(BB, NewInner);
}
// The preheader of the original outer loop becomes part of the new
// outer loop.
NewOuter->addBlockEntry(OrigOuterPreHeader);
LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
// Tell SE that we move the loops around.
SE->forgetLoop(NewOuter);
}
/// User can write, or optimizers can generate the reduction for inner loop.
/// To make the interchange valid, apply Reduction2Mem by moving the
/// initializer and store instructions into the inner loop. So far we only
/// handle cases where the reduction variable is initialized to a constant.
/// For example, below code:
///
/// loop:
/// re = phi<0.0, next>
/// next = re op ...
/// endloop
/// reduc_sum = phi<next> // lcssa phi
/// MEM_REF[idx] = reduc_sum // LcssaStore
///
/// is transformed into:
///
/// loop:
/// tmp = MEM_REF[idx];
/// new_var = !first_iteration ? tmp : 0.0;
/// next = new_var op ...
/// MEM_REF[idx] = next; // after moving
/// endloop
///
/// In this way the initial const is used in the first iteration of loop.
void LoopInterchangeTransform::reduction2Memory() {
ArrayRef<LoopInterchangeLegality::InnerReduction> InnerReductions =
LIL.getInnerReductions();
assert(InnerReductions.size() == 1 &&
"So far we only support at most one reduction.");
LoopInterchangeLegality::InnerReduction SR = InnerReductions[0];
BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
IRBuilder<> Builder(InnerLoopHeader->getFirstNonPHIIt());
// Check if it's the first iteration.
LLVMContext &Context = InnerLoopHeader->getContext();
PHINode *FirstIter =
Builder.CreatePHI(Type::getInt1Ty(Context), 2, "first.iter");
FirstIter->addIncoming(ConstantInt::get(Type::getInt1Ty(Context), 1),
InnerLoop->getLoopPreheader());
FirstIter->addIncoming(ConstantInt::get(Type::getInt1Ty(Context), 0),
InnerLoop->getLoopLatch());
assert(FirstIter->isComplete() && "The FirstIter PHI node is not complete.");
// When the reduction is initialized from a constant value, we need to add
// a stmt loading from the memory object to target basic block in inner
// loop.
Instruction *LoadMem = Builder.CreateLoad(SR.ElemTy, SR.MemRef);
// Init new_var to MEM_REF or CONST depending on if it is the first iteration.
Value *NewVar = Builder.CreateSelect(FirstIter, SR.Init, LoadMem, "new.var");
// Replace all uses of the reduction variable with a new variable.
SR.Reduction->replaceAllUsesWith(NewVar);
// Move store instruction into inner loop, just after reduction next's
// definition.
SR.LcssaStore->setOperand(0, SR.Next);
SR.LcssaStore->moveAfter(dyn_cast<Instruction>(SR.Next));
}
void LoopInterchangeTransform::transform(
ArrayRef<Instruction *> DropNoWrapInsts,
ArrayRef<Instruction *> DropNoInfInsts) {
ArrayRef<LoopInterchangeLegality::InnerReduction> InnerReductions =
LIL.getInnerReductions();
if (InnerReductions.size() == 1)
reduction2Memory();
LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n");
auto &InductionPHIs = LIL.getInnerLoopInductions();
assert(!InductionPHIs.empty() &&
"Expected at least one induction variable in the inner loop");
SmallVector<Instruction *, 8> InnerIndexVarList;
for (PHINode *CurInductionPHI : InductionPHIs) {
Instruction *IncomingValue = dyn_cast<Instruction>(
CurInductionPHI->getIncomingValueForBlock(InnerLoop->getLoopLatch()));
assert(IncomingValue &&
"Incoming value from loop latch isn't an instruction");
if (is_contained(InductionPHIs, IncomingValue))
continue;
InnerIndexVarList.push_back(IncomingValue);
}
// Create a new latch block for the inner loop. We split at the
// current latch's terminator and then move the condition and all
// operands that are not either loop-invariant or the induction PHI into the
// new latch block.
BasicBlock *NewLatch =
SplitBlock(InnerLoop->getLoopLatch(),
InnerLoop->getLoopLatch()->getTerminator(), DT, LI);
// Keep these seeds and the operand filter aligned with
// findFreezeInInnerLatchCloneSet.
SmallSetVector<Instruction *, 4> WorkList;
unsigned i = 0;
auto MoveInstructions = [&i, &WorkList, this, &InductionPHIs, NewLatch]() {
for (; i < WorkList.size(); i++) {
// PHI nodes cannot be cloned and moved here; the legality check
// (areInnerLoopLatchPHIsSupported) ensures none reach the worklist.
assert(!isa<PHINode>(WorkList[i]) &&
"MoveInstructions does not support PHI nodes");
// Duplicate instruction and move it to the new latch. Update uses that
// have been moved.
Instruction *NewI = WorkList[i]->clone();
NewI->insertBefore(NewLatch->getFirstNonPHIIt());
assert(!NewI->mayHaveSideEffects() &&
"Moving instructions with side-effects may change behavior of "
"the loop nest!");
for (Use &U : llvm::make_early_inc_range(WorkList[i]->uses())) {
Instruction *UserI = cast<Instruction>(U.getUser());
if (!InnerLoop->contains(UserI->getParent()) ||
UserI->getParent() == NewLatch ||
llvm::is_contained(InductionPHIs, UserI))
U.set(NewI);
}
// Add operands of moved instruction to the worklist, except if they are
// outside the inner loop or are the induction PHI.
for (Value *Op : WorkList[i]->operands()) {
Instruction *OpI = dyn_cast<Instruction>(Op);
if (!OpI || this->LI->getLoopFor(OpI->getParent()) != this->InnerLoop ||
llvm::is_contained(InductionPHIs, OpI))
continue;
WorkList.insert(OpI);
}
}
};
// FIXME: Should we interchange when we have a constant condition?
Instruction *CondI = dyn_cast<Instruction>(
cast<CondBrInst>(InnerLoop->getLoopLatch()->getTerminator())
->getCondition());
if (CondI)
WorkList.insert(CondI);
MoveInstructions();
for (Instruction *InnerIndexVar : InnerIndexVarList)
WorkList.insert(cast<Instruction>(InnerIndexVar));
MoveInstructions();
// Split the inner header so that it has a unique successor.
BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHIIt(), DT, LI);
LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");
// Instructions in the original inner loop preheader may depend on values
// defined in the outer loop header. Move them there, because the original
// inner loop preheader will become the entry into the interchanged loop nest.
// Currently we move all instructions and rely on LICM to move invariant
// instructions outside the loop nest.
BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
if (InnerLoopPreHeader != OuterLoopHeader) {
// Eliminate PHIs in the inner-loop preheader.
for (PHINode &P : make_early_inc_range(InnerLoopPreHeader->phis())) {
assert(all_equal(P.incoming_values()) &&
"Expected equivalent incoming values in inner loop preheader");
P.replaceAllUsesWith(P.getIncomingValue(0));
P.eraseFromParent();
}
for (Instruction &I :
make_early_inc_range(make_range(InnerLoopPreHeader->begin(),
std::prev(InnerLoopPreHeader->end()))))
I.moveBeforePreserving(OuterLoopHeader->getTerminator()->getIterator());
}
adjustLoopBranches();
// Finally, drop the nsw/nuw/ninf flags from the instructions for reduction
// calculations.
for (Instruction *Reduction : DropNoWrapInsts) {
Reduction->setHasNoSignedWrap(false);
Reduction->setHasNoUnsignedWrap(false);
}
for (Instruction *I : DropNoInfInsts)
I->setHasNoInfs(false);
}
/// \brief Move all instructions except the terminator from FromBB right before
/// InsertBefore
static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
BasicBlock *ToBB = InsertBefore->getParent();
ToBB->splice(InsertBefore->getIterator(), FromBB, FromBB->begin(),
FromBB->getTerminator()->getIterator());
}
/// Swap instructions between \p BB1 and \p BB2 but keep terminators intact.
static void swapBBContents(BasicBlock *BB1, BasicBlock *BB2) {
// Save all non-terminator instructions of BB1 into TempInstrs and unlink them
// from BB1 afterwards.
auto Iter = map_range(*BB1, [](Instruction &I) { return &I; });
SmallVector<Instruction *, 4> TempInstrs(Iter.begin(), std::prev(Iter.end()));
for (Instruction *I : TempInstrs)
I->removeFromParent();
// Move instructions from BB2 to BB1.
moveBBContents(BB2, BB1->getTerminator());
// Move instructions from TempInstrs to BB2.
for (Instruction *I : TempInstrs)
I->insertBefore(BB2->getTerminator()->getIterator());
}
// Update BI to jump to NewBB instead of OldBB. Records updates to the
// dominator tree in DTUpdates. If \p MustUpdateOnce is true, assert that
// \p OldBB is exactly once in BI's successor list.
static void updateSuccessor(Instruction *Term, BasicBlock *OldBB,
BasicBlock *NewBB,
std::vector<DominatorTree::UpdateType> &DTUpdates,
bool MustUpdateOnce = true) {
assert((!MustUpdateOnce || llvm::count(successors(Term), OldBB) == 1) &&
"BI must jump to OldBB exactly once.");
bool Changed = false;
for (Use &Op : Term->operands())
if (Op == OldBB) {
Op.set(NewBB);
Changed = true;
}
if (Changed) {
DTUpdates.push_back(
{DominatorTree::UpdateKind::Insert, Term->getParent(), NewBB});
DTUpdates.push_back(
{DominatorTree::UpdateKind::Delete, Term->getParent(), OldBB});
}
assert(Changed && "Expected a successor to be updated");
}
// Move Lcssa PHIs to the right place.
static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
BasicBlock *InnerLatch, BasicBlock *OuterHeader,
BasicBlock *OuterLatch, BasicBlock *OuterExit,
Loop *InnerLoop, LoopInfo *LI) {
// Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
// defined either in the header or latch. Those blocks will become header and
// latch of the new outer loop, and the only possible users can PHI nodes
// in the exit block of the loop nest or the outer loop header (reduction
// PHIs, in that case, the incoming value must be defined in the inner loop
// header). We can just substitute the user with the incoming value and remove
// the PHI.
for (PHINode &P : make_early_inc_range(InnerExit->phis())) {
assert(P.getNumIncomingValues() == 1 &&
"Only loops with a single exit are supported!");
Value *IncomingValue = P.getIncomingValueForBlock(InnerLatch);
auto *IncI = dyn_cast<Instruction>(IncomingValue);
if (!IncI) {
// If the incoming value is not an instruction, it must be loop invariant.
// In that case, we can just replace the PHI with the incoming value and
// remove the PHI.
assert(InnerLoop->isLoopInvariant(IncomingValue) &&
"Expected non-instruction incoming value to be loop invariant");
P.replaceAllUsesWith(IncomingValue);
P.eraseFromParent();
continue;
}
// In case of multi-level nested loops, follow LCSSA to find the incoming
// value defined from the innermost loop.
auto *IncIInnerMost = dyn_cast<Instruction>(followLCSSA(IncI));
// Skip phis when:
// - they are not an instruction, e.g. incoming values are constants.
// - Incomming values from the inner loop body, excluding the header and
// latch.
if (!IncIInnerMost || (IncIInnerMost->getParent() != InnerLatch &&
IncIInnerMost->getParent() != InnerHeader))
continue;
assert(all_of(P.users(),
[OuterHeader, OuterExit, IncI, InnerHeader](User *U) {
return (cast<PHINode>(U)->getParent() == OuterHeader &&
IncI->getParent() == InnerHeader) ||
cast<PHINode>(U)->getParent() == OuterExit;
}) &&
"Can only replace phis iff the uses are in the loop nest exit or "
"the incoming value is defined in the inner header (it will "
"dominate all loop blocks after interchanging)");
P.replaceAllUsesWith(IncI);
P.eraseFromParent();
}
SmallVector<PHINode *, 8> LcssaInnerExit(
llvm::make_pointer_range(InnerExit->phis()));
SmallVector<PHINode *, 8> LcssaInnerLatch(
llvm::make_pointer_range(InnerLatch->phis()));
// Lcssa PHIs for values used outside the inner loop are in InnerExit.
// If a PHI node has users outside of InnerExit, it has a use outside the
// interchanged loop and we have to preserve it. We move these to
// InnerLatch, which will become the new exit block for the innermost
// loop after interchanging.
for (PHINode *P : LcssaInnerExit)
P->moveBefore(InnerLatch->getFirstNonPHIIt());
// If the inner loop latch contains LCSSA PHIs, those come from a child loop
// and we have to move them to the new inner latch.
for (PHINode *P : LcssaInnerLatch)
P->moveBefore(InnerExit->getFirstNonPHIIt());
// Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
// incoming values defined in the outer loop, we have to add a new PHI
// in the inner loop latch, which became the exit block of the outer loop,
// after interchanging.
if (OuterExit) {
for (PHINode &P : OuterExit->phis()) {
if (P.getNumIncomingValues() != 1)
continue;
// Skip Phis with incoming values defined in the inner loop. Those should
// already have been updated.
auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
if (!I || LI->getLoopFor(I->getParent()) == InnerLoop)
continue;
PHINode *NewPhi = dyn_cast<PHINode>(P.clone());
NewPhi->setIncomingValue(0, P.getIncomingValue(0));
NewPhi->setIncomingBlock(0, OuterLatch);
// We might have incoming edges from other BBs, i.e., the original outer
// header.
for (auto *Pred : predecessors(InnerLatch)) {
if (Pred == OuterLatch)
continue;
NewPhi->addIncoming(P.getIncomingValue(0), Pred);
}
NewPhi->insertBefore(InnerLatch->getFirstNonPHIIt());
P.setIncomingValue(0, NewPhi);
}
}
// Now adjust the incoming blocks for the LCSSA PHIs.
// For PHIs moved from Inner's exit block, we need to replace Inner's latch
// with the new latch.
InnerLatch->replacePhiUsesWith(InnerLatch, OuterLatch);
}
/// This deals with a corner case when a LCSSA phi node appears in a non-exit
/// block: the outer loop latch block does not need to be exit block of the
/// inner loop. Consider a loop that was in LCSSA form, but then some
/// transformation like loop-unswitch comes along and creates an empty block,
/// where BB5 in this example is the outer loop latch block:
///
/// BB4:
/// br label %BB5
/// BB5:
/// %old.cond.lcssa = phi i16 [ %cond, %BB4 ]
/// br outer.header
///
/// Interchange then brings it in LCSSA form again resulting in this chain of
/// single-input phi nodes:
///
/// BB4:
/// %new.cond.lcssa = phi i16 [ %cond, %BB3 ]
/// br label %BB5
/// BB5:
/// %old.cond.lcssa = phi i16 [ %new.cond.lcssa, %BB4 ]
///
/// The problem is that interchange can reoder blocks BB4 and BB5 placing the
/// use before the def if we don't check this. The solution is to simplify
/// lcssa phi nodes (remove) if they appear in non-exit blocks.
///
static void simplifyLCSSAPhis(Loop *OuterLoop, Loop *InnerLoop) {
BasicBlock *InnerLoopExit = InnerLoop->getExitBlock();
BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
// Do not modify lcssa phis where they actually belong, i.e. in exit blocks.
if (OuterLoopLatch == InnerLoopExit)
return;
// Collect and remove phis in non-exit blocks if they have 1 input.
SmallVector<PHINode *, 8> Phis(
llvm::make_pointer_range(OuterLoopLatch->phis()));
for (PHINode *Phi : Phis) {
assert(Phi->getNumIncomingValues() == 1 && "Single input phi expected");
LLVM_DEBUG(dbgs() << "Removing 1-input phi in non-exit block: " << *Phi
<< "\n");
Phi->replaceAllUsesWith(Phi->getIncomingValue(0));
Phi->eraseFromParent();
}
}
void LoopInterchangeTransform::adjustLoopBranches() {
LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");
std::vector<DominatorTree::UpdateType> DTUpdates;
BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
assert(OuterLoopPreHeader != OuterLoop->getHeader() &&
InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&
InnerLoopPreHeader && "Guaranteed by loop-simplify form");
simplifyLCSSAPhis(OuterLoop, InnerLoop);
// Ensure that both preheaders do not contain PHI nodes and have single
// predecessors. This allows us to move them easily. We use
// InsertPreHeaderForLoop to create an 'extra' preheader, if the existing
// preheaders do not satisfy those conditions.
if (isa<PHINode>(OuterLoopPreHeader->begin()) ||
!OuterLoopPreHeader->getUniquePredecessor())
OuterLoopPreHeader =
InsertPreheaderForLoop(OuterLoop, DT, LI, nullptr, true);
if (InnerLoopPreHeader == OuterLoop->getHeader())
InnerLoopPreHeader =
InsertPreheaderForLoop(InnerLoop, DT, LI, nullptr, true);
// Adjust the loop preheader
BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
BasicBlock *InnerLoopLatchPredecessor =
InnerLoopLatch->getUniquePredecessor();
BasicBlock *InnerLoopLatchSuccessor;
BasicBlock *OuterLoopLatchSuccessor;
CondBrInst *OuterLoopLatchBI =
dyn_cast<CondBrInst>(OuterLoopLatch->getTerminator());
CondBrInst *InnerLoopLatchBI =
dyn_cast<CondBrInst>(InnerLoopLatch->getTerminator());
Instruction *OuterLoopHeaderBI = OuterLoopHeader->getTerminator();
Instruction *InnerLoopHeaderBI = InnerLoopHeader->getTerminator();
assert(OuterLoopPredecessor && InnerLoopLatchPredecessor &&
"Failed to find a unique predecessor");
assert(OuterLoopLatchBI && InnerLoopLatchBI &&
"Failed to find a conditional branch");
Instruction *InnerLoopLatchPredecessorBI =
InnerLoopLatchPredecessor->getTerminator();
Instruction *OuterLoopPredecessorBI = OuterLoopPredecessor->getTerminator();
BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
assert(InnerLoopHeaderSuccessor &&
"Failed to find a unique successor for the inner loop header");
// Adjust Loop Preheader and headers.
// The branches in the outer loop predecessor and the outer loop header can
// be unconditional branches or conditional branches with duplicates. Consider
// this when updating the successors.
updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
InnerLoopPreHeader, DTUpdates, /*MustUpdateOnce=*/false);
// The outer loop header might or might not branch to the outer latch.
// We are guaranteed to branch to the inner loop preheader.
if (llvm::is_contained(successors(OuterLoopHeaderBI), OuterLoopLatch)) {
// In this case the outerLoopHeader should branch to the InnerLoopLatch.
updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, InnerLoopLatch,
DTUpdates,
/*MustUpdateOnce=*/false);
}
updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
InnerLoopHeaderSuccessor, DTUpdates,
/*MustUpdateOnce=*/false);
// Adjust reduction PHI's now that the incoming block has changed.
InnerLoopHeaderSuccessor->replacePhiUsesWith(InnerLoopHeader,
OuterLoopHeader);
updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
OuterLoopPreHeader, DTUpdates);
// -------------Adjust loop latches-----------
if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
else
InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
InnerLoopLatchSuccessor, DTUpdates);
if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
else
OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
OuterLoopLatchSuccessor, DTUpdates);
updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
DTUpdates);
DT->applyUpdates(DTUpdates);
restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
OuterLoopPreHeader);
moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,
OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock(),
InnerLoop, LI);
// For PHIs in the exit block of the outer loop, outer's latch has been
// replaced by Inners'.
OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
auto &OuterInnerReductions = LIL.getOuterInnerReductions();
// Now update the reduction PHIs in the inner and outer loop headers.
SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
for (PHINode &PHI : InnerLoopHeader->phis())
if (OuterInnerReductions.contains(&PHI))
InnerLoopPHIs.push_back(&PHI);
for (PHINode &PHI : OuterLoopHeader->phis())
if (OuterInnerReductions.contains(&PHI))
OuterLoopPHIs.push_back(&PHI);
// Now move the remaining reduction PHIs from outer to inner loop header and
// vice versa. The PHI nodes must be part of a reduction across the inner and
// outer loop and all the remains to do is and updating the incoming blocks.
for (PHINode *PHI : OuterLoopPHIs) {
LLVM_DEBUG(dbgs() << "Outer loop reduction PHIs:\n"; PHI->dump(););
PHI->moveBefore(InnerLoopHeader->getFirstNonPHIIt());
assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
}
for (PHINode *PHI : InnerLoopPHIs) {
LLVM_DEBUG(dbgs() << "Inner loop reduction PHIs:\n"; PHI->dump(););
PHI->moveBefore(OuterLoopHeader->getFirstNonPHIIt());
assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
}
// Update the incoming blocks for moved PHI nodes.
OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);
OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);
InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);
InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
// Swap the preheader contents so each definition sits in the preheader of the
// loop it now belongs to. This runs before the LCSSA rebuild below so that
// any definition referenced across the interchanged levels dominates its uses
// when formLCSSAForInstructions runs.
swapBBContents(OuterLoop->getLoopPreheader(), InnerLoop->getLoopPreheader());
// Values defined in the outer loop header could be used in the inner loop
// latch. In that case, we need to create LCSSA phis for them, because after
// interchanging they will be defined in the new inner loop and used in the
// new outer loop.
SmallVector<Instruction *, 4> MayNeedLCSSAPhis;
for (Instruction &I :
make_range(OuterLoopHeader->begin(), std::prev(OuterLoopHeader->end())))
MayNeedLCSSAPhis.push_back(&I);
#ifndef NDEBUG
assert(!verifyFunction(*OuterLoopHeader->getParent(), &errs()) &&
"LoopInterchange handed dominance-broken IR to LCSSA rebuild");
#endif
formLCSSAForInstructions(MayNeedLCSSAPhis, *DT, *LI, SE);
}
PreservedAnalyses LoopInterchangePass::run(LoopNest &LN,
LoopAnalysisManager &AM,
LoopStandardAnalysisResults &AR,
LPMUpdater &U) {
Function &F = *LN.getParent();
OptimizationRemarkEmitter ORE(&F);
ORE.emit([&]() {
return OptimizationRemarkAnalysis(DEBUG_TYPE, "Dependence",
LN.getOutermostLoop().getStartLoc(),
LN.getOutermostLoop().getHeader())
<< "Computed dependence info, invoking the transform.";
});
DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI);
const ScalarOptions &Opts =
F.getContext().getLibraryOptions().get<ScalarOptions>();
if (!LoopInterchange(Opts, &AR.SE, &AR.LI, &DI, &AR.DT, &AR, &ORE).run(LN))
return PreservedAnalyses::all();
U.markLoopNestChanged(true);
return getLoopPassPreservedAnalyses();
}