This is an archive of the discontinued LLVM Phabricator instance.

[ADCE] Modify data structures to support removing control flow
ClosedPublic

Authored by david2050 on Aug 5 2016, 1:33 PM.

Details

Summary

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

This patch changes the data structures to hold liveness information to
support the additional information we will eventually need. In
particular we now have a notion of basic blocks being live because
they contain a live operations. This will eventually feed into control
dependence analysis of which branches are live. We cater to getting
from instructions to associated block information and from blocks to
information about their terminators.

This patch also changes the structure of the main loop of the
algorithm so that it alternates propagating liveness between
instructions and usign control dependence information to mark branches
live.

We 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:

D23065 [ADCE] Refactor anticipating new functionality (NFC)
D23102 [ADCE] Refactoring for new functionality (NFC)

Diff Detail

Event Timeline

david2050 updated this revision to Diff 67008.Aug 5 2016, 1:33 PM
david2050 retitled this revision from to [ADCE] Modify data structures to support removing control flow.
david2050 updated this object.
david2050 added reviewers: mehdi_amini, nadav, majnemer.
david2050 added subscribers: llvm-commits, twoh, freik.
nadav added inline comments.Aug 5 2016, 1:51 PM
lib/Transforms/Scalar/ADCE.cpp
45

"Instruction's" -> "Instructions. "

48

Doxygen comment above the line.

54

Period at the end of the sentence.

62

What's "== & InstInfo[Terminator]" ? Can you write in english that this pointer points to "InstInfo[Terminator]".

Also, it could be a good idea to say something about the invalidation of InstInfo.

69

Comment above the line.

77

Are you using std::vector instead of SmallVector because you are expecting that most function will have a large number of basic blocks?

146

Can you please add a comment that explains why BlockInfo is twice as big as BlockInfoVec?

160

initialize -> Initialize.
Period.

mehdi_amini edited edge metadata.Aug 5 2016, 2:33 PM

No tests?

lib/Transforms/Scalar/ADCE.cpp
40

"optimization"

70

Is this struct supposed to evolve in the future?
I feel it is close to the point where it may become a proper class.
(It seems to have invariants like Terminator == BB->getTerminator)

77

Why do you need this?
Is it because the iteration ordering over the BlockInfo DenseMap isn't deterministic?
Why can't you always iterate over the function? Will you mutate the ordering in the vector or remove elements?

147

Use reserve() instead, unless you have a good reason to use grow() here?

150

One line comment for this loop.

161

(Same as above)

204

auto *BB to mark explicitly that it is a pointer.

230

No trivial braces for the two previous if

264

Right now I don't make sense of this two-levels loop structure, because the checkControlDependences() operates only on BlocksWithDeadTerminators, which is only inserted to during initialize(). I assume it will change in a future patch? (Or I missed something)

291

"unconditional"

294

Fuse the two if with an &&

329

auto *BB

david2050 marked 8 inline comments as done.Aug 5 2016, 2:35 PM
david2050 added inline comments.
lib/Transforms/Scalar/ADCE.cpp
77

No, will change.

david2050 updated this revision to Diff 67027.Aug 5 2016, 2:53 PM
david2050 marked an inline comment as done.
david2050 edited edge metadata.

address review comments

david2050 marked 6 inline comments as done.Aug 5 2016, 3:03 PM

Thanks!

lib/Transforms/Scalar/ADCE.cpp
70

We will had a little more state to support but it really will have no private data or sophisticated function.

77

Mehdi, yes, there are places where we iterate over the blocks in order so the DenseMap itself is not suitable. The order of the vector never changes. We could iterative of the basic blocks and index into the map if you feel strongly that it should be eliminated.

147

Is this comment about the resize above or the grow below?

264

In future, checkControlDependences will mark some branches as live as it determines they are needed. We then restart the data flow loop to make the data dependences of those branches as live.

david2050 updated this revision to Diff 67033.Aug 5 2016, 3:11 PM

Address comments

majnemer added inline comments.Aug 5 2016, 3:16 PM
lib/Transforms/Scalar/ADCE.cpp
139

Prefer auto * for pointer types.

331

Ditto.

mehdi_amini added inline comments.Aug 5 2016, 3:17 PM
lib/Transforms/Scalar/ADCE.cpp
77

For the three current loop over BlockInfoVec the iteration order does not seem to matter you could iterate over the DenseMap, the question is more about future patches that may benefit from this vector.

147

It is about grow below.

(Note there is an arrow on the top left of the comment next to my name with every comment that was made on a previous revision that can bring the context where the comment was made)

david2050 marked an inline comment as done.Aug 5 2016, 3:17 PM
david2050 added inline comments.
lib/Transforms/Scalar/ADCE.cpp
150

Missed this the first pass, in next diff

264

Will rename function to make this more explicit

david2050 updated this revision to Diff 67035.Aug 5 2016, 3:21 PM

Address comments

david2050 added inline comments.Aug 5 2016, 3:25 PM
lib/Transforms/Scalar/ADCE.cpp
147

I would have sworn I tried to use reserve() on a DenseMap and it did not have it. Must have misunderstood the error message. I will change to use reserve()

david2050 updated this revision to Diff 67038.Aug 5 2016, 3:28 PM

Address comments

david2050 updated this revision to Diff 67434.Aug 9 2016, 4:30 PM

Remove BlockInfoVec and move data structure into BlockInfo map.

All comments have been addressed

lib/Transforms/Scalar/ADCE.cpp
77

I was made some simplifications in code-to-be added and eliminated BlockInfoVec to just store the information directly in BlockInfo.

mehdi_amini accepted this revision.Aug 9 2016, 4:44 PM
mehdi_amini edited edge metadata.

Patch looks good overall, but it seems to me that you missed D.Majnemer's comments.
I added a few nits.
LGTM with these fixed.

lib/Transforms/Scalar/ADCE.cpp
39

"tempoary"

93

"blocks with not know to" does not seem correct (but English is not my native language)

101

"Instruscions"

139

ping.

148

Stalled comment (probably don't need a comment here, reserve is fairly explicit)

331

Ping

This revision is now accepted and ready to land.Aug 9 2016, 4:44 PM
david2050 closed this revision.Aug 16 2016, 7:39 AM