LCOV - code coverage report
Current view: top level - lib/CodeGen - RegAllocBasic.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 91 93 97.8 %
Date: 2018-07-13 00:08:38 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/LiveIntervals.h"
      22             : #include "llvm/CodeGen/LiveRangeEdit.h"
      23             : #include "llvm/CodeGen/LiveRegMatrix.h"
      24             : #include "llvm/CodeGen/LiveStacks.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/TargetRegisterInfo.h"
      33             : #include "llvm/CodeGen/VirtRegMap.h"
      34             : #include "llvm/PassAnalysisSupport.h"
      35             : #include "llvm/Support/Debug.h"
      36             : #include "llvm/Support/raw_ostream.h"
      37             : #include <cstdlib>
      38             : #include <queue>
      39             : 
      40             : using namespace llvm;
      41             : 
      42             : #define DEBUG_TYPE "regalloc"
      43             : 
      44       99743 : static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
      45             :                                       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         132 : 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         444 :   Spiller &spiller() override { return *SpillerInstance; }
      91             : 
      92        5034 :   void enqueue(LiveInterval *LI) override {
      93        5035 :     Queue.push(LI);
      94        5034 :   }
      95             : 
      96        5257 :   LiveInterval *dequeue() override {
      97        5257 :     if (Queue.empty())
      98             :       return nullptr;
      99        5035 :     LiveInterval *LI = Queue.top();
     100             :     Queue.pop();
     101        5035 :     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          88 :     return MachineFunctionProperties().set(
     112          44 :         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       26316 : INITIALIZE_PASS_BEGIN(RABasic, "regallocbasic", "Basic Register Allocator",
     131             :                       false, false)
     132       26316 : INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
     133       26316 : INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
     134       26316 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
     135       26316 : INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer)
     136       26316 : INITIALIZE_PASS_DEPENDENCY(MachineScheduler)
     137       26316 : INITIALIZE_PASS_DEPENDENCY(LiveStacks)
     138       26316 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     139       26316 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
     140       26316 : INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
     141       26316 : INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix)
     142      146610 : INITIALIZE_PASS_END(RABasic, "regallocbasic", "Basic Register Allocator", false,
     143             :                     false)
     144             : 
     145         836 : bool RABasic::LRE_CanEraseVirtReg(unsigned VirtReg) {
     146         836 :   LiveInterval &LI = LIS->getInterval(VirtReg);
     147        1672 :   if (VRM->hasPhys(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             :   // Nonetheless, clear the live-range so that the debug
     155             :   // dump will show the right state for that VirtReg.
     156             :   LI.clear();
     157         836 :   return false;
     158             : }
     159             : 
     160         252 : void RABasic::LRE_WillShrinkVirtReg(unsigned VirtReg) {
     161         504 :   if (!VRM->hasPhys(VirtReg))
     162             :     return;
     163             : 
     164             :   // Register is assigned, put it back on the queue for reassignment.
     165           1 :   LiveInterval &LI = LIS->getInterval(VirtReg);
     166           1 :   Matrix->unassign(LI);
     167             :   enqueue(&LI);
     168             : }
     169             : 
     170          88 : RABasic::RABasic(): MachineFunctionPass(ID) {
     171          44 : }
     172             : 
     173          44 : void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
     174          44 :   AU.setPreservesCFG();
     175             :   AU.addRequired<AAResultsWrapperPass>();
     176             :   AU.addPreserved<AAResultsWrapperPass>();
     177             :   AU.addRequired<LiveIntervals>();
     178             :   AU.addPreserved<LiveIntervals>();
     179             :   AU.addPreserved<SlotIndexes>();
     180             :   AU.addRequired<LiveDebugVariables>();
     181             :   AU.addPreserved<LiveDebugVariables>();
     182             :   AU.addRequired<LiveStacks>();
     183             :   AU.addPreserved<LiveStacks>();
     184             :   AU.addRequired<MachineBlockFrequencyInfo>();
     185             :   AU.addPreserved<MachineBlockFrequencyInfo>();
     186          44 :   AU.addRequiredID(MachineDominatorsID);
     187             :   AU.addPreservedID(MachineDominatorsID);
     188             :   AU.addRequired<MachineLoopInfo>();
     189             :   AU.addPreserved<MachineLoopInfo>();
     190             :   AU.addRequired<VirtRegMap>();
     191             :   AU.addPreserved<VirtRegMap>();
     192             :   AU.addRequired<LiveRegMatrix>();
     193             :   AU.addPreserved<LiveRegMatrix>();
     194          44 :   MachineFunctionPass::getAnalysisUsage(AU);
     195          44 : }
     196             : 
     197         222 : void RABasic::releaseMemory() {
     198             :   SpillerInstance.reset();
     199         222 : }
     200             : 
     201             : 
     202             : // Spill or split all live virtual registers currently unified under PhysReg
     203             : // that interfere with VirtReg. The newly spilled or split live intervals are
     204             : // returned by appending them to SplitVRegs.
     205       29939 : bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
     206             :                                  SmallVectorImpl<unsigned> &SplitVRegs) {
     207             :   // Record each interference and determine if all are spillable before mutating
     208             :   // either the union or live intervals.
     209             :   SmallVector<LiveInterval*, 8> Intfs;
     210             : 
     211             :   // Collect interferences assigned to any alias of the physical register.
     212       59899 :   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
     213       59906 :     LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
     214       29953 :     Q.collectInterferingVRegs();
     215       29972 :     for (unsigned i = Q.interferingVRegs().size(); i; --i) {
     216       59902 :       LiveInterval *Intf = Q.interferingVRegs()[i - 1];
     217       59902 :       if (!Intf->isSpillable() || Intf->weight > VirtReg.weight)
     218       29932 :         return false;
     219          19 :       Intfs.push_back(Intf);
     220             :     }
     221             :   }
     222             :   LLVM_DEBUG(dbgs() << "spilling " << printReg(PhysReg, TRI)
     223             :                     << " interferences with " << VirtReg << "\n");
     224             :   assert(!Intfs.empty() && "expected interference");
     225             : 
     226             :   // Spill each interfering vreg allocated to PhysReg or an alias.
     227          26 :   for (unsigned i = 0, e = Intfs.size(); i != e; ++i) {
     228          38 :     LiveInterval &Spill = *Intfs[i];
     229             : 
     230             :     // Skip duplicates.
     231          38 :     if (!VRM->hasPhys(Spill.reg))
     232          12 :       continue;
     233             : 
     234             :     // Deallocate the interfering vreg by removing it from the union.
     235             :     // A LiveInterval instance may not be in a union during modification!
     236           7 :     Matrix->unassign(Spill);
     237             : 
     238             :     // Spill the extracted interval.
     239          14 :     LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
     240           7 :     spiller().spill(LRE);
     241             :   }
     242             :   return true;
     243             : }
     244             : 
     245             : // Driver for the register assignment and splitting heuristics.
     246             : // Manages iteration over the LiveIntervalUnions.
     247             : //
     248             : // This is a minimal implementation of register assignment and splitting that
     249             : // spills whenever we run out of registers.
     250             : //
     251             : // selectOrSplit can only be called once per live virtual register. We then do a
     252             : // single interference test for each register the correct class until we find an
     253             : // available register. So, the number of interference tests in the worst case is
     254             : // |vregs| * |machineregs|. And since the number of interference tests is
     255             : // minimal, there is no value in caching them outside the scope of
     256             : // selectOrSplit().
     257        5034 : unsigned RABasic::selectOrSplit(LiveInterval &VirtReg,
     258             :                                 SmallVectorImpl<unsigned> &SplitVRegs) {
     259             :   // Populate a list of physical register spill candidates.
     260             :   SmallVector<unsigned, 8> PhysRegSpillCands;
     261             : 
     262             :   // Check for an available register in this class.
     263        5034 :   AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
     264      114561 :   while (unsigned PhysReg = Order.next()) {
     265             :     // Check for interference in PhysReg
     266      223494 :     switch (Matrix->checkInterference(VirtReg, PhysReg)) {
     267        4440 :     case LiveRegMatrix::IK_Free:
     268             :       // PhysReg is available, allocate it.
     269        4440 :       return PhysReg;
     270             : 
     271       36988 :     case LiveRegMatrix::IK_VirtReg:
     272             :       // Only virtual registers in the way, we may be able to spill them.
     273       36988 :       PhysRegSpillCands.push_back(PhysReg);
     274      146515 :       continue;
     275             : 
     276       72539 :     default:
     277             :       // RegMask or RegUnit interference.
     278       72539 :       continue;
     279             :     }
     280      109527 :   }
     281             : 
     282             :   // Try to spill another interfering reg with less spill weight.
     283       29932 :   for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
     284       30526 :        PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
     285       29939 :     if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs))
     286             :       continue;
     287             : 
     288             :     assert(!Matrix->checkInterference(VirtReg, *PhysRegI) &&
     289             :            "Interference after spill.");
     290             :     // Tell the caller to allocate to this newly freed physical register.
     291           7 :     return *PhysRegI;
     292             :   }
     293             : 
     294             :   // No other spill candidates were found, so spill the current VirtReg.
     295             :   LLVM_DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
     296        1174 :   if (!VirtReg.isSpillable())
     297             :     return ~0u;
     298        1168 :   LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
     299         584 :   spiller().spill(LRE);
     300             : 
     301             :   // The live virtual register requesting allocation was spilled, so tell
     302             :   // the caller not to allocate anything during this round.
     303             :   return 0;
     304             : }
     305             : 
     306         222 : bool RABasic::runOnMachineFunction(MachineFunction &mf) {
     307             :   LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
     308             :                     << "********** Function: " << mf.getName() << '\n');
     309             : 
     310         222 :   MF = &mf;
     311         222 :   RegAllocBase::init(getAnalysis<VirtRegMap>(),
     312             :                      getAnalysis<LiveIntervals>(),
     313             :                      getAnalysis<LiveRegMatrix>());
     314             : 
     315         222 :   calculateSpillWeightsAndHints(*LIS, *MF, VRM,
     316         222 :                                 getAnalysis<MachineLoopInfo>(),
     317         222 :                                 getAnalysis<MachineBlockFrequencyInfo>());
     318             : 
     319         222 :   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
     320             : 
     321         222 :   allocatePhysRegs();
     322         222 :   postOptimization();
     323             : 
     324             :   // Diagnostic output before rewriting
     325             :   LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
     326             : 
     327             :   releaseMemory();
     328         222 :   return true;
     329             : }
     330             : 
     331          42 : FunctionPass* llvm::createBasicRegisterAllocator()
     332             : {
     333          42 :   return new RABasic();
     334      299229 : }

Generated by: LCOV version 1.13