Page MenuHomePhabricator

[NFC] Use GetUnderlyingObjects in findAllocaForValue
Changes PlannedPublic

Authored by vitalybuka on Jul 29 2020, 7:50 PM.

Details

Summary

Depends on D84621.

Diff Detail

Event Timeline

vitalybuka created this revision.Jul 29 2020, 7:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 29 2020, 7:50 PM
vitalybuka requested review of this revision.Jul 29 2020, 7:50 PM
jdoerfert added inline comments.
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 added inline comments.Jul 31 2020, 3:15 AM
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 added inline comments.Jul 31 2020, 4:00 AM
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 added inline comments.
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 added inline comments.Aug 7 2020, 12:36 PM
llvm/lib/Analysis/ValueTracking.cpp
4358–4359

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

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 :)

vitalybuka planned changes to this revision.Wed, Aug 26, 10:33 PM