10b57cec5SDimitry Andric //==-- llvm/CodeGen/ExecutionDomainFix.h - Execution Domain Fix -*- C++ -*--==// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric /// \file Execution Domain Fix pass. 100b57cec5SDimitry Andric /// 110b57cec5SDimitry Andric /// Some X86 SSE instructions like mov, and, or, xor are available in different 120b57cec5SDimitry Andric /// variants for different operand types. These variant instructions are 130b57cec5SDimitry Andric /// equivalent, but on Nehalem and newer cpus there is extra latency 140b57cec5SDimitry Andric /// transferring data between integer and floating point domains. ARM cores 150b57cec5SDimitry Andric /// have similar issues when they are configured with both VFP and NEON 160b57cec5SDimitry Andric /// pipelines. 170b57cec5SDimitry Andric /// 180b57cec5SDimitry Andric /// This pass changes the variant instructions to minimize domain crossings. 190b57cec5SDimitry Andric // 200b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 210b57cec5SDimitry Andric 220b57cec5SDimitry Andric #ifndef LLVM_CODEGEN_EXECUTIONDOMAINFIX_H 230b57cec5SDimitry Andric #define LLVM_CODEGEN_EXECUTIONDOMAINFIX_H 240b57cec5SDimitry Andric 250b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h" 260b57cec5SDimitry Andric #include "llvm/CodeGen/LoopTraversal.h" 270b57cec5SDimitry Andric #include "llvm/CodeGen/MachineFunctionPass.h" 280b57cec5SDimitry Andric #include "llvm/CodeGen/ReachingDefAnalysis.h" 290b57cec5SDimitry Andric #include "llvm/CodeGen/TargetRegisterInfo.h" 300b57cec5SDimitry Andric 310b57cec5SDimitry Andric namespace llvm { 320b57cec5SDimitry Andric 330b57cec5SDimitry Andric class MachineInstr; 340b57cec5SDimitry Andric class TargetInstrInfo; 350b57cec5SDimitry Andric 360b57cec5SDimitry Andric /// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track 370b57cec5SDimitry Andric /// of execution domains. 380b57cec5SDimitry Andric /// 390b57cec5SDimitry Andric /// An open DomainValue represents a set of instructions that can still switch 400b57cec5SDimitry Andric /// execution domain. Multiple registers may refer to the same open 410b57cec5SDimitry Andric /// DomainValue - they will eventually be collapsed to the same execution 420b57cec5SDimitry Andric /// domain. 430b57cec5SDimitry Andric /// 440b57cec5SDimitry Andric /// A collapsed DomainValue represents a single register that has been forced 450b57cec5SDimitry Andric /// into one of more execution domains. There is a separate collapsed 460b57cec5SDimitry Andric /// DomainValue for each register, but it may contain multiple execution 470b57cec5SDimitry Andric /// domains. A register value is initially created in a single execution 480b57cec5SDimitry Andric /// domain, but if we were forced to pay the penalty of a domain crossing, we 490b57cec5SDimitry Andric /// keep track of the fact that the register is now available in multiple 500b57cec5SDimitry Andric /// domains. 510b57cec5SDimitry Andric struct DomainValue { 520b57cec5SDimitry Andric /// Basic reference counting. 530b57cec5SDimitry Andric unsigned Refs = 0; 540b57cec5SDimitry Andric 550b57cec5SDimitry Andric /// Bitmask of available domains. For an open DomainValue, it is the still 560b57cec5SDimitry Andric /// possible domains for collapsing. For a collapsed DomainValue it is the 570b57cec5SDimitry Andric /// domains where the register is available for free. 580b57cec5SDimitry Andric unsigned AvailableDomains; 590b57cec5SDimitry Andric 600b57cec5SDimitry Andric /// Pointer to the next DomainValue in a chain. When two DomainValues are 610b57cec5SDimitry Andric /// merged, Victim.Next is set to point to Victor, so old DomainValue 620b57cec5SDimitry Andric /// references can be updated by following the chain. 630b57cec5SDimitry Andric DomainValue *Next; 640b57cec5SDimitry Andric 650b57cec5SDimitry Andric /// Twiddleable instructions using or defining these registers. 660b57cec5SDimitry Andric SmallVector<MachineInstr *, 8> Instrs; 670b57cec5SDimitry Andric DomainValueDomainValue680b57cec5SDimitry Andric DomainValue() { clear(); } 690b57cec5SDimitry Andric 700b57cec5SDimitry Andric /// A collapsed DomainValue has no instructions to twiddle - it simply keeps 710b57cec5SDimitry Andric /// track of the domains where the registers are already available. isCollapsedDomainValue720b57cec5SDimitry Andric bool isCollapsed() const { return Instrs.empty(); } 730b57cec5SDimitry Andric 740b57cec5SDimitry Andric /// Is domain available? hasDomainDomainValue750b57cec5SDimitry Andric bool hasDomain(unsigned domain) const { 760b57cec5SDimitry Andric assert(domain < 770b57cec5SDimitry Andric static_cast<unsigned>(std::numeric_limits<unsigned>::digits) && 780b57cec5SDimitry Andric "undefined behavior"); 790b57cec5SDimitry Andric return AvailableDomains & (1u << domain); 800b57cec5SDimitry Andric } 810b57cec5SDimitry Andric 820b57cec5SDimitry Andric /// Mark domain as available. addDomainDomainValue835ffd83dbSDimitry Andric void addDomain(unsigned domain) { 845ffd83dbSDimitry Andric assert(domain < 855ffd83dbSDimitry Andric static_cast<unsigned>(std::numeric_limits<unsigned>::digits) && 865ffd83dbSDimitry Andric "undefined behavior"); 875ffd83dbSDimitry Andric AvailableDomains |= 1u << domain; 885ffd83dbSDimitry Andric } 890b57cec5SDimitry Andric 900b57cec5SDimitry Andric // Restrict to a single domain available. setSingleDomainDomainValue915ffd83dbSDimitry Andric void setSingleDomain(unsigned domain) { 925ffd83dbSDimitry Andric assert(domain < 935ffd83dbSDimitry Andric static_cast<unsigned>(std::numeric_limits<unsigned>::digits) && 945ffd83dbSDimitry Andric "undefined behavior"); 955ffd83dbSDimitry Andric AvailableDomains = 1u << domain; 965ffd83dbSDimitry Andric } 970b57cec5SDimitry Andric 980b57cec5SDimitry Andric /// Return bitmask of domains that are available and in mask. getCommonDomainsDomainValue990b57cec5SDimitry Andric unsigned getCommonDomains(unsigned mask) const { 1000b57cec5SDimitry Andric return AvailableDomains & mask; 1010b57cec5SDimitry Andric } 1020b57cec5SDimitry Andric 1030b57cec5SDimitry Andric /// First domain available. getFirstDomainDomainValue1040b57cec5SDimitry Andric unsigned getFirstDomain() const { 10506c3fb27SDimitry Andric return llvm::countr_zero(AvailableDomains); 1060b57cec5SDimitry Andric } 1070b57cec5SDimitry Andric 1080b57cec5SDimitry Andric /// Clear this DomainValue and point to next which has all its data. clearDomainValue1090b57cec5SDimitry Andric void clear() { 1100b57cec5SDimitry Andric AvailableDomains = 0; 1110b57cec5SDimitry Andric Next = nullptr; 1120b57cec5SDimitry Andric Instrs.clear(); 1130b57cec5SDimitry Andric } 1140b57cec5SDimitry Andric }; 1150b57cec5SDimitry Andric 1160b57cec5SDimitry Andric class ExecutionDomainFix : public MachineFunctionPass { 1170b57cec5SDimitry Andric SpecificBumpPtrAllocator<DomainValue> Allocator; 1180b57cec5SDimitry Andric SmallVector<DomainValue *, 16> Avail; 1190b57cec5SDimitry Andric 1200b57cec5SDimitry Andric const TargetRegisterClass *const RC; 12106c3fb27SDimitry Andric MachineFunction *MF = nullptr; 12206c3fb27SDimitry Andric const TargetInstrInfo *TII = nullptr; 12306c3fb27SDimitry Andric const TargetRegisterInfo *TRI = nullptr; 1240b57cec5SDimitry Andric std::vector<SmallVector<int, 1>> AliasMap; 1250b57cec5SDimitry Andric const unsigned NumRegs; 1260b57cec5SDimitry Andric /// Value currently in each register, or NULL when no value is being tracked. 1270b57cec5SDimitry Andric /// This counts as a DomainValue reference. 1280b57cec5SDimitry Andric using LiveRegsDVInfo = std::vector<DomainValue *>; 1290b57cec5SDimitry Andric LiveRegsDVInfo LiveRegs; 1300b57cec5SDimitry Andric /// Keeps domain information for all registers. Note that this 1310b57cec5SDimitry Andric /// is different from the usual definition notion of liveness. The CPU 1320b57cec5SDimitry Andric /// doesn't care whether or not we consider a register killed. 1330b57cec5SDimitry Andric using OutRegsInfoMap = SmallVector<LiveRegsDVInfo, 4>; 1340b57cec5SDimitry Andric OutRegsInfoMap MBBOutRegsInfos; 1350b57cec5SDimitry Andric 13606c3fb27SDimitry Andric ReachingDefAnalysis *RDA = nullptr; 1370b57cec5SDimitry Andric 1380b57cec5SDimitry Andric public: ExecutionDomainFix(char & PassID,const TargetRegisterClass & RC)1390b57cec5SDimitry Andric ExecutionDomainFix(char &PassID, const TargetRegisterClass &RC) 1400b57cec5SDimitry Andric : MachineFunctionPass(PassID), RC(&RC), NumRegs(RC.getNumRegs()) {} 1410b57cec5SDimitry Andric getAnalysisUsage(AnalysisUsage & AU)1420b57cec5SDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override { 1430b57cec5SDimitry Andric AU.setPreservesAll(); 1440b57cec5SDimitry Andric AU.addRequired<ReachingDefAnalysis>(); 1450b57cec5SDimitry Andric MachineFunctionPass::getAnalysisUsage(AU); 1460b57cec5SDimitry Andric } 1470b57cec5SDimitry Andric 1480b57cec5SDimitry Andric bool runOnMachineFunction(MachineFunction &MF) override; 1490b57cec5SDimitry Andric getRequiredProperties()1500b57cec5SDimitry Andric MachineFunctionProperties getRequiredProperties() const override { 1510b57cec5SDimitry Andric return MachineFunctionProperties().set( 1520b57cec5SDimitry Andric MachineFunctionProperties::Property::NoVRegs); 1530b57cec5SDimitry Andric } 1540b57cec5SDimitry Andric 1550b57cec5SDimitry Andric private: 1560b57cec5SDimitry Andric /// Translate TRI register number to a list of indices into our smaller tables 1570b57cec5SDimitry Andric /// of interesting registers. 1580b57cec5SDimitry Andric iterator_range<SmallVectorImpl<int>::const_iterator> 1590b57cec5SDimitry Andric regIndices(unsigned Reg) const; 1600b57cec5SDimitry Andric 1610b57cec5SDimitry Andric /// DomainValue allocation. 1620b57cec5SDimitry Andric DomainValue *alloc(int domain = -1); 1630b57cec5SDimitry Andric 1640b57cec5SDimitry Andric /// Add reference to DV. retain(DomainValue * DV)1650b57cec5SDimitry Andric DomainValue *retain(DomainValue *DV) { 1660b57cec5SDimitry Andric if (DV) 1670b57cec5SDimitry Andric ++DV->Refs; 1680b57cec5SDimitry Andric return DV; 1690b57cec5SDimitry Andric } 1700b57cec5SDimitry Andric 1710b57cec5SDimitry Andric /// Release a reference to DV. When the last reference is released, 1720b57cec5SDimitry Andric /// collapse if needed. 1730b57cec5SDimitry Andric void release(DomainValue *); 1740b57cec5SDimitry Andric 1750b57cec5SDimitry Andric /// Follow the chain of dead DomainValues until a live DomainValue is reached. 1760b57cec5SDimitry Andric /// Update the referenced pointer when necessary. 1770b57cec5SDimitry Andric DomainValue *resolve(DomainValue *&); 1780b57cec5SDimitry Andric 1790b57cec5SDimitry Andric /// Set LiveRegs[rx] = dv, updating reference counts. 1800b57cec5SDimitry Andric void setLiveReg(int rx, DomainValue *DV); 1810b57cec5SDimitry Andric 1820b57cec5SDimitry Andric /// Kill register rx, recycle or collapse any DomainValue. 1830b57cec5SDimitry Andric void kill(int rx); 1840b57cec5SDimitry Andric 1850b57cec5SDimitry Andric /// Force register rx into domain. 1860b57cec5SDimitry Andric void force(int rx, unsigned domain); 1870b57cec5SDimitry Andric 1880b57cec5SDimitry Andric /// Collapse open DomainValue into given domain. If there are multiple 1890b57cec5SDimitry Andric /// registers using dv, they each get a unique collapsed DomainValue. 1900b57cec5SDimitry Andric void collapse(DomainValue *dv, unsigned domain); 1910b57cec5SDimitry Andric 1920b57cec5SDimitry Andric /// All instructions and registers in B are moved to A, and B is released. 1930b57cec5SDimitry Andric bool merge(DomainValue *A, DomainValue *B); 1940b57cec5SDimitry Andric 1950b57cec5SDimitry Andric /// Set up LiveRegs by merging predecessor live-out values. 1960b57cec5SDimitry Andric void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); 1970b57cec5SDimitry Andric 1980b57cec5SDimitry Andric /// Update live-out values. 1990b57cec5SDimitry Andric void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); 2000b57cec5SDimitry Andric 2010b57cec5SDimitry Andric /// Process he given basic block. 2020b57cec5SDimitry Andric void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); 2030b57cec5SDimitry Andric 2040b57cec5SDimitry Andric /// Visit given insturcion. 2050b57cec5SDimitry Andric bool visitInstr(MachineInstr *); 2060b57cec5SDimitry Andric 2070b57cec5SDimitry Andric /// Update def-ages for registers defined by MI. 2080b57cec5SDimitry Andric /// If Kill is set, also kill off DomainValues clobbered by the defs. 2090b57cec5SDimitry Andric void processDefs(MachineInstr *, bool Kill); 2100b57cec5SDimitry Andric 2110b57cec5SDimitry Andric /// A soft instruction can be changed to work in other domains given by mask. 2120b57cec5SDimitry Andric void visitSoftInstr(MachineInstr *, unsigned mask); 2130b57cec5SDimitry Andric 2140b57cec5SDimitry Andric /// A hard instruction only works in one domain. All input registers will be 2150b57cec5SDimitry Andric /// forced into that domain. 2160b57cec5SDimitry Andric void visitHardInstr(MachineInstr *, unsigned domain); 2170b57cec5SDimitry Andric }; 2180b57cec5SDimitry Andric 2190b57cec5SDimitry Andric } // namespace llvm 2200b57cec5SDimitry Andric 2210b57cec5SDimitry Andric #endif // LLVM_CODEGEN_EXECUTIONDOMAINFIX_H 222