diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -1012,18 +1012,19 @@ /// present in \p Opcode and return true if \p Pred holds on all of them. bool checkForAllInstructions(const function_ref &Pred, const AbstractAttribute &QueryingAA, - const ArrayRef &Opcodes); + const ArrayRef &Opcodes, + bool CheckInstSeparately = false); /// Check \p Pred on all call-like instructions (=CallBased derived). /// /// See checkForAllCallLikeInstructions(...) for more information. bool checkForAllCallLikeInstructions(const function_ref &Pred, - const AbstractAttribute &QueryingAA) { - return checkForAllInstructions(Pred, QueryingAA, - {(unsigned)Instruction::Invoke, - (unsigned)Instruction::CallBr, - (unsigned)Instruction::Call}); + const AbstractAttribute &QueryingAA, + bool CheckInstSeparately = false) { + auto Opcodes = {(unsigned)Instruction::Invoke, + (unsigned)Instruction::CallBr, (unsigned)Instruction::Call}; + return checkForAllInstructions(Pred, QueryingAA, Opcodes, CheckInstSeparately); } /// Check \p Pred on all Read/Write instructions. @@ -1965,6 +1966,15 @@ /// Returns true if \p I is assumed dead. virtual bool isAssumedDead(const Instruction *I) const = 0; + /// Returns true if \p I is assumed dead. + /// \p CheckInstSeparately indicates that \p I will be checked whether it is + /// due to be deleted. Currently only mallocs and frees from H2S are + /// considered. + virtual bool isAssumedDead(const Instruction *I, + bool CheckInstSeparately) const { + return false; + } + /// Returns true if \p I is known dead. virtual bool isKnownDead(const Instruction *I) const = 0; @@ -2262,6 +2272,12 @@ /// Returns true if HeapToStack conversion is known to be possible. bool isKnownHeapToStack() const { return getKnown(); } + /// Returns all mallocs that will be deleted. + virtual SmallSetVector removableMallocs() const; + + /// Returns all frees associated with malloc call. + virtual SmallPtrSet freesForMalloc(Instruction *Malloc) const; + /// Return an IR position, see struct IRPosition. const IRPosition &getIRPosition() const { return *this; } diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -1566,7 +1566,8 @@ return NoFreeAA.isAssumedNoFree(); }; - if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this)) + if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this, + /* CheckInstSeparately */ true)) return indicatePessimisticFixpoint(); return ChangeStatus::UNCHANGED; } @@ -2188,6 +2189,7 @@ if (!SimplifiedV.hasValue()) { // If it is known (which we tested above) but it doesn't have a value, // then we can assume `undef` and hence the instruction is UB. + KnownUBInsts.insert(I); return llvm::None; } @@ -2944,14 +2946,25 @@ /// See AAIsDead::isAssumed(Instruction *I). bool isAssumedDead(const Instruction *I) const override { + return isAssumedDead(I, /* CheckInstSeparately */ false); + } + + bool isAssumedDead(const Instruction *I, + bool CheckInstSeparately) const override { assert(I->getParent()->getParent() == getAssociatedFunction() && "Instruction must be in the same anchor scope function."); if (!getAssumed()) return false; + // While a BB can be live, there can still exist dead instructions inside of + // it. + if (CheckInstSeparately && AssumedDeadInstructions.count(I)) + return true; + // If it is not in AssumedLiveBlocks then it for sure dead. - // Otherwise, it can still be after noreturn call in a live block. + // Otherwise, it can still be after noreturn call in a live block, + // or 'to be deleted' instruction in a live block. if (!AssumedLiveBlocks.count(I->getParent())) return true; @@ -2993,6 +3006,11 @@ return true; } + /// Assume \p I is dead. + bool assumeDead(const Instruction *I) { + return AssumedDeadInstructions.insert(I); + } + /// Collection of instructions that need to be explored again, e.g., we /// did assume they do not transfer control to (one of their) successors. SmallSetVector ToBeExploredFrom; @@ -3002,6 +3020,11 @@ /// Collection of all assumed live BasicBlocks. DenseSet AssumedLiveBlocks; + + /// Collection od Instructions that are assumed dead. Since liveness works on + /// basic blocks and we also delete stuff elsewhere, we need a way to check if + /// only one instruction inside a BB is dead (to be deleted). + SmallSetVector AssumedDeadInstructions; }; static bool @@ -3185,6 +3208,25 @@ ToBeExploredFrom = std::move(NewToBeExploredFrom); + const IRPosition &IRPFunction = + IRPosition::function(*getAssociatedFunction()); + + // Check for any mallocs/frees that will be deleted (dead). + const auto &HeapToStackAA = A.getAAFor( + *this, IRPFunction, /* TrackDepencence */ false); + + if (HeapToStackAA.getAssumed()) { + for (Instruction *Malloc : HeapToStackAA.removableMallocs()) { + if (!assumeDead(Malloc)) + continue; + // Record dependence only if candidate malloc exists. + A.recordDependence(HeapToStackAA, *this, DepClassTy::OPTIONAL); + Change = ChangeStatus::CHANGED; + for (Instruction *FreeCall : HeapToStackAA.freesForMalloc(Malloc)) + assumeDead(FreeCall); + } + } + // If we know everything is live there is no need to query for liveness. // Instead, indicating a pessimistic fixpoint will cause the state to be // "invalid" and all queries to be answered conservatively without lookups. @@ -3195,8 +3237,12 @@ getAssociatedFunction()->size() == AssumedLiveBlocks.size() && llvm::all_of(KnownDeadEnds, [](const Instruction *DeadEndI) { return DeadEndI->isTerminator() && DeadEndI->getNumSuccessors() == 0; - })) - return indicatePessimisticFixpoint(); + })) { + if (AssumedDeadInstructions.empty()) + return indicatePessimisticFixpoint(); + else + return indicateOptimisticFixpoint(); + } return Change; } @@ -4535,6 +4581,17 @@ /// A map for each malloc call to the set of associated free calls. DenseMap> FreesForMalloc; + /// Returns all mallocs that will be removed. + SmallSetVector removableMallocs() const override { + return MallocCalls; + } + + /// Returns all frees associated with malloc call. + SmallPtrSet + freesForMalloc(Instruction *Malloc) const override { + return FreesForMalloc.lookup(Malloc); + } + ChangeStatus updateImpl(Attributor &A) override; }; @@ -5368,11 +5425,12 @@ checkForAllInstructionsImpl(InformationCache::OpcodeInstMapTy &OpcodeInstMap, const function_ref &Pred, const AAIsDead *LivenessAA, bool &AnyDead, - const ArrayRef &Opcodes) { + const ArrayRef &Opcodes, + bool CheckInstSeparately = false) { for (unsigned Opcode : Opcodes) { for (Instruction *I : OpcodeInstMap[Opcode]) { // Skip dead instructions. - if (LivenessAA && LivenessAA->isAssumedDead(I)) { + if (LivenessAA && LivenessAA->isAssumedDead(I, CheckInstSeparately)) { AnyDead = true; continue; } @@ -5386,7 +5444,8 @@ bool Attributor::checkForAllInstructions( const llvm::function_ref &Pred, - const AbstractAttribute &QueryingAA, const ArrayRef &Opcodes) { + const AbstractAttribute &QueryingAA, const ArrayRef &Opcodes, + bool CheckInstSeparately) { const IRPosition &IRP = QueryingAA.getIRPosition(); // Since we need to provide instructions we have to have an exact definition. @@ -5403,7 +5462,7 @@ auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(*AssociatedFunction); if (!checkForAllInstructionsImpl(OpcodeInstMap, Pred, &LivenessAA, AnyDead, - Opcodes)) + Opcodes, CheckInstSeparately)) return false; // If we actually used liveness information so we have to record a dependence. diff --git a/llvm/test/Transforms/Attributor/heap_to_stack.ll b/llvm/test/Transforms/Attributor/heap_to_stack.ll --- a/llvm/test/Transforms/Attributor/heap_to_stack.ll +++ b/llvm/test/Transforms/Attributor/heap_to_stack.ll @@ -56,6 +56,8 @@ ; TEST 3 - 1 malloc, 1 free +; CHECK: Function Attrs: nofree +; CHECK-NEXT: define void @test3() define void @test3() { %1 = tail call noalias i8* @malloc(i64 4) ; CHECK: %1 = alloca i8, i64 4 @@ -78,6 +80,8 @@ declare noalias i8* @calloc(i64, i64) +; CHECK: Function Attrs: nofree +; CHECK-NEXT: define void @test0() define void @test0() { %1 = tail call noalias i8* @calloc(i64 2, i64 4) ; CHECK: %1 = alloca i8, i64 8 @@ -91,6 +95,9 @@ } ; TEST 4 + +; CHECK: Function Attrs: nofree +; CHECK-NEXT: define void @test4() define void @test4() { %1 = tail call noalias i8* @malloc(i64 4) ; CHECK: %1 = alloca i8, i64 4 @@ -125,6 +132,8 @@ ; TEST 6 - all exit paths have a call to free +; CHECK: Function Attrs: nofree +; CHECK-NEXT: define void @test6 define void @test6(i32) { %2 = tail call noalias i8* @malloc(i64 4) ; CHECK: %2 = alloca i8, i64 4 @@ -192,6 +201,8 @@ ; TEST 10 - 1 malloc, 1 free +; CHECK: Function Attrs: nofree +; CHECK-NEXT: define i32 @test10() define i32 @test10() { %1 = tail call noalias i8* @malloc(i64 4) ; CHECK: %1 = alloca i8, i64 4 @@ -357,6 +368,8 @@ ret void } +; CHECK: Function Attrs: nofree +; CHECK-NEXT: define void @test16a define void @test16a(i8 %v, i8** %P) { ; CHECK: %1 = alloca %1 = tail call noalias i8* @malloc(i64 4) @@ -381,6 +394,8 @@ ret void } +; CHECK: Function Attrs: nofree +; CHECK-NEXT: define void @test16c define void @test16c(i8 %v, i8** %P) { ; CHECK: %1 = alloca %1 = tail call noalias i8* @malloc(i64 4)