Subzero: Rewrite the pass timing infrastructure.

src/IceRegAlloc.cpp

 //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the LinearScan class, which performs the
@@ skipping 46 matching lines @@
 // Constraints" by Hanspeter Mössenböck and Michael Pfeiffer,
 // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF .  This
 // implementation is modified to take affinity into account and allow
 // two interfering variables to share the same register in certain
 // cases.
 //
 // Requires running Cfg::liveness(Liveness_Intervals) in
 // preparation.  Results are assigned to Variable::RegNum for each
 // Variable.
 void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
+  static TimerIdT IDscan = GlobalContext::getTimerID("scan");

[jvoung (off chromium), 2014/09/30 20:19:04]

If it makes sense, it might be better to say "linear_scan" or something since
"scan" could seem a bit generic when placed alongside other timer names. On the
other hand, there's also the regAlloc timer, but this is after the bitvector
creation.

[Jim Stichnoth, 2014/09/30 22:46:00]

Done, with "linearScan" to match the style of the others.

I think it's good to keep this timer in addition to the regAlloc timer, in case
regAlloc one day is changed to do substantially more work.

+  TimerMarker T(IDscan, Func->getContext());
   assert(RegMaskFull.any()); // Sanity check
   Unhandled.clear();
   Handled.clear();
   Inactive.clear();
   Active.clear();
   Ostream &Str = Func->getContext()->getStrDump();
+  bool Verbose = Func->getContext()->isVerbose(IceV_LinearScan);
   Func->resetCurrentNode();
   VariablesMetadata *VMetadata = Func->getVMetadata();
 
   // Gather the live ranges of all variables and add them to the
   // Unhandled set.  TODO: Unhandled is a set<> which is based on a
   // balanced binary tree, so inserting live ranges for N variables is
   // O(N log N) complexity.  N may be proportional to the number of
   // instructions, thanks to temporary generation during lowering.  As
   // a result, it may be useful to design a better data structure for
   // storing Func->getVariables().
   const VarList &Vars = Func->getVariables();
-  for (VarList::const_iterator I = Vars.begin(), E = Vars.end(); I != E; ++I) {
-    Variable *Var = *I;
-    // Explicitly don't consider zero-weight variables, which are
-    // meant to be spill slots.
-    if (Var->getWeight() == RegWeight::Zero)
-      continue;
-    // Don't bother if the variable has a null live range, which means
-    // it was never referenced.
-    if (Var->getLiveRange().isEmpty())
-      continue;
-    Unhandled.insert(LiveRangeWrapper(Var));
-    if (Var->hasReg()) {
-      Var->setRegNumTmp(Var->getRegNum());
-      Var->setLiveRangeInfiniteWeight();
+  {
+    static TimerIdT IDinitUnhandled =
+        GlobalContext::getTimerID("initUnhandled");
+    TimerMarker T(IDinitUnhandled, Func->getContext());
+    for (VarList::const_iterator I = Vars.begin(), E = Vars.end(); I != E;
+         ++I) {
+      Variable *Var = *I;
+      // Explicitly don't consider zero-weight variables, which are
+      // meant to be spill slots.
+      if (Var->getWeight() == RegWeight::Zero)
+        continue;
+      // Don't bother if the variable has a null live range, which means
+      // it was never referenced.
+      if (Var->getLiveRange().isEmpty())
+        continue;
+      Unhandled.insert(LiveRangeWrapper(Var));
+      if (Var->hasReg()) {
+        Var->setRegNumTmp(Var->getRegNum());
+        Var->setLiveRangeInfiniteWeight();
+      }
     }
   }
 
   // RegUses[I] is the number of live ranges (variables) that register
   // I is currently assigned to.  It can be greater than 1 as a result
   // of Variable::AllowRegisterOverlap.

[jvoung (off chromium), 2014/09/30 20:19:04]

Update comment about Variable::AllowRegisterOverlap now that it's not part of
Variable?

[Jim Stichnoth, 2014/09/30 22:45:59]

Done.

   std::vector<int> RegUses(RegMaskFull.size());
   // Unhandled is already set to all ranges in increasing order of
   // start points.
   assert(Active.empty());
   assert(Inactive.empty());
   assert(Handled.empty());
   UnorderedRanges::iterator Next;
 
   while (!Unhandled.empty()) {
     LiveRangeWrapper Cur = *Unhandled.begin();
     Unhandled.erase(Unhandled.begin());
-    if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+    if (Verbose) {
       Str << "\nConsidering  ";
       Cur.dump(Func);
       Str << "\n";
     }
     const llvm::SmallBitVector RegMask =
         RegMaskFull &
         Func->getTarget()->getRegisterSetForType(Cur.Var->getType());
 
     // Check for precolored ranges.  If Cur is precolored, it
     // definitely gets that register.  Previously processed live
     // ranges would have avoided that register due to it being
     // precolored.  Future processed live ranges won't evict that
     // register because the live range has infinite weight.
     if (Cur.Var->hasReg()) {
       int32_t RegNum = Cur.Var->getRegNum();
       // RegNumTmp should have already been set above.
       assert(Cur.Var->getRegNumTmp() == RegNum);
-      if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+      if (Verbose) {
         Str << "Precoloring  ";
         Cur.dump(Func);
         Str << "\n";
       }
       Active.push_back(Cur);
       assert(RegUses[RegNum] >= 0);
       ++RegUses[RegNum];
       continue;
     }
 
     // Check for active ranges that have expired or become inactive.
     for (UnorderedRanges::iterator I = Active.begin(), E = Active.end(); I != E;
          I = Next) {
       Next = I;
       ++Next;
       LiveRangeWrapper Item = *I;
       bool Moved = false;
       if (Item.endsBefore(Cur)) {
         // Move Item from Active to Handled list.
-        if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+        if (Verbose) {
           Str << "Expiring     ";
           Item.dump(Func);
           Str << "\n";
         }
         Active.erase(I);
         Handled.push_back(Item);
         Moved = true;
       } else if (!Item.overlapsStart(Cur)) {
         // Move Item from Active to Inactive list.
-        if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+        if (Verbose) {
           Str << "Inactivating ";
           Item.dump(Func);
           Str << "\n";
         }
         Active.erase(I);
         Inactive.push_back(Item);
         Moved = true;
       }
       if (Moved) {
         // Decrement Item from RegUses[].
         assert(Item.Var->hasRegTmp());
         int32_t RegNum = Item.Var->getRegNumTmp();
         --RegUses[RegNum];
         assert(RegUses[RegNum] >= 0);
       }
     }
 
     // Check for inactive ranges that have expired or reactivated.
     for (UnorderedRanges::iterator I = Inactive.begin(), E = Inactive.end();
          I != E; I = Next) {
       Next = I;
       ++Next;
       LiveRangeWrapper Item = *I;
       if (Item.endsBefore(Cur)) {
         // Move Item from Inactive to Handled list.
-        if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+        if (Verbose) {
           Str << "Expiring     ";
           Item.dump(Func);
           Str << "\n";
         }
         Inactive.erase(I);
         Handled.push_back(Item);
       } else if (Item.overlapsStart(Cur)) {
         // Move Item from Inactive to Active list.
-        if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+        if (Verbose) {
           Str << "Reactivating ";
           Item.dump(Func);
           Str << "\n";
         }
         Inactive.erase(I);
         Active.push_back(Item);
         // Increment Item in RegUses[].
         assert(Item.Var->hasRegTmp());
         int32_t RegNum = Item.Var->getRegNumTmp();
         assert(RegUses[RegNum] >= 0);
@@ skipping 45 matching lines @@
                   IsSingleDef && IsAssign && !overlapsDefs(Func, Cur, SrcVar);
             }
             if (AllowOverlap || Free[SrcReg]) {
               Prefer = SrcVar;
               PreferReg = SrcReg;
             }
           }
         }
       }
     }
-    if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+    if (Verbose) {
       if (Prefer) {
         Str << "Initial Prefer=" << *Prefer << " R=" << PreferReg
             << " LIVE=" << Prefer->getLiveRange() << " Overlap=" << AllowOverlap
             << "\n";
       }
     }
 
     // Remove registers from the Free[] list where an Inactive range
     // overlaps with the current range.
     for (UnorderedRanges::const_iterator I = Inactive.begin(),
                                          E = Inactive.end();
          I != E; ++I) {
       LiveRangeWrapper Item = *I;
-      if (Item.overlaps(Cur)) {
-        int32_t RegNum = Item.Var->getRegNumTmp();
+      int32_t RegNum = Item.Var->getRegNumTmp();
+      if (Free[RegNum] && Item.overlaps(Cur)) {
         // Don't assert(Free[RegNum]) because in theory (though

[jvoung (off chromium), 2014/09/30 20:19:04]

Based on the comment, it seems like there could still be a reason to see if
AllowOverlap should be set to false. Or maybe that was just an artifact of the
manual marking.

[Jim Stichnoth, 2014/09/30 22:46:00]

I think you're right and I may have incorrectly optimized that.  Reverting for
now.

         // probably never in practice) there could be two inactive
         // variables that were allowed marked with
         // AllowRegisterOverlap.

[jvoung (off chromium), 2014/09/30 20:19:04]

AllowRegisterOverlap -> AllowOverlap

[Jim Stichnoth, 2014/09/30 22:45:59]

Done.

         Free[RegNum] = false;
         // Disable AllowOverlap if an Inactive variable, which is not
         // Prefer, shares Prefer's register, and has a definition
         // within Cur's live range.
         if (AllowOverlap && Item.Var != Prefer && RegNum == PreferReg &&
             overlapsDefs(Func, Cur, Item.Var)) {
           AllowOverlap = false;
           dumpDisableOverlap(Func, Item.Var, "Inactive");
         }
       }
@@ skipping 30 matching lines @@
         // Disable AllowOverlap if the preferred register is one of
         // these precolored unhandled overlapping ranges.
         if (AllowOverlap && ItemReg == PreferReg) {
           AllowOverlap = false;
           dumpDisableOverlap(Func, Item.Var, "PrecoloredUnhandled");
         }
       }
     }
 
     // Print info about physical register availability.
-    if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+    if (Verbose) {
       for (SizeT i = 0; i < RegMask.size(); ++i) {
         if (RegMask[i]) {
           Str << Func->getTarget()->getRegName(i, IceType_i32)
               << "(U=" << RegUses[i] << ",F=" << Free[i]
               << ",P=" << PrecoloredUnhandled[i] << ") ";
         }
       }
       Str << "\n";
     }
 
     if (Prefer && (AllowOverlap || Free[PreferReg])) {
       // First choice: a preferred register that is either free or is
       // allowed to overlap with its linked variable.
       Cur.Var->setRegNumTmp(PreferReg);
-      if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+      if (Verbose) {
         Str << "Preferring   ";
         Cur.dump(Func);
         Str << "\n";
       }
       assert(RegUses[PreferReg] >= 0);
       ++RegUses[PreferReg];
       Active.push_back(Cur);
     } else if (Free.any()) {
       // Second choice: any free register.  TODO: After explicit
       // affinity is considered, is there a strategy better than just
       // picking the lowest-numbered available register?
       int32_t RegNum = Free.find_first();
       Cur.Var->setRegNumTmp(RegNum);
-      if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+      if (Verbose) {
         Str << "Allocating   ";
         Cur.dump(Func);
         Str << "\n";
       }
       assert(RegUses[RegNum] >= 0);
       ++RegUses[RegNum];
       Active.push_back(Cur);
     } else {
       // Fallback: there are no free registers, so we look for the
       // lowest-weight register and see if Cur has higher weight.
@@ skipping 53 matching lines @@
         }
       } else {
         // Evict all live ranges in Active that register number
         // MinWeightIndex is assigned to.
         for (UnorderedRanges::iterator I = Active.begin(), E = Active.end();
              I != E; I = Next) {
           Next = I;
           ++Next;
           LiveRangeWrapper Item = *I;
           if (Item.Var->getRegNumTmp() == MinWeightIndex) {
-            if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+            if (Verbose) {
               Str << "Evicting     ";
               Item.dump(Func);
               Str << "\n";
             }
             --RegUses[MinWeightIndex];
             assert(RegUses[MinWeightIndex] >= 0);
             Item.Var->setRegNumTmp(Variable::NoRegister);
             Active.erase(I);
             Handled.push_back(Item);
           }
         }
         // Do the same for Inactive.
         for (UnorderedRanges::iterator I = Inactive.begin(), E = Inactive.end();
              I != E; I = Next) {
           Next = I;
           ++Next;
           LiveRangeWrapper Item = *I;
           // Note: The Item.overlaps(Cur) clause is not part of the
           // description of AssignMemLoc() in the original paper.  But
           // there doesn't seem to be any need to evict an inactive
           // live range that doesn't overlap with the live range
           // currently being considered.  It's especially bad if we
           // would end up evicting an infinite-weight but
           // currently-inactive live range.  The most common situation
           // for this would be a scratch register kill set for call
           // instructions.
           if (Item.Var->getRegNumTmp() == MinWeightIndex &&
               Item.overlaps(Cur)) {
-            if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+            if (Verbose) {
               Str << "Evicting     ";
               Item.dump(Func);
               Str << "\n";
             }
             Item.Var->setRegNumTmp(Variable::NoRegister);
             Inactive.erase(I);
             Handled.push_back(Item);
           }
         }
         // Assign the register to Cur.
         Cur.Var->setRegNumTmp(MinWeightIndex);
         assert(RegUses[MinWeightIndex] >= 0);
         ++RegUses[MinWeightIndex];
         Active.push_back(Cur);
-        if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+        if (Verbose) {
           Str << "Allocating   ";
           Cur.dump(Func);
           Str << "\n";
         }
       }
     }
     dump(Func);
   }
   // Move anything Active or Inactive to Handled for easier handling.
   for (UnorderedRanges::iterator I = Active.begin(), E = Active.end(); I != E;
@@ skipping 10 matching lines @@
     Handled.push_back(*I);
     Inactive.erase(I);
   }
   dump(Func);
 
   // Finish up by assigning RegNumTmp->RegNum for each Variable.
   for (UnorderedRanges::const_iterator I = Handled.begin(), E = Handled.end();
        I != E; ++I) {
     LiveRangeWrapper Item = *I;
     int32_t RegNum = Item.Var->getRegNumTmp();
-    if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+    if (Verbose) {
       if (!Item.Var->hasRegTmp()) {
         Str << "Not assigning ";
         Item.Var->dump(Func);
         Str << "\n";
       } else {
         Str << (RegNum == Item.Var->getRegNum() ? "Reassigning " : "Assigning ")
             << Func->getTarget()->getRegName(RegNum, IceType_i32) << "(r"
             << RegNum << ") to ";
         Item.Var->dump(Func);
         Str << "\n";
@@ skipping 52 matching lines @@
   }
   Str << "++++++ Inactive:\n";
   for (UnorderedRanges::const_iterator I = Inactive.begin(), E = Inactive.end();
        I != E; ++I) {
     I->dump(Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice