Subzero: Simplify the FakeKill instruction.

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
 // linear-scan register allocation after liveness analysis has been
 // performed.
 //
 //===----------------------------------------------------------------------===//
 
 #include "IceCfg.h"
+#include "IceCfgNode.h"
 #include "IceInst.h"
 #include "IceOperand.h"
 #include "IceRegAlloc.h"
 #include "IceTargetLowering.h"
 
 namespace Ice {
 
 namespace {
 
 // Returns true if Var has any definitions within Item's live range.
@@ skipping 38 matching lines @@
   const static size_t BufLen = 30;
   char buf[BufLen];
   snprintf(buf, BufLen, "%2d", Var->getRegNumTmp());
   Str << "R=" << buf << "  V=";
   Var->dump(Func);
   Str << "  Range=" << Var->getLiveRange();
 }
 
 } // end of anonymous namespace
 
+void LinearScan::initForGlobalAlloc() {
+  TimerMarker T(TimerStack::TT_initUnhandled, Func);
+  Unhandled.clear();
+  UnhandledPrecolored.clear();
+  Handled.clear();
+  Inactive.clear();
+  Active.clear();
+  // Gather the live ranges of all variables and add them to the
+  // Unhandled set.
+  const VarList &Vars = Func->getVariables();
+  Unhandled.reserve(Vars.size());
+  for (Variable *Var : Vars) {
+    // 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;
+    Var->untrimLiveRange();
+    Unhandled.push_back(Var);
+    if (Var->hasReg()) {
+      Var->setRegNumTmp(Var->getRegNum());
+      Var->setLiveRangeInfiniteWeight();
+      UnhandledPrecolored.push_back(Var);
+    }
+  }
+  struct CompareRanges {
+    bool operator()(const Variable *L, const Variable *R) {
+      InstNumberT Lstart = L->getLiveRange().getStart();
+      InstNumberT Rstart = R->getLiveRange().getStart();
+      if (Lstart == Rstart)
+        return L->getIndex() < R->getIndex();
+      return Lstart < Rstart;
+    }
+  };
+  // Do a reverse sort so that erasing elements (from the end) is fast.
+  std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges());
+  std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(),
+            CompareRanges());
+
+  // Build the (ordered) list of FakeKill instruction numbers.
+  Kills.clear();
+  for (CfgNode *Node : Func->getNodes()) {
+    for (auto I = Node->getInsts().begin(), E = Node->getInsts().end(); I != E;
+         ++I) {
+      if (I->isDeleted())
+        continue;
+      if (auto Kill = llvm::dyn_cast<InstFakeKill>(I)) {
+        if (!Kill->getLinked()->isDeleted())
+          Kills.push_back(I->getNumber());
+      }
+    }
+  }
+}
+
 // Implements the linear-scan algorithm.  Based on "Linear Scan
 // Register Allocation in the Context of SSA Form and Register
 // 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) {
   TimerMarker T(TimerStack::TT_linearScan, Func);
   assert(RegMaskFull.any()); // Sanity check
-  Unhandled.clear();
-  UnhandledPrecolored.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.
-  const VarList &Vars = Func->getVariables();
-  {
-    TimerMarker T(TimerStack::TT_initUnhandled, Func);
-    Unhandled.reserve(Vars.size());
-    for (Variable *Var : Vars) {
-      // 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;
-      Var->untrimLiveRange();
-      Unhandled.push_back(Var);
-      if (Var->hasReg()) {
-        Var->setRegNumTmp(Var->getRegNum());
-        Var->setLiveRangeInfiniteWeight();
-        UnhandledPrecolored.push_back(Var);
-      }
-    }
-    struct CompareRanges {
-      bool operator()(const Variable *L, const Variable *R) {
-        InstNumberT Lstart = L->getLiveRange().getStart();
-        InstNumberT Rstart = R->getLiveRange().getStart();
-        if (Lstart == Rstart)
-          return L->getIndex() < R->getIndex();
-        return Lstart < Rstart;
-      }
-    };
-    // Do a reverse sort so that erasing elements (from the end) is fast.
-    std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges());
-    std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(),
-              CompareRanges());
-  }
+  // Build a LiveRange representing the Kills list.
+  LiveRange KillsRange;
+  for (InstNumberT I : Kills)
+    KillsRange.addSegment(I, I);
+  KillsRange.untrim();
 
   // 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 AllowOverlap inference below.
   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()) {
     Variable *Cur = Unhandled.back();
     Unhandled.pop_back();
     if (Verbose) {
       Str << "\nConsidering  ";
       dumpLiveRange(Cur, Func);
       Str << "\n";
     }
     const llvm::SmallBitVector RegMask =
         RegMaskFull & Func->getTarget()->getRegisterSetForType(Cur->getType());
+    KillsRange.trim(Cur->getLiveRange().getStart());
+    llvm::SmallBitVector KillsMask = Func->getTarget()->getRegisterSet(

[jvoung (off chromium), 2014/11/14 16:47:23]

Can the kills mask be lifted out of the while loop? It is also const?

[Jim Stichnoth, 2014/11/14 18:27:03]

Good point, done.

+        TargetLowering::RegSet_CallerSave, TargetLowering::RegSet_None);
 
     // 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->hasReg()) {
       int32_t RegNum = Cur->getRegNum();
       // RegNumTmp should have already been set above.
       assert(Cur->getRegNumTmp() == RegNum);
@@ skipping 45 matching lines @@
         assert(RegUses[RegNum] >= 0);
       }
     }
 
     // Check for inactive ranges that have expired or reactivated.
     for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) {
       Next = I;
       ++Next;
       Variable *Item = *I;
       Item->trimLiveRange(Cur->getLiveRange().getStart());
-      // As an optimization, don't bother checking pure point-valued
-      // Inactive ranges, because the overlapsStart() test will never
-      // succeed, and the rangeEndsBefore() test will generally only
-      // succeed after the last call instruction, which statistically
-      // happens near the end.  TODO(stichnot): Consider suppressing
-      // this check every N iterations in case calls are only at the
-      // beginning of the function.
-      if (!Item->getLiveRange().isNonpoints())
-        continue;
       if (Item->rangeEndsBefore(Cur)) {
         // Move Item from Inactive to Handled list.
         if (Verbose) {
           Str << "Expiring     ";
           dumpLiveRange(Item, Func);
           Str << "\n";
         }
         Handled.splice(Handled.end(), Inactive, I);
       } else if (Item->rangeOverlapsStart(Cur)) {
         // Move Item from Inactive to Active list.
@@ skipping 76 matching lines @@
       if (Item->rangeOverlaps(Cur)) {
         int32_t RegNum = Item->getRegNumTmp();
         // Don't assert(Free[RegNum]) because in theory (though
         // probably never in practice) there could be two inactive
         // variables that were marked with AllowOverlap.
         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 != Prefer && RegNum == PreferReg &&
             overlapsDefs(Func, Cur, Item)) {

[Jim Stichnoth, 2014/11/14 00:51:13]

It turns out this code had a bug, because a pre-colored variable originating
from a FakeKill instruction did not have any defining instructions tabulated in
VMetadata, and therefore overlapsDefs() would always return false, sometimes
incorrectly.  As a result, AllowOverlap could be set to true even though Cur
overlapped with a FakeKill register.

           AllowOverlap = false;
           dumpDisableOverlap(Func, Item, "Inactive");
         }
       }
     }
 
     // Disable AllowOverlap if an Active variable, which is not
     // Prefer, shares Prefer's register, and has a definition within
     // Cur's live range.
     for (const Variable *Item : Active) {
@@ skipping 28 matching lines @@
         PrecoloredUnhandledMask[ItemReg] = true;
         // Disable AllowOverlap if the preferred register is one of
         // these precolored unhandled overlapping ranges.
         if (AllowOverlap && ItemReg == PreferReg) {
           AllowOverlap = false;
           dumpDisableOverlap(Func, Item, "PrecoloredUnhandled");
         }
       }
     }
 
+    // Remove scratch registers from the Free[] list, and mark their
+    // Weights[] as infinite, if KillsRange overlaps Cur's live range.
+    const bool UseTrimmed = true;
+    if (Cur->getLiveRange().overlaps(KillsRange, UseTrimmed)) {
+      Free.reset(KillsMask);
+      for (int i = KillsMask.find_first(); i != -1;
+           i = KillsMask.find_next(i)) {
+        Weights[i].setWeight(RegWeight::Inf);
+        if (PreferReg == i)
+          AllowOverlap = false;
+      }
+    }
+
     // Print info about physical register availability.
     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=" << PrecoloredUnhandledMask[i] << ") ";
         }
       }
       Str << "\n";
@@ skipping 185 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice