Subzero: Initial O2 lowering

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 "IceInst.h"
+#include "IceOperand.h"
+#include "IceRegAlloc.h"
+#include "IceTargetLowering.h"
+
+namespace Ice {
+
+// 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_RangesFull) in
+// preparation.  Results are assigned to Variable::RegNum for each
+// Variable.
+void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull) {
+  assert(RegMaskFull.any()); // Sanity check
+  Unhandled.clear();
+  Handled.clear();
+  Inactive.clear();
+  Active.clear();
+  Ostream &Str = Func->getContext()->getStrDump();
+  Func->setCurrentNode(NULL);
+
+  // 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();
+    }
+  }
+
+  // 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.
+  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)) {
+      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)) {
+        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)) {
+          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)) {
+          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)) {
+          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)) {
+          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);
+        ++RegUses[RegNum];
+      }
+    }
+
+    // Calculate available registers into Free[].
+    llvm::SmallBitVector Free = RegMask;
+    for (SizeT i = 0; i < RegMask.size(); ++i) {
+      if (RegUses[i] > 0)
+        Free[i] = false;
+    }
+
+    // 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();
+        // Don't assert(Free[RegNum]) because in theory (though
+        // probably never in practice) there could be two inactive
+        // variables that were allowed marked with
+        // AllowRegisterOverlap.
+        Free[RegNum] = false;
+      }
+    }
+
+    // Remove registers from the Free[] list where an Unhandled range
+    // overlaps with the current range and is precolored.
+    // Cur.endsBefore(*I) is an early exit check that turns a
+    // guaranteed O(N^2) algorithm into expected linear complexity.
+    for (OrderedRanges::const_iterator I = Unhandled.begin(),
+                                       E = Unhandled.end();
+         I != E && !Cur.endsBefore(*I); ++I) {
+      LiveRangeWrapper Item = *I;
+      if (Item.Var->hasReg() && Item.overlaps(Cur)) {

[jvoung (off chromium), 2014/06/02 17:07:43]

because unhandled is sorted and !Cur.endsBefore(Item), is Item guaranteed to
overlap(Cur) already?

[Jim Stichnoth, 2014/06/04 14:18:03]

Not necessarily.  Example:

  int Cur = ...;
  if (cond) {
    int Item = ...;
    // use Item
    // no uses of Cur in this block
  } else {
    // use Cur
  }
  // no more uses of Cur

Assuming the instruction numbering matches C statement ordering, the live range
of Cur has a gap corresponding to the true branch of the if statement, and the
live range of Item is contained within the true branch.  Therefore they don't
overlap and so it doesn't matter to Cur whether Item is precolored, yet Item
comes after Cur in the sorted Unhandled list.

[jvoung (off chromium), 2014/06/04 18:17:57]

Ah okay, makes sense.

+        Free[Item.Var->getRegNum()] = false; // Note: getRegNum not getRegNumTmp
+      }
+    }
+
+    // Print info about physical register availability.
+    if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+      for (SizeT i = 0; i < RegMask.size(); ++i) {
+        if (RegMask[i]) {
+          Str << Func->getTarget()->getRegName(i, IceType_i32)
+              << "(U=" << RegUses[i] << ",F=" << Free[i] << ") ";
+        }
+      }
+      Str << "\n";
+    }
+
+    Variable *Prefer = Cur.Var->getPreferredRegister();
+    int32_t PreferReg = Prefer && Prefer->hasRegTmp() ? Prefer->getRegNumTmp()
+                                                      : Variable::NoRegister;
+    if (PreferReg != Variable::NoRegister &&
+        (Cur.Var->getRegisterOverlap() || 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)) {
+        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)) {
+        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.
+      std::vector<RegWeight> Weights(RegMask.size());
+      // Check Active ranges.
+      for (UnorderedRanges::const_iterator I = Active.begin(), E = Active.end();
+           I != E; ++I) {
+        LiveRangeWrapper Item = *I;
+        assert(Item.overlaps(Cur));
+        int32_t RegNum = Item.Var->getRegNumTmp();
+        assert(Item.Var->hasRegTmp());
+        Weights[RegNum].addWeight(Item.range().getWeight());
+      }
+      // Same as above, but check Inactive ranges instead of Active.
+      for (UnorderedRanges::const_iterator I = Inactive.begin(),
+                                           E = Inactive.end();
+           I != E; ++I) {
+        LiveRangeWrapper Item = *I;

[jvoung (off chromium), 2014/06/02 17:07:43]

Do you have to check for overlap first? For Active you can assume it overlaps,
but for Inactive it's not so certain?

[Jim Stichnoth, 2014/06/04 14:18:03]

I think you're right and the lack of overlap check was a transcription or
copy/paste error.

+        int32_t RegNum = Item.Var->getRegNumTmp();
+        assert(Item.Var->hasRegTmp());
+        Weights[RegNum].addWeight(Item.range().getWeight());
+      }
+      // Check Unhandled ranges that overlap Cur and are precolored.
+      // Cur.endsBefore(*I) is an early exit check that turns a
+      // guaranteed O(N^2) algorithm into expected linear complexity.
+      for (OrderedRanges::const_iterator I = Unhandled.begin(),
+                                         E = Unhandled.end();
+           I != E && !Cur.endsBefore(*I); ++I) {
+        LiveRangeWrapper Item = *I;
+        int32_t RegNum = Item.Var->getRegNumTmp();
+        if (RegNum < 0)
+          continue;
+        if (Item.overlaps(Cur))
+          Weights[RegNum].setWeight(RegWeight::Inf);
+      }
+
+      // All the weights are now calculated.  Find the register with
+      // smallest weight.
+      int32_t MinWeightIndex = RegMask.find_first();
+      // MinWeightIndex must be valid because of the initial
+      // RegMask.any() test.
+      assert(MinWeightIndex >= 0);
+      for (SizeT i = MinWeightIndex + 1; i < Weights.size(); ++i) {
+        if (RegMask[i] && Weights[i] < Weights[MinWeightIndex])
+          MinWeightIndex = i;
+      }
+
+      if (Cur.range().getWeight() <= Weights[MinWeightIndex]) {
+        // Cur doesn't have priority over any other live ranges, so
+        // don't allocate any register to it, and move it to the
+        // Handled state.
+        Handled.push_back(Cur);
+        if (Cur.range().getWeight().isInf()) {
+          Func->setError("Unable to find a physical register for an "
+                         "infinite-weight live range");
+        }
+      } 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)) {
+              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;
+          if (Item.Var->getRegNumTmp() == MinWeightIndex) {
+            if (Func->getContext()->isVerbose(IceV_LinearScan)) {
+              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)) {
+          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;
+       I = Next) {
+    Next = I;
+    ++Next;
+    Handled.push_back(*I);
+    Active.erase(I);
+  }
+  for (UnorderedRanges::iterator I = Inactive.begin(), E = Inactive.end();
+       I != E; I = Next) {
+    Next = I;
+    ++Next;
+    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 (!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";
+      }
+    }
+    Item.Var->setRegNum(Item.Var->getRegNumTmp());
+  }
+
+  // TODO: Consider running register allocation one more time, with
+  // infinite registers, for two reasons.  First, evicted live ranges
+  // get a second chance for a register.  Second, it allows coalescing
+  // of stack slots.  If there is no time budget for the second
+  // register allocation run, each unallocated variable just gets its
+  // own slot.
+  //
+  // Another idea for coalescing stack slots is to initialize the
+  // Unhandled list with just the unallocated variables, saving time
+  // but not offering second-chance opportunities.
+}
+
+// ======================== Dump routines ======================== //
+
+void LiveRangeWrapper::dump(const Cfg *Func) const {
+  Ostream &Str = Func->getContext()->getStrDump();
+  const static size_t BufLen = 30;
+  char buf[BufLen];
+  snprintf(buf, BufLen, "%2d", Var->getRegNumTmp());
+  Str << "R=" << buf << "  V=";
+  Var->dump(Func);
+  Str << "  Range=" << range();
+}
+
+void LinearScan::dump(Cfg *Func) const {
+  Ostream &Str = Func->getContext()->getStrDump();
+  if (!Func->getContext()->isVerbose(IceV_LinearScan))
+    return;
+  Func->setCurrentNode(NULL);
+  Str << "**** Current regalloc state:\n";
+  Str << "++++++ Handled:\n";
+  for (UnorderedRanges::const_iterator I = Handled.begin(), E = Handled.end();
+       I != E; ++I) {
+    I->dump(Func);
+    Str << "\n";
+  }
+  Str << "++++++ Unhandled:\n";
+  for (OrderedRanges::const_iterator I = Unhandled.begin(), E = Unhandled.end();
+       I != E; ++I) {
+    I->dump(Func);
+    Str << "\n";
+  }
+  Str << "++++++ Active:\n";
+  for (UnorderedRanges::const_iterator I = Active.begin(), E = Active.end();
+       I != E; ++I) {
+    I->dump(Func);
+    Str << "\n";
+  }
+  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