[AliasSetTracker] Actually delete instructions from the AliasSetTracker.

[asbirlea]

Summary

When instructions are added, it's not the instruction being added, but its pointer.
The only actual instructions that are added are the unknown ones.
Trying to make some sense of this by actually removing pointers when an instruction is removed.
Oddly, this patch doesn't break anything.

Sending the changes to perhaps makes some sense on the purpose of the removeValue() function.
These changes are incomplete, given the special handling of arguments for callsites when adding an instruction,
but it's deleting more than before...

[MaskRay]

lib/Analysis/AliasSetTracker.cpp

557

deleteValue((Value *)I);

[asbirlea]

clang-format. Thank you!

[reames]

Hm, can I ask what problem you were originally trying to solve? From a quick search, this code is only invoked through the value handle deleted callback. In which case, the value being deleted is the pointer itself, not the original using instruction.

This feels like possibly a solution in search of a problem?

lib/Analysis/AliasSetTracker.cpp

555

I get what you're going for, but this is not enough. Some instructions (calls) can map to multiple memory locations. You're also not removing unknown instructions.

lib/Transforms/Scalar/LICM.cpp

318–320

It took me a second to see why this was necessary. This change actually worries me a bit since it implies we may have other cases which need updated after your change.

[reames]

In D53786#1279569, @reames wrote:

This feels like possibly a solution in search of a problem?

One potentially problematic scenario in the current code would be if someone recursively deleted a user instruction inside an AST iteration loop. I think that would delete the pointer value, and if that was the last value in a given AS, invalidate the iteration.

What I'm not entirely clear about is why we care about deleting empty AliasSets from the AST eagerly? That's probably a deeper design question though.

[asbirlea]

I agree with all your points! Thank you for following up.

The issue is, we have this "deleteValue" which, AFAICT, is only called from LICM, only when removing dead instructions.

But, the AST has pointers + unknown instructions. So calling deleteValue(I) never removes pointers, only the unknown instructions.
I was attempting to see what happens if I do make it remove the pointers, when given an Instruction. But that's not nearly enough or, in my mind, correct.

1. It's not enough, because when adding an instruction we may add more than a pointer (such as arguments added for a CallSite), just like you said.
2. It's not correct, because when removing an instruction with pointer Ptr, we're removing Ptr from the set, even if there may be other instructions modifying that Ptr.

Hence my surprise that this patch is not breaking anything :)

Now, when actually removing pointers in LICM we're now invalidating the iterator over alias sets, hence the change you noticed that's worrying. I cannot see other cases where this would happen.
Before, we were not removing anything, because that part is doing promotion, and we're never promoting unknown instructions, hence the calls to deleteValue in that part of LICM are pretty much no-ops.

Broader question is, as you very well put it: why are we removing things? Or better phrased: why are we attempting to remove things?
If we really care about removed instructions to reflect in the AST, this patch needs a rewrite.
If we don't care about removed instructions, then the "deleteValue()" API and its uses can *mostly* all go away.

(I can see one potential use case: call deleteValue(I) when sinking/hoisting if the instruction is dead, which may make an alias set free of unknown instructions and hence promotable; but then deleteValue could be renamed deleteUnknownInstruction and it would not be called anywhere in the promotion section, so we wouldn't worry about potential iterator invalidations.)

[asbirlea]

lib/Analysis/AliasSetTracker.cpp

555

You're right about the unknown instructions. I had thought that at least we're removing those, but they're never added to the PointerMap.
So, yeah, I don't understand the purpose of deleteValue() at all.
AFAICT, all these calls and the API can be dropped.

[mkazantsev]

Is it possible to write a test on that?

lib/Analysis/AliasSetTracker.cpp

554

Does it make sense to name it deleteInstruction and remove the cast below?

[asbirlea]

Let me re-purpose this patch:
Is there a point to having deleteValue()?
Is there a point to having the ref count (addRef, dropRef) for alias sets?

AFAICT these are incomplete and not used.

[mkazantsev]

Unfortunately I am not familiar enough with AliasSetTracker to answer that question. We should maybe wait for @reames to clarify it.

[chandlerc]

In D53786#1281557, @asbirlea wrote:

Let me re-purpose this patch:
Is there a point to having deleteValue()?
Is there a point to having the ref count (addRef, dropRef) for alias sets?

AFAICT these are incomplete and not used.

Any update here? Or should this just be a separate patch?

[asbirlea]

I'm going to drop this for now.

include/llvm/Analysis/AliasSetTracker.h

public:
   /// Return the underlying alias analysis object used by this tracker.
   AliasAnalysis &getAliasAnalysis() const { return AA; }
 
   /// This method is used to remove a pointer value from the AliasSetTracker
   /// entirely. It should be used when an instruction is deleted from the
   /// program to update the AST. If you don't use this, you would have dangling
   /// pointers to deleted instructions.
   void deleteValue(Value *PtrVal);
+  void deleteValue(Instruction *I);
 
   /// This method should be used whenever a preexisting value in the program is
   /// copied or cloned, introducing a new value.  Note that it is ok for clients
   /// that use this method to introduce the same value multiple times: if the
   /// tracker already knows about a value, it will ignore the request.
   void copyValue(Value *From, Value *To);
 
   using iterator = ilist<AliasSet>::iterator;

lib/Analysis/AliasSetTracker.cpp

void AliasSetTracker::deleteValue(Value *PtrVal) {
   }
 
   // Stop using the alias set.
   AS->dropRef(*this);
 
   PointerMap.erase(I);
 }
 
+void AliasSetTracker::deleteValue(Instruction *I) {
+  auto Loc = MemoryLocation::getOrNone(I);
+  if (Loc == None)
+    deleteValue((Value*) I);
+  else
+    deleteValue(const_cast<Value*>(Loc->Ptr));
+}
+
 // copyValue - This method should be used whenever a preexisting value in the
 // program is copied or cloned, introducing a new value.  Note that it is ok for
 // clients that use this method to introduce the same value multiple times: if
 // the tracker already knows about a value, it will ignore the request.
 //
 void AliasSetTracker::copyValue(Value *From, Value *To) {
   // First, look up the PointerRec for this pointer.
   PointerMapType::iterator I = PointerMap.find_as(From);

lib/Transforms/Scalar/LICM.cpp

if (!HasCatchSwitch) {
       for (BasicBlock *ExitBlock : ExitBlocks)
         InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
 
       PredIteratorCache PIC;
 
       bool Promoted = false;
 
       // Loop over all of the alias sets in the tracker object.
-      for (AliasSet &AS : *CurAST) {
+      for (auto ASItB = CurAST->begin(), ASItE = CurAST->end(); ASItB != ASItE ; ) {
+        auto &AS = *ASItB;
+        ++ASItB;
         // We can promote this alias set if it has a store, if it is a "Must"
         // alias set, if the pointer is loop invariant, and if we are not
         // eliminating any volatile loads or stores.
         if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
             !L->isLoopInvariant(AS.begin()->getValue()))
           continue;
 
         assert(