Subzero: Fix the simple register allocation for -Om1.

src/IceTargetLoweringX8632.cpp

Index: src/IceTargetLoweringX8632.cpp
diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp
index 35792aaac0aebc38cafca62a0744a7e8c9fe4572..51bcb65b2f285fa182cfbc726ac75a49b4ed2b87 100644
--- a/src/IceTargetLoweringX8632.cpp
+++ b/src/IceTargetLoweringX8632.cpp
@@ -4153,6 +4153,10 @@ void TargetX8632::postLower() {
   // there was some prior register allocation pass that made register
   // assignments, those registers need to be black-listed here as
   // well.
+  std::map<const Variable *, const Inst *> LastUses;

[wala, 2014/08/18 04:44:54]

How about a DenseMap?

"DenseMap is a great way to map pointers to pointers, or map other small types
to each other."

http://llvm.org/docs/ProgrammersManual.html#llvm-adt-densemap-h

[Jim Stichnoth, 2014/08/18 17:31:02]

Nice, done.

+  // 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;
@@ -4165,6 +4169,9 @@ void TargetX8632::postLower() {
       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;
@@ -4173,36 +4180,52 @@ void TargetX8632::postLower() {
   }
   // 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);
+    // 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);

[wala, 2014/08/18 04:44:54]

Now that Dest is included in this iteration, should there ever be a situation
where you encounter an unassigned infinite weight source operand? That would
seem to imply that the source was used before being defined.

[wala, 2014/08/18 04:46:31]

I meant "Dest is included in this OperandList"

[Jim Stichnoth, 2014/08/18 17:31:02]

This should generally be the case for local variables (including arguments)
defined at the bitcode level.  Infinite-weight and pre-colored are usually just
for the temporaries that are part of the lowering expansion.

+    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;
+        }
+        if (Var->hasReg() && LastUses[Var] == Inst) {

[wala, 2014/08/18 04:44:54]

Would it make sense to assert that if Var->hasReg(), then Var->getRegNum() is
not in AvailableRegisters? This would help validate the assumption you mention
in the comment on line 4198.

[Jim Stichnoth, 2014/08/18 17:31:02]

Done.

BTW, this required initializing RegExclude to RegSet_StackPointer instead of
RegSet_None, otherwise the stacksave/stackrestore intrinsics would cause an
assertion failure in this new assert.

+          int32_t RegNum = Var->getRegNum();
+          if (WhiteList[RegNum])
+            FreedRegisters[RegNum] = true;
         }
-        assert(AvailableTypedRegisters.any());
-        int32_t RegNum = AvailableTypedRegisters.find_first();
-        Var->setRegNum(RegNum);
-        AvailableRegisters[RegNum] = false;
       }
     }
+    AvailableRegisters |= FreedRegisters;
   }
 }