Hi Sanjoy,
Thanks for investigating the issue!
I am more interested in getting the underlying problem fixed rather than making this particular test case work. I think I have more test cases where this problem crops up. I would any day prefer consistent results over compile time savings which can lead to inconsistencies. These inconsistencies require significant developer time to analyze and fix which just doesn't seem worth it.
Based on my limited familiarity with ScalarEvolution code I would like to propose a solution that may work-
Have two levels of caching for data structures for which infinite recursion is possible (like Value -> SCEV, Value->Predicate, Loop->BackedgeTakenCount etc).
The first level of caching is the 'PendingCache' and the second one is the 'FinalCache'. PendingCache is similar to PendingLoopPredicates. It is used to break infinite recursion. In addition we keep a Boolean class member 'PessimisticMode' (common to all caches).
The lookup logic for the cache is something like this-
If (PendingCache.find(Key)) {
PessimisticMode = true;
return Value;
} else if (FinalCache.find(Key)) {
return Value;
}
Insertion logic is like this-
If (PessimisticMode) {
PendingCache.insert(Entry);
} else {
FinalCache.insert(Entry);
}
We need to distinguish top level calls to the external interface like getSCEV()/getBackedgeTakenCount() etc from the internal recursive calls for setting/resetting the state correctly. We start with adding the most conservative result for the value in PendingCache. This would be getUnknown() for getSCEV().
So getSCEV() may be implemented something like this-
ScalarEvolution::getSCEV(Value *V) {
return getSCEVImpl(V, true);
}
ScalarEvolution::getSCEVImpl (Value *V, bool IsTopCall = false) {
// Look up in cache using logic described above
If (S = getExistingSCEV())
return S;
if (IsTopCall) {
PessimisticMode = false;
PendingCache.clear();
PendingCache.insert(V, getUnknown(V));
}
SCEV *S = createSCEV();
If(IsTopCall) {
FinalCache.insert(V, S);
forgetMemoizedResults(PendingCache);
} else if (PessimisticMode) {
PendingCache.insert(V, S);
} else {
FinalCache.insert(V, S);
}
return S;
}
Implementation in ScalarEvolution.cpp uses getSCEVImpl() instead of getSCEV().
The idea is that we can conclude accurate result for the topmost call and for values computed before we hit PessimisticMode (recursion on self). We actually do this in some parts of the codebase. For example, getBackedgeTakenInfo() inserts a conservative entry in the map, then replaces it with the real result and cleans up (possibly inaccurate) results for all the loop header phis. We just need to apply the approach in a more generic manner.
We may have to handle AddRecs (which are inherently self-recursive) as a special case in this setup.
Of course, we may be discarding more than necessary in this setup so it may have compile time implications. A better solution is more that welcome.
Please let me know your thoughts.
Thanks,
Pankaj
