Index: include/llvm/Analysis/AssumptionTracker.h =================================================================== --- /dev/null +++ include/llvm/Analysis/AssumptionTracker.h @@ -0,0 +1,126 @@ +//===- llvm/Analysis/AssumptionTracker.h - Track @llvm.assume ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains a pass that keeps track of @llvm.assume intrinsics in +// the functions of a module. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ASSUMPTIONTRACKER_H +#define LLVM_ANALYSIS_ASSUMPTIONTRACKER_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Pass.h" + +namespace llvm { + +/// An immutable pass that tracks @llvm.assume intrinsics in a module. +class AssumptionTracker : public ImmutablePass { + /// A callback value handle applied to function objects, which we use to + /// delete our cache of intrinsics for a function when it is deleted. + class ATFunctionCallbackVH : public CallbackVH { + AssumptionTracker *AT; + void deleted() override; + + public: + ATFunctionCallbackVH(Value *V, AssumptionTracker *AT = nullptr) + : CallbackVH(V), AT(AT) {} + }; + + /// A callback value handle applied to function objects, which we use to + /// delete our cache of intrinsics for a function when it is deleted. + class ATCallCallbackVH : public CallbackVH { + AssumptionTracker *AT; + void deleted() override; + + // We store the function here because we need it to lookup the set + // containing this handle when the underlying CallInst is being deleted. + Function *F; + + public: + typedef DenseMapInfo DMI; + + ATCallCallbackVH(Instruction *I, AssumptionTracker *AT = nullptr) + : CallbackVH(I), AT(AT), F(nullptr) { + if (I != DMI::getEmptyKey() && I != DMI::getTombstoneKey() && + I->getParent()) + F = I->getParent()->getParent(); + } + + operator CallInst*() const { + Value *V = getValPtr(); + if (V == DMI::getEmptyKey() || V == DMI::getTombstoneKey()) + return static_cast(V); + + return cast(V); + } + + CallInst *operator->() const { return cast(getValPtr()); } + CallInst &operator*() const { return *cast(getValPtr()); } + }; + + friend ATFunctionCallbackVH; + friend ATCallCallbackVH; + + // FIXME: SmallSet might be better here, but it currently has no iterators. + typedef DenseSet CallHandleSet; + // FIXME: DenseMap is not thread safe; if we ever run function passes + // concurrently, this will need to be changed! + typedef DenseMap> FunctionCallsMap; + FunctionCallsMap CachedAssumeCalls; + + /// Scan the provided function for @llvm.assume intrinsic calls. Returns an + /// iterator to the set for this function in the CachedAssumeCalls map. + FunctionCallsMap::iterator scanFunction(Function *F); + +public: + /// Remove the cache of @llvm.assume intrinsics for the given function. + void clearAssumptions(Function *F); + + /// Add an @llvm.assume intrinsic to the cache for its parent function. + void registerAssumption(CallInst *CI); + + // --------------------------------------------------------------------------- + // Assumption Iterator interface... + // + typedef CallHandleSet::iterator assumption_iterator; + typedef iterator_range assumption_range; + + inline assumption_range assumptions(Function *F) { + FunctionCallsMap::iterator I = CachedAssumeCalls.find(F); + if (I == CachedAssumeCalls.end()) { + I = scanFunction(F); + } + + return assumption_range(I->second.begin(), I->second.end()); + } + + // --------------------------------------------------------------------------- + // Pass interface... + // + + AssumptionTracker(); + ~AssumptionTracker(); + + void releaseMemory() override { + CachedAssumeCalls.clear(); + } + + static char ID; // Pass identification, replacement for typeid +}; + +} // end namespace llvm + +#endif Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -261,6 +261,7 @@ void initializeTargetTransformInfoAnalysisGroup(PassRegistry&); void initializeNoTTIPass(PassRegistry&); void initializeTargetLibraryInfoPass(PassRegistry&); +void initializeAssumptionTrackerPass(PassRegistry &); void initializeTwoAddressInstructionPassPass(PassRegistry&); void initializeTypeBasedAliasAnalysisPass(PassRegistry&); void initializeScopedNoAliasAAPass(PassRegistry&); Index: lib/Analysis/AssumptionTracker.cpp =================================================================== --- /dev/null +++ lib/Analysis/AssumptionTracker.cpp @@ -0,0 +1,92 @@ +//===- AssumptionTracker.cpp - Track @llvm.assume -------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains a pass that keeps track of @llvm.assume intrinsics in +// the functions of a module. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/AssumptionTracker.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/PatternMatch.h" +#include "llvm/Support/Debug.h" +using namespace llvm; +using namespace llvm::PatternMatch; + +void AssumptionTracker::ATFunctionCallbackVH::deleted() { + AT->clearAssumptions(cast(getValPtr())); + // this now dangles! +} + +void AssumptionTracker::clearAssumptions(Function *F) { + CachedAssumeCalls.erase(F); +} + +void AssumptionTracker::ATCallCallbackVH::deleted() { + assert(F && "delete callback called on dummy handle"); + FunctionCallsMap::iterator I = AT->CachedAssumeCalls.find(F); + assert(I != AT->CachedAssumeCalls.end() && + "Function cleared from the map without removing the values?"); + + I->second.erase(cast(getValPtr())); + // this now dangles! +} + +AssumptionTracker::FunctionCallsMap::iterator +AssumptionTracker::scanFunction(Function *F) { + auto IP = + CachedAssumeCalls.insert(std::make_pair(ATFunctionCallbackVH(F, this), + CallHandleSet())); + assert(IP.second && "Scanning function already in the map?"); + + FunctionCallsMap::iterator I = IP.first; + + // Go through all instructions in all blocks, add all calls to @llvm.assume + // to our cache. + for (BasicBlock &B : *F) + for (Instruction &II : B) + if (match(cast(&II), m_Intrinsic(m_Value()))) + I->second.insert(ATCallCallbackVH(&II, this)); + + return I; +} + +void AssumptionTracker::registerAssumption(CallInst *CI) { + assert(match(cast(CI), + m_Intrinsic(m_Value())) && + "Registered call does not call @llvm.assume"); + + Function *F = CI->getParent()->getParent(); + assert(F && "Cannot register @llvm.assume call not in a function"); + + FunctionCallsMap::iterator I = CachedAssumeCalls.find(F); + if (I == CachedAssumeCalls.end()) { + I = scanFunction(F); + assert(I->second.count(CI) && "Function scan did not find the call"); + + return; + } + + I->second.insert(ATCallCallbackVH(CI, this)); +} + +AssumptionTracker::AssumptionTracker() : ImmutablePass(ID) { + initializeAssumptionTrackerPass(*PassRegistry::getPassRegistry()); +} + +AssumptionTracker::~AssumptionTracker() {} + +INITIALIZE_PASS(AssumptionTracker, "assumption-tracker", "Assumption Tracker", + false, true) +char AssumptionTracker::ID = 0; + Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -5,6 +5,7 @@ AliasDebugger.cpp AliasSetTracker.cpp Analysis.cpp + AssumptionTracker.cpp BasicAliasAnalysis.cpp BlockFrequencyInfo.cpp BlockFrequencyInfoImpl.cpp Index: lib/Transforms/InstCombine/InstCombine.h =================================================================== --- lib/Transforms/InstCombine/InstCombine.h +++ lib/Transforms/InstCombine/InstCombine.h @@ -24,6 +24,7 @@ namespace llvm { class CallSite; +class AssumptionTracker; class DataLayout; class TargetLibraryInfo; class DbgDeclareInst; @@ -86,6 +87,7 @@ class LLVM_LIBRARY_VISIBILITY InstCombiner : public FunctionPass, public InstVisitor { + AssumptionTracker *AT; const DataLayout *DL; TargetLibraryInfo *TLI; bool MadeIRChange; @@ -114,6 +116,8 @@ void getAnalysisUsage(AnalysisUsage &AU) const override; + AssumptionTracker *getAssumptionTracker() const { return AT; } + const DataLayout *getDataLayout() const { return DL; } TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; } Index: lib/Transforms/InstCombine/InstCombineCalls.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineCalls.cpp +++ lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -13,6 +13,7 @@ #include "InstCombine.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AssumptionTracker.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/DataLayout.h" @@ -999,14 +1000,18 @@ Value *IIOperand = II->getArgOperand(0), *A, *B, *AssumeIntrinsic = II->getCalledValue(); if (match(IIOperand, m_And(m_Value(A), m_Value(B)))) { - Builder->CreateCall(AssumeIntrinsic, A, II->getName()); - Builder->CreateCall(AssumeIntrinsic, B, II->getName()); + AT->registerAssumption( + Builder->CreateCall(AssumeIntrinsic, A, II->getName())); + AT->registerAssumption( + Builder->CreateCall(AssumeIntrinsic, B, II->getName())); return EraseInstFromFunction(*II); } // assume(!(a || b)) -> assume(!a); assume(!b); if (match(IIOperand, m_Not(m_Or(m_Value(A), m_Value(B))))) { - Builder->CreateCall(AssumeIntrinsic, Builder->CreateNot(A), II->getName()); - Builder->CreateCall(AssumeIntrinsic, Builder->CreateNot(B), II->getName()); + AT->registerAssumption( + Builder->CreateCall(AssumeIntrinsic, Builder->CreateNot(A), II->getName())); + AT->registerAssumption( + Builder->CreateCall(AssumeIntrinsic, Builder->CreateNot(B), II->getName())); return EraseInstFromFunction(*II); } break; Index: lib/Transforms/InstCombine/InstructionCombining.cpp =================================================================== --- lib/Transforms/InstCombine/InstructionCombining.cpp +++ lib/Transforms/InstCombine/InstructionCombining.cpp @@ -39,6 +39,7 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringSwitch.h" +#include "llvm/Analysis/AssumptionTracker.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" @@ -85,12 +86,14 @@ char InstCombiner::ID = 0; INITIALIZE_PASS_BEGIN(InstCombiner, "instcombine", "Combine redundant instructions", false, false) +INITIALIZE_PASS_DEPENDENCY(AssumptionTracker) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) INITIALIZE_PASS_END(InstCombiner, "instcombine", "Combine redundant instructions", false, false) void InstCombiner::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); + AU.addRequired(); AU.addRequired(); } @@ -2829,6 +2832,7 @@ if (skipOptnoneFunction(F)) return false; + AT = &getAnalysis(); DataLayoutPass *DLP = getAnalysisIfAvailable(); DL = DLP ? &DLP->getDataLayout() : nullptr; TLI = &getAnalysis(); Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -823,6 +823,10 @@ F->getBasicBlockList().splice(NewPreheader, F->getBasicBlockList(), NewBlocks[0], F->end()); + // FIXME: We could register any cloned assumptions instead of clearing the + // whole function's cache. + AT->clearAssumptions(F); + // Now we create the new Loop object for the versioned loop. Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM); Index: lib/Transforms/Utils/InlineFunction.cpp =================================================================== --- lib/Transforms/Utils/InlineFunction.cpp +++ lib/Transforms/Utils/InlineFunction.cpp @@ -18,6 +18,7 @@ #include "llvm/ADT/SetVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionTracker.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/InstructionSimplify.h" @@ -923,6 +924,11 @@ // Add noalias metadata if necessary. AddAliasScopeMetadata(CS, VMap, IFI.DL); + + // FIXME: We could register any cloned assumptions instead of clearing the + // whole function's cache. + if (IFI.AT) + IFI.AT->clearAssumptions(Caller); } // If there are any alloca instructions in the block that used to be the entry Index: lib/Transforms/Utils/LoopUnroll.cpp =================================================================== --- lib/Transforms/Utils/LoopUnroll.cpp +++ lib/Transforms/Utils/LoopUnroll.cpp @@ -19,6 +19,7 @@ #include "llvm/Transforms/Utils/UnrollLoop.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AssumptionTracker.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/LoopPass.h" @@ -442,6 +443,10 @@ } } + // FIXME: We could register any cloned assumptions instead of clearing the + // whole function's cache. + AT->clearAssumptions(F); + DominatorTree *DT = nullptr; if (PP) { // FIXME: Reconstruct dom info, because it is not preserved properly.