Subzero: Fix a regalloc bug involving too-aggressive AllowRegisterOverlap.

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 187 matching lines @@
         // 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.
+    llvm::SmallBitVector PrecoloredUnhandled(RegMask.size());
     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)) {
         Free[Item.Var->getRegNum()] = false; // Note: getRegNum not getRegNumTmp
+        PrecoloredUnhandled[Item.Var->getRegNum()] = true;
       }
     }
 
     // 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] << ") ";

[jvoung (off chromium), 2014/07/10 21:55:32]

Maybe print the PrecoloredUnhandled[] status too.

[jvoung (off chromium), 2014/07/10 21:56:42]

Hmm, or I guess you can look at the Unhandled list, and spot the pre-colored
registers -- so it's fine to leave out too.

[Jim Stichnoth, 2014/07/10 22:32:10]

Good idea, done.  You're right that you can study the Unhandled list, but then
you also have to be careful to look at only the Unhandled live ranges that
overlap with the current live range.

         }
       }
       Str << "\n";
     }
 
     Variable *Prefer = Cur.Var->getPreferredRegister();
     int32_t PreferReg = Prefer && Prefer->hasRegTmp() ? Prefer->getRegNumTmp()
                                                       : Variable::NoRegister;
+    bool AllowedToOverlap = Cur.Var->getRegisterOverlap() &&
+                            PreferReg != Variable::NoRegister &&
+                            !PrecoloredUnhandled[PreferReg];
     if (PreferReg != Variable::NoRegister &&
-        (Cur.Var->getRegisterOverlap() || Free[PreferReg])) {
+        (AllowedToOverlap || 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];
@@ skipping 209 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