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 32ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng#include "llvm/ADT/DenseMap.h" 33b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 34dace0ed8c7b33056c533a7e878d600f7eec5fd1cEvan Cheng#include "llvm/ADT/SmallSet.h" 35e96f50142e8d12a2e12c3329bffb372e09731dd2Evan Cheng#include "llvm/ADT/SmallVector.h" 36493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin#include "llvm/ADT/SparseBitVector.h" 37255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/CodeGen/MachineFunctionPass.h" 38255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/CodeGen/MachineInstr.h" 39255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 40db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 41d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 42d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 43f31034db8c12197d00b3e356e1d2a702c2339d49Jakub Staszakclass MachineBasicBlock; 44ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Chengclass MachineRegisterInfo; 45db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 46db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattnerclass LiveVariables : public MachineFunctionPass { 47bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattnerpublic: 48ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 49081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson LiveVariables() : MachineFunctionPass(ID) { 50081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLiveVariablesPass(*PassRegistry::getPassRegistry()); 51081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 52794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 5351d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// VarInfo - This represents the regions where a virtual register is live in 54f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// the program. We represent this with three different pieces of 55e8f4ac2b10cc058431f534c53b7f021f492bd9c0Dan Gohman /// information: the set of blocks in which the instruction is live 56e8f4ac2b10cc058431f534c53b7f021f492bd9c0Dan Gohman /// throughout, the set of blocks in which the instruction is actually used, 57e8f4ac2b10cc058431f534c53b7f021f492bd9c0Dan Gohman /// and the set of non-phi instructions that are the last users of the value. 5851d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// 597fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// In the common case where a value is defined and killed in the same block, 607fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// There is one killing instruction, and AliveBlocks is empty. 617fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// 627fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// Otherwise, the value is live out of the block. If the value is live 637fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// throughout any blocks, these blocks are listed in AliveBlocks. Blocks 647fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// where the liveness range ends are not included in AliveBlocks, instead 657fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// being captured by the Kills set. In these blocks, the value is live into 667fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// the block (unless the value is defined and killed in the same block) and 677fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// lives until the specified instruction. Note that there cannot ever be a 687fc610f07311ecbbbdf163e5bcb45c636b87c983Dan Gohman /// value whose Kills set contains two instructions from the same basic block. 6951d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// 7051d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// PHI nodes complicate things a bit. If a PHI node is the last user of a 7151d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// value in one of its predecessor blocks, it is not listed in the kills set, 7251d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// but does include the predecessor block in the AliveBlocks set (unless that 7351d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// block also defines the value). This leads to the (perfectly sensical) 7451d6e76ff4cf950b759be389d23e9383a29b1dc9Chris Lattner /// situation where a value is defined in a block, and the last use is a phi 759f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// node in the successor. In this case, AliveBlocks is empty (the value is 769f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// not live across any blocks) and Kills is empty (phi nodes are not 779f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// included). This is sensical because the value must be live to the end of 789f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// the block, but is not live in any successor blocks. 79db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner struct VarInfo { 80e8f4ac2b10cc058431f534c53b7f021f492bd9c0Dan Gohman /// AliveBlocks - Set of blocks in which this value is alive completely 81db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// through. This is a bit set which uses the basic block number as an 82db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// index. 83db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// 84493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin SparseBitVector<> AliveBlocks; 85db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 8674de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner /// Kills - List of MachineInstruction's which are the last use of this 8774de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner /// virtual register (kill it) in their basic block. 88db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// 8974de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner std::vector<MachineInstr*> Kills; 90db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 9171499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// removeKill - Delete a kill corresponding to the specified 9271499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// machine instruction. Returns true if there was a kill 9371499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// corresponding to this instruction, false otherwise. 94de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool removeKill(MachineInstr &MI) { 95de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::vector<MachineInstr *>::iterator I = 96de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::find(Kills.begin(), Kills.end(), &MI); 97fe666a3592b2f59cf67a2f72a148f4db40f34b2fEvan Cheng if (I == Kills.end()) 98fe666a3592b2f59cf67a2f72a148f4db40f34b2fEvan Cheng return false; 99fe666a3592b2f59cf67a2f72a148f4db40f34b2fEvan Cheng Kills.erase(I); 100fe666a3592b2f59cf67a2f72a148f4db40f34b2fEvan Cheng return true; 101bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner } 102f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 103f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen /// findKill - Find a kill instruction in MBB. Return NULL if none is found. 104f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineInstr *findKill(const MachineBasicBlock *MBB) const; 105f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 106323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// isLiveIn - Is Reg live in to MBB? This means that Reg is live through 107323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// MBB, or it is killed in MBB. If Reg is only used by PHI instructions in 108323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// MBB, it is not considered live in. 109323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen bool isLiveIn(const MachineBasicBlock &MBB, 110323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen unsigned Reg, 111323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineRegisterInfo &MRI); 112323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen 1130df687b1be4a29e0358e6e8710f0c71d5966c43aChris Lattner void dump() const; 114db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner }; 115db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 116bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattnerprivate: 117db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// VirtRegInfo - This list is a mapping from virtual register number to 118b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen /// variable information. 119db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner /// 120b421c566f512ed0ec87851866d335e9086c3f8beJakob Stoklund Olesen IndexedMap<VarInfo, VirtReg2IndexFunctor> VirtRegInfo; 121db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 122dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// PHIJoins - list of virtual registers that are PHI joins. These registers 123dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// may have multiple definitions, and they require special handling when 124dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// building live intervals. 125dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SparseBitVector<> PHIJoins; 126dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 127db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattnerprivate: // Intermediate data structures 128c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng MachineFunction *MF; 129c6a2410d58916b8a8a1b26f2448b903d12e77f2fEvan Cheng 130ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng MachineRegisterInfo* MRI; 131ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng 1326130f66eaae89f8878590796977678afa8448926Evan Cheng const TargetRegisterInfo *TRI; 133db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 1340d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // PhysRegInfo - Keep track of which instruction was the last def of a 13524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // physical register. This is a purely local property, because all physical 1365ec3ab7f67ab740681b1ddbba2290da6e7040777Bill Wendling // register references are presumed dead across basic blocks. 13737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<MachineInstr *> PhysRegDef; 13824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 1390d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // PhysRegInfo - Keep track of which instruction was the last use of a 1400d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // physical register. This is a purely local property, because all physical 1410d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng // register references are presumed dead across basic blocks. 14237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<MachineInstr *> PhysRegUse; 143f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling 14437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<SmallVector<unsigned, 4>> PHIVarInfo; 145a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng 146ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng // DistanceMap - Keep track the distance of a MI from the start of the 147ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng // current basic block. 148ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng DenseMap<MachineInstr*, unsigned> DistanceMap; 149ea1d9cdc4e4f4e4570acddb7c4a63f703b110dadEvan Cheng 1504efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng /// HandlePhysRegKill - Add kills of Reg and its sub-registers to the 1514efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng /// uses. Pay special attention to the sub-register uses which may come below 1524efe74129f7483bc8c48d68f095d632b974c353dEvan Cheng /// the last use of the whole register. 153a894ae130b6e69a367aa691eec7e96973a20e901Evan Cheng bool HandlePhysRegKill(unsigned Reg, MachineInstr *MI); 1540d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng 1558c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen /// HandleRegMask - Call HandlePhysRegKill for all registers clobbered by Mask. 1568c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen void HandleRegMask(const MachineOperand&); 1578c47ad8c4708286bda9362f8089f84a3d7e41056Jakob Stoklund Olesen 158de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void HandlePhysRegUse(unsigned Reg, MachineInstr &MI); 159296925dc169b45e7535abdccc8dc143a8bec7f0aEvan Cheng void HandlePhysRegDef(unsigned Reg, MachineInstr *MI, 1609e639e8fd95488cb4c8ef2f7f3a41919acb29ac4Craig Topper SmallVectorImpl<unsigned> &Defs); 161de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void UpdatePhysRegDefs(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs); 162b08bdc4a161313bb09a73e6c61f0cb0669e291c7Alkis Evlogimenos 163a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// FindLastRefOrPartRef - Return the last reference or partial reference of 164a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// the specified register. 165a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng MachineInstr *FindLastRefOrPartRef(unsigned Reg); 166a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng 167a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// FindLastPartialDef - Return the last partial def of the specified 168a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// register. Also returns the sub-registers that're defined by the 169a4025df42d2393da7041cd11e48a3d44b0ae2bb1Evan Cheng /// instruction. 170dace0ed8c7b33056c533a7e878d600f7eec5fd1cEvan Cheng MachineInstr *FindLastPartialDef(unsigned Reg, 171dace0ed8c7b33056c533a7e878d600f7eec5fd1cEvan Cheng SmallSet<unsigned,4> &PartDefRegs); 1720d4bdde3270a8ed182a685a580031d6d5d743164Evan Cheng 173f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// analyzePHINodes - Gather information about the PHI nodes in here. In 174f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// particular, we want to map the variable information of a virtual 175f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// register which is used in a PHI node. We map that to the BB the vreg 176f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling /// is coming from. 177f7da4e939f02678cbe56cae666506da3b1a5e100Bill Wendling void analyzePHINodes(const MachineFunction& Fn); 17837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 179de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void runOnInstr(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs); 18037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 18137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs); 182db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattnerpublic: 183db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnMachineFunction(MachineFunction &MF) override; 185db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 18620647a55bfabd715bfef52f68d6d13753a672940Chris Lattner /// RegisterDefIsDead - Return true if the specified instruction defines the 18720647a55bfabd715bfef52f68d6d13753a672940Chris Lattner /// specified register, but that definition is dead. 188de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool RegisterDefIsDead(MachineInstr &MI, unsigned Reg) const; 189a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng 1909c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner //===--------------------------------------------------------------------===// 1919c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner // API to update live variable information 1929c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner 193be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng /// replaceKillInstruction - Update register kill info by replacing a kill 194be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng /// instruction with a new one. 195de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void replaceKillInstruction(unsigned Reg, MachineInstr &OldMI, 196de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineInstr &NewMI); 197be04dc1413bdab0c8687a8086792af6cfd7540c0Evan Cheng 1989c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner /// addVirtualRegisterKilled - Add information about the fact that the 1999c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner /// specified register is killed after being used by the specified 20005350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// instruction. If AddIfNotFound is true, add a implicit operand if it's 20105350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// not found. 202de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr &MI, 20305350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng bool AddIfNotFound = false) { 204de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (MI.addRegisterKilled(IncomingReg, TRI, AddIfNotFound)) 205de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar getVarInfo(IncomingReg).Kills.push_back(&MI); 20681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 2079c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner 2089f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// removeVirtualRegisterKilled - Remove the specified kill of the virtual 20971499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// register from the live variable information. Returns true if the 21071499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// variable was marked as killed by the specified instruction, 21171499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// false otherwise. 212de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool removeVirtualRegisterKilled(unsigned reg, MachineInstr &MI) { 21371499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos if (!getVarInfo(reg).removeKill(MI)) 21471499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return false; 215e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner 216a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng bool Removed = false; 217de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 218de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineOperand &MO = MI.getOperand(i); 219d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.isKill() && MO.getReg() == reg) { 220f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner MO.setIsKill(false); 221a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng Removed = true; 222a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng break; 223e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner } 224a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng } 225a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng 226a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng assert(Removed && "Register is not used by this instruction!"); 2271f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)Removed; 22871499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return true; 22971499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos } 23071499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos 231e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner /// removeVirtualRegistersKilled - Remove all killed info for the specified 232e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner /// instruction. 233de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void removeVirtualRegistersKilled(MachineInstr &MI); 23481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 2359c341366a7e644c9d8333ed84a90aa57516c7aceChris Lattner /// addVirtualRegisterDead - Add information about the fact that the specified 23605350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// register is dead after being used by the specified instruction. If 23705350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng /// AddIfNotFound is true, add a implicit operand if it's not found. 238de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr &MI, 23905350288a6bc22a294ff7625f244731ef7125f8aEvan Cheng bool AddIfNotFound = false) { 240de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (MI.addRegisterDead(IncomingReg, TRI, AddIfNotFound)) 241de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar getVarInfo(IncomingReg).Kills.push_back(&MI); 242db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner } 243db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 2449f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng /// removeVirtualRegisterDead - Remove the specified kill of the virtual 24571499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// register from the live variable information. Returns true if the 24671499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// variable was marked dead at the specified instruction, false 24771499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos /// otherwise. 248de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool removeVirtualRegisterDead(unsigned reg, MachineInstr &MI) { 24971499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos if (!getVarInfo(reg).removeKill(MI)) 25071499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return false; 25171499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos 252a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng bool Removed = false; 253de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 254de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineOperand &MO = MI.getOperand(i); 255d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.isDef() && MO.getReg() == reg) { 256f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner MO.setIsDead(false); 257a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng Removed = true; 258a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng break; 259e0cbf970ac5e9636a3a635e1f3390aa5d93c827aChris Lattner } 260a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng } 261a6c4c1eb90413986519c46f70222539dee39ffe9Evan Cheng assert(Removed && "Register is not defined by this instruction!"); 2621f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)Removed; 26371499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos return true; 26471499ded4d76233f3b605638b539548bea8bb2f1Alkis Evlogimenos } 265db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 26736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseMemory() override { 269db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner VirtRegInfo.clear(); 270db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner } 271bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner 272bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL 273bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner /// register. 274bc4a15f6faa6c32b2b84205fcdac9042728cf365Chris Lattner VarInfo &getVarInfo(unsigned RegIdx); 275db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 27640a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock, 27740a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MachineBasicBlock *BB); 27840a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock, 27940a627ddf87fe8e5fe057fba405cc0893cf14e70Owen Anderson MachineBasicBlock *BB, 28056184904cd9a348920de0c3b391d42b691091137Evan Cheng std::vector<MachineBasicBlock*> &WorkList); 281de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void HandleVirtRegDef(unsigned reg, MachineInstr &MI); 282de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, MachineInstr &MI); 283f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 284323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen bool isLiveIn(unsigned Reg, const MachineBasicBlock &MBB) { 285323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI); 286323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen } 287323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen 2888f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen /// isLiveOut - Determine if Reg is live out from MBB, when not considering 2898f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen /// PHI nodes. This means that Reg is either killed by a successor block or 2908f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen /// passed through one. 2918f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB); 2928f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen 293323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All 294323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// variables that are live out of DomBB and live into SuccBB will be marked 295323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// as passing live through BB. This method assumes that the machine code is 296323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen /// still in SSA form. 297323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen void addNewBlock(MachineBasicBlock *BB, 298323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineBasicBlock *DomBB, 299323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen MachineBasicBlock *SuccBB); 300dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 301dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// isPHIJoin - Return true if Reg is a phi join register. 302dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); } 303dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 304dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen /// setPHIJoin - Mark Reg as a phi join register. 305dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen void setPHIJoin(unsigned Reg) { PHIJoins.set(Reg); } 306db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner}; 307db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner 308d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 309d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 310db00065fc8ab9fe8b7ac87640c57fd61e922c0f2Chris Lattner#endif 311