[WebAssembly] Implement irreducible control flow.

This implements a very simple conservative transformation that doesn't
require more than linear code size growth. There's room for much more
optimization in this space.

llvm-svn: 262982

1 files changed, 88 insertions, 0 deletions

diff --git a/llvm/test/CodeGen/WebAssembly/irreducible-cfg.ll b/llvm/test/CodeGen/WebAssembly/irreducible-cfg.ll
new file mode 100644
index 00000000000..5226f176cd1
--- /dev/null
+++ b/llvm/test/CodeGen/WebAssembly/irreducible-cfg.ll
@@ -0,0 +1,88 @@
+; RUN: llc < %s -asm-verbose=false -verify-machineinstrs | FileCheck %s
+
+; Test irreducible CFG handling.
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+; A simple loop with two entries.
+
+; CHECK-LABEL: test0:
+define void @test0(double* %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
+bb:
+  %tmp = icmp eq i32 %arg2, 0
+  br i1 %tmp, label %bb6, label %bb3
+
+bb3:
+  %tmp4 = getelementptr double, double* %arg, i32 %arg3
+  %tmp5 = load double, double* %tmp4, align 4
+  br label %bb13
+
+bb6:
+  %tmp7 = phi i32 [ %tmp18, %bb13 ], [ 0, %bb ]
+  %tmp8 = icmp slt i32 %tmp7, %arg1
+  br i1 %tmp8, label %bb9, label %bb19
+
+bb9:
+  %tmp10 = getelementptr double, double* %arg, i32 %tmp7
+  %tmp11 = load double, double* %tmp10, align 4
+  %tmp12 = fmul double %tmp11, 2.300000e+00
+  store double %tmp12, double* %tmp10, align 4
+  br label %bb13
+
+bb13:
+  %tmp14 = phi double [ %tmp5, %bb3 ], [ %tmp12, %bb9 ]
+  %tmp15 = phi i32 [ undef, %bb3 ], [ %tmp7, %bb9 ]
+  %tmp16 = getelementptr double, double* %arg, i32 %tmp15
+  %tmp17 = fadd double %tmp14, 1.300000e+00
+  store double %tmp17, double* %tmp16, align 4
+  %tmp18 = add nsw i32 %tmp15, 1
+  br label %bb6
+
+bb19:
+  ret void
+}
+
+; A simple loop with two entries and an inner natural loop.
+
+; CHECK-LABEL: test1:
+define void @test1(double* %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
+bb:
+  %tmp = icmp eq i32 %arg2, 0
+  br i1 %tmp, label %bb6, label %bb3
+
+bb3:
+  %tmp4 = getelementptr double, double* %arg, i32 %arg3
+  %tmp5 = load double, double* %tmp4, align 4
+  br label %bb13
+
+bb6:
+  %tmp7 = phi i32 [ %tmp18, %bb13 ], [ 0, %bb ]
+  %tmp8 = icmp slt i32 %tmp7, %arg1
+  br i1 %tmp8, label %bb9, label %bb19
+
+bb9:
+  %tmp10 = getelementptr double, double* %arg, i32 %tmp7
+  %tmp11 = load double, double* %tmp10, align 4
+  %tmp12 = fmul double %tmp11, 2.300000e+00
+  store double %tmp12, double* %tmp10, align 4
+  br label %bb10
+
+bb10:
+  %p = phi i32 [ 0, %bb9 ], [ %pn, %bb10 ]
+  %pn = add i32 %p, 1
+  %c = icmp slt i32 %pn, 256
+  br i1 %c, label %bb10, label %bb13
+
+bb13:
+  %tmp14 = phi double [ %tmp5, %bb3 ], [ %tmp12, %bb10 ]
+  %tmp15 = phi i32 [ undef, %bb3 ], [ %tmp7, %bb10 ]
+  %tmp16 = getelementptr double, double* %arg, i32 %tmp15
+  %tmp17 = fadd double %tmp14, 1.300000e+00
+  store double %tmp17, double* %tmp16, align 4
+  %tmp18 = add nsw i32 %tmp15, 1
+  br label %bb6
+
+bb19:
+  ret void
+}