Page MenuHomePhabricator

[ADCE] Add control dependence computation

Authored by david2050 on Aug 16 2016, 8:21 AM.



This is part of a serious of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch adds the ability to compute control dependences using
the iterated dominance frontier. We extend the liveness propagation
to alternate between data and control dependences until convergences.

Modify the pass manager intergation to compute the post-dominator tree
needed for iterator dominance frontier.

We still force all terminators live for now until we add code to
handlinge removing control flow in a later patch.

No changes to effective behavior with this patch

Previous patches:

D23225 [ADCE] Modify data structures to support removing control flow
D23065 [ADCE] Refactor anticipating new functionality (NFC)
D23102 [ADCE] Refactoring for new functionality (NFC)

Diff Detail

Event Timeline

david2050 updated this revision to Diff 68185.Aug 16 2016, 8:21 AM
david2050 retitled this revision from to [ADCE] Add control dependence computation.
david2050 updated this object.
david2050 added reviewers: mehdi_amini, nadav, majnemer.
david2050 added subscribers: llvm-commits, freik, twoh.
nadav added inline comments.Aug 16 2016, 9:36 AM

Comments start with a capital letter. End with a period.

david2050 updated this revision to Diff 68211.Aug 16 2016, 10:06 AM

fix comments

david2050 updated this revision to Diff 68728.Aug 19 2016, 2:09 PM

Add a missing block which logically fits with this diff (since not yet accepted)

mehdi_amini added inline comments.Aug 22 2016, 12:07 PM

How expensive is this?

david2050 added inline comments.Aug 22 2016, 12:41 PM

In email, Daniel Berlin discusses this as well.

I measured ~400 cpp source files internally and impact is about ~0.6% (that is end to end starting with C++ source)

mehdi_amini added inline comments.Aug 22 2016, 12:46 PM


0.6% is not negligible: some LLVM users are starting from bitcode (i.e. they don't pay the frontend cost) so the % could be considerably higher, and have low-latency requirements.

It seems there is a tradeoff where the "existing" "fast" ADCE may still be desirable. Do you remember if this was addressed in a previous email thread? (I kind of remember there was a fairly extensive discussion on your first submissions)

david2050 added inline comments.Aug 22 2016, 1:38 PM

The previous discussion focused on the negative maintenance costs of having two implementations. That said, it clearly could choose to not build the PDT and forego control flow removal at lower optimiation levels. Then we would pay a smaller tax (~ double the number of hash table lookups) for the reduced functionality.

What should we do at this point? Should I add code to restrict use of PDT to -O3 or do that in a later diff?

mehdi_amini accepted this revision.Aug 23 2016, 9:27 AM
mehdi_amini edited edge metadata.

Let's postpone and figure later if we need an option to have a "degraded mode". Folks who really need it will have to measure the compile-time cost on their workload.

This revision is now accepted and ready to land.Aug 23 2016, 9:27 AM
david2050 closed this revision.Aug 23 2016, 5:17 PM