Subzero: Fix a performance regression in the register allocator.

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.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 80 matching lines @@
   // (meaning we look for opportunities for two overlapping live ranges to
   // safely share the same register). However, we disable it for phi-lowering
   // register allocation since no overlap opportunities should be available and
   // it's more expensive to look for opportunities.
   FindOverlap = (Kind != RAK_Phi);
   const VarList &Vars = Func->getVariables();
   Unhandled.reserve(Vars.size());
   UnhandledPrecolored.reserve(Vars.size());
   // Gather the live ranges of all variables and add them to the Unhandled set.
   for (Variable *Var : Vars) {
+    // Don't consider rematerializable variables.
+    if (Var->isRematerializable())
+      continue;
     // Explicitly don't consider zero-weight variables, which are meant to be
     // spill slots.
     if (Var->mustNotHaveReg())
       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);
@@ skipping 83 matching lines @@
   // Iterate across all instructions and record the begin and end of the live
   // range for each variable that is pre-colored or infinite weight.
   CfgVector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel);
   CfgVector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel);
   DefUseErrorList DefsWithoutUses, UsesBeforeDefs;
   for (CfgNode *Node : Func->getNodes()) {
     for (Inst &Inst : Node->getInsts()) {
       if (Inst.isDeleted())
         continue;
       FOREACH_VAR_IN_INST(Var, Inst) {
+        if (Var->isRematerializable())
+          continue;
         if (Var->getIgnoreLiveness())
           continue;
         if (Var->hasReg() || Var->mustHaveReg()) {
           SizeT VarNum = Var->getIndex();
           LREnd[VarNum] = Inst.getNumber();
           if (!Var->getIsArg() && LRBegin[VarNum] == Inst::NumberSentinel)
             UsesBeforeDefs.push_back(VarNum);
         }
       }
       if (const Variable *Var = Inst.getDest()) {
-        if (!Var->getIgnoreLiveness() &&
+        if (!Var->isRematerializable() && !Var->getIgnoreLiveness() &&
             (Var->hasReg() || Var->mustHaveReg())) {
           if (LRBegin[Var->getIndex()] == Inst::NumberSentinel) {
             LRBegin[Var->getIndex()] = Inst.getNumber();
             ++NumVars;
           }
         }
       }
     }
   }
 
   Unhandled.reserve(NumVars);
   UnhandledPrecolored.reserve(NumVars);
   for (SizeT i = 0; i < Vars.size(); ++i) {
     Variable *Var = Vars[i];
+    if (Var->isRematerializable())
+      continue;
     if (LRBegin[i] != Inst::NumberSentinel) {
       if (LREnd[i] == Inst::NumberSentinel) {
         DefsWithoutUses.push_back(i);
         continue;
       }
       Unhandled.push_back(Var);
       Var->resetLiveRange();
       Var->addLiveRange(LRBegin[i], LREnd[i]);
       Var->untrimLiveRange();
       if (Var->hasReg()) {
@@ skipping 38 matching lines @@
 }
 
 void LinearScan::initForSecondChance() {
   TimerMarker T(TimerStack::TT_initUnhandled, Func);
   FindPreference = true;
   FindOverlap = true;
   const VarList &Vars = Func->getVariables();
   Unhandled.reserve(Vars.size());
   UnhandledPrecolored.reserve(Vars.size());
   for (Variable *Var : Vars) {
+    if (Var->isRematerializable())
+      continue;
     if (Var->hasReg()) {
       Var->untrimLiveRange();
       Var->setRegNumTmp(Var->getRegNum());
       Var->setMustHaveReg();
       UnhandledPrecolored.push_back(Var);
       Unhandled.push_back(Var);
     }
   }
   for (Variable *Var : Evicted) {
     Var->untrimLiveRange();
@@ skipping 263 matching lines @@
     }
   }
 }
 
 // Remove registers from the Free[] list where an Unhandled pre-colored range
 // overlaps with the current range, and set those registers to infinite weight
 // so that they aren't candidates for eviction. Cur->rangeEndsBefore(Item) is an
 // early exit check that turns a guaranteed O(N^2) algorithm into expected
 // linear complexity.
 void LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) {
+  // TODO(stichnot): Partition UnhandledPrecolored according to register class,
+  // to restrict the number of overlap comparisons needed.
   for (Variable *Item : reverse_range(UnhandledPrecolored)) {
     assert(Item->hasReg());
     if (Iter.Cur->rangeEndsBefore(Item))
       break;
     if (!Item->rangeOverlaps(Iter.Cur))
       continue;
     const llvm::SmallBitVector &Aliases =
         *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp()
     for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
          RegAlias = Aliases.find_next(RegAlias)) {
@@ skipping 386 matching lines @@
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
   for (const Variable *Item : Inactive) {
     dumpLiveRange(Item, Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice