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 323a190f5e5e8b936d008e0ce9d03b051d80a6ac6fDavid Greene#include "llvm/CodeGen/MachineBasicBlock.h" 33db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner#include "llvm/CodeGen/MachineFunctionPass.h" 343a190f5e5e8b936d008e0ce9d03b051d80a6ac6fDavid Greene#include "llvm/CodeGen/MachineInstr.h" 35b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen#include "llvm/Target/TargetRegisterInfo.h" 3661de82d8853a02fe39c47302432abb70a586704fEvan Cheng#include "llvm/ADT/BitVector.h" 37ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng#include "llvm/ADT/DenseMap.h" 38b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 39dace0ed8c7b33056c533a7e878d600f7eec5fd1cEvan Cheng#include "llvm/ADT/SmallSet.h" 40e96f50142e8d12a2e12c3329bffb372e09731dd2Evan Cheng#include "llvm/ADT/SmallVector.h" 41493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin#include "llvm/ADT/SparseBitVector.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 129b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng /// ReservedRegisters - This vector keeps track of which registers 130b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng /// are reserved register which are not allocatable by the target machine. 131b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng /// We can not track liveness for values that are in this set. 1328a88563a32d63b74f486ae6887e0f25365800b51Chris Lattner /// 133b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng BitVector ReservedRegisters; 1349c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner 135db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattnerprivate: // Intermediate data structures 136c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng MachineFunction *MF; 137c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng 138ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng MachineRegisterInfo* MRI; 139ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng 1406130f66eaae89f8878590796977678afa8448926Evan Cheng const TargetRegisterInfo *TRI; 141db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 1420d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // PhysRegInfo - Keep track of which instruction was the last def of a 14324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // physical register. This is a purely local property, because all physical 1445ec3ab7f67ab740681b1ddbba2290da6e7040777Bill Wendling // register references are presumed dead across basic blocks. 1450d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng MachineInstr **PhysRegDef; 14624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 1470d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // PhysRegInfo - Keep track of which instruction was the last use of a 1480d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // physical register. This is a purely local property, because all physical 1490d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // register references are presumed dead across basic blocks. 1500d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng MachineInstr **PhysRegUse; 151f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling 152e96f50142e8d12a2e12c3329bffb372e09731dd2Evan Cheng SmallVector<unsigned, 4> *PHIVarInfo; 153a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng 154ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng // DistanceMap - Keep track the distance of a MI from the start of the 155ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng // current basic block. 156ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng DenseMap<MachineInstr*, unsigned> DistanceMap; 157ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng 1584efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng /// HandlePhysRegKill - Add kills of Reg and its sub-registers to the 1594efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng /// uses. Pay special attention to the sub-register uses which may come below 1604efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng /// the last use of the whole register. 161a894ae130b6e69a367aa691eec7e96973a20e901Evan Cheng bool HandlePhysRegKill(unsigned Reg, MachineInstr *MI); 1620d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng 1638c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen /// HandleRegMask - Call HandlePhysRegKill for all registers clobbered by Mask. 1648c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen void HandleRegMask(const MachineOperand&); 1658c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen 166b08bdc4a161313bb09a73e6c61f0cb0669e291c7Alkis Evlogimenos void HandlePhysRegUse(unsigned Reg, MachineInstr *MI); 167296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng void HandlePhysRegDef(unsigned Reg, MachineInstr *MI, 168ad934b821c78d39e73a213c62cd57288f8605a0cEvan Cheng SmallVector<unsigned, 4> &Defs); 169296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng void UpdatePhysRegDefs(MachineInstr *MI, SmallVector<unsigned, 4> &Defs); 170b08bdc4a161313bb09a73e6c61f0cb0669e291c7Alkis Evlogimenos 171a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// FindLastRefOrPartRef - Return the last reference or partial reference of 172a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// the specified register. 173a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng MachineInstr *FindLastRefOrPartRef(unsigned Reg); 174a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng 175a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// FindLastPartialDef - Return the last partial def of the specified 176a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// register. Also returns the sub-registers that're defined by the 177a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// instruction. 178dace0ed8c7b33056c533a7e878d600f7eec5fd1cEvan Cheng MachineInstr *FindLastPartialDef(unsigned Reg, 179dace0ed8c7b33056c533a7e878d600f7eec5fd1cEvan Cheng SmallSet<unsigned,4> &PartDefRegs); 1800d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng 181f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// analyzePHINodes - Gather information about the PHI nodes in here. In 182f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// particular, we want to map the variable information of a virtual 183f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// register which is used in a PHI node. We map that to the BB the vreg 184f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// is coming from. 185f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling void analyzePHINodes(const MachineFunction& Fn); 186db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattnerpublic: 187db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 188db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner virtual bool runOnMachineFunction(MachineFunction &MF); 189db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 19020647a55bfabd715bfef52f68d6d13753a672940Chris Lattner /// RegisterDefIsDead - Return true if the specified instruction defines the 19120647a55bfabd715bfef52f68d6d13753a672940Chris Lattner /// specified register, but that definition is dead. 192c44fff472c6d56390b9c4c7da6cc77c1d45b1744Chris Lattner bool RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const; 193a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng 1949c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner //===--------------------------------------------------------------------===// 1959c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner // API to update live variable information 1969c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner 197be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng /// replaceKillInstruction - Update register kill info by replacing a kill 198be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng /// instruction with a new one. 199be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng void replaceKillInstruction(unsigned Reg, MachineInstr *OldMI, 200be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng MachineInstr *NewMI); 201be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng 2029c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner /// addVirtualRegisterKilled - Add information about the fact that the 2039c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner /// specified register is killed after being used by the specified 20405350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// instruction. If AddIfNotFound is true, add a implicit operand if it's 20505350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// not found. 20605350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr *MI, 20705350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng bool AddIfNotFound = false) { 2086130f66eaae89f8878590796977678afa8448926Evan Cheng if (MI->addRegisterKilled(IncomingReg, TRI, AddIfNotFound)) 20905350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng getVarInfo(IncomingReg).Kills.push_back(MI); 21081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 2119c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner 2129f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// removeVirtualRegisterKilled - Remove the specified kill of the virtual 21371499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// register from the live variable information. Returns true if the 21471499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// variable was marked as killed by the specified instruction, 21571499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// false otherwise. 2169f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng bool removeVirtualRegisterKilled(unsigned reg, MachineInstr *MI) { 21771499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos if (!getVarInfo(reg).removeKill(MI)) 21871499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return false; 219e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner 220a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng bool Removed = false; 221a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 222a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng MachineOperand &MO = MI->getOperand(i); 223d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.isKill() && MO.getReg() == reg) { 224f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner MO.setIsKill(false); 225a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng Removed = true; 226a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng break; 227e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner } 228a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng } 229a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng 230a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng assert(Removed && "Register is not used by this instruction!"); 2311f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)Removed; 23271499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return true; 23371499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos } 23471499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos 235e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner /// removeVirtualRegistersKilled - Remove all killed info for the specified 236e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner /// instruction. 2377a3abdc63c0cc4e5d5411c3add0e909c6ac49e79Chris Lattner void removeVirtualRegistersKilled(MachineInstr *MI); 23881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 2399c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner /// addVirtualRegisterDead - Add information about the fact that the specified 24005350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// register is dead after being used by the specified instruction. If 24105350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// AddIfNotFound is true, add a implicit operand if it's not found. 24205350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr *MI, 24305350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng bool AddIfNotFound = false) { 2446130f66eaae89f8878590796977678afa8448926Evan Cheng if (MI->addRegisterDead(IncomingReg, TRI, AddIfNotFound)) 2459f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng getVarInfo(IncomingReg).Kills.push_back(MI); 246db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner } 247db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 2489f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// removeVirtualRegisterDead - Remove the specified kill of the virtual 24971499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// register from the live variable information. Returns true if the 25071499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// variable was marked dead at the specified instruction, false 25171499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// otherwise. 2529f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng bool removeVirtualRegisterDead(unsigned reg, MachineInstr *MI) { 25371499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos if (!getVarInfo(reg).removeKill(MI)) 25471499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return false; 25571499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos 256a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng bool Removed = false; 257a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 258a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng MachineOperand &MO = MI->getOperand(i); 259d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.isDef() && MO.getReg() == reg) { 260f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner MO.setIsDead(false); 261a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng Removed = true; 262a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng break; 263e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner } 264a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng } 265a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng assert(Removed && "Register is not defined by this instruction!"); 2661f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)Removed; 26771499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return true; 26871499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos } 269bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson 270bd3ba461eb5578a81ba09ff7bd7eb271d1130196Owen Anderson void getAnalysisUsage(AnalysisUsage &AU) const; 271db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 272db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner virtual void releaseMemory() { 273db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner VirtRegInfo.clear(); 274db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner } 275bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner 276bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL 277bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner /// register. 278bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner VarInfo &getVarInfo(unsigned RegIdx); 279db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 28040a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock, 28140a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MachineBasicBlock *BB); 28240a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock, 28340a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MachineBasicBlock *BB, 28456184904cd9a348920de0c3b391d42b691091137Evan Cheng std::vector<MachineBasicBlock*> &WorkList); 2853bdf5fe71ad2d48d81d013b16181766bde295f58Dan Gohman void HandleVirtRegDef(unsigned reg, MachineInstr *MI); 286426df7538d1d89eac4fe3b56a74a9febcea6b196Evan Cheng void HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, 28700876a2808f1a8061f7e0852c7949fc5074ecb04Misha Brukman MachineInstr *MI); 288f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 289323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen bool isLiveIn(unsigned Reg, const MachineBasicBlock &MBB) { 290323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI); 291323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen } 292323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen 2938f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen /// isLiveOut - Determine if Reg is live out from MBB, when not considering 2948f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen /// PHI nodes. This means that Reg is either killed by a successor block or 2958f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen /// passed through one. 2968f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB); 2978f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen 298323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All 299323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// variables that are live out of DomBB and live into SuccBB will be marked 300323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// as passing live through BB. This method assumes that the machine code is 301323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// still in SSA form. 302323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen void addNewBlock(MachineBasicBlock *BB, 303323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineBasicBlock *DomBB, 304323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineBasicBlock *SuccBB); 305dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 306dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// isPHIJoin - Return true if Reg is a phi join register. 307dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); } 308dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 309dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// setPHIJoin - Mark Reg as a phi join register. 310dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen void setPHIJoin(unsigned Reg) { PHIJoins.set(Reg); } 311db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner}; 312db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 313d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 314d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 315db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner#endif 316