[AliasSetTracker] Degrade AliasSetTracker when may-alias sets get too large.
authorMichael Kuperstein <mkuper@google.com>
Fri, 19 Aug 2016 17:05:22 +0000 (17:05 +0000)
committerMichael Kuperstein <mkuper@google.com>
Fri, 19 Aug 2016 17:05:22 +0000 (17:05 +0000)
commit41898f0396533432d51fc34ceb9fbfb8f75efd3e
treede4ce1c3133f8f838022bfaa1e57fc89e9bf40aa
parentd7a3782ae4b86421b45704adbe3deac028e49dc8
[AliasSetTracker] Degrade AliasSetTracker when may-alias sets get too large.

Repeated inserts into AliasSetTracker have quadratic behavior - inserting a
pointer into AST is linear, since it requires walking over all "may" alias
sets and running an alias check vs. every pointer in the set.

We can avoid this by tracking the total number of pointers in "may" sets,
and when that number exceeds a threshold, declare the tracker "saturated".
This lumps all pointers into a single "may" set that aliases every other
pointer.

(This is a stop-gap solution until we migrate to MemorySSA)

This fixes PR28832.
Differential Revision: https://reviews.llvm.org/D23432

llvm-svn: 279274
llvm/include/llvm/Analysis/AliasSetTracker.h
llvm/lib/Analysis/AliasSetTracker.cpp
llvm/test/Analysis/AliasSet/saturation.ll [new file with mode: 0644]