Page MenuHomePhabricator

Limit the MaxSteps used in hasPredessorHelper
Needs ReviewPublic

Authored by trixirt on Apr 13 2018, 4:50 PM.

Details

Reviewers
hans
bogner
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.

Diff Detail

Repository
rL LLVM

Event Timeline

trixirt created this revision.Apr 13 2018, 4:50 PM

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 added inline comments.May 10 2018, 12:50 PM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
13264

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