#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/StringExtras.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Support/CommandLine.h"
+#include <algorithm>
using namespace llvm;
+static cl::opt<bool>
+EnableNoAliasConversion("enable-noalias-to-md-conversion", cl::init(false),
+ cl::Hidden,
+ cl::desc("Convert noalias attributes to metadata during inlining."));
+
bool llvm::InlineFunction(CallInst *CI, InlineFunctionInfo &IFI,
bool InsertLifetime) {
return InlineFunction(CallSite(CI), IFI, InsertLifetime);
if (!NI)
continue;
- if (MDNode *M = NI->getMetadata(LLVMContext::MD_alias_scope))
- NI->setMetadata(LLVMContext::MD_alias_scope, MDMap[M]);
+ if (MDNode *M = NI->getMetadata(LLVMContext::MD_alias_scope)) {
+ MDNode *NewMD = MDMap[M];
+ // If the call site also had alias scope metadata (a list of scopes to
+ // which instructions inside it might belong), propagate those scopes to
+ // the inlined instructions.
+ if (MDNode *CSM =
+ CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope))
+ NewMD = MDNode::concatenate(NewMD, CSM);
+ NI->setMetadata(LLVMContext::MD_alias_scope, NewMD);
+ } else if (NI->mayReadOrWriteMemory()) {
+ if (MDNode *M =
+ CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope))
+ NI->setMetadata(LLVMContext::MD_alias_scope, M);
+ }
- if (MDNode *M = NI->getMetadata(LLVMContext::MD_noalias))
- NI->setMetadata(LLVMContext::MD_noalias, MDMap[M]);
+ if (MDNode *M = NI->getMetadata(LLVMContext::MD_noalias)) {
+ MDNode *NewMD = MDMap[M];
+ // If the call site also had noalias metadata (a list of scopes with
+ // which instructions inside it don't alias), propagate those scopes to
+ // the inlined instructions.
+ if (MDNode *CSM =
+ CS.getInstruction()->getMetadata(LLVMContext::MD_noalias))
+ NewMD = MDNode::concatenate(NewMD, CSM);
+ NI->setMetadata(LLVMContext::MD_noalias, NewMD);
+ } else if (NI->mayReadOrWriteMemory()) {
+ if (MDNode *M =
+ CS.getInstruction()->getMetadata(LLVMContext::MD_noalias))
+ NI->setMetadata(LLVMContext::MD_noalias, M);
+ }
}
// Now that everything has been replaced, delete the dummy nodes.
MDNode::deleteTemporary(DummyNodes[i]);
}
+/// AddAliasScopeMetadata - If the inlined function has noalias arguments, then
+/// add new alias scopes for each noalias argument, tag the mapped noalias
+/// parameters with noalias metadata specifying the new scope, and tag all
+/// non-derived loads, stores and memory intrinsics with the new alias scopes.
+static void AddAliasScopeMetadata(CallSite CS, ValueToValueMapTy &VMap,
+ const DataLayout *DL) {
+ if (!EnableNoAliasConversion)
+ return;
+
+ const Function *CalledFunc = CS.getCalledFunction();
+ SmallVector<const Argument *, 4> NoAliasArgs;
+
+ for (Function::const_arg_iterator I = CalledFunc->arg_begin(),
+ E = CalledFunc->arg_end(); I != E; ++I) {
+ if (I->hasNoAliasAttr() && !I->hasNUses(0))
+ NoAliasArgs.push_back(I);
+ }
+
+ if (NoAliasArgs.empty())
+ return;
+
+ // To do a good job, if a noalias variable is captured, we need to know if
+ // the capture point dominates the particular use we're considering.
+ DominatorTree DT;
+ DT.recalculate(const_cast<Function&>(*CalledFunc));
+
+ // noalias indicates that pointer values based on the argument do not alias
+ // pointer values which are not based on it. So we add a new "scope" for each
+ // noalias function argument. Accesses using pointers based on that argument
+ // become part of that alias scope, accesses using pointers not based on that
+ // argument are tagged as noalias with that scope.
+
+ DenseMap<const Argument *, MDNode *> NewScopes;
+ MDBuilder MDB(CalledFunc->getContext());
+
+ // Create a new scope domain for this function.
+ MDNode *NewDomain =
+ MDB.createAnonymousAliasScopeDomain(CalledFunc->getName());
+ for (unsigned i = 0, e = NoAliasArgs.size(); i != e; ++i) {
+ const Argument *A = NoAliasArgs[i];
+
+ std::string Name = CalledFunc->getName();
+ if (A->hasName()) {
+ Name += ": %";
+ Name += A->getName();
+ } else {
+ Name += ": argument ";
+ Name += utostr(i);
+ }
+
+ // Note: We always create a new anonymous root here. This is true regardless
+ // of the linkage of the callee because the aliasing "scope" is not just a
+ // property of the callee, but also all control dependencies in the caller.
+ MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
+ NewScopes.insert(std::make_pair(A, NewScope));
+ }
+
+ // Iterate over all new instructions in the map; for all memory-access
+ // instructions, add the alias scope metadata.
+ for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end();
+ VMI != VMIE; ++VMI) {
+ if (const Instruction *I = dyn_cast<Instruction>(VMI->first)) {
+ if (!VMI->second)
+ continue;
+
+ Instruction *NI = dyn_cast<Instruction>(VMI->second);
+ if (!NI)
+ continue;
+
+ SmallVector<const Value *, 2> PtrArgs;
+
+ if (const LoadInst *LI = dyn_cast<LoadInst>(I))
+ PtrArgs.push_back(LI->getPointerOperand());
+ else if (const StoreInst *SI = dyn_cast<StoreInst>(I))
+ PtrArgs.push_back(SI->getPointerOperand());
+ else if (const VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
+ PtrArgs.push_back(VAAI->getPointerOperand());
+ else if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I))
+ PtrArgs.push_back(CXI->getPointerOperand());
+ else if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I))
+ PtrArgs.push_back(RMWI->getPointerOperand());
+ else if (ImmutableCallSite ICS = ImmutableCallSite(I)) {
+ // If we know that the call does not access memory, then we'll still
+ // know that about the inlined clone of this call site, and we don't
+ // need to add metadata.
+ if (ICS.doesNotAccessMemory())
+ continue;
+
+ for (ImmutableCallSite::arg_iterator AI = ICS.arg_begin(),
+ AE = ICS.arg_end(); AI != AE; ++AI)
+ // We need to check the underlying objects of all arguments, not just
+ // the pointer arguments, because we might be passing pointers as
+ // integers, etc.
+ // FIXME: If we know that the call only accesses pointer arguments,
+ // then we only need to check the pointer arguments.
+ PtrArgs.push_back(*AI);
+ }
+
+ // If we found no pointers, then this instruction is not suitable for
+ // pairing with an instruction to receive aliasing metadata.
+ // However, if this is a call, this we might just alias with none of the
+ // noalias arguments.
+ if (PtrArgs.empty() && !isa<CallInst>(I) && !isa<InvokeInst>(I))
+ continue;
+
+ // It is possible that there is only one underlying object, but you
+ // need to go through several PHIs to see it, and thus could be
+ // repeated in the Objects list.
+ SmallPtrSet<const Value *, 4> ObjSet;
+ SmallVector<Value *, 4> Scopes, NoAliases;
+
+ SmallSetVector<const Argument *, 4> NAPtrArgs;
+ for (unsigned i = 0, ie = PtrArgs.size(); i != ie; ++i) {
+ SmallVector<Value *, 4> Objects;
+ GetUnderlyingObjects(const_cast<Value*>(PtrArgs[i]),
+ Objects, DL, /* MaxLookup = */ 0);
+
+ for (Value *O : Objects)
+ ObjSet.insert(O);
+ }
+
+ // Figure out if we're derived from anyhing that is not a noalias
+ // argument.
+ bool CanDeriveViaCapture = false;
+ for (const Value *V : ObjSet)
+ if (!isIdentifiedFunctionLocal(const_cast<Value*>(V))) {
+ CanDeriveViaCapture = true;
+ break;
+ }
+
+ // First, we want to figure out all of the sets with which we definitely
+ // don't alias. Iterate over all noalias set, and add those for which:
+ // 1. The noalias argument is not in the set of objects from which we
+ // definitely derive.
+ // 2. The noalias argument has not yet been captured.
+ for (const Argument *A : NoAliasArgs) {
+ if (!ObjSet.count(A) && (!CanDeriveViaCapture ||
+ A->hasNoCaptureAttr() ||
+ !PointerMayBeCapturedBefore(A,
+ /* ReturnCaptures */ false,
+ /* StoreCaptures */ false, I, &DT)))
+ NoAliases.push_back(NewScopes[A]);
+ }
+
+ if (!NoAliases.empty())
+ NI->setMetadata(LLVMContext::MD_noalias, MDNode::concatenate(
+ NI->getMetadata(LLVMContext::MD_noalias),
+ MDNode::get(CalledFunc->getContext(), NoAliases)));
+ // Next, we want to figure out all of the sets to which we might belong.
+ // We might below to a set if:
+ // 1. The noalias argument is in the set of underlying objects
+ // or
+ // 2. There is some non-noalias argument in our list and the no-alias
+ // argument has been captured.
+
+ for (const Argument *A : NoAliasArgs) {
+ if (ObjSet.count(A) || (CanDeriveViaCapture &&
+ PointerMayBeCapturedBefore(A,
+ /* ReturnCaptures */ false,
+ /* StoreCaptures */ false,
+ I, &DT)))
+ Scopes.push_back(NewScopes[A]);
+ }
+
+ if (!Scopes.empty())
+ NI->setMetadata(LLVMContext::MD_alias_scope, MDNode::concatenate(
+ NI->getMetadata(LLVMContext::MD_alias_scope),
+ MDNode::get(CalledFunc->getContext(), Scopes)));
+ }
+ }
+}
+
/// UpdateCallGraphAfterInlining - Once we have cloned code over from a callee
/// into the caller, update the specified callgraph to reflect the changes we
/// made. Note that it's possible that not all code was copied over, so only
}
}
-/// Returns a musttail call instruction if one immediately precedes the given
-/// return instruction with an optional bitcast instruction between them.
-static CallInst *getPrecedingMustTailCall(ReturnInst *RI) {
- Instruction *Prev = RI->getPrevNode();
- if (!Prev)
- return nullptr;
-
- if (Value *RV = RI->getReturnValue()) {
- if (RV != Prev)
- return nullptr;
-
- // Look through the optional bitcast.
- if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
- RV = BI->getOperand(0);
- Prev = BI->getPrevNode();
- if (!Prev || RV != Prev)
- return nullptr;
- }
- }
-
- if (auto *CI = dyn_cast<CallInst>(Prev)) {
- if (CI->isMustTailCall())
- return CI;
- }
- return nullptr;
-}
-
/// InlineFunction - This function inlines the called function into the basic
/// block of the caller. This returns false if it is not possible to inline
/// this call. The program is still in a well defined state if this occurs
// Clone existing noalias metadata if necessary.
CloneAliasScopeMetadata(CS, VMap);
+
+ // Add noalias metadata if necessary.
+ AddAliasScopeMetadata(CS, VMap, IFI.DL);
}
// If there are any alloca instructions in the block that used to be the entry
for (ReturnInst *RI : Returns) {
// Don't insert llvm.lifetime.end calls between a musttail call and a
// return. The return kills all local allocas.
- if (InlinedMustTailCalls && getPrecedingMustTailCall(RI))
+ if (InlinedMustTailCalls &&
+ RI->getParent()->getTerminatingMustTailCall())
continue;
IRBuilder<>(RI).CreateLifetimeEnd(AI, AllocaSize);
}
for (ReturnInst *RI : Returns) {
// Don't insert llvm.stackrestore calls between a musttail call and a
// return. The return will restore the stack pointer.
- if (InlinedMustTailCalls && getPrecedingMustTailCall(RI))
+ if (InlinedMustTailCalls && RI->getParent()->getTerminatingMustTailCall())
continue;
IRBuilder<>(RI).CreateCall(StackRestore, SavedPtr);
}
// Handle the returns preceded by musttail calls separately.
SmallVector<ReturnInst *, 8> NormalReturns;
for (ReturnInst *RI : Returns) {
- CallInst *ReturnedMustTail = getPrecedingMustTailCall(RI);
+ CallInst *ReturnedMustTail =
+ RI->getParent()->getTerminatingMustTailCall();
if (!ReturnedMustTail) {
NormalReturns.push_back(RI);
continue;