This is an archive of the discontinued LLVM Phabricator instance.

[Dominators] Split SemiNCA into smaller functions
ClosedPublic

Authored by kuhar on Jul 11 2017, 5:25 PM.

Details

Summary

This patch splits the SemiNCA algorithm into smaller functions. It also adds a new debug macro.

In order to perform incremental updates, we need to be able to refire SemiNCA on a subset of CFG nodes (determined by a DFS walk results). We also need to skip nodes that are not deep enough in a DomTree.

Diff Detail

Repository
rL LLVM

Event Timeline

kuhar created this revision.Jul 11 2017, 5:25 PM
dberlin added inline comments.Jul 11 2017, 8:33 PM
include/llvm/Support/GenericDomTreeConstruction.h
34 ↗(On Diff #106120)

Why doesn't #define DEBUG_TYPE work?

69 ↗(On Diff #106120)

Why?

73 ↗(On Diff #106120)

Why?

205 ↗(On Diff #106120)

I'd rewrite this comment to "Skip predecessors whose level is above the subtree we are processing"

kuhar added inline comments.Jul 11 2017, 9:37 PM
include/llvm/Support/GenericDomTreeConstruction.h
34 ↗(On Diff #106120)

The macro can clash with DEBUG_TYPE in a file including it. Is it better change it to DEBUG_TYPE and undef it at the bottom of this header?

davide added inline comments.Jul 12 2017, 8:19 AM
include/llvm/Support/GenericDomTreeConstruction.h
34 ↗(On Diff #106120)

This seems to be symptom of a more general problem, there shouldn't be clashes. Which file is actually defining another dom-tree-builder ?

kuhar updated this revision to Diff 106330.Jul 12 2017, 3:48 PM

Added comments explaining that NumToNode is 1-based. Fixed the DEBUG macros.

kuhar marked 4 inline comments as done.Jul 12 2017, 3:50 PM
kuhar added inline comments.
include/llvm/Support/GenericDomTreeConstruction.h
34 ↗(On Diff #106120)

You were absolutely right. MachineCombiner defined the DEBUG_TYPE *before* including headers, and that was the root cause.

dberlin accepted this revision.Jul 13 2017, 10:20 AM

You should submit the machinecombiner change separately, but otherwise okay.

This revision is now accepted and ready to land.Jul 13 2017, 10:20 AM
davide accepted this revision.Jul 13 2017, 10:31 AM

Looks good to me as well (agree that the machinecombiner bit should be separated, you can do that without pre-commit review, it's a no-brainer [assuming it doesn't break anything :)]

kuhar marked an inline comment as done.Jul 13 2017, 1:28 PM

I fixed MachineCombiner in r307940 and a few places within Target/Hexagon in r307947.

kuhar updated this revision to Diff 106512.Jul 13 2017, 1:32 PM

Remove MachineCombiner changes.

This revision was automatically updated to reflect the committed changes.