Limit the MaxSteps used in hasPredessorHelper

[trixirt]

Summary

hasPredecessorHelper uses SmallPtrSet for the Visted data structure.
SmallPtrSet assumes it's size is less than 32 but can grow as large
as there is memory. When it does grow, the rehashing of it's large
table is very expensive.

By instrumenting hasPredecessorHelp and printing at the final Visited
size for a llvm+clang build, it was seen that nearly all of the
Visited's were less than 16.

In a 'small' 2000 line test case, when the Visited size was 1200,
the compile time 2 minutes. Now is down to 1 sec.

Only the function causing the problem was changed.
If anyone is interested in the instrumented data / histograms contact me offline.

[rogfer01]

Hi Tom,

please can you attach a patch with more context? See http://www.llvm.org/docs/Phabricator.html#phabricator-request-review-web

Also the function hasPredecessorHelperMaxSteps does not seem to follow the coding style in the variable names, see http://www.llvm.org/docs/CodingStandards.html#introduction

Kind regards,

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13264

I'm not sure to understand the whole change: doesn't this call return always compute 32*4 - 4?

If so, why using a function in the first place instead of adjusting Max above?

[trixirt]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13264

The input parameter controls the max level, so it is tunable.

include/llvm/CodeGen/SelectionDAGNodes.h

   }
 
   /// Return true if N is a predecessor of this node.
   /// N is either an operand of this node, or can be reached by recursively
   /// traversing up the operands.
   /// NOTE: This is an expensive method. Use it carefully.
   bool hasPredecessor(const SDNode *N) const;
 
+  /// Return a value to use in the MaxSteps of hasPredecessorHelper
+  /// This value helps to enforce the assumption that SmallPtrSet is small
+  /// When SmallPtrSet is large, rehashing Visited is the performace
+  /// bottleneck of the compiler.
+  static unsigned int hasPredecessorHelperMaxSteps(unsigned int OptimizationLevel = 2) {
+    //
+    // From reviewing the final Visited size while building llvm+clang,
+    // the mean was 12.45 and the standard deviation was 11.73.
+    // For SmallPtrSet, SmallSize max is 32.
+    unsigned int ret = 32;
+    // The maximum MaxSteps currently in use is 8192
+    // Do not go higher.
+    unsigned int max = 8192;
+    if (OptimizationLevel > 9) {
+      ret = max;
+    } else {
+      ret <<= OptimizationLevel;
+    }
+    // SmallPtrSet rehashes on powers of two.
+    // Reduce the MaxSteps by a bit to stop the last rehash.
+    unsigned int abit = 4;
+    ret -= abit;
+    return ret;
+  }
+
   /// Returns true if N is a predecessor of any node in Worklist. This
   /// helper keeps Visited and Worklist sets externally to allow unions
   /// searches to be performed in parallel, caching of results across
   /// queries and incremental addition to Worklist. Stops early if N is
   /// found but will resume. Remember to clear Visited and Worklists
   /// if DAG changes. MaxSteps gives a maximum number of nodes to visit before
   /// giving up. The TopologicalPrune flag signals that positive NodeIds are
   /// topologically ordered (Operands have strictly smaller node id) and search

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

     SmallVectorImpl<MemOpLink> &StoreNodes, unsigned NumStores) {
   // FIXME: We should be able to truncate a full search of
   // predecessors by doing a BFS and keeping tabs the originating
   // stores from which worklist nodes come from in a similar way to
   // TokenFactor simplfication.
 
   SmallPtrSet<const SDNode *, 16> Visited;
   SmallVector<const SDNode *, 8> Worklist;
-  unsigned int Max = 8192;
   // Search Ops of store candidates.
   for (unsigned i = 0; i < NumStores; ++i) {
     SDNode *n = StoreNodes[i].MemNode;
     // Potential loops may happen only through non-chain operands
     for (unsigned j = 1; j < n->getNumOperands(); ++j)
       Worklist.push_back(n->getOperand(j).getNode());
   }
   // Search through DAG. We can stop early if we find a store node.
   for (unsigned i = 0; i < NumStores; ++i)
     if (SDNode::hasPredecessorHelper(StoreNodes[i].MemNode, Visited, Worklist,
-                                     Max))
+                                     SDNode::hasPredecessorHelperMaxSteps()))
       return false;
   return true;
 }
 
 bool DAGCombiner::MergeConsecutiveStores(StoreSDNode *St) {
   if (OptLevel == CodeGenOpt::None)
     return false;