HexagonCommonGEP.cpp | Explore in Territory

//===- HexagonCommonGEP.cpp -----------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/Verifier.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <map>
#include <set>
#include <utility>
#include <vector>

#define DEBUG_TYPE …

usingnamespacellvm;

static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true),
                                  cl::Hidden);

static cl::opt<bool> OptEnableInv("commgep-inv", cl::init(true), cl::Hidden);

static cl::opt<bool> OptEnableConst("commgep-const", cl::init(true),
                                    cl::Hidden);

namespace llvm {

  void initializeHexagonCommonGEPPass(PassRegistry&);

} // end namespace llvm

namespace {

  struct GepNode;
  NodeSet;
  NodeToValueMap;
  NodeVect;
  NodeChildrenMap;
  UseSet;
  NodeToUsesMap;

  // Numbering map for gep nodes. Used to keep track of ordering for
  // gep nodes.
  struct NodeOrdering { … };

  class HexagonCommonGEP : public FunctionPass { … };

} // end anonymous namespace

char HexagonCommonGEP::ID = …;

INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
      false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
      false, false)

namespace {

  struct GepNode { … };

  raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN) { … }

  template <typename NodeContainer>
  void dump_node_container(raw_ostream &OS, const NodeContainer &S) { … }

  raw_ostream &operator<< (raw_ostream &OS,
                           const NodeVect &S) LLVM_ATTRIBUTE_UNUSED;
  raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) { … }

  raw_ostream &operator<< (raw_ostream &OS,
                           const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED;
  raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){ … }

  struct in_set { … };

} // end anonymous namespace

inline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) { … }

void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
      ValueVect &Order) { … }

bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) { … }

void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,
      ValueToNodeMap &NM) { … }

void HexagonCommonGEP::collect() { … }

static void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM,
                              NodeVect &Roots) { … }

static void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM,
                           NodeSet &Nodes) { … }

namespace {

  NodeSymRel;
  NodePair;
  NodePairSet;

} // end anonymous namespace

static const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) { … }

  // Create an ordered pair of GepNode pointers. The pair will be used in
  // determining equality. The only purpose of the ordering is to eliminate
  // duplication due to the commutativity of equality/non-equality.
static NodePair node_pair(GepNode *N1, GepNode *N2) { … }

static unsigned node_hash(GepNode *N) { … }

static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq,
                    NodePairSet &Ne) { … }

void HexagonCommonGEP::common() { … }

template <typename T>
static BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) { … }

template <typename T>
static BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) { … }

// Find the first use in B of any value from Values. If no such use,
// return B->end().
template <typename T>
static BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B) { … }

static bool is_empty(const BasicBlock *B) { … }

BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
      NodeChildrenMap &NCM, NodeToValueMap &Loc) { … }

BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
      NodeChildrenMap &NCM, NodeToValueMap &Loc) { … }

bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) { … }

bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) { … }

bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) { … }

static BasicBlock *preheader(DominatorTree *DT, Loop *L) { … }

BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
      NodeChildrenMap &NCM, NodeToValueMap &Loc) { … }

namespace {

  struct LocationAsBlock { … };

  raw_ostream &operator<< (raw_ostream &OS,
                           const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ;
  raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) { … }

  inline bool is_constant(GepNode *N) { … }

} // end anonymous namespace

void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
      NodeToValueMap &Loc) { … }

void HexagonCommonGEP::separateConstantChains(GepNode *Node,
      NodeChildrenMap &NCM, NodeToValueMap &Loc) { … }

void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) { … }

Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
      BasicBlock *LocB) { … }

void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
      NodeChildrenMap &NCM) { … }

void HexagonCommonGEP::materialize(NodeToValueMap &Loc) { … }

void HexagonCommonGEP::removeDeadCode() { … }

bool HexagonCommonGEP::runOnFunction(Function &F) { … }

namespace llvm {

  FunctionPass *createHexagonCommonGEP() { … }

} // end namespace llvm
llvm/llvm/lib/Target/Hexagon/HexagonCommonGEP.cpp
