Bytecode interpreter: Find a way around `PointerToIntegral` casts that result in an lvalue

[tbaederr]

Consider this simple example:

typedef __typeof((int*) 0 - (int*) 0) intptr_t;

int a = 10;
intptr_t s = (intptr_t) &a;

Compiled as C, there are no compilation errors. However, when evaluating the initializer for s:

CStyleCastExpr 0x7d6799454e40 'intptr_t':'long' <PointerToIntegral>
`-UnaryOperator 0x7d6799454e08 'int *' prefix '&' cannot overflow
  `-DeclRefExpr 0x7d6799454de0 'int' lvalue Var 0x7d6799454bf8 'a' 'int'

the current interpreter doesn't actually return an integer value at all, it returns an lvalue pointing to a:

LValue Base=VarDecl 0x7d6799454bf8, Null=0, Offset=0, HasPath=0

which ultimately means we get the following IR:

@a = dso_local global i32 10, align 4
@s = dso_local global i64 ptrtoint (ptr @a to i64), align 8

that's because the current interpreter takes this code path:

llvm-project/clang/lib/AST/ExprConstant.cpp

Lines 15269 to 15280 in fb00fa5

	if (LV.getLValueBase()) {
	// Only allow based lvalue casts if they are lossless.
	// FIXME: Allow a larger integer size than the pointer size, and allow
	// narrowing back down to pointer width in subsequent integral casts.
	// FIXME: Check integer type's active bits, not its type size.
	if (Info.Ctx.getTypeSize(DestType) != Info.Ctx.getTypeSize(SrcType))
	return Error(E);
	LV.Designator.setInvalid();
	LV.moveInto(Result);
	return true;
	}

which means it returns an lvalue from an AST node that returns an integer. That works in the current interpreter where everything is an APValue an one can check the type of those values, but in a bytecode interpreter, where we expect the computed type to match the node type, it doesn't work.

[llvmbot]

@llvm/issue-subscribers-clang-frontend

Author: Timm Baeder (tbaederr)

Consider this simple example: ```c typedef __typeof((int*) 0 - (int*) 0) intptr_t;

int a = 10;
intptr_t s = (intptr_t) &a;

Comipiled as C, there are no compilation errors. However, when evaluating the initializer for `s`:

CStyleCastExpr 0x7d6799454e40 'intptr_t':'long' <PointerToIntegral>
-UnaryOperator 0x7d6799454e08 'int *' prefix '&' cannot overflow -DeclRefExpr 0x7d6799454de0 'int' lvalue Var 0x7d6799454bf8 'a' 'int'

the current interpreter doesn't actually return an integer value at all, it returns an lvalue pointing to `a`:

LValue Base=VarDecl 0x7d6799454bf8, Null=0, Offset=0, HasPath=0

which ultimately means we get the following IR:
```llvm
@<!-- -->a = dso_local global i32 10, align 4
@<!-- -->s = dso_local global i64 ptrtoint (ptr @<!-- -->a to i64), align 8

that's because the current interpreter takes this code path:

llvm-project/clang/lib/AST/ExprConstant.cpp

Lines 15269 to 15280 in fb00fa5

	if (LV.getLValueBase()) {
	// Only allow based lvalue casts if they are lossless.
	// FIXME: Allow a larger integer size than the pointer size, and allow
	// narrowing back down to pointer width in subsequent integral casts.
	// FIXME: Check integer type's active bits, not its type size.
	if (Info.Ctx.getTypeSize(DestType) != Info.Ctx.getTypeSize(SrcType))
	return Error(E);
	LV.Designator.setInvalid();
	LV.moveInto(Result);
	return true;
	}

which means it returns an lvalue from an AST node that returns an integer. That works in the current interpreter where everything is an APValue an one can check the type of those values, but in a bytecode interpreter, where we expect the computed type to match the node type, it doesn't work.

[tbaederr]

A few observations:

• The current interpreter's support for this is limited, e.g. it doesn't support casting the resulting lvalue to another integer type: typedef int zomg; intptr_t s = ((zomg)(intptr_t) &a); fails to evaluate and results in a global constructor for s.
• intptr_t s = ((intptr_t) &a) + 12; works though and results in an lvalue with offset 12.
• The classified value of such a cast is an integer, but we need to express it as "actually a pointer". Adding a pointer member (even if in a union) to Integral would increase its size substantially though.
• Adding another PrimType for this doesn't work either since we're classifying the expression as a regular integral type.
• Even if we look through parens and then classify those casts as PT_Ptr instead, that breaks some other invariants about the AST, e.g. that suddenly both sides of a comparison operator aren't of the same type anymore.

[tbaederr]

Going the other way instead and using

  union {
    ReprT V; // Actual Value
    struct {
      const ValueDecl *VD;
      uint32_t VDOffset;
    } Ptr;
  };
  bool JustInt = true;

in Integral, lets us keep the information that an integer is actually the address of a variable plus an offset.

This increases the size of any Integral to 24 bytes (we align to pointer size). It also breaks a few tests because we assume that e.g. sizeof(Integral<8, true)) == sizeof(signed char) when evaluating strcmp I think.

It also has a significant performance penalty:

mafft 	9191M 	9740M (+5.97%)

[tbaederr]

Also, when simply disabling this support in ExprConstant.cpp:

--- i/clang/lib/AST/ExprConstant.cpp
+++ w/clang/lib/AST/ExprConstant.cpp
@@ -15270,6 +15270,7 @@ bool IntExprEvaluator::VisitCastExpr(const CastExpr *E) {
       return false;

     if (LV.getLValueBase()) {
+      return false;
       // Only allow based lvalue casts if they are lossless.
       // FIXME: Allow a larger integer size than the pointer size, and allow
       // narrowing back down to pointer width in subsequent integral casts.

(this does not cause performance problems, it seems slightly positive in some cases: http://llvm-compile-time-tracker.com/compare.php?from=959905a5adca4dc697160f8cbab302fefe610034&to=8c8ef466e432d5cfe143d81bece1daa2bc4ae01d&stat=instructions:u)

we now get a global constructor for the original test case:

@a = dso_local global i8 10, align 1
@s = dso_local global i64 0, align 8
@llvm.global_ctors = appending global [1 x { i32, ptr, ptr }] [{ i32, ptr, ptr } { i32 65535, ptr @_GLOBAL__sub_I_array.cpp, ptr null }]

which gets turned into this when optimizations (-O2) are applied:

@a = dso_local global i8 10, align 1
@s = dso_local local_unnamed_addr global i64 ptrtoint (ptr @a to i64), align 8
@llvm.global_ctors = appending global [0 x { i32, ptr, ptr }] zeroinitializer

which looks a lot like the original output with the ptr-to-int support.

With -O2, the output with the support is:

@a = dso_local global i8 10, align 1
@s = dso_local local_unnamed_addr global i64 ptrtoint (ptr getelementptr (i8, ptr @a, i64 12) to i64), align 8

which looks also very similar.

One could ask why this is even supported, it never(?) works in constant contexts. Is avoiding the global constructor the only reason?

CC @AaronBallman @zygoloid

[tbaederr]

Ping @AaronBallman @zygoloid

[AaronBallman]

The original code has been there forever: 1c8560d and suggests this was done to resolve some crashes, but whether that is still necessary is another matter. I don't honestly know if this is still required or not. Maybe @zygoloid recalls more?

[tbaederr]

Ping @zygoloid

[tbaederr]

Ping @zygoloid

[zygoloid]

This was probably originally added as a GNU extension, but now it's been around for long enough that even if it's not a GNU extension, it's a Clang extension. Clang's model of a constant integer value is that it's either a concrete constant value, or it's a pointer cast to integer type. So I think whatever representation you use for integers should be able to support representing a pointer, at least if the integer is at least pointer-sized. You could try to remove the extension, but it'll be hard to tell how much that breaks, especially as the breaks could be pretty subtle (it won't cause compilation failures most of the time, and probably won't change behavior when optimizing), and I guess we'd need at least one release cycle with that change behind a flag.

If you want to save as much space as possible given that this should be a very rare case, maybe you could reserve one unlucky integer bit-pattern for the pointer-cast-to-integer case, and use a side-table to store the pointers (or, if absent from the table, to represent that we actually mean that integer value)? Or maybe you can find a spare bit somewhere to track whether the integer is a concrete constant versus a symbolic address? And again you only need to do this for integer types that are at least as large as intptr_t.

[tbaederr]

And again you only need to do this for integer types that are at least as large as intptr_t.

That is true for the pointer-to-integer case, but not for AddrLabelDiff types.
This works just fine in clang:

int c(void) {
  static char ar1 = &&l2 - &&l1;
l1:
  return 10;
l2:
  return 11;
}

even though the representation for ar1 requires two host pointers. I now went with storing those in a side-table and using the integer value as the key into that table, but that still means that we can only have 128 such values.

I opened #169769 as a draf PR.