Verifier: Avoid quadratic checking of aggregates for bad bitcasts
authorDuncan P. N. Exon Smith <dexonsmith@apple.com>
Thu, 10 Dec 2015 17:56:06 +0000 (17:56 +0000)
committerDuncan P. N. Exon Smith <dexonsmith@apple.com>
Thu, 10 Dec 2015 17:56:06 +0000 (17:56 +0000)
commitfbc0a7d38b86d72481140d4e991327e86fdf2f2b
tree1dc8c0441746544e178e6c303441c2c1ca6a62cb
parent2c4226901e82fba7c2fe9b244a037e1b12acbff7
Verifier: Avoid quadratic checking of aggregates for bad bitcasts

Avoid O(N^2) behaviour when checking for bad bitcasts in `ConstantExpr`s
buried inside of aggregate initializers to `GlobalVariable`s.  I've:
- centralized the "visited" set for recursing through `ConstantExpr`s so
  that expressions are only visited once per Verifier run,
- removed the duplicate logic for the stack visit, and
- avoided recursing into other `GlobalValue`s.

This recovers roughly a 100x time difference in clang compiles of a
particular input file (filled with large cross-referencing tables) that
depends on whether `-disable-llvm-verifier` is on.  This slowdown was
caused by r187506, which introduced these checks.

Now, avoiding `-disable-llvm-verifier` only causes a 2x slowdown for
this case.

(Interestingly, dumping the textual IR for this file starts at least
50GB of global variable initializers (I don't know the total, since I
killed the dump)...)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@255269 91177308-0d34-0410-b5e6-96231b3b80d8
lib/IR/Verifier.cpp