Pointer Arithmetic

After further reflection, I've realized that the test

if (isa<PointerType>(ExprTy)) {

in

case BinaryOperator::Sub

should not detect (pointer - pointer), since the type of that
expression should be integral (ptrdiff_t). However, it *is* detecting
(pointer - pointer), which is causing at least one of the problems I
had with implementing it...

Where is that expression's type coming from?

-Keith

This looks like a bug in the semantic analyzer for -. Take a look at Sema/SemaExpr.cpp:819.

-Chris

OK, a new patch, with apparently-working (pointer - pointer) too.

I've made getSize virtual in clang::Type (default implementation
asserts, and it should become pure virtual when it's implemented for
all the subclasses) and renamed the conflicting getSize in
clang::ArrayType to getSizeExpr.

I've added a getPointerDiffType alongside getSizeType, and updated
SemaExpr to return that type for (pointer - pointer).

There's a test case which checks that errors are generated or not as
appropriate in all cases (tests/Parser/pointer-arithmetic.c).

Again, criticism is welcome :wink:

-Keith

PointerArithmetic.diff (12.5 KB)

Should also say, whilst I'm here, it compiles:

int *test1(int *a) { return a + 1; }
int *test2(int *a) { return 1 + a; }
int *test3(int *a) { return a - 1; }
int test4(int *a, int *b) { return a - b; }

into:

; ModuleID = 'foo'

define i32* @test1(i32* %a) {
entry:
  %a.addr = alloca i32* ; <i32**> [#uses=2]
  %allocapt = bitcast i32 undef to i32 ; <i32> [#uses=0]
  store i32* %a, i32** %a.addr
  %tmp = load i32** %a.addr ; <i32*> [#uses=1]
  %add.ptr = getelementptr i32* %tmp, i32 1 ; <i32*> [#uses=1]
  ret i32* %add.ptr
    ; No predecessors!
  ret i32* undef
}

define i32* @test2(i32* %a) {
entry:
  %a.addr = alloca i32* ; <i32**> [#uses=2]
  %allocapt = bitcast i32 undef to i32 ; <i32> [#uses=0]
  store i32* %a, i32** %a.addr
  %tmp = load i32** %a.addr ; <i32*> [#uses=1]
  %add.ptr = getelementptr i32* %tmp, i32 1 ; <i32*> [#uses=1]
  ret i32* %add.ptr
    ; No predecessors!
  ret i32* undef
}

define i32* @test3(i32* %a) {
entry:
  %a.addr = alloca i32* ; <i32**> [#uses=2]
  %allocapt = bitcast i32 undef to i32 ; <i32> [#uses=0]
  store i32* %a, i32** %a.addr
  %tmp = load i32** %a.addr ; <i32*> [#uses=1]
  %sub.ptr.neg = sub i32 0, 1 ; <i32> [#uses=1]
  %sub.ptr = getelementptr i32* %tmp, i32 %sub.ptr.neg ; <i32*> [#uses=1]
  ret i32* %sub.ptr
    ; No predecessors!
  ret i32* undef
}

define i32 @test4(i32* %a, i32* %b) {
entry:
  %a.addr = alloca i32* ; <i32**> [#uses=2]
  %b.addr = alloca i32* ; <i32**> [#uses=2]
  %allocapt = bitcast i32 undef to i32 ; <i32> [#uses=0]
  store i32* %a, i32** %a.addr
  store i32* %b, i32** %b.addr
  %tmp = load i32** %a.addr ; <i32*> [#uses=1]
  %tmp1 = load i32** %b.addr ; <i32*> [#uses=1]
  %sub.ptr.lhs.cast = ptrtoint i32* %tmp to i32 ; <i32> [#uses=1]
  %sub.ptr.rhs.cast = ptrtoint i32* %tmp1 to i32 ; <i32> [#uses=1]
  %sub.ptr.sub = sub i32 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast ; <i32> [#uses=1]
  %sub.ptr.div = sdiv i32 %sub.ptr.sub, 4 ; <i32> [#uses=1]
  ret i32 %sub.ptr.div
    ; No predecessors!
  ret i32 undef
}

which gets optimized to:

; ModuleID = '<stdin>'

define i32* @test1(i32* %a) {
entry:
  %add.ptr = getelementptr i32* %a, i32 1 ; <i32*> [#uses=1]
  ret i32* %add.ptr
}

define i32* @test2(i32* %a) {
entry:
  %add.ptr = getelementptr i32* %a, i32 1 ; <i32*> [#uses=1]
  ret i32* %add.ptr
}

define i32* @test3(i32* %a) {
entry:
  %sub.ptr = getelementptr i32* %a, i32 -1 ; <i32*> [#uses=1]
  ret i32* %sub.ptr
}

define i32 @test4(i32* %a, i32* %b) {
entry:
  %sub.ptr.lhs.cast = ptrtoint i32* %a to i32 ; <i32> [#uses=1]
  %sub.ptr.rhs.cast = ptrtoint i32* %b to i32 ; <i32> [#uses=1]
  %sub.ptr.sub = sub i32 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast ; <i32> [#uses=1]
  %sub.ptr.div = sdiv i32 %sub.ptr.sub, 4 ; <i32> [#uses=1]
  ret i32 %sub.ptr.div
}

(I guess the div can't be optimized to a shift because it's signed division?)

-Keith

Cool, this is looking really good. Minor (pedantic) comments:

+ /// the number of bits to represent the type.
+ // currently only implemented for BuiltinType -- the base implementation
+ // asserts. Should become pure virtual in future.
+ virtual unsigned getSize() const;

The nearby code is a bit inconsistent, but please format the comment like this:

+ /// getSize - the number of bits to represent the type.
+ virtual unsigned getSize() const;

In addition, please make it non-virtual, implemented in Type.cpp. For type predicates, we tend to implement them in terms of switch statements on the canonical type (see the other predicates for examples). We prefer non-virtual methods because we have vague plans to eliminate the vtable pointer at some point, and this keeps related code together in the same method.

From a philosophical software engineering perspective, virtual methods are great when you have a class hierarchy that often changes. The C type system doesn't often change, so we're ok :slight_smile:

+ // On Darwin, ptrdiff_t is defined as a "int". This seems silly, so I'm
+ // using "long" instead...
+ // FIXME: should derive from "Target".
+ return LongTy;

Please use int :slight_smile:

  bool Type::isConstantSizeType(SourceLocation *loc) const {
    if (const ArrayType *Ary = dyn_cast<ArrayType>(CanonicalType)) {
- assert(Ary->getSize() && "Incomplete types don't have a size at all!");
- return Ary->getSize()->isIntegerConstantExpr(loc); // Variable Length Array?
+ assert(Ary->getSizeExpr() && "Incomplete types don't have a size at all!");
+ return Ary->getSizeExpr()->isIntegerConstantExpr(loc); // Variable Length Array?
    }

Please keep the code in 80 columns. I'm not a stickler about testcases fitting in 80 columns, but the C++ code should.

    RValue EmitDiv(RValue LHS, RValue RHS, QualType EltTy);
    RValue EmitRem(RValue LHS, RValue RHS, QualType EltTy);
    RValue EmitAdd(RValue LHS, RValue RHS, QualType EltTy);
+ RValue EmitPointerAdd(RValue LHS, QualType LHSTy, RValue RHS, QualType RHSTy, QualType EltTy);
    RValue EmitSub(RValue LHS, RValue RHS, QualType EltTy);
+ RValue EmitPointerSub(RValue LHS, QualType LHSTy, RValue RHS, QualType RHSTy, QualType EltTy);
    RValue EmitShl(RValue LHS, RValue RHS, QualType ResTy);

likewise.

+ case BinaryOperator::Add: {
+ QualType ExprTy = E->getType();
+ if (isa<PointerType>(ExprTy)) {
+ Expr *LHSExpr = E->getLHS();

This won't work correctly if you're adding to a typedef for a pointer. Because of the way we handle typedefs, you should always strip off typedef information, by using ExprTy.getCanonicalType(), like this:

+ case BinaryOperator::Add: {
+ QualType ExprTy = E->getType();
+ if (isa<PointerType>(ExprTy.getCanonicalType())) {
+ Expr *LHSExpr = E->getLHS();

You can think of this as "looking through" any typedefs if present to find the actual underlying type.

Alternatively, there are some predicates on type that do this for you, which are even better to use when suitable. This would make the code be:

+ case BinaryOperator::Add: {
+ QualType ExprTy = E->getType();
+ if (ExprTy->isPointerType()) {
+ Expr *LHSExpr = E->getLHS();

+ case BinaryOperator::Sub: {
+ QualType ExprTy = E->getType();
+ Expr *LHSExpr = E->getLHS();
+ if (isa<PointerType>(LHSExpr->getType())) {

+RValue CodeGenFunction::EmitPointerAdd(RValue LHS, QualType LHSTy, RValue RHS, QualType RHSTy, QualType ResTy) {
+ llvm::Value *LHSValue = LHS.getVal();
+ llvm::Value *RHSValue = RHS.getVal();
+ if (isa<PointerType>(LHSTy.getTypePtr())) {

likewise, these should check Ty->isPointerType(). In the second case, you don't need to call getTypePtr().

+RValue CodeGenFunction::EmitPointerAdd(RValue LHS, QualType LHSTy, RValue RHS, QualType RHSTy, QualType ResTy) {
+RValue CodeGenFunction::EmitPointerSub(RValue LHS, QualType LHSTy, RValue RHS, QualType RHSTy, QualType ResTy) {
...

please keep these in 80 cols.

For this case:

+RValue CodeGenFunction::EmitPointerSub(RValue LHS, QualType LHSTy, RValue RHS, QualType RHSTy, QualType ResTy) {
+ llvm::Value *LHSValue = LHS.getVal();
+ llvm::Value *RHSValue = RHS.getVal();
+ const PointerType *RHSPtrType = dyn_cast<PointerType>(RHSTy.getTypePtr());
+ if (RHSPtrType != NULL) {

I suggest writing this as:

+ if (const PointerType *RHSPtrType = dyn_cast<PointerType>(RHSTy.getQualifiedType())) {

+ // do we care about non-8-bit bytes? Why is getSize returning bits?

1) no. 2) so we have a consistent measure of size, which works for bitfields and other things. Dividing by 8 here is good, but please update the comment.

+ // is signed division correct?

Yep :slight_smile: For example:

int A[10];
int *B = &A[0], *C = &A[4];

C-B -> 4 B-C -> -4

Please update the patch and resend it, it's very close. Thanks!

-Chris

Yep, this is right. In the future, LLVM may get some way to represent "exact division" which is useful for pointer subtraction. When it has that, it will be able to simplify this.

-Chris