LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - LiveVariables.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 42 42 100.0 %
Date: 2017-09-14 15:23:50 Functions: 11 11 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- llvm/CodeGen/LiveVariables.h - Live Variable Analysis ---*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements the LiveVariables analysis pass.  For each machine
      11             : // instruction in the function, this pass calculates the set of registers that
      12             : // are immediately dead after the instruction (i.e., the instruction calculates
      13             : // the value, but it is never used) and the set of registers that are used by
      14             : // the instruction, but are never used after the instruction (i.e., they are
      15             : // killed).
      16             : //
      17             : // This class computes live variables using a sparse implementation based on
      18             : // the machine code SSA form.  This class computes live variable information for
      19             : // each virtual and _register allocatable_ physical register in a function.  It
      20             : // uses the dominance properties of SSA form to efficiently compute live
      21             : // variables for virtual registers, and assumes that physical registers are only
      22             : // live within a single basic block (allowing it to do a single local analysis
      23             : // to resolve physical register lifetimes in each basic block).  If a physical
      24             : // register is not register allocatable, it is not tracked.  This is useful for
      25             : // things like the stack pointer and condition codes.
      26             : //
      27             : //===----------------------------------------------------------------------===//
      28             : 
      29             : #ifndef LLVM_CODEGEN_LIVEVARIABLES_H
      30             : #define LLVM_CODEGEN_LIVEVARIABLES_H
      31             : 
      32             : #include "llvm/ADT/DenseMap.h"
      33             : #include "llvm/ADT/IndexedMap.h"
      34             : #include "llvm/ADT/SmallSet.h"
      35             : #include "llvm/ADT/SmallVector.h"
      36             : #include "llvm/ADT/SparseBitVector.h"
      37             : #include "llvm/CodeGen/MachineFunctionPass.h"
      38             : #include "llvm/CodeGen/MachineInstr.h"
      39             : #include "llvm/Target/TargetRegisterInfo.h"
      40             : 
      41             : namespace llvm {
      42             : 
      43             : class MachineBasicBlock;
      44             : class MachineRegisterInfo;
      45             : 
      46      114771 : class LiveVariables : public MachineFunctionPass {
      47             : public:
      48             :   static char ID; // Pass identification, replacement for typeid
      49      115493 :   LiveVariables() : MachineFunctionPass(ID) {
      50       16499 :     initializeLiveVariablesPass(*PassRegistry::getPassRegistry());
      51       16499 :   }
      52             : 
      53             :   /// VarInfo - This represents the regions where a virtual register is live in
      54             :   /// the program.  We represent this with three different pieces of
      55             :   /// information: the set of blocks in which the instruction is live
      56             :   /// throughout, the set of blocks in which the instruction is actually used,
      57             :   /// and the set of non-phi instructions that are the last users of the value.
      58             :   ///
      59             :   /// In the common case where a value is defined and killed in the same block,
      60             :   /// There is one killing instruction, and AliveBlocks is empty.
      61             :   ///
      62             :   /// Otherwise, the value is live out of the block.  If the value is live
      63             :   /// throughout any blocks, these blocks are listed in AliveBlocks.  Blocks
      64             :   /// where the liveness range ends are not included in AliveBlocks, instead
      65             :   /// being captured by the Kills set.  In these blocks, the value is live into
      66             :   /// the block (unless the value is defined and killed in the same block) and
      67             :   /// lives until the specified instruction.  Note that there cannot ever be a
      68             :   /// value whose Kills set contains two instructions from the same basic block.
      69             :   ///
      70             :   /// PHI nodes complicate things a bit.  If a PHI node is the last user of a
      71             :   /// value in one of its predecessor blocks, it is not listed in the kills set,
      72             :   /// but does include the predecessor block in the AliveBlocks set (unless that
      73             :   /// block also defines the value).  This leads to the (perfectly sensical)
      74             :   /// situation where a value is defined in a block, and the last use is a phi
      75             :   /// node in the successor.  In this case, AliveBlocks is empty (the value is
      76             :   /// not live across any  blocks) and Kills is empty (phi nodes are not
      77             :   /// included). This is sensical because the value must be live to the end of
      78             :   /// the block, but is not live in any successor blocks.
      79    12093529 :   struct VarInfo {
      80             :     /// AliveBlocks - Set of blocks in which this value is alive completely
      81             :     /// through.  This is a bit set which uses the basic block number as an
      82             :     /// index.
      83             :     ///
      84             :     SparseBitVector<> AliveBlocks;
      85             : 
      86             :     /// Kills - List of MachineInstruction's which are the last use of this
      87             :     /// virtual register (kill it) in their basic block.
      88             :     ///
      89             :     std::vector<MachineInstr*> Kills;
      90             : 
      91             :     /// removeKill - Delete a kill corresponding to the specified
      92             :     /// machine instruction. Returns true if there was a kill
      93             :     /// corresponding to this instruction, false otherwise.
      94      188344 :     bool removeKill(MachineInstr &MI) {
      95      376688 :       std::vector<MachineInstr *>::iterator I = find(Kills, &MI);
      96      565032 :       if (I == Kills.end())
      97             :         return false;
      98      559443 :       Kills.erase(I);
      99      186481 :       return true;
     100             :     }
     101             : 
     102             :     /// findKill - Find a kill instruction in MBB. Return NULL if none is found.
     103             :     MachineInstr *findKill(const MachineBasicBlock *MBB) const;
     104             : 
     105             :     /// isLiveIn - Is Reg live in to MBB? This means that Reg is live through
     106             :     /// MBB, or it is killed in MBB. If Reg is only used by PHI instructions in
     107             :     /// MBB, it is not considered live in.
     108             :     bool isLiveIn(const MachineBasicBlock &MBB,
     109             :                   unsigned Reg,
     110             :                   MachineRegisterInfo &MRI);
     111             : 
     112             :     void dump() const;
     113             :   };
     114             : 
     115             : private:
     116             :   /// VirtRegInfo - This list is a mapping from virtual register number to
     117             :   /// variable information.
     118             :   ///
     119             :   IndexedMap<VarInfo, VirtReg2IndexFunctor> VirtRegInfo;
     120             : 
     121             :   /// PHIJoins - list of virtual registers that are PHI joins. These registers
     122             :   /// may have multiple definitions, and they require special handling when
     123             :   /// building live intervals.
     124             :   SparseBitVector<> PHIJoins;
     125             : 
     126             : private:   // Intermediate data structures
     127             :   MachineFunction *MF;
     128             : 
     129             :   MachineRegisterInfo* MRI;
     130             : 
     131             :   const TargetRegisterInfo *TRI;
     132             : 
     133             :   // PhysRegInfo - Keep track of which instruction was the last def of a
     134             :   // physical register. This is a purely local property, because all physical
     135             :   // register references are presumed dead across basic blocks.
     136             :   std::vector<MachineInstr *> PhysRegDef;
     137             : 
     138             :   // PhysRegInfo - Keep track of which instruction was the last use of a
     139             :   // physical register. This is a purely local property, because all physical
     140             :   // register references are presumed dead across basic blocks.
     141             :   std::vector<MachineInstr *> PhysRegUse;
     142             : 
     143             :   std::vector<SmallVector<unsigned, 4>> PHIVarInfo;
     144             : 
     145             :   // DistanceMap - Keep track the distance of a MI from the start of the
     146             :   // current basic block.
     147             :   DenseMap<MachineInstr*, unsigned> DistanceMap;
     148             : 
     149             :   /// HandlePhysRegKill - Add kills of Reg and its sub-registers to the
     150             :   /// uses. Pay special attention to the sub-register uses which may come below
     151             :   /// the last use of the whole register.
     152             :   bool HandlePhysRegKill(unsigned Reg, MachineInstr *MI);
     153             : 
     154             :   /// HandleRegMask - Call HandlePhysRegKill for all registers clobbered by Mask.
     155             :   void HandleRegMask(const MachineOperand&);
     156             : 
     157             :   void HandlePhysRegUse(unsigned Reg, MachineInstr &MI);
     158             :   void HandlePhysRegDef(unsigned Reg, MachineInstr *MI,
     159             :                         SmallVectorImpl<unsigned> &Defs);
     160             :   void UpdatePhysRegDefs(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs);
     161             : 
     162             :   /// FindLastRefOrPartRef - Return the last reference or partial reference of
     163             :   /// the specified register.
     164             :   MachineInstr *FindLastRefOrPartRef(unsigned Reg);
     165             : 
     166             :   /// FindLastPartialDef - Return the last partial def of the specified
     167             :   /// register. Also returns the sub-registers that're defined by the
     168             :   /// instruction.
     169             :   MachineInstr *FindLastPartialDef(unsigned Reg,
     170             :                                    SmallSet<unsigned,4> &PartDefRegs);
     171             : 
     172             :   /// analyzePHINodes - Gather information about the PHI nodes in here. In
     173             :   /// particular, we want to map the variable information of a virtual
     174             :   /// register which is used in a PHI node. We map that to the BB the vreg
     175             :   /// is coming from.
     176             :   void analyzePHINodes(const MachineFunction& Fn);
     177             : 
     178             :   void runOnInstr(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs);
     179             : 
     180             :   void runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs);
     181             : public:
     182             : 
     183             :   bool runOnMachineFunction(MachineFunction &MF) override;
     184             : 
     185             :   /// RegisterDefIsDead - Return true if the specified instruction defines the
     186             :   /// specified register, but that definition is dead.
     187             :   bool RegisterDefIsDead(MachineInstr &MI, unsigned Reg) const;
     188             : 
     189             :   //===--------------------------------------------------------------------===//
     190             :   //  API to update live variable information
     191             : 
     192             :   /// replaceKillInstruction - Update register kill info by replacing a kill
     193             :   /// instruction with a new one.
     194             :   void replaceKillInstruction(unsigned Reg, MachineInstr &OldMI,
     195             :                               MachineInstr &NewMI);
     196             : 
     197             :   /// addVirtualRegisterKilled - Add information about the fact that the
     198             :   /// specified register is killed after being used by the specified
     199             :   /// instruction. If AddIfNotFound is true, add a implicit operand if it's
     200             :   /// not found.
     201      286137 :   void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr &MI,
     202             :                                 bool AddIfNotFound = false) {
     203      286137 :     if (MI.addRegisterKilled(IncomingReg, TRI, AddIfNotFound))
     204      572274 :       getVarInfo(IncomingReg).Kills.push_back(&MI);
     205      286137 :   }
     206             : 
     207             :   /// removeVirtualRegisterKilled - Remove the specified kill of the virtual
     208             :   /// register from the live variable information. Returns true if the
     209             :   /// variable was marked as killed by the specified instruction,
     210             :   /// false otherwise.
     211         773 :   bool removeVirtualRegisterKilled(unsigned reg, MachineInstr &MI) {
     212         773 :     if (!getVarInfo(reg).removeKill(MI))
     213             :       return false;
     214             : 
     215         773 :     bool Removed = false;
     216        2104 :     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     217        4208 :       MachineOperand &MO = MI.getOperand(i);
     218        4107 :       if (MO.isReg() && MO.isKill() && MO.getReg() == reg) {
     219         773 :         MO.setIsKill(false);
     220         773 :         Removed = true;
     221         773 :         break;
     222             :       }
     223             :     }
     224             : 
     225             :     assert(Removed && "Register is not used by this instruction!");
     226             :     (void)Removed;
     227             :     return true;
     228             :   }
     229             : 
     230             :   /// removeVirtualRegistersKilled - Remove all killed info for the specified
     231             :   /// instruction.
     232             :   void removeVirtualRegistersKilled(MachineInstr &MI);
     233             : 
     234             :   /// addVirtualRegisterDead - Add information about the fact that the specified
     235             :   /// register is dead after being used by the specified instruction. If
     236             :   /// AddIfNotFound is true, add a implicit operand if it's not found.
     237           1 :   void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr &MI,
     238             :                               bool AddIfNotFound = false) {
     239           1 :     if (MI.addRegisterDead(IncomingReg, TRI, AddIfNotFound))
     240           2 :       getVarInfo(IncomingReg).Kills.push_back(&MI);
     241           1 :   }
     242             : 
     243             :   /// removeVirtualRegisterDead - Remove the specified kill of the virtual
     244             :   /// register from the live variable information. Returns true if the
     245             :   /// variable was marked dead at the specified instruction, false
     246             :   /// otherwise.
     247        1864 :   bool removeVirtualRegisterDead(unsigned reg, MachineInstr &MI) {
     248        1864 :     if (!getVarInfo(reg).removeKill(MI))
     249             :       return false;
     250             : 
     251           1 :     bool Removed = false;
     252           1 :     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     253           2 :       MachineOperand &MO = MI.getOperand(i);
     254           2 :       if (MO.isReg() && MO.isDef() && MO.getReg() == reg) {
     255           1 :         MO.setIsDead(false);
     256           1 :         Removed = true;
     257           1 :         break;
     258             :       }
     259             :     }
     260             :     assert(Removed && "Register is not defined by this instruction!");
     261             :     (void)Removed;
     262             :     return true;
     263             :   }
     264             : 
     265             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
     266             : 
     267      141656 :   void releaseMemory() override {
     268      283312 :     VirtRegInfo.clear();
     269      141656 :   }
     270             : 
     271             :   /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL
     272             :   /// register.
     273             :   VarInfo &getVarInfo(unsigned RegIdx);
     274             : 
     275             :   void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock,
     276             :                                MachineBasicBlock *BB);
     277             :   void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock,
     278             :                                MachineBasicBlock *BB,
     279             :                                std::vector<MachineBasicBlock*> &WorkList);
     280             :   void HandleVirtRegDef(unsigned reg, MachineInstr &MI);
     281             :   void HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, MachineInstr &MI);
     282             : 
     283        2198 :   bool isLiveIn(unsigned Reg, const MachineBasicBlock &MBB) {
     284        2198 :     return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI);
     285             :   }
     286             : 
     287             :   /// isLiveOut - Determine if Reg is live out from MBB, when not considering
     288             :   /// PHI nodes. This means that Reg is either killed by a successor block or
     289             :   /// passed through one.
     290             :   bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB);
     291             : 
     292             :   /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All
     293             :   /// variables that are live out of DomBB and live into SuccBB will be marked
     294             :   /// as passing live through BB. This method assumes that the machine code is
     295             :   /// still in SSA form.
     296             :   void addNewBlock(MachineBasicBlock *BB,
     297             :                    MachineBasicBlock *DomBB,
     298             :                    MachineBasicBlock *SuccBB);
     299             : 
     300             :   /// isPHIJoin - Return true if Reg is a phi join register.
     301             :   bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); }
     302             : 
     303             :   /// setPHIJoin - Mark Reg as a phi join register.
     304       33422 :   void setPHIJoin(unsigned Reg) { PHIJoins.set(Reg); }
     305             : };
     306             : 
     307             : } // End llvm namespace
     308             : 
     309             : #endif

Generated by: LCOV version 1.13