LoopUnrollAndJam.cpp | Explore in Territory

//===-- LoopUnrollAndJam.cpp - Loop unrolling utilities -------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements loop unroll and jam as a routine, much like
// LoopUnroll.cpp implements loop unroll.
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GenericDomTree.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <assert.h>
#include <memory>
#include <type_traits>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumUnrolledAndJammed, "Number of loops unroll and jammed");
STATISTIC(NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed");

BasicBlockSet;

// Partition blocks in an outer/inner loop pair into blocks before and after
// the loop
static bool partitionLoopBlocks(Loop &L, BasicBlockSet &ForeBlocks,
                                BasicBlockSet &AftBlocks, DominatorTree &DT) { … }

/// Partition blocks in a loop nest into blocks before and after each inner
/// loop.
static bool partitionOuterLoopBlocks(
    Loop &Root, Loop &JamLoop, BasicBlockSet &JamLoopBlocks,
    DenseMap<Loop *, BasicBlockSet> &ForeBlocksMap,
    DenseMap<Loop *, BasicBlockSet> &AftBlocksMap, DominatorTree &DT) { … }

// TODO Remove when UnrollAndJamLoop changed to support unroll and jamming more
// than 2 levels loop.
static bool partitionOuterLoopBlocks(Loop *L, Loop *SubLoop,
                                     BasicBlockSet &ForeBlocks,
                                     BasicBlockSet &SubLoopBlocks,
                                     BasicBlockSet &AftBlocks,
                                     DominatorTree *DT) { … }

// Looks at the phi nodes in Header for values coming from Latch. For these
// instructions and all their operands calls Visit on them, keeping going for
// all the operands in AftBlocks. Returns false if Visit returns false,
// otherwise returns true. This is used to process the instructions in the
// Aft blocks that need to be moved before the subloop. It is used in two
// places. One to check that the required set of instructions can be moved
// before the loop. Then to collect the instructions to actually move in
// moveHeaderPhiOperandsToForeBlocks.
template <typename T>
static bool processHeaderPhiOperands(BasicBlock *Header, BasicBlock *Latch,
                                     BasicBlockSet &AftBlocks, T Visit) { … }

// Move the phi operands of Header from Latch out of AftBlocks to InsertLoc.
static void moveHeaderPhiOperandsToForeBlocks(BasicBlock *Header,
                                              BasicBlock *Latch,
                                              Instruction *InsertLoc,
                                              BasicBlockSet &AftBlocks) { … }

/*
  This method performs Unroll and Jam. For a simple loop like:
  for (i = ..)
    Fore(i)
    for (j = ..)
      SubLoop(i, j)
    Aft(i)

  Instead of doing normal inner or outer unrolling, we do:
  for (i = .., i+=2)
    Fore(i)
    Fore(i+1)
    for (j = ..)
      SubLoop(i, j)
      SubLoop(i+1, j)
    Aft(i)
    Aft(i+1)

  So the outer loop is essetially unrolled and then the inner loops are fused
  ("jammed") together into a single loop. This can increase speed when there
  are loads in SubLoop that are invariant to i, as they become shared between
  the now jammed inner loops.

  We do this by spliting the blocks in the loop into Fore, Subloop and Aft.
  Fore blocks are those before the inner loop, Aft are those after. Normal
  Unroll code is used to copy each of these sets of blocks and the results are
  combined together into the final form above.

  isSafeToUnrollAndJam should be used prior to calling this to make sure the
  unrolling will be valid. Checking profitablility is also advisable.

  If EpilogueLoop is non-null, it receives the epilogue loop (if it was
  necessary to create one and not fully unrolled).
*/
LoopUnrollResult
llvm::UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
                       unsigned TripMultiple, bool UnrollRemainder,
                       LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
                       AssumptionCache *AC, const TargetTransformInfo *TTI,
                       OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop) { … }

static bool getLoadsAndStores(BasicBlockSet &Blocks,
                              SmallVector<Instruction *, 4> &MemInstr) { … }

static bool preservesForwardDependence(Instruction *Src, Instruction *Dst,
                                       unsigned UnrollLevel, unsigned JamLevel,
                                       bool Sequentialized, Dependence *D) { … }

static bool preservesBackwardDependence(Instruction *Src, Instruction *Dst,
                                        unsigned UnrollLevel, unsigned JamLevel,
                                        bool Sequentialized, Dependence *D) { … }

// Check whether it is semantically safe Src and Dst considering any potential
// dependency between them.
//
// @param UnrollLevel The level of the loop being unrolled
// @param JamLevel    The level of the loop being jammed; if Src and Dst are on
// different levels, the outermost common loop counts as jammed level
//
// @return true if is safe and false if there is a dependency violation.
static bool checkDependency(Instruction *Src, Instruction *Dst,
                            unsigned UnrollLevel, unsigned JamLevel,
                            bool Sequentialized, DependenceInfo &DI) { … }

static bool
checkDependencies(Loop &Root, const BasicBlockSet &SubLoopBlocks,
                  const DenseMap<Loop *, BasicBlockSet> &ForeBlocksMap,
                  const DenseMap<Loop *, BasicBlockSet> &AftBlocksMap,
                  DependenceInfo &DI, LoopInfo &LI) { … }

static bool isEligibleLoopForm(const Loop &Root) { … }

static Loop *getInnerMostLoop(Loop *L) { … }

bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
                                DependenceInfo &DI, LoopInfo &LI) { … }
llvm/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
