LCOV - code coverage report
Current view: top level - lib/CodeGen - RegAllocBasic.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 114 117 97.4 %
Date: 2017-09-14 15:23:50 Functions: 20 20 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===//
       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 defines the RABasic function pass, which provides a minimal
      11             : // implementation of the basic register allocator.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #include "AllocationOrder.h"
      16             : #include "LiveDebugVariables.h"
      17             : #include "RegAllocBase.h"
      18             : #include "Spiller.h"
      19             : #include "llvm/Analysis/AliasAnalysis.h"
      20             : #include "llvm/CodeGen/CalcSpillWeights.h"
      21             : #include "llvm/CodeGen/LiveIntervalAnalysis.h"
      22             : #include "llvm/CodeGen/LiveRangeEdit.h"
      23             : #include "llvm/CodeGen/LiveRegMatrix.h"
      24             : #include "llvm/CodeGen/LiveStackAnalysis.h"
      25             : #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
      26             : #include "llvm/CodeGen/MachineFunctionPass.h"
      27             : #include "llvm/CodeGen/MachineInstr.h"
      28             : #include "llvm/CodeGen/MachineLoopInfo.h"
      29             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      30             : #include "llvm/CodeGen/Passes.h"
      31             : #include "llvm/CodeGen/RegAllocRegistry.h"
      32             : #include "llvm/CodeGen/VirtRegMap.h"
      33             : #include "llvm/PassAnalysisSupport.h"
      34             : #include "llvm/Support/Debug.h"
      35             : #include "llvm/Support/raw_ostream.h"
      36             : #include "llvm/Target/TargetRegisterInfo.h"
      37             : #include <cstdlib>
      38             : #include <queue>
      39             : 
      40             : using namespace llvm;
      41             : 
      42             : #define DEBUG_TYPE "regalloc"
      43             : 
      44       72306 : static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
      45       72306 :                                       createBasicRegisterAllocator);
      46             : 
      47             : namespace {
      48             :   struct CompSpillWeight {
      49             :     bool operator()(LiveInterval *A, LiveInterval *B) const {
      50             :       return A->weight < B->weight;
      51             :     }
      52             :   };
      53             : }
      54             : 
      55             : namespace {
      56             : /// RABasic provides a minimal implementation of the basic register allocation
      57             : /// algorithm. It prioritizes live virtual registers by spill weight and spills
      58             : /// whenever a register is unavailable. This is not practical in production but
      59             : /// provides a useful baseline both for measuring other allocators and comparing
      60             : /// the speed of the basic algorithm against other styles of allocators.
      61         264 : class RABasic : public MachineFunctionPass,
      62             :                 public RegAllocBase,
      63             :                 private LiveRangeEdit::Delegate {
      64             :   // context
      65             :   MachineFunction *MF;
      66             : 
      67             :   // state
      68             :   std::unique_ptr<Spiller> SpillerInstance;
      69             :   std::priority_queue<LiveInterval*, std::vector<LiveInterval*>,
      70             :                       CompSpillWeight> Queue;
      71             : 
      72             :   // Scratch space.  Allocated here to avoid repeated malloc calls in
      73             :   // selectOrSplit().
      74             :   BitVector UsableRegs;
      75             : 
      76             :   bool LRE_CanEraseVirtReg(unsigned) override;
      77             :   void LRE_WillShrinkVirtReg(unsigned) override;
      78             : 
      79             : public:
      80             :   RABasic();
      81             : 
      82             :   /// Return the pass name.
      83          44 :   StringRef getPassName() const override { return "Basic Register Allocator"; }
      84             : 
      85             :   /// RABasic analysis usage.
      86             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
      87             : 
      88             :   void releaseMemory() override;
      89             : 
      90        1612 :   Spiller &spiller() override { return *SpillerInstance; }
      91             : 
      92        3726 :   void enqueue(LiveInterval *LI) override {
      93        3727 :     Queue.push(LI);
      94        3726 :   }
      95             : 
      96        3942 :   LiveInterval *dequeue() override {
      97        7884 :     if (Queue.empty())
      98             :       return nullptr;
      99        7454 :     LiveInterval *LI = Queue.top();
     100        7454 :     Queue.pop();
     101        3727 :     return LI;
     102             :   }
     103             : 
     104             :   unsigned selectOrSplit(LiveInterval &VirtReg,
     105             :                          SmallVectorImpl<unsigned> &SplitVRegs) override;
     106             : 
     107             :   /// Perform register allocation.
     108             :   bool runOnMachineFunction(MachineFunction &mf) override;
     109             : 
     110          44 :   MachineFunctionProperties getRequiredProperties() const override {
     111         132 :     return MachineFunctionProperties().set(
     112         132 :         MachineFunctionProperties::Property::NoPHIs);
     113             :   }
     114             : 
     115             :   // Helper for spilling all live virtual registers currently unified under preg
     116             :   // that interfere with the most recently queried lvr.  Return true if spilling
     117             :   // was successful, and append any new spilled/split intervals to splitLVRs.
     118             :   bool spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
     119             :                           SmallVectorImpl<unsigned> &SplitVRegs);
     120             : 
     121             :   static char ID;
     122             : };
     123             : 
     124             : char RABasic::ID = 0;
     125             : 
     126             : } // end anonymous namespace
     127             : 
     128             : char &llvm::RABasicID = RABasic::ID;
     129             : 
     130       20212 : INITIALIZE_PASS_BEGIN(RABasic, "regallocbasic", "Basic Register Allocator",
     131             :                       false, false)
     132       20212 : INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
     133       20212 : INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
     134       20212 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
     135       20212 : INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer)
     136       20212 : INITIALIZE_PASS_DEPENDENCY(MachineScheduler)
     137       20212 : INITIALIZE_PASS_DEPENDENCY(LiveStacks)
     138       20212 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     139       20212 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
     140       20212 : INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
     141       20212 : INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix)
     142      151199 : INITIALIZE_PASS_END(RABasic, "regallocbasic", "Basic Register Allocator", false,
     143             :                     false)
     144             : 
     145         836 : bool RABasic::LRE_CanEraseVirtReg(unsigned VirtReg) {
     146        1672 :   if (VRM->hasPhys(VirtReg)) {
     147           0 :     LiveInterval &LI = LIS->getInterval(VirtReg);
     148           0 :     Matrix->unassign(LI);
     149             :     aboutToRemoveInterval(LI);
     150           0 :     return true;
     151             :   }
     152             :   // Unassigned virtreg is probably in the priority queue.
     153             :   // RegAllocBase will erase it after dequeueing.
     154             :   return false;
     155             : }
     156             : 
     157         252 : void RABasic::LRE_WillShrinkVirtReg(unsigned VirtReg) {
     158         504 :   if (!VRM->hasPhys(VirtReg))
     159             :     return;
     160             : 
     161             :   // Register is assigned, put it back on the queue for reassignment.
     162           1 :   LiveInterval &LI = LIS->getInterval(VirtReg);
     163           1 :   Matrix->unassign(LI);
     164           1 :   enqueue(&LI);
     165             : }
     166             : 
     167         220 : RABasic::RABasic(): MachineFunctionPass(ID) {
     168          44 : }
     169             : 
     170          44 : void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
     171          44 :   AU.setPreservesCFG();
     172          44 :   AU.addRequired<AAResultsWrapperPass>();
     173          44 :   AU.addPreserved<AAResultsWrapperPass>();
     174          44 :   AU.addRequired<LiveIntervals>();
     175          44 :   AU.addPreserved<LiveIntervals>();
     176          44 :   AU.addPreserved<SlotIndexes>();
     177          44 :   AU.addRequired<LiveDebugVariables>();
     178          44 :   AU.addPreserved<LiveDebugVariables>();
     179          44 :   AU.addRequired<LiveStacks>();
     180          44 :   AU.addPreserved<LiveStacks>();
     181          44 :   AU.addRequired<MachineBlockFrequencyInfo>();
     182          44 :   AU.addPreserved<MachineBlockFrequencyInfo>();
     183          44 :   AU.addRequiredID(MachineDominatorsID);
     184          88 :   AU.addPreservedID(MachineDominatorsID);
     185          44 :   AU.addRequired<MachineLoopInfo>();
     186          44 :   AU.addPreserved<MachineLoopInfo>();
     187          44 :   AU.addRequired<VirtRegMap>();
     188          44 :   AU.addPreserved<VirtRegMap>();
     189          44 :   AU.addRequired<LiveRegMatrix>();
     190          44 :   AU.addPreserved<LiveRegMatrix>();
     191          44 :   MachineFunctionPass::getAnalysisUsage(AU);
     192          44 : }
     193             : 
     194         215 : void RABasic::releaseMemory() {
     195         860 :   SpillerInstance.reset();
     196         215 : }
     197             : 
     198             : 
     199             : // Spill or split all live virtual registers currently unified under PhysReg
     200             : // that interfere with VirtReg. The newly spilled or split live intervals are
     201             : // returned by appending them to SplitVRegs.
     202       29483 : bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
     203             :                                  SmallVectorImpl<unsigned> &SplitVRegs) {
     204             :   // Record each interference and determine if all are spillable before mutating
     205             :   // either the union or live intervals.
     206       58966 :   SmallVector<LiveInterval*, 8> Intfs;
     207             : 
     208             :   // Collect interferences assigned to any alias of the physical register.
     209       58978 :   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
     210       58976 :     LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
     211       29488 :     Q.collectInterferingVRegs();
     212       58986 :     for (unsigned i = Q.interferingVRegs().size(); i; --i) {
     213       58972 :       LiveInterval *Intf = Q.interferingVRegs()[i - 1];
     214       58972 :       if (!Intf->isSpillable() || Intf->weight > VirtReg.weight)
     215       29476 :         return false;
     216          10 :       Intfs.push_back(Intf);
     217             :     }
     218             :   }
     219             :   DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) <<
     220             :         " interferences with " << VirtReg << "\n");
     221             :   assert(!Intfs.empty() && "expected interference");
     222             : 
     223             :   // Spill each interfering vreg allocated to PhysReg or an alias.
     224          24 :   for (unsigned i = 0, e = Intfs.size(); i != e; ++i) {
     225          20 :     LiveInterval &Spill = *Intfs[i];
     226             : 
     227             :     // Skip duplicates.
     228          20 :     if (!VRM->hasPhys(Spill.reg))
     229           3 :       continue;
     230             : 
     231             :     // Deallocate the interfering vreg by removing it from the union.
     232             :     // A LiveInterval instance may not be in a union during modification!
     233           7 :     Matrix->unassign(Spill);
     234             : 
     235             :     // Spill the extracted interval.
     236          21 :     LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
     237          14 :     spiller().spill(LRE);
     238             :   }
     239             :   return true;
     240             : }
     241             : 
     242             : // Driver for the register assignment and splitting heuristics.
     243             : // Manages iteration over the LiveIntervalUnions.
     244             : //
     245             : // This is a minimal implementation of register assignment and splitting that
     246             : // spills whenever we run out of registers.
     247             : //
     248             : // selectOrSplit can only be called once per live virtual register. We then do a
     249             : // single interference test for each register the correct class until we find an
     250             : // available register. So, the number of interference tests in the worst case is
     251             : // |vregs| * |machineregs|. And since the number of interference tests is
     252             : // minimal, there is no value in caching them outside the scope of
     253             : // selectOrSplit().
     254        3726 : unsigned RABasic::selectOrSplit(LiveInterval &VirtReg,
     255             :                                 SmallVectorImpl<unsigned> &SplitVRegs) {
     256             :   // Populate a list of physical register spill candidates.
     257        7452 :   SmallVector<unsigned, 8> PhysRegSpillCands;
     258             : 
     259             :   // Check for an available register in this class.
     260        7452 :   AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
     261      114493 :   while (unsigned PhysReg = Order.next()) {
     262             :     // Check for interference in PhysReg
     263      224666 :     switch (Matrix->checkInterference(VirtReg, PhysReg)) {
     264        3132 :     case LiveRegMatrix::IK_Free:
     265             :       // PhysReg is available, allocate it.
     266        3132 :       return PhysReg;
     267             : 
     268       37785 :     case LiveRegMatrix::IK_VirtReg:
     269             :       // Only virtual registers in the way, we may be able to spill them.
     270       37785 :       PhysRegSpillCands.push_back(PhysReg);
     271      148552 :       continue;
     272             : 
     273       72982 :     default:
     274             :       // RegMask or RegUnit interference.
     275       72982 :       continue;
     276             :     }
     277      110767 :   }
     278             : 
     279             :   // Try to spill another interfering reg with less spill weight.
     280       30070 :   for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
     281       30664 :        PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
     282       29483 :     if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs))
     283             :       continue;
     284             : 
     285             :     assert(!Matrix->checkInterference(VirtReg, *PhysRegI) &&
     286             :            "Interference after spill.");
     287             :     // Tell the caller to allocate to this newly freed physical register.
     288           7 :     return *PhysRegI;
     289             :   }
     290             : 
     291             :   // No other spill candidates were found, so spill the current VirtReg.
     292             :   DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
     293        1174 :   if (!VirtReg.isSpillable())
     294             :     return ~0u;
     295        1752 :   LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
     296        1168 :   spiller().spill(LRE);
     297             : 
     298             :   // The live virtual register requesting allocation was spilled, so tell
     299             :   // the caller not to allocate anything during this round.
     300             :   return 0;
     301             : }
     302             : 
     303         215 : bool RABasic::runOnMachineFunction(MachineFunction &mf) {
     304             :   DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
     305             :                << "********** Function: "
     306             :                << mf.getName() << '\n');
     307             : 
     308         215 :   MF = &mf;
     309         215 :   RegAllocBase::init(getAnalysis<VirtRegMap>(),
     310             :                      getAnalysis<LiveIntervals>(),
     311             :                      getAnalysis<LiveRegMatrix>());
     312             : 
     313         215 :   calculateSpillWeightsAndHints(*LIS, *MF, VRM,
     314         215 :                                 getAnalysis<MachineLoopInfo>(),
     315         215 :                                 getAnalysis<MachineBlockFrequencyInfo>());
     316             : 
     317         430 :   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
     318             : 
     319         215 :   allocatePhysRegs();
     320         215 :   postOptimization();
     321             : 
     322             :   // Diagnostic output before rewriting
     323             :   DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
     324             : 
     325         430 :   releaseMemory();
     326         215 :   return true;
     327             : }
     328             : 
     329          42 : FunctionPass* llvm::createBasicRegisterAllocator()
     330             : {
     331          42 :   return new RABasic();
     332      216918 : }

Generated by: LCOV version 1.13