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 /llvm/test | |
| 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 'llvm/test')
| -rw-r--r-- | llvm/test/CodeGen/AArch64/arm64-jumptable.ll | 16 | ||||
| -rw-r--r-- | llvm/test/CodeGen/ARM/avoid-cpsr-rmw.ll | 4 |
2 files changed, 9 insertions, 11 deletions
diff --git a/llvm/test/CodeGen/AArch64/arm64-jumptable.ll b/llvm/test/CodeGen/AArch64/arm64-jumptable.ll index f5c2ee6da0b..fac3e5704d1 100644 --- a/llvm/test/CodeGen/AArch64/arm64-jumptable.ll +++ b/llvm/test/CodeGen/AArch64/arm64-jumptable.ll @@ -6,22 +6,20 @@ define void @sum(i32 %a, i32* %to, i32 %c) { entry: switch i32 %a, label %exit [ i32 1, label %bb1 - i32 2, label %bb2 + i32 2, label %exit.sink.split i32 3, label %bb3 i32 4, label %bb4 ] bb1: %b = add i32 %c, 1 - store i32 %b, i32* %to - br label %exit -bb2: - store i32 2, i32* %to - br label %exit + br label %exit.sink.split bb3: - store i32 3, i32* %to - br label %exit + br label %exit.sink.split bb4: - store i32 5, i32* %to + br label %exit.sink.split +exit.sink.split: + %.sink = phi i32 [ 5, %bb4 ], [ %b, %bb1 ], [ 3, %bb3 ], [ %a, %entry ] + store i32 %.sink, i32* %to br label %exit exit: ret void diff --git a/llvm/test/CodeGen/ARM/avoid-cpsr-rmw.ll b/llvm/test/CodeGen/ARM/avoid-cpsr-rmw.ll index 78d3ebf371a..9373c5d4421 100644 --- a/llvm/test/CodeGen/ARM/avoid-cpsr-rmw.ll +++ b/llvm/test/CodeGen/ARM/avoid-cpsr-rmw.ll @@ -1,5 +1,5 @@ -; RUN: llc < %s -mtriple=thumbv7-apple-darwin -mcpu=cortex-a9 | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-CORTEX -; RUN: llc < %s -mtriple=thumbv7-apple-darwin -mcpu=swift | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-SWIFT +; RUN: llc < %s -mtriple=thumbv7-apple-darwin -mcpu=cortex-a9 -simplifycfg-sink-common=false | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-CORTEX +; RUN: llc < %s -mtriple=thumbv7-apple-darwin -mcpu=swift -simplifycfg-sink-common=false | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-SWIFT ; Avoid some 's' 16-bit instruction which partially update CPSR (and add false ; dependency) when it isn't dependent on last CPSR defining instruction. ; rdar://8928208 |
