1bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner//===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// 2edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 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// 1716d6eae08209251a31dae638908c79bd39620c91Lang Hames// This class computes live variables using a 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" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DepthFirstIterator.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallPtrSet.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallSet.h" 34bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/MachineInstr.h" 3584bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 36bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson#include "llvm/CodeGen/Passes.h" 371d44df6afe6f9e722a8c7be4a0fbcd9163d9a379David Greene#include "llvm/Support/Debug.h" 38d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/ErrorHandling.h" 393501feab811c86c9659248a4875fc31a3165f84dChris Lattner#include "llvm/Target/TargetInstrInfo.h" 40bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/Target/TargetMachine.h" 41657b4d1ac6a64d8751ed8c53d662201dab4438e1Chris Lattner#include <algorithm> 4249a5aaacef127970f91648ac468de1cd2b6f462fChris Lattnerusing namespace llvm; 43d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 441997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveVariables::ID = 0; 458dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trickchar &llvm::LiveVariablesID = LiveVariables::ID; 462ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LiveVariables, "livevars", 472ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Live Variable Analysis", false, false) 482ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElim) 492ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LiveVariables, "livevars", 50ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Live Variable Analysis", false, false) 51bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 52bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 53bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Andersonvoid LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const { 54bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson AU.addRequiredID(UnreachableMachineBlockElimID); 55bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson AU.setPreservesAll(); 56ad2afc2a421a0e41603d5eee412d4d8c77e9bc1cDan Gohman MachineFunctionPass::getAnalysisUsage(AU); 57bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson} 58bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 59f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund OlesenMachineInstr * 60f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund OlesenLiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const { 61f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (unsigned i = 0, e = Kills.size(); i != e; ++i) 62f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen if (Kills[i]->getParent() == MBB) 63f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen return Kills[i]; 64f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen return NULL; 65f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen} 66f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 67dacceef2666d37eb984c6f5e0a84cdabab8dfffcChris Lattnervoid LiveVariables::VarInfo::dump() const { 68b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 691d44df6afe6f9e722a8c7be4a0fbcd9163d9a379David Greene dbgs() << " Alive in blocks: "; 70493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin for (SparseBitVector<>::iterator I = AliveBlocks.begin(), 71493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin E = AliveBlocks.end(); I != E; ++I) 721d44df6afe6f9e722a8c7be4a0fbcd9163d9a379David Greene dbgs() << *I << ", "; 731d44df6afe6f9e722a8c7be4a0fbcd9163d9a379David Greene dbgs() << "\n Killed by:"; 74dacceef2666d37eb984c6f5e0a84cdabab8dfffcChris Lattner if (Kills.empty()) 751d44df6afe6f9e722a8c7be4a0fbcd9163d9a379David Greene dbgs() << " No instructions.\n"; 76dacceef2666d37eb984c6f5e0a84cdabab8dfffcChris Lattner else { 77dacceef2666d37eb984c6f5e0a84cdabab8dfffcChris Lattner for (unsigned i = 0, e = Kills.size(); i != e; ++i) 781d44df6afe6f9e722a8c7be4a0fbcd9163d9a379David Greene dbgs() << "\n #" << i << ": " << *Kills[i]; 791d44df6afe6f9e722a8c7be4a0fbcd9163d9a379David Greene dbgs() << "\n"; 80dacceef2666d37eb984c6f5e0a84cdabab8dfffcChris Lattner } 8177e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 82dacceef2666d37eb984c6f5e0a84cdabab8dfffcChris Lattner} 83dacceef2666d37eb984c6f5e0a84cdabab8dfffcChris Lattner 8490a3868fe5702caaa56082cde2edb6521de73e01Bill Wendling/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg. 85fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris LattnerLiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 866f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(RegIdx) && 87fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner "getVarInfo: not a virtual register!"); 88b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen VirtRegInfo.grow(RegIdx); 89493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin return VirtRegInfo[RegIdx]; 90fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner} 91fb2cb69dc55c1e1d7754186cd1c8a9d543f54bddChris Lattner 9240a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Andersonvoid LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, 9340a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MachineBasicBlock *DefBlock, 9456184904cd9a348920de0c3b391d42b691091137Evan Cheng MachineBasicBlock *MBB, 9556184904cd9a348920de0c3b391d42b691091137Evan Cheng std::vector<MachineBasicBlock*> &WorkList) { 968ba9771549bcff6109ad45ff3944a1b6c3c54b46Chris Lattner unsigned BBNum = MBB->getNumber(); 978247e0dca6759d9a22ac4c5cf305fac052b285acAndrew Trick 98bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Check to see if this basic block is one of the killing blocks. If so, 9990a3868fe5702caaa56082cde2edb6521de73e01Bill Wendling // remove it. 100bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 10174de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner if (VRInfo.Kills[i]->getParent() == MBB) { 102bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 103bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner break; 104bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 1058247e0dca6759d9a22ac4c5cf305fac052b285acAndrew Trick 10640a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson if (MBB == DefBlock) return; // Terminate recursion 107bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 108493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin if (VRInfo.AliveBlocks.test(BBNum)) 109bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return; // We already know the block is live 110bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 111bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Mark the variable known alive in this bb 112493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin VRInfo.AliveBlocks.set(BBNum); 113bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 1149ab3dbe617af06627fed2455c93ab9dc6b459951Jakob Stoklund Olesen assert(MBB != &MF->front() && "Can't find reaching def for virtreg"); 115f337fb2fa8be9100f469650f1e32e8474525672fBenjamin Kramer WorkList.insert(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend()); 116bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 117bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 118420cdebbcb95f3881ab3518fd3bb670837669e43Bill Wendlingvoid LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 11940a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MachineBasicBlock *DefBlock, 12056184904cd9a348920de0c3b391d42b691091137Evan Cheng MachineBasicBlock *MBB) { 12156184904cd9a348920de0c3b391d42b691091137Evan Cheng std::vector<MachineBasicBlock*> WorkList; 12240a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList); 123420cdebbcb95f3881ab3518fd3bb670837669e43Bill Wendling 12456184904cd9a348920de0c3b391d42b691091137Evan Cheng while (!WorkList.empty()) { 12556184904cd9a348920de0c3b391d42b691091137Evan Cheng MachineBasicBlock *Pred = WorkList.back(); 12656184904cd9a348920de0c3b391d42b691091137Evan Cheng WorkList.pop_back(); 12740a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList); 12856184904cd9a348920de0c3b391d42b691091137Evan Cheng } 12956184904cd9a348920de0c3b391d42b691091137Evan Cheng} 13056184904cd9a348920de0c3b391d42b691091137Evan Cheng 1317047dd4d227b5fb2e5ae0cb2e7d5de1d0098ad60Owen Andersonvoid LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, 13209ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman MachineInstr *MI) { 133ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng assert(MRI->getVRegDef(reg) && "Register use before def!"); 1342e58a410896ffbee3d856b113c3718bc4a5462e8Alkis Evlogimenos 135a018540807775703d630e9c92f9d8013d545599eOwen Anderson unsigned BBNum = MBB->getNumber(); 136a018540807775703d630e9c92f9d8013d545599eOwen Anderson 1377047dd4d227b5fb2e5ae0cb2e7d5de1d0098ad60Owen Anderson VarInfo& VRInfo = getVarInfo(reg); 138c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng 13990a3868fe5702caaa56082cde2edb6521de73e01Bill Wendling // Check to see if this basic block is already a kill block. 14074de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 14190a3868fe5702caaa56082cde2edb6521de73e01Bill Wendling // Yes, this register is killed in this basic block already. Increase the 142bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // live range by updating the kill instruction. 14374de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner VRInfo.Kills.back() = MI; 144bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return; 145bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 146bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 147bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#ifndef NDEBUG 148bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 14974de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 150bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#endif 151bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 152ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // This situation can occur: 153ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // 154ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // ,------. 155ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // | | 156ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // | v 157ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // | t2 = phi ... t1 ... 158ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // | | 159ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // | v 160ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // | t1 = ... 161ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // | ... = ... t1 ... 162ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // | | 163ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // `------' 164ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // 165ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // where there is a use in a PHI node that's a predecessor to the defining 166ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // block. We don't want to mark all predecessors as having the value "alive" 167ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling // in this case. 168ebcba612b537f45a033ccd9a60bee0c45e2e2dedBill Wendling if (MBB == MRI->getVRegDef(reg)->getParent()) return; 169bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 17090a3868fe5702caaa56082cde2edb6521de73e01Bill Wendling // Add a new kill entry for this basic block. If this virtual register is 17190a3868fe5702caaa56082cde2edb6521de73e01Bill Wendling // already marked as alive in this basic block, that means it is alive in at 17290a3868fe5702caaa56082cde2edb6521de73e01Bill Wendling // least one of the successor blocks, it's not a kill. 173493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin if (!VRInfo.AliveBlocks.test(BBNum)) 174e2ee99620fa6e428292737349d8e28bbcdcdaa0bEvan Cheng VRInfo.Kills.push_back(MI); 175bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 176420cdebbcb95f3881ab3518fd3bb670837669e43Bill Wendling // Update all dominating blocks to mark them as "known live". 177f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 178f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner E = MBB->pred_end(); PI != E; ++PI) 179ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI); 180bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 181bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 1823bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohmanvoid LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr *MI) { 1833bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohman VarInfo &VRInfo = getVarInfo(Reg); 1843bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohman 185493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin if (VRInfo.AliveBlocks.empty()) 1863bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohman // If vr is not alive in any block, then defaults to dead. 1873bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohman VRInfo.Kills.push_back(MI); 1883bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohman} 1893bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohman 1900d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng/// FindLastPartialDef - Return the last partial def of the specified register. 19160c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng/// Also returns the sub-registers that're defined by the instruction. 1920d4bdde3270a8ed182a685a580031d6d5d743164Evan ChengMachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, 19360c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng SmallSet<unsigned,4> &PartDefRegs) { 1940d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng unsigned LastDefReg = 0; 1950d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng unsigned LastDefDist = 0; 1960d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng MachineInstr *LastDef = NULL; 197396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 198396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned SubReg = *SubRegs; 1990d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng MachineInstr *Def = PhysRegDef[SubReg]; 2000d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng if (!Def) 2010d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng continue; 2020d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng unsigned Dist = DistanceMap[Def]; 2030d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng if (Dist > LastDefDist) { 2040d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng LastDefReg = SubReg; 2050d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng LastDef = Def; 2060d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng LastDefDist = Dist; 2070d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } 2080d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } 20960c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng 21060c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng if (!LastDef) 21160c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng return 0; 21260c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng 21360c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng PartDefRegs.insert(LastDefReg); 21460c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) { 21560c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng MachineOperand &MO = LastDef->getOperand(i); 21660c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0) 21760c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng continue; 21860c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng unsigned DefReg = MO.getReg(); 21960c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng if (TRI->isSubRegister(Reg, DefReg)) { 2205cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier for (MCSubRegIterator SubRegs(DefReg, TRI, /*IncludeSelf=*/true); 2215cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier SubRegs.isValid(); ++SubRegs) 222396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen PartDefRegs.insert(*SubRegs); 22360c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng } 22460c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng } 2250d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng return LastDef; 2260d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng} 2270d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng 2286d794746b7ae1ed531f08c04dd29d79c13b35075Bill Wendling/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add 2296d794746b7ae1ed531f08c04dd29d79c13b35075Bill Wendling/// implicit defs to a machine instruction if there was an earlier def of its 2306d794746b7ae1ed531f08c04dd29d79c13b35075Bill Wendling/// super-register. 231bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnervoid LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { 232236490d870c2734203ecf26c8f104d0b3283e69eEvan Cheng MachineInstr *LastDef = PhysRegDef[Reg]; 2330d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // If there was a previous use or a "full" def all is well. 234236490d870c2734203ecf26c8f104d0b3283e69eEvan Cheng if (!LastDef && !PhysRegUse[Reg]) { 2350d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // Otherwise, the last sub-register def implicitly defines this register. 2360d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // e.g. 2370d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // AH = 2380d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // AL = ... <imp-def EAX>, <imp-kill AH> 2390d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // = AH 2400d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // ... 2410d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // = EAX 2420d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // All of the sub-registers must have been defined before the use of Reg! 24360c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng SmallSet<unsigned, 4> PartDefRegs; 24460c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs); 2450d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // If LastPartialDef is NULL, it must be using a livein register. 2460d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng if (LastPartialDef) { 2470d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, 2480d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng true/*IsImp*/)); 2490d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng PhysRegDef[Reg] = LastPartialDef; 250bbf55832831482a73fa59fcd1746f9272e82a144Owen Anderson SmallSet<unsigned, 8> Processed; 251396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 252396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned SubReg = *SubRegs; 2530d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng if (Processed.count(SubReg)) 2540d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng continue; 25560c7df2c9311fc35ab02f1600419e91d55d5b133Evan Cheng if (PartDefRegs.count(SubReg)) 2560d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng continue; 2570d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // This part of Reg was defined before the last partial def. It's killed 2580d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // here. 2590d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg, 2600d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng false/*IsDef*/, 2610d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng true/*IsImp*/)); 2620d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng PhysRegDef[SubReg] = LastPartialDef; 263396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS) 2640d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng Processed.insert(*SS); 2650d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } 2660d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } 267bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng } else if (LastDef && !PhysRegUse[Reg] && 268bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng !LastDef->findRegisterDefOperand(Reg)) 269236490d870c2734203ecf26c8f104d0b3283e69eEvan Cheng // Last def defines the super register, add an implicit def of reg. 270bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng LastDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, 271bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng true/*IsImp*/)); 27290a3868fe5702caaa56082cde2edb6521de73e01Bill Wendling 2730d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // Remember this use. 2745cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 2755cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier SubRegs.isValid(); ++SubRegs) 276396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen PhysRegUse[*SubRegs] = MI; 2774efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng} 2784efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng 279a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng/// FindLastRefOrPartRef - Return the last reference or partial reference of 280a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng/// the specified register. 281a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan ChengMachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) { 282a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng MachineInstr *LastDef = PhysRegDef[Reg]; 283a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng MachineInstr *LastUse = PhysRegUse[Reg]; 284a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng if (!LastDef && !LastUse) 28598cdfc779df1d8d9a0071103af13f43ba65504c2Chris Lattner return 0; 286a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng 287a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; 288a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; 289a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng unsigned LastPartDefDist = 0; 290396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 291396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned SubReg = *SubRegs; 292a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng MachineInstr *Def = PhysRegDef[SubReg]; 293a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng if (Def && Def != LastDef) { 294a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng // There was a def of this sub-register in between. This is a partial 295a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng // def, keep track of the last one. 296a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng unsigned Dist = DistanceMap[Def]; 297e7078aed24d81c0b4bacb41385ea0237d1c0caf0Benjamin Kramer if (Dist > LastPartDefDist) 298a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng LastPartDefDist = Dist; 299e7078aed24d81c0b4bacb41385ea0237d1c0caf0Benjamin Kramer } else if (MachineInstr *Use = PhysRegUse[SubReg]) { 300a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng unsigned Dist = DistanceMap[Use]; 301a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng if (Dist > LastRefOrPartRefDist) { 302a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng LastRefOrPartRefDist = Dist; 303a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng LastRefOrPartRef = Use; 304a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng } 305a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng } 306a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng } 307a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng 308a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng return LastRefOrPartRef; 309a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng} 310a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng 311a894ae130b6e69a367aa691eec7e96973a20e901Evan Chengbool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { 312ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng MachineInstr *LastDef = PhysRegDef[Reg]; 313ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng MachineInstr *LastUse = PhysRegUse[Reg]; 314ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng if (!LastDef && !LastUse) 3150d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng return false; 3160d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng 317ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; 3180d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; 3190d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // The whole register is used. 3200d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // AL = 3210d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // AH = 3220d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // 3230d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // = AX 3240d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // = AL, AX<imp-use, kill> 3250d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // AX = 3260d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // 3270d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // Or whole register is defined, but not used at all. 3280d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // AX<dead> = 3290d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // ... 3300d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // AX = 3310d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // 3320d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // Or whole register is defined, but only partly used. 3330d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // AX<dead> = AL<imp-def> 3340d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // = AL<kill> 3358247e0dca6759d9a22ac4c5cf305fac052b285acAndrew Trick // AX = 336ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng MachineInstr *LastPartDef = 0; 337ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng unsigned LastPartDefDist = 0; 338bbf55832831482a73fa59fcd1746f9272e82a144Owen Anderson SmallSet<unsigned, 8> PartUses; 339396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 340396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned SubReg = *SubRegs; 341ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng MachineInstr *Def = PhysRegDef[SubReg]; 342ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng if (Def && Def != LastDef) { 343ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng // There was a def of this sub-register in between. This is a partial 344ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng // def, keep track of the last one. 345ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng unsigned Dist = DistanceMap[Def]; 346ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng if (Dist > LastPartDefDist) { 347ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng LastPartDefDist = Dist; 348ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng LastPartDef = Def; 349ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng } 350ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng continue; 351ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng } 3520d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng if (MachineInstr *Use = PhysRegUse[SubReg]) { 3535cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); SS.isValid(); 3545cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier ++SS) 3550d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng PartUses.insert(*SS); 3560d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng unsigned Dist = DistanceMap[Use]; 3570d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng if (Dist > LastRefOrPartRefDist) { 3580d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng LastRefOrPartRefDist = Dist; 3590d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng LastRefOrPartRef = Use; 3600d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } 3610d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } 3620d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } 363a894ae130b6e69a367aa691eec7e96973a20e901Evan Cheng 36453e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen if (!PhysRegUse[Reg]) { 365ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng // Partial uses. Mark register def dead and add implicit def of 366ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng // sub-registers which are used. 367ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng // EAX<dead> = op AL<imp-def> 368ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng // That is, EAX def is dead but AL def extends pass it. 3690d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true); 370396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 371396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned SubReg = *SubRegs; 372ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng if (!PartUses.count(SubReg)) 373ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng continue; 374ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng bool NeedDef = true; 375ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng if (PhysRegDef[Reg] == PhysRegDef[SubReg]) { 376ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng MachineOperand *MO = PhysRegDef[Reg]->findRegisterDefOperand(SubReg); 377ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng if (MO) { 378ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng NeedDef = false; 379ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng assert(!MO->isDead()); 3802c4d96dfe9c309cc6b206c7d2cf03fe9fbd8aa93Evan Cheng } 3810d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } 382ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng if (NeedDef) 383ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg, 384ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng true/*IsDef*/, true/*IsImp*/)); 385a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg); 386a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng if (LastSubRef) 387a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng LastSubRef->addRegisterKilled(SubReg, TRI, true); 388a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng else { 389a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); 3905cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); 3915cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier SS.isValid(); ++SS) 392396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen PhysRegUse[*SS] = LastRefOrPartRef; 393a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng } 394396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS) 395ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng PartUses.erase(*SS); 3960d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } 39753e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) { 39853e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen if (LastPartDef) 39953e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen // The last partial def kills the register. 40053e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, 40153e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen true/*IsImp*/, true/*IsKill*/)); 40253e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen else { 40353e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen MachineOperand *MO = 40453e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen LastRefOrPartRef->findRegisterDefOperand(Reg, false, TRI); 40553e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg; 40653e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen // If the last reference is the last def, then it's not used at all. 40753e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen // That is, unless we are currently processing the last reference itself. 40853e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen LastRefOrPartRef->addRegisterDead(Reg, TRI, true); 40953e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen if (NeedEC) { 41053e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen // If we are adding a subreg def and the superreg def is marked early 41153e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen // clobber, add an early clobber marker to the subreg def. 41253e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen MO = LastRefOrPartRef->findRegisterDefOperand(Reg); 41353e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen if (MO) 41453e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen MO->setIsEarlyClobber(); 41553e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen } 41653e000bac319a25f7c13ec8b7b413418fba5ef20Jakob Stoklund Olesen } 417ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng } else 4180d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng LastRefOrPartRef->addRegisterKilled(Reg, TRI, true); 4190d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng return true; 4200d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng} 4210d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng 4228c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesenvoid LiveVariables::HandleRegMask(const MachineOperand &MO) { 4238c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen // Call HandlePhysRegKill() for all live registers clobbered by Mask. 4248c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen // Clobbered registers are always dead, sp there is no need to use 4258c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen // HandlePhysRegDef(). 4268c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen for (unsigned Reg = 1, NumRegs = TRI->getNumRegs(); Reg != NumRegs; ++Reg) { 4278c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen // Skip dead regs. 4288c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen if (!PhysRegDef[Reg] && !PhysRegUse[Reg]) 4298c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen continue; 4308c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen // Skip mask-preserved regs. 4317423db2dcf3434e74456e379751459f0d579da46Evan Cheng if (!MO.clobbersPhysReg(Reg)) 4328c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen continue; 4338c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen // Kill the largest clobbered super-register. 4348c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen // This avoids needless implicit operands. 4358c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen unsigned Super = Reg; 436396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) 4378c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen if ((PhysRegDef[*SR] || PhysRegUse[*SR]) && MO.clobbersPhysReg(*SR)) 4388c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen Super = *SR; 4398c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen HandlePhysRegKill(Super, 0); 4408c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen } 4418c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen} 4428c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen 443296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Chengvoid LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI, 4449e639e8fd95488cb4c8ef2f7f3a41919acb29ac4Craig Topper SmallVectorImpl<unsigned> &Defs) { 4450d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // What parts of the register are previously defined? 446bffdf66b8050b45188cb265f27e81c41277ab0caOwen Anderson SmallSet<unsigned, 32> Live; 4470d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng if (PhysRegDef[Reg] || PhysRegUse[Reg]) { 4485cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 4495cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier SubRegs.isValid(); ++SubRegs) 450396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen Live.insert(*SubRegs); 4510d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } else { 452396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 453396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned SubReg = *SubRegs; 4540d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // If a register isn't itself defined, but all parts that make up of it 4550d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // are defined, then consider it also defined. 4560d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // e.g. 4570d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // AL = 4580d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // AH = 4590d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // = AX 460ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng if (Live.count(SubReg)) 461ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng continue; 4620d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) { 4635cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); 4645cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier SS.isValid(); ++SS) 4650d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng Live.insert(*SS); 4664efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng } 467420cdebbcb95f3881ab3518fd3bb670837669e43Bill Wendling } 468bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 46924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 4700d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // Start from the largest piece, find the last time any part of the register 4710d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // is referenced. 472ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng HandlePhysRegKill(Reg, MI); 473ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng // Only some of the sub-registers are used. 474396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 475396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned SubReg = *SubRegs; 476ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng if (!Live.count(SubReg)) 477ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng // Skip if this sub-register isn't defined. 478ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng continue; 479ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng HandlePhysRegKill(SubReg, MI); 48024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 48124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 482ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng if (MI) 483ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng Defs.push_back(Reg); // Remember this def. 484296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng} 485296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng 486296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Chengvoid LiveVariables::UpdatePhysRegDefs(MachineInstr *MI, 4879e639e8fd95488cb4c8ef2f7f3a41919acb29ac4Craig Topper SmallVectorImpl<unsigned> &Defs) { 488296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng while (!Defs.empty()) { 489296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng unsigned Reg = Defs.back(); 490296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng Defs.pop_back(); 4915cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 4925cc3c989fc4295103ee46a2697e82dc1c4453545Chad Rosier SubRegs.isValid(); ++SubRegs) { 493396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned SubReg = *SubRegs; 4940d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng PhysRegDef[SubReg] = MI; 4950d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng PhysRegUse[SubReg] = NULL; 4964efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng } 49719b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos } 498bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 499bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 500c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Chengbool LiveVariables::runOnMachineFunction(MachineFunction &mf) { 501c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng MF = &mf; 502ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng MRI = &mf.getRegInfo(); 5036130f66eaae89f8878590796977678afa8448926Evan Cheng TRI = MF->getTarget().getRegisterInfo(); 50496aef893383a6ffcc6d6955c5d969f0fd57831c2Chris Lattner 5056130f66eaae89f8878590796977678afa8448926Evan Cheng unsigned NumRegs = TRI->getNumRegs(); 5060d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng PhysRegDef = new MachineInstr*[NumRegs]; 5070d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng PhysRegUse = new MachineInstr*[NumRegs]; 508e96f50142e8d12a2e12c3329bffb372e09731dd2Evan Cheng PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()]; 5090d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 5100d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 511dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen PHIJoins.clear(); 512bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 5138dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick // FIXME: LiveIntervals will be updated to remove its dependence on 5148dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick // LiveVariables to improve compilation time and eliminate bizarre pass 5158dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick // dependencies. Until then, we can't change much in -O0. 5168dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick if (!MRI->isSSA()) 5178dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick report_fatal_error("regalloc=... not currently supported with -O0"); 5188dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick 519c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng analyzePHINodes(mf); 520f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling 521bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Calculate live variable information in depth first order on the CFG of the 522bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // function. This guarantees that we will see the definition of a virtual 523bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // register before its uses due to dominance properties of SSA (except for PHI 524bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // nodes, which are treated as a special case). 525c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng MachineBasicBlock *Entry = MF->begin(); 526041040717db7dafe31155615fcb43d214ac88aa4Evan Cheng SmallPtrSet<MachineBasicBlock*,16> Visited; 5276d794746b7ae1ed531f08c04dd29d79c13b35075Bill Wendling 528041040717db7dafe31155615fcb43d214ac88aa4Evan Cheng for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 529041040717db7dafe31155615fcb43d214ac88aa4Evan Cheng DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 530041040717db7dafe31155615fcb43d214ac88aa4Evan Cheng DFI != E; ++DFI) { 531f25fb4bc640340c60793a3e2bbf2510dea0e15f4Chris Lattner MachineBasicBlock *MBB = *DFI; 532bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 533b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Mark live-in registers as live-in. 534296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng SmallVector<unsigned, 4> Defs; 53581bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator II = MBB->livein_begin(), 5360c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng EE = MBB->livein_end(); II != EE; ++II) { 5376f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isPhysicalRegister(*II) && 5380c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng "Cannot have a live-in virtual register!"); 539ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng HandlePhysRegDef(*II, 0, Defs); 5400c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng } 5410c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 542bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Loop over all of the instructions, processing them. 543ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng DistanceMap.clear(); 544ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng unsigned Dist = 0; 545bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 54609ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman I != E; ++I) { 547c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineInstr *MI = I; 548518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isDebugValue()) 549d94998f52574eacef148bd856de701af2c594b03Dale Johannesen continue; 550ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng DistanceMap.insert(std::make_pair(MI, Dist++)); 551bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 552bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Process all of the operands of the instruction... 553bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner unsigned NumOperandsToProcess = MI->getNumOperands(); 554bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 555bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Unless it is a PHI node. In this case, ONLY process the DEF, not any 556bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // of the uses. They will be handled in other basic blocks. 557518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isPHI()) 55809ba906cf55b165550aecefbd6286939be84b8d1Misha Brukman NumOperandsToProcess = 1; 559bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 560d05e8055362be52fc33dcc685ba2ae5c722506b5Evan Cheng // Clear kill and dead markers. LV will recompute them. 5610d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng SmallVector<unsigned, 4> UseRegs; 5620d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng SmallVector<unsigned, 4> DefRegs; 5638c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen SmallVector<unsigned, 1> RegMasks; 564bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 565d05e8055362be52fc33dcc685ba2ae5c722506b5Evan Cheng MachineOperand &MO = MI->getOperand(i); 5668c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen if (MO.isRegMask()) { 5678c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen RegMasks.push_back(i); 5688c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen continue; 5698c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen } 570a894ae130b6e69a367aa691eec7e96973a20e901Evan Cheng if (!MO.isReg() || MO.getReg() == 0) 571a894ae130b6e69a367aa691eec7e96973a20e901Evan Cheng continue; 572a894ae130b6e69a367aa691eec7e96973a20e901Evan Cheng unsigned MOReg = MO.getReg(); 573d05e8055362be52fc33dcc685ba2ae5c722506b5Evan Cheng if (MO.isUse()) { 574d05e8055362be52fc33dcc685ba2ae5c722506b5Evan Cheng MO.setIsKill(false); 5757806c0778f22552ebe6711f3dc43887dc6097bfcJakob Stoklund Olesen if (MO.readsReg()) 5767806c0778f22552ebe6711f3dc43887dc6097bfcJakob Stoklund Olesen UseRegs.push_back(MOReg); 577d05e8055362be52fc33dcc685ba2ae5c722506b5Evan Cheng } else /*MO.isDef()*/ { 578d05e8055362be52fc33dcc685ba2ae5c722506b5Evan Cheng MO.setIsDead(false); 579a894ae130b6e69a367aa691eec7e96973a20e901Evan Cheng DefRegs.push_back(MOReg); 580d05e8055362be52fc33dcc685ba2ae5c722506b5Evan Cheng } 581bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 582bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 5830d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // Process all uses. 5840d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { 5850d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng unsigned MOReg = UseRegs[i]; 5860d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng if (TargetRegisterInfo::isVirtualRegister(MOReg)) 5870d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng HandleVirtRegUse(MOReg, MBB, MI); 588fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen else if (!MRI->isReserved(MOReg)) 5890d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng HandlePhysRegUse(MOReg, MI); 5900d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng } 59190a3868fe5702caaa56082cde2edb6521de73e01Bill Wendling 5928c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen // Process all masked registers. (Call clobbers). 5938c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen for (unsigned i = 0, e = RegMasks.size(); i != e; ++i) 5948c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen HandleRegMask(MI->getOperand(RegMasks[i])); 5958c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen 5960d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // Process all defs. 5970d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { 5980d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng unsigned MOReg = DefRegs[i]; 5993bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohman if (TargetRegisterInfo::isVirtualRegister(MOReg)) 6003bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohman HandleVirtRegDef(MOReg, MI); 601fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen else if (!MRI->isReserved(MOReg)) 602ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng HandlePhysRegDef(MOReg, MI, Defs); 603bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 604296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng UpdatePhysRegDefs(MI, Defs); 605bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 606bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 607bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Handle any virtual assignments from PHI nodes which might be at the 608bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // bottom of this basic block. We check all of our successor blocks to see 609bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // if they have PHI nodes, and if so, we simulate an assignment at the end 610bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // of the current block. 611e96f50142e8d12a2e12c3329bffb372e09731dd2Evan Cheng if (!PHIVarInfo[MBB->getNumber()].empty()) { 612f22fd3f7b557a967b1edc1fa9ae770006a39e97cCraig Topper SmallVectorImpl<unsigned> &VarInfoVec = PHIVarInfo[MBB->getNumber()]; 6134efeab208cf0fe7ae2f68bcdd1264a8fdb18826cChris Lattner 614f22fd3f7b557a967b1edc1fa9ae770006a39e97cCraig Topper for (SmallVectorImpl<unsigned>::iterator I = VarInfoVec.begin(), 615420cdebbcb95f3881ab3518fd3bb670837669e43Bill Wendling E = VarInfoVec.end(); I != E; ++I) 616420cdebbcb95f3881ab3518fd3bb670837669e43Bill Wendling // Mark it alive only in the block we are representing. 617ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), 61840a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MBB); 619bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 620edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 621bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng // MachineCSE may CSE instructions which write to non-allocatable physical 622bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng // registers across MBBs. Remember if any reserved register is liveout. 623bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng SmallSet<unsigned, 4> LiveOuts; 624bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), 625bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng SE = MBB->succ_end(); SI != SE; ++SI) { 626bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng MachineBasicBlock *SuccMBB = *SI; 627bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng if (SuccMBB->isLandingPad()) 628bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng continue; 629bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng for (MachineBasicBlock::livein_iterator LI = SuccMBB->livein_begin(), 630bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng LE = SuccMBB->livein_end(); LI != LE; ++LI) { 631bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng unsigned LReg = *LI; 632bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng if (!TRI->isInAllocatableClass(LReg)) 633bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng // Ignore other live-ins, e.g. those that are live into landing pads. 634bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng LiveOuts.insert(LReg); 635bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng } 636bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng } 637bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng 6380d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // Loop over PhysRegDef / PhysRegUse, killing any registers that are 6390d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // available at the end of the basic block. 640e96f50142e8d12a2e12c3329bffb372e09731dd2Evan Cheng for (unsigned i = 0; i != NumRegs; ++i) 641bfe8afaaec03795fe6c78daa9817e54c186a699dEvan Cheng if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i)) 642ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng HandlePhysRegDef(i, 0, Defs); 64324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 6440d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 6450d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 646bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 647bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 648a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng // Convert and transfer the dead / killed information we have gathered into 649a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng // VirtRegInfo onto MI's. 650b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) { 651b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen const unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 652b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j) 653b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg)) 654b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI); 655bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner else 656b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI); 657b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen } 658a5287a63762fbf0976e333fb7787ec135fdc2061Chris Lattner 6599fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner // Check to make sure there are no unreachable blocks in the MC CFG for the 6609fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner // function. If so, it is due to a bug in the instruction selector or some 6619fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner // other part of the code generator if this happens. 6629fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner#ifndef NDEBUG 663c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i) 6649fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 6659fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner#endif 6669fb6cf1d82617994cd6dad33ecd45c1e913534aaChris Lattner 6670d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng delete[] PhysRegDef; 6680d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng delete[] PhysRegUse; 669e96f50142e8d12a2e12c3329bffb372e09731dd2Evan Cheng delete[] PHIVarInfo; 670e96f50142e8d12a2e12c3329bffb372e09731dd2Evan Cheng 671bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return false; 672bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 6735ed001b6afe2225343ec79f58645a9aaf35c1fd2Chris Lattner 674be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng/// replaceKillInstruction - Update register kill info by replacing a kill 675be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng/// instruction with a new one. 676be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Chengvoid LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI, 677be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng MachineInstr *NewMI) { 678be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng VarInfo &VI = getVarInfo(Reg); 6795b9f60bc22582e80b081d4277a47d8b7fa14e3f4Evan Cheng std::replace(VI.Kills.begin(), VI.Kills.end(), OldMI, NewMI); 680be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng} 681be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng 6827a3abdc63c0cc4e5d5411c3add0e909c6ac49e79Chris Lattner/// removeVirtualRegistersKilled - Remove all killed info for the specified 6837a3abdc63c0cc4e5d5411c3add0e909c6ac49e79Chris Lattner/// instruction. 6847a3abdc63c0cc4e5d5411c3add0e909c6ac49e79Chris Lattnervoid LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { 685a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 686a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng MachineOperand &MO = MI->getOperand(i); 687d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.isKill()) { 688f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner MO.setIsKill(false); 689a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng unsigned Reg = MO.getReg(); 6906f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isVirtualRegister(Reg)) { 691a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng bool removed = getVarInfo(Reg).removeKill(MI); 692a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng assert(removed && "kill not in register's VarInfo?"); 6931f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)removed; 694a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng } 6957a3abdc63c0cc4e5d5411c3add0e909c6ac49e79Chris Lattner } 6967a3abdc63c0cc4e5d5411c3add0e909c6ac49e79Chris Lattner } 6977a3abdc63c0cc4e5d5411c3add0e909c6ac49e79Chris Lattner} 6987a3abdc63c0cc4e5d5411c3add0e909c6ac49e79Chris Lattner 699f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling/// analyzePHINodes - Gather information about the PHI nodes in here. In 7006d794746b7ae1ed531f08c04dd29d79c13b35075Bill Wendling/// particular, we want to map the variable information of a virtual register 7016d794746b7ae1ed531f08c04dd29d79c13b35075Bill Wendling/// which is used in a PHI node. We map that to the BB the vreg is coming from. 702f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling/// 703f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendlingvoid LiveVariables::analyzePHINodes(const MachineFunction& Fn) { 704f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 705f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling I != E; ++I) 706f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 707518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner BBI != BBE && BBI->isPHI(); ++BBI) 708f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 7097806c0778f22552ebe6711f3dc43887dc6097bfcJakob Stoklund Olesen if (BBI->getOperand(i).readsReg()) 7107806c0778f22552ebe6711f3dc43887dc6097bfcJakob Stoklund Olesen PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()] 7117806c0778f22552ebe6711f3dc43887dc6097bfcJakob Stoklund Olesen .push_back(BBI->getOperand(i).getReg()); 712f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling} 713f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 714323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesenbool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB, 715323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen unsigned Reg, 716323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineRegisterInfo &MRI) { 717323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen unsigned Num = MBB.getNumber(); 718323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen 719323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen // Reg is live-through. 720323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen if (AliveBlocks.test(Num)) 721323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen return true; 722323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen 723323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen // Registers defined in MBB cannot be live in. 724323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen const MachineInstr *Def = MRI.getVRegDef(Reg); 725323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen if (Def && Def->getParent() == &MBB) 726323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen return false; 727323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen 728323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen // Reg was not defined in MBB, was it killed here? 729323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen return findKill(&MBB); 730323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen} 731323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen 7328f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesenbool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) { 7338f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen LiveVariables::VarInfo &VI = getVarInfo(Reg); 7348f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen 7358f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen // Loop over all of the successors of the basic block, checking to see if 7368f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen // the value is either live in the block, or if it is killed in the block. 737f337fb2fa8be9100f469650f1e32e8474525672fBenjamin Kramer SmallVector<MachineBasicBlock*, 8> OpSuccBlocks; 7388f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 7398f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen E = MBB.succ_end(); SI != E; ++SI) { 7408f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen MachineBasicBlock *SuccMBB = *SI; 7418f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen 7428f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen // Is it alive in this successor? 7438f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen unsigned SuccIdx = SuccMBB->getNumber(); 7448f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen if (VI.AliveBlocks.test(SuccIdx)) 7458f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen return true; 7468f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen OpSuccBlocks.push_back(SuccMBB); 7478f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen } 7488f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen 7498f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen // Check to see if this value is live because there is a use in a successor 7508f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen // that kills it. 7518f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen switch (OpSuccBlocks.size()) { 7528f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen case 1: { 7538f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen MachineBasicBlock *SuccMBB = OpSuccBlocks[0]; 7548f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) 7558f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen if (VI.Kills[i]->getParent() == SuccMBB) 7568f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen return true; 7578f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen break; 7588f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen } 7598f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen case 2: { 7608f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1]; 7618f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) 7628f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen if (VI.Kills[i]->getParent() == SuccMBB1 || 7638f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen VI.Kills[i]->getParent() == SuccMBB2) 7648f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen return true; 7658f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen break; 7668f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen } 7678f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen default: 7688f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end()); 7698f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) 7708f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), 7718f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen VI.Kills[i]->getParent())) 7728f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen return true; 7738f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen } 7748f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen return false; 7758f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen} 7768f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen 7773e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All 7783e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen/// variables that are live out of DomBB will be marked as passing live through 7793e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen/// BB. 7803e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesenvoid LiveVariables::addNewBlock(MachineBasicBlock *BB, 781323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineBasicBlock *DomBB, 782323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineBasicBlock *SuccBB) { 7833e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen const unsigned NumNew = BB->getNumber(); 784323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen 78511b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer SmallSet<unsigned, 16> Defs, Kills; 78611b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer 78711b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end(); 78811b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer for (; BBI != BBE && BBI->isPHI(); ++BBI) { 78911b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer // Record the def of the PHI node. 79011b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer Defs.insert(BBI->getOperand(0).getReg()); 79111b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer 79211b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer // All registers used by PHI nodes in SuccBB must be live through BB. 793323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 794323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen if (BBI->getOperand(i+1).getMBB() == BB) 795323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew); 79611b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer } 79711b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer 79811b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer // Record all vreg defs and kills of all instructions in SuccBB. 79911b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer for (; BBI != BBE; ++BBI) { 80011b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer for (MachineInstr::mop_iterator I = BBI->operands_begin(), 80111b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer E = BBI->operands_end(); I != E; ++I) { 80211b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer if (I->isReg() && TargetRegisterInfo::isVirtualRegister(I->getReg())) { 80311b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer if (I->isDef()) 80411b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer Defs.insert(I->getReg()); 80511b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer else if (I->isKill()) 80611b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer Kills.insert(I->getReg()); 80711b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer } 80811b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer } 80911b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer } 810f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 811f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen // Update info for all live variables 812b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 813b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 81411b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer 81511b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer // If the Defs is defined in the successor it can't be live in BB. 81611b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer if (Defs.count(Reg)) 81711b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer continue; 81811b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer 81911b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer // If the register is either killed in or live through SuccBB it's also live 82011b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer // through BB. 8213e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen VarInfo &VI = getVarInfo(Reg); 82211b450589978a39e59b77cd074dcda9d5697f174Benjamin Kramer if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber())) 8233e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen VI.AliveBlocks.set(NumNew); 824f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } 825f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen} 826