[NFC] Use GetUnderlyingObjects in findAllocaForValue

[vitalybuka]

Summary

Depends on D84621.

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

4358–4359

It seems silly that we have the single object and multi object interface that do different things. Arguably, you would like to write the above code. Maybe we should allow GetUnderlyingObject to (optionally) look through PHI and select instead? Making that happen seems little work but makes these awkward invocations unnecessary. WDYT?

[vitalybuka]

llvm/lib/Analysis/ValueTracking.cpp

4358–4359

To handle select and PHI we need search like in getUnderlyingObjects, which requires Visited and Worklist on the stack.
So we will have add similar silly code into optional part of getUnderlyingObject.
Even if this part is OK, adding new option into public interface looks like adding more complexity then we trying to remove here from non-public part.
Ideally we would like to support select and PHI non-optionally, but this requires some validation of all call sites which is not a trivial piece of work.

Maybe I can do the following.
This is more efficient but it does not look better to me.

template <class F>
static void findUnderlyingObjects(const Value *V, F OnObj, LoopInfo *LI = nullptr,
                                  unsigned MaxLookup = 6) {
  SmallPtrSet<const Value *, 4> Visited;
  SmallVector<const Value *, 4> Worklist;
  Worklist.push_back(V);
  do {
    const Value *P = Worklist.pop_back_val();
    P = getUnderlyingObject(P, MaxLookup);

    if (!Visited.insert(P).second)
      continue;

    if (auto *SI = dyn_cast<SelectInst>(P)) {
      Worklist.push_back(SI->getTrueValue());
      Worklist.push_back(SI->getFalseValue());
      continue;
    }

    if (auto *PN = dyn_cast<PHINode>(P)) {
      // If this PHI changes the underlying object in every iteration of the
      // loop, don't look through it.  Consider:
      //   int **A;
      //   for (i) {
      //     Prev = Curr;     // Prev = PHI (Prev_0, Curr)
      //     Curr = A[i];
      //     *Prev, *Curr;
      //
      // Prev is tracking Curr one iteration behind so they refer to different
      // underlying objects.
      if (!LI || !LI->isLoopHeader(PN->getParent()) ||
          isSameUnderlyingObjectInLoop(PN, LI))
        for (Value *IncValue : PN->incoming_values())
          Worklist.push_back(IncValue);
      continue;
    }

    if (!OnObj(P))
      return;
  } while (!Worklist.empty());
}

void llvm::getUnderlyingObjects(const Value *V,
                                SmallVectorImpl<const Value *> &Objects,
                                LoopInfo *LI, unsigned MaxLookup) {
  findUnderlyingObjects(
      V,
      [&Objects](const Value *V) {
        Objects.push_back(V);
        return true;
      },
      LI, MaxLookup);
}

AllocaInst *llvm::findAllocaForValue(Value *V) {
  const AllocaInst *A = nullptr;
  findUnderlyingObjects(V, [&A](const Value *V) -> bool {
    if (!A)
      A = dyn_cast<AllocaInst>(V);
    else if (A != V)
      A = nullptr;
    return A;
  });
  return const_cast<AllocaInst *>(A);
}

[vitalybuka]

llvm/lib/Analysis/ValueTracking.cpp

4358–4359

Actually OnObj can't be called twice for the same obj, so

AllocaInst *llvm::findAllocaForValue(Value *V) {
  const AllocaInst *A = nullptr;
  findUnderlyingObjects(V, [&A](const Value *V) -> bool {
     A = A ? nullptr : dyn_cast<AllocaInst>(V);
     return A;
  });
  return const_cast<AllocaInst *>(A);
}

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

4358–4359

My main point was that we should merge the object and objects callbacks such that in the former you stop at the second object while in the latter you don't. Basically what you did for the findAlloca case now, except that I think this code should be the behavior of the object API. FindAlloca is then a call and a dyn_cast_or_null. That said, there might be compile time concerns which might justify a flag on the objects API that directly calls what is now getUnderlyingObject. I'm not in favor of the flag FWIW.

Maybe others want to chime in, to name a few @lebedev.ri @efriedma @spatel

[efriedma]

llvm/lib/Analysis/ValueTracking.cpp

4358–4359

Making getUnderlyingObject() as powerful as getUnderlyingObjects() makes sense to me.

[vitalybuka]

update

llvm/lib/Analysis/ValueTracking.cpp

4183–4226

Simple change like this brakes:

Value *llvm::GetUnderlyingObject(Value *V, unsigned MaxLookup) {
  if (!V->getType()->isPointerTy())
    return V;
  for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
    if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
      V = GEP->getPointerOperand();
    } else if (Operator::getOpcode(V) == Instruction::BitCast ||
               Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
      V = cast<Operator>(V)->getOperand(0);
      if (!V->getType()->isPointerTy())
        return V;
    } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
      if (GA->isInterposable())
        return V;
      V = GA->getAliasee();
    } else {
      if (auto *PHI = dyn_cast<PHINode>(V)) {
        // Look through single-arg phi nodes created by LCSSA.
        if (PHI->getNumIncomingValues() == 1) {
          V = PHI->getIncomingValue(0);
          continue;
        } 
        if ((!MaxLookup || MaxLookup > Count + 1) && PHI->getNumIncomingValues() > 1) {
          unsigned NewMaxLookup = MaxLookup ? (MaxLookup - Count - 1) : 0;
          V = nullptr;
          for (Value *IncValue : PHI->incoming_values()) {
            Value* U = getUnderlyingObject(IncValue, NewMaxLookup);
            if (V && V != U)
              return PHI;
            V = U;
          }
          assert(V);
        }
      } else if (auto *Call = dyn_cast<CallBase>(V)) {
        // CaptureTracking can know about special capturing properties of some
        // intrinsics like launder.invariant.group, that can't be expressed with
        // the attributes, but have properties like returning aliasing pointer.
        // Because some analysis may assume that nocaptured pointer is not
        // returned from some special intrinsic (because function would have to
        // be marked with returns attribute), it is crucial to use this function
        // because it should be in sync with CaptureTracking. Not using it may
        // cause weird miscompilations where 2 aliasing pointers are assumed to
        // noalias.
        if (auto *RP = getArgumentAliasingToReturnedPointer(Call, false)) {
          V = RP;
          continue;
        }
      } else if (auto *SI = dyn_cast<SelectInst>(V)) {
        if (MaxLookup || MaxLookup > Count + 1) {
          unsigned NewMaxLookup = MaxLookup ? (MaxLookup - Count - 1) : 0;
          Value* T = getUnderlyingObject(SI->getTrueValue(), NewMaxLookup);
          Value* F = getUnderlyingObject(SI->getFalseValue(), NewMaxLookup);
          return T != F ? V : T;
        }
      }

      return V;
    }
    assert(V->getType()->isPointerTy() && "Unexpected operand type!");
  }
  return V;
}

LLVM :: Analysis/BasicAA/noalias-geps.ll
LLVM :: CodeGen/Hexagon/swp-sigma.ll

BasicAA has strong assumptions about getUnderlyingObject behavior. Maybe some callers as well. We have tens of them.
Even if no other tests fail I don't think it's good idea to change behavior without investigating all callsites. But I don't like to do that.

4358–4359

My main point was that we should merge the object and objects callbacks such that in the former you stop at the second object while in the latter you don't. Basically what you did for the findAlloca case now, except that I think this code should be the behavior of the object API. FindAlloca is then a call and a dyn_cast_or_null. That said, there might be compile time concerns which might justify a flag on the objects API that directly calls what is now getUnderlyingObject. I'm not in favor of the flag FWIW.

Stop on the second one does not work for getUnderlyingObject as it returns deepest unambiguous resolved value.

E.g.
b = PHI x y
c = PHI q s
d = PHI b c
a = d

Here for getUnderlyingObject(a), I'd expect "d", not "b".

Then not sure what is suppose to return for

b = PHI x y
c = PHI x y
d = PHI b c
a = d

or
b = PHI x y
c = PHI x y
e = c
d = PHI b e
a = d

This can be done but it's going to make getUnderlyingObject slower then the current getUnderlyingObjects.

Probably it could be easier if for dis-ambiguity we return nullptr. But then it should be a separate function. I don't like the flag as well.
The separate function could be findAllocaForValue generalized for any value :)

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Analysis/ValueTracking.cpp

static bool isSameUnderlyingObjectInLoop(const PHINode *PN,
   //       int *p = a[i];
   //       ...
   if (auto *Load = dyn_cast<LoadInst>(PrevValue))
     if (!L->isLoopInvariant(Load->getPointerOperand()))
       return false;
   return true;
 }
 
 Value *llvm::getUnderlyingObject(Value *V, unsigned MaxLookup) {
   if (!V->getType()->isPointerTy())
     return V;
   for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
       if (!V->getType()->isPointerTy())
         return V;
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
       if (GA->isInterposable())
         return V;
       V = GA->getAliasee();
     } else {
       if (auto *PHI = dyn_cast<PHINode>(V)) {
         // Look through single-arg phi nodes created by LCSSA.
         if (PHI->getNumIncomingValues() == 1) {
           V = PHI->getIncomingValue(0);
           continue;
         }
       } else if (auto *Call = dyn_cast<CallBase>(V)) {
         // CaptureTracking can know about special capturing properties of some
         // intrinsics like launder.invariant.group, that can't be expressed with
         // the attributes, but have properties like returning aliasing pointer.
         // Because some analysis may assume that nocaptured pointer is not
         // returned from some special intrinsic (because function would have to
         // be marked with returns attribute), it is crucial to use this function
         // because it should be in sync with CaptureTracking. Not using it may
         // cause weird miscompilations where 2 aliasing pointers are assumed to
         // noalias.
         if (auto *RP = getArgumentAliasingToReturnedPointer(Call, false)) {
           V = RP;
           continue;
         }
       }
 
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   }
   return V;
 }
 
-void llvm::getUnderlyingObjects(const Value *V,
-                                SmallVectorImpl<const Value *> &Objects,
-                                LoopInfo *LI, unsigned MaxLookup) {
+template <class F>
+static void findUnderlyingObjects(const Value *V, F OnObj,
+                                  LoopInfo *LI = nullptr,
+                                  unsigned MaxLookup = 6) {
   SmallPtrSet<const Value *, 4> Visited;
   SmallVector<const Value *, 4> Worklist;
   Worklist.push_back(V);
   do {
     const Value *P = Worklist.pop_back_val();
     P = getUnderlyingObject(P, MaxLookup);
 
     if (!Visited.insert(P).second)
if (auto *PN = dyn_cast<PHINode>(P)) {
       // underlying objects.
       if (!LI || !LI->isLoopHeader(PN->getParent()) ||
           isSameUnderlyingObjectInLoop(PN, LI))
         for (Value *IncValue : PN->incoming_values())
           Worklist.push_back(IncValue);
       continue;
     }
 
-    Objects.push_back(P);
+    if (!OnObj(P))
+      return;
   } while (!Worklist.empty());
 }
 
+void llvm::getUnderlyingObjects(const Value *V,
+                                SmallVectorImpl<const Value *> &Objects,
+                                LoopInfo *LI, unsigned MaxLookup) {
+  findUnderlyingObjects(
+      V,
+      [&Objects](const Value *V) {
+        Objects.push_back(V);
+        return true;
+      },
+      LI, MaxLookup);
+}
+
+AllocaInst *llvm::findAllocaForValue(Value *V) {
+  const AllocaInst *A = nullptr;
+  findUnderlyingObjects(V, [&A](const Value *V) -> bool {
+    if (!A)
+      A = dyn_cast<AllocaInst>(V);
+    else if (A != V)
+      A = nullptr;
+    return A;
+  });
+  return const_cast<AllocaInst *>(A);
+}
+
 /// This is the function that does the work of looking through basic
 /// ptrtoint+arithmetic+inttoptr sequences.
 static const Value *getUnderlyingObjectFromInt(const Value *V) {
   do {
     if (const Operator *U = dyn_cast<Operator>(V)) {
       // If we find a ptrtoint, we can transfer control back to the
       // regular getUnderlyingObjectFromInt.
       if (U->getOpcode() == Instruction::PtrToInt)
for (const Value *V : Objs) {
         Objects.clear();
         return false;
       }
       Objects.push_back(const_cast<Value *>(V));
     }
   } while (!Working.empty());
   return true;
 }
 
-static AllocaInst *
-findAllocaForValue(Value *V, DenseMap<Value *, AllocaInst *> &AllocaForValue) {
-  if (AllocaInst *AI = dyn_cast<AllocaInst>(V))
-    return AI;
-  // See if we've already calculated (or started to calculate) alloca for a
-  // given value.
-  auto I = AllocaForValue.find(V);
-  if (I != AllocaForValue.end())
-    return I->second;
-  // Store 0 while we're calculating alloca for value V to avoid
-  // infinite recursion if the value references itself.
-  AllocaForValue[V] = nullptr;
-  AllocaInst *Res = nullptr;
-  if (CastInst *CI = dyn_cast<CastInst>(V))
-    Res = findAllocaForValue(CI->getOperand(0), AllocaForValue);
-  else if (PHINode *PN = dyn_cast<PHINode>(V)) {
-    for (Value *IncValue : PN->incoming_values()) {
-      // Allow self-referencing phi-nodes.
-      if (IncValue == PN)
-        continue;
-      AllocaInst *IncValueAI = findAllocaForValue(IncValue, AllocaForValue);
-      // AI for incoming values should exist and should all be equal.
-      if (IncValueAI == nullptr || (Res != nullptr && IncValueAI != Res))
-        return nullptr;
-      Res = IncValueAI;
-    }
-  } else if (GetElementPtrInst *EP = dyn_cast<GetElementPtrInst>(V)) {
-    Res = findAllocaForValue(EP->getPointerOperand(), AllocaForValue);
-  }
-  if (Res)
-    AllocaForValue[V] = Res;
-  return Res;
-}
-
-AllocaInst *llvm::findAllocaForValue(Value *V) {
-  DenseMap<Value *, AllocaInst *> AllocaForValue;
-  return ::findAllocaForValue(V, AllocaForValue);
-}
-
 static bool onlyUsedByLifetimeMarkersOrDroppableInstsHelper(
     const Value *V, bool AllowLifetime, bool AllowDroppable) {
   for (const User *U : V->users()) {
     const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);
     if (!II)
       return false;
 
     if (AllowLifetime && II->isLifetimeStartOrEnd())
       continue;