LCOV - code coverage report
Current view: top level - lib/CodeGen - LivePhysRegs.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 154 166 92.8 %
Date: 2018-02-25 19:55:18 Functions: 16 17 94.1 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===//
       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 LivePhysRegs utility for tracking liveness of
      11             : // physical registers across machine instructions in forward or backward order.
      12             : // A more detailed description can be found in the corresponding header file.
      13             : //
      14             : //===----------------------------------------------------------------------===//
      15             : 
      16             : #include "llvm/CodeGen/LivePhysRegs.h"
      17             : #include "llvm/CodeGen/MachineFrameInfo.h"
      18             : #include "llvm/CodeGen/MachineFunction.h"
      19             : #include "llvm/CodeGen/MachineInstrBundle.h"
      20             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      21             : #include "llvm/Support/Debug.h"
      22             : #include "llvm/Support/raw_ostream.h"
      23             : using namespace llvm;
      24             : 
      25             : 
      26             : /// \brief Remove all registers from the set that get clobbered by the register
      27             : /// mask.
      28             : /// The clobbers set will be the list of live registers clobbered
      29             : /// by the regmask.
      30      272310 : void LivePhysRegs::removeRegsInMask(const MachineOperand &MO,
      31             :         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers) {
      32             :   SparseSet<unsigned>::iterator LRI = LiveRegs.begin();
      33     4992453 :   while (LRI != LiveRegs.end()) {
      34     9440286 :     if (MO.clobbersPhysReg(*LRI)) {
      35     1257939 :       if (Clobbers)
      36         250 :         Clobbers->push_back(std::make_pair(*LRI, &MO));
      37             :       LRI = LiveRegs.erase(LRI);
      38             :     } else
      39     3462204 :       ++LRI;
      40             :   }
      41      272310 : }
      42             : 
      43             : /// Remove defined registers and regmask kills from the set.
      44     2467077 : void LivePhysRegs::removeDefs(const MachineInstr &MI) {
      45    13266626 :   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
      46    10799549 :     if (O->isReg()) {
      47     7565002 :       if (!O->isDef())
      48     5209182 :         continue;
      49     2355820 :       unsigned Reg = O->getReg();
      50     2355820 :       if (!TargetRegisterInfo::isPhysicalRegister(Reg))
      51           7 :         continue;
      52     2355813 :       removeReg(Reg);
      53     3234547 :     } else if (O->isRegMask())
      54      187593 :       removeRegsInMask(*O);
      55             :   }
      56     2467077 : }
      57             : 
      58             : /// Add uses to the set.
      59     2467077 : void LivePhysRegs::addUses(const MachineInstr &MI) {
      60    13266626 :   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
      61    16563025 :     if (!O->isReg() || !O->readsReg())
      62     5763476 :       continue;
      63     5036073 :     unsigned Reg = O->getReg();
      64     6803515 :     if (!TargetRegisterInfo::isPhysicalRegister(Reg))
      65     1767442 :       continue;
      66     3268631 :     addReg(Reg);
      67             :   }
      68     2467077 : }
      69             : 
      70             : /// Simulates liveness when stepping backwards over an instruction(bundle):
      71             : /// Remove Defs, add uses. This is the recommended way of calculating liveness.
      72     2460586 : void LivePhysRegs::stepBackward(const MachineInstr &MI) {
      73             :   // Remove defined registers and regmask kills from the set.
      74     2460586 :   removeDefs(MI);
      75             : 
      76             :   // Add uses to the set.
      77     2460586 :   addUses(MI);
      78     2460586 : }
      79             : 
      80             : /// Simulates liveness when stepping forward over an instruction(bundle): Remove
      81             : /// killed-uses, add defs. This is the not recommended way, because it depends
      82             : /// on accurate kill flags. If possible use stepBackward() instead of this
      83             : /// function.
      84        3692 : void LivePhysRegs::stepForward(const MachineInstr &MI,
      85             :         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers) {
      86             :   // Remove killed registers from the set.
      87       22607 :   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
      88       18915 :     if (O->isReg()) {
      89       10647 :       unsigned Reg = O->getReg();
      90       10647 :       if (!TargetRegisterInfo::isPhysicalRegister(Reg))
      91         264 :         continue;
      92       10383 :       if (O->isDef()) {
      93             :         // Note, dead defs are still recorded.  The caller should decide how to
      94             :         // handle them.
      95        2856 :         Clobbers.push_back(std::make_pair(Reg, &*O));
      96             :       } else {
      97        7527 :         if (!O->isKill())
      98        5503 :           continue;
      99             :         assert(O->isUse());
     100        2024 :         removeReg(Reg);
     101             :       }
     102        8268 :     } else if (O->isRegMask())
     103          90 :       removeRegsInMask(*O, &Clobbers);
     104             :   }
     105             : 
     106             :   // Add defs to the set.
     107       43392 :   for (auto Reg : Clobbers) {
     108             :     // Skip dead defs.  They shouldn't be added to the set.
     109       37685 :     if (Reg.second->isReg() && Reg.second->isDead())
     110        1132 :       continue;
     111       18718 :     addReg(Reg.first);
     112             :   }
     113        3692 : }
     114             : 
     115             : /// Prin the currently live registers to OS.
     116           0 : void LivePhysRegs::print(raw_ostream &OS) const {
     117           0 :   OS << "Live Registers:";
     118           0 :   if (!TRI) {
     119           0 :     OS << " (uninitialized)\n";
     120           0 :     return;
     121             :   }
     122             : 
     123           0 :   if (empty()) {
     124           0 :     OS << " (empty)\n";
     125           0 :     return;
     126             :   }
     127             : 
     128           0 :   for (const_iterator I = begin(), E = end(); I != E; ++I)
     129           0 :     OS << " " << printReg(*I, TRI);
     130           0 :   OS << "\n";
     131             : }
     132             : 
     133             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     134             : LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
     135             :   dbgs() << "  " << *this;
     136             : }
     137             : #endif
     138             : 
     139     2149946 : bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
     140             :                              unsigned Reg) const {
     141     2149946 :   if (LiveRegs.count(Reg))
     142             :     return false;
     143     1192274 :   if (MRI.isReserved(Reg))
     144             :     return false;
     145    11712996 :   for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
     146     5103965 :     if (LiveRegs.count(*R))
     147       15866 :       return false;
     148             :   }
     149      752533 :   return true;
     150             : }
     151             : 
     152             : /// Add live-in registers of basic block \p MBB to \p LiveRegs.
     153      324715 : void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
     154     1166177 :   for (const auto &LI : MBB.liveins()) {
     155      841462 :     unsigned Reg = LI.PhysReg;
     156      841462 :     LaneBitmask Mask = LI.LaneMask;
     157      841462 :     MCSubRegIndexIterator S(Reg, TRI);
     158             :     assert(Mask.any() && "Invalid livein mask");
     159     1681148 :     if (Mask.all() || !S.isValid()) {
     160      839686 :       addReg(Reg);
     161             :       continue;
     162             :     }
     163       12271 :     for (; S.isValid(); ++S) {
     164             :       unsigned SI = S.getSubRegIndex();
     165       20990 :       if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
     166        7435 :         addReg(S.getSubReg());
     167             :     }
     168             :   }
     169      324715 : }
     170             : 
     171             : /// Adds all callee saved registers to \p LiveRegs.
     172      366490 : static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
     173             :                                const MachineFunction &MF) {
     174      366490 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     175     3603530 :   for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
     176     3237040 :     LiveRegs.addReg(*CSR);
     177      366490 : }
     178             : 
     179      369250 : void LivePhysRegs::addPristines(const MachineFunction &MF) {
     180      369250 :   const MachineFrameInfo &MFI = MF.getFrameInfo();
     181      369250 :   if (!MFI.isCalleeSavedInfoValid())
     182      367716 :     return;
     183             :   /// This function will usually be called on an empty object, handle this
     184             :   /// as a special case.
     185      366490 :   if (empty()) {
     186             :     /// Add all callee saved regs, then remove the ones that are saved and
     187             :     /// restored.
     188      364956 :     addCalleeSavedRegs(*this, MF);
     189             :     /// Remove the ones that are not saved/restored; they are pristine.
     190      364956 :     for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
     191      880968 :       removeReg(Info.getReg());
     192             :     return;
     193             :   }
     194             :   /// If a callee-saved register that is not pristine is already present
     195             :   /// in the set, we should make sure that it stays in it. Precompute the
     196             :   /// set of pristine registers in a separate object.
     197             :   /// Add all callee saved regs, then remove the ones that are saved+restored.
     198        1534 :   LivePhysRegs Pristine(*TRI);
     199        1534 :   addCalleeSavedRegs(Pristine, MF);
     200             :   /// Remove the ones that are not saved/restored; they are pristine.
     201        1534 :   for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
     202         786 :     Pristine.removeReg(Info.getReg());
     203      138126 :   for (MCPhysReg R : Pristine)
     204       68296 :     addReg(R);
     205             : }
     206             : 
     207      376883 : void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
     208             :   // To get the live-outs we simply merge the live-ins of all successors.
     209      698497 :   for (const MachineBasicBlock *Succ : MBB.successors())
     210      321614 :     addBlockLiveIns(*Succ);
     211      376883 :   if (MBB.isReturnBlock()) {
     212             :     // Return blocks are a special case because we currently don't mark up
     213             :     // return instructions completely: specifically, there is no explicit
     214             :     // use for callee-saved registers. So we add all callee saved registers
     215             :     // that are saved and restored (somewhere). This does not include
     216             :     // callee saved registers that are unused and hence not saved and
     217             :     // restored; they are called pristine.
     218             :     // FIXME: PEI should add explicit markings to return instructions
     219             :     // instead of implicitly handling them here.
     220      151903 :     const MachineFunction &MF = *MBB.getParent();
     221      151903 :     const MachineFrameInfo &MFI = MF.getFrameInfo();
     222      151903 :     if (MFI.isCalleeSavedInfoValid()) {
     223      150755 :       for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
     224       46958 :         if (Info.isRestored())
     225       44678 :           addReg(Info.getReg());
     226             :     }
     227             :   }
     228      376882 : }
     229             : 
     230      366149 : void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
     231      366149 :   const MachineFunction &MF = *MBB.getParent();
     232      366149 :   addPristines(MF);
     233      366149 :   addLiveOutsNoPristines(MBB);
     234      366149 : }
     235             : 
     236        3101 : void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
     237        3101 :   const MachineFunction &MF = *MBB.getParent();
     238        3101 :   addPristines(MF);
     239        3101 :   addBlockLiveIns(MBB);
     240        3101 : }
     241             : 
     242        9053 : void llvm::computeLiveIns(LivePhysRegs &LiveRegs,
     243             :                           const MachineBasicBlock &MBB) {
     244        9053 :   const MachineFunction &MF = *MBB.getParent();
     245        9053 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     246        9053 :   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
     247             :   LiveRegs.init(TRI);
     248        9053 :   LiveRegs.addLiveOutsNoPristines(MBB);
     249       47300 :   for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
     250       29194 :     LiveRegs.stepBackward(MI);
     251        9053 : }
     252             : 
     253        9053 : void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
     254             :   assert(MBB.livein_empty() && "Expected empty live-in list");
     255        9053 :   const MachineFunction &MF = *MBB.getParent();
     256        9053 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     257        9053 :   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
     258      207349 :   for (MCPhysReg Reg : LiveRegs) {
     259       99148 :     if (MRI.isReserved(Reg))
     260       31921 :       continue;
     261             :     // Skip the register if we are about to add one of its super registers.
     262             :     bool ContainsSuperReg = false;
     263       82808 :     for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
     264      111219 :       if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) {
     265             :         ContainsSuperReg = true;
     266             :         break;
     267             :       }
     268             :     }
     269       67227 :     if (ContainsSuperReg)
     270       47819 :       continue;
     271             :     MBB.addLiveIn(Reg);
     272             :   }
     273        9053 : }
     274             : 
     275        1540 : void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) {
     276        1540 :   const MachineFunction &MF = *MBB.getParent();
     277        1540 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     278        1540 :   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
     279             : 
     280             :   // We walk through the block backwards and start with the live outs.
     281             :   LivePhysRegs LiveRegs;
     282             :   LiveRegs.init(TRI);
     283        1540 :   LiveRegs.addLiveOutsNoPristines(MBB);
     284             : 
     285        9571 :   for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
     286             :     // Recompute dead flags.
     287       34037 :     for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
     288       46066 :       if (!MO->isReg() || !MO->isDef() || MO->isDebug())
     289       21700 :         continue;
     290             : 
     291        5846 :       unsigned Reg = MO->getReg();
     292        5846 :       if (Reg == 0)
     293           0 :         continue;
     294             :       assert(TargetRegisterInfo::isPhysicalRegister(Reg));
     295             : 
     296        5846 :       bool IsNotLive = LiveRegs.available(MRI, Reg);
     297             :       MO->setIsDead(IsNotLive);
     298             :     }
     299             : 
     300             :     // Step backward over defs.
     301        6491 :     LiveRegs.removeDefs(MI);
     302             : 
     303             :     // Recompute kill flags.
     304       34037 :     for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
     305       27552 :       if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
     306       14982 :         continue;
     307             : 
     308       12564 :       unsigned Reg = MO->getReg();
     309       15435 :       if (Reg == 0)
     310        2871 :         continue;
     311             :       assert(TargetRegisterInfo::isPhysicalRegister(Reg));
     312             : 
     313        9693 :       bool IsNotLive = LiveRegs.available(MRI, Reg);
     314             :       MO->setIsKill(IsNotLive);
     315             :     }
     316             : 
     317             :     // Complete the stepbackward.
     318        6491 :     LiveRegs.addUses(MI);
     319             :   }
     320        1540 : }
     321             : 
     322        3569 : void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
     323             :                                 MachineBasicBlock &MBB) {
     324        3569 :   computeLiveIns(LiveRegs, MBB);
     325        3569 :   addLiveIns(MBB, LiveRegs);
     326        3569 : }

Generated by: LCOV version 1.13