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

src/IceOperand.cpp

 //===- subzero/src/IceOperand.cpp - High-level operand implementation -----===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 129 matching lines @@
   Variable *V = new (getCurrentCfgAllocator()->Allocate<Variable>())
       Variable(kVariable, Ty, Number);
   V->NameIndex = NameIndex;
   V->RegNum = RegNum;
   V->StackOffset = StackOffset;
   return V;
 }
 
 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;
   // TODO(stichnot): If the use occurs as a source operand in the
   // first instruction of the block, and its definition is in this
   // block's only predecessor, we might consider not marking this as a
   // separate use.  This may also apply if it's the first instruction
   // of the block that actually uses a Variable.
   assert(Node);
   bool MakeMulti = false;
@@ skipping 216 matching lines @@
   return Metadata[VarNum].getLatterDefinitions();
 }
 
 CfgNode *VariablesMetadata::getLocalUseNode(const Variable *Var) const {
   if (!isTracked(Var))
     return nullptr; // conservative answer
   SizeT VarNum = Var->getIndex();
   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();
 }
 
 const InstDefList VariablesMetadata::NoDefinitions;
 
 // ======================== dump routines ======================== //
 
 void Variable::emit(const Cfg *Func) const {
   if (BuildDefs::dump())
@@ skipping 112 matching lines @@
   if (getType() != IceType_i32 && getType() != IceType_i16 &&
       getType() != IceType_i8)
     return false;
   // The Following checks if the signed representation of Value is between
   // -Threshold/2 and +Threshold/2
   bool largerThanThreshold = Threshold / 2 + Value >= Threshold;
   return largerThanThreshold;
 }
 
 } // end of namespace Ice