This is an archive of the discontinued LLVM Phabricator instance.

Differential D69823

[IR] [NFC] PR27065: Added tests for BasicBlock::removePredecessor.
AbandonedPublic

Authored by dendibakh on Nov 4 2019, 1:27 PM.

Details

Reviewers
grosser
spatel
lebedev.ri
Summary

This patch precommits tests that expose bugs in BasicBlock::removePredecessor.
In certain cases calling this function breaks SSA form.
Those bugs will be fixed in upcoming patches.

Diff Detail

Event Timeline

dendibakh created this revision.Nov 4 2019, 1:27 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 4 2019, 1:27 PM
Herald added a subscriber: llvm-commits. · View Herald Transcript
lebedev.ri added inline comments.Nov 4 2019, 1:32 PM
llvm/test/Transforms/Inline/clone-function-no-assert-on-phis.ll
8–10

Can that happen for non-dead code?
That is perfectly okay for dead, unreachable code.

dendibakh marked an inline comment as done.Nov 4 2019, 2:58 PM
dendibakh added inline comments.
llvm/test/Transforms/Inline/clone-function-no-assert-on-phis.ll
8–10

I think it doesn't happen for non-dead code. Otherwise, verifier would tell us about that.
Regarding BasicBlock::removePredecessor behavior: this is okay to leave broken code in unreachable blocks until someone will try to link detached blocks again. And we never know what will happen after user called removePredecessor. In this sense BasicBlock::removePredecessor should not leave broken code.

lebedev.ri added a reviewer: spatel.Nov 5 2019, 5:04 AM
lebedev.ri added inline comments.
llvm/test/Transforms/Inline/clone-function-no-assert-on-phis.ll
8–10

Please can you be more specific?
Is there more complete test case that demonstrates the issues this causes?

https://bugs.llvm.org/show_bug.cgi?id=27065
(which is no longer reproducible since that pass is gone)
reads to me as classical "pass gets overwhelmed by
the wonders of unreachable IR", which is solved by
not handling unreachable code, which also is faster:
rL372339 rL370911 rL355337 etc

dendibakh marked an inline comment as done.Nov 5 2019, 8:58 AM
dendibakh added inline comments.
llvm/test/Transforms/Inline/clone-function-no-assert-on-phis.ll
8–10

I don't have a test case for LLVM where this would cause miscompilation or compiler crash. But I ran into issues in our downstream. If you look from an API perspective, BasicBlock::removePredecessor violates its 'contract'. I mean it could leave broken code after itself. And we are not sure noone will use this code afterwards.

Moreover, implementation of BasicBlock::removePredecessor has serious issue and happens to work just by luck. I will upload the fix to showcase this.

As for the second part, yes, the repro in the LLVM bug tracker is no longer valid. You can find small examples in the unittests attached to this patch.

dendibakh retitled this revision from [IR] PR27065: Added tests for BasicBlock::removePredecessor. to [IR] [NFC] PR27065: Added tests for BasicBlock::removePredecessor..Nov 6 2019, 8:14 AM

Here are the 2 follow-up patches: D69862, D69865

spatel mentioned this in D69865: [IR] PR27065: Part2. Fix BasicBlock::removePredecessor to not break SSA form..Nov 7 2019, 5:17 AM
lebedev.ri requested changes to this revision.Nov 10 2019, 9:33 AM

(as per disscussion in https://reviews.llvm.org/D69865)

This revision now requires changes to proceed.Nov 10 2019, 9:33 AM
lebedev.ri resigned from this revision.Jan 12 2023, 4:43 PM

This review seems to be stuck/dead, consider abandoning if no longer relevant.

This revision now requires review to proceed.Jan 12 2023, 4:43 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 12 2023, 4:43 PM
Herald added a subscriber: StephenFan. · View Herald Transcript
dendibakh abandoned this revision.Jan 13 2023, 3:43 AM

Revision Contents

PathSize
llvm/
test/
Transforms/
Inline/
203 lines
unittests/
IR/
335 lines

Diff 227771

llvm/test/Transforms/Inline/clone-function-no-assert-on-phis.ll

  • This file was added.
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -S -inline < %s | FileCheck %s
; RUN: opt -S -passes='cgscc(inline)' < %s | FileCheck %s
; This test exposes bugs in BasicBlock::removePredecessor and
; will be fixed in further patches.
; Take a look at this line which has invalid SSA form:
; [[TMP81_I:%.*]] = getelementptr inbounds i8, i8* [[TMP81_I]], i64 1
; It happens to work, because the code is dead and
; verifier doesn't complain.
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

Can that happen for non-dead code?
That is perfectly okay for dead, unreachable code.

lebedev.ri: Can that happen for non-dead code? That is perfectly okay for dead, unreachable code.
dendibakhAuthorUnsubmitted
Done
ReplyInline Actions

I think it doesn't happen for non-dead code. Otherwise, verifier would tell us about that.
Regarding BasicBlock::removePredecessor behavior: this is okay to leave broken code in unreachable blocks until someone will try to link detached blocks again. And we never know what will happen after user called removePredecessor. In this sense BasicBlock::removePredecessor should not leave broken code.

dendibakh: I think it doesn't happen for non-dead code. Otherwise, verifier would tell us about that.
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

Please can you be more specific?
Is there more complete test case that demonstrates the issues this causes?

https://bugs.llvm.org/show_bug.cgi?id=27065
(which is no longer reproducible since that pass is gone)
reads to me as classical "pass gets overwhelmed by
the wonders of unreachable IR", which is solved by
not handling unreachable code, which also is faster:
rL372339 rL370911 rL355337 etc

lebedev.ri: Please can you be more specific? Is there more complete test case that demonstrates the issues…
dendibakhAuthorUnsubmitted
Done
ReplyInline Actions

I don't have a test case for LLVM where this would cause miscompilation or compiler crash. But I ran into issues in our downstream. If you look from an API perspective, BasicBlock::removePredecessor violates its 'contract'. I mean it could leave broken code after itself. And we are not sure noone will use this code afterwards.

Moreover, implementation of BasicBlock::removePredecessor has serious issue and happens to work just by luck. I will upload the fix to showcase this.

As for the second part, yes, the repro in the LLVM bug tracker is no longer valid. You can find small examples in the unittests attached to this patch.

dendibakh: I don't have a test case for LLVM where this would cause miscompilation or compiler crash. But…
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
@global = external hidden unnamed_addr constant [5 x i8], align 1
define i32 @main(i32 %arg, i8** %arg1) {
; CHECK-LABEL: @main(
; CHECK-NEXT: bb:
; CHECK-NEXT: [[TMP:%.*]] = alloca [5 x i8], align 1
; CHECK-NEXT: [[TMP2:%.*]] = alloca i8, align 1
; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds [5 x i8], [5 x i8]* [[TMP]], i64 0, i64 0
; CHECK-NEXT: call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(5) [[TMP3]], i8* nonnull align 1 dereferenceable(5) getelementptr inbounds ([5 x i8], [5 x i8]* @global, i64 0, i64 0), i64 5, i1 false)
; CHECK-NEXT: [[TMP4:%.*]] = getelementptr inbounds [5 x i8], [5 x i8]* [[TMP]], i64 0, i64 0
; CHECK-NEXT: store i8 97, i8* [[TMP2]], align 1
; CHECK-NEXT: [[TMP_I:%.*]] = ptrtoint i8* [[TMP4]] to i64
; CHECK-NEXT: [[TMP3_I:%.*]] = ptrtoint i8* [[TMP4]] to i64
; CHECK-NEXT: br label [[_ZST6REMOVEIPCCET_S1_S1_RKT0__EXIT:%.*]]
; CHECK: bb77.i:
; CHECK-NEXT: store i8 [[TMP75_I:%.*]], i8* [[TMP80_I:%.*]], align 1
; CHECK-NEXT: [[TMP78_I:%.*]] = getelementptr inbounds i8, i8* [[TMP80_I]], i64 1
; CHECK-NEXT: br label [[BB79_I:%.*]]
; CHECK: bb79.i:
; CHECK-NEXT: [[TMP80_I]] = phi i8* [ [[TMP80_I]], [[BB83_I:%.*]] ], [ [[TMP78_I]], [[BB77_I:%.*]] ]
; CHECK-NEXT: [[TMP81_I:%.*]] = getelementptr inbounds i8, i8* [[TMP81_I]], i64 1
; CHECK-NEXT: [[TMP82_I:%.*]] = icmp eq i8* [[TMP81_I]], [[TMP4]]
; CHECK-NEXT: br i1 [[TMP82_I]], label [[_ZST6REMOVEIPCCET_S1_S1_RKT0__EXIT]], label [[BB83_I]]
; CHECK: bb83.i:
; CHECK-NEXT: [[TMP84_I:%.*]] = load i8, i8* [[TMP2]], align 1
; CHECK-NEXT: [[TMP75_I]] = load i8, i8* [[TMP81_I]], align 1
; CHECK-NEXT: [[TMP76_I:%.*]] = icmp eq i8 [[TMP75_I]], [[TMP84_I]]
; CHECK-NEXT: br i1 [[TMP76_I]], label [[BB79_I]], label [[BB77_I]]
; CHECK: _ZSt6removeIPccET_S1_S1_RKT0_.exit:
; CHECK-NEXT: [[TMP86_I:%.*]] = phi i8* [ [[TMP4]], [[BB:%.*]] ], [ [[TMP80_I]], [[BB79_I]] ]
; CHECK-NEXT: ret i32 0
;
bb:
%tmp = alloca [5 x i8], align 1
%tmp2 = alloca i8, align 1
%tmp3 = getelementptr inbounds [5 x i8], [5 x i8]* %tmp, i64 0, i64 0
call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(5) %tmp3, i8* nonnull align 1 dereferenceable(5) getelementptr inbounds ([5 x i8], [5 x i8]* @global, i64 0, i64 0), i64 5, i1 false)
%tmp4 = getelementptr inbounds [5 x i8], [5 x i8]* %tmp, i64 0, i64 0
store i8 97, i8* %tmp2, align 1
%tmp5 = call i8* @_ZSt6removeIPccET_S1_S1_RKT0_(i8* nonnull %tmp4, i8* nonnull %tmp4, i8* nonnull dereferenceable(1) %tmp2)
ret i32 0
}
declare void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture writeonly, i8* noalias nocapture readonly, i64, i1 immarg)
define i8* @_ZSt6removeIPccET_S1_S1_RKT0_(i8* %arg, i8* %arg1, i8* dereferenceable(1) %arg2) {
bb:
%tmp = ptrtoint i8* %arg1 to i64
%tmp3 = ptrtoint i8* %arg to i64
%tmp4 = sub i64 %tmp, %tmp3
%tmp5 = icmp sgt i64 %tmp4, 3
br i1 %tmp5, label %bb6, label %bb32
bb6: ; preds = %bb
%tmp7 = lshr i64 %tmp4, 2
%tmp8 = load i8, i8* %arg2, align 1
br label %bb9
bb9: ; preds = %bb26, %bb6
%tmp10 = phi i64 [ %tmp7, %bb6 ], [ %tmp28, %bb26 ]
%tmp11 = phi i8* [ %arg, %bb6 ], [ %tmp27, %bb26 ]
%tmp12 = load i8, i8* %tmp11, align 1
%tmp13 = icmp eq i8 %tmp12, %tmp8
br i1 %tmp13, label %bb64, label %bb14
bb14: ; preds = %bb9
%tmp15 = getelementptr inbounds i8, i8* %tmp11, i64 1
%tmp16 = load i8, i8* %tmp15, align 1
%tmp17 = icmp eq i8 %tmp16, %tmp8
br i1 %tmp17, label %bb58, label %bb18
bb18: ; preds = %bb14
%tmp19 = getelementptr inbounds i8, i8* %tmp11, i64 2
%tmp20 = load i8, i8* %tmp19, align 1
%tmp21 = icmp eq i8 %tmp20, %tmp8
br i1 %tmp21, label %bb60, label %bb22
bb22: ; preds = %bb18
%tmp23 = getelementptr inbounds i8, i8* %tmp11, i64 3
%tmp24 = load i8, i8* %tmp23, align 1
%tmp25 = icmp eq i8 %tmp24, %tmp8
br i1 %tmp25, label %bb62, label %bb26
bb26: ; preds = %bb22
%tmp27 = getelementptr inbounds i8, i8* %tmp11, i64 4
%tmp28 = add nsw i64 %tmp10, -1
%tmp29 = icmp sgt i64 %tmp28, 0
br i1 %tmp29, label %bb9, label %bb30
bb30: ; preds = %bb26
%tmp31 = ptrtoint i8* %tmp27 to i64
br label %bb32
bb32: ; preds = %bb30, %bb
%tmp33 = phi i64 [ %tmp31, %bb30 ], [ %tmp3, %bb ]
%tmp34 = phi i8* [ %tmp27, %bb30 ], [ %arg, %bb ]
%tmp35 = sub i64 %tmp, %tmp33
switch i64 %tmp35, label %bb85 [
i64 3, label %bb40
i64 2, label %bb38
i64 1, label %bb36
]
bb36: ; preds = %bb32
%tmp37 = load i8, i8* %arg2, align 1
br label %bb53
bb38: ; preds = %bb32
%tmp39 = load i8, i8* %arg2, align 1
br label %bb46
bb40: ; preds = %bb32
%tmp41 = load i8, i8* %tmp34, align 1
%tmp42 = load i8, i8* %arg2, align 1
%tmp43 = icmp eq i8 %tmp41, %tmp42
br i1 %tmp43, label %bb64, label %bb44
bb44: ; preds = %bb40
%tmp45 = getelementptr inbounds i8, i8* %tmp34, i64 1
br label %bb46
bb46: ; preds = %bb44, %bb38
%tmp47 = phi i8 [ %tmp39, %bb38 ], [ %tmp42, %bb44 ]
%tmp48 = phi i8* [ %tmp34, %bb38 ], [ %tmp45, %bb44 ]
%tmp49 = load i8, i8* %tmp48, align 1
%tmp50 = icmp eq i8 %tmp49, %tmp47
br i1 %tmp50, label %bb64, label %bb51
bb51: ; preds = %bb46
%tmp52 = getelementptr inbounds i8, i8* %tmp48, i64 1
br label %bb53
bb53: ; preds = %bb51, %bb36
%tmp54 = phi i8 [ %tmp37, %bb36 ], [ %tmp47, %bb51 ]
%tmp55 = phi i8* [ %tmp34, %bb36 ], [ %tmp52, %bb51 ]
%tmp56 = load i8, i8* %tmp55, align 1
%tmp57 = icmp eq i8 %tmp56, %tmp54
br i1 %tmp57, label %bb64, label %bb85
bb58: ; preds = %bb14
%tmp59 = getelementptr inbounds i8, i8* %tmp11, i64 1
br label %bb64
bb60: ; preds = %bb18
%tmp61 = getelementptr inbounds i8, i8* %tmp11, i64 2
br label %bb64
bb62: ; preds = %bb22
%tmp63 = getelementptr inbounds i8, i8* %tmp11, i64 3
br label %bb64
bb64: ; preds = %bb62, %bb60, %bb58, %bb53, %bb46, %bb40, %bb9
%tmp65 = phi i8 [ %tmp41, %bb40 ], [ %tmp47, %bb46 ], [ %tmp54, %bb53 ], [ %tmp8, %bb9 ], [ %tmp8, %bb62 ], [ %tmp8, %bb60 ], [ %tmp8, %bb58 ]
%tmp66 = phi i8* [ %tmp34, %bb40 ], [ %tmp48, %bb46 ], [ %tmp55, %bb53 ], [ %tmp11, %bb9 ], [ %tmp63, %bb62 ], [ %tmp61, %bb60 ], [ %tmp59, %bb58 ]
%tmp67 = icmp eq i8* %tmp66, %arg1
br i1 %tmp67, label %bb85, label %bb68
bb68: ; preds = %bb64
%tmp69 = getelementptr inbounds i8, i8* %tmp66, i64 1
%tmp70 = icmp eq i8* %tmp69, %arg1
br i1 %tmp70, label %bb85, label %bb71
bb71: ; preds = %bb83, %bb68
%tmp72 = phi i8 [ %tmp84, %bb83 ], [ %tmp65, %bb68 ]
%tmp73 = phi i8* [ %tmp81, %bb83 ], [ %tmp69, %bb68 ]
%tmp74 = phi i8* [ %tmp80, %bb83 ], [ %tmp66, %bb68 ]
%tmp75 = load i8, i8* %tmp73, align 1
%tmp76 = icmp eq i8 %tmp75, %tmp72
br i1 %tmp76, label %bb79, label %bb77
bb77: ; preds = %bb71
store i8 %tmp75, i8* %tmp74, align 1
%tmp78 = getelementptr inbounds i8, i8* %tmp74, i64 1
br label %bb79
bb79: ; preds = %bb77, %bb71
%tmp80 = phi i8* [ %tmp74, %bb71 ], [ %tmp78, %bb77 ]
%tmp81 = getelementptr inbounds i8, i8* %tmp73, i64 1
%tmp82 = icmp eq i8* %tmp81, %arg1
br i1 %tmp82, label %bb85, label %bb83
bb83: ; preds = %bb79
%tmp84 = load i8, i8* %arg2, align 1
br label %bb71
bb85: ; preds = %bb79, %bb68, %bb64, %bb53, %bb32
%tmp86 = phi i8* [ %arg1, %bb64 ], [ %arg1, %bb32 ], [ %arg1, %bb53 ], [ %tmp66, %bb68 ], [ %tmp80, %bb79 ]
ret i8* %tmp86
}

llvm/unittests/IR/BasicBlockTest.cpp

//===- llvm/unittest/IR/BasicBlockTest.cpp - BasicBlock unit tests --------===// //===- llvm/unittest/IR/BasicBlockTest.cpp - BasicBlock unit tests --------===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#include "llvm/IR/BasicBlock.h" #include "llvm/IR/BasicBlock.h"
#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/STLExtras.h"
#include "llvm/IR/Function.h" #include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h" #include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h" #include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h" #include "llvm/IR/Module.h"
#include "llvm/IR/NoFolder.h" #include "llvm/IR/NoFolder.h"
#include "llvm/IR/Verifier.h"
#include "llvm/AsmParser/Parser.h"
#include "llvm/Support/SourceMgr.h"
#include "gmock/gmock-matchers.h" #include "gmock/gmock-matchers.h"
#include "gtest/gtest.h" #include "gtest/gtest.h"
#include <memory> #include <memory>
namespace llvm { namespace llvm {
namespace { namespace {
TEST(BasicBlockTest, PhiRange) { TEST(BasicBlockTest, PhiRange) {
▲ Show 20 Lines • Show All 100 Lines • ▼ Show 20 LinesTEST(BasicBlockTest, TestInstructionsWithoutDebug) {
EXPECT_EQ(static_cast<size_t>(BB1->sizeWithoutDebug()), Exp.size()); EXPECT_EQ(static_cast<size_t>(BB1->sizeWithoutDebug()), Exp.size());
EXPECT_EQ(static_cast<size_t>(BBConst->sizeWithoutDebug()), Exp.size()); EXPECT_EQ(static_cast<size_t>(BBConst->sizeWithoutDebug()), Exp.size());
delete M; delete M;
delete V; delete V;
} }
static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
StringRef ModuleStr) {
SMDiagnostic Err;
std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
assert(M && "Bad LLVM IR?");
return M;
}
static void checkFunctionIsValid(const Function &F) {
std::string Error;
raw_string_ostream ErrorOS(Error);
EXPECT_FALSE(verifyFunction(F, &ErrorOS));
EXPECT_STREQ(ErrorOS.str().c_str(), "");
}
static void checkFunctionIsNotValid(const Function &F) {
EXPECT_TRUE(verifyFunction(F));
}
TEST(BasicBlockTest, RemovePredecessorPhiOneInput) {
StringRef ModuleString = R"(
define i32 @f(i1 %cmp, i8 *%call) {
entry:
br i1 %cmp, label %body, label %ret.bb
body:
%ptr.1 = phi i8* [ %call, %entry]
%inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
br label %ret.bb
ret.bb:
ret i32 0
})";
LLVMContext Context;
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
Function *F = M->getFunction("f");
Function::iterator FI = F->begin();
BasicBlock *EntryBB = &*FI++;
BasicBlock *BodyBB = &*FI++;
{
EXPECT_EQ(BodyBB->size(), 3u);
PHINode *PN = dyn_cast<PHINode>(BodyBB->begin());
ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
EXPECT_EQ(PN->getNumIncomingValues(), 1u);
}
BodyBB->removePredecessor(EntryBB);
{
// Input value was propagated into the use of %ptr.1.
// In this case it's useless to verify the function, since
// verifier doesn't analyze dead blocks.
EXPECT_EQ(BodyBB->size(), 2u);
GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(BodyBB->begin());
ASSERT_NE(GEP, nullptr) << "Expecting GEP as a first instruction";
EXPECT_NE(GEP, GEP->getPointerOperand());
}
}
TEST(BasicBlockTest, RemovePredecessorPhiTwoInputsLoop) {
StringRef ModuleString = R"(
define i32 @f(i1 %cmp, i8 *%call) {
entry:
br i1 %cmp, label %body, label %ret.bb
body:
%ptr.1 = phi i8* [ %call, %entry],[ %inc.ptr1, %body ]
%inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
br i1 %cmp, label %ret.bb, label %body
ret.bb:
ret i32 0
})";
LLVMContext Context;
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
Function *F = M->getFunction("f");
Function::iterator FI = F->begin();
BasicBlock *EntryBB = &*FI++;
BasicBlock *BodyBB = &*FI++;
{
checkFunctionIsValid(*F);
EXPECT_EQ(BodyBB->size(), 3u);
PHINode *PN = dyn_cast<PHINode>(BodyBB->begin());
ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
EXPECT_EQ(PN->getNumIncomingValues(), 2u);
}
BodyBB->removePredecessor(EntryBB);
{
checkFunctionIsNotValid(*F);
// Input value was propagated into the use of %ptr.1.
// It broke SSA form!
EXPECT_EQ(BodyBB->size(), 2u);
GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(BodyBB->begin());
ASSERT_NE(GEP, nullptr) << "Expecting GEP as a first instruction";
EXPECT_EQ(GEP, GEP->getPointerOperand());
}
}
TEST(BasicBlockTest, RemovePredecessorMultipleLoopPhis) {
StringRef ModuleString = R"(
define i32 @f(i1 %cmp, i8 *%call) {
entry:
br i1 %cmp, label %body, label %ret.bb
body:
%ptr.1 = phi i8* [ %call, %entry],[ %inc.ptr1, %body ]
%ptr.2 = phi i8* [ %call, %entry],[ %inc.ptr2, %body ]
%inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
%inc.ptr2 = getelementptr inbounds i8, i8* %ptr.2, i64 2
br i1 %cmp, label %ret.bb, label %body
ret.bb:
ret i32 0
})";
LLVMContext Context;
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
Function *F = M->getFunction("f");
Function::iterator FI = F->begin();
BasicBlock *EntryBB = &*FI++;
BasicBlock *BodyBB = &*FI++;
{
checkFunctionIsValid(*F);
EXPECT_EQ(BodyBB->size(), 5u);
PHINode *PN = dyn_cast<PHINode>(BodyBB->begin());
ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
EXPECT_EQ(PN->getNumIncomingValues(), 2u);
}
BodyBB->removePredecessor(EntryBB);
{
checkFunctionIsNotValid(*F);
// Input values were propagated into the use of %ptr.1.
// It broke SSA form!
EXPECT_EQ(BodyBB->size(), 3u);
GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(BodyBB->begin());
ASSERT_NE(GEP1, nullptr) << "Expecting GEP as a first instruction";
EXPECT_EQ(GEP1, GEP1->getPointerOperand());
GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(BodyBB->begin()++);
ASSERT_NE(GEP2, nullptr) << "Expecting GEP as a second instruction";
EXPECT_EQ(GEP2, GEP2->getPointerOperand());
}
}
TEST(BasicBlockTest, RemovePredecessorPhiTwoInputsIfElse) {
StringRef ModuleString = R"(
define i32 @f(i1 %cmp, i8 *%call) {
entry:
br i1 %cmp, label %body, label %if.bb
if.bb:
br i1 %cmp, label %body, label %ret.bb
body:
%ptr.1 = phi i8* [ %call, %entry],[ %call, %if.bb ]
%inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
br label %ret.bb
ret.bb:
ret i32 0
})";
LLVMContext Context;
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
Function *F = M->getFunction("f");
Function::iterator FI = F->begin();
BasicBlock *EntryBB = &*FI++;
*FI++; // IfBB
BasicBlock *BodyBB = &*FI++;
{
EXPECT_EQ(BodyBB->size(), 3u);
PHINode *PN = dyn_cast<PHINode>(BodyBB->begin());
ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
EXPECT_EQ(PN->getNumIncomingValues(), 2u);
}
BodyBB->removePredecessor(EntryBB);
{
// Input value was propagated into the use of %ptr.1.
// In this case it's okay, since SSA from is preserved.
checkFunctionIsValid(*F);
EXPECT_EQ(BodyBB->size(), 2u);
GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(BodyBB->begin());
ASSERT_NE(GEP, nullptr) << "Expecting GEP as a first instruction";
EXPECT_NE(GEP, GEP->getPointerOperand());
}
}
TEST(BasicBlockTest, RemovePredecessorPhiThreeInputsLoop) {
StringRef ModuleString = R"(
define i32 @f(i1 %cmp, i8 *%call) {
entry:
br i1 %cmp, label %body, label %if.bb
if.bb:
br i1 %cmp, label %body, label %ret.bb
body:
%ptr.1 = phi i8* [ %call, %entry],[ %call, %if.bb],[ %inc.ptr1, %body ]
%inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
br i1 %cmp, label %ret.bb, label %body
ret.bb:
ret i32 0
})";
LLVMContext Context;
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
Function *F = M->getFunction("f");
Function::iterator FI = F->begin();
BasicBlock *EntryBB = &*FI++;
BasicBlock *IfBB = &*FI++;
BasicBlock *BodyBB = &*FI++;
BasicBlock *RetBB = &*FI++;
{
checkFunctionIsValid(*F);
EXPECT_EQ(BodyBB->size(), 3u);
PHINode *PN = dyn_cast<PHINode>(BodyBB->begin());
ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
EXPECT_EQ(PN->getNumIncomingValues(), 3u);
}
BodyBB->removePredecessor(EntryBB);
// update the edge from entry->body to entry->ret.bb
// this is needed to verify the function
BranchInst *BI = dyn_cast<BranchInst>(EntryBB->getTerminator());
ASSERT_NE(BI, nullptr) << "Couldn't get BranchInst.";
BI->setSuccessor(0, RetBB);
{
checkFunctionIsValid(*F);
// Phi stays, because there are still 2 input values left.
EXPECT_EQ(BodyBB->size(), 3u);
PHINode *PN = dyn_cast<PHINode>(BodyBB->begin());
ASSERT_NE(PN, nullptr) << "Expecting PHINode as a first instruction";
EXPECT_EQ(PN->getNumIncomingValues(), 2u);
EXPECT_EQ(PN->getIncomingBlock(0), IfBB);
EXPECT_EQ(PN->getIncomingBlock(1), BodyBB);
}
}
TEST(BasicBlockTest, RemovePredecessorReplaceUsesOfPhiWith2Inputs) {
StringRef ModuleString = R"(
define i32 @f(i1 %cmp, i8 *%call) {
entry:
br i1 %cmp, label %phi.bb, label %ret.bb
phi.bb:
%ptr.1 = phi i8* [ %call, %entry],[ %inc.ptr1, %use.bb ]
br label %use.bb
use.bb:
%inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
br i1 %cmp, label %ret.bb, label %phi.bb
ret.bb:
ret i32 0
})";
LLVMContext Context;
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
Function *F = M->getFunction("f");
Function::iterator FI = F->begin();
BasicBlock *EntryBB = &*FI++;
BasicBlock *PhiBB = &*FI++;
BasicBlock *UseBB = &*FI++;
{
checkFunctionIsValid(*F);
EXPECT_EQ(PhiBB->size(), 2u);
PHINode *PN = dyn_cast<PHINode>(PhiBB->begin());
ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
EXPECT_EQ(PN->getNumIncomingValues(), 2u);
}
PhiBB->removePredecessor(EntryBB);
{
checkFunctionIsNotValid(*F);
// Input value %inc.ptr1 was propagated into all it's uses.
// Now SSA form is broken.
EXPECT_EQ(PhiBB->size(), 1u);
EXPECT_EQ(UseBB->size(), 2u);
GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UseBB->begin());
ASSERT_NE(GEP, nullptr) << "Expecting GEP as a first instruction";
EXPECT_EQ(GEP, GEP->getPointerOperand());
}
}
TEST(BasicBlockTest, RemovePredecessorReplaceUsesOfPhiWith3Inputs) {
StringRef ModuleString = R"(
define i32 @f(i1 %cmp, i8 *%call) {
entry:
br i1 %cmp, label %phi.bb, label %ret.bb
phi.bb:
%ptr.1 = phi i8* [ %call, %entry],[ %inc.ptr1, %use.bb ],[ %inc.ptr1, %exit.bb ]
br label %use.bb
use.bb:
%inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
br i1 %cmp, label %exit.bb, label %phi.bb
exit.bb:
br label %phi.bb
ret.bb:
ret i32 0
})";
LLVMContext Context;
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
Function *F = M->getFunction("f");
Function::iterator FI = F->begin();
BasicBlock *EntryBB = &*FI++;
BasicBlock *PhiBB = &*FI++;
BasicBlock *UseBB = &*FI++;
{
checkFunctionIsValid(*F);
EXPECT_EQ(PhiBB->size(), 2u);
PHINode *PN = dyn_cast<PHINode>(PhiBB->begin());
ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
EXPECT_EQ(PN->getNumIncomingValues(), 3u);
}
PhiBB->removePredecessor(EntryBB);
{
// Input value %inc.ptr1 was propagated into all it's uses.
// Now SSA form is broken.
checkFunctionIsNotValid(*F);
EXPECT_EQ(PhiBB->size(), 1u);
EXPECT_EQ(UseBB->size(), 2u);
GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UseBB->begin());
ASSERT_NE(GEP, nullptr) << "Expecting GEP as a first instruction";
EXPECT_EQ(GEP, GEP->getPointerOperand());
}
}
} // End anonymous namespace. } // End anonymous namespace.
} // End llvm namespace. } // End llvm namespace.