LiveVariables.cpp revision 74de8b1b26b12fda3364382946e519a2e37b6709
1bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner//===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// 2bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 105cdfbad72d76864325260f134d58294c290a4886Chris Lattner// This file implements the LiveVariable analysis pass. For each machine 115cdfbad72d76864325260f134d58294c290a4886Chris Lattner// instruction in the function, this pass calculates the set of registers that 125cdfbad72d76864325260f134d58294c290a4886Chris Lattner// are immediately dead after the instruction (i.e., the instruction calculates 135cdfbad72d76864325260f134d58294c290a4886Chris Lattner// the value, but it is never used) and the set of registers that are used by 145cdfbad72d76864325260f134d58294c290a4886Chris Lattner// the instruction, but are never used after the instruction (i.e., they are 155cdfbad72d76864325260f134d58294c290a4886Chris Lattner// killed). 165cdfbad72d76864325260f134d58294c290a4886Chris Lattner// 175cdfbad72d76864325260f134d58294c290a4886Chris Lattner// This class computes live variables using are sparse implementation based on 185cdfbad72d76864325260f134d58294c290a4886Chris Lattner// the machine code SSA form. This class computes live variable information for 195cdfbad72d76864325260f134d58294c290a4886Chris Lattner// each virtual and _register allocatable_ physical register in a function. It 205cdfbad72d76864325260f134d58294c290a4886Chris Lattner// uses the dominance properties of SSA form to efficiently compute live 215cdfbad72d76864325260f134d58294c290a4886Chris Lattner// variables for virtual registers, and assumes that physical registers are only 225cdfbad72d76864325260f134d58294c290a4886Chris Lattner// live within a single basic block (allowing it to do a single local analysis 235cdfbad72d76864325260f134d58294c290a4886Chris Lattner// to resolve physical register lifetimes in each basic block). If a physical 245cdfbad72d76864325260f134d58294c290a4886Chris Lattner// register is not register allocatable, it is not tracked. This is useful for 255cdfbad72d76864325260f134d58294c290a4886Chris Lattner// things like the stack pointer and condition codes. 265cdfbad72d76864325260f134d58294c290a4886Chris Lattner// 27bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner//===----------------------------------------------------------------------===// 28bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 29bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/LiveVariables.h" 30bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/MachineInstr.h" 3161b08f193a6e84db44d3032a822e324ebb42a584Chris Lattner#include "llvm/Target/MRegisterInfo.h" 323501feab811c86c9659248a4875fc31a3165f84dChris Lattner#include "llvm/Target/TargetInstrInfo.h" 33bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/Target/TargetMachine.h" 34bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "Support/DepthFirstIterator.h" 355ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner#include "Support/STLExtras.h" 3649a5aaacef127970f91648ac468de1cd2b6f462fChris Lattnerusing namespace llvm; 37d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 38bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnerstatic RegisterAnalysis<LiveVariables> X("livevars", "Live Variable Analysis"); 39bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 40fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris LattnerLiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 41ef09c63e7ba5dd5410655f71d35eb7245893b1f1Chris Lattner assert(MRegisterInfo::isVirtualRegister(RegIdx) && 42fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner "getVarInfo: not a virtual register!"); 43fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner RegIdx -= MRegisterInfo::FirstVirtualRegister; 44fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner if (RegIdx >= VirtRegInfo.size()) { 45fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner if (RegIdx >= 2*VirtRegInfo.size()) 46fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner VirtRegInfo.resize(RegIdx*2); 47fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner else 48fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner VirtRegInfo.resize(2*VirtRegInfo.size()); 49fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner } 50fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner return VirtRegInfo[RegIdx]; 51fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner} 52fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner 53fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner 54fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner 55bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnervoid LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 5609ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman MachineBasicBlock *MBB) { 578ba9771549bcff6109ad45ff3944a1b6c3c54b46Chris Lattner unsigned BBNum = MBB->getNumber(); 58bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 59bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Check to see if this basic block is one of the killing blocks. If so, 60bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // remove it... 61bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 6274de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner if (VRInfo.Kills[i]->getParent() == MBB) { 63bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 64bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner break; 65bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 66bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 6773d4adfb1e5d6c0ce834b331e6099b14d3341dd7Chris Lattner if (MBB == VRInfo.DefInst->getParent()) return; // Terminate recursion 68bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 69bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner if (VRInfo.AliveBlocks.size() <= BBNum) 70bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner VRInfo.AliveBlocks.resize(BBNum+1); // Make space... 71bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 72bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner if (VRInfo.AliveBlocks[BBNum]) 73bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return; // We already know the block is live 74bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 75bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Mark the variable known alive in this bb 76bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner VRInfo.AliveBlocks[BBNum] = true; 77bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 78f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 79f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner E = MBB->pred_end(); PI != E; ++PI) 80bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MarkVirtRegAliveInBlock(VRInfo, *PI); 81bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 82bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 83bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnervoid LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, 8409ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman MachineInstr *MI) { 85bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Check to see if this basic block is already a kill block... 8674de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 87bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Yes, this register is killed in this basic block already. Increase the 88bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // live range by updating the kill instruction. 8974de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner VRInfo.Kills.back() = MI; 90bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return; 91bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 92bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 93bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#ifndef NDEBUG 94bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 9574de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 96bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#endif 97bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 9873d4adfb1e5d6c0ce834b331e6099b14d3341dd7Chris Lattner assert(MBB != VRInfo.DefInst->getParent() && 9973d4adfb1e5d6c0ce834b331e6099b14d3341dd7Chris Lattner "Should have kill for defblock!"); 100bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 101bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Add a new kill entry for this basic block. 10274de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner VRInfo.Kills.push_back(MI); 103bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 104bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Update all dominating blocks to mark them known live. 105bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner const BasicBlock *BB = MBB->getBasicBlock(); 106f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 107f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner E = MBB->pred_end(); PI != E; ++PI) 108bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MarkVirtRegAliveInBlock(VRInfo, *PI); 109bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 110bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 111bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnervoid LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { 112c55640f0194511d2c44f4d8bea099e373199ae9dAlkis Evlogimenos PhysRegInfo[Reg] = MI; 113c55640f0194511d2c44f4d8bea099e373199ae9dAlkis Evlogimenos PhysRegUsed[Reg] = true; 1146d3848df7e1f2d773ed7ae1a225944810d8510adChris Lattner 1156d3848df7e1f2d773ed7ae1a225944810d8510adChris Lattner for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 1166d3848df7e1f2d773ed7ae1a225944810d8510adChris Lattner unsigned Alias = *AliasSet; ++AliasSet) { 1176d3848df7e1f2d773ed7ae1a225944810d8510adChris Lattner PhysRegInfo[Alias] = MI; 1186d3848df7e1f2d773ed7ae1a225944810d8510adChris Lattner PhysRegUsed[Alias] = true; 1196d3848df7e1f2d773ed7ae1a225944810d8510adChris Lattner } 120bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 121bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 122bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnervoid LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { 123bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Does this kill a previous version of this register? 124bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner if (MachineInstr *LastUse = PhysRegInfo[Reg]) { 125bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner if (PhysRegUsed[Reg]) 126bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner RegistersKilled.insert(std::make_pair(LastUse, Reg)); 127bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner else 128bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner RegistersDead.insert(std::make_pair(LastUse, Reg)); 129bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 130bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner PhysRegInfo[Reg] = MI; 131bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner PhysRegUsed[Reg] = false; 13219b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos 13319b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 1346d3848df7e1f2d773ed7ae1a225944810d8510adChris Lattner unsigned Alias = *AliasSet; ++AliasSet) { 135499487742ec4299852f7ae8962acebf7bc2a22a4Chris Lattner if (MachineInstr *LastUse = PhysRegInfo[Alias]) { 136499487742ec4299852f7ae8962acebf7bc2a22a4Chris Lattner if (PhysRegUsed[Alias]) 1376d3848df7e1f2d773ed7ae1a225944810d8510adChris Lattner RegistersKilled.insert(std::make_pair(LastUse, Alias)); 13819b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos else 13909ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman RegistersDead.insert(std::make_pair(LastUse, Alias)); 14019b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos } 141499487742ec4299852f7ae8962acebf7bc2a22a4Chris Lattner PhysRegInfo[Alias] = MI; 142499487742ec4299852f7ae8962acebf7bc2a22a4Chris Lattner PhysRegUsed[Alias] = false; 14319b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos } 144bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 145bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 146bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnerbool LiveVariables::runOnMachineFunction(MachineFunction &MF) { 1479bcdcd17c7219dbc68de2f11ca2de86471c8c390Chris Lattner const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); 14896aef893383a6ffcc6d6955c5d969f0fd57831c2Chris Lattner RegInfo = MF.getTarget().getRegisterInfo(); 14996aef893383a6ffcc6d6955c5d969f0fd57831c2Chris Lattner assert(RegInfo && "Target doesn't have register information?"); 15096aef893383a6ffcc6d6955c5d969f0fd57831c2Chris Lattner 1515cdfbad72d76864325260f134d58294c290a4886Chris Lattner // First time though, initialize AllocatablePhysicalRegisters for the target 1525cdfbad72d76864325260f134d58294c290a4886Chris Lattner if (AllocatablePhysicalRegisters.empty()) { 1535cdfbad72d76864325260f134d58294c290a4886Chris Lattner // Make space, initializing to false... 15496aef893383a6ffcc6d6955c5d969f0fd57831c2Chris Lattner AllocatablePhysicalRegisters.resize(RegInfo->getNumRegs()); 1555cdfbad72d76864325260f134d58294c290a4886Chris Lattner 1565cdfbad72d76864325260f134d58294c290a4886Chris Lattner // Loop over all of the register classes... 15796aef893383a6ffcc6d6955c5d969f0fd57831c2Chris Lattner for (MRegisterInfo::regclass_iterator RCI = RegInfo->regclass_begin(), 15896aef893383a6ffcc6d6955c5d969f0fd57831c2Chris Lattner E = RegInfo->regclass_end(); RCI != E; ++RCI) 1595cdfbad72d76864325260f134d58294c290a4886Chris Lattner // Loop over all of the allocatable registers in the function... 1605cdfbad72d76864325260f134d58294c290a4886Chris Lattner for (TargetRegisterClass::iterator I = (*RCI)->allocation_order_begin(MF), 1615cdfbad72d76864325260f134d58294c290a4886Chris Lattner E = (*RCI)->allocation_order_end(MF); I != E; ++I) 1625cdfbad72d76864325260f134d58294c290a4886Chris Lattner AllocatablePhysicalRegisters[*I] = true; // The reg is allocatable! 1635cdfbad72d76864325260f134d58294c290a4886Chris Lattner } 1645cdfbad72d76864325260f134d58294c290a4886Chris Lattner 165bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // PhysRegInfo - Keep track of which instruction was the last use of a 166bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // physical register. This is a purely local property, because all physical 167bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // register references as presumed dead across basic blocks. 168bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 169859a18b5833f3566799313ecba8db4916500485bAlkis Evlogimenos MachineInstr *PhysRegInfoA[RegInfo->getNumRegs()]; 170859a18b5833f3566799313ecba8db4916500485bAlkis Evlogimenos bool PhysRegUsedA[RegInfo->getNumRegs()]; 171859a18b5833f3566799313ecba8db4916500485bAlkis Evlogimenos std::fill(PhysRegInfoA, PhysRegInfoA+RegInfo->getNumRegs(), (MachineInstr*)0); 172bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner PhysRegInfo = PhysRegInfoA; 173bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner PhysRegUsed = PhysRegUsedA; 174bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 175bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// Get some space for a respectable number of registers... 176bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner VirtRegInfo.resize(64); 177bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 178bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Calculate live variable information in depth first order on the CFG of the 179bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // function. This guarantees that we will see the definition of a virtual 180bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // register before its uses due to dominance properties of SSA (except for PHI 181bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // nodes, which are treated as a special case). 182bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 183f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner MachineBasicBlock *Entry = MF.begin(); 184a5287a63762fbf0976e333fb7787ec135fdc2061Chris Lattner std::set<MachineBasicBlock*> Visited; 185a5287a63762fbf0976e333fb7787ec135fdc2061Chris Lattner for (df_ext_iterator<MachineBasicBlock*> DFI = df_ext_begin(Entry, Visited), 186a5287a63762fbf0976e333fb7787ec135fdc2061Chris Lattner E = df_ext_end(Entry, Visited); DFI != E; ++DFI) { 187f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner MachineBasicBlock *MBB = *DFI; 1888ba9771549bcff6109ad45ff3944a1b6c3c54b46Chris Lattner unsigned BBNum = MBB->getNumber(); 189bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 190bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Loop over all of the instructions, processing them. 191bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 19209ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman I != E; ++I) { 193c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineInstr *MI = I; 194bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner const TargetInstrDescriptor &MID = TII.get(MI->getOpcode()); 195bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 196bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Process all of the operands of the instruction... 197bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner unsigned NumOperandsToProcess = MI->getNumOperands(); 198bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 199bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Unless it is a PHI node. In this case, ONLY process the DEF, not any 200bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // of the uses. They will be handled in other basic blocks. 201bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner if (MI->getOpcode() == TargetInstrInfo::PHI) 20209ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman NumOperandsToProcess = 1; 203bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 204bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Loop over implicit uses, using them. 20573ff5120eb8b8c0ccbfed8a17f1024c67a75f319Alkis Evlogimenos for (const unsigned *ImplicitUses = MID.ImplicitUses; 20673ff5120eb8b8c0ccbfed8a17f1024c67a75f319Alkis Evlogimenos *ImplicitUses; ++ImplicitUses) 20709ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman HandlePhysRegUse(*ImplicitUses, MI); 208bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 209bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Process all explicit uses... 210bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 21109ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman MachineOperand &MO = MI->getOperand(i); 21209ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman if (MO.isUse() && MO.isRegister() && MO.getReg()) { 21309ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman if (MRegisterInfo::isVirtualRegister(MO.getReg())){ 21409ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI); 21509ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 2165cdfbad72d76864325260f134d58294c290a4886Chris Lattner AllocatablePhysicalRegisters[MO.getReg()]) { 21709ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman HandlePhysRegUse(MO.getReg(), MI); 21809ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman } 21909ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman } 220bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 221bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 222bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Loop over implicit defs, defining them. 223efe995a4063dd3f414f60c6ee2f4704dbb0fad34Alkis Evlogimenos for (const unsigned *ImplicitDefs = MID.ImplicitDefs; 224efe995a4063dd3f414f60c6ee2f4704dbb0fad34Alkis Evlogimenos *ImplicitDefs; ++ImplicitDefs) 225efe995a4063dd3f414f60c6ee2f4704dbb0fad34Alkis Evlogimenos HandlePhysRegDef(*ImplicitDefs, MI); 226bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 227bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Process all explicit defs... 228bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 22909ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman MachineOperand &MO = MI->getOperand(i); 23009ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman if (MO.isDef() && MO.isRegister() && MO.getReg()) { 23109ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman if (MRegisterInfo::isVirtualRegister(MO.getReg())) { 23209ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman VarInfo &VRInfo = getVarInfo(MO.getReg()); 23309ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman 23473d4adfb1e5d6c0ce834b331e6099b14d3341dd7Chris Lattner assert(VRInfo.DefInst == 0 && "Variable multiply defined!"); 23509ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman VRInfo.DefInst = MI; 236472405e0dc05f6fb8c09af00713ff893fff25b94Chris Lattner // Defaults to dead 23774de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner VRInfo.Kills.push_back(MI); 23809ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 2395cdfbad72d76864325260f134d58294c290a4886Chris Lattner AllocatablePhysicalRegisters[MO.getReg()]) { 24009ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman HandlePhysRegDef(MO.getReg(), MI); 24109ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman } 24209ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman } 243bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 244bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 245bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 246bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Handle any virtual assignments from PHI nodes which might be at the 247bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // bottom of this basic block. We check all of our successor blocks to see 248bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // if they have PHI nodes, and if so, we simulate an assignment at the end 249bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // of the current block. 250f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 251f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner E = MBB->succ_end(); SI != E; ++SI) { 252f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner MachineBasicBlock *Succ = *SI; 253bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 254bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // PHI nodes are guaranteed to be at the top of the block... 255c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (MachineBasicBlock::iterator MI = Succ->begin(), ME = Succ->end(); 25609ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman MI != ME && MI->getOpcode() == TargetInstrInfo::PHI; ++MI) { 25709ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman for (unsigned i = 1; ; i += 2) { 25892bc3bc11c2d439264b1cf9e7fc5bc79f4215a54Chris Lattner assert(MI->getNumOperands() > i+1 && 25992bc3bc11c2d439264b1cf9e7fc5bc79f4215a54Chris Lattner "Didn't find an entry for our predecessor??"); 26009ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman if (MI->getOperand(i+1).getMachineBasicBlock() == MBB) { 26109ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman MachineOperand &MO = MI->getOperand(i); 26209ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman if (!MO.getVRegValueOrNull()) { 26309ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman VarInfo &VRInfo = getVarInfo(MO.getReg()); 26409ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman 26509ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman // Only mark it alive only in the block we are representing... 26609ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman MarkVirtRegAliveInBlock(VRInfo, MBB); 26709ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman break; // Found the PHI entry for this block... 26809ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman } 26909ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman } 27092bc3bc11c2d439264b1cf9e7fc5bc79f4215a54Chris Lattner } 271bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 272bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 273bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 274bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Loop over PhysRegInfo, killing any registers that are available at the 275bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // end of the basic block. This also resets the PhysRegInfo map. 27696aef893383a6ffcc6d6955c5d969f0fd57831c2Chris Lattner for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) 277bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner if (PhysRegInfo[i]) 27809ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman HandlePhysRegDef(i, 0); 279bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 280bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 281bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Convert the information we have gathered into VirtRegInfo and transform it 282bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // into a form usable by RegistersKilled. 283bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 284bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i) 285bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (unsigned j = 0, e = VirtRegInfo[i].Kills.size(); j != e; ++j) { 28674de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst) 28774de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner RegistersDead.insert(std::make_pair(VirtRegInfo[i].Kills[j], 28809ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman i + MRegisterInfo::FirstVirtualRegister)); 289bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 290bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner else 29174de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner RegistersKilled.insert(std::make_pair(VirtRegInfo[i].Kills[j], 29209ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman i + MRegisterInfo::FirstVirtualRegister)); 293bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 294a5287a63762fbf0976e333fb7787ec135fdc2061Chris Lattner 2959fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner // Check to make sure there are no unreachable blocks in the MC CFG for the 2969fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner // function. If so, it is due to a bug in the instruction selector or some 2979fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner // other part of the code generator if this happens. 2989fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner#ifndef NDEBUG 2999fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner for(MachineFunction::iterator i = MF.begin(), e = MF.end(); i != e; ++i) 3009fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 3019fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner#endif 3029fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner 303bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return false; 304bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 3055ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner 3065ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner/// instructionChanged - When the address of an instruction changes, this 3075ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner/// method should be called so that live variables can update its internal 3085ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner/// data structures. This removes the records for OldMI, transfering them to 3095ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner/// the records for NewMI. 3105ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattnervoid LiveVariables::instructionChanged(MachineInstr *OldMI, 3115ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner MachineInstr *NewMI) { 3125ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner // If the instruction defines any virtual registers, update the VarInfo for 3135ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner // the instruction. 314a8db01ac8353f00b519211e6e9e7d53feb1b2923Alkis Evlogimenos for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { 315a8db01ac8353f00b519211e6e9e7d53feb1b2923Alkis Evlogimenos MachineOperand &MO = OldMI->getOperand(i); 31671e353ed3530a5da48c3dd3257c410f6c4ce2e3eAlkis Evlogimenos if (MO.isRegister() && MO.isDef() && MO.getReg() && 3175ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner MRegisterInfo::isVirtualRegister(MO.getReg())) { 3185ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner unsigned Reg = MO.getReg(); 3195ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner VarInfo &VI = getVarInfo(Reg); 3205ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner if (VI.DefInst == OldMI) 321a8db01ac8353f00b519211e6e9e7d53feb1b2923Alkis Evlogimenos VI.DefInst = NewMI; 3225ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner } 3235ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner } 3245ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner 3255ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner // Move the killed information over... 3265ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner killed_iterator I, E; 3275ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner tie(I, E) = killed_range(OldMI); 328a96478d7d6b2aee1aecad4af23506167ec16752cChris Lattner std::vector<unsigned> Regs; 3295ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner for (killed_iterator A = I; A != E; ++A) 330a96478d7d6b2aee1aecad4af23506167ec16752cChris Lattner Regs.push_back(A->second); 3315ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner RegistersKilled.erase(I, E); 3325ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner 333a96478d7d6b2aee1aecad4af23506167ec16752cChris Lattner for (unsigned i = 0, e = Regs.size(); i != e; ++i) 334a96478d7d6b2aee1aecad4af23506167ec16752cChris Lattner RegistersKilled.insert(std::make_pair(NewMI, Regs[i])); 335a96478d7d6b2aee1aecad4af23506167ec16752cChris Lattner Regs.clear(); 336a96478d7d6b2aee1aecad4af23506167ec16752cChris Lattner 3375ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner // Move the dead information over... 3385ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner tie(I, E) = dead_range(OldMI); 3395ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner for (killed_iterator A = I; A != E; ++A) 340a96478d7d6b2aee1aecad4af23506167ec16752cChris Lattner Regs.push_back(A->second); 3415ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner RegistersDead.erase(I, E); 342a96478d7d6b2aee1aecad4af23506167ec16752cChris Lattner 343a96478d7d6b2aee1aecad4af23506167ec16752cChris Lattner for (unsigned i = 0, e = Regs.size(); i != e; ++i) 344a96478d7d6b2aee1aecad4af23506167ec16752cChris Lattner RegistersDead.insert(std::make_pair(NewMI, Regs[i])); 3455ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner} 346