//===- TwoAddressInstructionPass.cpp - Two-Address instruction pass -------===// // // 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 implements the TwoAddress instruction pass which is used // by most register allocators. Two-Address instructions are rewritten // from: // // A = B op C // // to: // // A = B // A op= C // // Note that if a register allocator chooses to use this pass, that it // has to be capable of handling the non-SSA nature of these rewritten // virtual registers. // // It is also worth noting that the duplicate operand of the two // address instruction is removed. // //===----------------------------------------------------------------------===// #include "llvm/CodeGen/TwoAddressInstructionPass.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveInterval.h" #include "llvm/CodeGen/LiveIntervals.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/SlotIndexes.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetOpcodes.h" #include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/MC/MCInstrDesc.h" #include "llvm/Pass.h" #include "llvm/Support/CodeGen.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetMachine.h" #include <cassert> #include <iterator> #include <utility> usingnamespacellvm; #define DEBUG_TYPE … STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted"); STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up"); STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down"); // Temporary flag to disable rescheduling. static cl::opt<bool> EnableRescheduling("twoaddr-reschedule", cl::desc("Coalesce copies by rescheduling (default=true)"), cl::init(true), cl::Hidden); // Limit the number of dataflow edges to traverse when evaluating the benefit // of commuting operands. static cl::opt<unsigned> MaxDataFlowEdge( "dataflow-edge-limit", cl::Hidden, cl::init(3), cl::desc("Maximum number of dataflow edges to traverse when evaluating " "the benefit of commuting operands")); namespace { class TwoAddressInstructionImpl { … }; class TwoAddressInstructionLegacyPass : public MachineFunctionPass { … }; } // end anonymous namespace PreservedAnalyses TwoAddressInstructionPass::run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM) { … } char TwoAddressInstructionLegacyPass::ID = …; char &llvm::TwoAddressInstructionPassID = …; INITIALIZE_PASS_BEGIN(TwoAddressInstructionLegacyPass, DEBUG_TYPE, "Two-Address instruction pass", false, false) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_END(TwoAddressInstructionLegacyPass, DEBUG_TYPE, "Two-Address instruction pass", false, false) TwoAddressInstructionImpl::TwoAddressInstructionImpl( MachineFunction &Func, MachineFunctionAnalysisManager &MFAM) : … { … } TwoAddressInstructionImpl::TwoAddressInstructionImpl(MachineFunction &Func, MachineFunctionPass *P) : … { … } /// Return the MachineInstr* if it is the single def of the Reg in current BB. MachineInstr * TwoAddressInstructionImpl::getSingleDef(Register Reg, MachineBasicBlock *BB) const { … } /// Check if there is a reversed copy chain from FromReg to ToReg: /// %Tmp1 = copy %Tmp2; /// %FromReg = copy %Tmp1; /// %ToReg = add %FromReg ... /// %Tmp2 = copy %ToReg; /// MaxLen specifies the maximum length of the copy chain the func /// can walk through. bool TwoAddressInstructionImpl::isRevCopyChain(Register FromReg, Register ToReg, int Maxlen) { … } /// Return true if there are no intervening uses between the last instruction /// in the MBB that defines the specified register and the two-address /// instruction which is being processed. It also returns the last def location /// by reference. bool TwoAddressInstructionImpl::noUseAfterLastDef(Register Reg, unsigned Dist, unsigned &LastDef) { … } /// Return true if the specified MI is a copy instruction or an extract_subreg /// instruction. It also returns the source and destination registers and /// whether they are physical registers by reference. bool TwoAddressInstructionImpl::isCopyToReg(MachineInstr &MI, Register &SrcReg, Register &DstReg, bool &IsSrcPhys, bool &IsDstPhys) const { … } bool TwoAddressInstructionImpl::isPlainlyKilled(const MachineInstr *MI, LiveRange &LR) const { … } /// Test if the given register value, which is used by the /// given instruction, is killed by the given instruction. bool TwoAddressInstructionImpl::isPlainlyKilled(const MachineInstr *MI, Register Reg) const { … } /// Test if the register used by the given operand is killed by the operand's /// instruction. bool TwoAddressInstructionImpl::isPlainlyKilled( const MachineOperand &MO) const { … } /// Test if the given register value, which is used by the given /// instruction, is killed by the given instruction. This looks through /// coalescable copies to see if the original value is potentially not killed. /// /// For example, in this code: /// /// %reg1034 = copy %reg1024 /// %reg1035 = copy killed %reg1025 /// %reg1036 = add killed %reg1034, killed %reg1035 /// /// %reg1034 is not considered to be killed, since it is copied from a /// register which is not killed. Treating it as not killed lets the /// normal heuristics commute the (two-address) add, which lets /// coalescing eliminate the extra copy. /// /// If allowFalsePositives is true then likely kills are treated as kills even /// if it can't be proven that they are kills. bool TwoAddressInstructionImpl::isKilled(MachineInstr &MI, Register Reg, bool allowFalsePositives) const { … } /// Return true if the specified MI uses the specified register as a two-address /// use. If so, return the destination register by reference. static bool isTwoAddrUse(MachineInstr &MI, Register Reg, Register &DstReg) { … } /// Given a register, if all its uses are in the same basic block, return the /// last use instruction if it's a copy or a two-address use. MachineInstr *TwoAddressInstructionImpl::findOnlyInterestingUse( Register Reg, MachineBasicBlock *MBB, bool &IsCopy, Register &DstReg, bool &IsDstPhys) const { … } /// Return the physical register the specified virtual register might be mapped /// to. static MCRegister getMappedReg(Register Reg, DenseMap<Register, Register> &RegMap) { … } /// Return true if the two registers are equal or aliased. bool TwoAddressInstructionImpl::regsAreCompatible(Register RegA, Register RegB) const { … } /// From RegMap remove entries mapped to a physical register which overlaps MO. void TwoAddressInstructionImpl::removeMapRegEntry( const MachineOperand &MO, DenseMap<Register, Register> &RegMap) const { … } /// If a physical register is clobbered, old entries mapped to it should be /// deleted. For example /// /// %2:gr64 = COPY killed $rdx /// MUL64r %3:gr64, implicit-def $rax, implicit-def $rdx /// /// After the MUL instruction, $rdx contains different value than in the COPY /// instruction. So %2 should not map to $rdx after MUL. void TwoAddressInstructionImpl::removeClobberedSrcRegMap(MachineInstr *MI) { … } // Returns true if Reg is equal or aliased to at least one register in Set. bool TwoAddressInstructionImpl::regOverlapsSet( const SmallVectorImpl<Register> &Set, Register Reg) const { … } /// Return true if it's potentially profitable to commute the two-address /// instruction that's being processed. bool TwoAddressInstructionImpl::isProfitableToCommute(Register RegA, Register RegB, Register RegC, MachineInstr *MI, unsigned Dist) { … } /// Commute a two-address instruction and update the basic block, distance map, /// and live variables if needed. Return true if it is successful. bool TwoAddressInstructionImpl::commuteInstruction(MachineInstr *MI, unsigned DstIdx, unsigned RegBIdx, unsigned RegCIdx, unsigned Dist) { … } /// Return true if it is profitable to convert the given 2-address instruction /// to a 3-address one. bool TwoAddressInstructionImpl::isProfitableToConv3Addr(Register RegA, Register RegB) { … } /// Convert the specified two-address instruction into a three address one. /// Return true if this transformation was successful. bool TwoAddressInstructionImpl::convertInstTo3Addr( MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, Register RegA, Register RegB, unsigned &Dist) { … } /// Scan forward recursively for only uses, update maps if the use is a copy or /// a two-address instruction. void TwoAddressInstructionImpl::scanUses(Register DstReg) { … } /// If the specified instruction is not yet processed, process it if it's a /// copy. For a copy instruction, we find the physical registers the /// source and destination registers might be mapped to. These are kept in /// point-to maps used to determine future optimizations. e.g. /// v1024 = mov r0 /// v1025 = mov r1 /// v1026 = add v1024, v1025 /// r1 = mov r1026 /// If 'add' is a two-address instruction, v1024, v1026 are both potentially /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is /// potentially joined with r1 on the output side. It's worthwhile to commute /// 'add' to eliminate a copy. void TwoAddressInstructionImpl::processCopy(MachineInstr *MI) { … } /// If there is one more local instruction that reads 'Reg' and it kills 'Reg, /// consider moving the instruction below the kill instruction in order to /// eliminate the need for the copy. bool TwoAddressInstructionImpl::rescheduleMIBelowKill( MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, Register Reg) { … } /// Return true if the re-scheduling will put the given instruction too close /// to the defs of its register dependencies. bool TwoAddressInstructionImpl::isDefTooClose(Register Reg, unsigned Dist, MachineInstr *MI) { … } /// If there is one more local instruction that reads 'Reg' and it kills 'Reg, /// consider moving the kill instruction above the current two-address /// instruction in order to eliminate the need for the copy. bool TwoAddressInstructionImpl::rescheduleKillAboveMI( MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, Register Reg) { … } /// Tries to commute the operand 'BaseOpIdx' and some other operand in the /// given machine instruction to improve opportunities for coalescing and /// elimination of a register to register copy. /// /// 'DstOpIdx' specifies the index of MI def operand. /// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx' /// operand is killed by the given instruction. /// The 'Dist' arguments provides the distance of MI from the start of the /// current basic block and it is used to determine if it is profitable /// to commute operands in the instruction. /// /// Returns true if the transformation happened. Otherwise, returns false. bool TwoAddressInstructionImpl::tryInstructionCommute(MachineInstr *MI, unsigned DstOpIdx, unsigned BaseOpIdx, bool BaseOpKilled, unsigned Dist) { … } /// For the case where an instruction has a single pair of tied register /// operands, attempt some transformations that may either eliminate the tied /// operands or improve the opportunities for coalescing away the register copy. /// Returns true if no copy needs to be inserted to untie mi's operands /// (either because they were untied, or because mi was rescheduled, and will /// be visited again later). If the shouldOnlyCommute flag is true, only /// instruction commutation is attempted. bool TwoAddressInstructionImpl::tryInstructionTransform( MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, unsigned SrcIdx, unsigned DstIdx, unsigned &Dist, bool shouldOnlyCommute) { … } // Collect tied operands of MI that need to be handled. // Rewrite trivial cases immediately. // Return true if any tied operands where found, including the trivial ones. bool TwoAddressInstructionImpl::collectTiedOperands( MachineInstr *MI, TiedOperandMap &TiedOperands) { … } // Process a list of tied MI operands that all use the same source register. // The tied pairs are of the form (SrcIdx, DstIdx). void TwoAddressInstructionImpl::processTiedPairs(MachineInstr *MI, TiedPairList &TiedPairs, unsigned &Dist) { … } // For every tied operand pair this function transforms statepoint from // RegA = STATEPOINT ... RegB(tied-def N) // to // RegB = STATEPOINT ... RegB(tied-def N) // and replaces all uses of RegA with RegB. // No extra COPY instruction is necessary because tied use is killed at // STATEPOINT. bool TwoAddressInstructionImpl::processStatepoint( MachineInstr *MI, TiedOperandMap &TiedOperands) { … } /// Reduce two-address instructions to two operands. bool TwoAddressInstructionImpl::run() { … } /// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process. /// /// The instruction is turned into a sequence of sub-register copies: /// /// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1 /// /// Becomes: /// /// undef %dst:ssub0 = COPY %v1 /// %dst:ssub1 = COPY %v2 void TwoAddressInstructionImpl::eliminateRegSequence( MachineBasicBlock::iterator &MBBI) { … }
Codebase Browser
llvm