NutshellySima (Chijun Sima)
User

Projects

User does not belong to any projects.

User Details

User Since
Feb 21 2018, 10:09 PM (38 w, 2 d)

Recent Activity

Tue, Nov 13

NutshellySima accepted D54312: [CSP, Cloning] Update DuplicateInstructionsInSplitBetween to use DomTreeUpdater..

LGTM. Thanks!

Tue, Nov 13, 8:31 AM

Fri, Nov 9

NutshellySima added inline comments to D54312: [CSP, Cloning] Update DuplicateInstructionsInSplitBetween to use DomTreeUpdater..
Fri, Nov 9, 11:01 AM
NutshellySima added inline comments to D54312: [CSP, Cloning] Update DuplicateInstructionsInSplitBetween to use DomTreeUpdater..
Fri, Nov 9, 10:37 AM
NutshellySima accepted D54317: [IPSCCP,PM] Preserve PDT in the new pass manager..

LGTM, thanks for the patch :)

Fri, Nov 9, 9:06 AM

Thu, Nov 8

NutshellySima accepted D47259: [IPSCCP,PM] Preserve DT in the new pass manager..

LGTM.

Thu, Nov 8, 11:53 AM
NutshellySima added inline comments to D47259: [IPSCCP,PM] Preserve DT in the new pass manager..
Thu, Nov 8, 10:24 AM

Tue, Oct 30

NutshellySima updated the diff for D50300: [WIP!][Dominators] Collect DomTree construction/update statistics and timing data.
  1. Add the timer on stateful deduplication (which aims to be deprecated soon).
  2. rebase.
Tue, Oct 30, 10:36 PM

Sat, Oct 27

NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

Since bug 37929 is a regression in version 7.0, should we backport this patch into branch 7.0.1 later (maybe November) if there isn't anyone reporting issues on this patch?

Sounds like a good idea

I recommend waiting about 2 weeks for the patch to get through all the various automated regression test frameworks out there. If there's a performance regression you'll likely hear about it within that time frame.

Sat, Oct 27, 1:51 AM

Thu, Oct 25

NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

Since bug 37929 is a regression in version 7.0, should we backport this patch into branch 7.0.1 later (maybe November) if there isn't anyone reporting issues on this patch?

Thu, Oct 25, 10:24 PM
NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

The constant "40" selected is based on the previous table and additional tests on "25" and "50" (see below),

αy/clangy/sqlitey/oggenc
0/baseline33.20%25.60%28.40%
2020.70%21.70%22.50%
2520.40%------
3013.10%23.10%23.70%
4013.60%24.10%24.90%
50---25.60%---
5514.20%26.00%28.00%
40 (n>=100)13.30%21.20%24.50%

I'll test n>=200/300/400 to see whether it is better.

Thu, Oct 25, 10:08 AM
NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

The issue I find with cl::opt here is that this is a generic class that may not necessarily have a corresponding cpp file -- there can be multiple clients to GenericDomTreeConstruction, each with different requirements. Because of that, it's not clear to me in which translation unit one would put cl::opt for the constant in.
Is that a solved problem somewhere else in LLVM? I'm not familiar with using cl::opt in header files.

Fair enough. I'm more used to working on function passes that have several cl::opt() lines at the top of the .cpp file. If we don't have a corresponding cpp it's non-trivial to add it as a command-line argument. I too have never tried to use cl::opt() in a .h.

Thu, Oct 25, 9:45 AM
NutshellySima updated the diff for D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).
  1. Adjust the constant to be 40.
  2. Disable recalculation when n<=100 && k<=n making the unittest of the incremental algorithm works as before.
Thu, Oct 25, 8:53 AM

Oct 16 2018

NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

@kuhar , here is the statistics for k*α>n:
Let y=time used by DT.applyUpdates/Times used by all DomTree Updating operations.
raw statistics:
clang: https://paste.ubuntu.com/p/yC8sSQqbsx/
SQLite: https://paste.ubuntu.com/p/cTpqDthsNC/
oggenc: https://paste.ubuntu.com/p/4RJkCxjhkY/

αy/clangy/sqlitey/oggenc
0/always update directly33.20%24.90%28.40%
522.10%19.60%20.80%
1020.90%20.00%20.30%
2020.70%21.70%22.50%
3013.10%23.10%23.70%
4013.60%24.10%24.90%
5514.20%26.00%28.00%
6513.80%27%28.70%
7014.10%27.30%29.30%
7514.00%28.80%30.10%
8014.20%28.10%30.20%
8514.20%29.50%30.80%
10014.70%30.60%31.00%
30017.60%42.90%34.60%
100056.40%43.00%34.50%
Oct 16 2018, 6:55 AM

Oct 15 2018

NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

I have tested heuristic k>n/α with α=10/40/65/70/75/80/100/300/1000 on clang.bcs. (But I didn't save them to a file :\) 10/1000 produce very bad result. ("10" is better than the current implementation). 300 produces better result than 1000. 40/100 produce better ones than 10/300/1000. And 65-80 don't make much difference and produce the best results among all αs I selected.

I'd be very interested to see the numbers for these constants.

Oct 15 2018, 8:21 AM
NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

For k>n you mentioned, I think you mean k>n/α (α is a constant) because for the reproducer in 37929, the minimum value of α to make the time consumed by clang acceptable is about 3 (α should definitely be larger than 3). But selecting a higher value like "75" can also boost other inputs more (about 2x~4.5x on clang*.bcs).

OK, makes sense if that the case in the bug report.

Would you be able to produce some numbers for clang for a heuristic like this:
if (n > 100) k * a >n; else if (k > n)
with different as?

Oct 15 2018, 8:06 AM
NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

Interesting. Nice improvements. What about small trees? It would seem that any tree less that 75 nodes would always be recalculated. Do the timings you ran include things to show that this is better? Or was that just looking at larger trees at the time?

I haven't conducted dedicated tests on graphs with the number of vertices less than 75, but among all the domtrees recalculated in the two clang-*.bc I mentioned above, there are approximately 63% of them has an n smaller than 75.

I'd be much more comfortable if this change didn't always recalculate for graphs smaller than 75. I think there is a lot of value in making sure the incremental updater is behaving correctly on small examples (e.g., existing unit tests, most regression tests, etc.). If for some reason it stops working, it will be much easier to detect and fix it on these small examples.

Thanks for the feedback. It makes sense to stop recalculating on small graphs but I need to have a check on whether it performs well.

In fact, the time used by directly applying updates to the domtree also depends on whether the graph is sparse or dense. It is hard to generate accurate heuristic to estimate when to recalculate the domtree or not. Because edge insertions have a complexity of O(m*min{n,k}+nk), edge deletions have a complexity of O(m*k) and recalculation has a complexity of O(n^2). (Let n denote number of vertices of the graph/m be the number of edges after updates/k be the number of updates). I think if we want to fine-tune this heuristic, we need to collect a lot of statistics and mathematically fit the function (n,m,k)->bool (whether to recalculate or not).

Since we cannot measure running time directly in any realistic scenario, I think that the best way to approach this would be to count the number of graph nodes visited during DFS walks and see how many of them we get with different heuristics.
I think that the bugs already established that we need to have some fallback heuristic. I'd suggest being careful here and trying at least a couple of different policies on different projects (maybe clang, sqlite, the lnt test suite). There are a couple of properties I propose for the heuristic:

  1. Don't always recalculate small trees (say, n < 100)
  2. Recalculate when k > n
  3. Recalculate in the case of the performance bugs we saw
  4. Visit fewer nodes than the current updater for Clang + SQLite + Oggenc + ...

For k>n you mentioned, I think you mean k>n/α (α is a constant) because for the reproducer in 37929, the minimum value of α to make the time consumed by clang acceptable is about 3 (α should definitely be larger than 3). But selecting a higher value like "75" can also boost other inputs more (about 2x~4.5x on clang*.bcs).

@kuhar , do you think we need to use another heuristic involving m? Though I think maybe using only n is sufficient? :)

Intuitively, I think that the heuristic can be some linear function: a * n + b * k > threshold, where a and b are coefficients and the threshold is a constant. I don't think it's possible to calculate m efficiently, is it?

m is the number of edges after updates. I think m can only be calculated by traversing two levels of linked lists to count the number of edges. It seems that it is O(m). I just think whether it is worthy to find some heuristic like n^2/m (I'm not sure whether it works better than the current one) and can avoid some cases when the graph is really sparse but also triggers the recalculation.

Oct 15 2018, 7:34 AM
NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

Interesting. Nice improvements. What about small trees? It would seem that any tree less that 75 nodes would always be recalculated. Do the timings you ran include things to show that this is better? Or was that just looking at larger trees at the time?

Oct 15 2018, 12:58 AM

Oct 14 2018

NutshellySima updated the summary of D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).
Oct 14 2018, 7:50 AM
NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).
  • For the constant "650", I used the 2nd reproducer in bug PR37929 and collected some statistics on the size of the updates after legalization and the time used by applying updates. The statistics shows that the time complexity is about Θ(k^2.4) (let k be the size of the update vector after legalization) [I have just checked the original paper, it is O(m min{n, k} + kn), so about Ω(k*(k+n)) in the case of the reproducer] and it seems that at least for a CFG size no larger than the one in PR37929, "650" is a reasonable value that the time used by recalculating is sure to be less than applying updates directly. (I think there sure should be some better heuristics deciding this.)

Thanks for the detailed explanation. This is what I expected. I don't it's enough to use 650 in the code without any explanation or justification -- even if it works in practise, I think it deserves a comment.

  • It is definitely better to get it related to the tree size but I'm lack of inputs with different CFG sizes to experiment on.

You can take intermediate bitcode files when doing full-LTO built using lld. I think the command that does the trick is --save-temps=DIR or similar.

  • I acknowledged this as an issue of the incremental updater not handling a huge update vector correctly; It definitely should fallback to recalculating if it is much faster. I believe this constant is related to the size of updates after legalization so I put it in the incremental updater. [Currently, there is a similar functionality in DTU which is Ω(n^2) and I believe it is slow and (redundant if JT submits updates normally) so I am considering removing it from DTU, then it is impossible to know the size of the legalized update vector]. Besides, it can also benefit other places not using the DomTreeUpdater.

I see. If we expect to see many redundant updates, then it makes sense to check that after legalization.

How about this heuristic instead: since we expect the complexity of a batch update to be O(k^2 + nk) and full recomputation is O(n^2) worst case, we can fallback to recomputation when k > n. Size of the tree should be accessible with just DT.size(), and it seems like a conservative choice we could improve later. What do you think?

Oct 14 2018, 7:31 AM
NutshellySima updated the diff for D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

Make the threshold selected proportional to the domtree size.

Oct 14 2018, 7:25 AM

Oct 13 2018

NutshellySima added a comment to D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).

Thanks for looking into this. A couple of high-level questions:

  • how was the constant "650" picked? Is it just playing with different values and choosing something that seemed reasonable?
  • why is the threshold independent of the tree size? Intuitively the policy could be to recalculate if the number of updates is greater than some multiple of size. Maybe we can refer to the average-case complexity from Lucuas' paper?
  • why do we want to put it in the incremental updater instead of the DomTreeUpdater class?
Oct 13 2018, 9:24 AM
NutshellySima created D53245: Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929).
Oct 13 2018, 7:04 AM

Aug 16 2018

NutshellySima accepted D48790: Update MemorySSA in Local utils removing blocks..

Thanks for the change.
Please have a look at my new inline comments. (I have a quick glance at the source code of MemorySSA and I think it's fine; but it's better for you to check that).
LGTM.

Aug 16 2018, 12:05 PM
NutshellySima added a comment to D48790: Update MemorySSA in Local utils removing blocks..

Thanks for the improvement! Comments are inline.

Aug 16 2018, 4:32 AM

Aug 15 2018

NutshellySima added a comment to D48790: Update MemorySSA in Local utils removing blocks..

Looks like a nice improvement.

Aug 15 2018, 8:21 AM

Aug 14 2018

NutshellySima retitled D50717: [SimplifyCFG] Remove pointer from SmallPtrSet before deletion from [NFC][SimplifyCFG] Remove pointer from SmallPtrSet before deletion to [SimplifyCFG] Remove pointer from SmallPtrSet before deletion.
Aug 14 2018, 11:44 PM
NutshellySima retitled D50717: [SimplifyCFG] Remove pointer from SmallPtrSet before deletion from [SimplifyCFG] Fix BasicBlock use-after-free to [NFC][SimplifyCFG] Remove pointer from SmallPtrSet before deletion.
Aug 14 2018, 9:54 AM
NutshellySima added a comment to D50717: [SimplifyCFG] Remove pointer from SmallPtrSet before deletion.

LGTM

I guess because it's only erasing it from a SmallPtrSet, it's not actually _using_ it, but this looks like a very sensible change.

Aug 14 2018, 9:50 AM
NutshellySima created D50717: [SimplifyCFG] Remove pointer from SmallPtrSet before deletion.
Aug 14 2018, 9:23 AM

Aug 11 2018

NutshellySima edited P8098 [WIP!][DomTreeUpdater] Benchmarks on Lazy UpdateStrategy.
Aug 11 2018, 5:11 AM

Aug 7 2018

NutshellySima edited P8097 [WIP!][DomTreeUpdater] Benchmarks on preserving DT in SimplifyCFG pass.
Aug 7 2018, 9:58 AM
NutshellySima added a comment to D50311: [WIP!][DomTreeUpdater/Auto[3]] A new Auto UpdateStrategy candidate.

Benchmark results on Auto UpdateStrategy 3:
https://reviews.llvm.org/P8101

Aug 7 2018, 9:51 AM
NutshellySima created P8101 [WIP!][DomTreeUpdater] Benchmarks on Auto UpdateStrategy 3.
Aug 7 2018, 9:50 AM
NutshellySima added a comment to D50308: [WIP!][DomTreeUpdater/Auto[2]] A new Auto UpdateStrategy candidate.

Some benchmarks on Auto UpdateStrategy 2:
https://reviews.llvm.org/P8100

Aug 7 2018, 9:49 AM
NutshellySima created P8100 [WIP!][DomTreeUpdater] Benchmarks on Auto UpdateStrategy 2.
Aug 7 2018, 9:49 AM
NutshellySima added a comment to D50302: [WIP!][DomTreeUpdater/Auto[1]] A new Auto UpdateStrategy to test the impact of passes preserving DomTree.

Some benchmarks on Auto UpdateStrategy 1:
https://reviews.llvm.org/P8099

Aug 7 2018, 9:48 AM
NutshellySima created P8099 [WIP!][DomTreeUpdater] Benchmarks on Auto UpdateStrategy 1.
Aug 7 2018, 9:47 AM
NutshellySima added a comment to D50300: [WIP!][Dominators] Collect DomTree construction/update statistics and timing data.

Some timing benchmarks on Lazy UpdateStrategy:
https://reviews.llvm.org/P8098

Aug 7 2018, 9:45 AM
NutshellySima created P8098 [WIP!][DomTreeUpdater] Benchmarks on Lazy UpdateStrategy.
Aug 7 2018, 9:45 AM
NutshellySima added a comment to D50305: [WIP!][DomTreeUpdater/Auto[1]] Preserve the DomTree in the SimplifyCFG pass.

Benchmark results: https://reviews.llvm.org/P8097

Aug 7 2018, 9:41 AM
NutshellySima created P8097 [WIP!][DomTreeUpdater] Benchmarks on preserving DT in SimplifyCFG pass.
Aug 7 2018, 9:40 AM

Aug 5 2018

NutshellySima retitled D50302: [WIP!][DomTreeUpdater/Auto[1]] A new Auto UpdateStrategy to test the impact of passes preserving DomTree from [WIP!][Dominators] A new Auto UpdateStrategy to test the impact of passes preserving DomTree to [WIP!][DomTreeUpdater/Auto[1]] A new Auto UpdateStrategy to test the impact of passes preserving DomTree.
Aug 5 2018, 8:31 AM
NutshellySima retitled D50305: [WIP!][DomTreeUpdater/Auto[1]] Preserve the DomTree in the SimplifyCFG pass from [WIP!][SimplifyCFG] Preserve the DomTree in the SimplifyCFG pass to [WIP!][DomTreeUpdater/Auto[1]] Preserve the DomTree in the SimplifyCFG pass.
Aug 5 2018, 8:31 AM
NutshellySima added a dependent revision for D50311: [WIP!][DomTreeUpdater/Auto[3]] A new Auto UpdateStrategy candidate: D50313: [WIP!][DomTreeUpdater-Auto[3]] Collect DomTree construction/update statistics and timing data.
Aug 5 2018, 8:28 AM
NutshellySima added a dependency for D50313: [WIP!][DomTreeUpdater-Auto[3]] Collect DomTree construction/update statistics and timing data: D50311: [WIP!][DomTreeUpdater/Auto[3]] A new Auto UpdateStrategy candidate.
Aug 5 2018, 8:28 AM
NutshellySima created D50313: [WIP!][DomTreeUpdater-Auto[3]] Collect DomTree construction/update statistics and timing data.
Aug 5 2018, 8:27 AM
NutshellySima added a dependency for D50312: [WIP!][DomTreeUpdater/Auto[3]] Convert existing passes and utils to use the Auto UpdateStrategy: D50311: [WIP!][DomTreeUpdater/Auto[3]] A new Auto UpdateStrategy candidate.
Aug 5 2018, 8:21 AM
NutshellySima added a dependent revision for D50311: [WIP!][DomTreeUpdater/Auto[3]] A new Auto UpdateStrategy candidate: D50312: [WIP!][DomTreeUpdater/Auto[3]] Convert existing passes and utils to use the Auto UpdateStrategy.
Aug 5 2018, 8:21 AM
NutshellySima created D50312: [WIP!][DomTreeUpdater/Auto[3]] Convert existing passes and utils to use the Auto UpdateStrategy.
Aug 5 2018, 8:21 AM
NutshellySima created D50311: [WIP!][DomTreeUpdater/Auto[3]] A new Auto UpdateStrategy candidate.
Aug 5 2018, 8:16 AM
NutshellySima added a dependent revision for D50308: [WIP!][DomTreeUpdater/Auto[2]] A new Auto UpdateStrategy candidate: D50309: [WIP!][DomTreeUpdater-Auto[2]] Collect DomTree construction/update statistics and timing data.
Aug 5 2018, 8:11 AM
NutshellySima added a dependency for D50309: [WIP!][DomTreeUpdater-Auto[2]] Collect DomTree construction/update statistics and timing data: D50308: [WIP!][DomTreeUpdater/Auto[2]] A new Auto UpdateStrategy candidate.
Aug 5 2018, 8:11 AM
NutshellySima created D50309: [WIP!][DomTreeUpdater-Auto[2]] Collect DomTree construction/update statistics and timing data.
Aug 5 2018, 7:55 AM
NutshellySima created D50308: [WIP!][DomTreeUpdater/Auto[2]] A new Auto UpdateStrategy candidate.
Aug 5 2018, 7:51 AM
NutshellySima added a dependent revision for D50302: [WIP!][DomTreeUpdater/Auto[1]] A new Auto UpdateStrategy to test the impact of passes preserving DomTree: D50305: [WIP!][DomTreeUpdater/Auto[1]] Preserve the DomTree in the SimplifyCFG pass.
Aug 5 2018, 4:22 AM
NutshellySima added a dependency for D50305: [WIP!][DomTreeUpdater/Auto[1]] Preserve the DomTree in the SimplifyCFG pass: D50302: [WIP!][DomTreeUpdater/Auto[1]] A new Auto UpdateStrategy to test the impact of passes preserving DomTree.
Aug 5 2018, 4:22 AM
NutshellySima added a comment to D50305: [WIP!][DomTreeUpdater/Auto[1]] Preserve the DomTree in the SimplifyCFG pass.

This patch only converts a limited number of tests to demonstrate the implementation of preserving the DT is correct.

Aug 5 2018, 4:04 AM
NutshellySima created D50305: [WIP!][DomTreeUpdater/Auto[1]] Preserve the DomTree in the SimplifyCFG pass.
Aug 5 2018, 4:03 AM
NutshellySima updated the summary of D50300: [WIP!][Dominators] Collect DomTree construction/update statistics and timing data.
Aug 5 2018, 4:01 AM
NutshellySima updated the summary of D50303: [WIP!][DomTreeUpdater-Auto[1]] Collect DomTree construction/update statistics and timing data.
Aug 5 2018, 4:00 AM
NutshellySima added a dependent revision for D50302: [WIP!][DomTreeUpdater/Auto[1]] A new Auto UpdateStrategy to test the impact of passes preserving DomTree: D50303: [WIP!][DomTreeUpdater-Auto[1]] Collect DomTree construction/update statistics and timing data.
Aug 5 2018, 3:49 AM
NutshellySima added a dependency for D50303: [WIP!][DomTreeUpdater-Auto[1]] Collect DomTree construction/update statistics and timing data: D50302: [WIP!][DomTreeUpdater/Auto[1]] A new Auto UpdateStrategy to test the impact of passes preserving DomTree.
Aug 5 2018, 3:49 AM
NutshellySima created D50303: [WIP!][DomTreeUpdater-Auto[1]] Collect DomTree construction/update statistics and timing data.
Aug 5 2018, 3:49 AM
NutshellySima created D50302: [WIP!][DomTreeUpdater/Auto[1]] A new Auto UpdateStrategy to test the impact of passes preserving DomTree.
Aug 5 2018, 3:40 AM
NutshellySima created D50300: [WIP!][Dominators] Collect DomTree construction/update statistics and timing data.
Aug 5 2018, 2:44 AM

Aug 2 2018

NutshellySima updated the diff for D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.

Fix the IR that the entryBB cannot have any pred.

Aug 2 2018, 9:54 PM
NutshellySima updated the diff for D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.

Fix a nit in Local.cpp of dealing with the TerminatorInst.

Aug 2 2018, 9:26 PM
NutshellySima updated the diff for D49982: [TailCallElim] Preserve DT and PDT.

Amend comments.

Aug 2 2018, 12:18 PM
NutshellySima updated the diff for D49982: [TailCallElim] Preserve DT and PDT.

Address comments

Aug 2 2018, 12:16 PM
NutshellySima updated the diff for D49982: [TailCallElim] Preserve DT and PDT.

Add the comment to point out the reason why we recalculate the DominatorTree.

Aug 2 2018, 11:17 AM
NutshellySima added inline comments to D49982: [TailCallElim] Preserve DT and PDT.
Aug 2 2018, 10:55 AM
NutshellySima added a comment to D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.

LGTM. I like how this revision of the patch is minimally invasive and most of the hard work is hidden in DTU. I strongly recommend running ninja check, ninja check-all, and a standard test-suite run on tip before committing.

Thank you for your hard work and patience on refactoring this interface @NutshellySima .

Aug 2 2018, 10:32 AM
NutshellySima updated the diff for D49988: [ADCE] Remove the need of DomTree.

Address comments.

Aug 2 2018, 9:04 AM
NutshellySima updated the diff for D49738: [Dominators] Make RemoveUnreachableBlocks return false if the BasicBlock is already awaiting deletion.

Address comments.

Aug 2 2018, 8:57 AM
NutshellySima retitled D49747: [Dominators] Remove the DeferredDominance class from [Dominators] Deprecate the DeferredDominance class to [Dominators] Remove the DeferredDominance class.
Aug 2 2018, 8:44 AM
NutshellySima created D50173: [Dominators] Refine the logic of recalculate() in the DomTreeUpdater.
Aug 2 2018, 2:17 AM
NutshellySima updated the diff for D49982: [TailCallElim] Preserve DT and PDT.

rebase

Aug 2 2018, 1:18 AM
NutshellySima updated the diff for D49738: [Dominators] Make RemoveUnreachableBlocks return false if the BasicBlock is already awaiting deletion.

rebase

Aug 2 2018, 12:50 AM
NutshellySima updated the diff for D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.

Remove the dependency of D49802

Aug 2 2018, 12:37 AM
NutshellySima removed a dependent revision for D49807: [Dominators] Make DTU be able to delete a BB before recalculation under Eager UpdateStrategy: D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.
Aug 2 2018, 12:35 AM
NutshellySima removed a dependency for D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class: D49807: [Dominators] Make DTU be able to delete a BB before recalculation under Eager UpdateStrategy.
Aug 2 2018, 12:35 AM
NutshellySima abandoned D49807: [Dominators] Make DTU be able to delete a BB before recalculation under Eager UpdateStrategy.

It's possible to do updates related to DelBB first then call deleteBB(DelBB) then do the recalculation, which will make the DTU interface less confusing to users.

Aug 2 2018, 12:35 AM

Jul 31 2018

NutshellySima updated the diff for D49982: [TailCallElim] Preserve DT and PDT.

Use Lazy Strategy instead of Eager to eliminate unnecessary recalculation like

DomTreeUpdater DTU(...);
// EntryBB changed
DTU.recalculate(F);
DTU.insertEdge(...)/deleteEdge(...);
DTU.flush(); // We can delay the recalculation to here if we use the Lazy UpdateStrategy.
Jul 31 2018, 5:30 AM

Jul 30 2018

NutshellySima accepted D49955: [Dominators] Make slow walks shorter.

LGTM.

Jul 30 2018, 9:48 AM
NutshellySima added a dependent revision for D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class: D49982: [TailCallElim] Preserve DT and PDT.
Jul 30 2018, 8:25 AM
NutshellySima added a dependency for D49982: [TailCallElim] Preserve DT and PDT: D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.
Jul 30 2018, 8:25 AM
NutshellySima updated the diff for D49982: [TailCallElim] Preserve DT and PDT.

rebase

Jul 30 2018, 8:25 AM
NutshellySima added a dependent revision for D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class: D49988: [ADCE] Remove the need of DomTree.
Jul 30 2018, 7:59 AM
NutshellySima added a dependency for D49988: [ADCE] Remove the need of DomTree: D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.
Jul 30 2018, 7:59 AM
NutshellySima created D49988: [ADCE] Remove the need of DomTree.
Jul 30 2018, 7:58 AM
NutshellySima created D49982: [TailCallElim] Preserve DT and PDT.
Jul 30 2018, 6:09 AM

Jul 25 2018

NutshellySima added a comment to D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.

Now the utils after conversion is functionally equivalent with the current DDT implementation and I think the patch is ready.

Jul 25 2018, 11:23 AM
NutshellySima added a comment to D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.

The patch converts passes and utils as the following
A. Pass Convertions

Eager (It's functionally equivalent)
DT/PDT.insertEdge/deleteEdge/applyUpdates -> DTU.insertEdge/deleteEdge/applyUpdates
Lazy
DDT.applyUpdates -> DTU.applyUpdates (because pass can control the UpdateStrategy it uses)
DDT.insert/deleteEdge -> DTU.insert/deleteEdgeRelaxed
DDT.pendingDeletedBB -> DTU.isBBPendingDeletion
DDT.flush -> DTU.getDomTree (DTU will auto-flush on destruction)
DDT.deleteBB -> DTU.deleteBB

B. Util Transforms
Despite transforms above,
a. DDT.applyUpdates is replaced with DTU.applyUpdates(..., /*ForceRemoveDuplicates*/ true) to make Eager Strategy DTU passed into can also do deduplication like DDT does.
b.

DDT.deleteBB(...);
DDT.applyUpdates(...);

is replaced with

... // Make sure the successor list of BB is cleared!
DTU.applyUpdates(..., /*ForceRemoveDuplicates*/ true);
DTU.deleteBB(BB);

c. Eager Strategy recalculation

DDT.deleteBB(BB);
DDT.recalculate(F);

is replaced with

DTU.deleteBB(BB, /*DisableNodeErasing*/)
DTU.recalculate(F);

d. All code not using the incremental update method is removed.
C. Unittest

  1. Modify the unittest to check MergeBasicBlockIntoOnlyPred in Local.cpp (12 [2*3*2] patterns)
UpdateStrategy
a. Eager UpdateStrategy
b. Lazy UpdateStrategy
DT/PDT
a. only DT
b. only PDT
c. DT+PDT
IR
a. replace the Entry BB
b. does not replace entry BB
  1. Modify the unittest for ConstantFoldTerminator to test both DT and PDT under Eager/Lazy UpdateStrategy.
  2. Add a unittest for RemoveUnreachableBlocks to test DT and PDT under Eager/Lazy UpdateStrategy
Jul 25 2018, 11:19 AM
NutshellySima added a dependent revision for D49807: [Dominators] Make DTU be able to delete a BB before recalculation under Eager UpdateStrategy: D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.
Jul 25 2018, 11:16 AM
NutshellySima added a dependency for D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class: D49807: [Dominators] Make DTU be able to delete a BB before recalculation under Eager UpdateStrategy.
Jul 25 2018, 11:16 AM
NutshellySima updated the diff for D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.

Fix minor issues.

Jul 25 2018, 11:15 AM
NutshellySima created D49807: [Dominators] Make DTU be able to delete a BB before recalculation under Eager UpdateStrategy.
Jul 25 2018, 11:15 AM

Jul 24 2018

NutshellySima added a dependency for D49747: [Dominators] Remove the DeferredDominance class: D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class.
Jul 24 2018, 11:48 AM
NutshellySima added a dependent revision for D48967: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class: D49747: [Dominators] Remove the DeferredDominance class.
Jul 24 2018, 11:48 AM
NutshellySima created D49747: [Dominators] Remove the DeferredDominance class.
Jul 24 2018, 11:48 AM