diff options
| author | Michael Zolotukhin <mzolotukhin@apple.com> | 2017-12-21 01:22:13 +0000 |
|---|---|---|
| committer | Michael Zolotukhin <mzolotukhin@apple.com> | 2017-12-21 01:22:13 +0000 |
| commit | ad371e0caa6203e7e10aac9ef5aeac2a8618c8d4 (patch) | |
| tree | 449b45de65d276cc8ebca0c95325a237f3115c9f /lldb/packages/Python/lldbsuite/test/lang/cpp/exceptions/TestCPPExceptionBreakpoints.py | |
| parent | 5c73c49c9fccd3fd3fa69269e0eb16ee59ff0f78 (diff) | |
| download | bcm5719-llvm-ad371e0caa6203e7e10aac9ef5aeac2a8618c8d4.tar.gz bcm5719-llvm-ad371e0caa6203e7e10aac9ef5aeac2a8618c8d4.zip | |
[SimplifyCFG] Avoid quadratic on a predecessors number behavior in instruction sinking.
If a block has N predecessors, then the current algorithm will try to
sink common code to this block N times (whenever we visit a
predecessor). Every attempt to sink the common code includes going
through all predecessors, so the complexity of the algorithm becomes
O(N^2).
With this patch we try to sink common code only when we visit the block
itself. With this, the complexity goes down to O(N).
As a side effect, the moment the code is sunk is slightly different than
before (the order of simplifications has been changed), that's why I had
to adjust two tests (note that neither of the tests is supposed to test
SimplifyCFG):
* test/CodeGen/AArch64/arm64-jumptable.ll - changes in this test mimic
the changes that previous implementation of SimplifyCFG would do.
* test/CodeGen/ARM/avoid-cpsr-rmw.ll - in this test I disabled common
code sinking by a command line flag.
llvm-svn: 321236
Diffstat (limited to 'lldb/packages/Python/lldbsuite/test/lang/cpp/exceptions/TestCPPExceptionBreakpoints.py')
0 files changed, 0 insertions, 0 deletions
