Subzero: Implement "second-chance bin-packing" for register allocation.

src/IceTargetLowering.cpp

 //===- subzero/src/IceTargetLowering.cpp - Basic lowering implementation --===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 249 matching lines @@
 // performance testing.
 void TargetLowering::regAlloc(RegAllocKind Kind) {
   TimerMarker T(TimerStack::TT_regAlloc, Func);
   LinearScan LinearScan(Func);
   RegSetMask RegInclude = RegSet_None;
   RegSetMask RegExclude = RegSet_None;
   RegInclude |= RegSet_CallerSave;
   RegInclude |= RegSet_CalleeSave;
   if (hasFramePointer())
     RegExclude |= RegSet_FramePointer;
-  LinearScan.init(Kind);
   llvm::SmallBitVector RegMask = getRegisterSet(RegInclude, RegExclude);
-  LinearScan.scan(RegMask, Ctx->getFlags().shouldRandomizeRegAlloc());
+  bool Repeat = (Kind == RAK_Global && Ctx->getFlags().shouldRepeatRegAlloc());
+  do {
+    LinearScan.init(Kind);
+    LinearScan.scan(RegMask, Ctx->getFlags().shouldRandomizeRegAlloc());
+    if (!LinearScan.hasEvictions())
+      Repeat = false;
+    Kind = RAK_SecondChance;
+  } while (Repeat);
 }
 
 void TargetLowering::markRedefinitions() {
   // Find (non-SSA) instructions where the Dest variable appears in some source
   // operand, and set the IsDestRedefined flag to keep liveness analysis
   // consistent.
   for (auto Inst = Context.getCur(), E = Context.getNext(); Inst != E; ++Inst) {
     if (Inst->isDeleted())
       continue;
     Variable *Dest = Inst->getDest();
@@ skipping 337 matching lines @@
   if (Target == Target_##X)                                                    \
     return TargetHeader##X::create(Ctx);
 #include "llvm/Config/SZTargets.def"
 
   llvm::report_fatal_error("Unsupported target header lowering");
 }
 
 TargetHeaderLowering::~TargetHeaderLowering() = default;
 
 } // end of namespace Ice