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 139 matching lines @@
   return RegWeight(mustHaveReg()
                        ? RegWeight::Inf
                        : mustNotHaveReg() ? 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 LogTypicalLoopTripCount = 3; // 2^3 = 8

[Jim Stichnoth, 2015/09/01 22:17:37]

nit: "Typical" implies knowledge we don't have.  I think
LogLoopTripCountEstimate would be better.

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

Done.

+  uint32_t ThisUseWeight =

[Jim Stichnoth, 2015/09/01 22:17:37]

Maybe SizeT instead of uint32_t?

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

Done.

+      1 << std::min(Node->getLoopNestDepth() * LogTypicalLoopTripCount, 31u);

[Jim Stichnoth, 2015/09/01 22:17:37]

No magic constants please. :)

CHAR_BIT * sizeof(ThisUseWeight) - 1

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

Done.

+  uint32_t NewWeight = UseWeight + ThisUseWeight;
+  // Make sure the weight doesn't overflow or become infinite.
+  UseWeight = NewWeight < UseWeight ? RegWeight::Inf - 1

[Jim Stichnoth, 2015/09/01 22:17:38]

How about something defining something like RegWeight::Max which is denoted as
the maximum non-infinite weight?  RegWeight::addWeight() could also be tightened
up using that.

+                                    : std::min(NewWeight, RegWeight::Inf - 1);
 
   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 218 matching lines @@
 
 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 {
   if (!isTracked(Var))
     return 1; // conservative answer

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

Is 1 the right number here? Why would a variable not be tracked? Does that mean
it isn't used?

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

If the variable is not tracked, it usually means that the variable was created
after the VariablesMetadata was initialized.  VariablesMetadata tries to be
tolerant of that kind of situation.  1 seems like a perfectly reasonable default
in that case.

   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