Value: Provide a shortcut in stripPointerCastsAndOffsets()

[MatzeB]

Summary

The majority of stripPointerCastsAndOffsets() queries can be resolved
after checking 1 or 2 values. This patch delays the creation and
insertion into a SmallPtrSet until we have to check more than that. This
slightly improves compile time in my benchmarks.

[chandlerc]

Ugh. It's pretty sad that the optimizer doesn't fix this.

lib/IR/Value.cpp

424

Maybe use a lambda instead?

[hfinkel]

In D16622#336984, @chandlerc wrote:

Ugh. It's pretty sad that the optimizer doesn't fix this.

I recall also seeing this problem recently in a different context, and it looked like the reason why this mattered was because the constructor ends up zeroing the stack array (instead of leaving it uninitialized).

If we can fix the class implementation, or the optimizer, that would be better. It looks like there are two problems here, one is the memset (which is what I recall seeing in the profile), and the other is that we don't inline the destructor.

Specifically:

$ cat /tmp/q1.cpp 
#include <llvm/ADT/SmallPtrSet.h>
#include <llvm/IR/Type.h>
using namespace llvm;

bool foo(SmallPtrSetImpl<Type*> *Visited);

bool isSized() {
  SmallPtrSet<Type *, 4> V;
  return foo(&V);
}

$ clang++ -std=gnu++11 -O3 -S -emit-llvm -Iinclude -I/build/ppc64/llvm/include --gcc-toolchain=/install/ppc64/gcc -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -o - /tmp/q1.cpp -fno-exceptions
...
define zeroext i1 @_Z7isSizedv() #0 {
entry:
  %V = alloca %"class.llvm::SmallPtrSet", align 8
  %0 = bitcast %"class.llvm::SmallPtrSet"* %V to i8*
  call void @llvm.lifetime.start(i64 64, i8* %0) #3
  %arraydecay.i = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 1, i64 0
  %SmallArray.i.i.i = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 0, i32 0, i32 0
  store i8** %arraydecay.i, i8*** %SmallArray.i.i.i, align 8, !tbaa !1
  %1 = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 0, i32 0, i32 1
  store i8** %arraydecay.i, i8*** %1, align 8, !tbaa !7
  %2 = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 0, i32 0, i32 2
  store i32 4, i32* %2, align 8, !tbaa !8
  %3 = bitcast i8** %arraydecay.i to i8*
  %4 = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 0, i32 0, i32 3
  call void @llvm.memset.p0i8.i64(i8* %3, i8 -1, i64 32, i32 8, i1 false) #3
  store i32 0, i32* %4, align 4, !tbaa !9
  %5 = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 0, i32 0, i32 4
  store i32 0, i32* %5, align 8, !tbaa !10
  %6 = bitcast %"class.llvm::SmallPtrSet"* %V to %"class.llvm::SmallPtrSetImpl"*
  %call = call zeroext i1 @_Z3fooPN4llvm15SmallPtrSetImplIPNS_4TypeEEE(%"class.llvm::SmallPtrSetImpl"* %6) #3
  %7 = bitcast %"class.llvm::SmallPtrSet"* %V to %"class.llvm::SmallPtrSetImplBase"*
  call void @_ZN4llvm19SmallPtrSetImplBaseD2Ev(%"class.llvm::SmallPtrSetImplBase"* nonnull %7) #3
  call void @llvm.lifetime.end(i64 64, i8* %0) #3
  ret i1 %call
}
...

Consider, on the other hand, what happens with a SmallVector of the same type:

$ cat /tmp/q2.cpp 
#include <llvm/ADT/SmallVector.h>
#include <llvm/IR/Type.h>
using namespace llvm;

bool foo(SmallVectorImpl<Type*> *Visited);

bool isSized() {
  SmallVector<Type *, 4> V;
  return foo(&V);
}

$ clang ... /tmp/q2.cpp ...
...
define zeroext i1 @_Z7isSizedv() #0 {
entry:
  %V = alloca %"class.llvm::SmallVector", align 8
  %0 = bitcast %"class.llvm::SmallVector"* %V to i8*
  call void @llvm.lifetime.start(i64 56, i8* %0) #3
  %1 = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0, i64 0
  %BeginX.i.i.i.i.i = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0, i32 0, i32 0, i32 0, i32 0
  store i8* %1, i8** %BeginX.i.i.i.i.i, align 8, !tbaa !1
  %EndX.i.i.i.i.i = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0, i32 0, i32 0, i32 0, i32 1
  store i8* %1, i8** %EndX.i.i.i.i.i, align 8, !tbaa !6
  %CapacityX.i.i.i.i.i = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0, i32 0, i32 0, i32 0, i32 2
  %add.ptr.i.i.i.i.i = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0, i64 32
  store i8* %add.ptr.i.i.i.i.i, i8** %CapacityX.i.i.i.i.i, align 8, !tbaa !7
  %2 = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0
  %call = call zeroext i1 @_Z3fooPN4llvm15SmallVectorImplIPNS_4TypeEEE(%"class.llvm::SmallVectorImpl"* %2) #3
  %3 = load i8*, i8** %BeginX.i.i.i.i.i, align 8, !tbaa !1
  %cmp.i.i = icmp eq i8* %3, %1
  br i1 %cmp.i.i, label %_ZN4llvm15SmallVectorImplIPNS_4TypeEED2Ev.exit, label %if.then.i
 
if.then.i:                                        ; preds = %entry
  call void @free(i8* %3) #3
  br label %_ZN4llvm15SmallVectorImplIPNS_4TypeEED2Ev.exit
 
_ZN4llvm15SmallVectorImplIPNS_4TypeEED2Ev.exit:   ; preds = %entry, %if.then.i
  call void @llvm.lifetime.end(i64 56, i8* %0) #3
  ret i1 %call
}  
...

Here we have no memset and the destructor is inlined.

[MatzeB]

I just posted patches that

In D16622#337127, @hfinkel wrote:

In D16622#336984, @chandlerc wrote:

Ugh. It's pretty sad that the optimizer doesn't fix this.

I recall also seeing this problem recently in a different context, and it looked like the reason why this mattered was because the constructor ends up zeroing the stack array (instead of leaving it uninitialized).

If we can fix the class implementation, or the optimizer, that would be better. It looks like there are two problems here, one is the memset (which is what I recall seeing in the profile), and the other is that we don't inline the destructor.

Specifically:

$ cat /tmp/q1.cpp 
#include <llvm/ADT/SmallPtrSet.h>
#include <llvm/IR/Type.h>
using namespace llvm;

bool foo(SmallPtrSetImpl<Type*> *Visited);

bool isSized() {
  SmallPtrSet<Type *, 4> V;
  return foo(&V);
}

$ clang++ -std=gnu++11 -O3 -S -emit-llvm -Iinclude -I/build/ppc64/llvm/include --gcc-toolchain=/install/ppc64/gcc -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -o - /tmp/q1.cpp -fno-exceptions
...
define zeroext i1 @_Z7isSizedv() #0 {
entry:
  %V = alloca %"class.llvm::SmallPtrSet", align 8
  %0 = bitcast %"class.llvm::SmallPtrSet"* %V to i8*
  call void @llvm.lifetime.start(i64 64, i8* %0) #3
  %arraydecay.i = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 1, i64 0
  %SmallArray.i.i.i = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 0, i32 0, i32 0
  store i8** %arraydecay.i, i8*** %SmallArray.i.i.i, align 8, !tbaa !1
  %1 = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 0, i32 0, i32 1
  store i8** %arraydecay.i, i8*** %1, align 8, !tbaa !7
  %2 = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 0, i32 0, i32 2
  store i32 4, i32* %2, align 8, !tbaa !8
  %3 = bitcast i8** %arraydecay.i to i8*
  %4 = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 0, i32 0, i32 3
  call void @llvm.memset.p0i8.i64(i8* %3, i8 -1, i64 32, i32 8, i1 false) #3
  store i32 0, i32* %4, align 4, !tbaa !9
  %5 = getelementptr inbounds %"class.llvm::SmallPtrSet", %"class.llvm::SmallPtrSet"* %V, i64 0, i32 0, i32 0, i32 4
  store i32 0, i32* %5, align 8, !tbaa !10
  %6 = bitcast %"class.llvm::SmallPtrSet"* %V to %"class.llvm::SmallPtrSetImpl"*
  %call = call zeroext i1 @_Z3fooPN4llvm15SmallPtrSetImplIPNS_4TypeEEE(%"class.llvm::SmallPtrSetImpl"* %6) #3
  %7 = bitcast %"class.llvm::SmallPtrSet"* %V to %"class.llvm::SmallPtrSetImplBase"*
  call void @_ZN4llvm19SmallPtrSetImplBaseD2Ev(%"class.llvm::SmallPtrSetImplBase"* nonnull %7) #3
  call void @llvm.lifetime.end(i64 64, i8* %0) #3
  ret i1 %call
}
...

Consider, on the other hand, what happens with a SmallVector of the same type:

$ cat /tmp/q2.cpp 
#include <llvm/ADT/SmallVector.h>
#include <llvm/IR/Type.h>
using namespace llvm;

bool foo(SmallVectorImpl<Type*> *Visited);

bool isSized() {
  SmallVector<Type *, 4> V;
  return foo(&V);
}

$ clang ... /tmp/q2.cpp ...
...
define zeroext i1 @_Z7isSizedv() #0 {
entry:
  %V = alloca %"class.llvm::SmallVector", align 8
  %0 = bitcast %"class.llvm::SmallVector"* %V to i8*
  call void @llvm.lifetime.start(i64 56, i8* %0) #3
  %1 = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0, i64 0
  %BeginX.i.i.i.i.i = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0, i32 0, i32 0, i32 0, i32 0
  store i8* %1, i8** %BeginX.i.i.i.i.i, align 8, !tbaa !1
  %EndX.i.i.i.i.i = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0, i32 0, i32 0, i32 0, i32 1
  store i8* %1, i8** %EndX.i.i.i.i.i, align 8, !tbaa !6
  %CapacityX.i.i.i.i.i = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0, i32 0, i32 0, i32 0, i32 2
  %add.ptr.i.i.i.i.i = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0, i64 32
  store i8* %add.ptr.i.i.i.i.i, i8** %CapacityX.i.i.i.i.i, align 8, !tbaa !7
  %2 = getelementptr inbounds %"class.llvm::SmallVector", %"class.llvm::SmallVector"* %V, i64 0, i32 0
  %call = call zeroext i1 @_Z3fooPN4llvm15SmallVectorImplIPNS_4TypeEEE(%"class.llvm::SmallVectorImpl"* %2) #3
  %3 = load i8*, i8** %BeginX.i.i.i.i.i, align 8, !tbaa !1
  %cmp.i.i = icmp eq i8* %3, %1
  br i1 %cmp.i.i, label %_ZN4llvm15SmallVectorImplIPNS_4TypeEED2Ev.exit, label %if.then.i
 
if.then.i:                                        ; preds = %entry
  call void @free(i8* %3) #3
  br label %_ZN4llvm15SmallVectorImplIPNS_4TypeEED2Ev.exit
 
_ZN4llvm15SmallVectorImplIPNS_4TypeEED2Ev.exit:   ; preds = %entry, %if.then.i
  call void @llvm.lifetime.end(i64 56, i8* %0) #3
  ret i1 %call
}  
...

Here we have no memset and the destructor is inlined.

I just posted reviews that should avoid the memset in the small SmallPtrSet cases. I can't measure any signifant differences with it, so we can abandon this (assuming the SmallPtrSet changes get approved).

[hfinkel]

In D16622#338097, @MatzeB wrote:

I just posted patches that

...

I just posted reviews that should avoid the memset in the small SmallPtrSet cases. I can't measure any signifant differences with it, so we can abandon this (assuming the SmallPtrSet changes get approved).

Great, thanks!

lib/IR/Value.cpp

 enum PointerStripKind {
   PSK_ZeroIndices,
   PSK_ZeroIndicesAndAliases,
   PSK_InBoundsConstantIndices,
   PSK_InBounds
 };
 
 template <PointerStripKind StripKind>
-static Value *stripPointerCastsAndOffsets(Value *V) {
-  if (!V->getType()->isPointerTy())
-    return V;
-
-  // Even though we don't look through PHI nodes, we could be called on an
-  // instruction in an unreachable block, which may be on a cycle.
-  SmallPtrSet<Value *, 4> Visited;
-
-  Visited.insert(V);
-  do {
-    if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
-      switch (StripKind) {
-      case PSK_ZeroIndicesAndAliases:
-      case PSK_ZeroIndices:
-        if (!GEP->hasAllZeroIndices())
-          return V;
-        break;
-      case PSK_InBoundsConstantIndices:
-        if (!GEP->hasAllConstantIndices())
-          return V;
-        // fallthrough
-      case PSK_InBounds:
-        if (!GEP->isInBounds())
-          return V;
-        break;
-      }
-      V = GEP->getPointerOperand();
-    } else if (Operator::getOpcode(V) == Instruction::BitCast ||
-               Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
-      V = cast<Operator>(V)->getOperand(0);
-    } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
-      if (StripKind == PSK_ZeroIndices || GA->mayBeOverridden())
-        return V;
-      V = GA->getAliasee();
-    } else {
-      return V;
-    }
+static Value *stripOne(Value *V) {
+        return nullptr;
+        return nullptr;
+        return nullptr;
+    return GEP->getPointerOperand();
+    return cast<Operator>(V)->getOperand(0);
+      return nullptr;
+    return GA->getAliasee();
+    return nullptr;
+  }
+
+template <PointerStripKind StripKind>
+static Value *stripPointerCastsAndOffsets(Value *V) {
+  if (!V->getType()->isPointerTy())
+    return V;
+
+  // This function is performance sensitive so try the common case first
+  // before constructing the SmallPtrSet.
+  Value *Next = stripOne<StripKind>(V);
+  if (Next == nullptr)
+    return V;
+
+  // Even though we don't look through PHI nodes, we could be called on an
+  // instruction in an unreachable block, which may be on a cycle.
+  SmallPtrSet<Value *, 4> Visited;
+  Visited.insert(V);
+  if (!Visited.insert(Next).second)
+    return Next;
+  V = Next;
+  do {
+    Next = stripOne<StripKind>(V);
+    if (Next == nullptr)
+      return V;
+    V = Next;
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V).second);
 
   return V;
 }
 } // namespace
 
 Value *Value::stripPointerCasts() {