From d68bf2b419ed0c761c412bf2a58ed2f3c71ce904 Mon Sep 17 00:00:00 2001 From: Quentin Colombet Date: Thu, 17 Sep 2015 23:21:34 +0000 Subject: [PATCH] [ShrinkWrap] Refactor the handling of infinite loop in the analysis. - Strenghten the logic to be sure we hoist the restore point out of the current loop. (The fixes a bug with infinite loop, added as part of the patch.) - Walk over the exit blocks of the current loop to conver to the desired restore point in one iteration of the update loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@247958 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/ShrinkWrap.cpp | 20 +++--- test/CodeGen/AArch64/arm64-shrink-wrapping.ll | 62 +++++++++++++++++++ test/CodeGen/ARM/arm-shrink-wrapping.ll | 62 +++++++++++++++++++ test/CodeGen/PowerPC/ppc-shrink-wrapping.ll | 62 +++++++++++++++++++ test/CodeGen/X86/x86-shrink-wrapping.ll | 32 ++++++++++ 5 files changed, 229 insertions(+), 9 deletions(-) diff --git a/lib/CodeGen/ShrinkWrap.cpp b/lib/CodeGen/ShrinkWrap.cpp index c406c149c00..dff0973c924 100644 --- a/lib/CodeGen/ShrinkWrap.cpp +++ b/lib/CodeGen/ShrinkWrap.cpp @@ -313,16 +313,18 @@ void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB) { // for a post-dominator outside the loop. SmallVector ExitBlocks; MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks); - if (ExitBlocks.empty()) { - Restore = nullptr; - break; + // Push Restore outside of this loop. + // Look for the immediate post-dominator of the loop exits. + MachineBasicBlock *IPdom = Restore; + for (MachineBasicBlock *LoopExitBB: ExitBlocks) { + IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT); + if (!IPdom) + break; } - // Push Restore outside of this loop if immediate post-dominator is - // different from restore block. If immediate post-dominator is not - // different, bail out. - MachineBasicBlock *IPdom = - FindIDom<>(*Restore, Restore->successors(), *MPDT); - if (IPdom != Restore) + // If the immediate post-dominator is not in a less nested loop, + // then we are stuck in a program with an infinite loop. + // In that case, we will not find a safe point, hence, bail out. + if (IPdom && MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore)) Restore = IPdom; else { Restore = nullptr; diff --git a/test/CodeGen/AArch64/arm64-shrink-wrapping.ll b/test/CodeGen/AArch64/arm64-shrink-wrapping.ll index c547e8eceba..7d7005d82a0 100644 --- a/test/CodeGen/AArch64/arm64-shrink-wrapping.ll +++ b/test/CodeGen/AArch64/arm64-shrink-wrapping.ll @@ -568,3 +568,65 @@ for.body: ; preds = %for.body, %entry if.end: ret void } + +; Another infinite loop test this time with a body bigger than just one block. +; CHECK-LABEL: infiniteloop2 +; CHECK: ret +define void @infiniteloop2() { +entry: + br i1 undef, label %if.then, label %if.end + +if.then: + %ptr = alloca i32, i32 4 + br label %for.body + +for.body: ; preds = %for.body, %entry + %sum.03 = phi i32 [ 0, %if.then ], [ %add, %body1 ], [ 1, %body2] + %call = tail call i32 asm "mov $0, #0", "=r,~{x19}"() + %add = add nsw i32 %call, %sum.03 + store i32 %add, i32* %ptr + br i1 undef, label %body1, label %body2 + +body1: + tail call void asm sideeffect "nop", "~{x19}"() + br label %for.body + +body2: + tail call void asm sideeffect "nop", "~{x19}"() + br label %for.body + +if.end: + ret void +} + +; Another infinite loop test this time with two nested infinite loop. +; CHECK-LABEL: infiniteloop3 +; CHECK: ret +define void @infiniteloop3() { +entry: + br i1 undef, label %loop2a, label %body + +body: ; preds = %entry + br i1 undef, label %loop2a, label %end + +loop1: ; preds = %loop2a, %loop2b + %var.phi = phi i32* [ %next.phi, %loop2b ], [ %var, %loop2a ] + %next.phi = phi i32* [ %next.load, %loop2b ], [ %next.var, %loop2a ] + %0 = icmp eq i32* %var, null + %next.load = load i32*, i32** undef + br i1 %0, label %loop2a, label %loop2b + +loop2a: ; preds = %loop1, %body, %entry + %var = phi i32* [ null, %body ], [ null, %entry ], [ %next.phi, %loop1 ] + %next.var = phi i32* [ undef, %body ], [ null, %entry ], [ %next.load, %loop1 ] + br label %loop1 + +loop2b: ; preds = %loop1 + %gep1 = bitcast i32* %var.phi to i32* + %next.ptr = bitcast i32* %gep1 to i32** + store i32* %next.phi, i32** %next.ptr + br label %loop1 + +end: + ret void +} diff --git a/test/CodeGen/ARM/arm-shrink-wrapping.ll b/test/CodeGen/ARM/arm-shrink-wrapping.ll index 28ffca8344e..1313fefdd58 100644 --- a/test/CodeGen/ARM/arm-shrink-wrapping.ll +++ b/test/CodeGen/ARM/arm-shrink-wrapping.ll @@ -562,3 +562,65 @@ for.body: ; preds = %for.body, %entry if.end: ret void } + +; Another infinite loop test this time with a body bigger than just one block. +; CHECK-LABEL: infiniteloop2 +; CHECK: pop +define void @infiniteloop2() { +entry: + br i1 undef, label %if.then, label %if.end + +if.then: + %ptr = alloca i32, i32 4 + br label %for.body + +for.body: ; preds = %for.body, %entry + %sum.03 = phi i32 [ 0, %if.then ], [ %add, %body1 ], [ 1, %body2] + %call = tail call i32 asm "mov $0, #0", "=r,~{r4}"() + %add = add nsw i32 %call, %sum.03 + store i32 %add, i32* %ptr + br i1 undef, label %body1, label %body2 + +body1: + tail call void asm sideeffect "nop", "~{r4}"() + br label %for.body + +body2: + tail call void asm sideeffect "nop", "~{r4}"() + br label %for.body + +if.end: + ret void +} + +; Another infinite loop test this time with two nested infinite loop. +; CHECK-LABEL: infiniteloop3 +; CHECK: bx lr +define void @infiniteloop3() { +entry: + br i1 undef, label %loop2a, label %body + +body: ; preds = %entry + br i1 undef, label %loop2a, label %end + +loop1: ; preds = %loop2a, %loop2b + %var.phi = phi i32* [ %next.phi, %loop2b ], [ %var, %loop2a ] + %next.phi = phi i32* [ %next.load, %loop2b ], [ %next.var, %loop2a ] + %0 = icmp eq i32* %var, null + %next.load = load i32*, i32** undef + br i1 %0, label %loop2a, label %loop2b + +loop2a: ; preds = %loop1, %body, %entry + %var = phi i32* [ null, %body ], [ null, %entry ], [ %next.phi, %loop1 ] + %next.var = phi i32* [ undef, %body ], [ null, %entry ], [ %next.load, %loop1 ] + br label %loop1 + +loop2b: ; preds = %loop1 + %gep1 = bitcast i32* %var.phi to i32* + %next.ptr = bitcast i32* %gep1 to i32** + store i32* %next.phi, i32** %next.ptr + br label %loop1 + +end: + ret void +} diff --git a/test/CodeGen/PowerPC/ppc-shrink-wrapping.ll b/test/CodeGen/PowerPC/ppc-shrink-wrapping.ll index 1b4af819332..69adb39242b 100644 --- a/test/CodeGen/PowerPC/ppc-shrink-wrapping.ll +++ b/test/CodeGen/PowerPC/ppc-shrink-wrapping.ll @@ -554,3 +554,65 @@ for.body: ; preds = %for.body, %entry if.end: ret void } + +; Another infinite loop test this time with a body bigger than just one block. +; CHECK-LABEL: infiniteloop2 +; CHECK: blr +define void @infiniteloop2() { +entry: + br i1 undef, label %if.then, label %if.end + +if.then: + %ptr = alloca i32, i32 4 + br label %for.body + +for.body: ; preds = %for.body, %entry + %sum.03 = phi i32 [ 0, %if.then ], [ %add, %body1 ], [ 1, %body2] + %call = tail call i32 asm "mftb $0, 268", "=r,~{r14}"() + %add = add nsw i32 %call, %sum.03 + store i32 %add, i32* %ptr + br i1 undef, label %body1, label %body2 + +body1: + tail call void asm sideeffect "nop", "~{r14}"() + br label %for.body + +body2: + tail call void asm sideeffect "nop", "~{r14}"() + br label %for.body + +if.end: + ret void +} + +; Another infinite loop test this time with two nested infinite loop. +; CHECK-LABEL: infiniteloop3 +; CHECK: # %end +define void @infiniteloop3() { +entry: + br i1 undef, label %loop2a, label %body + +body: ; preds = %entry + br i1 undef, label %loop2a, label %end + +loop1: ; preds = %loop2a, %loop2b + %var.phi = phi i32* [ %next.phi, %loop2b ], [ %var, %loop2a ] + %next.phi = phi i32* [ %next.load, %loop2b ], [ %next.var, %loop2a ] + %0 = icmp eq i32* %var, null + %next.load = load i32*, i32** undef + br i1 %0, label %loop2a, label %loop2b + +loop2a: ; preds = %loop1, %body, %entry + %var = phi i32* [ null, %body ], [ null, %entry ], [ %next.phi, %loop1 ] + %next.var = phi i32* [ undef, %body ], [ null, %entry ], [ %next.load, %loop1 ] + br label %loop1 + +loop2b: ; preds = %loop1 + %gep1 = bitcast i32* %var.phi to i32* + %next.ptr = bitcast i32* %gep1 to i32** + store i32* %next.phi, i32** %next.ptr + br label %loop1 + +end: + ret void +} diff --git a/test/CodeGen/X86/x86-shrink-wrapping.ll b/test/CodeGen/X86/x86-shrink-wrapping.ll index ae9816f2fdc..5d4e63b329f 100644 --- a/test/CodeGen/X86/x86-shrink-wrapping.ll +++ b/test/CodeGen/X86/x86-shrink-wrapping.ll @@ -697,3 +697,35 @@ body2: if.end: ret void } + +; Another infinite loop test this time with two nested infinite loop. +; CHECK-LABEL: infiniteloop3 +; CHECK: retq +define void @infiniteloop3() { +entry: + br i1 undef, label %loop2a, label %body + +body: ; preds = %entry + br i1 undef, label %loop2a, label %end + +loop1: ; preds = %loop2a, %loop2b + %var.phi = phi i32* [ %next.phi, %loop2b ], [ %var, %loop2a ] + %next.phi = phi i32* [ %next.load, %loop2b ], [ %next.var, %loop2a ] + %0 = icmp eq i32* %var, null + %next.load = load i32*, i32** undef + br i1 %0, label %loop2a, label %loop2b + +loop2a: ; preds = %loop1, %body, %entry + %var = phi i32* [ null, %body ], [ null, %entry ], [ %next.phi, %loop1 ] + %next.var = phi i32* [ undef, %body ], [ null, %entry ], [ %next.load, %loop1 ] + br label %loop1 + +loop2b: ; preds = %loop1 + %gep1 = bitcast i32* %var.phi to i32* + %next.ptr = bitcast i32* %gep1 to i32** + store i32* %next.phi, i32** %next.ptr + br label %loop1 + +end: + ret void +} -- 2.34.1