Page MenuHomePhabricator
Differential D71617 Diff 235285 llvm/lib/Transforms/IPO/Attributor.cpp

Changeset View

Standalone View

View Options

llvm/lib/Transforms/IPO/Attributor.cpp

Show First 20 Lines • Show All 2,292 Lines • ▼ Show 20 Lines ChangeStatus updateImpl(Attributor &A) override {
if (!NoAliasAA.isAssumedNoAlias()) if (!NoAliasAA.isAssumedNoAlias())
return indicatePessimisticFixpoint(); return indicatePessimisticFixpoint();
LLVM_DEBUG(dbgs() << "[Attributor][AANoAliasCSArg] " << V LLVM_DEBUG(dbgs() << "[Attributor][AANoAliasCSArg] " << V
<< " is assumed NoAlias in the definition\n"); << " is assumed NoAlias in the definition\n");
// (ii) Check whether the value is captured in the scope using AANoCapture. // (ii) Check whether the value is captured in the scope using AANoCapture.
// FIXME: This is conservative though, it is better to look at CFG and // Look at CFG and check only uses possibly executed before this
// check only uses possibly executed before this callsite. // callsite.
auto UsePred = [&](const Use &U, bool &Follow) -> bool {
if (isa<GetElementPtrInst>(U) || isa<BitCastInst>(U) ||
jdoerfertUnsubmitted
Done
ReplyInline Actions

I think you need to allow UserI to be getCtx(). That is, if the user is the current instruction we ignore the use but follow if there are subsequent uses!

jdoerfert: I think you need to allow `UserI` to be `getCtx()`. That is, if the user is the current…
isa<PHINode>(U) || isa<SelectInst>(U)) {
Follow = true;
return true;
}
jdoerfertUnsubmitted
Done
ReplyInline Actions

You need to track dependences here. just remove the parameter for now, e.g. A.getAAFor<AAReachability>(*this, IRPosition::function(*ScopeFn))

jdoerfert: You need to track dependences here. just remove the parameter for now, e.g. `A.
// Unknown user for which we can not track uses further
jdoerfertUnsubmitted
Done
ReplyInline Actions

If you want to use the AANoCapture you need the IR position of the use: const IRPosition UseIRP = IRPosition::callsite_argument(CS, CS.getArgumentNo(&U)); not of the outer call site. If you just want to know if it already is marked nocapture you can just ask the call site CS: CS.paramHasAttr(CS.getArgumentNo(&U), Attribute::NoCapture)

You also want to return true (= all is OK) if the argument has a no-capture attribute. If not, you continue with the reachability check we need before // Unknown user for which we can not track uses further.

jdoerfert: If you want to use the `AANoCapture` you need the IR position of the use: `const IRPosition…
LLVM_DEBUG(dbgs() << "[Attributor][AANoAliasCSArg] Unknown user: " << *U << "\n");
return false;
};
auto &NoCaptureAA = A.getAAFor<AANoCapture>(*this, IRP); auto &NoCaptureAA = A.getAAFor<AANoCapture>(*this, IRP);
if (!NoCaptureAA.isAssumedNoCaptureMaybeReturned()) { if (!NoCaptureAA.isAssumedNoCaptureMaybeReturned()) {
if (V.getType()->isPointerTy()) {
jdoerfertUnsubmitted
Done
ReplyInline Actions

You need to iterate over all uses (not only reachable ones) and then in the UsePred ask if getCtxI() is reachable from the User. If not, the UsePred can return true (=all is OK).

jdoerfert: You need to iterate over all uses (not only reachable ones) and then in the `UsePred` ask if…
ImmutableCallSite ICSCaller(&getAnchorValue());
const Instruction *CallSiteI = ICSCaller.getInstruction();
jdoerfertUnsubmitted
Done
ReplyInline Actions

I don't think you should restrict it to uses reachable from getCtxI here. All uses are interesting and reachability is checked from the uses.

jdoerfert: I don't think you should restrict it to uses reachable from `getCtxI` here. All uses are…
pgodeAuthorUnsubmitted
Done
ReplyInline Actions

Please correct me if I am wrong, I understand that we don't need, where we were checking whether uses of V are reachable from getCtxI().
if (!A.checkForAllUses(UsePred, *this, V, getCtxI()))

Instead, we need the regular call which checks for all uses of V.
if (!A.checkForAllUses(UsePred, *this, V)

And in that case, we won't need the ReachableFromI parameter to 'checkForAllUses'. And thus we can have the reachability check only in Pred instead of having one more check in checkForAllUses.
Only problem with this would be w.r.t. setting AnyUnreachable, which records dependencies.

pgode: Please correct me if I am wrong, I understand that we don't need, where we were checking…
jdoerfertUnsubmitted
Done
ReplyInline Actions

Instead, we need the regular call which checks for all uses of V.
if (!A.checkForAllUses(UsePred, *this, V)

Yes.

And in that case, we won't need the ReachableFromI parameter to 'checkForAllUses'. And thus we can have the reachability check only in Pred instead of having one more check in checkForAllUses.

Yes.

Only problem with this would be w.r.t. setting AnyUnreachable, which records dependencies.

You can split the changes to checkForAllUses into a separate patch. We want the changes but it is not needed for the noalias stuff.

jdoerfert: > Instead, we need the regular call which checks for all uses of V. > if (!A.checkForAllUses…
if (!A.checkForAllUses(UsePred, *this, V, CallSiteI)) {
LLVM_DEBUG( LLVM_DEBUG(
jdoerfertUnsubmitted
Done
ReplyInline Actions

Move this check before the CallBase conditional.

jdoerfert: Move this check before the `CallBase` conditional.
pgodeAuthorUnsubmitted
Done
ReplyInline Actions

I agree. This doesn't depend on CallBase anyway.

pgode: I agree. This doesn't depend on CallBase anyway.
jdoerfertUnsubmitted
Done
ReplyInline Actions

Remove the ! here. A use is OK, thus we return true if it is assumed not captured.

jdoerfert: Remove the `!` here. A use is OK, thus we return `true` if it is assumed not captured.
dbgs() << "[Attributor][AANoAliasCSArg] " << V dbgs() << "[Attributor][AANoAliasCSArg] " << V
<< " cannot be noalias as it is potentially captured\n"); << " cannot be noalias as it is potentially captured\n");
return indicatePessimisticFixpoint(); return indicatePessimisticFixpoint();
} }
}
jdoerfertUnsubmitted
Done
ReplyInline Actions

What we need to check here is:

Are there uses of the pointer value that are potentially executed before the use at this call site *and* is the pointer potentially captured at any of those uses.

I think we could do this in two steps:

  1. Iterate over all uses of the pointer and collect the uses that may reach the current call instruction. So I think the A.checkForAllUses might actually do as we need to check if the call we are looking at is reachable from the use.
  2. For all those uses, ask AANoCapture if they are potentially capturing. The method doesn't exist yet but you can add it to the AANoCapture interface and for now return always true.
jdoerfert: What we need to check here is: Are there uses of the pointer value that are potentially…
}
jdoerfertUnsubmitted
Done
ReplyInline Actions

Minor:
You can asssume V has pointer type so you don't need to check it.
To get the CallSiteI directly you can call getCtxI().
I think you should even pass CallSiteI->getNextNode() to checkForAllUses because we don't want to see the uses in the call site.

jdoerfert: Minor: You can asssume V has pointer type so you don't need to check it. To get the `CallSiteI`…
pgodeAuthorUnsubmitted
Done
ReplyInline Actions

Thanks for the review comments. I didn't understand the part:

I think you should even pass CallSiteI->getNextNode() to checkForAllUses because we don't want to see the uses in the call site.

I thought that, if we don't have any uses of instruction/value passed to CallSite, before the callsite instruction then we can propagate. CallSiteI->getNextNode() gives me next node after the callsite instruction. Not sure about the reason why we should also have additional call to checkForAllUses.

Should we have something like below.

if (!A.checkForAllUses(UsePred, *this, V, getCtxI())  && !A.checkForAllUses(UsePred, *this, V, getCtxI()->getNextNode()) {
.. 
}
pgode: Thanks for the review comments. I didn't understand the part: >> I think you should even pass…
jdoerfertUnsubmitted
Done
ReplyInline Actions

First, I got confused myself in the last comment. I'll explain what my thinking was and then why it was not want we want anyway:
I thought:

We have a call `call @foo(%v)` and we want to know if `%v` is used *after* the call.
To do that we would look at used reachable from the instruction after the call because we do not want to see the use of `%v` in the call.
That is however not what we actually want to do.

What we want to do is:

Check if there is any use
   - which is not marked `nocapture`, 
   - which is not the call instruction, and
   - from which we can reach the call instruction.
If such a use exists, the value might have been captured already.
If not, it might only be captured by the call instruction or later.
In the former case we need to give up, in the latter we don't.

To achieve this we need to perform the reachability query in the callback (UsePred above). If the User (= U.getUser()) is an instruction that might cause the value to escape, it is not the call instruction (= getCtxI()), and from the user the call instruction is reachable, we give up. Otherwise we continue scanning.

jdoerfert: First, I got confused myself in the last comment. I'll explain what my thinking was and then…
pgodeAuthorUnsubmitted
Done
ReplyInline Actions

Thanks a lot for clarifying. That make perfect sense to me.
I am working on it and will soon submit the next version.

pgode: Thanks a lot for clarifying. That make perfect sense to me. I am working on it and will soon…
jdoerfertUnsubmitted
Done
ReplyInline Actions

Sounds good! Looking forward to it.

jdoerfert: Sounds good! Looking forward to it.
// (iii) Check there is no other pointer argument which could alias with the // (iii) Check there is no other pointer argument which could alias with the
// value. // value.
ImmutableCallSite ICS(&getAnchorValue()); ImmutableCallSite ICS(&getAnchorValue());
for (unsigned i = 0; i < ICS.getNumArgOperands(); i++) { for (unsigned i = 0; i < ICS.getNumArgOperands(); i++) {
if (getArgNo() == (int)i) if (getArgNo() == (int)i)
continue; continue;
const Value *ArgOp = ICS.getArgOperand(i); const Value *ArgOp = ICS.getArgOperand(i);
▲ Show 20 Lines • Show All 2,682 Lines • ▼ Show 20 Linesbool Attributor::isAssumedDead(const AbstractAttribute &AA,
// We actually used liveness information so we have to record a dependence. // We actually used liveness information so we have to record a dependence.
recordDependence(*LivenessAA, AA, DepClassTy::OPTIONAL); recordDependence(*LivenessAA, AA, DepClassTy::OPTIONAL);
return true; return true;
} }
bool Attributor::checkForAllUses( bool Attributor::checkForAllUses(
const function_ref<bool(const Use &, bool &)> &Pred, const function_ref<bool(const Use &, bool &)> &Pred,
const AbstractAttribute &QueryingAA, const Value &V) { const AbstractAttribute &QueryingAA, const Value &V,
const Instruction *ReachableFromI) {
const IRPosition &IRP = QueryingAA.getIRPosition(); const IRPosition &IRP = QueryingAA.getIRPosition();
SmallVector<const Use *, 16> Worklist; SmallVector<const Use *, 16> Worklist;
SmallPtrSet<const Use *, 16> Visited; SmallPtrSet<const Use *, 16> Visited;
for (const Use &U : V.uses()) for (const Use &U : V.uses())
Worklist.push_back(&U); Worklist.push_back(&U);
LLVM_DEBUG(dbgs() << "[Attributor] Got " << Worklist.size() LLVM_DEBUG(dbgs() << "[Attributor] Got " << Worklist.size()
<< " initial uses to check\n"); << " initial uses to check\n");
if (Worklist.empty()) if (Worklist.empty())
return true; return true;
bool AnyDead = false; bool AnyDead = false;
const Function *ScopeFn = IRP.getAnchorScope(); const Function *ScopeFn = IRP.getAnchorScope();
const auto *LivenessAA = const auto *LivenessAA =
ScopeFn ? &getAAFor<AAIsDead>(QueryingAA, IRPosition::function(*ScopeFn), ScopeFn ? &getAAFor<AAIsDead>(QueryingAA, IRPosition::function(*ScopeFn),
/* TrackDependence */ false) /* TrackDependence */ false)
: nullptr; : nullptr;
while (!Worklist.empty()) { while (!Worklist.empty()) {
const Use *U = Worklist.pop_back_val(); const Use *U = Worklist.pop_back_val();
if (!Visited.insert(U).second) if (!Visited.insert(U).second)
continue; continue;
jdoerfertUnsubmitted
Done
ReplyInline Actions

You need to track dependence here or remember if you excluded a use due to reachability and track the dependence then. For liveness we doe this with the AnyDead flag.

jdoerfert: You need to track dependence here or remember if you excluded a use due to reachability and…
LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << "\n"); LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << "\n");
if (Instruction *UserI = dyn_cast<Instruction>(U->getUser())) if (Instruction *UserI = dyn_cast<Instruction>(U->getUser())) {
if (LivenessAA && LivenessAA->isAssumedDead(UserI)) { if (LivenessAA && LivenessAA->isAssumedDead(UserI)) {
LLVM_DEBUG(dbgs() << "[Attributor] Dead user: " << *UserI << ": " LLVM_DEBUG(dbgs() << "[Attributor] Dead user: " << *UserI << ": "
<< *LivenessAA << "\n"); << *LivenessAA << "\n");
AnyDead = true; AnyDead = true;
continue; continue;
} }
// For uses which reachable call instruction.
if (ReachableFromI) {
if (UserI->isSameOperationAs(ReachableFromI)) {
const auto &NoCapture = getAAFor<AANoCapture>(
QueryingAA, IRP);
LLVM_DEBUG(dbgs() << "[Attributor] Use reachable. \n");
return NoCapture.isAssumedNoCaptureMaybeBeforeInstruction();
jdoerfertUnsubmitted
Not Done
ReplyInline Actions

You need to check both ReachableFromI and ReachabilityAA for null in the outer conditional.
If it is *not* reachable we should skip the user, thus continue, otherwise we fall through and call the predicate below.

We should also split the change to checkForAllUses from the rest and make it a separate review.

jdoerfert: You need to check both `ReachableFromI` and `ReachabilityAA` for `null` in the outer…
pgodeAuthorUnsubmitted
Done
ReplyInline Actions

I agree for the null checks and continue. I missed them both.
Can I keep this and create separate review after this ?
As of now, ReachableFromI not equal nullptr value is passed for noalias deduction only.

pgode: I agree for the null checks and continue. I missed them both. Can I keep this and create…
jdoerfertUnsubmitted
Not Done
ReplyInline Actions

You can split this in two reviews. One for the checkForAllUses code and one for the AANoAlias code.
You will not even need to set ReachableFromI from the NoAlias query but we still should keep the functionality to only visit reachable users. It will be useful soon.

jdoerfert: You can split this in two reviews. One for the `checkForAllUses` code and one for the…
jdoerfertUnsubmitted
Not Done
ReplyInline Actions

There is a continue missing in the above conditional.

jdoerfert: There is a `continue` missing in the above conditional.
pgodeAuthorUnsubmitted
Done
ReplyInline Actions

I agree, for unreachable we don't need to check the predicate.

pgode: I agree, for unreachable we don't need to check the predicate.
}
}
}
jdoerfertUnsubmitted
Done
ReplyInline Actions

I don't understand the code after the if (ReachableFromI) condition.
We should not care about the operation here and also not about nocapture because this is a generic utility function.

What you want to check if ReachableFromI is:

  • Query the AAReachability for the function (you can do that before the worklist while loop actually).
  • Ask AAReachability if UserI is reachable from ReachableFromI, if not skip the UserI.
jdoerfert: I don't understand the code after the `if (ReachableFromI)` condition. We should not care about…
bool Follow = false; bool Follow = false;
if (!Pred(*U, Follow)) if (!Pred(*U, Follow))
return false; return false;
if (!Follow) if (!Follow)
continue; continue;
for (const Use &UU : U->getUser()->uses()) for (const Use &UU : U->getUser()->uses())
Worklist.push_back(&UU); Worklist.push_back(&UU);
} }
▲ Show 20 Lines • Show All 1,034 Lines • Show Last 20 Lines