HexagonStoreWidening.cpp | Explore in Territory

//===- HexagonStoreWidening.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
//
//===----------------------------------------------------------------------===//
// Replace sequences of "narrow" stores to adjacent memory locations with
// a fewer "wide" stores that have the same effect.
// For example, replace:
//   S4_storeirb_io  %100, 0, 0   ; store-immediate-byte
//   S4_storeirb_io  %100, 1, 0   ; store-immediate-byte
// with
//   S4_storeirh_io  %100, 0, 0   ; store-immediate-halfword
// The above is the general idea.  The actual cases handled by the code
// may be a bit more complex.
// The purpose of this pass is to reduce the number of outstanding stores,
// or as one could say, "reduce store queue pressure".  Also, wide stores
// mean fewer stores, and since there are only two memory instructions allowed
// per packet, it also means fewer packets, and ultimately fewer cycles.
//===---------------------------------------------------------------------===//

#include "HexagonInstrInfo.h"
#include "HexagonRegisterInfo.h"
#include "HexagonSubtarget.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <vector>

#define DEBUG_TYPE …

usingnamespacellvm;

namespace llvm {

FunctionPass *createHexagonStoreWidening();
void initializeHexagonStoreWideningPass(PassRegistry&);

} // end namespace llvm

namespace {

  struct HexagonStoreWidening : public MachineFunctionPass { … };

} // end anonymous namespace

char HexagonStoreWidening::ID = …;

INITIALIZE_PASS_BEGIN(HexagonStoreWidening, "hexagon-widen-stores",
                "Hexason Store Widening", false, false)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(HexagonStoreWidening, "hexagon-widen-stores",
                "Hexagon Store Widening", false, false)

// Some local helper functions...
static unsigned getBaseAddressRegister(const MachineInstr *MI) { … }

static int64_t getStoreOffset(const MachineInstr *MI) { … }

static const MachineMemOperand &getStoreTarget(const MachineInstr *MI) { … }

// Filtering function: any stores whose opcodes are not "approved" of by
// this function will not be subjected to widening.
inline bool HexagonStoreWidening::handledStoreType(const MachineInstr *MI) { … }

// Check if the machine memory operand MMO is aliased with any of the
// stores in the store group Stores.
bool HexagonStoreWidening::instrAliased(InstrGroup &Stores,
      const MachineMemOperand &MMO) { … }

// Check if the machine instruction MI accesses any storage aliased with
// any store in the group Stores.
bool HexagonStoreWidening::instrAliased(InstrGroup &Stores,
      const MachineInstr *MI) { … }

// Inspect a machine basic block, and generate store groups out of stores
// encountered in the block.
//
// A store group is a group of stores that use the same base register,
// and which can be reordered within that group without altering the
// semantics of the program.  A single store group could be widened as
// a whole, if there existed a single store instruction with the same
// semantics as the entire group.  In many cases, a single store group
// may need more than one wide store.
void HexagonStoreWidening::createStoreGroups(MachineBasicBlock &MBB,
      InstrGroupList &StoreGroups) { … }

// Create a single store group.  The stores need to be independent between
// themselves, and also there cannot be other instructions between them
// that could read or modify storage being stored into.
void HexagonStoreWidening::createStoreGroup(MachineInstr *BaseStore,
      InstrGroup::iterator Begin, InstrGroup::iterator End, InstrGroup &Group) { … }

// Check if store instructions S1 and S2 are adjacent.  More precisely,
// S2 has to access memory immediately following that accessed by S1.
bool HexagonStoreWidening::storesAreAdjacent(const MachineInstr *S1,
      const MachineInstr *S2) { … }

/// Given a sequence of adjacent stores, and a maximum size of a single wide
/// store, pick a group of stores that  can be replaced by a single store
/// of size not exceeding MaxSize.  The selected sequence will be recorded
/// in OG ("old group" of instructions).
/// OG should be empty on entry, and should be left empty if the function
/// fails.
bool HexagonStoreWidening::selectStores(InstrGroup::iterator Begin,
      InstrGroup::iterator End, InstrGroup &OG, unsigned &TotalSize,
      unsigned MaxSize) { … }

/// Given an "old group" OG of stores, create a "new group" NG of instructions
/// to replace them.  Ideally, NG would only have a single instruction in it,
/// but that may only be possible for store-immediate.
bool HexagonStoreWidening::createWideStores(InstrGroup &OG, InstrGroup &NG,
      unsigned TotalSize) { … }

// Replace instructions from the old group OG with instructions from the
// new group NG.  Conceptually, remove all instructions in OG, and then
// insert all instructions in NG, starting at where the first instruction
// from OG was (in the order in which they appeared in the basic block).
// (The ordering in OG does not have to match the order in the basic block.)
bool HexagonStoreWidening::replaceStores(InstrGroup &OG, InstrGroup &NG) { … }

// Break up the group into smaller groups, each of which can be replaced by
// a single wide store.  Widen each such smaller group and replace the old
// instructions with the widened ones.
bool HexagonStoreWidening::processStoreGroup(InstrGroup &Group) { … }

// Process a single basic block: create the store groups, and replace them
// with the widened stores, if possible.  Processing of each basic block
// is independent from processing of any other basic block.  This transfor-
// mation could be stopped after having processed any basic block without
// any ill effects (other than not having performed widening in the unpro-
// cessed blocks).  Also, the basic blocks can be processed in any order.
bool HexagonStoreWidening::processBasicBlock(MachineBasicBlock &MBB) { … }

bool HexagonStoreWidening::runOnMachineFunction(MachineFunction &MFn) { … }

FunctionPass *llvm::createHexagonStoreWidening() { … }
llvm/llvm/lib/Target/Hexagon/HexagonStoreWidening.cpp
