[Attributor][Fix] Initialize the cache prior to using it

[jdoerfert]

Summary

There were segfaults as we modified and iterated the instruction maps in
the cache at the same time. This was happening because we created new
instructions while we populated the cache. This fix changes the order
in which we perform these actions. First, the caches for the whole
module are created, then we start to create abstract attributes.

I don't have a unit test but the LLVM test suite exposes this problem.

[jdoerfert]

Update tests

[xbolva00]

llvm/lib/Transforms/IPO/Attributor.cpp

3051

Check ´LivenessAA´ before loop

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

3051

I don't think that is practical. If LivenessAA is not null, we would still need a way to indicate it can be dereferenced. Pred should be executed even if LivenessAA is null.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

3051

I would need to duplicate the loop (as @sstefan1 noted) which is a compiler task ;)

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

struct Attributor {
   ///
   /// Note that abstract attribute instances are generally created even if the
   /// IR already contains the information they would deduce. The most important
   /// reason for this is the single interface, the one of the abstract attribute
   /// instance, which can be queried without the need to look at the IR in
   /// various places.
   void identifyDefaultAbstractAttributes(Function &F);
 
+  /// Initialize the information cache for queries regarding function \p F.
+  ///
+  /// This method needs to be called for all function that might be looked at
+  /// through the information cache interface *prior* to looking at them.
+  void initializeInformationCache(Function &F);
+
   /// Mark the internal function \p F as live.
   ///
   /// This will trigger the identification and initialization of attributes for
   /// \p F.
   void markLiveInternalFunction(const Function &F) {
     assert(F.hasInternalLinkage() &&
             "Only internal linkage is assumed dead initially.");
     identifyDefaultAbstractAttributes(const_cast<Function &>(F));

llvm/lib/Transforms/IPO/Attributor.cpp

struct AAIsDeadImpl : public AAIsDead {
   void initialize(Attributor &A) override {
     const Function *F = getAssociatedFunction();
     if (F && !F->isDeclaration())
       exploreFromEntry(A, F);
   }
 
   void exploreFromEntry(Attributor &A, const Function *F) {
     ToBeExploredPaths.insert(&(F->getEntryBlock().front()));
-    assumeLive(A, F->getEntryBlock());
 
     for (size_t i = 0; i < ToBeExploredPaths.size(); ++i)
       if (const Instruction *NextNoReturnI =
               findNextNoReturn(A, ToBeExploredPaths[i]))
         NoReturnCalls.insert(NextNoReturnI);
+
+    // Mark the block live after we looked for no-return instructions.
+    assumeLive(A, F->getEntryBlock());
   }
 
   /// Find the next assumed noreturn instruction in the block of \p I starting
   /// from, thus including, \p I.
   ///
   /// The caller is responsible to monitor the ToBeExploredPaths set as new
   /// instructions discovered in other basic block will be placed in there.
   ///
if (!AARetVal.getState().isValidState())
     return false;
 
   return AARetVal.checkForAllReturnedValuesAndReturnInsts(
       [&](Value &RV, const SmallSetVector<ReturnInst *, 4> &) {
         return Pred(RV);
       });
 }
 
+static bool
+checkForAllInstructionsImpl(InformationCache::OpcodeInstMapTy &OpcodeInstMap,
+                            const function_ref<bool(Instruction &)> &Pred,
+                            const AAIsDead *LivenessAA, bool &AnyDead,
+                            const ArrayRef<unsigned> &Opcodes) {
+  for (unsigned Opcode : Opcodes) {
+    for (Instruction *I : OpcodeInstMap[Opcode]) {
+      // Skip dead instructions.
+      if (LivenessAA && LivenessAA->isAssumedDead(I)) {
+        AnyDead = true;
+        continue;
+      }
+
+      if (!Pred(*I))
+        return false;
+    }
+  }
+  return true;
+}
+
 bool Attributor::checkForAllInstructions(
     const llvm::function_ref<bool(Instruction &)> &Pred,
     const AbstractAttribute &QueryingAA, const ArrayRef<unsigned> &Opcodes) {
 
   const IRPosition &IRP = QueryingAA.getIRPosition();
   // Since we need to provide instructions we have to have an exact definition.
   const Function *AssociatedFunction = IRP.getAssociatedFunction();
   if (!AssociatedFunction)
     return false;
 
   // TODO: use the function scope once we have call site AAReturnedValues.
   const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
   const auto &LivenessAA =
       getAAFor<AAIsDead>(QueryingAA, QueryIRP, /* TrackDependence */ false);
   bool AnyDead = false;
 
   auto &OpcodeInstMap =
       InfoCache.getOpcodeInstMapForFunction(*AssociatedFunction);
-  for (unsigned Opcode : Opcodes) {
-    for (Instruction *I : OpcodeInstMap[Opcode]) {
-      // Skip dead instructions.
-      if (LivenessAA.isAssumedDead(I)) {
-        AnyDead = true;
-        continue;
-      }
-
-      if (!Pred(*I))
-        return false;
-    }
-  }
+  if (!checkForAllInstructionsImpl(OpcodeInstMap, Pred, &LivenessAA, AnyDead, Opcodes))
 
   // If we actually used liveness information so we have to record a dependence.
   if (AnyDead)
     recordDependence(LivenessAA, QueryingAA);
 
   return true;
 }
 
errs() << "\n[Attributor] Fixpoint iteration done after: "
            << " iterations\n";
     llvm_unreachable("The fixpoint was not reached with exactly the number of "
                      "specified iterations!");
   }
 
   return ManifestChange;
 }
 
+void Attributor::initializeInformationCache(Function &F) {
+
+  // Walk all instructions to find interesting instructions that might be
+  // queried by abstract attributes during their initialization or update.
+  // This has to happen before we create attributes.
+  auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
+  auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
+
+  for (Instruction &I : instructions(&F)) {
+    bool IsInterestingOpcode = false;
+
+    // To allow easy access to all instructions in a function with a given
+    // opcode we store them in the InfoCache. As not all opcodes are interesting
+    // to concrete attributes we only cache the ones that are as identified in
+    // the following switch.
+    // Note: There are no concrete attributes now so this is initially empty.
+    switch (I.getOpcode()) {
+    default:
+      assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
+             "New call site/base instruction type needs to be known int the "
+             "Attributor.");
+      break;
+    case Instruction::Load:
+      // The alignment of a pointer is interesting for loads.
+    case Instruction::Store:
+      // The alignment of a pointer is interesting for stores.
+    case Instruction::Call:
+    case Instruction::CallBr:
+    case Instruction::Invoke:
+    case Instruction::CleanupRet:
+    case Instruction::CatchSwitch:
+    case Instruction::Resume:
+    case Instruction::Ret:
+      IsInterestingOpcode = true;
+    }
+    if (IsInterestingOpcode)
+      InstOpcodeMap[I.getOpcode()].push_back(&I);
+    if (I.mayReadOrWriteMemory())
+      ReadOrWriteInsts.push_back(&I);
+  }
+}
+
 void Attributor::identifyDefaultAbstractAttributes(Function &F) {
   if (!VisitedFunctions.insert(&F).second)
     return;
 
   IRPosition FPos = IRPosition::function(F);
 
   // Check for dead BasicBlocks in every function.
   // We need dead instruction detection because we do not want to deal with
if (Arg.getType()->isPointerTy()) {
       // Every argument with pointer type might be marked align.
       getOrCreateAAFor<AAAlign>(ArgPos);
 
       // Every argument with pointer type might be marked nocapture.
       getOrCreateAAFor<AANoCapture>(ArgPos);
     }
   }
 
-  // Walk all instructions to find more attribute opportunities and also
-  // interesting instructions that might be queried by abstract attributes
-  // during their initialization or update.
-  auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
-  auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
-
-  for (Instruction &I : instructions(&F)) {
-    bool IsInterestingOpcode = false;
-
-    // To allow easy access to all instructions in a function with a given
-    // opcode we store them in the InfoCache. As not all opcodes are interesting
-    // to concrete attributes we only cache the ones that are as identified in
-    // the following switch.
-    // Note: There are no concrete attributes now so this is initially empty.
-    switch (I.getOpcode()) {
-    default:
-      assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
-             "New call site/base instruction type needs to be known int the "
-             "attributor.");
-      break;
-    case Instruction::Load:
-      // The alignment of a pointer is interesting for loads.
-      getOrCreateAAFor<AAAlign>(
-          IRPosition::value(*cast<LoadInst>(I).getPointerOperand()));
-      break;
-    case Instruction::Store:
-      // The alignment of a pointer is interesting for stores.
-      getOrCreateAAFor<AAAlign>(
-          IRPosition::value(*cast<StoreInst>(I).getPointerOperand()));
-      break;
-    case Instruction::Call:
-    case Instruction::CallBr:
-    case Instruction::Invoke:
-    case Instruction::CleanupRet:
-    case Instruction::CatchSwitch:
-    case Instruction::Resume:
-    case Instruction::Ret:
-      IsInterestingOpcode = true;
-    }
-    if (IsInterestingOpcode)
-      InstOpcodeMap[I.getOpcode()].push_back(&I);
-    if (I.mayReadOrWriteMemory())
-      ReadOrWriteInsts.push_back(&I);
-
+  auto CallSitePred = [&](Instruction &I) -> bool {
     CallSite CS(&I);
-    if (CS && CS.getCalledFunction()) {
+    if (CS.getCalledFunction()) {
       for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) {
         if (!CS.getArgument(i)->getType()->isPointerTy())
           continue;
         IRPosition CSArgPos = IRPosition::callsite_argument(CS, i);
 
         // Call site argument attribute "non-null".
         getOrCreateAAFor<AANonNull>(CSArgPos);
 
         // Call site argument attribute "no-alias".
         getOrCreateAAFor<AANoAlias>(CSArgPos);
 
         // Call site argument attribute "dereferenceable".
         getOrCreateAAFor<AADereferenceable>(CSArgPos);
 
         // Call site argument attribute "align".
         getOrCreateAAFor<AAAlign>(CSArgPos);
       }
     }
-  }
+    return true;
+  };
+
+  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
+  bool Success, AnyDead = false;
+  Success = checkForAllInstructionsImpl(
+      OpcodeInstMap, CallSitePred, nullptr, AnyDead,
+      {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
+       (unsigned)Instruction::Call});
+  (void)Success;
+  assert(Success && !AnyDead && "Expected the check call to be successful!");
+
+  auto LoadStorePred = [&](Instruction &I) -> bool {
+    if (isa<LoadInst>(I))
+      getOrCreateAAFor<AAAlign>(
+          IRPosition::value(*cast<LoadInst>(I).getPointerOperand()));
+    else
+      getOrCreateAAFor<AAAlign>(
+          IRPosition::value(*cast<StoreInst>(I).getPointerOperand()));
+    return true;
+  };
+  Success = checkForAllInstructionsImpl(
+      OpcodeInstMap, LoadStorePred, nullptr, AnyDead,
+      {(unsigned)Instruction::Load, (unsigned)Instruction::Store});
+  (void)Success;
+  assert(Success && !AnyDead && "Expected the check call to be successful!");
 }
 
 /// Helpers to ease debugging through output streams and print calls.
 ///
 ///{
 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
   return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
 }
static bool runAttributorOnModule(Module &M) {
   LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
                     << " functions.\n");
 
   // Create an Attributor and initially empty information cache that is filled
   // while we identify default attribute opportunities.
   InformationCache InfoCache(M.getDataLayout());
   Attributor A(InfoCache, DepRecInterval);
 
+  for (Function &F : M)
+    A.initializeInformationCache(F);
+
   for (Function &F : M) {
     if (F.hasExactDefinition())
       NumFnWithExactDefinition++;
     else
       NumFnWithoutExactDefinition++;
 
     // For now we ignore naked and optnone functions.
     if (F.hasFnAttribute(Attribute::Naked) ||

llvm/test/Transforms/FunctionAttrs/align.ll

-; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=7 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Test cases specifically designed for "align" attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 
 
 ; TEST 1

llvm/test/Transforms/FunctionAttrs/arg_returned.ll

 ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR
-; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=9 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 ; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -functionattrs -S < %s | FileCheck %s --check-prefix=BOTH
 ;
 ; Test cases specifically designed for the "returned" argument attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 ;
 
 ; TEST SCC test returning an integer value argument
 ;

llvm/test/Transforms/FunctionAttrs/dereferenceable.ll

-; RUN: opt -attributor -attributor-manifest-internal --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR
+; RUN: opt -attributor -attributor-manifest-internal --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR
 
 
 declare void @deref_phi_user(i32* %a);
 
 ; TEST 1
 ; take mininimum of return values
 ;
 define i32* @test1(i32* dereferenceable(4) %0, double* dereferenceable(8) %1, i1 zeroext %2) local_unnamed_addr {

llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll

-; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s
 ;
 ; Test cases specifically designed for the "no-return" function attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 
 ; TEST 1, singleton SCC void return type

llvm/test/Transforms/FunctionAttrs/internal-noalias.ll

-; RUN: opt -S -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 < %s | FileCheck %s
+; RUN: opt -S -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=4 < %s | FileCheck %s
 
 define dso_local i32 @visible(i32* noalias %A, i32* noalias %B) #0 {
 entry:
   %call1 = call i32 @noalias_args(i32* %A, i32* %B)
   %call2 = call i32 @noalias_args_argmem(i32* %A, i32* %B)
   %add = add nsw i32 %call1, %call2
   ret i32 %add
 }

llvm/test/Transforms/FunctionAttrs/liveness.ll

-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=11 -S < %s | FileCheck %s
+; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s
 
 declare void @no_return_call() nofree noreturn nounwind readnone
 
 declare void @normal_call() readnone
 
 declare i32 @foo()
 
 declare i32 @foo_noreturn_nounwind() noreturn nounwind

llvm/test/Transforms/FunctionAttrs/noalias_returned.ll

-; RUN: opt -S -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=5 < %s | FileCheck %s
+; RUN: opt -S -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s | FileCheck %s
 
 ; TEST 1 - negative.
 
 ; void *G;
 ; void *foo(){
 ;   void *V = malloc(4);
 ;   G = V;
 ;   return V;

llvm/test/Transforms/FunctionAttrs/nofree-attributor.ll

 ; RUN: opt -functionattrs --disable-nofree-inference=false -S < %s | FileCheck %s --check-prefix=FNATTR
-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=7 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=4 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Test cases specifically designed for the "nofree" function attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 
 ; Free functions
 declare void @free(i8* nocapture) local_unnamed_addr #1

llvm/test/Transforms/FunctionAttrs/nonnull.ll

 ; RUN: opt -S -functionattrs -enable-nonnull-arg-prop %s | FileCheck %s --check-prefixes=BOTH,FNATTR
 ; RUN: opt -S -passes=function-attrs -enable-nonnull-arg-prop %s | FileCheck %s --check-prefixes=BOTH,FNATTR
-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=8 -S < %s | FileCheck %s --check-prefixes=BOTH,ATTRIBUTOR
+; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=7 -S < %s | FileCheck %s --check-prefixes=BOTH,ATTRIBUTOR
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 declare nonnull i8* @ret_nonnull()
 
 ; Return a pointer trivially nonnull (call return attribute)
 define i8* @test1() {
 ; BOTH: define nonnull i8* @test1

llvm/test/Transforms/FunctionAttrs/noreturn_async.ll

-; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s
 ;
 ; This file is the same as noreturn_sync.ll but with a personality which
 ; indicates that the exception handler *can* catch asynchronous exceptions. As
 ; a consequence, invokes to noreturn and nounwind functions are not translated
 ; to calls followed by an unreachable but the unwind edge is considered live.
 ;
 ; https://reviews.llvm.org/D59978#inline-586873
 ;

llvm/test/Transforms/FunctionAttrs/noreturn_sync.ll

-; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=4 -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s
 ;
 ; This file is the same as noreturn_async.ll but with a personality which
 ; indicates that the exception handler *cannot* catch asynchronous exceptions.
 ; As a consequence, invokes to noreturn and nounwind functions are translated
 ; to calls followed by an unreachable.
 ;
 ; https://reviews.llvm.org/D59978#inline-586873
 ;

llvm/test/Transforms/FunctionAttrs/nosync.ll

 ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR
-; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Test cases designed for the nosync function attribute.
 ; FIXME's are used to indicate problems and missing attributes.
 
 ; struct RT {
 ;   char A;
 ;   int B[10][20];

llvm/test/Transforms/FunctionAttrs/nounwind.ll

 ; RUN: opt < %s -functionattrs -S | FileCheck %s
-; RUN: opt < %s -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=4 -S | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt < %s -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S | FileCheck %s --check-prefix=ATTRIBUTOR
 
 ; TEST 1
 ; CHECK: Function Attrs: norecurse nounwind readnone
 ; CHECK-NEXT: define i32 @foo1()
 ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind
 ; ATTRIBUTOR-NEXT: define i32 @foo1()
 define i32 @foo1() {
   ret i32 1

llvm/test/Transforms/FunctionAttrs/willreturn.ll

 ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR
-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=7 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Test cases specifically designed for the "willreturn" function attribute.
 ; We use FIXME's to indicate problems and missing attributes.