156ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen//===- ExecutionDepsFix.cpp - Fix execution dependecy issues ----*- C++ -*-===// 2352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// 3352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 4352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// 5352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 6352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 7352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// 8352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 9352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// 1056ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen// This file contains the execution dependency fix pass. 11352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// 1256ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen// Some X86 SSE instructions like mov, and, or, xor are available in different 13352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// variants for different operand types. These variant instructions are 14352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// equivalent, but on Nehalem and newer cpus there is extra latency 1556ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen// transferring data between integer and floating point domains. ARM cores 1656ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen// have similar issues when they are configured with both VFP and NEON 1756ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen// pipelines. 18352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// 19352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// This pass changes the variant instructions to minimize domain crossings. 20352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen// 21352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 22352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 23df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen#define DEBUG_TYPE "execution-fix" 24352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 25352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 26df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 27df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 28df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 29a59ce0379134b249a3c949f7dcd6ec3566c4d7e3Jakob Stoklund Olesen#include "llvm/ADT/PostOrderIterator.h" 30bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen#include "llvm/Support/Allocator.h" 31352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen#include "llvm/Support/Debug.h" 32352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 33352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesenusing namespace llvm; 34352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 35563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner/// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track 36e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// of execution domains. 37e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// 38e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// An open DomainValue represents a set of instructions that can still switch 39e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// execution domain. Multiple registers may refer to the same open 40e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// DomainValue - they will eventually be collapsed to the same execution 41e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// domain. 42e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// 43e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// A collapsed DomainValue represents a single register that has been forced 44e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// into one of more execution domains. There is a separate collapsed 45e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// DomainValue for each register, but it may contain multiple execution 46e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// domains. A register value is initially created in a single execution 47e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// domain, but if we were forced to pay the penalty of a domain crossing, we 482947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen/// keep track of the fact that the register is now available in multiple 49e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// domains. 50bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesennamespace { 51e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesenstruct DomainValue { 52e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // Basic reference counting. 53e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen unsigned Refs; 54e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 55e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Bitmask of available domains. For an open DomainValue, it is the still 56e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // possible domains for collapsing. For a collapsed DomainValue it is the 57e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // domains where the register is available for free. 58e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen unsigned AvailableDomains; 59e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 60dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen // Pointer to the next DomainValue in a chain. When two DomainValues are 61dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen // merged, Victim.Next is set to point to Victor, so old DomainValue 62d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // references can be updated by following the chain. 63dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen DomainValue *Next; 64dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen 65e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // Twiddleable instructions using or defining these registers. 66e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen SmallVector<MachineInstr*, 8> Instrs; 67e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 68e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // A collapsed DomainValue has no instructions to twiddle - it simply keeps 69e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // track of the domains where the registers are already available. 70e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen bool isCollapsed() const { return Instrs.empty(); } 71e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 72e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Is domain available? 73e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen bool hasDomain(unsigned domain) const { 74e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen return AvailableDomains & (1u << domain); 75e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 76e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 771a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen // Mark domain as available. 78e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen void addDomain(unsigned domain) { 79e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen AvailableDomains |= 1u << domain; 80e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 81e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 82e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Restrict to a single domain available. 83e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen void setSingleDomain(unsigned domain) { 84e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen AvailableDomains = 1u << domain; 85e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen } 86e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen 87e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Return bitmask of domains that are available and in mask. 88e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen unsigned getCommonDomains(unsigned mask) const { 89e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen return AvailableDomains & mask; 90e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen } 91e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen 92e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // First domain available. 93e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen unsigned getFirstDomain() const { 94e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen return CountTrailingZeros_32(AvailableDomains); 951a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen } 961a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen 97737e9a2db27b9c3b212ff64fda7af5537ecbfb45Jakob Stoklund Olesen DomainValue() : Refs(0) { clear(); } 98e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 99dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen // Clear this DomainValue and point to next which has all its data. 100e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen void clear() { 1012947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen AvailableDomains = 0; 102dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen Next = 0; 103e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen Instrs.clear(); 104e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 105e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen}; 106bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen} 107e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 108bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesennamespace { 1092947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen/// LiveReg - Information about a live register. 1102947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesenstruct LiveReg { 1112947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen /// Value currently in this register, or NULL when no value is being tracked. 1122947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen /// This counts as a DomainValue reference. 1132947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen DomainValue *Value; 1142947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 1152947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen /// Instruction that defined this register, relative to the beginning of the 1162947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen /// current basic block. When a LiveReg is used to represent a live-out 1172947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen /// register, this value is relative to the end of the basic block, so it 1182947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen /// will be a negative number. 1192947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen int Def; 1202947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen}; 1212947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen} // anonynous namespace 1222947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 1232947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesennamespace { 12456ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesenclass ExeDepsFix : public MachineFunctionPass { 125352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen static char ID; 126bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen SpecificBumpPtrAllocator<DomainValue> Allocator; 127bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen SmallVector<DomainValue*,16> Avail; 128352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 129df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen const TargetRegisterClass *const RC; 130352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen MachineFunction *MF; 131df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen const TargetInstrInfo *TII; 132e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen const TargetRegisterInfo *TRI; 133df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen std::vector<int> AliasMap; 134df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen const unsigned NumRegs; 1352947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveReg *LiveRegs; 1362947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen typedef DenseMap<MachineBasicBlock*, LiveReg*> LiveOutMap; 1371a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen LiveOutMap LiveOuts; 1382947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 1392947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen /// Current instruction number. 1402947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen /// The first instruction in each basic block is 0. 1412947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen int CurInstr; 1422947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 1432947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen /// True when the current block has a predecessor that hasn't been visited 1442947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen /// yet. 1452947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen bool SeenUnknownBackEdge; 146e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 147352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesenpublic: 14856ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen ExeDepsFix(const TargetRegisterClass *rc) 149df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen : MachineFunctionPass(ID), RC(rc), NumRegs(RC->getNumRegs()) {} 150352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 151352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const { 152352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen AU.setPreservesAll(); 153352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 154352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen } 155352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 156352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction &MF); 157352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 158352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen virtual const char *getPassName() const { 159cd7dcad82a30363132d2dbabb45d60f1d2164a92Jakob Stoklund Olesen return "Execution dependency fix"; 160352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen } 161352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 162352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesenprivate: 163e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // Register mapping. 1646bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen int regIndex(unsigned Reg); 165e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 166bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen // DomainValue allocation. 1676bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen DomainValue *alloc(int domain = -1); 168dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen DomainValue *retain(DomainValue *DV) { 169dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen if (DV) ++DV->Refs; 170dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen return DV; 171dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen } 17235e932483a86a2b417d874648b903f6290ec3157Jakob Stoklund Olesen void release(DomainValue*); 173dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen DomainValue *resolve(DomainValue*&); 174bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen 175e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // LiveRegs manipulations. 1766bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen void setLiveReg(int rx, DomainValue *DV); 1776bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen void kill(int rx); 1786bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen void force(int rx, unsigned domain); 1796bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen void collapse(DomainValue *dv, unsigned domain); 1806bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen bool merge(DomainValue *A, DomainValue *B); 181e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 1822947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen void enterBasicBlock(MachineBasicBlock*); 18325265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen void leaveBasicBlock(MachineBasicBlock*); 18425265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen void visitInstr(MachineInstr*); 1852947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen void processDefs(MachineInstr*, bool Kill); 186e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen void visitSoftInstr(MachineInstr*, unsigned mask); 187e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen void visitHardInstr(MachineInstr*, unsigned domain); 188352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen}; 189352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen} 190352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 19156ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesenchar ExeDepsFix::ID = 0; 192352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 193e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// Translate TRI register number to an index into our smaller tables of 194e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// interesting registers. Return -1 for boring registers. 1956bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesenint ExeDepsFix::regIndex(unsigned Reg) { 196df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen assert(Reg < AliasMap.size() && "Invalid register"); 197df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen return AliasMap[Reg]; 198e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen} 199e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 2006bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund OlesenDomainValue *ExeDepsFix::alloc(int domain) { 201bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen DomainValue *dv = Avail.empty() ? 202bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen new(Allocator.Allocate()) DomainValue : 203bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen Avail.pop_back_val(); 204bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen if (domain >= 0) 205e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen dv->addDomain(domain); 206737e9a2db27b9c3b212ff64fda7af5537ecbfb45Jakob Stoklund Olesen assert(dv->Refs == 0 && "Reference count wasn't cleared"); 207dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen assert(!dv->Next && "Chained DomainValue shouldn't have been recycled"); 208bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen return dv; 209bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen} 210bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen 21135e932483a86a2b417d874648b903f6290ec3157Jakob Stoklund Olesen/// release - Release a reference to DV. When the last reference is released, 21235e932483a86a2b417d874648b903f6290ec3157Jakob Stoklund Olesen/// collapse if needed. 21335e932483a86a2b417d874648b903f6290ec3157Jakob Stoklund Olesenvoid ExeDepsFix::release(DomainValue *DV) { 214dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen while (DV) { 215dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen assert(DV->Refs && "Bad DomainValue"); 216dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen if (--DV->Refs) 217dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen return; 218dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen 219dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen // There are no more DV references. Collapse any contained instructions. 220dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen if (DV->AvailableDomains && !DV->isCollapsed()) 221dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen collapse(DV, DV->getFirstDomain()); 222dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen 223dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen DomainValue *Next = DV->Next; 224dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen DV->clear(); 225dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen Avail.push_back(DV); 226dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen // Also release the next DomainValue in the chain. 227dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen DV = Next; 228dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen } 229dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen} 23035e932483a86a2b417d874648b903f6290ec3157Jakob Stoklund Olesen 231dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen/// resolve - Follow the chain of dead DomainValues until a live DomainValue is 232dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen/// reached. Update the referenced pointer when necessary. 233dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund OlesenDomainValue *ExeDepsFix::resolve(DomainValue *&DVRef) { 234dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen DomainValue *DV = DVRef; 235dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen if (!DV || !DV->Next) 236dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen return DV; 237dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen 238dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen // DV has a chain. Find the end. 239dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen do DV = DV->Next; 240dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen while (DV->Next); 241dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen 242dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen // Update DVRef to point to DV. 243dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen retain(DV); 244dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen release(DVRef); 245dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen DVRef = DV; 246dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen return DV; 247bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen} 248bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen 249e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// Set LiveRegs[rx] = dv, updating reference counts. 2506bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesenvoid ExeDepsFix::setLiveReg(int rx, DomainValue *dv) { 2511a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen assert(unsigned(rx) < NumRegs && "Invalid index"); 2522947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen assert(LiveRegs && "Must enter basic block first."); 2531a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen 2542947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (LiveRegs[rx].Value == dv) 255e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen return; 2562947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (LiveRegs[rx].Value) 2572947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen release(LiveRegs[rx].Value); 2582947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveRegs[rx].Value = retain(dv); 259e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen} 260e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 261e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen// Kill register rx, recycle or collapse any DomainValue. 2626bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesenvoid ExeDepsFix::kill(int rx) { 2631a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen assert(unsigned(rx) < NumRegs && "Invalid index"); 2642947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen assert(LiveRegs && "Must enter basic block first."); 2652947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (!LiveRegs[rx].Value) 2662947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen return; 267e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 2682947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen release(LiveRegs[rx].Value); 2692947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveRegs[rx].Value = 0; 270e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen} 271e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 272e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// Force register rx into domain. 2736bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesenvoid ExeDepsFix::force(int rx, unsigned domain) { 2741a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen assert(unsigned(rx) < NumRegs && "Invalid index"); 2752947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen assert(LiveRegs && "Must enter basic block first."); 2762947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (DomainValue *dv = LiveRegs[rx].Value) { 277e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen if (dv->isCollapsed()) 278e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen dv->addDomain(domain); 2798ba1c6ab8749d03692207ab1fa32993c1fc5c7bfJakob Stoklund Olesen else if (dv->hasDomain(domain)) 2806bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen collapse(dv, domain); 2818ba1c6ab8749d03692207ab1fa32993c1fc5c7bfJakob Stoklund Olesen else { 28256ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen // This is an incompatible open DomainValue. Collapse it to whatever and 28356ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen // force the new value into domain. This costs a domain crossing. 2846bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen collapse(dv, dv->getFirstDomain()); 2852947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen assert(LiveRegs[rx].Value && "Not live after collapse?"); 2862947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveRegs[rx].Value->addDomain(domain); 2878ba1c6ab8749d03692207ab1fa32993c1fc5c7bfJakob Stoklund Olesen } 288e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } else { 2891a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen // Set up basic collapsed DomainValue. 2906bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen setLiveReg(rx, alloc(domain)); 291e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 292e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen} 293e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 294e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// Collapse open DomainValue into given domain. If there are multiple 295e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// registers using dv, they each get a unique collapsed DomainValue. 2966bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesenvoid ExeDepsFix::collapse(DomainValue *dv, unsigned domain) { 297e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen assert(dv->hasDomain(domain) && "Cannot collapse"); 298e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 299e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // Collapse all the instructions. 300e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen while (!dv->Instrs.empty()) 30198e933f9ad3cc2ede3a0a337144a504265d614cdJakob Stoklund Olesen TII->setExecutionDomain(dv->Instrs.pop_back_val(), domain); 302e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen dv->setSingleDomain(domain); 303e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 304e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // If there are multiple users, give them new, unique DomainValues. 305bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen if (LiveRegs && dv->Refs > 1) 3061a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen for (unsigned rx = 0; rx != NumRegs; ++rx) 3072947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (LiveRegs[rx].Value == dv) 3086bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen setLiveReg(rx, alloc(domain)); 309e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen} 310e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 311e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// Merge - All instructions and registers in B are moved to A, and B is 312e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen/// released. 3136bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesenbool ExeDepsFix::merge(DomainValue *A, DomainValue *B) { 314e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen assert(!A->isCollapsed() && "Cannot merge into collapsed"); 315e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen assert(!B->isCollapsed() && "Cannot merge from collapsed"); 31685ffee2c78e217d5c166d2623a0dee5396f67b0fJakob Stoklund Olesen if (A == B) 3175f282b5dfdfcc6afe2eb27d7d04766f9f33cb1f4Jakob Stoklund Olesen return true; 318e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Restrict to the domains that A and B have in common. 319e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen unsigned common = A->getCommonDomains(B->AvailableDomains); 320e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen if (!common) 321e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen return false; 322e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen A->AvailableDomains = common; 323e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen A->Instrs.append(B->Instrs.begin(), B->Instrs.end()); 324e1b3e11c15b705ad55c5ff2b04a0b790599013eaJakob Stoklund Olesen 325e1b3e11c15b705ad55c5ff2b04a0b790599013eaJakob Stoklund Olesen // Clear the old DomainValue so we won't try to swizzle instructions twice. 326737e9a2db27b9c3b212ff64fda7af5537ecbfb45Jakob Stoklund Olesen B->clear(); 327dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen // All uses of B are referred to A. 328dbc372f47e3a77343e6ef1ab4a88bc46f532f774Jakob Stoklund Olesen B->Next = retain(A); 329e1b3e11c15b705ad55c5ff2b04a0b790599013eaJakob Stoklund Olesen 3301a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen for (unsigned rx = 0; rx != NumRegs; ++rx) 3312947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (LiveRegs[rx].Value == B) 3326bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen setLiveReg(rx, A); 333e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen return true; 334e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen} 335e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 336f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen// enterBasicBlock - Set up LiveRegs by merging predecessor live-out values. 3372947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesenvoid ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) { 338f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen // Detect back-edges from predecessors we haven't processed yet. 3392947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen SeenUnknownBackEdge = false; 340f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen 3412947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Reset instruction counter in each basic block. 3422947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen CurInstr = 0; 3432947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 3442947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Set up LiveRegs to represent registers entering MBB. 3452947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (!LiveRegs) 3462947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveRegs = new LiveReg[NumRegs]; 3472947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 3482947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Default values are 'nothing happened a long time ago'. 3492947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen for (unsigned rx = 0; rx != NumRegs; ++rx) { 3502947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveRegs[rx].Value = 0; 3512947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveRegs[rx].Def = -(1 << 20); 3522947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen } 3532947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 3542947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // This is the entry block. 3552947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (MBB->pred_empty()) { 3562947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen for (MachineBasicBlock::livein_iterator i = MBB->livein_begin(), 3571a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen e = MBB->livein_end(); i != e; ++i) { 3582947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen int rx = regIndex(*i); 3592947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (rx < 0) 360f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen continue; 3612947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Treat function live-ins as if they were defined just before the first 3622947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // instruction. Usually, function arguments are set up immediately 3632947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // before the call. 3642947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveRegs[rx].Def = -1; 3652947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen } 3662947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MBB->getNumber() << ": entry\n"); 3672947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen return; 3682947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen } 3692947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 3702947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Try to coalesce live-out registers from predecessors. 3712947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(), 3722947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen pe = MBB->pred_end(); pi != pe; ++pi) { 3732947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveOutMap::const_iterator fi = LiveOuts.find(*pi); 3742947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (fi == LiveOuts.end()) { 3752947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen SeenUnknownBackEdge = true; 3762947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen continue; 3772947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen } 3782947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen assert(fi->second && "Can't have NULL entries"); 3792947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 3802947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen for (unsigned rx = 0; rx != NumRegs; ++rx) { 3812947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Use the most recent predecessor def for each register. 3822947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveRegs[rx].Def = std::max(LiveRegs[rx].Def, fi->second[rx].Def); 3832947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 3842947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen DomainValue *pdv = resolve(fi->second[rx].Value); 3852947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (!pdv) 386f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen continue; 3872947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (!LiveRegs[rx].Value) { 3886bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen setLiveReg(rx, pdv); 389563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner continue; 390563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner } 391563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner 392563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner // We have a live DomainValue from more than one predecessor. 3932947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (LiveRegs[rx].Value->isCollapsed()) { 394563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner // We are already collapsed, but predecessor is not. Force him. 3952947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen unsigned Domain = LiveRegs[rx].Value->getFirstDomain(); 3962947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (!pdv->isCollapsed() && pdv->hasDomain(Domain)) 3972947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen collapse(pdv, Domain); 398563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner continue; 3991a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen } 400bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen 401563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner // Currently open, merge in predecessor. 402e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen if (!pdv->isCollapsed()) 4032947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen merge(LiveRegs[rx].Value, pdv); 404563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner else 4056bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen force(rx, pdv->getFirstDomain()); 4061a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen } 4071a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen } 4082947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen DEBUG(dbgs() << "BB#" << MBB->getNumber() 4092947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen << (SeenUnknownBackEdge ? ": incomplete\n" : ": all preds known\n")); 410e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen} 411e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 41225265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesenvoid ExeDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) { 4132947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen assert(LiveRegs && "Must enter basic block first."); 41425265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen // Save live registers at end of MBB - used by enterBasicBlock(). 415f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen // Also use LiveOuts as a visited set to detect back-edges. 4162947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen bool First = LiveOuts.insert(std::make_pair(MBB, LiveRegs)).second; 4172947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 4182947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (First) { 4192947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // LiveRegs was inserted in LiveOuts. Adjust all defs to be relative to 4202947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // the end of this block instead of the beginning. 4212947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen for (unsigned i = 0, e = NumRegs; i != e; ++i) 4222947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveRegs[i].Def -= CurInstr; 4232947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen } else { 424f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen // Insertion failed, this must be the second pass. 425f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen // Release all the DomainValues instead of keeping them. 426f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen for (unsigned i = 0, e = NumRegs; i != e; ++i) 4272947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen release(LiveRegs[i].Value); 428f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen delete[] LiveRegs; 429f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen } 43025265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen LiveRegs = 0; 43125265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen} 43225265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen 43325265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesenvoid ExeDepsFix::visitInstr(MachineInstr *MI) { 43425265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen if (MI->isDebugValue()) 43525265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen return; 4362947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 4372947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Update instructions with explicit execution domains. 4382947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(MI); 4392947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (DomP.first) { 4402947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (DomP.second) 4412947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen visitSoftInstr(MI, DomP.second); 44225265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen else 4432947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen visitHardInstr(MI, DomP.first); 4442947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen } 4452947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 4462947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Process defs to track register ages, and kill values clobbered by generic 4472947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // instructions. 4482947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen processDefs(MI, !DomP.first); 4492947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen} 4502947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 4512947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen// Update def-ages for registers defined by MI. 4522947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen// If Kill is set, also kill off DomainValues clobbered by the defs. 4532947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesenvoid ExeDepsFix::processDefs(MachineInstr *MI, bool Kill) { 4542947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen assert(!MI->isDebugValue() && "Won't process debug values"); 4552947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen const MCInstrDesc &MCID = MI->getDesc(); 4562947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen for (unsigned i = 0, 4575a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs(); 4582947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen i != e; ++i) { 4592947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 4602947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (!MO.isReg()) 4612947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen continue; 4622947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (MO.isImplicit()) 4632947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen break; 4642947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (MO.isUse()) 4652947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen continue; 4662947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen int rx = regIndex(MO.getReg()); 4672947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (rx < 0) 4682947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen continue; 4692947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 4702947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // This instruction explicitly defines rx. 4712947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen DEBUG(dbgs() << TRI->getName(RC->getRegister(rx)) << ":\t" << CurInstr 4722947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen << '\t' << *MI); 4732947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 474c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen // How many instructions since rx was last written? 475c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen unsigned Clearance = CurInstr - LiveRegs[rx].Def; 4762947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen LiveRegs[rx].Def = CurInstr; 4772947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 4782947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Kill off domains redefined by generic instructions. 4792947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (Kill) 4802947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen kill(rx); 481c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen 482c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen // Verify clearance before partial register updates. 483c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen unsigned Pref = TII->getPartialRegUpdateClearance(MI, i, TRI); 484c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen if (!Pref) 485c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen continue; 486c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref); 487c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen if (Pref > Clearance) { 488c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen DEBUG(dbgs() << ": Break dependency.\n"); 489c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen TII->breakPartialRegDependency(MI, i, TRI); 490c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen continue; 491c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen } 492c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen 493c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen // The current clearance seems OK, but we may be ignoring a def from a 494c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen // back-edge. 495c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen if (!SeenUnknownBackEdge || Pref <= unsigned(CurInstr)) { 496c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen DEBUG(dbgs() << ": OK.\n"); 497c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen continue; 498c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen } 499c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen 500c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen // A def from an unprocessed back-edge may make us break this dependency. 501c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen DEBUG(dbgs() << ": Wait for back-edge to resolve.\n"); 5022947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen } 5032947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 5042947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen ++CurInstr; 50525265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen} 50625265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen 507e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen// A hard instruction only works in one domain. All input registers will be 508e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen// forced into that domain. 50956ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesenvoid ExeDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) { 510e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // Collapse all uses. 511e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen for (unsigned i = mi->getDesc().getNumDefs(), 512e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen e = mi->getDesc().getNumOperands(); i != e; ++i) { 513e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen MachineOperand &mo = mi->getOperand(i); 514e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen if (!mo.isReg()) continue; 5156bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen int rx = regIndex(mo.getReg()); 516e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen if (rx < 0) continue; 5176bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen force(rx, domain); 518e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 519e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 520e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // Kill all defs and force them. 521e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) { 522e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen MachineOperand &mo = mi->getOperand(i); 523e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen if (!mo.isReg()) continue; 5246bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen int rx = regIndex(mo.getReg()); 525e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen if (rx < 0) continue; 5266bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen kill(rx); 5276bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen force(rx, domain); 528e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 529e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen} 530e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 531e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen// A soft instruction can be changed to work in other domains given by mask. 53256ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesenvoid ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { 533e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Bitmask of available domains for this instruction after taking collapsed 534e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // operands into account. 535e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen unsigned available = mask; 536e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen 537e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // Scan the explicit use operands for incoming domains. 538e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen SmallVector<int, 4> used; 5391a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen if (LiveRegs) 5401a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen for (unsigned i = mi->getDesc().getNumDefs(), 5411a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen e = mi->getDesc().getNumOperands(); i != e; ++i) { 542563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner MachineOperand &mo = mi->getOperand(i); 543563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner if (!mo.isReg()) continue; 5446bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen int rx = regIndex(mo.getReg()); 545563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner if (rx < 0) continue; 5462947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (DomainValue *dv = LiveRegs[rx].Value) { 547e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Bitmask of domains that dv and available have in common. 548e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen unsigned common = dv->getCommonDomains(available); 549563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner // Is it possible to use this collapsed register for free? 550e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen if (dv->isCollapsed()) { 551e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Restrict available domains to the ones in common with the operand. 552e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // If there are no common domains, we must pay the cross-domain 553e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // penalty for this operand. 554e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen if (common) available = common; 555e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen } else if (common) 556e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Open DomainValue is compatible, save it for merging. 557563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner used.push_back(rx); 558563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner else 559e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Open DomainValue is not compatible with instruction. It is useless 560e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // now. 5616bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen kill(rx); 562563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner } 563e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 564e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 565e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // If the collapsed operands force a single domain, propagate the collapse. 566e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen if (isPowerOf2_32(available)) { 567e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen unsigned domain = CountTrailingZeros_32(available); 56898e933f9ad3cc2ede3a0a337144a504265d614cdJakob Stoklund Olesen TII->setExecutionDomain(mi, domain); 569e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen visitHardInstr(mi, domain); 570e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen return; 571e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 572e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 573e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // Kill off any remaining uses that don't match available, and build a list of 574e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // incoming DomainValues that we want to merge. 5752947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen SmallVector<LiveReg, 4> Regs; 576e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen for (SmallVector<int, 4>::iterator i=used.begin(), e=used.end(); i!=e; ++i) { 577e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen int rx = *i; 5782947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen const LiveReg &LR = LiveRegs[rx]; 5791a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen // This useless DomainValue could have been missed above. 5802947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (!LR.Value->getCommonDomains(available)) { 5812947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen kill(rx); 582e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen continue; 583e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 5842947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Sorted insertion. 5852947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen bool Inserted = false; 5862947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen for (SmallVector<LiveReg, 4>::iterator i = Regs.begin(), e = Regs.end(); 5872947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen i != e && !Inserted; ++i) { 5882947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (LR.Def < i->Def) { 5892947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen Inserted = true; 5902947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen Regs.insert(i, LR); 591e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 592e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 5932947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (!Inserted) 5942947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen Regs.push_back(LR); 595e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 596e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 597e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // doms are now sorted in order of appearance. Try to merge them all, giving 598e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // priority to the latest ones. 599e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen DomainValue *dv = 0; 6002947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen while (!Regs.empty()) { 601563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner if (!dv) { 6022947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen dv = Regs.pop_back_val().Value; 6037f5e43f61d3b28a03537c29156b0bad7dd3476e4Jakob Stoklund Olesen // Force the first dv to match the current instruction. 6047f5e43f61d3b28a03537c29156b0bad7dd3476e4Jakob Stoklund Olesen dv->AvailableDomains = dv->getCommonDomains(available); 6057f5e43f61d3b28a03537c29156b0bad7dd3476e4Jakob Stoklund Olesen assert(dv->AvailableDomains && "Domain should have been filtered"); 606563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner continue; 607563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner } 608bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen 6092947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen DomainValue *Latest = Regs.pop_back_val().Value; 6102947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen // Skip already merged values. 6112947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (Latest == dv || Latest->Next) 6122947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen continue; 6132947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (merge(dv, Latest)) 6142947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen continue; 615bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen 616e0103f03f05b770ebfc42152357a62acd8671945Jakob Stoklund Olesen // If latest didn't merge, it is useless now. Kill all registers using it. 617563d83ff5399060362b6a1373d42a6f166bd89a0Chris Lattner for (SmallVector<int,4>::iterator i=used.begin(), e=used.end(); i != e; ++i) 6182947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (LiveRegs[*i].Value == Latest) 6196bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen kill(*i); 620e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 621e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 622e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // dv is the DomainValue we are going to use for this instruction. 6237f5e43f61d3b28a03537c29156b0bad7dd3476e4Jakob Stoklund Olesen if (!dv) { 6246bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen dv = alloc(); 6257f5e43f61d3b28a03537c29156b0bad7dd3476e4Jakob Stoklund Olesen dv->AvailableDomains = available; 6267f5e43f61d3b28a03537c29156b0bad7dd3476e4Jakob Stoklund Olesen } 627e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen dv->Instrs.push_back(mi); 628e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 629e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen // Finally set all defs and non-collapsed uses to dv. 630e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen for (unsigned i = 0, e = mi->getDesc().getNumOperands(); i != e; ++i) { 631e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen MachineOperand &mo = mi->getOperand(i); 632e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen if (!mo.isReg()) continue; 6336bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen int rx = regIndex(mo.getReg()); 634e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen if (rx < 0) continue; 6352947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) { 6366bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen kill(rx); 6376bcb9a783b3220561ee3413322ad1037983d63cbJakob Stoklund Olesen setLiveReg(rx, dv); 638e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 639e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen } 640e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen} 641e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 64256ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesenbool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) { 643352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen MF = &mf; 644df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen TII = MF->getTarget().getInstrInfo(); 645e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen TRI = MF->getTarget().getRegisterInfo(); 6461a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen LiveRegs = 0; 647df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen assert(NumRegs == RC->getNumRegs() && "Bad regclass"); 648352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 6492947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: " 6502947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen << RC->getName() << " **********\n"); 6512947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen 65256ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen // If no relevant registers are used in the function, we can skip it 65356ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen // completely. 654e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen bool anyregs = false; 655df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen for (TargetRegisterClass::const_iterator I = RC->begin(), E = RC->end(); 656df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen I != E; ++I) 657a2a98fd0ddd2ae277be7cdd62aae92f6c5155e07Jakob Stoklund Olesen if (MF->getRegInfo().isPhysRegOrOverlapUsed(*I)) { 658a2a98fd0ddd2ae277be7cdd62aae92f6c5155e07Jakob Stoklund Olesen anyregs = true; 659a2a98fd0ddd2ae277be7cdd62aae92f6c5155e07Jakob Stoklund Olesen break; 660a2a98fd0ddd2ae277be7cdd62aae92f6c5155e07Jakob Stoklund Olesen } 661e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen if (!anyregs) return false; 662352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 663df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen // Initialize the AliasMap on the first use. 664df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen if (AliasMap.empty()) { 665df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen // Given a PhysReg, AliasMap[PhysReg] is either the relevant index into RC, 666df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen // or -1. 667df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen AliasMap.resize(TRI->getNumRegs(), -1); 668df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i) 669396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); 670396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen AI.isValid(); ++AI) 671df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen AliasMap[*AI] = i; 672df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen } 673df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesen 674352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen MachineBasicBlock *Entry = MF->begin(); 675a59ce0379134b249a3c949f7dcd6ec3566c4d7e3Jakob Stoklund Olesen ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry); 676f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen SmallVector<MachineBasicBlock*, 16> Loops; 677a59ce0379134b249a3c949f7dcd6ec3566c4d7e3Jakob Stoklund Olesen for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator 678a59ce0379134b249a3c949f7dcd6ec3566c4d7e3Jakob Stoklund Olesen MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) { 679a59ce0379134b249a3c949f7dcd6ec3566c4d7e3Jakob Stoklund Olesen MachineBasicBlock *MBB = *MBBI; 6802947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen enterBasicBlock(MBB); 6812947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (SeenUnknownBackEdge) 682f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen Loops.push_back(MBB); 683352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; 68425265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen ++I) 68525265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen visitInstr(I); 68625265d0e7af83f30e64851458c29c5b0c01befebJakob Stoklund Olesen leaveBasicBlock(MBB); 687352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen } 688e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 689f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen // Visit all the loop blocks again in order to merge DomainValues from 690f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen // back-edges. 691f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen for (unsigned i = 0, e = Loops.size(); i != e; ++i) { 692f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen MachineBasicBlock *MBB = Loops[i]; 693f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen enterBasicBlock(MBB); 694c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; 695c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen ++I) 696c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen if (!I->isDebugValue()) 697c2ecf3efbf375fc82bb1cea6afd7448498f9ae75Jakob Stoklund Olesen processDefs(I, false); 698f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen leaveBasicBlock(MBB); 699f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen } 700f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen 701b26c7727c9a45613d9bae69995cfd719c57c5614Jakob Stoklund Olesen // Clear the LiveOuts vectors and collapse any remaining DomainValues. 702b26c7727c9a45613d9bae69995cfd719c57c5614Jakob Stoklund Olesen for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator 703b26c7727c9a45613d9bae69995cfd719c57c5614Jakob Stoklund Olesen MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) { 704b26c7727c9a45613d9bae69995cfd719c57c5614Jakob Stoklund Olesen LiveOutMap::const_iterator FI = LiveOuts.find(*MBBI); 705f4c4768fb2277cb940a90cb2f0e9a747ebc671c3Jakob Stoklund Olesen if (FI == LiveOuts.end() || !FI->second) 706b26c7727c9a45613d9bae69995cfd719c57c5614Jakob Stoklund Olesen continue; 707b26c7727c9a45613d9bae69995cfd719c57c5614Jakob Stoklund Olesen for (unsigned i = 0, e = NumRegs; i != e; ++i) 7082947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen if (FI->second[i].Value) 7092947f730a96fc602ea008bba1929ae4f0638850aJakob Stoklund Olesen release(FI->second[i].Value); 7100fdb05deb9ccbebe55c05f2fb4af6ea813c97a98Jakob Stoklund Olesen delete[] FI->second; 711b26c7727c9a45613d9bae69995cfd719c57c5614Jakob Stoklund Olesen } 7121a5d2a8fa116c123bec6b0197c2d894e91f1f94bJakob Stoklund Olesen LiveOuts.clear(); 713bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen Avail.clear(); 714bbef815a3beeba3161cdad8e1cc108644bfc5ddcJakob Stoklund Olesen Allocator.DestroyAll(); 715e4b94b4efb9a4670f25a5a80dd3b97f9583de202Jakob Stoklund Olesen 716352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen return false; 717352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen} 718352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen 719df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund OlesenFunctionPass * 720df4b35e3dd85fead444e23b477d61dfd43e1fb6fJakob Stoklund Olesenllvm::createExecutionDependencyFixPass(const TargetRegisterClass *RC) { 72156ab875e554d30feb953052c3133ac36f88a3782Jakob Stoklund Olesen return new ExeDepsFix(RC); 722352aa503faee6c58e9cdb5054cc5ec1d90c696b4Jakob Stoklund Olesen} 723