Long ago , it was identified that part of LiveDebugValues had worst-case quadratic complexity. We test  whether a variable location would still be in scope when propagated into a block, to avoid needlessly propagating locations. If you have a block of DBG_VALUEs, all for different variables, then the LexicalScopes::dominates method will scan each instruction for each variable location, which is O(n^2). It doesn't appear to have been judged a high risk at the time.
We've run into a circumstance where this happens, once again with large amounts of inlining into a large basic block. To avoid the quadratic complexity, I think we can rely on the scope ranges that are computed in each LexicalScope object . These identify spans of the function that the lexical scope contains. Crucially, these spans cover all subscopes  as well. This patch changes the LexicalScopes::dominates method to, rather than testing each instruction in a block to see if it's dominated, instead test whether this block is in the set of dominated instructions blocks. (Which is a mouthful). This also involves fixing the getMachineBasicBlocks method, which didn't seem to be aware that each span could cover multiple blocks.
This patch eliminates the performance problem we encountered, and the complexity of LexicalScopes::dominates becomes linear with the size of the scope (measured in blocks), rather than the number of instructions in this block. The worst case would now be a circumstance where there are a large number of variable locations in a lexical scope that covers a large number of blocks (meaning we had to iterate over many blocks on each call to dominates). This, I believe, is not a circumstance that the inliner tries to create, as opposed to "many inlined scopes in one large block", which it does.
I tried building clang-3.4 with this patch applied, and there was no observable change in compile time (I guess it doesn't hit the worst case). I also tried building a stage2 build of clang with itself, with both implementations of LexicalScopes::dominates, comparing their answers. This showed up that the (current) implementation of dominates will interpret a metainstruction as being dominated , instead of ignoring it like the rest of LexicalScopes . Aside from that, both implementations of dominates agreed in all their results.
No test because this is a performance patch, although I can add one for the "don't consider metainstructions in scope dominance queries" matter if that's important.