C++: Fix infinite range analysis loop on invalid SSA #19477
Conversation
There was a problem hiding this comment.
Thanks for this work!
as an external viewer without much QL knowledge, it does seem there is some existing duplication in this code, among different versions of the IR implementation. I wonder if one could factor out some of that duplication?
Also, do you think there's any way to test this, or the code triggering this is too complex to easily put in a test? Can we have this covered in DCA? I think I recall you found this could be related to an endless loop in the SQL repo?
I will leave more knowledgeable QL devs to approve this.
| @@ -1319,6 +1319,13 @@ predicate canReuseSsaForMemoryResult(Instruction instruction) { | |||
| // We don't support reusing SSA for any location that could create a `Chi` instruction. | |||
| } | |||
|
|
|||
| predicate hasIncompleteSsa(IRFunction f) { | |||
There was a problem hiding this comment.
I understand this may be more or less an implementation detail, but should we still put a doc comment here?
There was a problem hiding this comment.
Happy to do that. Note that this is still a draft since I wanted to check the implications on DCA before I made this more pretty 🙂
There was a problem hiding this comment.
I've force-pushed some QLDoc in 510df38
…has correctly modelled SSA information.
The term you're looking for here is "parameterized modules" 😂 The IR implementation precedes parameterized modules and no one has found time to rewrite the IR to use parameterized modules yet. So right now the IR is "pyrameterized" via identical-files.json (so the duplication is actually not that bad since there's a script and a CI job to ensure that they're always identical)
Yeah, I plan on bumping a SHA on one of the projects in DCA once this PR goes in to make sure we have a test for this in DCA. I can't do that before this PR goes in since we can't test the "base SHA" since that will hit an infinite loop on the current main. |
dfdeeb8 to
9d2eb3d
Compare
|
DCA looks uneventful. No performance implications (as expected), and no result changes (since this affects such a small number of function bodies). |
|
DCA does seem to show some slowdown? Just over 10% for abseil on Linux, as the worst offender. |
Oh! You're right! Why wasn't that in I suppose the join order issue highlighted by DCA in |
Because it never is... |
Incidentally, it's the same question I asked yesterday here. As far as I could tell, we swept that kind of landing page alerts under a pretty high threshold in order to avoid wobble. That does seem to make the landing page less useful than it should... I wonder if the wobble we tried to silence was platform specific (i.e. windows maybe?) |
```
Evaluated relational algebra for predicate SsaInternals::getDefImpl/1#1ed4f567@65628fbv with tuple counts:
4935102 ~5% {4} r1 = SCAN `SsaInternals::SsaImpl::Definition.definesAt/3#dispred#7eea4c8f` OUTPUT In.2, In.3, In.0, In.1
104274503 ~1% {3} | JOIN WITH `SsaInternals::DefImpl.hasIndexInBlock/2#dispred#30a6c29f_120#join_rhs` ON FIRST 2 OUTPUT Rhs.2, Lhs.3, Lhs.2
4921319 ~2% {2} | JOIN WITH `SsaInternals::DefImpl.getSourceVariable/0#dispred#72437659` ON FIRST 2 OUTPUT Lhs.2, Lhs.0
return r1
```
After:
```
Evaluated relational algebra for predicate SsaInternals::SsaImpl::Definition.definesAt/3#dispred#7eea4c8f_1230#join_rhs@b280fb5h with tuple counts:
4935102 ~3% {4} r1 = SCAN `SsaInternals::SsaImpl::Definition.definesAt/3#dispred#7eea4c8f` OUTPUT In.1, In.2, In.3, In.0
return r1
Evaluated relational algebra for predicate SsaInternals::DefImpl.hasIndexInBlock/3#dispred#31d295aa_1230#join_rhs@2be655s4 with tuple counts:
5634706 ~1% {4} r1 = SCAN `SsaInternals::DefImpl.hasIndexInBlock/3#dispred#31d295aa` OUTPUT In.1, In.2, In.3, In.0
return r1
Evaluated relational algebra for predicate SsaInternals::getDefImpl/1#1ed4f567@8afa36uu with tuple counts:
4921319 ~2% {2} r1 = JOIN `SsaInternals::SsaImpl::Definition.definesAt/3#dispred#7eea4c8f_1230#join_rhs` WITH `SsaInternals::DefImpl.hasIndexInBlock/3#dispred#31d295aa_1230#join_rhs` ON FIRST 3 OUTPUT Lhs.3, Rhs.3
return r1
```
Should hopefully be fixed by 0836f0b. There were two issues:
Additionally, I found another small join order issue that I fixed in f255fc2. I'll rerun DCA and see if the performance has been fixed 🤞 |
As part of the IR SSA/alias analysis we compute the which memory allocations overlap. In #17062 we mitigated a problem where, in very large function bodies, the set of overlapping memory allocations was basically a cartesian product.
As a result of this, we don't always have proper SSA information on these large function bodies. It's well-known that even one missing SSA edge can cause the shared range analysis to loop infinitely.
This PR excludes the functions with incomplete SSA information from the new range analysis. Ideally, I would like us to move away from using the IR SSA/alias analysis in the new range analysis library, but that seemed like too big of a task to start right now.
On a customer codebase there were 3 functions in the entire database which contained incomplete SSA and this caused the range analysis to loop infinitely in any of these three functions.
I haven't managed to reproduce a test for this. However, I will make sure that we have testing for this in DCA once this PR is merged.