GVNHoist.cpp | Explore in Territory

//===- GVNHoist.cpp - Hoist scalar and load expressions -------------------===//
//
// 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 hoists expressions from branches to a common dominator. It uses
// GVN (global value numbering) to discover expressions computing the same
// values. The primary goals of code-hoisting are:
// 1. To reduce the code size.
// 2. In some cases reduce critical path (by exposing more ILP).
//
// The algorithm factors out the reachability of values such that multiple
// queries to find reachability of values are fast. This is based on finding the
// ANTIC points in the CFG which do not change during hoisting. The ANTIC points
// are basically the dominance-frontiers in the inverse graph. So we introduce a
// data structure (CHI nodes) to keep track of values flowing out of a basic
// block. We only do this for values with multiple occurrences in the function
// as they are the potential hoistable candidates. This approach allows us to
// hoist instructions to a basic block with more than two successors, as well as
// deal with infinite loops in a trivial way.
//
// Limitations: This pass does not hoist fully redundant expressions because
// they are already handled by GVN-PRE. It is advisable to run gvn-hoist before
// and after gvn-pre because gvn-pre creates opportunities for more instructions
// to be hoisted.
//
// Hoisting may affect the performance in some cases. To mitigate that, hoisting
// is disabled in the following cases.
// 1. Scalars across calls.
// 2. geps when corresponding load/store cannot be hoisted.
//===----------------------------------------------------------------------===//

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.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/LLVMContext.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar/GVN.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumHoisted, "Number of instructions hoisted");
STATISTIC(NumRemoved, "Number of instructions removed");
STATISTIC(NumLoadsHoisted, "Number of loads hoisted");
STATISTIC(NumLoadsRemoved, "Number of loads removed");
STATISTIC(NumStoresHoisted, "Number of stores hoisted");
STATISTIC(NumStoresRemoved, "Number of stores removed");
STATISTIC(NumCallsHoisted, "Number of calls hoisted");
STATISTIC(NumCallsRemoved, "Number of calls removed");

static cl::opt<int>
    MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1),
                        cl::desc("Max number of instructions to hoist "
                                 "(default unlimited = -1)"));

static cl::opt<int> MaxNumberOfBBSInPath(
    "gvn-hoist-max-bbs", cl::Hidden, cl::init(4),
    cl::desc("Max number of basic blocks on the path between "
             "hoisting locations (default = 4, unlimited = -1)"));

static cl::opt<int> MaxDepthInBB(
    "gvn-hoist-max-depth", cl::Hidden, cl::init(100),
    cl::desc("Hoist instructions from the beginning of the BB up to the "
             "maximum specified depth (default = 100, unlimited = -1)"));

static cl::opt<int>
    MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
                   cl::desc("Maximum length of dependent chains to hoist "
                            "(default = 10, unlimited = -1)"));

namespace llvm {

BBSideEffectsSet;
SmallVecInsn;
SmallVecImplInsn;

// Each element of a hoisting list contains the basic block where to hoist and
// a list of instructions to be hoisted.
HoistingPointInfo;

HoistingPointList;

// A map from a pair of VNs to all the instructions with those VNs.
VNType;

VNtoInsns;

// CHI keeps information about values flowing out of a basic block.  It is
// similar to PHI but in the inverse graph, and used for outgoing values on each
// edge. For conciseness, it is computed only for instructions with multiple
// occurrences in the CFG because they are the only hoistable candidates.
//     A (CHI[{V, B, I1}, {V, C, I2}]
//  /     \
// /       \
// B(I1)  C (I2)
// The Value number for both I1 and I2 is V, the CHI node will save the
// instruction as well as the edge where the value is flowing to.
struct CHIArg { … };

CHIIt;
CHIArgs;
OutValuesType;
InValuesType;

// An invalid value number Used when inserting a single value number into
// VNtoInsns.
enum : uintptr_t { … };

// Records all scalar instructions candidate for code hoisting.
class InsnInfo { … };

// Records all load instructions candidate for code hoisting.
class LoadInfo { … };

// Records all store instructions candidate for code hoisting.
class StoreInfo { … };

// Records all call instructions candidate for code hoisting.
class CallInfo { … };

// This pass hoists common computations across branches sharing common
// dominator. The primary goal is to reduce the code size, and in some
// cases reduce critical path (by exposing more ILP).
class GVNHoist { … };

bool GVNHoist::run(Function &F) { … }

unsigned int GVNHoist::rank(const Value *V) const { … }

bool GVNHoist::hasEH(const BasicBlock *BB) { … }

bool GVNHoist::hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
                            const BasicBlock *BB) { … }

bool GVNHoist::hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,
                           int &NBBsOnAllPaths) { … }

bool GVNHoist::hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
                                  int &NBBsOnAllPaths) { … }

bool GVNHoist::hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,
                           int &NBBsOnAllPaths) { … }

bool GVNHoist::safeToHoistLdSt(const Instruction *NewPt,
                               const Instruction *OldPt, MemoryUseOrDef *U,
                               GVNHoist::InsKind K, int &NBBsOnAllPaths) { … }

bool GVNHoist::valueAnticipable(CHIArgs C, Instruction *TI) const { … }

void GVNHoist::checkSafety(CHIArgs C, BasicBlock *BB, GVNHoist::InsKind K,
                           SmallVectorImpl<CHIArg> &Safe) { … }

void GVNHoist::fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
                               GVNHoist::RenameStackType &RenameStack) { … }

void GVNHoist::fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
                           GVNHoist::RenameStackType &RenameStack) { … }

void GVNHoist::findHoistableCandidates(OutValuesType &CHIBBs,
                                       GVNHoist::InsKind K,
                                       HoistingPointList &HPL) { … }

bool GVNHoist::allOperandsAvailable(const Instruction *I,
                                    const BasicBlock *HoistPt) const { … }

bool GVNHoist::allGepOperandsAvailable(const Instruction *I,
                                       const BasicBlock *HoistPt) const { … }

void GVNHoist::makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
                                 const SmallVecInsn &InstructionsToHoist,
                                 Instruction *Gep) const { … }

void GVNHoist::updateAlignment(Instruction *I, Instruction *Repl) { … }

unsigned GVNHoist::rauw(const SmallVecInsn &Candidates, Instruction *Repl,
                        MemoryUseOrDef *NewMemAcc) { … }

void GVNHoist::raMPHIuw(MemoryUseOrDef *NewMemAcc) { … }

unsigned GVNHoist::removeAndReplace(const SmallVecInsn &Candidates,
                                    Instruction *Repl, BasicBlock *DestBB,
                                    bool MoveAccess) { … }

bool GVNHoist::makeGepOperandsAvailable(
    Instruction *Repl, BasicBlock *HoistPt,
    const SmallVecInsn &InstructionsToHoist) const { … }

std::pair<unsigned, unsigned> GVNHoist::hoist(HoistingPointList &HPL) { … }

std::pair<unsigned, unsigned> GVNHoist::hoistExpressions(Function &F) { … }

} // end namespace llvm

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