llvm/llvm/lib/CodeGen/LiveRangeShrink.cpp

//===- LiveRangeShrink.cpp - Move instructions to shrink live range -------===//
//
// 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
//
///===---------------------------------------------------------------------===//
///
/// \file
/// This pass moves instructions close to the definition of its operands to
/// shrink live range of the def instruction. The code motion is limited within
/// the basic block. The moved instruction should have 1 def, and more than one
/// uses, all of which are the only use of the def.
///
///===---------------------------------------------------------------------===//

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <iterator>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumInstrsHoistedToShrinkLiveRange,
          "Number of insructions hoisted to shrink live range.");

namespace {

class LiveRangeShrink : public MachineFunctionPass { … };

} // end anonymous namespace

char LiveRangeShrink::ID = …;

char &llvm::LiveRangeShrinkID = …;

INITIALIZE_PASS(…)

InstOrderMap;

/// Returns \p New if it's dominated by \p Old, otherwise return \p Old.
/// \p M maintains a map from instruction to its dominating order that satisfies
/// M[A] > M[B] guarantees that A is dominated by B.
/// If \p New is not in \p M, return \p Old. Otherwise if \p Old is null, return
/// \p New.
static MachineInstr *FindDominatedInstruction(MachineInstr &New,
                                              MachineInstr *Old,
                                              const InstOrderMap &M) { … }

/// Builds Instruction to its dominating order number map \p M by traversing
/// from instruction \p Start.
static void BuildInstOrderMap(MachineBasicBlock::iterator Start,
                              InstOrderMap &M) { … }

bool LiveRangeShrink::runOnMachineFunction(MachineFunction &MF) { … }