From 01ec0ff2dcf5528b0e6728e5693b583e4e6f83f1 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Thu, 3 Nov 2022 14:13:08 +0100 Subject: [PATCH] [SimplifyCFG] Allow speculating block containing assume() SpeculativelyExecuteBB(), which converts a branch + phi structure into a select, currently bails out if the block contains an assume (because it is not speculatable). Adjust the fold to ignore ephemeral values (i.e. assumes and values only used in assumes) for cost modelling purposes, and drop them when performing the fold. Theoretically, we could try to preserve the assume information by generating a assume(br_cond || assume_cond) style assume, but this is very unlikely to to be useful (because we don't do anything useful with assumes of this form) and it would make things substantially more complicated once we take operand bundle assumes into account (which don't really support a || operation). I'd prefer not to do that without good motivation. Differential Revision: https://reviews.llvm.org/D137339 --- llvm/lib/Transforms/Utils/SimplifyCFG.cpp | 17 +++++++-- llvm/test/CodeGen/ARM/2010-05-18-PostIndexBug.ll | 4 +-- llvm/test/Transforms/SimplifyCFG/assume.ll | 42 ++++++---------------- .../SimplifyCFG/two-entry-phi-fold-crash.ll | 11 ++---- 4 files changed, 30 insertions(+), 44 deletions(-) diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp index 80854e8..ee7f8b2 100644 --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -2658,6 +2658,8 @@ public: } return false; } + + bool contains(const Instruction *I) const { return EphValues.contains(I); } }; } // namespace @@ -2885,7 +2887,8 @@ bool SimplifyCFGOpt::SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, unsigned SpeculatedInstructions = 0; Value *SpeculatedStoreValue = nullptr; StoreInst *SpeculatedStore = nullptr; - for (Instruction &I : drop_end(*ThenBB)) { + EphemeralValueTracker EphTracker; + for (Instruction &I : reverse(drop_end(*ThenBB))) { // Skip debug info. if (isa(I)) { SpeculatedDbgIntrinsics.push_back(&I); @@ -2904,6 +2907,10 @@ bool SimplifyCFGOpt::SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, continue; } + // Ignore ephemeral values, they will be dropped by the transform. + if (EphTracker.track(&I)) + continue; + // Only speculatively execute a single instruction (not counting the // terminator) for now. ++SpeculatedInstructions; @@ -2979,10 +2986,16 @@ bool SimplifyCFGOpt::SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, // be misleading while debugging. // Similarly strip attributes that maybe dependent on condition we are // hoisting above. - for (auto &I : *ThenBB) { + for (auto &I : make_early_inc_range(*ThenBB)) { if (!SpeculatedStoreValue || &I != SpeculatedStore) I.setDebugLoc(DebugLoc()); I.dropUndefImplyingAttrsAndUnknownMetadata(); + + // Drop ephemeral values. + if (EphTracker.contains(&I)) { + I.replaceAllUsesWith(PoisonValue::get(I.getType())); + I.eraseFromParent(); + } } // Hoist the instructions. diff --git a/llvm/test/CodeGen/ARM/2010-05-18-PostIndexBug.ll b/llvm/test/CodeGen/ARM/2010-05-18-PostIndexBug.ll index 24469cc..f0b7141 100644 --- a/llvm/test/CodeGen/ARM/2010-05-18-PostIndexBug.ll +++ b/llvm/test/CodeGen/ARM/2010-05-18-PostIndexBug.ll @@ -1,5 +1,5 @@ -; RUN: llc < %s -mtriple=armv7-apple-darwin | FileCheck %s -check-prefix=ARM -; RUN: llc < %s -mtriple=thumbv7-apple-darwin | FileCheck %s -check-prefix=THUMB +; RUN: llc < %s -mtriple=armv7-apple-darwin -arm-atomic-cfg-tidy=0 | FileCheck %s -check-prefix=ARM +; RUN: llc < %s -mtriple=thumbv7-apple-darwin -arm-atomic-cfg-tidy=0 | FileCheck %s -check-prefix=THUMB ; rdar://7998649 %struct.foo = type { i64, i64 } diff --git a/llvm/test/Transforms/SimplifyCFG/assume.ll b/llvm/test/Transforms/SimplifyCFG/assume.ll index 1091f74..cd41a80 100644 --- a/llvm/test/Transforms/SimplifyCFG/assume.ll +++ b/llvm/test/Transforms/SimplifyCFG/assume.ll @@ -22,14 +22,8 @@ define void @assume_undef_to_unreachable() { define i32 @speculate_block_with_assume_basic(i1 %c, i32 %x) { ; CHECK-LABEL: @speculate_block_with_assume_basic( ; CHECK-NEXT: entry: -; CHECK-NEXT: br i1 [[C:%.*]], label [[IF:%.*]], label [[JOIN:%.*]] -; CHECK: if: -; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32 [[X:%.*]], 0 -; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) -; CHECK-NEXT: br label [[JOIN]] -; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[IF]] ] -; CHECK-NEXT: ret i32 [[PHI]] +; CHECK-NEXT: [[SPEC_SELECT:%.*]] = select i1 [[C:%.*]], i32 1, i32 0 +; CHECK-NEXT: ret i32 [[SPEC_SELECT]] ; entry: br i1 %c, label %if, label %join @@ -47,15 +41,9 @@ join: define i32 @speculate_block_with_assume_extra_instr(i1 %c, i32 %x) { ; CHECK-LABEL: @speculate_block_with_assume_extra_instr( ; CHECK-NEXT: entry: -; CHECK-NEXT: br i1 [[C:%.*]], label [[IF:%.*]], label [[JOIN:%.*]] -; CHECK: if: ; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], 1 -; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32 [[ADD]], 0 -; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) -; CHECK-NEXT: br label [[JOIN]] -; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD]], [[IF]] ] -; CHECK-NEXT: ret i32 [[PHI]] +; CHECK-NEXT: [[SPEC_SELECT:%.*]] = select i1 [[C:%.*]], i32 [[ADD]], i32 0 +; CHECK-NEXT: ret i32 [[SPEC_SELECT]] ; entry: br i1 %c, label %if, label %join @@ -71,6 +59,8 @@ join: ret i32 %phi } +; We only allow speculating one instruction. Here %add and %add2 are used by +; the assume, but not ephemeral, because they are also used by %phi. define i32 @speculate_block_with_assume_extra_instrs_too_many(i1 %c, i32 %x) { ; CHECK-LABEL: @speculate_block_with_assume_extra_instrs_too_many( ; CHECK-NEXT: entry: @@ -103,16 +93,9 @@ join: define i32 @speculate_block_with_assume_extra_instrs_okay(i1 %c, i32 %x) { ; CHECK-LABEL: @speculate_block_with_assume_extra_instrs_okay( ; CHECK-NEXT: entry: -; CHECK-NEXT: br i1 [[C:%.*]], label [[IF:%.*]], label [[JOIN:%.*]] -; CHECK: if: ; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], 1 -; CHECK-NEXT: [[ADD2:%.*]] = add i32 [[ADD]], 1 -; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32 [[ADD2]], 0 -; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) -; CHECK-NEXT: br label [[JOIN]] -; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD]], [[IF]] ] -; CHECK-NEXT: ret i32 [[PHI]] +; CHECK-NEXT: [[SPEC_SELECT:%.*]] = select i1 [[C:%.*]], i32 [[ADD]], i32 0 +; CHECK-NEXT: ret i32 [[SPEC_SELECT]] ; entry: br i1 %c, label %if, label %join @@ -132,13 +115,8 @@ join: define i32 @speculate_block_with_assume_operand_bundle(i1 %c, ptr %p) { ; CHECK-LABEL: @speculate_block_with_assume_operand_bundle( ; CHECK-NEXT: entry: -; CHECK-NEXT: br i1 [[C:%.*]], label [[IF:%.*]], label [[JOIN:%.*]] -; CHECK: if: -; CHECK-NEXT: call void @llvm.assume(i1 true) [ "nonnull"(ptr [[P:%.*]]) ] -; CHECK-NEXT: br label [[JOIN]] -; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[IF]] ] -; CHECK-NEXT: ret i32 [[PHI]] +; CHECK-NEXT: [[SPEC_SELECT:%.*]] = select i1 [[C:%.*]], i32 1, i32 0 +; CHECK-NEXT: ret i32 [[SPEC_SELECT]] ; entry: br i1 %c, label %if, label %join diff --git a/llvm/test/Transforms/SimplifyCFG/two-entry-phi-fold-crash.ll b/llvm/test/Transforms/SimplifyCFG/two-entry-phi-fold-crash.ll index cfad189..2d698d1 100644 --- a/llvm/test/Transforms/SimplifyCFG/two-entry-phi-fold-crash.ll +++ b/llvm/test/Transforms/SimplifyCFG/two-entry-phi-fold-crash.ll @@ -8,16 +8,11 @@ define i32 @wibble(i8* %arg, i8** %arg1) { ; CHECK-NEXT: bb: ; CHECK-NEXT: br label [[BB2:%.*]] ; CHECK: bb2: -; CHECK-NEXT: [[BORG:%.*]] = phi i32 [ 0, [[BB:%.*]] ], [ [[BORG]], [[BB8:%.*]] ] -; CHECK-NEXT: [[BORG3:%.*]] = phi i32 [ 8, [[BB]] ], [ [[BORG10:%.*]], [[BB8]] ] +; CHECK-NEXT: [[BORG:%.*]] = phi i32 [ 0, [[BB:%.*]] ], [ [[BORG]], [[BB2]] ] +; CHECK-NEXT: [[BORG3:%.*]] = phi i32 [ 8, [[BB]] ], [ [[SPEC_SELECT:%.*]], [[BB2]] ] ; CHECK-NEXT: [[BORG4:%.*]] = tail call i32 @blam(i8* [[ARG:%.*]], i32 [[BORG]]) ; CHECK-NEXT: [[BORG5:%.*]] = icmp eq i32 [[BORG4]], 0 -; CHECK-NEXT: br i1 [[BORG5]], label [[BB8]], label [[BB6:%.*]] -; CHECK: bb6: -; CHECK-NEXT: [[BORG7:%.*]] = load i8*, i8** [[ARG1:%.*]], align 4 -; CHECK-NEXT: br label [[BB8]] -; CHECK: bb8: -; CHECK-NEXT: [[BORG10]] = phi i32 [ [[BORG4]], [[BB6]] ], [ [[BORG3]], [[BB2]] ] +; CHECK-NEXT: [[SPEC_SELECT]] = select i1 [[BORG5]], i32 [[BORG3]], i32 [[BORG4]] ; CHECK-NEXT: [[BORG11:%.*]] = icmp ult i32 [[BORG]], 2 ; CHECK-NEXT: br i1 [[BORG11]], label [[BB2]], label [[BB12:%.*]] ; CHECK: bb12: -- 2.7.4