Weight variables by their number of uses for register allocation.

src/IceInst.cpp

Index: src/IceInst.cpp
diff --git a/src/IceInst.cpp b/src/IceInst.cpp
index 4b89eb77b0fa88f5f692f637a5ef892305b1a62b..11fae679138bd06389bdcae5e42958ee2cb9aebe 100644
--- a/src/IceInst.cpp
+++ b/src/IceInst.cpp
@@ -203,7 +203,9 @@ bool Inst::liveness(InstNumberT InstNumber, LivenessBV &Live,
     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);