Speed up Value::isUsedInBasicBlock() for long use lists.
authorJakob Stoklund Olesen <stoklund@2pi.dk>
Tue, 14 May 2013 23:45:56 +0000 (23:45 +0000)
committerJakob Stoklund Olesen <stoklund@2pi.dk>
Tue, 14 May 2013 23:45:56 +0000 (23:45 +0000)
commita88d974ce274152d2f8f28660ba277906bde2384
tree602a4422e605e7b23aaa1a371ad2a60c6b493c60
parentda2ed458b4e7066fc414c403173b882ccc2c8833
Speed up Value::isUsedInBasicBlock() for long use lists.

This is expanding Ben's original heuristic for short basic blocks to
also work for longer basic blocks and huge use lists.

Scan the basic block and the use list in parallel, terminating the
search when the shorter list ends. In almost all cases, either the basic
block or the use list is short, and the function returns quickly.

In one crazy test case with very long use chains, CodeGenPrepare runs
400x faster. When compiling ARMDisassembler.cpp it is 5x faster.

<rdar://problem/13840497>

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