This is an archive of the discontinued LLVM Phabricator instance.

[Attributor][Fix] AAHeapToStack and AAIsDead connection
Needs ReviewPublic

Authored by sstefan1 on Jan 11 2020, 1:38 PM.

Details

Summary

Since AAHeapToStack is deleting mallocs/frees AAIsDead needs to be aware
of that. For now, AANoFree uses this to deduce nofree function attribute
when a call to free is deleted.

Event Timeline

sstefan1 created this revision.Jan 11 2020, 1:38 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 11 2020, 1:38 PM

I see where you are going and we need this, however I just fiddled around with the entire isAssumedDead stuff to make the helper methods aware of dead uses (and instructions). I will see how we can combine this best with H2S and report here, OK?

I see where you are going and we need this, however I just fiddled around with the entire isAssumedDead stuff to make the helper methods aware of dead uses (and instructions). I will see how we can combine this best with H2S and report here, OK?

That's ok with me. Are these changes commited?

baziotis added inline comments.Jan 12 2020, 9:56 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
1021–1024

I think it's good to update this comment if these changes are committed - any other relevant as well).

This needs to be integrated with D73313. I suggest we ask H2M if we have a call explicitly if it assumes to remove it.

This needs to be integrated with D73313.

I think there is no integration with D73313 since I only need to change AAIsDeadFunction::IsAssumedDead. If that is correct I think this doesn't depend on D73313.

Also, I'll drop the changes to the existing interfaces, e.g. CheckForAllXXX.

I suggest we ask H2M if we have a call explicitly if it assumes to remove it.

That is kind of the current implementation, but I'll change it a bit so the changes to existing interfaces are not needed.

This needs to be integrated with D73313.

I think there is no integration with D73313 since I only need to change AAIsDeadFunction::IsAssumedDead. If that is correct I think this doesn't depend on D73313.

Also, I'll drop the changes to the existing interfaces, e.g. CheckForAllXXX.

I suggest we ask H2M if we have a call explicitly if it assumes to remove it.

That is kind of the current implementation, but I'll change it a bit so the changes to existing interfaces are not needed.

I was wrong. Currently we ask h2s for all mallocs that are to be deleted and mark them and their respective free calls dead. However, for some attributes (e.g. h2s) we need a way to skip checking whether or not malloc is dead (that is, if h2s marked it to be deleted). Back then the best way to do this seemed to be CheckInstSeparately flag. Could you give another look at the implementation in this patch?

This needs to be integrated with D73313.

I think there is no integration with D73313 since I only need to change AAIsDeadFunction::IsAssumedDead. If that is correct I think this doesn't depend on D73313.

Also, I'll drop the changes to the existing interfaces, e.g. CheckForAllXXX.

I suggest we ask H2M if we have a call explicitly if it assumes to remove it.

That is kind of the current implementation, but I'll change it a bit so the changes to existing interfaces are not needed.

I was wrong. Currently we ask h2s for all mallocs that are to be deleted and mark them and their respective free calls dead. However, for some attributes (e.g. h2s) we need a way to skip checking whether or not malloc is dead (that is, if h2s marked it to be deleted). Back then the best way to do this seemed to be CheckInstSeparately flag. Could you give another look at the implementation in this patch?

I was hoping that after D73313 we could have a check this in AAIsDeadCallSiteReturned. In the init and update we ask H2S (and later others) if they assume to remove the instruction, if so, we consider it dead.

I was hoping that after D73313 we could have a check this in AAIsDeadCallSiteReturned. In the init and update we ask H2S (and later others) if they assume to remove the instruction, if so, we consider it dead.

Sorry for the delay.
Ok, I think this makes much more sense now.

Can you do a rebase on D73313 & D73311? I'm having trouble applying the patches.

I was hoping that after D73313 we could have a check this in AAIsDeadCallSiteReturned. In the init and update we ask H2S (and later others) if they assume to remove the instruction, if so, we consider it dead.

Sorry for the delay.
Ok, I think this makes much more sense now.

Can you do a rebase on D73313 & D73311? I'm having trouble applying the patches.

Done, though I have some minor patches before them I'll commit tomorrow. If you find the time to review the two above I can commit the whole series ;)

Done, though I have some minor patches before them I'll commit tomorrow. If you find the time to review the two above I can commit the whole series ;)

Reviewed.
I'm sorry, but I won't be able to do any real work until the weekend.

sstefan1 updated this revision to Diff 244979.Feb 17 2020, 8:06 AM

Changing the implementation to use new fine-grained liveness helpers.

This is basically what I was hoping for, thx for rebasing it on the new scheme. Some comments inlined.

llvm/include/llvm/Transforms/IPO/Attributor.h
2463

This is "assumed" information, correct? We should put it in the name (or Known if that is what it is)

llvm/lib/Transforms/IPO/Attributor.cpp
2915

Would it work the other way around, as well? Deleting them here not in H2S. If so it would remove the special case here and some code in H2S, right?

3066

Do not track dependences by default but manually register one in the conditional when H2S information is used.


the entire H2s thing should be in an scope like:

} else if (isa<CallBase>(CtxI)) {
<h2s>
}

to avoid calling it if we know its side effect free or not a call.

4928

I think we can just iterate over all of them with some helpers to keep the code simpler:

auto IsI = [I](Instruction *C) { return C == I; };
if (llvm::any_of(MallocCalls, IsI))
  ...
for (auto &It : FreesForMalloc)
  if (llvm::any_of(It.second, IsI))
    ...

wdyt?

7434

I would hope the existing single Attributor::isAssumedDead check would suffice. The problem is we will play whack-a-mole all over the place if we cannot "generalize" liveness queries.

Can you explain why it's not. What would it take to make it work with a single Attributor::isAssumedDead call here, moving the logic into Attributor::isAssumedDead.

sstefan1 marked 5 inline comments as done.Feb 17 2020, 10:02 AM
sstefan1 added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
2463

Makes sense.

llvm/lib/Transforms/IPO/Attributor.cpp
2915

I had this in mind, but I don't think it would work because isAssumedSideEffectFree() will be false.

3066

default tracking was leftover actually. Changes in max iterations should've been a red flag.

If I'm not wrong, everything in here should be a CallBase.

4928

Thanks for the suggestion. That indeed looks nicer :)

7434

Actually it works. I should've taken a closer look at IRPosition::value()...

sstefan1 updated this revision to Diff 244998.Feb 17 2020, 10:03 AM

addressing comments

sstefan1 updated this revision to Diff 245011.Feb 17 2020, 10:39 AM

small update

jdoerfert added inline comments.Feb 17 2020, 5:17 PM
llvm/lib/Transforms/IPO/Attributor.cpp
2915

I see. In that case, can you move the special logic into isAssumedSideEffectFree to cut down on the duplication and allow reuse later on?

3048

This is assumed information, correct? If so, we cannot indicate a fixpoint and we need to record a dependence if we use the information.

4920
if(IsMalloc)
  return llvm::any_of(MallocCalls, IsI);
sstefan1 marked 3 inline comments as done.Feb 18 2020, 11:49 AM
sstefan1 added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
2915

I've given this some more thought. While it would indeed be nicer to delete H2S stuff here as well, I think that can't work. Consider this example from the tests:

define void @nofree_arg_only(i8* %p1, i8* %p2) {
  tail call void @free(i8* %p2)
  tail call void @nofree_func(i8* %p1)
  ret void
}

Here free() is neither nounwind nor readonly but would be considered side effect free because we made isAssumedSideEffectFree consider it that way. As a result, since it is void value, it is deleted. Although it shouldn't have been.

If you still think we can/should do it, let me know.

3048

Correct. Interestingly, though, it doesn't work without indicating fixpoint.

jdoerfert added inline comments.Feb 18 2020, 12:25 PM
llvm/lib/Transforms/IPO/Attributor.cpp
2915

I did confuse you by putting the comment here, sorry. The code I want to move into isAssumedSideEffectFree is the code below, not the code here. By moving the logic from updateImpl into isAssumedSideEffectFree we should be able to remove the code here, that is what I should have said.

Here free() is neither nounwind nor readonly but would be considered side effect free because we made isAssumedSideEffectFree consider it that way.

I don't think this is what should happen. isAssumedSideEffectFree will ask H2S and H2S::isAssumedToBeDeleted() will return false which will cause the normal logic in isAssumedSideEffectFree to continue and conclude we don't know anything about free and we need to assume it has side effects.

3048

"Doesn't work" is a symptom not an explanation ;)

We cannot indicate an optimistic fixpoint based on assumed information. If the tests fail it needs to be investigated why. See my other comment though.

sstefan1 marked 2 inline comments as done.Feb 18 2020, 12:37 PM
sstefan1 added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
2915

That was the case :). The quoted comment was explaining how things would go if I were to move the code from above into the isAssumedSideEffectFree.

I think that should work.

3048

This was a quick comment. Didn't have time to look into it more carefully. I'll take a closer look tomorrow.

sstefan1 updated this revision to Diff 245512.Feb 19 2020, 1:43 PM

small fix

sstefan1 marked 2 inline comments as done.Feb 19 2020, 1:52 PM
sstefan1 added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
2915

Unfortunately, I have to go back to being against this idea as I've stumbled upon another problem...

define void @test3() {
  %1 = tail call noalias i8* @malloc(i64 4)
  tail call void @no_sync_func(i8* %1)
  tail call void @free(i8* %1)
  ret void
}

If isAssumedSideEffectFree() returned true the malloc would end up having live users in no_sync_func(). We need to skip checking areAllUsesAssumedDead for H2S stuff. I'm not sure if sticking with this would be worth it in the end.

3048

H2S stuff needed to be checked before the if statement below. In latter updates IsAssumedSideEffectFree is true but isAssumedSideEffectFree() returns false causing update to return CHANGED.

jdoerfert added inline comments.Feb 19 2020, 2:31 PM
llvm/lib/Transforms/IPO/Attributor.cpp
2915

OK, but we have to avoid duplication of H2S related code (here the ismalloc/isfree query). Having AAIsDead delete the code also has some appeal to it.

What if we add a boolean that tracks if we replace the value and therefore do not need to look at the users. We would not need this change here as isAssumedSideEffectFree returns true then. We also don't need to delete in H2S anymore.

4909
if (BadMallocCalls.count(I))
  return false;
4920

if it is a malloc we don't need to check the free's below, right?

sstefan1 marked 3 inline comments as done.Feb 23 2020, 1:35 PM
sstefan1 added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
2915

I've given this another try.

If we delegate the deletion to AAIsDead we need 2 runs of Attributor. As a result H2S does its job on the first run but only converts mallocs to allocas leaving malloc behind. On the second run, leftover malloc is again converted to alloca and then finally deleted leaving us with 2 allocas. Which is of course not good. The only thing that can be removed from here is isFreeCall check as it has no uses to be replaced with undef.

If we still want avoid deleting stuff in H2S, perhaps H2S needs a rework?
If that is the case I can abandon this and start looking in that direction, if possible. Otherwise, I don't think this is doable...

4909

This doesn't take frees into account.

4920

Right. I'll change this to your suggestion from above.

sstefan1 marked an inline comment as done.Feb 23 2020, 2:08 PM
sstefan1 added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
2915

Another thing that might work is to pass the TargetLibraryInfo to wouldInstructionBeTriviallyDead which would remove the isMallocCall check here, but would end up calling deleteAfterManifest which should be ok since it won't add it if it already exists. Will have to give this a try tomorrow first.

sstefan1 updated this revision to Diff 246261.Feb 24 2020, 11:03 AM

small update.

Can we postpone this until we figured out how AAIsDead and AAUB are working together? We need to figure this out and decide how much interaction with AAIsDead we want, e.g., if a rerun is sufficient do we need to integrate it.

Can we postpone this until we figured out how AAIsDead and AAUB are working together? We need to figure this out and decide how much interaction with AAIsDead we want, e.g., if a rerun is sufficient do we need to integrate it.

Sure, just wanted to check the status.