Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

Differential D108099 Diff 366547 llvm/lib/Transforms/IPO/Attributor.cpp

Changeset View

Standalone View

llvm/lib/Transforms/IPO/Attributor.cpp

Show First 20 Lines • Show All 1,307 Lines • ▼ Show 20 Lines	for (Instruction *I :

if (!Pred(*I))		if (!Pred(*I))
return false;		return false;
}		}

return true;		return true;
}		}

void Attributor::runTillFixpoint() {		void Attributor::runStage() {
TimeTraceScope TimeScope("Attributor::runTillFixpoint");		Phase = AttributorPhase::UPDATE;

		TimeTraceScope TimeScope("Attributor::runIterationStage");
LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "		LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
<< DG.SyntheticRoot.Deps.size()		<< DG.SyntheticRoot.Deps.size()
<< " abstract attributes.\n");		<< " abstract attributes.\n");

// Now that all abstract attributes are collected and initialized we start		// Now that all abstract attributes are collected and initialized we start
// the abstract analysis.		// the abstract analysis.

unsigned IterationCounter = 1;		unsigned IterationCounter = 1;
unsigned MaxFixedPointIterations;		unsigned MaxFixedPointIterations;
if (MaxFixpointIterations)		if (MaxFixpointIterations)
MaxFixedPointIterations = MaxFixpointIterations.getValue();		MaxFixedPointIterations = MaxFixpointIterations.getValue();
else		else
MaxFixedPointIterations = SetFixpointIterations;		MaxFixedPointIterations = SetFixpointIterations;

SmallVector<AbstractAttribute *, 32> ChangedAAs;		SmallVector<AbstractAttribute *, 32> ChangedAAs;
▲ Show 20 Lines • Show All 112 Lines • ▼ Show 20 Lines	if (!Visited.empty())
<< " abstract attributes.\n";		<< " abstract attributes.\n";
});		});

if (VerifyMaxFixpointIterations &&		if (VerifyMaxFixpointIterations &&
IterationCounter != MaxFixedPointIterations) {		IterationCounter != MaxFixedPointIterations) {
errs() << "\n[Attributor] Fixpoint iteration done after: "		errs() << "\n[Attributor] Fixpoint iteration done after: "
<< IterationCounter << "/" << MaxFixedPointIterations		<< IterationCounter << "/" << MaxFixedPointIterations
<< " iterations\n";		<< " iterations\n";
llvm_unreachable("The fixpoint was not reached with exactly the number of "		// llvm_unreachable("The fixpoint was not reached with exactly the number of
"specified iterations!");		// "
		// "specified iterations!");
}		}

		// We can still seed more attributes after running a fixpoint iteration.
		Phase = AttributorPhase::SEEDING;
}		}

ChangeStatus Attributor::manifestAttributes() {		ChangeStatus Attributor::manifestAttributes() {
TimeTraceScope TimeScope("Attributor::manifestAttributes");		TimeTraceScope TimeScope("Attributor::manifestAttributes");
size_t NumFinalAAs = DG.SyntheticRoot.Deps.size();		size_t NumFinalAAs = DG.SyntheticRoot.Deps.size();

unsigned NumManifested = 0;		unsigned NumManifested = 0;
unsigned NumAtFixpoint = 0;		unsigned NumAtFixpoint = 0;
▲ Show 20 Lines • Show All 348 Lines • ▼ Show 20 Lines

ChangeStatus Attributor::run() {		ChangeStatus Attributor::run() {
TimeTraceScope TimeScope("Attributor::run");		TimeTraceScope TimeScope("Attributor::run");
AttributorCallGraph ACallGraph(*this);		AttributorCallGraph ACallGraph(*this);

if (PrintCallGraph)		if (PrintCallGraph)
ACallGraph.populateAll();		ACallGraph.populateAll();

Phase = AttributorPhase::UPDATE;		runStage();
runTillFixpoint();

// dump graphs on demand		// dump graphs on demand
if (DumpDepGraph)		if (DumpDepGraph)
DG.dumpGraph();		DG.dumpGraph();

if (ViewDepGraph)		if (ViewDepGraph)
DG.viewGraph();		DG.viewGraph();

if (PrintDependencies)		if (PrintDependencies)
DG.print();		DG.print();

		if (PrintCallGraph)
		ACallGraph.print();

		return finalize();
		}

		ChangeStatus Attributor::finalize() {
		// More attributes can be seeded after the runStage() function is called.
		assert(Phase == AttributorPhase::SEEDING &&
		"Expected attributor to be in the seeeding stage!");

Phase = AttributorPhase::MANIFEST;		Phase = AttributorPhase::MANIFEST;
ChangeStatus ManifestChange = manifestAttributes();		ChangeStatus ManifestChange = manifestAttributes();

Phase = AttributorPhase::CLEANUP;		Phase = AttributorPhase::CLEANUP;
ChangeStatus CleanupChange = cleanupIR();		ChangeStatus CleanupChange = cleanupIR();

if (PrintCallGraph)
ACallGraph.print();

return ManifestChange \| CleanupChange;		return ManifestChange \| CleanupChange;
}		}

ChangeStatus Attributor::updateAA(AbstractAttribute &AA) {		ChangeStatus Attributor::updateAA(AbstractAttribute &AA) {
TimeTraceScope TimeScope(		TimeTraceScope TimeScope(
AA.getName() + std::to_string(AA.getIRPosition().getPositionKind()) +		AA.getName() + std::to_string(AA.getIRPosition().getPositionKind()) +
"::updateAA");		"::updateAA");
assert(Phase == AttributorPhase::UPDATE &&		assert(Phase == AttributorPhase::UPDATE &&
▲ Show 20 Lines • Show All 571 Lines • ▼ Show 20 Lines	assert((DI.DepClass == DepClassTy::REQUIRED \|\|
DI.DepClass == DepClassTy::OPTIONAL) &&		DI.DepClass == DepClassTy::OPTIONAL) &&
"Expected required or optional dependence (1 bit)!");		"Expected required or optional dependence (1 bit)!");
auto &DepAAs = const_cast<AbstractAttribute &>(*DI.FromAA).Deps;		auto &DepAAs = const_cast<AbstractAttribute &>(*DI.FromAA).Deps;
DepAAs.push_back(AbstractAttribute::DepTy(		DepAAs.push_back(AbstractAttribute::DepTy(
const_cast<AbstractAttribute *>(DI.ToAA), unsigned(DI.DepClass)));		const_cast<AbstractAttribute *>(DI.ToAA), unsigned(DI.DepClass)));
}		}
}		}

void Attributor::identifyDefaultAbstractAttributes(Function &F) {		void Attributor::identifyFirstStageAttributes(Function &F) {
		jdoerfertUnsubmitted Not Done Reply Inline Actions Should we interleave this one and the default one, add an argument to pick which handling the user want? Seems there is some obvious duplication but it might not be as much as I feared. jdoerfert: Should we interleave this one and the default one, add an argument to pick which handling the…
if (!VisitedFunctions.insert(&F).second)
return;
if (F.isDeclaration())		if (F.isDeclaration())
return;		return;

		IRPosition FPos = IRPosition::function(F);

// In non-module runs we need to look at the call sites of a function to		// In non-module runs we need to look at the call sites of a function to
// determine if it is part of a must-tail call edge. This will influence what		// determine if it is part of a must-tail call edge. This will influence what
// attributes we can derive.		// attributes we can derive.
InformationCache::FunctionInfo &FI = InfoCache.getFunctionInfo(F);		InformationCache::FunctionInfo &FI = InfoCache.getFunctionInfo(F);
if (!isModulePass() && !FI.CalledViaMustTail) {		if (!isModulePass() && !FI.CalledViaMustTail) {
for (const Use &U : F.uses())		for (const Use &U : F.uses())
if (const auto *CB = dyn_cast<CallBase>(U.getUser()))		if (const auto *CB = dyn_cast<CallBase>(U.getUser()))
if (CB->isCallee(&U) && CB->isMustTailCall())		if (CB->isCallee(&U) && CB->isMustTailCall())
FI.CalledViaMustTail = true;		FI.CalledViaMustTail = true;
}		}

IRPosition FPos = IRPosition::function(F);

// Check for dead BasicBlocks in every function.		// Check for dead BasicBlocks in every function.
// We need dead instruction detection because we do not want to deal with		// We need dead instruction detection because we do not want to deal with
// broken IR in which SSA rules do not apply.		// broken IR in which SSA rules do not apply.
getOrCreateAAFor<AAIsDead>(FPos);		getOrCreateAAFor<AAIsDead>(FPos);

		// Return attributes are only appropriate if the return type is non void.
		Type *ReturnType = F.getReturnType();
		if (!ReturnType->isVoidTy()) {
		IRPosition RetPos = IRPosition::returned(F);

		// Every returned value might be dead.
		getOrCreateAAFor<AAIsDead>(RetPos);
		}

		for (Argument &Arg : F.args()) {
		IRPosition ArgPos = IRPosition::argument(Arg);

		// Every argument might be dead.
		getOrCreateAAFor<AAIsDead>(ArgPos);
		}

		auto CallSitePred = [&](Instruction &I) -> bool {
		auto &CB = cast<CallBase>(I);
		IRPosition CBRetPos = IRPosition::callsite_returned(CB);

		// Call sites might be dead if they do not have side effects and no live
		// users. The return value might be dead if there are no live users.
		getOrCreateAAFor<AAIsDead>(CBRetPos);

		Function *Callee = CB.getCalledFunction();
		// TODO: Even if the callee is not known now we might be able to simplify
		// the call/callee.
		if (!Callee)
		return true;

		for (int I = 0, E = CB.getNumArgOperands(); I < E; ++I) {
		IRPosition CBArgPos = IRPosition::callsite_argument(CB, I);

		// Every call site argument might be dead.
		getOrCreateAAFor<AAIsDead>(CBArgPos);
		}

		return true;
		};

		auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
		bool Success;
		bool UsedAssumedInformation = false;
		Success = checkForAllInstructionsImpl(
		nullptr, OpcodeInstMap, CallSitePred, nullptr, nullptr,
		{(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
		(unsigned)Instruction::Call},
		UsedAssumedInformation);
		(void)Success;
		assert(Success && "Expected the check call to be successful!");
		}

		void Attributor::identifyDefaultAbstractAttributes(Function &F) {
		if (F.isDeclaration())
		return;

		IRPosition FPos = IRPosition::function(F);

// Every function might be "will-return".		// Every function might be "will-return".
getOrCreateAAFor<AAWillReturn>(FPos);		getOrCreateAAFor<AAWillReturn>(FPos);

// Every function might contain instructions that cause "undefined behavior".		// Every function might contain instructions that cause "undefined behavior".
getOrCreateAAFor<AAUndefinedBehavior>(FPos);		getOrCreateAAFor<AAUndefinedBehavior>(FPos);

// Every function can be nounwind.		// Every function can be nounwind.
getOrCreateAAFor<AANoUnwind>(FPos);		getOrCreateAAFor<AANoUnwind>(FPos);
Show All 24 Lines	void Attributor::identifyDefaultAbstractAttributes(Function &F) {
Type *ReturnType = F.getReturnType();		Type *ReturnType = F.getReturnType();
if (!ReturnType->isVoidTy()) {		if (!ReturnType->isVoidTy()) {
// Argument attribute "returned" --- Create only one per function even		// Argument attribute "returned" --- Create only one per function even
// though it is an argument attribute.		// though it is an argument attribute.
getOrCreateAAFor<AAReturnedValues>(FPos);		getOrCreateAAFor<AAReturnedValues>(FPos);

IRPosition RetPos = IRPosition::returned(F);		IRPosition RetPos = IRPosition::returned(F);

// Every returned value might be dead.
getOrCreateAAFor<AAIsDead>(RetPos);

// Every function might be simplified.		// Every function might be simplified.
getOrCreateAAFor<AAValueSimplify>(RetPos);		getOrCreateAAFor<AAValueSimplify>(RetPos);

// Every returned value might be marked noundef.		// Every returned value might be marked noundef.
getOrCreateAAFor<AANoUndef>(RetPos);		getOrCreateAAFor<AANoUndef>(RetPos);

if (ReturnType->isPointerTy()) {		if (ReturnType->isPointerTy()) {

Show All 16 Lines	for (Argument &Arg : F.args()) {
IRPosition ArgPos = IRPosition::argument(Arg);		IRPosition ArgPos = IRPosition::argument(Arg);

// Every argument might be simplified. We have to go through the Attributor		// Every argument might be simplified. We have to go through the Attributor
// interface though as outside AAs can register custom simplification		// interface though as outside AAs can register custom simplification
// callbacks.		// callbacks.
bool UsedAssumedInformation = false;		bool UsedAssumedInformation = false;
getAssumedSimplified(ArgPos, /* AA */ nullptr, UsedAssumedInformation);		getAssumedSimplified(ArgPos, /* AA */ nullptr, UsedAssumedInformation);

// Every argument might be dead.
getOrCreateAAFor<AAIsDead>(ArgPos);

// Every argument might be marked noundef.		// Every argument might be marked noundef.
getOrCreateAAFor<AANoUndef>(ArgPos);		getOrCreateAAFor<AANoUndef>(ArgPos);

if (Arg.getType()->isPointerTy()) {		if (Arg.getType()->isPointerTy()) {
// Every argument with pointer type might be marked nonnull.		// Every argument with pointer type might be marked nonnull.
getOrCreateAAFor<AANonNull>(ArgPos);		getOrCreateAAFor<AANonNull>(ArgPos);

// Every argument with pointer type might be marked noalias.		// Every argument with pointer type might be marked noalias.
Show All 17 Lines	if (Arg.getType()->isPointerTy()) {

// Every argument with pointer type might be privatizable (or promotable)		// Every argument with pointer type might be privatizable (or promotable)
getOrCreateAAFor<AAPrivatizablePtr>(ArgPos);		getOrCreateAAFor<AAPrivatizablePtr>(ArgPos);
}		}
}		}

auto CallSitePred = [&](Instruction &I) -> bool {		auto CallSitePred = [&](Instruction &I) -> bool {
auto &CB = cast<CallBase>(I);		auto &CB = cast<CallBase>(I);
IRPosition CBRetPos = IRPosition::callsite_returned(CB);

// Call sites might be dead if they do not have side effects and no live
// users. The return value might be dead if there are no live users.
getOrCreateAAFor<AAIsDead>(CBRetPos);

Function *Callee = CB.getCalledFunction();		Function *Callee = CB.getCalledFunction();
// TODO: Even if the callee is not known now we might be able to simplify		// TODO: Even if the callee is not known now we might be able to simplify
// the call/callee.		// the call/callee.
if (!Callee)		if (!Callee)
return true;		return true;

// Skip declarations except if annotations on their call sites were		// Skip declarations except if annotations on their call sites were
// explicitly requested.		// explicitly requested.
if (!AnnotateDeclarationCallSites && Callee->isDeclaration() &&		if (!AnnotateDeclarationCallSites && Callee->isDeclaration() &&
!Callee->hasMetadata(LLVMContext::MD_callback))		!Callee->hasMetadata(LLVMContext::MD_callback))
return true;		return true;

if (!Callee->getReturnType()->isVoidTy() && !CB.use_empty()) {		if (!Callee->getReturnType()->isVoidTy() && !CB.use_empty()) {

IRPosition CBRetPos = IRPosition::callsite_returned(CB);		IRPosition CBRetPos = IRPosition::callsite_returned(CB);
getOrCreateAAFor<AAValueSimplify>(CBRetPos);		getOrCreateAAFor<AAValueSimplify>(CBRetPos);
}		}

for (int I = 0, E = CB.getNumArgOperands(); I < E; ++I) {		for (int I = 0, E = CB.getNumArgOperands(); I < E; ++I) {

IRPosition CBArgPos = IRPosition::callsite_argument(CB, I);		IRPosition CBArgPos = IRPosition::callsite_argument(CB, I);

// Every call site argument might be dead.
getOrCreateAAFor<AAIsDead>(CBArgPos);

// Call site argument might be simplified. We have to go through the		// Call site argument might be simplified. We have to go through the
// Attributor interface though as outside AAs can register custom		// Attributor interface though as outside AAs can register custom
// simplification callbacks.		// simplification callbacks.
bool UsedAssumedInformation = false;		bool UsedAssumedInformation = false;
getAssumedSimplified(CBArgPos, /* AA */ nullptr, UsedAssumedInformation);		getAssumedSimplified(CBArgPos, /* AA */ nullptr, UsedAssumedInformation);

// Every call site argument might be marked "noundef".		// Every call site argument might be marked "noundef".
getOrCreateAAFor<AANoUndef>(CBArgPos);		getOrCreateAAFor<AANoUndef>(CBArgPos);
▲ Show 20 Lines • Show All 219 Lines • ▼ Show 20 Lines	for (unsigned u = 0; u < FunSize; u++) {
if (CallBase *CB = dyn_cast<CallBase>(U.getUser())) {		if (CallBase *CB = dyn_cast<CallBase>(U.getUser())) {
auto *CallerF = CB->getCaller();		auto *CallerF = CB->getCaller();
CGUpdater.reanalyzeFunction(*CallerF);		CGUpdater.reanalyzeFunction(*CallerF);
}		}
}		}
}		}
}		}

for (Function *F : Functions) {		// We are running the Attributor in two stages.
if (F->hasExactDefinition())		// First we identify first stage attributes (like AAIsDead).
NumFnWithExactDefinition++;		// We run a fixpoint iteration for those attributes
else		// before running a iteration on the rest, this helps with the performance.
NumFnWithoutExactDefinition++;

		// TODO: Consider running each function as a separate stage.

		auto ShouldSkipFunction = [&](Function *F) {
// We look at internal functions only on-demand but if any use is not a		// We look at internal functions only on-demand but if any use is not a
// direct call or outside the current set of analyzed functions, we have		// direct call or outside the current set of analyzed functions, we have
// to do it eagerly.		// to do it eagerly.
if (F->hasLocalLinkage()) {		if (F->hasLocalLinkage()) {
if (llvm::all_of(F->uses(), [&Functions](const Use &U) {		if (llvm::all_of(F->uses(), [&Functions](const Use &U) {
const auto *CB = dyn_cast<CallBase>(U.getUser());		const auto *CB = dyn_cast<CallBase>(U.getUser());
return CB && CB->isCallee(&U) &&		return CB && CB->isCallee(&U) &&
Functions.count(const_cast<Function *>(CB->getCaller()));		Functions.count(const_cast<Function *>(CB->getCaller()));
}))		}))
		return true;
		}

		return false;
		};

		for (Function *F : Functions) {
		if (F->hasExactDefinition())
		NumFnWithExactDefinition++;
		else
		NumFnWithoutExactDefinition++;

		if (ShouldSkipFunction(F))
continue;		continue;

		// Identify AbstactAttribute oppurtunities that shuold be run on the first
		// stage.
		A.identifyFirstStageAttributes(*F);
}		}

// Populate the Attributor with abstract attribute opportunities in the		// Run the first stage.
// function and the information cache with IR information.		A.runStage();

		for (Function *F : Functions) {
		if (ShouldSkipFunction(F))
		continue;

A.identifyDefaultAbstractAttributes(*F);		A.identifyDefaultAbstractAttributes(*F);
}		}

ChangeStatus Changed = A.run();		// Run the second stage.
		A.runStage();

		// Finalize the Attributor.
		ChangeStatus Changed = A.finalize();

LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size()		LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size()
<< " functions, result: " << Changed << ".\n");		<< " functions, result: " << Changed << ".\n");
return Changed == ChangeStatus::CHANGED;		return Changed == ChangeStatus::CHANGED;
}		}

void AADepGraph::viewGraph() { llvm::ViewGraph(this, "Dependency Graph"); }		void AADepGraph::viewGraph() { llvm::ViewGraph(this, "Dependency Graph"); }

▲ Show 20 Lines • Show All 214 Lines • Show Last 20 Lines