This is an archive of the discontinued LLVM Phabricator instance.

[clang][dataflow] When checking `ExprToLoc` convergence, only consider children of block terminator.
AbandonedPublic

Authored by mboehme on Jul 31 2023, 2:38 AM.

Details

Reviewers
NoQ
Summary

The only entries in ExprToLoc that will be read by a different block are the direct children of the block terminator (if one exists). For the purposes of determining whether ExprToLoc has converged, it is therefore sufficient to look at these entries, as any differences in other entries will not be seen by other blocks.

The other entries in ExprToLoc are only read during processing of the block that contains the corresponding expressions. To be clear, these entries can affect the results of the block, but only indirectly, in one of two ways:

  • If they are indirect descendants of the terminator and therefore affect the values of the terminator's direct children.
  • If they affect the entries in one of the other mappings in Environment.

Before this patch, we were comparing all entries in ExprToLoc, even if they were never accessed by other blocks, which could cause non-convergence. This patch adds two tests that demonstrate this; they do not converge without the other changes in this patch.

Diff Detail

Event Timeline

mboehme created this revision.Jul 31 2023, 2:38 AM
Herald added a project: Restricted Project. · View Herald Transcript
mboehme requested review of this revision.Jul 31 2023, 2:38 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 31 2023, 2:38 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
mboehme edited the summary of this revision. (Show Details)Jul 31 2023, 2:39 AM
mboehme added reviewers: ymandel, xazax.hun.

Retracting from review momentarily -- I've just realized that I should be comparing values the same way this is done for the LocToVal map.

mboehme updated this revision to Diff 545561.Jul 31 2023, 2:52 AM

Make check for Value equivalence consistent with the corresponding check for
LocToVal.

mboehme updated this revision to Diff 545571.Jul 31 2023, 3:14 AM

Use dyn_cast_or_null instead of dyn_cast. (Children can be null.)

Retracting from review. I think I was overly hasty with this change:

  • There are edges between expressions that cross CFG block boundaries but don't involve block terminators. Here's an example -- [B1.1] has [B2.1] as a child, yet [B2] doesn't even have a terminator.
  • More fundamentally, convergence is not only important when considering the environment as an input to successor blocks, but also as a basis for the diagnostics that we will emit, which may look at arbitrary expressions in the block. So we really want all expressions to be fully converged.

It looks as if, instead, what we should be doing to improve convergence in a sound manner is to implement widening for ExprToLoc. I'll submit a corresponding patch shortly.

It looks as if, instead, what we should be doing to improve convergence in a sound manner is to implement widening for ExprToLoc. I'll submit a corresponding patch shortly.

+1, I believe we want ExprToLoc to converge. That being said, if we can get away with not checking some parts, it could potentially be implemented as an optimization. In that case, I'd expect to still have full checking in debug builds and a strong argument why is it OK to not compare some parts.

It looks as if, instead, what we should be doing to improve convergence in a sound manner is to implement widening for ExprToLoc. I'll submit a corresponding patch shortly.

+1, I believe we want ExprToLoc to converge. That being said, if we can get away with not checking some parts, it could potentially be implemented as an optimization. In that case, I'd expect to still have full checking in debug builds and a strong argument why is it OK to not compare some parts.

I've investigated this in more detail. Unfortunately, it turns out that it's not quite as simple as just implementing widening on ExprToLoc.

One of the reasons for this is that we only apply widening at loop heads, but the expressions that are "blocking" convergence may be contained in a block that is not a loop head.

We could solve this by applying widening everywhere, but AFAIU, that's really not desirable because you lose a lot of precision that way.

But really, I think ExprToLoc is just a red herring here. The real issue is:

  • We lack widening on PointerValues
  • Instead, for the purposes of convergence, we simply ignore differences in PointerValues
  • However, different PointerValues can lead to different locations for expressions that dereference these PointerValues, and we do consider the difference in these locations to be relevant for convergence

In other words, we have an inconsistency between when we consider a PointerValue to be converged and when we consider the storage location for an expression to be converged.

I think the real solution to this would be to introduce widening for PointerValues. Essentially, what we want is a "top" PointerValue that does not have an associated StorageLocation. However, we don't want to eliminate the PointerValue entirely; we still want to be able to attach properties to it, so that, for example, an analysis can record that the PointerValue is non-null, even though we don't know what its exact location is. This is important for us to be able to handle cases like this one correctly.

The most obvious way to implement a "top" PointerValue would be to make PointerValue::getPointeeLoc() return a nullable pointer instead of a reference. When dereferencing a PointerValue without a storage location, we would then not associate the corresponding Expr with a storage location at all, thereby solving the convergence issue. However, this approach would require some effort, as it would involve changing callers of PointerValue::getPointeeLoc() so that they can deal with the case where no pointee location is available.

I therefore think that we should consider a shorter-term solution: In Environment::equivalentTo(), ignoring glvalue entries in ExprToLoc for certain expressions where it's unlikely that any analysis will ever want to retrieve their storage location. See https://reviews.llvm.org/D156856, which I've just submitted for review. I hope that, in practice, this will cover a majority of the cases that are causing non-convergence.

I've investigated this in more detail. Unfortunately, it turns out that it's not quite as simple as just implementing widening on ExprToLoc.

One of the reasons for this is that we only apply widening at loop heads, but the expressions that are "blocking" convergence may be contained in a block that is not a loop head.

I am probably missing something, but I why does it matter where are we doing the widening? It is possible that we might need to redesign how parts of the program state is represented, but I do not immediately see any fundamental roadblocks.

I think the real solution to this would be to introduce widening for PointerValues.

Fully agreed.

Essentially, what we want is a "top" PointerValue that does not have an associated StorageLocation. However, we don't want to eliminate the PointerValue entirely; we still want to be able to attach properties to it, so that, for example, an analysis can record that the PointerValue is non-null, even though we don't know what its exact location is.

Another way to interpret "top": it points to a "summary" StorageLocation that can be any other StorageLocation, we just do not know which one. This interpretation/formulation has some advantages:

  • We have a StorageLocation to use when we dereference these top pointers.
  • It is compatible with the alias sets representation.
  • It is compatible with some other representations where we have other "summary" locations, like "UnkownStackLocation" or "UnkownHeapLocation".

These summary memory locations are sort of the union of all the potential memory locations they could represent. I think in general it might be useful to embrace this idea, e.g., when we model arrays, we can have a single element region representing all the knowledge we know to be true for all elements of the array.

Sorry for the late response -- I was on vacation.

I've investigated this in more detail. Unfortunately, it turns out that it's not quite as simple as just implementing widening on ExprToLoc.

One of the reasons for this is that we only apply widening at loop heads, but the expressions that are "blocking" convergence may be contained in a block that is not a loop head.

I am probably missing something, but I why does it matter where are we doing the widening?

We only do widening at loop heads, and this means that widening only affects locations and values that flow into the loop from the outside or from a previous loop iteration.

But convergence can also be blocked by locations and values that are only used within the loop body. If these change from loop iteration to loop iteration and we don't perform widening on them, we will conclude that the state of the loop body never converges.

Essentially, what we want is a "top" PointerValue that does not have an associated StorageLocation. However, we don't want to eliminate the PointerValue entirely; we still want to be able to attach properties to it, so that, for example, an analysis can record that the PointerValue is non-null, even though we don't know what its exact location is.

Another way to interpret "top": it points to a "summary" StorageLocation that can be any other StorageLocation, we just do not know which one. This interpretation/formulation has some advantages:

  • We have a StorageLocation to use when we dereference these top pointers.
  • It is compatible with the alias sets representation.
  • It is compatible with some other representations where we have other "summary" locations, like "UnkownStackLocation" or "UnkownHeapLocation".

These summary memory locations are sort of the union of all the potential memory locations they could represent. I think in general it might be useful to embrace this idea, e.g., when we model arrays, we can have a single element region representing all the knowledge we know to be true for all elements of the array.

I like this!

I'll have to do some thinking about how we want to represent these unknown / "top" storage locations exactly. Is there going to be a singleton "top" storage location? Are we going to allow associating the "top" storage location with a value (probably not...)? And so on. But this seems like a good direction to investigate.

mboehme abandoned this revision.Aug 22 2023, 6:50 AM

I've broken out the tests into https://reviews.llvm.org/D158513, as it seems clear we want to get these submitted.

We only do widening at loop heads, and this means that widening only affects locations and values that flow into the loop from the outside or from a previous loop iteration.

But convergence can also be blocked by locations and values that are only used within the loop body. If these change from loop iteration to loop iteration and we don't perform widening on them, we will conclude that the state of the loop body never converges.

I wonder if this is something we need to solve. Maybe when we do the widening at the loop head that should also affect values that are not flowing into that node. I.e., at the loop heads we might want to also look at the values from the previous iteration that are only used within the loop body.