Subzero: Fix the simple register allocation for -Om1.

src/IceTargetLoweringX8632.cpp

 //===- subzero/src/IceTargetLoweringX8632.cpp - x86-32 lowering -----------===//
 //
 //                        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 TargetLoweringX8632 class, which
 // consists almost entirely of the lowering sequence for each
 // high-level instruction.  It also implements
 // TargetX8632Fast::postLower() which does the simplest possible
 // register allocation for the "fast" target.
 //
 //===----------------------------------------------------------------------===//
 
 #include "IceDefs.h"
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceInstX8632.h"
 #include "IceOperand.h"
 #include "IceTargetLoweringX8632.def"
 #include "IceTargetLoweringX8632.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/CommandLine.h"
 
 #include <strings.h>
 
 namespace Ice {
 
 namespace {
 
 // The following table summarizes the logic for lowering the fcmp
 // instruction.  There is one table entry for each of the 16 conditions.
@@ skipping 4122 matching lines @@
   else
     Reg->setRegNum(RegNum);
   return Reg;
 }
 
 void TargetX8632::postLower() {
   if (Ctx->getOptLevel() != Opt_m1)
     return;
   // TODO: Avoid recomputing WhiteList every instruction.
   RegSetMask RegInclude = RegSet_All;
-  RegSetMask RegExclude = RegSet_None;
+  RegSetMask RegExclude = RegSet_StackPointer;
   if (hasFramePointer())
     RegExclude |= RegSet_FramePointer;
   llvm::SmallBitVector WhiteList = getRegisterSet(RegInclude, RegExclude);
   // Make one pass to black-list pre-colored registers.  TODO: If
   // there was some prior register allocation pass that made register
   // assignments, those registers need to be black-listed here as
   // well.
+  llvm::DenseMap<const Variable *, const Inst *> LastUses;
+  // The first pass also keeps track of which instruction is the last
+  // use for each infinite-weight variable.  After the last use, the
+  // variable is released to the free list.
   for (InstList::iterator I = Context.getCur(), E = Context.getEnd(); I != E;
        ++I) {
     const Inst *Inst = *I;
     if (Inst->isDeleted())
       continue;
+    // Don't consider a FakeKill instruction, because (currently) it
+    // is only used to kill all scratch registers at a call site, and
+    // we don't want to black-list all scratch registers during the
+    // call lowering.  This could become a problem since it relies on
+    // the lowering sequence not keeping any infinite-weight variables
+    // live across a call.  TODO(stichnot): Consider replacing this
+    // whole postLower() implementation with a robust local register
+    // allocator, for example compute live ranges only for pre-colored
+    // and infinite-weight variables and run the existing linear-scan
+    // allocator.
     if (llvm::isa<InstFakeKill>(Inst))
       continue;
     for (SizeT SrcNum = 0; SrcNum < Inst->getSrcSize(); ++SrcNum) {
       Operand *Src = Inst->getSrc(SrcNum);
       SizeT NumVars = Src->getNumVars();
       for (SizeT J = 0; J < NumVars; ++J) {
         const Variable *Var = Src->getVar(J);
+        // Track last uses of all variables, regardless of whether
+        // they are pre-colored or infinite-weight.
+        LastUses[Var] = Inst;
         if (!Var->hasReg())
           continue;
         WhiteList[Var->getRegNum()] = false;
       }
     }
   }
   // The second pass colors infinite-weight variables.
   llvm::SmallBitVector AvailableRegisters = WhiteList;
+  llvm::SmallBitVector FreedRegisters(WhiteList.size());
   for (InstList::iterator I = Context.getCur(), E = Context.getEnd(); I != E;
        ++I) {
+    FreedRegisters.reset();
     const Inst *Inst = *I;
     if (Inst->isDeleted())
       continue;
-    for (SizeT SrcNum = 0; SrcNum < Inst->getSrcSize(); ++SrcNum) {
-      Operand *Src = Inst->getSrc(SrcNum);
+    // Skip FakeKill instructions like above.
+    if (llvm::isa<InstFakeKill>(Inst))
+      continue;
+    // Iterate over all variables referenced in the instruction,
+    // including the Dest variable (if any).  If the variable is
+    // marked as infinite-weight, find it a register.  If this
+    // instruction is the last use of the variable in the lowered
+    // sequence, release the register to the free list after this
+    // instruction is completely processed.  Note that the first pass
+    // ignores the Dest operand, under the assumption that a
+    // pre-colored Dest will appear as a source operand in some
+    // subsequent instruction in the lowered sequence.
+    Variable *Dest = Inst->getDest();
+    SizeT NumSrcs = Inst->getSrcSize();
+    if (Dest)
+      ++NumSrcs;
+    OperandList Srcs(NumSrcs);
+    for (SizeT i = 0; i < Inst->getSrcSize(); ++i)
+      Srcs[i] = Inst->getSrc(i);
+    if (Dest)
+      Srcs[NumSrcs - 1] = Dest;
+    for (SizeT SrcNum = 0; SrcNum < NumSrcs; ++SrcNum) {
+      Operand *Src = Srcs[SrcNum];
       SizeT NumVars = Src->getNumVars();
       for (SizeT J = 0; J < NumVars; ++J) {
         Variable *Var = Src->getVar(J);
-        if (Var->hasReg())
-          continue;
-        if (!Var->getWeight().isInf())
-          continue;
-        llvm::SmallBitVector AvailableTypedRegisters =
-            AvailableRegisters & getRegisterSetForType(Var->getType());
-        if (!AvailableTypedRegisters.any()) {
-          // This is a hack in case we run out of physical registers due
-          // to an excessively long code sequence, as might happen when
-          // lowering arguments in lowerCall().
-          AvailableRegisters = WhiteList;
-          AvailableTypedRegisters =
+        if (!Var->hasReg() && Var->getWeight().isInf()) {
+          llvm::SmallBitVector AvailableTypedRegisters =
               AvailableRegisters & getRegisterSetForType(Var->getType());
+          assert(AvailableTypedRegisters.any());
+          int32_t RegNum = AvailableTypedRegisters.find_first();
+          Var->setRegNum(RegNum);
+          AvailableRegisters[RegNum] = false;
         }
-        assert(AvailableTypedRegisters.any());
-        int32_t RegNum = AvailableTypedRegisters.find_first();
-        Var->setRegNum(RegNum);
-        AvailableRegisters[RegNum] = false;
+        if (Var->hasReg()) {
+          int32_t RegNum = Var->getRegNum();
+          assert(!AvailableRegisters[RegNum]);
+          if (LastUses[Var] == Inst) {
+            if (WhiteList[RegNum])
+              FreedRegisters[RegNum] = true;
+          }
+        }
       }
     }
+    AvailableRegisters |= FreedRegisters;
   }
 }
 
 template <> void ConstantInteger::emit(GlobalContext *Ctx) const {
   Ostream &Str = Ctx->getStrEmit();
   Str << (int64_t) getValue();
 }
 
 template <> void ConstantFloat::emit(GlobalContext *Ctx) const {
   Ostream &Str = Ctx->getStrEmit();
@@ skipping 101 matching lines @@
     Str << "\t.align\t" << Align << "\n";
     Str << MangledName << ":\n";
     for (SizeT i = 0; i < Size; ++i) {
       Str << "\t.byte\t" << (((unsigned)Data[i]) & 0xff) << "\n";
     }
     Str << "\t.size\t" << MangledName << ", " << Size << "\n";
   }
 }
 
 } // end of namespace Ice