- User Since
- Jul 15 2015, 7:49 AM (183 w, 4 d)
Mon, Jan 7
Exactly. Given a set of CFG updates, if figures out how to change the DomTree and PostDomTree such that they match the CFG.
Thu, Jan 3
@anna Can this be rewritten to use the DomTreeUpdater utility? We have large number of examples in the codebase already, so the question is whether this affects the performance in this case. Historically, we had tons of bugs in manual DomTree updates and I'd rather we replaces as much as possible using the incremental updater.
Nov 20 2018
Nov 19 2018
We experimented with different ordering of updates before, including scheduling deletions before insertions, but didn't discover any promising strategies. Because of that, updates are performed in the exact order they were scheduled (except optimizing out trivially redundant ones).
Nov 13 2018
Nov 9 2018
Nov 8 2018
Looks good to me now, thanks for the fixes! You may want for somebody else to take a look at it, though.
Oct 25 2018
LGTM. Thanks for looking into this!
Oct 24 2018
Oct 16 2018
Awesome, thanks for the numbers. It's much easier to reason about it this way. But I'm a bit confused by why you measured it like this. Can we have statistics with respect to nodes visited during DFS? That should be highly correlated and give us more confidence in the measured times.
I think maybe "40" is a better choice?
30 seems best to me :)
Oct 15 2018
I think that for small n it shouldn't recalculate when k < n.
I'd be very interested to see the numbers for these constants.
OK, makes sense if that the case in the bug report.
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.
Oct 13 2018
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.
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?
Sep 24 2018
Sep 21 2018
Sep 4 2018
Thank you for the comments, Richard!
Aug 24 2018
Rename missed CallInlineKind parameters to CIK
Fix naming and add more tests.
One extra question: do you think this deserves a separate RFC?
Aug 23 2018
Disclaimer: I'm a Clang newbie and I'm not sure if that's a good way to implement these intrinsics. I'm not sure about the following things:
- The new enum CallInlineKind may not be in the right place
- Not sure if adding the extra parameter to EmitSomething methods is the cleanest thing possible -- some functions have it now, some don't, and it makes argument lists longer
- Not sure if just adding an extra attribute at each callsite is enough -- I'm not sure what is supposed to happen when there are conflicting inline attributes at call sites and function declarations (e.g. __builtin_always_inline and __attribute__ ((always_inline)))
- I don't know how to handle constexpr functions
- I don't know how to implement it for constructor calls
Aug 20 2018
Aug 17 2018
Aug 16 2018
Aug 14 2018
Aug 13 2018
Thanks for the changes. LGTM.
Aug 10 2018
Aug 9 2018
Sure. The children are being reversed to preserve the successor order in DFS, which uses stack and reverses them (again) internally. But this reverse can be moved somewhere else and you don't have to worry about it.
Aug 8 2018
One thing that is not clear to me is how you decide whether to apply the updates on top of the current CFG or to reverse-apply them. DomTreeConstruction needs the latter, but I don't know what makes sense in your use-case.
Aug 2 2018
Thanks for the changes!
Looks good, thanks for the patch!
Nit: It's removal and not deprecation.
Looks good otherwise.
Looks fine except for the test IR.
Jul 31 2018
Jul 28 2018
Jul 27 2018
@chandlerc FYI, all existing uses of the 'raw' api (DT.insert/deleteEdge, DT.applyUpdates) are going to be replaced with the new unified API after branching to 8.0. @NutshellySima is working on this.
The plan is also to hide insert/deleteEdge completely, so that we won't have bugs like this in the future.
This case requires batch updater. It's always surprising that these kinds of bugs can stay undetected for months.
Jul 25 2018
Thanks for the changes, Chijun!
Jul 24 2018
Thanks for the comment!
Jul 11 2018
LGTM, but please wait to see if @brzycki has some comments before submitting the patch
Looks like a nice improvement!
Jul 9 2018
A general high-level question/suggestion: would it be possible to split this patch such that we don't change all of the uses of DDT and plain updates at once? I'm afraid this can subtly break in many places, and the patch will have to be reverted a couple of times before you get them right. If you do it with more granularity, then it should be easier to land each part and test it in isolation.
Is it possible, or do you have a dependency on the utility functions from Local.cpp and other helper files?
Have you considered detecting that both trees are null and overriding the update strategy to Eager in that case? I think that should functionally be equivalent, although more confusing when the strategy you get can be different from what someone just set :P I'm just wondering what pros/cons there are.
Perhaps it would make sense to expose a similar function for the Eager strategy?
And I would make it sorter, so just isLazy and isEager -- shouldn't make anything more ambiguous IMO.
Jul 4 2018
One thing that is not clear to me is whether it's work to replace plain updates (DT->insert/deleteEdge, DT->applyUpdates) with DTU when it's clear that both are going to be functionally the same. The overhead of constructing DTU is probably negligible, but it's more verbose and I'm not sure what benefit it brings.
LGTM. Should make life easier.
Jul 2 2018
Jul 1 2018
Looks good to me now. Thanks for making all the fixes!
Jun 29 2018
Jun 28 2018
Looks almost ready to me. Found just a couple of nits.