LCOV - code coverage report
Current view: top level - lib/CodeGen - LivePhysRegs.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 145 156 92.9 %
Date: 2018-09-23 13:06:45 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/Config/llvm-config.h"
      22             : #include "llvm/Support/Debug.h"
      23             : #include "llvm/Support/raw_ostream.h"
      24             : using namespace llvm;
      25             : 
      26             : 
      27             : /// Remove all registers from the set that get clobbered by the register
      28             : /// mask.
      29             : /// The clobbers set will be the list of live registers clobbered
      30             : /// by the regmask.
      31      222118 : void LivePhysRegs::removeRegsInMask(const MachineOperand &MO,
      32             :         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers) {
      33             :   SparseSet<unsigned>::iterator LRI = LiveRegs.begin();
      34     4925485 :   while (LRI != LiveRegs.end()) {
      35     9406734 :     if (MO.clobbersPhysReg(*LRI)) {
      36     1686170 :       if (Clobbers)
      37         254 :         Clobbers->push_back(std::make_pair(*LRI, &MO));
      38     1686170 :       LRI = LiveRegs.erase(LRI);
      39             :     } else
      40     3017197 :       ++LRI;
      41             :   }
      42      222118 : }
      43             : 
      44             : /// Remove defined registers and regmask kills from the set.
      45     3592272 : void LivePhysRegs::removeDefs(const MachineInstr &MI) {
      46    20264649 :   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
      47    16672378 :     if (O->isReg()) {
      48    10850155 :       if (!O->isDef() || O->isDebug())
      49             :         continue;
      50     3111370 :       unsigned Reg = O->getReg();
      51     3111370 :       if (!TargetRegisterInfo::isPhysicalRegister(Reg))
      52             :         continue;
      53     3111363 :       removeReg(Reg);
      54     5822223 :     } else if (O->isRegMask())
      55      176837 :       removeRegsInMask(*O);
      56             :   }
      57     3592271 : }
      58             : 
      59             : /// Add uses to the set.
      60     3592272 : void LivePhysRegs::addUses(const MachineInstr &MI) {
      61    20264650 :   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
      62    24261175 :     if (!O->isReg() || !O->readsReg() || O->isDebug())
      63             :       continue;
      64     7352563 :     unsigned Reg = O->getReg();
      65     7352563 :     if (!TargetRegisterInfo::isPhysicalRegister(Reg))
      66             :       continue;
      67     4075216 :     addReg(Reg);
      68             :   }
      69     3592272 : }
      70             : 
      71             : /// Simulates liveness when stepping backwards over an instruction(bundle):
      72             : /// Remove Defs, add uses. This is the recommended way of calculating liveness.
      73     3585102 : void LivePhysRegs::stepBackward(const MachineInstr &MI) {
      74             :   // Remove defined registers and regmask kills from the set.
      75     3585102 :   removeDefs(MI);
      76             : 
      77             :   // Add uses to the set.
      78     3585102 :   addUses(MI);
      79     3585102 : }
      80             : 
      81             : /// Simulates liveness when stepping forward over an instruction(bundle): Remove
      82             : /// killed-uses, add defs. This is the not recommended way, because it depends
      83             : /// on accurate kill flags. If possible use stepBackward() instead of this
      84             : /// function.
      85        4119 : void LivePhysRegs::stepForward(const MachineInstr &MI,
      86             :         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers) {
      87             :   // Remove killed registers from the set.
      88       24835 :   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
      89       20716 :     if (O->isReg() && !O->isDebug()) {
      90       11955 :       unsigned Reg = O->getReg();
      91       11955 :       if (!TargetRegisterInfo::isPhysicalRegister(Reg))
      92             :         continue;
      93       11644 :       if (O->isDef()) {
      94             :         // Note, dead defs are still recorded.  The caller should decide how to
      95             :         // handle them.
      96        3206 :         Clobbers.push_back(std::make_pair(Reg, &*O));
      97             :       } else {
      98        8438 :         if (!O->isKill())
      99             :           continue;
     100             :         assert(O->isUse());
     101        2294 :         removeReg(Reg);
     102             :       }
     103        8761 :     } else if (O->isRegMask())
     104         170 :       removeRegsInMask(*O, &Clobbers);
     105             :   }
     106             : 
     107             :   // Add defs to the set.
     108       23817 :   for (auto Reg : Clobbers) {
     109             :     // Skip dead defs and registers clobbered by regmasks. They shouldn't
     110             :     // be added to the set.
     111       19698 :     if (Reg.second->isReg() && Reg.second->isDead())
     112             :       continue;
     113       18181 :     if (Reg.second->isRegMask() &&
     114        1711 :         MachineOperand::clobbersPhysReg(Reg.second->getRegMask(), Reg.first))
     115             :       continue;
     116       16470 :     addReg(Reg.first);
     117             :   }
     118        4119 : }
     119             : 
     120             : /// Prin the currently live registers to OS.
     121           0 : void LivePhysRegs::print(raw_ostream &OS) const {
     122           0 :   OS << "Live Registers:";
     123           0 :   if (!TRI) {
     124           0 :     OS << " (uninitialized)\n";
     125           0 :     return;
     126             :   }
     127             : 
     128           0 :   if (empty()) {
     129           0 :     OS << " (empty)\n";
     130           0 :     return;
     131             :   }
     132             : 
     133           0 :   for (const_iterator I = begin(), E = end(); I != E; ++I)
     134           0 :     OS << " " << printReg(*I, TRI);
     135           0 :   OS << "\n";
     136             : }
     137             : 
     138             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     139             : LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
     140             :   dbgs() << "  " << *this;
     141             : }
     142             : #endif
     143             : 
     144     2220392 : bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
     145             :                              unsigned Reg) const {
     146     2220392 :   if (LiveRegs.count(Reg))
     147             :     return false;
     148     1091437 :   if (MRI.isReserved(Reg))
     149             :     return false;
     150     6801566 :   for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
     151     5996104 :     if (LiveRegs.count(*R))
     152       15092 :       return false;
     153             :   }
     154      805462 :   return true;
     155             : }
     156             : 
     157             : /// Add live-in registers of basic block \p MBB to \p LiveRegs.
     158      635746 : void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
     159     2214114 :   for (const auto &LI : MBB.liveins()) {
     160     1578368 :     unsigned Reg = LI.PhysReg;
     161     1578368 :     LaneBitmask Mask = LI.LaneMask;
     162     1578368 :     MCSubRegIndexIterator S(Reg, TRI);
     163             :     assert(Mask.any() && "Invalid livein mask");
     164     1578368 :     if (Mask.all() || !S.isValid()) {
     165     1576261 :       addReg(Reg);
     166             :       continue;
     167             :     }
     168       14206 :     for (; S.isValid(); ++S) {
     169             :       unsigned SI = S.getSubRegIndex();
     170       24198 :       if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
     171        8439 :         addReg(S.getSubReg());
     172             :     }
     173             :   }
     174      635746 : }
     175             : 
     176             : /// Adds all callee saved registers to \p LiveRegs.
     177      567621 : static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
     178             :                                const MachineFunction &MF) {
     179      567621 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     180     5115925 :   for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
     181     4548304 :     LiveRegs.addReg(*CSR);
     182      567621 : }
     183             : 
     184      647741 : void LivePhysRegs::addPristines(const MachineFunction &MF) {
     185      647741 :   const MachineFrameInfo &MFI = MF.getFrameInfo();
     186      647741 :   if (!MFI.isCalleeSavedInfoValid())
     187      646023 :     return;
     188             :   /// This function will usually be called on an empty object, handle this
     189             :   /// as a special case.
     190      567621 :   if (empty()) {
     191             :     /// Add all callee saved regs, then remove the ones that are saved and
     192             :     /// restored.
     193      565903 :     addCalleeSavedRegs(*this, MF);
     194             :     /// Remove the ones that are not saved/restored; they are pristine.
     195     2111850 :     for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
     196     1545947 :       removeReg(Info.getReg());
     197             :     return;
     198             :   }
     199             :   /// If a callee-saved register that is not pristine is already present
     200             :   /// in the set, we should make sure that it stays in it. Precompute the
     201             :   /// set of pristine registers in a separate object.
     202             :   /// Add all callee saved regs, then remove the ones that are saved+restored.
     203        1718 :   LivePhysRegs Pristine(*TRI);
     204        1718 :   addCalleeSavedRegs(Pristine, MF);
     205             :   /// Remove the ones that are not saved/restored; they are pristine.
     206        2545 :   for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
     207         827 :     Pristine.removeReg(Info.getReg());
     208       76714 :   for (MCPhysReg R : Pristine)
     209       74996 :     addReg(R);
     210             : }
     211             : 
     212      665820 : void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
     213             :   // To get the live-outs we simply merge the live-ins of all successors.
     214     1298090 :   for (const MachineBasicBlock *Succ : MBB.successors())
     215      632270 :     addBlockLiveIns(*Succ);
     216      665820 :   if (MBB.isReturnBlock()) {
     217             :     // Return blocks are a special case because we currently don't mark up
     218             :     // return instructions completely: specifically, there is no explicit
     219             :     // use for callee-saved registers. So we add all callee saved registers
     220             :     // that are saved and restored (somewhere). This does not include
     221             :     // callee saved registers that are unused and hence not saved and
     222             :     // restored; they are called pristine.
     223             :     // FIXME: PEI should add explicit markings to return instructions
     224             :     // instead of implicitly handling them here.
     225      188335 :     const MachineFunction &MF = *MBB.getParent();
     226      188335 :     const MachineFrameInfo &MFI = MF.getFrameInfo();
     227      188335 :     if (MFI.isCalleeSavedInfoValid()) {
     228      243644 :       for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
     229       57188 :         if (Info.isRestored())
     230       54791 :           addReg(Info.getReg());
     231             :     }
     232             :   }
     233      665820 : }
     234             : 
     235      644265 : void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
     236      644265 :   const MachineFunction &MF = *MBB.getParent();
     237      644265 :   addPristines(MF);
     238      644265 :   addLiveOutsNoPristines(MBB);
     239      644265 : }
     240             : 
     241        3476 : void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
     242        3476 :   const MachineFunction &MF = *MBB.getParent();
     243        3476 :   addPristines(MF);
     244        3476 :   addBlockLiveIns(MBB);
     245        3476 : }
     246             : 
     247       19655 : void llvm::computeLiveIns(LivePhysRegs &LiveRegs,
     248             :                           const MachineBasicBlock &MBB) {
     249       19655 :   const MachineFunction &MF = *MBB.getParent();
     250       19655 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     251       19655 :   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
     252             :   LiveRegs.init(TRI);
     253       19655 :   LiveRegs.addLiveOutsNoPristines(MBB);
     254       83386 :   for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
     255       63731 :     LiveRegs.stepBackward(MI);
     256       19655 : }
     257             : 
     258       19655 : void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
     259             :   assert(MBB.livein_empty() && "Expected empty live-in list");
     260       19655 :   const MachineFunction &MF = *MBB.getParent();
     261       19655 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     262       19655 :   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
     263      326971 :   for (MCPhysReg Reg : LiveRegs) {
     264      307316 :     if (MRI.isReserved(Reg))
     265             :       continue;
     266             :     // Skip the register if we are about to add one of its super registers.
     267             :     bool ContainsSuperReg = false;
     268      250481 :     for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
     269      202548 :       if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) {
     270             :         ContainsSuperReg = true;
     271             :         break;
     272             :       }
     273             :     }
     274      219175 :     if (ContainsSuperReg)
     275             :       continue;
     276             :     MBB.addLiveIn(Reg);
     277             :   }
     278       19655 : }
     279             : 
     280        1726 : void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) {
     281        1726 :   const MachineFunction &MF = *MBB.getParent();
     282        1726 :   const MachineRegisterInfo &MRI = MF.getRegInfo();
     283        1726 :   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
     284             : 
     285             :   // We walk through the block backwards and start with the live outs.
     286             :   LivePhysRegs LiveRegs;
     287             :   LiveRegs.init(TRI);
     288        1726 :   LiveRegs.addLiveOutsNoPristines(MBB);
     289             : 
     290        8896 :   for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
     291             :     // Recompute dead flags.
     292       37817 :     for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
     293       30647 :       if (!MO->isReg() || !MO->isDef() || MO->isDebug())
     294             :         continue;
     295             : 
     296        6472 :       unsigned Reg = MO->getReg();
     297        6472 :       if (Reg == 0)
     298             :         continue;
     299             :       assert(TargetRegisterInfo::isPhysicalRegister(Reg));
     300             : 
     301        6472 :       bool IsNotLive = LiveRegs.available(MRI, Reg);
     302             :       MO->setIsDead(IsNotLive);
     303             :     }
     304             : 
     305             :     // Step backward over defs.
     306        7170 :     LiveRegs.removeDefs(MI);
     307             : 
     308             :     // Recompute kill flags.
     309       37817 :     for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
     310       44592 :       if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
     311             :         continue;
     312             : 
     313       13936 :       unsigned Reg = MO->getReg();
     314       13936 :       if (Reg == 0)
     315             :         continue;
     316             :       assert(TargetRegisterInfo::isPhysicalRegister(Reg));
     317             : 
     318       10780 :       bool IsNotLive = LiveRegs.available(MRI, Reg);
     319             :       MO->setIsKill(IsNotLive);
     320             :     }
     321             : 
     322             :     // Complete the stepbackward.
     323        7170 :     LiveRegs.addUses(MI);
     324             :   }
     325        1726 : }
     326             : 
     327        9272 : void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
     328             :                                 MachineBasicBlock &MBB) {
     329        9272 :   computeLiveIns(LiveRegs, MBB);
     330        9272 :   addLiveIns(MBB, LiveRegs);
     331        9272 : }

Generated by: LCOV version 1.13