1db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner//===-- llvm/CodeGen/LiveVariables.h - Live Variable Analysis ---*- C++ -*-===// 2ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 7ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 9ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 1035e9f7d711ad77aec8336073ca843d94f386d498Dan Gohman// This file implements the LiveVariables analysis pass. For each machine 118a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// instruction in the function, this pass calculates the set of registers that 128a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// are immediately dead after the instruction (i.e., the instruction calculates 138a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// the value, but it is never used) and the set of registers that are used by 148a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// the instruction, but are never used after the instruction (i.e., they are 158a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// killed). 168a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// 176326b0d0f862090c288fc3412b51101800288ac6Dan Gohman// This class computes live variables using a sparse implementation based on 18db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner// the machine code SSA form. This class computes live variable information for 198a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// each virtual and _register allocatable_ physical register in a function. It 208a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// uses the dominance properties of SSA form to efficiently compute live 218a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// variables for virtual registers, and assumes that physical registers are only 228a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// live within a single basic block (allowing it to do a single local analysis 238a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// to resolve physical register lifetimes in each basic block). If a physical 248a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// register is not register allocatable, it is not tracked. This is useful for 258a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner// things like the stack pointer and condition codes. 26ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 27db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner//===----------------------------------------------------------------------===// 28db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 29db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner#ifndef LLVM_CODEGEN_LIVEVARIABLES_H 30db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner#define LLVM_CODEGEN_LIVEVARIABLES_H 31db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 3261de82d8853a02fe39c47302432abb70a586704fEvan Cheng#include "llvm/ADT/BitVector.h" 33ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng#include "llvm/ADT/DenseMap.h" 34b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 35dace0ed8c7b33056c533a7e878d600f7eec5fd1cEvan Cheng#include "llvm/ADT/SmallSet.h" 36e96f50142e8d12a2e12c3329bffb372e09731dd2Evan Cheng#include "llvm/ADT/SmallVector.h" 37493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin#include "llvm/ADT/SparseBitVector.h" 38255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/CodeGen/MachineBasicBlock.h" 39255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/CodeGen/MachineFunctionPass.h" 40255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/CodeGen/MachineInstr.h" 41255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 42db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 43d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 44d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 45ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Chengclass MachineRegisterInfo; 466f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohmanclass TargetRegisterInfo; 47db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 48db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattnerclass LiveVariables : public MachineFunctionPass { 49bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattnerpublic: 50ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 51081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson LiveVariables() : MachineFunctionPass(ID) { 52081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLiveVariablesPass(*PassRegistry::getPassRegistry()); 53081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 54794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 5551d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// VarInfo - This represents the regions where a virtual register is live in 56f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// the program. We represent this with three different pieces of 57e8f4ac2b10cc058431f534c53b7f021f492bd9c0Dan Gohman /// information: the set of blocks in which the instruction is live 58e8f4ac2b10cc058431f534c53b7f021f492bd9c0Dan Gohman /// throughout, the set of blocks in which the instruction is actually used, 59e8f4ac2b10cc058431f534c53b7f021f492bd9c0Dan Gohman /// and the set of non-phi instructions that are the last users of the value. 6051d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// 617fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// In the common case where a value is defined and killed in the same block, 627fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// There is one killing instruction, and AliveBlocks is empty. 637fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// 647fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// Otherwise, the value is live out of the block. If the value is live 657fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// throughout any blocks, these blocks are listed in AliveBlocks. Blocks 667fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// where the liveness range ends are not included in AliveBlocks, instead 677fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// being captured by the Kills set. In these blocks, the value is live into 687fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// the block (unless the value is defined and killed in the same block) and 697fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// lives until the specified instruction. Note that there cannot ever be a 707fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// value whose Kills set contains two instructions from the same basic block. 7151d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// 7251d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// PHI nodes complicate things a bit. If a PHI node is the last user of a 7351d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// value in one of its predecessor blocks, it is not listed in the kills set, 7451d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// but does include the predecessor block in the AliveBlocks set (unless that 7551d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// block also defines the value). This leads to the (perfectly sensical) 7651d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// situation where a value is defined in a block, and the last use is a phi 779f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// node in the successor. In this case, AliveBlocks is empty (the value is 789f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// not live across any blocks) and Kills is empty (phi nodes are not 799f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// included). This is sensical because the value must be live to the end of 809f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// the block, but is not live in any successor blocks. 81db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner struct VarInfo { 82e8f4ac2b10cc058431f534c53b7f021f492bd9c0Dan Gohman /// AliveBlocks - Set of blocks in which this value is alive completely 83db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// through. This is a bit set which uses the basic block number as an 84db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// index. 85db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// 86493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin SparseBitVector<> AliveBlocks; 87db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 8874de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner /// Kills - List of MachineInstruction's which are the last use of this 8974de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner /// virtual register (kill it) in their basic block. 90db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// 9174de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner std::vector<MachineInstr*> Kills; 92db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 9371499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// removeKill - Delete a kill corresponding to the specified 9471499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// machine instruction. Returns true if there was a kill 9571499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// corresponding to this instruction, false otherwise. 9671499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos bool removeKill(MachineInstr *MI) { 97fe666a3592b2f59cf67a2f72a148f4db40f34b2fEvan Cheng std::vector<MachineInstr*>::iterator 98fe666a3592b2f59cf67a2f72a148f4db40f34b2fEvan Cheng I = std::find(Kills.begin(), Kills.end(), MI); 99fe666a3592b2f59cf67a2f72a148f4db40f34b2fEvan Cheng if (I == Kills.end()) 100fe666a3592b2f59cf67a2f72a148f4db40f34b2fEvan Cheng return false; 101fe666a3592b2f59cf67a2f72a148f4db40f34b2fEvan Cheng Kills.erase(I); 102fe666a3592b2f59cf67a2f72a148f4db40f34b2fEvan Cheng return true; 103bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner } 104f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 105f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen /// findKill - Find a kill instruction in MBB. Return NULL if none is found. 106f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineInstr *findKill(const MachineBasicBlock *MBB) const; 107f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 108323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// isLiveIn - Is Reg live in to MBB? This means that Reg is live through 109323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// MBB, or it is killed in MBB. If Reg is only used by PHI instructions in 110323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// MBB, it is not considered live in. 111323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen bool isLiveIn(const MachineBasicBlock &MBB, 112323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen unsigned Reg, 113323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineRegisterInfo &MRI); 114323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen 1150df687b1be4a29e0358e6e8710f0c71d5966c43aChris Lattner void dump() const; 116db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner }; 117db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 118bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattnerprivate: 119db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// VirtRegInfo - This list is a mapping from virtual register number to 120b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen /// variable information. 121db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// 122b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen IndexedMap<VarInfo, VirtReg2IndexFunctor> VirtRegInfo; 123db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 124dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// PHIJoins - list of virtual registers that are PHI joins. These registers 125dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// may have multiple definitions, and they require special handling when 126dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// building live intervals. 127dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SparseBitVector<> PHIJoins; 128dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 129db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattnerprivate: // Intermediate data structures 130c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng MachineFunction *MF; 131c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng 132ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng MachineRegisterInfo* MRI; 133ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng 1346130f66eaae89f8878590796977678afa8448926Evan Cheng const TargetRegisterInfo *TRI; 135db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 1360d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // PhysRegInfo - Keep track of which instruction was the last def of a 13724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // physical register. This is a purely local property, because all physical 1385ec3ab7f67ab740681b1ddbba2290da6e7040777Bill Wendling // register references are presumed dead across basic blocks. 1390d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng MachineInstr **PhysRegDef; 14024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 1410d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // PhysRegInfo - Keep track of which instruction was the last use of a 1420d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // physical register. This is a purely local property, because all physical 1430d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // register references are presumed dead across basic blocks. 1440d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng MachineInstr **PhysRegUse; 145f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling 146e96f50142e8d12a2e12c3329bffb372e09731dd2Evan Cheng SmallVector<unsigned, 4> *PHIVarInfo; 147a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng 148ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng // DistanceMap - Keep track the distance of a MI from the start of the 149ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng // current basic block. 150ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng DenseMap<MachineInstr*, unsigned> DistanceMap; 151ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng 1524efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng /// HandlePhysRegKill - Add kills of Reg and its sub-registers to the 1534efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng /// uses. Pay special attention to the sub-register uses which may come below 1544efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng /// the last use of the whole register. 155a894ae130b6e69a367aa691eec7e96973a20e901Evan Cheng bool HandlePhysRegKill(unsigned Reg, MachineInstr *MI); 1560d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng 1578c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen /// HandleRegMask - Call HandlePhysRegKill for all registers clobbered by Mask. 1588c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen void HandleRegMask(const MachineOperand&); 1598c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen 160b08bdc4a161313bb09a73e6c61f0cb0669e291c7Alkis Evlogimenos void HandlePhysRegUse(unsigned Reg, MachineInstr *MI); 161296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng void HandlePhysRegDef(unsigned Reg, MachineInstr *MI, 162ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng SmallVector<unsigned, 4> &Defs); 163296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng void UpdatePhysRegDefs(MachineInstr *MI, SmallVector<unsigned, 4> &Defs); 164b08bdc4a161313bb09a73e6c61f0cb0669e291c7Alkis Evlogimenos 165a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// FindLastRefOrPartRef - Return the last reference or partial reference of 166a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// the specified register. 167a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng MachineInstr *FindLastRefOrPartRef(unsigned Reg); 168a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng 169a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// FindLastPartialDef - Return the last partial def of the specified 170a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// register. Also returns the sub-registers that're defined by the 171a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// instruction. 172dace0ed8c7b33056c533a7e878d600f7eec5fd1cEvan Cheng MachineInstr *FindLastPartialDef(unsigned Reg, 173dace0ed8c7b33056c533a7e878d600f7eec5fd1cEvan Cheng SmallSet<unsigned,4> &PartDefRegs); 1740d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng 175f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// analyzePHINodes - Gather information about the PHI nodes in here. In 176f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// particular, we want to map the variable information of a virtual 177f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// register which is used in a PHI node. We map that to the BB the vreg 178f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// is coming from. 179f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling void analyzePHINodes(const MachineFunction& Fn); 180db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattnerpublic: 181db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 182db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner virtual bool runOnMachineFunction(MachineFunction &MF); 183db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 18420647a55bfabd715bfef52f68d6d13753a672940Chris Lattner /// RegisterDefIsDead - Return true if the specified instruction defines the 18520647a55bfabd715bfef52f68d6d13753a672940Chris Lattner /// specified register, but that definition is dead. 186c44fff472c6d56390b9c4c7da6cc77c1d45b1744Chris Lattner bool RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const; 187a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng 1889c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner //===--------------------------------------------------------------------===// 1899c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner // API to update live variable information 1909c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner 191be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng /// replaceKillInstruction - Update register kill info by replacing a kill 192be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng /// instruction with a new one. 193be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng void replaceKillInstruction(unsigned Reg, MachineInstr *OldMI, 194be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng MachineInstr *NewMI); 195be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng 1969c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner /// addVirtualRegisterKilled - Add information about the fact that the 1979c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner /// specified register is killed after being used by the specified 19805350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// instruction. If AddIfNotFound is true, add a implicit operand if it's 19905350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// not found. 20005350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr *MI, 20105350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng bool AddIfNotFound = false) { 2026130f66eaae89f8878590796977678afa8448926Evan Cheng if (MI->addRegisterKilled(IncomingReg, TRI, AddIfNotFound)) 20305350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng getVarInfo(IncomingReg).Kills.push_back(MI); 20481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 2059c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner 2069f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// removeVirtualRegisterKilled - Remove the specified kill of the virtual 20771499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// register from the live variable information. Returns true if the 20871499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// variable was marked as killed by the specified instruction, 20971499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// false otherwise. 2109f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng bool removeVirtualRegisterKilled(unsigned reg, MachineInstr *MI) { 21171499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos if (!getVarInfo(reg).removeKill(MI)) 21271499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return false; 213e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner 214a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng bool Removed = false; 215a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 216a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng MachineOperand &MO = MI->getOperand(i); 217d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.isKill() && MO.getReg() == reg) { 218f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner MO.setIsKill(false); 219a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng Removed = true; 220a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng break; 221e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner } 222a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng } 223a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng 224a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng assert(Removed && "Register is not used by this instruction!"); 2251f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)Removed; 22671499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return true; 22771499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos } 22871499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos 229e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner /// removeVirtualRegistersKilled - Remove all killed info for the specified 230e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner /// instruction. 2317a3abdc63c0cc4e5d5411c3add0e909c6ac49e79Chris Lattner void removeVirtualRegistersKilled(MachineInstr *MI); 23281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 2339c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner /// addVirtualRegisterDead - Add information about the fact that the specified 23405350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// register is dead after being used by the specified instruction. If 23505350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// AddIfNotFound is true, add a implicit operand if it's not found. 23605350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr *MI, 23705350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng bool AddIfNotFound = false) { 2386130f66eaae89f8878590796977678afa8448926Evan Cheng if (MI->addRegisterDead(IncomingReg, TRI, AddIfNotFound)) 2399f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng getVarInfo(IncomingReg).Kills.push_back(MI); 240db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner } 241db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 2429f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// removeVirtualRegisterDead - Remove the specified kill of the virtual 24371499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// register from the live variable information. Returns true if the 24471499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// variable was marked dead at the specified instruction, false 24571499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// otherwise. 2469f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng bool removeVirtualRegisterDead(unsigned reg, MachineInstr *MI) { 24771499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos if (!getVarInfo(reg).removeKill(MI)) 24871499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return false; 24971499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos 250a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng bool Removed = false; 251a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 252a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng MachineOperand &MO = MI->getOperand(i); 253d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.isDef() && MO.getReg() == reg) { 254f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner MO.setIsDead(false); 255a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng Removed = true; 256a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng break; 257e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner } 258a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng } 259a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng assert(Removed && "Register is not defined by this instruction!"); 2601f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)Removed; 26171499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return true; 26271499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos } 263bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 264bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson void getAnalysisUsage(AnalysisUsage &AU) const; 265db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 266db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner virtual void releaseMemory() { 267db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner VirtRegInfo.clear(); 268db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner } 269bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner 270bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL 271bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner /// register. 272bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner VarInfo &getVarInfo(unsigned RegIdx); 273db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 27440a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock, 27540a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MachineBasicBlock *BB); 27640a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock, 27740a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MachineBasicBlock *BB, 27856184904cd9a348920de0c3b391d42b691091137Evan Cheng std::vector<MachineBasicBlock*> &WorkList); 2793bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohman void HandleVirtRegDef(unsigned reg, MachineInstr *MI); 280426df7538d1d89eac4fe3b56a74a9febcea6b196Evan Cheng void HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, 28100876a2808f1a8061f7e0852c7949fc5074ecb04Misha Brukman MachineInstr *MI); 282f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 283323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen bool isLiveIn(unsigned Reg, const MachineBasicBlock &MBB) { 284323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI); 285323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen } 286323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen 2878f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen /// isLiveOut - Determine if Reg is live out from MBB, when not considering 2888f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen /// PHI nodes. This means that Reg is either killed by a successor block or 2898f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen /// passed through one. 2908f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB); 2918f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen 292323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All 293323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// variables that are live out of DomBB and live into SuccBB will be marked 294323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// as passing live through BB. This method assumes that the machine code is 295323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// still in SSA form. 296323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen void addNewBlock(MachineBasicBlock *BB, 297323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineBasicBlock *DomBB, 298323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineBasicBlock *SuccBB); 299dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 300dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// isPHIJoin - Return true if Reg is a phi join register. 301dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); } 302dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 303dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// setPHIJoin - Mark Reg as a phi join register. 304dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen void setPHIJoin(unsigned Reg) { PHIJoins.set(Reg); } 305db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner}; 306db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 307d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 308d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 309db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner#endif 310