Weight variables by their number of uses for register allocation.

src/IceInst.cpp

 //===- subzero/src/IceInst.cpp - High-level instruction implementation ----===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 164 matching lines @@
 bool Inst::liveness(InstNumberT InstNumber, LivenessBV &Live,
                     Liveness *Liveness, LiveBeginEndMap *LiveBegin,
                     LiveBeginEndMap *LiveEnd) {
   assert(!isDeleted());
 
   Dead = false;
   if (Dest) {
     SizeT VarNum = Liveness->getLiveIndex(Dest->getIndex());
     if (Live[VarNum]) {
       if (!isDestNonKillable()) {
         Live[VarNum] = false;

[Jim Stichnoth, 2015/08/27 05:03:06]

I kind of expected Dest to be marked as having a use here.

Maybe that doesn't really matter because non-SSA variables with more than one
definition are only infinite-weight variables from lowering?

Maybe that unfairly diminishes weights of function arguments, which lack
explicit definitions?

If you mean to not track the use of Dest here, it's probably good to leave a
comment.

EDIT: I see this issue was already discussed.  I actually vote for counting the
dest var as a use.  Ignoring the fact that two-address instructions generally
involve infinite-weight variables, if we have an instruction like this:
  add [esp], 1
then there are actually two memory operations and it seems that the register
allocator should weight it accordingly.

[jvoung (off chromium), 2015/08/27 18:34:27]

I'm not against counting Dests too, but wanted to understand what would be
affected.

[ascull, 2015/08/28 19:26:36]

Dest counting will return.

         if (LiveBegin && Liveness->getRangeMask(Dest->getIndex())) {
           LiveBegin->push_back(std::make_pair(VarNum, InstNumber));
         }
       }
     } else {
       if (!hasSideEffects())
         Dead = true;
     }
   }
   if (Dead)
     return false;
   // Phi arguments only get added to Live in the predecessor node, but
   // we still need to update LiveRangesEnded.
   bool IsPhi = llvm::isa<InstPhi>(this);
   resetLastUses();
   SizeT VarIndex = 0;
   for (SizeT I = 0; I < getSrcSize(); ++I) {
     Operand *Src = getSrc(I);
     SizeT NumVars = Src->getNumVars();
     for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) {
-      const Variable *Var = Src->getVar(J);
+      Variable *Var = Src->getVar(J);
+      // TODO(ascull): get the loop nest depth
+      Var->addUse(1);

[Jim Stichnoth, 2015/08/27 05:03:06]

So there's kind of a maybe sort of big problem here.

Liveness analysis is a dataflow algorithm that iterates until convergence.  If
the Cfg nodes are topologically sorted and there are no loops (i.e., backward
branches), everything is find and liveness converges after one iteration per
node.  But if there is a loop, convergence is generally proportional to the loop
nest depth.  I think this means that the uses will end up being counted N times
when they are inside a loop nest of depth N.

Maybe that's OK since we anyway want to apply higher weight inside loops, but
it's not necessarily strictly the use count.

So far, the best solution I can think of (other than just living with the
approximate count) is a separate pass instead of combining it with liveness
analysis.  Otherwise you need some way of representing per-block use counts, and
you have to make use of sparsity, and that's tough.

[jvoung (off chromium), 2015/08/27 18:34:27]

Good point =)  So the TODO was almost done ;-)

Seems better to be more explicit about the loop nest and have a separate pass
then? I was about to suggest making it part of the VMetadata init() pass, but
that's run multiple times while this is only needed for regalloc.

Also, be careful about where the Var->resetUses() is done. That currently
happens as part of resetLiveRange(), but that's after Inst::liveness()?

[Jim Stichnoth, 2015/08/27 20:04:21]

Actually, incrementing the use count right at the start of
VariableTracking::markUse() seems like a really good idea.

[ascull, 2015/08/28 19:26:36]

Moved into VMetadata.

       SizeT VarNum = Liveness->getLiveIndex(Var->getIndex());
       if (!Live[VarNum]) {
         setLastUse(VarIndex);
         if (!IsPhi) {
           Live[VarNum] = true;
           // For a variable in SSA form, its live range can end at
           // most once in a basic block.  However, after lowering to
           // two-address instructions, we end up with sequences like
           // "t=b;t+=c;a=t" where t's live range begins and ends
           // twice.  ICE only allows a variable to have a single
@@ skipping 757 matching lines @@
     // preserve these.
     return true;
   }
   if (!Dest->hasReg() && !SrcVar->hasReg() &&
       Dest->getStackOffset() == SrcVar->getStackOffset())
     return true;
   return false;
 }
 
 } // end of namespace Ice