FastISel.cpp | Explore in Territory

//===- FastISel.cpp - Implementation of the FastISel class ----------------===//
//
// 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 file contains the implementation of the FastISel class.
//
// "Fast" instruction selection is designed to emit very poor code quickly.
// Also, it is not designed to be able to do much lowering, so most illegal
// types (e.g. i64 on 32-bit targets) and operations are not supported.  It is
// also not intended to be able to do much optimization, except in a few cases
// where doing optimizations reduces overall compile time.  For example, folding
// constants into immediate fields is often done, because it's cheap and it
// reduces the number of instructions later phases have to examine.
//
// "Fast" instruction selection is able to fail gracefully and transfer
// control to the SelectionDAG selector for operations that it doesn't
// support.  In many cases, this allows us to avoid duplicating a lot of
// the complicated lowering logic that SelectionDAG currently has.
//
// The intended use for "fast" instruction selection is "-O0" mode
// compilation, where the quality of the generated code is irrelevant when
// weighed against the speed at which the code can be generated.  Also,
// at -O0, the LLVM optimizers are not running, and this makes the
// compile time of codegen a much higher portion of the overall compile
// time.  Despite its limitations, "fast" instruction selection is able to
// handle enough code on its own to provide noticeable overall speedups
// in -O0 compiles.
//
// Basic operations are supported in a target-independent way, by reading
// the same instruction descriptions that the SelectionDAG selector reads,
// and identifying simple arithmetic operations that can be directly selected
// from simple operators.  More complicated operations currently require
// target-specific code.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/FastISel.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/APSInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/CodeGen/Analysis.h"
#include "llvm/CodeGen/FunctionLoweringInfo.h"
#include "llvm/CodeGen/ISDOpcodes.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/StackMaps.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGen/ValueTypes.h"
#include "llvm/CodeGenTypes/MachineValueType.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallingConv.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Mangler.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/MC/MCContext.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <optional>
#include <utility>

usingnamespacellvm;
usingnamespacePatternMatch;

#define DEBUG_TYPE …

STATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by "
                                         "target-independent selector");
STATISTIC(NumFastIselSuccessTarget, "Number of insts selected by "
                                    "target-specific selector");
STATISTIC(NumFastIselDead, "Number of dead insts removed on failure");

/// Set the current block to which generated machine instructions will be
/// appended.
void FastISel::startNewBlock() { … }

void FastISel::finishBasicBlock() { … }

bool FastISel::lowerArguments() { … }

/// Return the defined register if this instruction defines exactly one
/// virtual register and uses no other virtual registers. Otherwise return 0.
static Register findLocalRegDef(MachineInstr &MI) { … }

static bool isRegUsedByPhiNodes(Register DefReg,
                                FunctionLoweringInfo &FuncInfo) { … }

void FastISel::flushLocalValueMap() { … }

Register FastISel::getRegForValue(const Value *V) { … }

Register FastISel::materializeConstant(const Value *V, MVT VT) { … }

/// Helper for getRegForValue. This function is called when the value isn't
/// already available in a register and must be materialized with new
/// instructions.
Register FastISel::materializeRegForValue(const Value *V, MVT VT) { … }

Register FastISel::lookUpRegForValue(const Value *V) { … }

void FastISel::updateValueMap(const Value *I, Register Reg, unsigned NumRegs) { … }

Register FastISel::getRegForGEPIndex(const Value *Idx) { … }

void FastISel::recomputeInsertPt() { … }

void FastISel::removeDeadCode(MachineBasicBlock::iterator I,
                              MachineBasicBlock::iterator E) { … }

FastISel::SavePoint FastISel::enterLocalValueArea() { … }

void FastISel::leaveLocalValueArea(SavePoint OldInsertPt) { … }

bool FastISel::selectBinaryOp(const User *I, unsigned ISDOpcode) { … }

bool FastISel::selectGetElementPtr(const User *I) { … }

bool FastISel::addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
                                   const CallInst *CI, unsigned StartIdx) { … }

bool FastISel::selectStackmap(const CallInst *I) { … }

/// Lower an argument list according to the target calling convention.
///
/// This is a helper for lowering intrinsics that follow a target calling
/// convention or require stack pointer adjustment. Only a subset of the
/// intrinsic's operands need to participate in the calling convention.
bool FastISel::lowerCallOperands(const CallInst *CI, unsigned ArgIdx,
                                 unsigned NumArgs, const Value *Callee,
                                 bool ForceRetVoidTy, CallLoweringInfo &CLI) { … }

FastISel::CallLoweringInfo &FastISel::CallLoweringInfo::setCallee(
    const DataLayout &DL, MCContext &Ctx, CallingConv::ID CC, Type *ResultTy,
    StringRef Target, ArgListTy &&ArgsList, unsigned FixedArgs) { … }

bool FastISel::selectPatchpoint(const CallInst *I) { … }

bool FastISel::selectXRayCustomEvent(const CallInst *I) { … }

bool FastISel::selectXRayTypedEvent(const CallInst *I) { … }

/// Returns an AttributeList representing the attributes applied to the return
/// value of the given call.
static AttributeList getReturnAttrs(FastISel::CallLoweringInfo &CLI) { … }

bool FastISel::lowerCallTo(const CallInst *CI, const char *SymName,
                           unsigned NumArgs) { … }

bool FastISel::lowerCallTo(const CallInst *CI, MCSymbol *Symbol,
                           unsigned NumArgs) { … }

bool FastISel::lowerCallTo(CallLoweringInfo &CLI) { … }

bool FastISel::lowerCall(const CallInst *CI) { … }

bool FastISel::selectCall(const User *I) { … }

void FastISel::handleDbgInfo(const Instruction *II) { … }

bool FastISel::lowerDbgValue(const Value *V, DIExpression *Expr,
                             DILocalVariable *Var, const DebugLoc &DL) { … }

bool FastISel::lowerDbgDeclare(const Value *Address, DIExpression *Expr,
                               DILocalVariable *Var, const DebugLoc &DL) { … }

bool FastISel::selectIntrinsicCall(const IntrinsicInst *II) { … }

bool FastISel::selectCast(const User *I, unsigned Opcode) { … }

bool FastISel::selectBitCast(const User *I) { … }

bool FastISel::selectFreeze(const User *I) { … }

// Remove local value instructions starting from the instruction after
// SavedLastLocalValue to the current function insert point.
void FastISel::removeDeadLocalValueCode(MachineInstr *SavedLastLocalValue)
{ … }

bool FastISel::selectInstruction(const Instruction *I) { … }

/// Emit an unconditional branch to the given block, unless it is the immediate
/// (fall-through) successor, and update the CFG.
void FastISel::fastEmitBranch(MachineBasicBlock *MSucc,
                              const DebugLoc &DbgLoc) { … }

void FastISel::finishCondBranch(const BasicBlock *BranchBB,
                                MachineBasicBlock *TrueMBB,
                                MachineBasicBlock *FalseMBB) { … }

/// Emit an FNeg operation.
bool FastISel::selectFNeg(const User *I, const Value *In) { … }

bool FastISel::selectExtractValue(const User *U) { … }

bool FastISel::selectOperator(const User *I, unsigned Opcode) { … }

FastISel::FastISel(FunctionLoweringInfo &FuncInfo,
                   const TargetLibraryInfo *LibInfo,
                   bool SkipTargetIndependentISel)
    : … { … }

FastISel::~FastISel() = default;

bool FastISel::fastLowerArguments() { … }

bool FastISel::fastLowerCall(CallLoweringInfo & /*CLI*/) { … }

bool FastISel::fastLowerIntrinsicCall(const IntrinsicInst * /*II*/) { … }

unsigned FastISel::fastEmit_(MVT, MVT, unsigned) { … }

unsigned FastISel::fastEmit_r(MVT, MVT, unsigned, unsigned /*Op0*/) { … }

unsigned FastISel::fastEmit_rr(MVT, MVT, unsigned, unsigned /*Op0*/,
                               unsigned /*Op1*/) { … }

unsigned FastISel::fastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) { … }

unsigned FastISel::fastEmit_f(MVT, MVT, unsigned,
                              const ConstantFP * /*FPImm*/) { … }

unsigned FastISel::fastEmit_ri(MVT, MVT, unsigned, unsigned /*Op0*/,
                               uint64_t /*Imm*/) { … }

/// This method is a wrapper of fastEmit_ri. It first tries to emit an
/// instruction with an immediate operand using fastEmit_ri.
/// If that fails, it materializes the immediate into a register and try
/// fastEmit_rr instead.
Register FastISel::fastEmit_ri_(MVT VT, unsigned Opcode, unsigned Op0,
                                uint64_t Imm, MVT ImmType) { … }

Register FastISel::createResultReg(const TargetRegisterClass *RC) { … }

Register FastISel::constrainOperandRegClass(const MCInstrDesc &II, Register Op,
                                            unsigned OpNum) { … }

Register FastISel::fastEmitInst_(unsigned MachineInstOpcode,
                                 const TargetRegisterClass *RC) { … }

Register FastISel::fastEmitInst_r(unsigned MachineInstOpcode,
                                  const TargetRegisterClass *RC, unsigned Op0) { … }

Register FastISel::fastEmitInst_rr(unsigned MachineInstOpcode,
                                   const TargetRegisterClass *RC, unsigned Op0,
                                   unsigned Op1) { … }

Register FastISel::fastEmitInst_rrr(unsigned MachineInstOpcode,
                                    const TargetRegisterClass *RC, unsigned Op0,
                                    unsigned Op1, unsigned Op2) { … }

Register FastISel::fastEmitInst_ri(unsigned MachineInstOpcode,
                                   const TargetRegisterClass *RC, unsigned Op0,
                                   uint64_t Imm) { … }

Register FastISel::fastEmitInst_rii(unsigned MachineInstOpcode,
                                    const TargetRegisterClass *RC, unsigned Op0,
                                    uint64_t Imm1, uint64_t Imm2) { … }

Register FastISel::fastEmitInst_f(unsigned MachineInstOpcode,
                                  const TargetRegisterClass *RC,
                                  const ConstantFP *FPImm) { … }

Register FastISel::fastEmitInst_rri(unsigned MachineInstOpcode,
                                    const TargetRegisterClass *RC, unsigned Op0,
                                    unsigned Op1, uint64_t Imm) { … }

Register FastISel::fastEmitInst_i(unsigned MachineInstOpcode,
                                  const TargetRegisterClass *RC, uint64_t Imm) { … }

Register FastISel::fastEmitInst_extractsubreg(MVT RetVT, unsigned Op0,
                                              uint32_t Idx) { … }

/// Emit MachineInstrs to compute the value of Op with all but the least
/// significant bit set to zero.
Register FastISel::fastEmitZExtFromI1(MVT VT, unsigned Op0) { … }

/// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
/// Emit code to ensure constants are copied into registers when needed.
/// Remember the virtual registers that need to be added to the Machine PHI
/// nodes as input.  We cannot just directly add them, because expansion
/// might result in multiple MBB's for one BB.  As such, the start of the
/// BB might correspond to a different MBB than the end.
bool FastISel::handlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) { … }

bool FastISel::tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst) { … }

bool FastISel::canFoldAddIntoGEP(const User *GEP, const Value *Add) { … }

MachineMemOperand *
FastISel::createMachineMemOperandFor(const Instruction *I) const { … }

CmpInst::Predicate FastISel::optimizeCmpPredicate(const CmpInst *CI) const { … }
llvm/llvm/lib/CodeGen/SelectionDAG/FastISel.cpp
