119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===- ExecutionDepsFix.cpp - Fix execution dependecy issues ----*- C++ -*-===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file contains the execution dependency fix pass. 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Some X86 SSE instructions like mov, and, or, xor are available in different 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// variants for different operand types. These variant instructions are 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// equivalent, but on Nehalem and newer cpus there is extra latency 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// transferring data between integer and floating point domains. ARM cores 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// have similar issues when they are configured with both VFP and NEON 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// pipelines. 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This pass changes the variant instructions to minimize domain crossings. 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define DEBUG_TYPE "execution-fix" 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineFunctionPass.h" 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineRegisterInfo.h" 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/Passes.h" 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetInstrInfo.h" 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetMachine.h" 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/DepthFirstIterator.h" 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/Allocator.h" 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/Debug.h" 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/raw_ostream.h" 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanusing namespace llvm; 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// of execution domains. 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// An open DomainValue represents a set of instructions that can still switch 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// execution domain. Multiple registers may refer to the same open 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// DomainValue - they will eventually be collapsed to the same execution 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// domain. 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// A collapsed DomainValue represents a single register that has been forced 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// into one of more execution domains. There is a separate collapsed 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// DomainValue for each register, but it may contain multiple execution 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// domains. A register value is initially created in a single execution 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// domain, but if we were forced to pay the penalty of a domain crossing, we 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// keep track of the fact the the register is now available in multiple 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// domains. 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace { 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstruct DomainValue { 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Basic reference counting. 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Refs; 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Bitmask of available domains. For an open DomainValue, it is the still 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // possible domains for collapsing. For a collapsed DomainValue it is the 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // domains where the register is available for free. 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned AvailableDomains; 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Position of the last defining instruction. 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Dist; 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Twiddleable instructions using or defining these registers. 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<MachineInstr*, 8> Instrs; 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A collapsed DomainValue has no instructions to twiddle - it simply keeps 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // track of the domains where the registers are already available. 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isCollapsed() const { return Instrs.empty(); } 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Is domain available? 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool hasDomain(unsigned domain) const { 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AvailableDomains & (1u << domain); 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Mark domain as available. 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void addDomain(unsigned domain) { 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AvailableDomains |= 1u << domain; 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Restrict to a single domain available. 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setSingleDomain(unsigned domain) { 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AvailableDomains = 1u << domain; 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Return bitmask of domains that are available and in mask. 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned getCommonDomains(unsigned mask) const { 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AvailableDomains & mask; 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // First domain available. 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned getFirstDomain() const { 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return CountTrailingZeros_32(AvailableDomains); 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DomainValue() { clear(); } 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void clear() { 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Refs = AvailableDomains = Dist = 0; 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instrs.clear(); 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace { 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass ExeDepsFix : public MachineFunctionPass { 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static char ID; 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SpecificBumpPtrAllocator<DomainValue> Allocator; 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<DomainValue*,16> Avail; 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *const RC; 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineFunction *MF; 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetInstrInfo *TII; 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterInfo *TRI; 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *MBB; 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::vector<int> AliasMap; 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const unsigned NumRegs; 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DomainValue **LiveRegs; 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef DenseMap<MachineBasicBlock*,DomainValue**> LiveOutMap; 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveOutMap LiveOuts; 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Distance; 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExeDepsFix(const TargetRegisterClass *rc) 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman : MachineFunctionPass(ID), RC(rc), NumRegs(RC->getNumRegs()) {} 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.setPreservesAll(); 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineFunctionPass::getAnalysisUsage(AU); 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual bool runOnMachineFunction(MachineFunction &MF); 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual const char *getPassName() const { 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return "SSE execution domain fixup"; 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanprivate: 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Register mapping. 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int RegIndex(unsigned Reg); 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // DomainValue allocation. 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DomainValue *Alloc(int domain = -1); 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void Recycle(DomainValue*); 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // LiveRegs manipulations. 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void SetLiveReg(int rx, DomainValue *DV); 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void Kill(int rx); 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void Force(int rx, unsigned domain); 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void Collapse(DomainValue *dv, unsigned domain); 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Merge(DomainValue *A, DomainValue *B); 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void enterBasicBlock(); 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void visitGenericInstr(MachineInstr*); 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void visitSoftInstr(MachineInstr*, unsigned mask); 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void visitHardInstr(MachineInstr*, unsigned domain); 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanchar ExeDepsFix::ID = 0; 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Translate TRI register number to an index into our smaller tables of 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// interesting registers. Return -1 for boring registers. 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanint ExeDepsFix::RegIndex(unsigned Reg) { 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Reg < AliasMap.size() && "Invalid register"); 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AliasMap[Reg]; 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 16719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanDomainValue *ExeDepsFix::Alloc(int domain) { 16919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DomainValue *dv = Avail.empty() ? 17019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman new(Allocator.Allocate()) DomainValue : 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Avail.pop_back_val(); 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dv->Dist = Distance; 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (domain >= 0) 17419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dv->addDomain(domain); 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return dv; 17619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 17719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ExeDepsFix::Recycle(DomainValue *dv) { 17919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(dv && "Cannot recycle NULL"); 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dv->clear(); 18119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Avail.push_back(dv); 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Set LiveRegs[rx] = dv, updating reference counts. 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ExeDepsFix::SetLiveReg(int rx, DomainValue *dv) { 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(unsigned(rx) < NumRegs && "Invalid index"); 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LiveRegs) { 18819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRegs = new DomainValue*[NumRegs]; 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::fill(LiveRegs, LiveRegs+NumRegs, (DomainValue*)0); 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs[rx] == dv) 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs[rx]) { 19519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(LiveRegs[rx]->Refs && "Bad refcount"); 19619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (--LiveRegs[rx]->Refs == 0) Recycle(LiveRegs[rx]); 19719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRegs[rx] = dv; 19919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (dv) ++dv->Refs; 20019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Kill register rx, recycle or collapse any DomainValue. 20319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ExeDepsFix::Kill(int rx) { 20419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(unsigned(rx) < NumRegs && "Invalid index"); 20519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LiveRegs || !LiveRegs[rx]) return; 20619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Before killing the last reference to an open DomainValue, collapse it to 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the first available domain. 20919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs[rx]->Refs == 1 && !LiveRegs[rx]->isCollapsed()) 21019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Collapse(LiveRegs[rx], LiveRegs[rx]->getFirstDomain()); 21119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 21219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SetLiveReg(rx, 0); 21319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 21419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Force register rx into domain. 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ExeDepsFix::Force(int rx, unsigned domain) { 21719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(unsigned(rx) < NumRegs && "Invalid index"); 21819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DomainValue *dv; 21919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs && (dv = LiveRegs[rx])) { 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (dv->isCollapsed()) 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dv->addDomain(domain); 22219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (dv->hasDomain(domain)) 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Collapse(dv, domain); 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else { 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This is an incompatible open DomainValue. Collapse it to whatever and 22619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // force the new value into domain. This costs a domain crossing. 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Collapse(dv, dv->getFirstDomain()); 22819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(LiveRegs[rx] && "Not live after collapse?"); 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRegs[rx]->addDomain(domain); 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 23219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Set up basic collapsed DomainValue. 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SetLiveReg(rx, Alloc(domain)); 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Collapse open DomainValue into given domain. If there are multiple 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// registers using dv, they each get a unique collapsed DomainValue. 23919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ExeDepsFix::Collapse(DomainValue *dv, unsigned domain) { 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(dv->hasDomain(domain) && "Cannot collapse"); 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Collapse all the instructions. 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!dv->Instrs.empty()) 24419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TII->setExecutionDomain(dv->Instrs.pop_back_val(), domain); 24519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dv->setSingleDomain(domain); 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If there are multiple users, give them new, unique DomainValues. 24819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs && dv->Refs > 1) 24919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned rx = 0; rx != NumRegs; ++rx) 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs[rx] == dv) 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SetLiveReg(rx, Alloc(domain)); 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 25319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Merge - All instructions and registers in B are moved to A, and B is 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// released. 25619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool ExeDepsFix::Merge(DomainValue *A, DomainValue *B) { 25719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!A->isCollapsed() && "Cannot merge into collapsed"); 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!B->isCollapsed() && "Cannot merge from collapsed"); 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (A == B) 26019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 26119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Restrict to the domains that A and B have in common. 26219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned common = A->getCommonDomains(B->AvailableDomains); 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!common) 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman A->AvailableDomains = common; 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman A->Dist = std::max(A->Dist, B->Dist); 26719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman A->Instrs.append(B->Instrs.begin(), B->Instrs.end()); 26819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned rx = 0; rx != NumRegs; ++rx) 26919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs[rx] == B) 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SetLiveReg(rx, A); 27119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 27219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 27319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ExeDepsFix::enterBasicBlock() { 27519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Try to coalesce live-out registers from predecessors. 27619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::livein_iterator i = MBB->livein_begin(), 27719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman e = MBB->livein_end(); i != e; ++i) { 27819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int rx = RegIndex(*i); 27919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (rx < 0) continue; 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(), 28119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman pe = MBB->pred_end(); pi != pe; ++pi) { 28219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveOutMap::const_iterator fi = LiveOuts.find(*pi); 28319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (fi == LiveOuts.end()) continue; 28419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DomainValue *pdv = fi->second[rx]; 28519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!pdv) continue; 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LiveRegs || !LiveRegs[rx]) { 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SetLiveReg(rx, pdv); 28819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 29019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We have a live DomainValue from more than one predecessor. 29219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs[rx]->isCollapsed()) { 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We are already collapsed, but predecessor is not. Force him. 29419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned domain = LiveRegs[rx]->getFirstDomain(); 29519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!pdv->isCollapsed() && pdv->hasDomain(domain)) 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Collapse(pdv, domain); 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Currently open, merge in predecessor. 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!pdv->isCollapsed()) 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Merge(LiveRegs[rx], pdv); 30319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Force(rx, pdv->getFirstDomain()); 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// A hard instruction only works in one domain. All input registers will be 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// forced into that domain. 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ExeDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) { 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Collapse all uses. 31319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = mi->getDesc().getNumDefs(), 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman e = mi->getDesc().getNumOperands(); i != e; ++i) { 31519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &mo = mi->getOperand(i); 31619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!mo.isReg()) continue; 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int rx = RegIndex(mo.getReg()); 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (rx < 0) continue; 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Force(rx, domain); 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Kill all defs and force them. 32319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) { 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &mo = mi->getOperand(i); 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!mo.isReg()) continue; 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int rx = RegIndex(mo.getReg()); 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (rx < 0) continue; 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Kill(rx); 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Force(rx, domain); 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// A soft instruction can be changed to work in other domains given by mask. 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Bitmask of available domains for this instruction after taking collapsed 33619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // operands into account. 33719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned available = mask; 33819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Scan the explicit use operands for incoming domains. 34019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<int, 4> used; 34119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs) 34219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = mi->getDesc().getNumDefs(), 34319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman e = mi->getDesc().getNumOperands(); i != e; ++i) { 34419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &mo = mi->getOperand(i); 34519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!mo.isReg()) continue; 34619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int rx = RegIndex(mo.getReg()); 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (rx < 0) continue; 34819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DomainValue *dv = LiveRegs[rx]) { 34919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Bitmask of domains that dv and available have in common. 35019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned common = dv->getCommonDomains(available); 35119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Is it possible to use this collapsed register for free? 35219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (dv->isCollapsed()) { 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Restrict available domains to the ones in common with the operand. 35419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If there are no common domains, we must pay the cross-domain 35519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // penalty for this operand. 35619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (common) available = common; 35719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (common) 35819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Open DomainValue is compatible, save it for merging. 35919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman used.push_back(rx); 36019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Open DomainValue is not compatible with instruction. It is useless 36219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // now. 36319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Kill(rx); 36419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 36519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 36619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 36719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the collapsed operands force a single domain, propagate the collapse. 36819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isPowerOf2_32(available)) { 36919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned domain = CountTrailingZeros_32(available); 37019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TII->setExecutionDomain(mi, domain); 37119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman visitHardInstr(mi, domain); 37219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 37319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 37419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 37519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Kill off any remaining uses that don't match available, and build a list of 37619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // incoming DomainValues that we want to merge. 37719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<DomainValue*,4> doms; 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SmallVector<int, 4>::iterator i=used.begin(), e=used.end(); i!=e; ++i) { 37919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int rx = *i; 38019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DomainValue *dv = LiveRegs[rx]; 38119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This useless DomainValue could have been missed above. 38219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!dv->getCommonDomains(available)) { 38319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Kill(*i); 38419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 38519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 38619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // sorted, uniqued insert. 38719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool inserted = false; 38819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SmallVector<DomainValue*,4>::iterator i = doms.begin(), e = doms.end(); 38919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman i != e && !inserted; ++i) { 39019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (dv == *i) 39119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman inserted = true; 39219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (dv->Dist < (*i)->Dist) { 39319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman inserted = true; 39419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman doms.insert(i, dv); 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 39619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 39719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!inserted) 39819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman doms.push_back(dv); 39919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 40019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 40119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // doms are now sorted in order of appearance. Try to merge them all, giving 40219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // priority to the latest ones. 40319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DomainValue *dv = 0; 40419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!doms.empty()) { 40519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!dv) { 40619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dv = doms.pop_back_val(); 40719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 40819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 40919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 41019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DomainValue *latest = doms.pop_back_val(); 41119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Merge(dv, latest)) continue; 41219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 41319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If latest didn't merge, it is useless now. Kill all registers using it. 41419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SmallVector<int,4>::iterator i=used.begin(), e=used.end(); i != e; ++i) 41519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs[*i] == latest) 41619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Kill(*i); 41719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 41819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 41919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // dv is the DomainValue we are going to use for this instruction. 42019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!dv) 42119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dv = Alloc(); 42219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dv->Dist = Distance; 42319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dv->AvailableDomains = available; 42419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dv->Instrs.push_back(mi); 42519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 42619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Finally set all defs and non-collapsed uses to dv. 42719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = mi->getDesc().getNumOperands(); i != e; ++i) { 42819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &mo = mi->getOperand(i); 42919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!mo.isReg()) continue; 43019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int rx = RegIndex(mo.getReg()); 43119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (rx < 0) continue; 43219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LiveRegs || !LiveRegs[rx] || (mo.isDef() && LiveRegs[rx]!=dv)) { 43319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Kill(rx); 43419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SetLiveReg(rx, dv); 43519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 43619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 43719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 43819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ExeDepsFix::visitGenericInstr(MachineInstr *mi) { 44019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Process explicit defs, kill any relevant registers redefined. 44119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) { 44219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &mo = mi->getOperand(i); 44319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!mo.isReg()) continue; 44419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int rx = RegIndex(mo.getReg()); 44519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (rx < 0) continue; 44619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Kill(rx); 44719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 44819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 44919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 45019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) { 45119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MF = &mf; 45219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TII = MF->getTarget().getInstrInfo(); 45319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TRI = MF->getTarget().getRegisterInfo(); 45419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MBB = 0; 45519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRegs = 0; 45619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Distance = 0; 45719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(NumRegs == RC->getNumRegs() && "Bad regclass"); 45819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 45919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If no relevant registers are used in the function, we can skip it 46019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // completely. 46119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool anyregs = false; 46219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (TargetRegisterClass::const_iterator I = RC->begin(), E = RC->end(); 46319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I != E; ++I) 46419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MF->getRegInfo().isPhysRegUsed(*I)) { 46519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman anyregs = true; 46619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 46719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 46819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!anyregs) return false; 46919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 47019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Initialize the AliasMap on the first use. 47119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AliasMap.empty()) { 47219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Given a PhysReg, AliasMap[PhysReg] is either the relevant index into RC, 47319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // or -1. 47419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasMap.resize(TRI->getNumRegs(), -1); 47519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i) 47619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (const unsigned *AI = TRI->getOverlaps(RC->getRegister(i)); *AI; ++AI) 47719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasMap[*AI] = i; 47819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 47919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 48019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *Entry = MF->begin(); 48119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<MachineBasicBlock*, 16> Visited; 48219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*, 16> > 48319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DFI = df_ext_begin(Entry, Visited), DFE = df_ext_end(Entry, Visited); 48419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DFI != DFE; ++DFI) { 48519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MBB = *DFI; 48619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enterBasicBlock(); 48719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; 48819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++I) { 48919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *mi = I; 49019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (mi->isDebugValue()) continue; 49119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++Distance; 49219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<uint16_t, uint16_t> domp = TII->getExecutionDomain(mi); 49319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (domp.first) 49419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (domp.second) 49519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman visitSoftInstr(mi, domp.second); 49619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 49719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman visitHardInstr(mi, domp.first); 49819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (LiveRegs) 49919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman visitGenericInstr(mi); 50019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 50119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 50219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Save live registers at end of MBB - used by enterBasicBlock(). 50319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LiveRegs) 50419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveOuts.insert(std::make_pair(MBB, LiveRegs)); 50519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRegs = 0; 50619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 50719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 50819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Clear the LiveOuts vectors. Should we also collapse any remaining 50919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // DomainValues? 51019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveOutMap::const_iterator i = LiveOuts.begin(), e = LiveOuts.end(); 51119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman i != e; ++i) 51219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman delete[] i->second; 51319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveOuts.clear(); 51419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Avail.clear(); 51519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Allocator.DestroyAll(); 51619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 51719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 51819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 51919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 52019bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanFunctionPass * 52119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanllvm::createExecutionDependencyFixPass(const TargetRegisterClass *RC) { 52219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return new ExeDepsFix(RC); 52319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 524