[AliasSetTracker] Teach AliasSetTracker about MemSetInst

[haicheng]

Summary

This change is to fix the problem discussed here.

In short, if running -licm -loop-idiom on the c-code like this

int	i, j, k;
for (i = 0; i < 1; i++) {
  for (j = 0; j < 2; j++) {
     for (k = 0; k < 10; k++) {
         a[j][k] = 42;
      }
   }
}

loop-idiom turns the store in the inner loop into a small memset in the middle loop and then the small memset into a big memset in the outer loop. But, the middle memset is already tagged by LICM as an unknown instruction in AliasSetTracker and deleting it in loop-idiom can trigger an assertion.

This patch teaches AliasSetTracker about MemSetInst. When deleting the small memset in loop-idiom, AliasSetTracker::ASTCallbackVH::deleted() can properly update the AliasSetTracker.

[mssimpso]

Looks good to me.

[mssimpso]

One comment, actually.

lib/Analysis/AliasSetTracker.cpp

513

Is MSI->getOperand(0) right? I would think we would want to use getDest() here.

[mcrosier]

LGTM, with a small request.

lib/Analysis/AliasSetTracker.cpp

540–541

Please add a FIXME comment for memcpy and memmov. Feel free to fix the issue in a later patch, if you like. Alternatively, please file a bug.

[mcrosier]

Please make sure to include the commit-list when you post the patch. Regardless, I think this one is good to go in..

[haicheng]

Address Matt and Chad's comments.

[uabelho]

I'm not very familiar with this code but at least I've verified it to solve my original problem. Thanks!

[mcrosier]

LGTM. Feel free to commit. Thanks, Haicheng.

[haicheng]

Committed in r261052.

include/llvm/Analysis/AliasSetTracker.h

 #include "llvm/IR/ValueHandle.h"
 #include <vector>
 
 namespace llvm {
 
 class LoadInst;
 class StoreInst;
 class VAArgInst;
+class MemSetInst;
 class AliasSetTracker;
 class AliasSet;
 
 class AliasSet : public ilist_node<AliasSet> {
   friend class AliasSetTracker;
 
   class PointerRec {
     Value *Val;  // The pointer this record corresponds to.
public:
   ///
   /// These methods return true if inserting the instruction resulted in the
   /// addition of a new alias set (i.e., the pointer did not alias anything).
   ///
   bool add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo); // Add a loc.
   bool add(LoadInst *LI);
   bool add(StoreInst *SI);
   bool add(VAArgInst *VAAI);
+  bool add(MemSetInst *MSI);
   bool add(Instruction *I);       // Dispatch to one of the other add methods...
   void add(BasicBlock &BB);       // Add all instructions in basic block
   void add(const AliasSetTracker &AST); // Add alias relations from another AST
   bool addUnknown(Instruction *I);
 
   /// These methods are used to remove all entries that might be aliased by the
   /// specified instruction. These methods return true if any alias sets were
   /// eliminated.
   bool remove(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo);
   bool remove(LoadInst *LI);
   bool remove(StoreInst *SI);
   bool remove(VAArgInst *VAAI);
+  bool remove(MemSetInst *MSI);
   bool remove(Instruction *I);
   void remove(AliasSet &AS);
   bool removeUnknown(Instruction *I);
 
   void clear();
 
   /// Return the alias sets that are active.
   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }

lib/Analysis/AliasSetTracker.cpp

bool AliasSetTracker::add(VAArgInst *VAAI) {
   VAAI->getAAMetadata(AAInfo);
 
   bool NewPtr;
   addPointer(VAAI->getOperand(0), MemoryLocation::UnknownSize, AAInfo,
              AliasSet::ModRefAccess, NewPtr);
   return NewPtr;
 }
 
+bool AliasSetTracker::add(MemSetInst *MSI) {
+  AAMDNodes AAInfo;
+  MSI->getAAMetadata(AAInfo);
+
+  bool NewPtr;
+  uint64_t Len;
+
+  if (ConstantInt *C = dyn_cast<ConstantInt>(MSI->getLength()))
+    Len = C->getZExtValue();
+  else
+    Len = MemoryLocation::UnknownSize;
+
+  AliasSet &AS =
+      addPointer(MSI->getDest(), Len, AAInfo, AliasSet::ModAccess, NewPtr);
+  if (MSI->isVolatile())
+    AS.setVolatile();
+  return NewPtr;
+}
 
 bool AliasSetTracker::addUnknown(Instruction *Inst) {
   if (isa<DbgInfoIntrinsic>(Inst)) 
     return true; // Ignore DbgInfo Intrinsics.
   if (!Inst->mayReadOrWriteMemory())
     return true; // doesn't alias anything
 
   AliasSet *AS = findAliasSetForUnknownInst(Inst);

 bool AliasSetTracker::add(Instruction *I) {
   // Dispatch to one of the other add methods.
   if (LoadInst *LI = dyn_cast<LoadInst>(I))
     return add(LI);
   if (StoreInst *SI = dyn_cast<StoreInst>(I))
     return add(SI);
   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
     return add(VAAI);
+  if (MemSetInst *MSI = dyn_cast<MemSetInst>(I))
+    return add(MSI);
   return addUnknown(I);
+  // FIXME: add support of memcpy and memmove. 
 }
 
 void AliasSetTracker::add(BasicBlock &BB) {
   for (auto &I : BB)
     add(&I);
 }
 
 void AliasSetTracker::add(const AliasSetTracker &AST) {
bool AliasSetTracker::remove(VAArgInst *VAAI) {
 
   AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0),
                                         MemoryLocation::UnknownSize, AAInfo);
   if (!AS) return false;
   remove(*AS);
   return true;
 }
 
+bool AliasSetTracker::remove(MemSetInst *MSI) {
+  AAMDNodes AAInfo;
+  MSI->getAAMetadata(AAInfo);
+  uint64_t Len;
+
+  if (ConstantInt *C = dyn_cast<ConstantInt>(MSI->getLength()))
+    Len = C->getZExtValue();
+  else
+    Len = MemoryLocation::UnknownSize;
+
+  AliasSet *AS = findAliasSetForPointer(MSI->getDest(), Len, AAInfo);
+  if (!AS)
+    return false;
+  remove(*AS);
+  return true;
+}
+
 bool AliasSetTracker::removeUnknown(Instruction *I) {
   if (!I->mayReadOrWriteMemory())
     return false; // doesn't alias anything
 
   AliasSet *AS = findAliasSetForUnknownInst(I);
   if (!AS) return false;
   remove(*AS);
   return true;
 }
 
 bool AliasSetTracker::remove(Instruction *I) {
   // Dispatch to one of the other remove methods...
   if (LoadInst *LI = dyn_cast<LoadInst>(I))
     return remove(LI);
   if (StoreInst *SI = dyn_cast<StoreInst>(I))
     return remove(SI);
   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
     return remove(VAAI);
+  if (MemSetInst *MSI = dyn_cast<MemSetInst>(I))
+    return remove(MSI);
   return removeUnknown(I);
+  // FIXME: add support of memcpy and memmove. 
 }
 
 
 // deleteValue method - 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.
 //

test/Transforms/LICM/AliasSetMemSet.ll

+; RUN: opt < %s -loop-deletion -licm -loop-idiom -disable-output
+; Check no assertion when loop-idiom deletes the MemSet already analyzed by licm
+define void @set_array() {
+  br i1 false, label %bb3.preheader.lr.ph, label %bb9
+
+bb3.preheader.lr.ph:                              ; preds = %0
+  br label %bb3.preheader
+
+bb4:                                              ; preds = %bb4.lr.ph, %bb7
+  %j.3.06 = phi i8 [ %j.3.17, %bb4.lr.ph ], [ %_tmp13, %bb7 ]
+  br label %bb6
+
+bb6:                                              ; preds = %bb4, %bb6
+  %k.4.04 = phi i8 [ 0, %bb4 ], [ %_tmp9, %bb6 ]
+  %_tmp31 = sext i8 %j.3.06 to i64
+  %_tmp4 = mul i64 %_tmp31, 10
+  %_tmp5 = getelementptr i8, i8* undef, i64 %_tmp4
+  %_tmp7 = getelementptr i8, i8* %_tmp5, i8 %k.4.04
+  store i8 42, i8* %_tmp7
+  %_tmp9 = add i8 %k.4.04, 1
+  %_tmp11 = icmp slt i8 %_tmp9, 10
+  br i1 %_tmp11, label %bb6, label %bb7
+
+bb7:                                              ; preds = %bb6
+  %_tmp13 = add i8 %j.3.06, 1
+  %_tmp15 = icmp slt i8 %_tmp13, 2
+  br i1 %_tmp15, label %bb4, label %bb3.bb1.loopexit_crit_edge
+
+bb3.bb1.loopexit_crit_edge:                       ; preds = %bb7
+  %split = phi i8 [ %_tmp13, %bb7 ]
+  br label %bb1.loopexit
+
+bb1.loopexit:                                     ; preds = %bb3.bb1.loopexit_crit_edge, %bb3.preheader
+  %j.3.0.lcssa = phi i8 [ %split, %bb3.bb1.loopexit_crit_edge ], [ %j.3.17, %bb3.preheader ]
+  br i1 false, label %bb3.preheader, label %bb1.bb9_crit_edge
+
+bb3.preheader:                                    ; preds = %bb3.preheader.lr.ph, %bb1.loopexit
+  %j.3.17 = phi i8 [ undef, %bb3.preheader.lr.ph ], [ %j.3.0.lcssa, %bb1.loopexit ]
+  %_tmp155 = icmp slt i8 %j.3.17, 2
+  br i1 %_tmp155, label %bb4.lr.ph, label %bb1.loopexit
+
+bb4.lr.ph:                                        ; preds = %bb3.preheader
+  br label %bb4
+
+bb1.bb9_crit_edge:                                ; preds = %bb1.loopexit
+  br label %bb9
+
+bb9:                                              ; preds = %bb1.bb9_crit_edge, %0
+  ret void
+}
+