Index: llvm/lib/CodeGen/CodeGenPrepare.cpp =================================================================== --- llvm/lib/CodeGen/CodeGenPrepare.cpp +++ llvm/lib/CodeGen/CodeGenPrepare.cpp @@ -378,7 +378,6 @@ } void removeAllAssertingVHReferences(Value *V); - bool eliminateAssumptions(Function &F); bool eliminateFallThrough(Function &F); bool eliminateMostlyEmptyBlocks(Function &F); BasicBlock *findDestBlockOfMergeableEmptyBlock(BasicBlock *BB); @@ -509,11 +508,6 @@ } } - // Get rid of @llvm.assume builtins before attempting to eliminate empty - // blocks, since there might be blocks that only contain @llvm.assume calls - // (plus arguments that we can get rid of). - EverMadeChange |= eliminateAssumptions(F); - // Eliminate blocks that contain only PHI nodes and an // unconditional branch. EverMadeChange |= eliminateMostlyEmptyBlocks(F); @@ -623,26 +617,6 @@ return EverMadeChange; } -bool CodeGenPrepare::eliminateAssumptions(Function &F) { - bool MadeChange = false; - for (BasicBlock &BB : F) { - CurInstIterator = BB.begin(); - while (CurInstIterator != BB.end()) { - Instruction *I = &*(CurInstIterator++); - if (auto *Assume = dyn_cast(I)) { - MadeChange = true; - Value *Operand = Assume->getOperand(0); - Assume->eraseFromParent(); - - resetIteratorIfInvalidatedWhileCalling(&BB, [&]() { - RecursivelyDeleteTriviallyDeadInstructions(Operand, TLInfo, nullptr); - }); - } - } - } - return MadeChange; -} - /// An instruction is about to be deleted, so remove all references to it in our /// GEP-tracking data strcutures. void CodeGenPrepare::removeAllAssertingVHReferences(Value *V) { @@ -2166,8 +2140,6 @@ if (II) { switch (II->getIntrinsicID()) { default: break; - case Intrinsic::assume: - llvm_unreachable("llvm.assume should have been removed already"); case Intrinsic::experimental_widenable_condition: { // Give up on future widening oppurtunties so that we can fold away dead // paths and merge blocks before going into block-local instruction Index: llvm/lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -6707,6 +6707,81 @@ return false; } +/// Hoist @llvm.assume and inputs of BB into the single predecessor Pred if they +/// are the only non-terminator instructions in BB. When hoisted the original +/// assumption %X needs to be weakened to include the possibility that the +/// branch was not taken. That is with branch condition %Y in Pred the new +/// assumption becomes (!%Y | %X) if BB is the true-target of Pred and (%Y | %X) +/// if BB is the false-target of Pred. Since 'Assume Operand Bundles' are not +/// easily transformed in this way they are simply dropped. +static bool hoistAssumptions(BasicBlock *BB) { + auto *Pred = BB->getSinglePredecessor(); + if (!Pred) + return false; + + SetVector Candidates; + + for (auto It = BB->rbegin(), E = BB->rend(); It != E; ++It) { + auto I = &(*It); + // Skip the terminator. + if (I->isTerminator()) + continue; + + // Bail if side-effects. + if (I->mayHaveSideEffects() && !isa(I)) + return false; + + // Insert into Candidates either if instruction is a @llvm.assume or if all + // uses of the instruction are covered by the Candidates set. Otherwise + // bail. + if (isa(I)) + Candidates.insert(I); + else if (!empty(I->users()) && all_of(I->users(), [&](User *U) { + return isa(U) + ? Candidates.count(cast(U)) + : false; + })) + Candidates.insert(I); + else + return false; + } + + if (!Candidates.size()) + return false; + + // If we reach this point BB contains only @llvm.assume instructions and + // their input. Hoist into Pred. + + auto *PredBranch = dyn_cast(Pred->getTerminator()); + if (!PredBranch || PredBranch->isUnconditional()) + return false; + + // Now move Candidates into Pred. When we get to a @llvm.assume update the + // assume condition to depend on PredBranch->getCondition(). + Module *M = BB->getParent()->getParent(); + IRBuilder<> IRB(M->getContext()); + IRB.SetInsertPoint(PredBranch); + + Value *Cond = PredBranch->getCondition(); + auto *PredTrueSucc = PredBranch->getSuccessor(0); + if (BB == PredTrueSucc) + Cond = IRB.CreateNot(Cond); + + for (auto It = Candidates.rbegin(), E = Candidates.rend(); It != E; ++It) { + if (auto *Assume = dyn_cast(*It)) { + auto *OrCond = IRB.CreateOr(Cond, Assume->getOperand(0)); + // Note that any Operand Bundle is dropped at this point. + IRB.CreateAssumption(OrCond); + Assume->eraseFromParent(); + } else { + auto *I = *It; + I->moveBefore(PredBranch); + } + } + + return true; +} + bool SimplifyCFGOpt::simplifyOnceImpl(BasicBlock *BB) { bool Changed = false; @@ -6739,6 +6814,10 @@ if (MergeBlockIntoPredecessor(BB, DTU)) return true; + // Hoist @llvm.assumes if they (and their inputs) are the only contents of + // the block. + Changed |= hoistAssumptions(BB); + if (SinkCommon && Options.SinkCommonInsts) Changed |= SinkCommonCodeFromPredecessors(BB, DTU); Index: llvm/test/Transforms/CodeGenPrepare/X86/delete-assume-dead-code.ll =================================================================== --- llvm/test/Transforms/CodeGenPrepare/X86/delete-assume-dead-code.ll +++ /dev/null @@ -1,30 +0,0 @@ -; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -codegenprepare -S -mtriple=x86_64-linux < %s | FileCheck %s - -define i32 @test1(i8* %d) nounwind { -; CHECK-LABEL: @test1( -; CHECK-NEXT: entry: -; CHECK-NEXT: [[L:%.*]] = load i8, i8* [[D:%.*]], align 1 -; CHECK-NEXT: [[TMP0:%.*]] = icmp eq i8 [[L]], 0 -; CHECK-NEXT: [[CONV:%.*]] = zext i1 [[TMP0]] to i32 -; CHECK-NEXT: ret i32 [[CONV]] -; -entry: - %l = load i8, i8* %d - %cmp = icmp eq i8 %l, 0 - br i1 %cmp, label %exit, label %if.end - -if.end: - %gep = getelementptr i8, i8* %d, i32 42 - %call = call i64 @foo(i8* %gep) nounwind readonly willreturn - %cmp2 = icmp ne i64 %call, 0 - call void @llvm.assume(i1 %cmp2) - br label %exit - -exit: - %conv = zext i1 %cmp to i32 - ret i32 %conv -} - -declare i64 @foo(i8*) nounwind readonly willreturn -declare void @llvm.assume(i1 noundef) nounwind willreturn Index: llvm/test/Transforms/CodeGenPrepare/X86/recursively-delete-dead-instructions.ll =================================================================== --- llvm/test/Transforms/CodeGenPrepare/X86/recursively-delete-dead-instructions.ll +++ /dev/null @@ -1,27 +0,0 @@ -; RUN: opt -codegenprepare -S -mtriple=x86_64-linux < %s | FileCheck %s - -declare void @llvm.assume(i1 noundef) nounwind willreturn - -; Recursively deleting dead operands of assume() may result in its next -; instruction deleted and the iterator pointing to the next instruction -; invalidated. This prevents the following simple loop in -; CodeGenPrepare::optimizeBlock() unless CurInstIterator is fixed: -; -; CurInstIterator = BB.begin(); -; while (CurInstIterator != BB.end()) -; optimizeInst(&*CurInstIterator++, ModifiedDT); -; -define i32 @test_assume_in_loop(i1 %cond1, i1 %cond2) { -; CHECK-LABEL: @test_assume_in_loop( -; CHECK-NEXT: entry: -entry: - br label %loop - -; CHECK: loop: -; CHECK-NEXT: br label %loop -loop: - %cond3 = phi i1 [%cond1, %entry], [%cond4, %loop] - call void @llvm.assume(i1 %cond3) - %cond4 = icmp ult i1 %cond1, %cond2 - br label %loop -} Index: llvm/test/Transforms/CodeGenPrepare/X86/remove-assume-block.ll =================================================================== --- llvm/test/Transforms/CodeGenPrepare/X86/remove-assume-block.ll +++ /dev/null @@ -1,46 +0,0 @@ -; RUN: opt -S -codegenprepare -mtriple=x86_64-linux < %s | FileCheck %s -; -; Ensure that blocks that only contain @llvm.assume are removed completely -; during CodeGenPrepare. - -; CHECK-LABEL: @simple( -; CHECK-NEXT: end: -; CHECK-NEXT: ret void -define void @simple(i64 %addr, i1 %assumption) { - %cmp1 = icmp eq i64 %addr, 0 - br i1 %cmp1, label %do_assume, label %end - -do_assume: - tail call void @llvm.assume(i1 %assumption) - br label %end - -end: - ret void -} - -; CHECK-LABEL: @complex_assume( -; CHECK-NEXT: end: -; CHECK-NEXT: ret void -define void @complex_assume(i64 %addr, i1 %assumption_a, i1 %assumption_b, - i64 %val_a, i64 %val_b) { - %cmp1 = icmp eq i64 %addr, 0 - br i1 %cmp1, label %do_assume, label %end - -do_assume: - call void @llvm.assume(i1 %assumption_a) - call void @llvm.assume(i1 %assumption_b) - %val_xor = xor i64 %val_a, %val_b - %val_shifted = lshr i64 %val_xor, 7 - %assumption_c = trunc i64 %val_shifted to i1 - call void @llvm.assume(i1 %assumption_c) - %assumption_d = call i1 @readonly_func(i64 %val_b) - call void @llvm.assume(i1 %assumption_d) - br label %end - -end: - ret void -} - -declare void @llvm.assume(i1 noundef) -declare i1 @readonly_func(i64) nounwind readonly willreturn; - Index: llvm/test/Transforms/CodeGenPrepare/X86/tailcall-assume-xbb.ll =================================================================== --- llvm/test/Transforms/CodeGenPrepare/X86/tailcall-assume-xbb.ll +++ /dev/null @@ -1,53 +0,0 @@ -; RUN: opt -codegenprepare -S -mtriple=x86_64-linux < %s | FileCheck %s - -; The ret instruction can be duplicated into BB case2 even though there is an -; intermediate BB exit1 and call to llvm.assume. - -@ptr = external global i8*, align 8 - -; CHECK: %ret1 = tail call i8* @qux() -; CHECK-NEXT: ret i8* %ret1 - -; CHECK: %ret2 = tail call i8* @bar() -; CHECK-NEXT: ret i8* %ret2 - -define i8* @foo(i64 %size, i64 %v1, i64 %v2) { -entry: - %a = alloca i8 - call void @llvm.lifetime.start.p0i8(i64 -1, i8* %a) nounwind - %cmp1 = icmp ult i64 %size, 1025 - br i1 %cmp1, label %if.end, label %case1 - -case1: - %ret1 = tail call i8* @qux() - br label %exit2 - -if.end: - %cmp2 = icmp ult i64 %v1, %v2 - br i1 %cmp2, label %case3, label %case2 - -case2: - %ret2 = tail call i8* @bar() - br label %exit1 - -case3: - %ret3 = load i8*, i8** @ptr, align 8 - br label %exit1 - -exit1: - %retval1 = phi i8* [ %ret2, %case2 ], [ %ret3, %case3 ] - %cmp3 = icmp ne i8* %retval1, null - tail call void @llvm.assume(i1 %cmp3) - br label %exit2 - -exit2: - %retval2 = phi i8* [ %ret1, %case1 ], [ %retval1, %exit1 ] - call void @llvm.lifetime.end.p0i8(i64 -1, i8* %a) nounwind - ret i8* %retval2 -} - -declare void @llvm.assume(i1) -declare i8* @qux() -declare i8* @bar() -declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) nounwind -declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) nounwind Index: llvm/test/Transforms/InstCombine/assume-align.ll =================================================================== --- llvm/test/Transforms/InstCombine/assume-align.ll +++ llvm/test/Transforms/InstCombine/assume-align.ll @@ -10,11 +10,13 @@ ; CHECK-NEXT: [[TMP0:%.*]] = ptrtoint i8* [[PTR]] to i64 ; CHECK-NEXT: [[TMP1:%.*]] = and i64 [[TMP0]], 3 ; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i64 [[TMP1]], 0 -; CHECK-NEXT: br i1 [[TMP2]], label [[IF_THEN:%.*]], label [[IF_END:%.*]] -; CHECK: if.then: -; CHECK-NEXT: call void @llvm.assume(i1 true) [ "align"(i8* [[PTR]], i64 4) ] -; CHECK-NEXT: [[TMP3:%.*]] = bitcast i8* [[PTR]] to i32* -; CHECK-NEXT: store i32 4, i32* [[TMP3]], align 4 +; CHECK-NEXT: [[TMP3:%.*]] = xor i1 [[TMP2]], true +; CHECK-NEXT: [[TMP4:%.*]] = or i1 [[TMP3]], true +; CHECK-NEXT: call void @llvm.assume(i1 [[TMP4]]) +; CHECK-NEXT: br i1 [[TMP2]], label [[IF_THEN1:%.*]], label [[IF_END:%.*]] +; CHECK: if.then1: +; CHECK-NEXT: [[TMP5:%.*]] = bitcast i8* [[PTR]] to i32* +; CHECK-NEXT: store i32 4, i32* [[TMP5]], align 4 ; CHECK-NEXT: br label [[IF_END]] ; CHECK: if.end: ; CHECK-NEXT: ret void