GlobalMerge.cpp | Explore in Territory

//===- GlobalMerge.cpp - Internal globals merging -------------------------===//
//
// 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 merges globals with internal linkage into one. This way all the
// globals which were merged into a biggest one can be addressed using offsets
// from the same base pointer (no need for separate base pointer for each of the
// global). Such a transformation can significantly reduce the register pressure
// when many globals are involved.
//
// For example, consider the code which touches several global variables at
// once:
//
// static int foo[N], bar[N], baz[N];
//
// for (i = 0; i < N; ++i) {
//    foo[i] = bar[i] * baz[i];
// }
//
//  On ARM the addresses of 3 arrays should be kept in the registers, thus
//  this code has quite large register pressure (loop body):
//
//  ldr     r1, [r5], #4
//  ldr     r2, [r6], #4
//  mul     r1, r2, r1
//  str     r1, [r0], #4
//
//  Pass converts the code to something like:
//
//  static struct {
//    int foo[N];
//    int bar[N];
//    int baz[N];
//  } merged;
//
//  for (i = 0; i < N; ++i) {
//    merged.foo[i] = merged.bar[i] * merged.baz[i];
//  }
//
//  and in ARM code this becomes:
//
//  ldr     r0, [r5, #40]
//  ldr     r1, [r5, #80]
//  mul     r0, r1, r0
//  str     r0, [r5], #4
//
//  note that we saved 2 registers here almostly "for free".
//
// However, merging globals can have tradeoffs:
// - it confuses debuggers, tools, and users
// - it makes linker optimizations less useful (order files, LOHs, ...)
// - it forces usage of indexed addressing (which isn't necessarily "free")
// - it can increase register pressure when the uses are disparate enough.
//
// We use heuristics to discover the best global grouping we can (cf cl::opts).
//
// ===---------------------------------------------------------------------===//

#include "llvm/CodeGen/GlobalMerge.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/SectionKind.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLoweringObjectFile.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/TargetParser/Triple.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

// FIXME: This is only useful as a last-resort way to disable the pass.
static cl::opt<bool>
EnableGlobalMerge("enable-global-merge", cl::Hidden,
                  cl::desc("Enable the global merge pass"),
                  cl::init(true));

static cl::opt<unsigned>
GlobalMergeMaxOffset("global-merge-max-offset", cl::Hidden,
                     cl::desc("Set maximum offset for global merge pass"),
                     cl::init(0));

static cl::opt<bool> GlobalMergeGroupByUse(
    "global-merge-group-by-use", cl::Hidden,
    cl::desc("Improve global merge pass to look at uses"), cl::init(true));

static cl::opt<bool> GlobalMergeIgnoreSingleUse(
    "global-merge-ignore-single-use", cl::Hidden,
    cl::desc("Improve global merge pass to ignore globals only used alone"),
    cl::init(true));

static cl::opt<bool>
EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden,
                         cl::desc("Enable global merge pass on constants"),
                         cl::init(false));

// FIXME: this could be a transitional option, and we probably need to remove
// it if only we are sure this optimization could always benefit all targets.
static cl::opt<cl::boolOrDefault>
EnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden,
     cl::desc("Enable global merge pass on external linkage"));

static cl::opt<unsigned>
    GlobalMergeMinDataSize("global-merge-min-data-size",
                           cl::desc("The minimum size in bytes of each global "
                                    "that should considered in merging."),
                           cl::init(0), cl::Hidden);

STATISTIC(NumMerged, "Number of globals merged");

namespace {

class GlobalMergeImpl { … };

class GlobalMerge : public FunctionPass { … };

} // end anonymous namespace

PreservedAnalyses GlobalMergePass::run(Module &M, ModuleAnalysisManager &) { … }

char GlobalMerge::ID = …;

INITIALIZE_PASS(…)

bool GlobalMergeImpl::doMerge(SmallVectorImpl<GlobalVariable *> &Globals,
                              Module &M, bool isConst,
                              unsigned AddrSpace) const { … }

bool GlobalMergeImpl::doMerge(const SmallVectorImpl<GlobalVariable *> &Globals,
                              const BitVector &GlobalSet, Module &M,
                              bool isConst, unsigned AddrSpace) const { … }

void GlobalMergeImpl::collectUsedGlobalVariables(Module &M, StringRef Name) { … }

void GlobalMergeImpl::setMustKeepGlobalVariables(Module &M) { … }

bool GlobalMergeImpl::run(Module &M) { … }

Pass *llvm::createGlobalMergePass(const TargetMachine *TM, unsigned Offset,
                                  bool OnlyOptimizeForSize,
                                  bool MergeExternalByDefault,
                                  bool MergeConstantByDefault) { … }
llvm/llvm/lib/CodeGen/GlobalMerge.cpp
