Inline Cost improvement - GetElementPtr with constant operands

[knaumov]

Summary

Currently, InlineCost doesn't simplify GetElementPtr with constant operands. In this patch, we are introducing this functionality.
The improvement is built on a similar lambda-structure as the other simplification of instructions with constant operands.

[mtrofin]

What is the impact on the performance of the generated code?

Also, consider offering an opt-in flag.

llvm/lib/Analysis/InlineCost.cpp

1008

Code style: Index (not index)

[knaumov]

Answering @mtrofin 's comments:

As such cases (GEPs from a constant address with constant operands) will be simplified by the pipeline to a constant, InlineCost should be able to see this to apply the correct cost to the instruction. As eventually, the instruction will turn to a constant, the cost is 0.

[mtrofin]

In D81026#2069569, @knaumov wrote:

Answering @mtrofin 's comments:

As such cases (GEPs from a constant address with constant operands) will be simplified by the pipeline to a constant, InlineCost should be able to see this to apply the correct cost to the instruction. As eventually, the instruction will turn to a constant, the cost is 0.

That sounds fine, my point is that having some run on benchmarks to quantify the benefit would help understand the value of this particular omission from the cost analysis (or at minimum show there's no regression, or understand where the regressions may be). It could shed important insights into what matters for the cost analysis, basically.

Having an optin/out flag would help teams quickly handle any unexpected regressions they may encounter in the field.

[apilipenko]

In D81026#2069624, @mtrofin wrote:

That sounds fine, my point is that having some run on benchmarks to quantify the benefit would help understand the value of this particular omission from the cost analysis (or at minimum show there's no regression, or understand where the regressions may be). It could shed important insights into what matters for the cost analysis, basically.

The motivation for this change is the sequence generated by our downstream frontend. Essentially we are looking at something like this:

void foo(ID) {
  X = constant_table[ID];
  if (X == some constant) {
    ...
  }
}

This is a bit oversimplified, but when constant ID is passed into foo it can significantly reduce the cost of inlining. But in order to recognize this we need to recognize a gep of constant operands (the gep is used to compute the address of constant_table[ID]).

Teaching InlineCost to recognize geps of constant operands look like a generic enhancements. If you'd like we can do some performance verification on Clang.

[mtrofin]

In D81026#2071857, @apilipenko wrote:

In D81026#2069624, @mtrofin wrote:

That sounds fine, my point is that having some run on benchmarks to quantify the benefit would help understand the value of this particular omission from the cost analysis (or at minimum show there's no regression, or understand where the regressions may be). It could shed important insights into what matters for the cost analysis, basically.

The motivation for this change is the sequence generated by our downstream frontend. Essentially we are looking at something like this:

void foo(ID) {
  X = constant_table[ID];
  if (X == some constant) {
    ...
  }
}

This is a bit oversimplified, but when constant ID is passed into foo it can significantly reduce the cost of inlining. But in order to recognize this we need to recognize a gep of constant operands (the gep is used to compute the address of constant_table[ID]).

Teaching InlineCost to recognize geps of constant operands look like a generic enhancements. If you'd like we can do some performance verification on Clang.

If it's easy, it'd be nice to have. I was mostly concerned with staging it, i.e. having first an easy way to revert in the field, should there be a regression, and then removing that flag later - since adding a flag should be very straight forward.

[knaumov]

• Added flag for the change which is true by default

I have been struggling to collect the data @mtrofin has asked for to prove the usefulness of the patch. I will continue to do so, but meanwhile, I suggest accepting the change. Once I have gathered needed data, I will post new differential presenting the results and (most likely) deleting the flag.

[mtrofin]

In D81026#2094588, @knaumov wrote:

• Added flag for the change which is true by default

I have been struggling to collect the data @mtrofin has asked for to prove the usefulness of the patch. I will continue to do so, but meanwhile, I suggest accepting the change. Once I have gathered needed data, I will post new differential presenting the results and (most likely) deleting the flag.

LGTM

llvm/lib/Analysis/InlineCost.cpp

bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) {
   // Lambda to check whether a GEP's indices are all constant.
   auto IsGEPOffsetConstant = [&](GetElementPtrInst &GEP) {
     for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I)
       if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I))
         return false;
     return true;
   };
 
+  if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
+      SmallVector<Constant *, 2> Indices;
+      for (unsigned int index = 1 ; index < COps.size() ; ++index)
+        Indices.push_back(COps[index]);
+      return ConstantExpr::getGetElementPtr(I.getSourceElementType(), COps[0],
+                                            Indices, I.isInBounds());
+    }))
+    return true;
+
   if ((I.isInBounds() && canFoldInboundsGEP(I)) || IsGEPOffsetConstant(I)) {
     if (SROAArg)
       SROAArgValues[&I] = SROAArg;
 
     // Constant GEPs are modeled as free.
     return true;
   }
 

llvm/test/Transforms/Inline/gep_from_constant.ll

+; RUN: opt < %s -passes="print<inline-cost>" 2>&1 | FileCheck %s
+
+; CHECK-LABEL: @foo
+; CHECK: cost before = {{.*}}, cost after = {{.*}}, threshold before = {{.*}}, threshold after = {{.*}}, cost delta = {{.*}}, simplified to i8 addrspace(1)** getelementptr (i8 addrspace(1)*, i8 addrspace(1)** inttoptr (i64 754974720 to i8 addrspace(1)**), i64 5)
+
+define i8 addrspace(1)** @foo(i64 %0) {
+  %2 = inttoptr i64 754974720 to i8 addrspace(1)**
+  %3 = getelementptr i8 addrspace(1)*, i8 addrspace(1)** %2, i64 %0
+  ret i8 addrspace(1)** %3
+}
+
+define i8 addrspace(1)** @main() {
+  %1 = call i8 addrspace(1)** @foo(i64 5)
+  ret i8 addrspace(1)** %1
+}