[WIP][LICM] Just rely on AA rather than special case calls

[reames]

Summary

Obviously, not ready to check in... I was thinking about the assume and guard patches currently out for review and/or recently landed by Max and I. Something was really bugging me, and I finally realized what it was. The code we were adding in LICM was essentially duplicating support already in AliasSetTracker and BasicAA. We were extending the existing code structure, but it raised the question of whether this was the right approach.

This patch demonstrates that yes, all the special casing can be deleted. It needs cleanup (and a lot more testing), but it's rather telling there are no test changes observed. And BasicAA+AST is generally more powerful than the special cases which previously was in LICM. (I need to find such an example for a test.)

Anyone see a problem with this basic idea? I'm worried this is too good to be true and I must be missing something...

[reames]

This was too good to be true. The patch made an important conceptual mistake which is that it assumes an instruction maps to a single alias set. In general, this is not true. It may instead map to several distinct alias sets. For a bit more discussion of this, see https://reviews.llvm.org/D50730.

You could extend this approach to multiple aliasing sets, but once you do, you're basically back to the code I was replacing with an extra layer of abstraction added. Overall, that's not a net win.

include/llvm/Analysis/AliasSetTracker.h

AliasSet &addPointer(Value *P, LocationSize Size, const AAMDNodes &AAInfo,
                        AliasSet::AccessLattice E);
   AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
                                      const AAMDNodes &AAInfo);
 
   /// Merge all alias sets into a single set that is considered to alias any
   /// pointer.
   AliasSet &mergeAllAliasSets();
 
+public: // HACK: fixme
   AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
 };
 
 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
   AST.print(OS);
   return OS;
 }
 
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_ALIASSETTRACKER_H

lib/Transforms/Scalar/LICM.cpp

if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     // Don't sink or hoist dbg info; it's legal, but not useful.
     if (isa<DbgInfoIntrinsic>(I))
       return false;
 
     // Don't sink calls which can throw.
     if (CI->mayThrow())
       return false;
 
+#if 0
     if (Function *F = CI->getCalledFunction())
         switch (F->getIntrinsicID()) {
         default: break;
         // TODO: support invariant.start, and experimental.guard here
         case Intrinsic::assume:
           // Assumes don't actually alias anything or throw
           return true;
         };
-    
     // Handle simple cases by querying alias analysis.
     FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
     if (Behavior == FMRB_DoesNotAccessMemory)
       return true;
     if (AliasAnalysis::onlyReadsMemory(Behavior)) {
       // A readonly argmemonly function only reads from memory pointed to by
       // it's arguments with arbitrary offsets.  If we can prove there are no
       // writes to this memory in the loop, we can hoist or sink.
       if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) {
         for (Value *Op : CI->arg_operands())
           if (Op->getType()->isPointerTy() &&
               pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize,
                                        AAMDNodes(), CurAST))
             return false;
         return true;
       }
       
+
       // If this call only reads from memory and there are no writes to memory
       // in the loop, we can hoist or sink the call as appropriate.
       if (isReadOnly(CurAST))
         return true;
     }
+#endif
 
-    // FIXME: This should use mod/ref information to see if we can hoist or
-    // sink the call.
+    AliasSet *AS = CurAST->findAliasSetForUnknownInst(CI);
+    if (!AS)
+      // Was considered by AST not to alias any possible memory location
+      return true;
+    if (!AS->isMod())
+      // The call (which must be readonly per AST) does read memory clobbered
+      // in the loop.
+      return true;
 
+#if 1
+    // May contain a clobber, give up!
     return false;
+#else
+    // Now check for a uniquely writing instruction within the loop.  In this
+    // case, the value written can't be overwritten or read within the loop.
+    // NOTE: Drop in first patch.
+    auto *UniqueI = AS->getUniqueInstruction();
+    if (!UniqueI)
+      // other memory op, give up
+      return false;
+    assert(UniqueI == CI && "AS must contain FI");
+    return true;
+#endif
   } else if (auto *FI = dyn_cast<FenceInst>(&I)) {
     // Fences alias (most) everything to provide ordering.  For the moment,
     // just give up if there are any other memory operations in the loop.
     auto Begin = CurAST->begin();
     assert(Begin != CurAST->end() && "must contain FI");
     if (std::next(Begin) != CurAST->end())
       // constant memory for instance, TODO: handle better
       return false;