Compute the loop nest depth of each CfgNode and weight Variables by it.

src/IceOperand.cpp

Index: src/IceOperand.cpp
diff --git a/src/IceOperand.cpp b/src/IceOperand.cpp
index 32316ba6ffda6d4f1e8bcab3e1a1ddd589960695..6cdcaf1fde0da75e0a40ea8075e4ea2db0a0a7eb 100644
--- a/src/IceOperand.cpp
+++ b/src/IceOperand.cpp
@@ -147,18 +147,25 @@ Variable *Variable::asType(Type Ty) {
 
 RegWeight Variable::getWeight(const Cfg *Func) const {
   VariablesMetadata *VMetadata = Func->getVMetadata();
-  return RegWeight(mustHaveReg()
-                       ? RegWeight::Inf
-                       : mustNotHaveReg() ? RegWeight::Zero
-                                          : VMetadata->getUseWeight(this));
+  return mustHaveReg() ? RegWeight(RegWeight::Inf)
+                       : mustNotHaveReg() ? RegWeight(RegWeight::Zero)
+                                          : VMetadata->getUseWeight(this);
 }
 
 void VariableTracking::markUse(MetadataKind TrackingKind, const Inst *Instr,
                                CfgNode *Node, bool IsImplicit) {
   (void)TrackingKind;
 
-  // TODO(ascull): get the loop nest depth from CfgNode
-  UseWeight += 1;
+  // Increment the use weight depending on the loop nest depth. The weight is
+  // exponential in the nest depth as inner loops are expected to be executed
+  // an exponentially greater number of times.
+  constexpr uint32_t LogLoopTripCountEstimate = 2; // 2^2 = 4
+  constexpr SizeT MaxShift = sizeof(uint32_t) * CHAR_BIT - 1;
+  constexpr SizeT MaxLoopNestDepth = MaxShift / LogLoopTripCountEstimate;
+  uint32_t ThisUseWeight =
+      1
+      << std::min(Node->getLoopNestDepth(), MaxLoopNestDepth) * LogLoopTripCountEstimate;

[ascull, 2015/09/03 19:52:38]

Why does clang-format fail here? Should I just use a shorter name?

[Jim Stichnoth, 2015/09/03 21:35:09]

Maybe do the std::min() in a separate statement?

Maybe file a clang-format bug? :)

[ascull, 2015/09/03 22:47:13]

Done.

+  UseWeight.addWeight(ThisUseWeight);
 
   if (MultiBlock == MBS_MultiBlock)
     return;
@@ -395,9 +402,9 @@ CfgNode *VariablesMetadata::getLocalUseNode(const Variable *Var) const {
   return Metadata[VarNum].getNode();
 }
 
-uint32_t VariablesMetadata::getUseWeight(const Variable *Var) const {
+RegWeight VariablesMetadata::getUseWeight(const Variable *Var) const {
   if (!isTracked(Var))
-    return 1; // conservative answer
+    return RegWeight(1); // conservative answer
   SizeT VarNum = Var->getIndex();
   return Metadata[VarNum].getUseWeight();
 }