Index: llvm/include/llvm/Transforms/Utils/KnowledgeRetention.h =================================================================== --- llvm/include/llvm/Transforms/Utils/KnowledgeRetention.h +++ llvm/include/llvm/Transforms/Utils/KnowledgeRetention.h @@ -59,6 +59,10 @@ AssumeCI, IsOn, Attribute::getNameFromAttrKind(Kind), ArgVal, AQR); } +/// Check if the assume still holds any information. +/// If this returns false this assume can be dropped without losing anyting. +bool isAssumeWithEmptyBundle(CallInst &Assume); + /// TODO: Add an function to create/fill a map from the bundle when users intend /// to make many different queries on the same bundles. to be used for example /// in the Attributor. Index: llvm/lib/IR/AsmWriter.cpp =================================================================== --- llvm/lib/IR/AsmWriter.cpp +++ llvm/lib/IR/AsmWriter.cpp @@ -2552,6 +2552,10 @@ for (unsigned i = 0, e = Call->getNumOperandBundles(); i != e; ++i) { OperandBundleUse BU = Call->getOperandBundleAt(i); + /// Bundles containing dropped values should be ignored. + if (any_of(BU.Inputs, [](const Use &U) { return !U.get(); })) + continue; + if (!FirstBundle) Out << ", "; FirstBundle = false; Index: llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp =================================================================== --- llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -65,6 +65,7 @@ #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" +#include "llvm/Transforms/Utils/KnowledgeRetention.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/SimplifyLibCalls.h" #include @@ -4119,7 +4120,7 @@ // then this one is redundant, and should be removed. KnownBits Known(1); computeKnownBits(IIOperand, Known, 0, II); - if (Known.isAllOnes()) + if (Known.isAllOnes() && isAssumeWithEmptyBundle(*II)) return eraseInstFromFunction(*II); // Update the cache of affected values for this assumption (we might be Index: llvm/lib/Transforms/InstCombine/InstructionCombining.cpp =================================================================== --- llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ llvm/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -3271,7 +3271,7 @@ /// instruction past all of the instructions between it and the end of its /// block. static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) { - assert(I->hasOneUse() && "Invariants didn't hold!"); + assert(I->getSingleUndroppableUse() && "Invariants didn't hold!"); BasicBlock *SrcBlock = I->getParent(); // Cannot move control-flow-involving, volatile loads, vaarg, etc. @@ -3304,6 +3304,15 @@ if (Scan->mayWriteToMemory()) return false; } + + I->dropDroppableUses([DestBlock](const Use *U) { + if (auto *I = dyn_cast(U->getUser())) + return I->getParent() != DestBlock; + return true; + }); + /// FIXME: We could remove droppable uses that are not dominated by + /// the new position. + BasicBlock::iterator InsertPos = DestBlock->getFirstInsertionPt(); I->moveBefore(&*InsertPos); ++NumSunkInst; @@ -3413,44 +3422,46 @@ } // See if we can trivially sink this instruction to a successor basic block. - if (EnableCodeSinking && I->hasOneUse()) { - BasicBlock *BB = I->getParent(); - Instruction *UserInst = cast(*I->user_begin()); - BasicBlock *UserParent; - - // Get the block the use occurs in. - if (PHINode *PN = dyn_cast(UserInst)) - UserParent = PN->getIncomingBlock(*I->use_begin()); - else - UserParent = UserInst->getParent(); - - if (UserParent != BB) { - bool UserIsSuccessor = false; - // See if the user is one of our successors. - for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) - if (*SI == UserParent) { - UserIsSuccessor = true; - break; - } + if (EnableCodeSinking) + if (Use *SingleUse = I->getSingleUndroppableUse()) { + BasicBlock *BB = I->getParent(); + Instruction *UserInst = cast(SingleUse->getUser()); + BasicBlock *UserParent; + + // Get the block the use occurs in. + if (PHINode *PN = dyn_cast(UserInst)) + UserParent = PN->getIncomingBlock(*I->use_begin()); + else + UserParent = UserInst->getParent(); + + if (UserParent != BB) { + bool UserIsSuccessor = false; + // See if the user is one of our successors. + for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; + ++SI) + if (*SI == UserParent) { + UserIsSuccessor = true; + break; + } - // If the user is one of our immediate successors, and if that successor - // only has us as a predecessors (we'd have to split the critical edge - // otherwise), we can keep going. - if (UserIsSuccessor && UserParent->getUniquePredecessor()) { - // Okay, the CFG is simple enough, try to sink this instruction. - if (TryToSinkInstruction(I, UserParent)) { - LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n'); - MadeIRChange = true; - // We'll add uses of the sunk instruction below, but since sinking - // can expose opportunities for it's *operands* add them to the - // worklist - for (Use &U : I->operands()) - if (Instruction *OpI = dyn_cast(U.get())) - Worklist.Add(OpI); + // If the user is one of our immediate successors, and if that + // successor only has us as a predecessors (we'd have to split the + // critical edge otherwise), we can keep going. + if (UserIsSuccessor && UserParent->getUniquePredecessor()) { + // Okay, the CFG is simple enough, try to sink this instruction. + if (TryToSinkInstruction(I, UserParent)) { + LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n'); + MadeIRChange = true; + // We'll add uses of the sunk instruction below, but since sinking + // can expose opportunities for it's *operands* add them to the + // worklist + for (Use &U : I->operands()) + if (Instruction *OpI = dyn_cast(U.get())) + Worklist.Add(OpI); + } } } } - } // Now that we have an instruction, try combining it to simplify it. Builder.SetInsertPoint(I); Index: llvm/lib/Transforms/Utils/KnowledgeRetention.cpp =================================================================== --- llvm/lib/Transforms/Utils/KnowledgeRetention.cpp +++ llvm/lib/Transforms/Utils/KnowledgeRetention.cpp @@ -167,6 +167,13 @@ return Builder.build(); } +Value *getElemFromBundleOpInfo(CallInst &Assume, + const CallBase::BundleOpInfo &BOI, + unsigned Idx) { + assert(BOI.End - BOI.Begin >= Idx && "index out of range"); + return (Assume.op_begin() + BOI.Begin + Idx)->get(); +}; + #ifndef NDEBUG static bool isExistingAttribute(StringRef Name) { @@ -194,12 +201,6 @@ if (Assume.bundle_op_infos().empty()) return false; - auto getElemFromBundleOpInfo = [&Assume](const CallBase::BundleOpInfo &BOI, - unsigned Idx) { - assert(BOI.End - BOI.Begin >= Idx && "index out of range"); - return (Assume.op_begin() + BOI.Begin + Idx)->get(); - }; - CallInst::bundle_op_iterator Lookup; /// The right attribute can be found by binary search. After this finding the @@ -233,7 +234,7 @@ if (Lookup == Assume.bundle_op_info_end() || Lookup->Tag->getKey() != AttrName) return false; - if (getElemFromBundleOpInfo(*Lookup, BOIE_WasOn) == IsOn) + if (getElemFromBundleOpInfo(Assume, *Lookup, BOIE_WasOn) == IsOn) break; if (AQR == AssumeQuery::Highest && Lookup == Assume.bundle_op_info_begin()) @@ -245,11 +246,23 @@ if (Lookup->End - Lookup->Begin < BOIE_Argument) return true; if (ArgVal) - *ArgVal = cast(getElemFromBundleOpInfo(*Lookup, BOIE_Argument)) + *ArgVal = cast( + getElemFromBundleOpInfo(Assume, *Lookup, BOIE_Argument)) ->getZExtValue(); return true; } +bool llvm::isAssumeWithEmptyBundle(CallInst &CI) { + IntrinsicInst &Assume = cast(CI); + assert(Assume.getIntrinsicID() == Intrinsic::assume && + "this function is intended to be used on llvm.assume"); + return none_of( + Assume.bundle_op_infos(), [&Assume](const CallBase::BundleOpInfo &BOI) { + return BOI.Begin == BOI.End || + getElemFromBundleOpInfo(Assume, BOI, BOIE_WasOn) != nullptr; + }); +} + PreservedAnalyses AssumeBuilderPass::run(Function &F, FunctionAnalysisManager &AM) { for (Instruction &I : instructions(F)) Index: llvm/lib/Transforms/Utils/Local.cpp =================================================================== --- llvm/lib/Transforms/Utils/Local.cpp +++ llvm/lib/Transforms/Utils/Local.cpp @@ -75,6 +75,7 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/KnownBits.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/KnowledgeRetention.h" #include "llvm/Transforms/Utils/ValueMapper.h" #include #include @@ -410,7 +411,8 @@ // true are operationally no-ops. In the future we can consider more // sophisticated tradeoffs for guards considering potential for check // widening, but for now we keep things simple. - if (II->getIntrinsicID() == Intrinsic::assume || + if ((II->getIntrinsicID() == Intrinsic::assume && + isAssumeWithEmptyBundle(*II)) || II->getIntrinsicID() == Intrinsic::experimental_guard) { if (ConstantInt *Cond = dyn_cast(II->getArgOperand(0))) return !Cond->isZero(); Index: llvm/test/Transforms/InstCombine/assume.ll =================================================================== --- llvm/test/Transforms/InstCombine/assume.ll +++ llvm/test/Transforms/InstCombine/assume.ll @@ -269,9 +269,9 @@ ; CHECK-LABEL: @nonnull3( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[LOAD:%.*]] = load i32*, i32** [[A:%.*]], align 8 +; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32* [[LOAD]], null ; CHECK-NEXT: br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]] ; CHECK: taken: -; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32* [[LOAD]], null ; CHECK-NEXT: tail call void @llvm.assume(i1 [[CMP]]) ; CHECK-NEXT: ret i1 false ; CHECK: not_taken: @@ -398,6 +398,56 @@ ret i32 %t2 } +define i1 @nonnull3A(i32** %a, i1 %control) { +; CHECK-LABEL: @nonnull3A( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[LOAD:%.*]] = load i32*, i32** [[A:%.*]], align 8 +; CHECK-NEXT: br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]] +; CHECK: taken: +; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32* [[LOAD]], null +; CHECK-NEXT: tail call void @llvm.assume(i1 [[CMP]]) +; CHECK-NEXT: ret i1 true +; CHECK: not_taken: +; CHECK-NEXT: [[RVAL_2:%.*]] = icmp sgt i32* [[LOAD]], null +; CHECK-NEXT: ret i1 [[RVAL_2]] +; +entry: + %load = load i32*, i32** %a + %cmp = icmp ne i32* %load, null + br i1 %control, label %taken, label %not_taken +taken: + tail call void @llvm.assume(i1 %cmp) + ret i1 %cmp +not_taken: + tail call void @llvm.assume(i1 %cmp) + %rval.2 = icmp sgt i32* %load, null + ret i1 %rval.2 +} + +define i1 @nonnull3B(i32** %a, i1 %control) { +; CHECK-LABEL: @nonnull3B( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[CONTROL:%.*]], label [[TAKEN:%.*]], label [[NOT_TAKEN:%.*]] +; CHECK: taken: +; CHECK-NEXT: [[LOAD:%.*]] = load i32*, i32** [[A:%.*]], align 8 +; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32* [[LOAD]], null +; CHECK-NEXT: tail call void @llvm.assume(i1 true) [ "nonnull"(i32* [[LOAD]]) ] +; CHECK-NEXT: ret i1 [[CMP]] +; CHECK: not_taken: +; CHECK-NEXT: ret i1 [[CONTROL]] +; +entry: + %load = load i32*, i32** %a + %cmp = icmp ne i32* %load, null + br i1 %control, label %taken, label %not_taken +taken: + tail call void @llvm.assume(i1 true) ["nonnull"(i32* %load)] + ret i1 %cmp +not_taken: + tail call void @llvm.assume(i1 %cmp) + ret i1 %control +} + declare void @llvm.dbg.value(metadata, metadata, metadata) !llvm.dbg.cu = !{!0} Index: llvm/unittests/Transforms/Utils/KnowledgeRetentionTest.cpp =================================================================== --- llvm/unittests/Transforms/Utils/KnowledgeRetentionTest.cpp +++ llvm/unittests/Transforms/Utils/KnowledgeRetentionTest.cpp @@ -190,7 +190,32 @@ Attribute::AttrKind::Dereferenceable, 12, true); })); - /// Keep this test last as it modifies the function. + /// The tests below modify the code keep them last to not interfere with + /// others. + Tests.push_back(std::make_pair( + "call void @func(i32* nonnull align 4 dereferenceable(16) %P, i32* align " + "8 noalias %P1)\n", + [](Instruction *I) { + CallInst *Assume = BuildAssumeFromInst(I); + Assume->insertBefore(I); + Value *Val = I->getOperand(0); + AssertMatchesExactlyAttributes(Assume, Val, + "(nonnull|align|dereferenceable)"); + AssertMatchesExactlyAttributes(Assume, I->getOperand(1), + "(noalias|align)"); + + Val->dropDroppableUses(); + AssertMatchesExactlyAttributes(Assume, Val, ""); + AssertMatchesExactlyAttributes(Assume, I->getOperand(1), + "(noalias|align)"); + })); + Tests.push_back( + std::make_pair("%in_assume = icmp ne i32* %P, null\n", [](Instruction *I) {})); + Tests.push_back( + std::make_pair("call void @llvm.assume(i1 %in_assume)\n", [](Instruction *I) { + I->getOperand(0)->dropDroppableUses(); + ASSERT_EQ(I->getOperand(0), ConstantInt::getTrue(I->getContext())); + })); Tests.push_back(std::make_pair( "call void @func(i32* nonnull align 4 dereferenceable(16) %P, i32* align " "8 noalias %P1)\n", @@ -202,10 +227,14 @@ AssertMatchesExactlyAttributes(Assume, New, ""); AssertMatchesExactlyAttributes(Assume, Old, "(nonnull|align|dereferenceable)"); + AssertMatchesExactlyAttributes(Assume, I->getOperand(1), + "(noalias|align)"); Old->replaceAllUsesWith(New); AssertMatchesExactlyAttributes(Assume, New, "(nonnull|align|dereferenceable)"); AssertMatchesExactlyAttributes(Assume, Old, ""); + AssertMatchesExactlyAttributes(Assume, I->getOperand(1), + "(noalias|align)"); })); RunTest(Head, Tail, Tests); }