Fix a performance problem in gep(gep ...) merging

[wmi]

Summary

The patch is to fix the performance problem described in https://llvm.org/bugs/show_bug.cgi?id=23163.

As described in the bug above, gep merging may have negative effect on performance, especially when the src of gep has multiple uses, so we want to make sure every target gep after the merging has lower cost than before. In the patch, we achieve it by requiring that the index values of the src and target geps to be merged are both constants.

The patch is performance neutral for spec2000 on x86 sandybridge. It improves google internal benchmarks by 0.6 on x86 sandybridge and 0.4 on x86 westmere in geomean.

[qcolombet]

Hi Wei,

Could you upload the context with your patch to ease the review?

Thanks,
-Quentin

lib/Transforms/InstCombine/InstructionCombining.cpp

1474

Without the context, this is hard to say whether or not this is true.
In particular, if the new GEP can be folded in an addressing mode, this is good for the register pressure.

[wmi]

sorry to miss the context in the diff.

[qcolombet]

Hi Wei,

What performance numbers do you have to back up your change?

Now the optimization looks too conservative too me. I may be wrong, but I would like to see evidences of that.

Thanks,
-Quentin

lib/Transforms/InstCombine/InstructionCombining.cpp

1473

This seems too conservative. In particular, in your comment you had mentioned the number of users.
What does a heuristic based on that give?

[wmi]

I didn't see much performance change in spec2000. But I saw improvements in several google internal benchmarks: 2.8% in licence plate detection, 2.5% in stitcher, 4.6% in vision and 2.7% in zippy on sandybridge.

lib/Transforms/InstCombine/InstructionCombining.cpp

1473

At first I planed to add !Src.hasOneUse() in shouldMergeGEPs which disabled all the gep merging if the src has multiple uses.

// Replace: gep (gep %P, long B), long A, ...
// With:    T = long A+B; gep %P, T, ...

Then I think propagation will introduce extra computation only when the add insn (T = long A+B above) generated after the gep merging cannot be deleted. If GO1 and SO1 are both constants, there is no add generated for gep merging, .i.e, in this case, propagation at least introduces no harm.

So I proposed the patch here. Compared with the first proposal, if there are multiple uses but GO1 and SO1 are constants for some or all the uses, it is still beneficial to do the gep merging fully or partially. However, I saw not much performance difference for both proposals in spec2000 and internal testing.

I know a more general proposal than the second proposal here is to do gep merging only when the add expr of SO1 and GO1 can be folded into constants. However considering the two proposals have not much perf difference, I didn't try this one. But I can try that if you think it is good to try.

[qcolombet]

Thanks for the numbers Wei!

lib/Transforms/InstCombine/InstructionCombining.cpp

1473

What about something in between:
if ((!isa<Constant>(GO1) || !isa<Constant>(SO1)) && !Src->hasOneUse())

We still keep the benefice when both are constants and we handle single user case.

[wmi]

What about something in between:
if ((!isa<Constant>(GO1) || !isa<Constant>(SO1)) && !Src->hasOneUse())

We still keep the benefice when both are constants and we handle single user case.

http://reviews.llvm.org/D8911

For single user case, combining may still hurt performance sometimes
when the src gep is outside a loop and target gep is inside a loop.
gep merging can move an add instruction outside of a loop to a place
inside the loop.

I got a testcase 2.cc which can show the problem. Disabling gep
merging for it can reduce insn number in its kernel loop.

Before gep merging:

%10 = sext i32 %7 to i64
%11 = getelementptr inbounds i8, i8* %9, i64 %10  ====> the src gep
....

; <label>:16 ; preds = %14, %18

%x.1 = phi i32 [ %x.0, %14 ], [ %27, %18 ]
%17 = icmp slt i32 %x.1, %2
br i1 %17, label %18, label %28

; <label>:18 ; preds = %16

%19 = mul nsw i32 %x.1, 2
%20 = sext i32 %19 to i64
%21 = getelementptr inbounds i8, i8* %11, i64 %20  ====> the target

gep. %11 is the only use inside loop.

...
br label %16

After gep merging:

; <label>:14 ; preds = %12, %16

%x.1 = phi i32 [ %x.0, %12 ], [ %25, %16 ]
%15 = icmp slt i32 %x.1, %2
br i1 %15, label %16, label %26

; <label>:16

%17 = shl nsw i32 %x.1, 1
%18 = sext i32 %17 to i64
%.sum = add nsw i64 %9, %18   ========> the extra add inside loop.
%19 = getelementptr inbounds i8, i8* %8, i64 %.sum
...
br label %14

• 2.cc639 BDownload

[qcolombet]

The thing with the "both constants" approach is that we may miss some cases where an addressing mode may apply. In particular, on x86, when one argument of the add is a constant, we would be able to match reg1 + reg2 + displacement.

That being said, your numbers imply this is not a problem in practice, and most targets do not support reg1 + reg2 + reg3/imm addressing mode. Anyway, we could recover from that later on if needed.

So LGTM.

Thanks Wei!
-Quentin

[nicholas]

Quentin Colombet wrote:

The thing with the "both constants" approach is that we may miss some cases where an addressing mode may apply. In particular, on x86, when one argument of the add is a constant, we would be able to match reg1 + reg2 + displacement.

That being said, your numbers imply this is not a problem in practice, and most targets do not support reg1 + reg2 + reg3/imm addressing mode. Anyway, we could recover from that later on if needed.

So LGTM.

I might be misunderstanding why this patch helps, please bear with me.
Is this not a special case of a general problem, mainly that we're
merging something into a loop that was previously two operations one
inside and one outside the loop? Why wouldn't this problem come up in
other ways? We already have other problems where we introduce loop
carried dependencies where ones previously didn't exist, shouldn't we
approach this by adding an API to detect those and then making
transforms conditional on that?

Nick

Thanks Wei!
-Quentin

REPOSITORY

rL LLVM

http://reviews.llvm.org/D8911

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

[meheff]

There was a discussion on the mailing list about the exact issue this patch is addressing. We (Google team working on NVPTX backend) ran into this same issue as did someone (Francois Pichet) working with the ppc backend. Here's the link to the discussion:

http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-March/083398.html

I initially proposed what your patch does. That is, don't merge geps unless the indices are constant (in which case the add is folded so no additional instructions are potentially created in loops). However, after some discussion we came to the conclusion that the gep merging is a good canonicalization which we want to do. Instead a better approach might be to split GEPs (undoing the early GEP merge) very late, right before codegen, if it is determined to be profitable. This way, all the intermediate passes get the advantage of the canonicalization, while still being able to do LICM/CSE on GEP subexpressions which the gep merge had prevented.

I have a patch I am in the last stages of testing which will perform this optimization in the pass SeparateConstOffsetFromGEP (to be renamed ReassociateGEPs... or maybe SplitGEPs now that I think about it). I ran my patch with your example from bug 23163 and it looks to perform better than the prevent gep merging approach does. With head compiler I get 29 instructions in the inner loop (this matches what you report in the bug). You mention disabling merging reduces the loop instructions down to 25 instructions. With the patch I am working on, it gets reduced down to 16 instructions.

The pass is currently enabled only for select backends: nvptx, arm (-O3), and ppc (-O3). For testing with your bug I added it in x86 addIRPasses() followed by CSE and LICM (these extra passes do nothing on your example without the GEP splitting pass).

I should have the patch out for review later in the week.

Sorry for the duplicate effort here. I should have filed a bug on this issue before diving in :-(

Mark

[wmi]

1. updated getelementptr.ll.
2. descale-zero.ll failed with the patch. Actually the testcase didn't go through the code added in the original patch (For the testcase, InstCombiner::Descale was not called), which showed it was an invalid testcase. So I simply removed it.

[wmi]

I collected the stat data for spec2000. Overall, reaching the limit of
MaxLookupSearchDepth is not quite often. After we disable gep merging,
the times when the limit being reached only increase a little for two
files in spec2000. The stat data is attached.

Without the patch -- with gep merging:
reach_limit = 27, total = 81402, ratio = 0.03%, file = sv.c

With the patch -- without gep merging:
reach_limit = 28, total = 81486, ratio = 0.03%, file = sv.c
reach_limit = 8, total = 1107, ratio = 0.72%, file = tietze.c

I also tested the performance for spec2000 and internal benchmarks.
There were no performance differences.

I added the stat in -stat result. I will send it out in a separate patch.

Wei.

• disable.gepmerging.stat2 KBDownload
• gepmerging.stat2 KBDownload

lib/Transforms/InstCombine/InstructionCombining.cpp

if (EndsWithSequential) {
         Sum = SO1;
       } else {
         // If they aren't the same type, then the input hasn't been processed
         // by the loop above yet (which canonicalizes sequential index types to
         // intptr_t).  Just avoid transforming this until the input has been
         // normalized.
         if (SO1->getType() != GO1->getType())
           return nullptr;
+        // Only do the combine when GO1 and SO1 are both constants. In this
+        // case, we are sure the cost after the merge is never higher than
+        // before.
+        if (!isa<Constant>(GO1) || !isa<Constant>(SO1))
+          return nullptr;
         Sum = Builder->CreateAdd(SO1, GO1, PtrOp->getName()+".sum");
       }
 
       // Update the GEP in place if possible.
       if (Src->getNumOperands() == 2) {
         GEP.setOperand(0, Src->getOperand(0));
         GEP.setOperand(1, Sum);
         return &GEP;

test/Transforms/InstCombine/gep-merge.ll

+; This test makes sure that gep(gep ...) merge doesn't come into effect.
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; Make sure there are no geps being merged.
+; CHECK-LABEL: @fn3(
+; CHECK: getelementptr
+; CHECK: getelementptr
+; CHECK: getelementptr
+
+@_ZN2cv1aE = global i8* zeroinitializer, align 8
+declare i32 @fn1() #2
+declare i32 @fn2() #2
+
+; Function Attrs: uwtable
+define linkonce_odr i32 @fn3() {
+entry:
+  %call = call i32 @fn1()
+  %call1 = call i32 @fn2()
+  %0 = load i8*, i8** @_ZN2cv1aE, align 8
+  %idx.ext2 = sext i32 %call1 to i64
+  %add.ptr3 = getelementptr inbounds i8, i8* %0, i64 %idx.ext2
+  br label %for.cond5
+
+for.cond5:
+  %total1 = phi i32 [ 0, %entry ], [ %total2, %for.body7 ]
+  %x.1 = phi i32 [ 0, %entry ], [ %inc, %for.body7 ]
+  %cmp6 = icmp slt i32 %x.1, %call
+  br i1 %cmp6, label %for.body7, label %for.cond34
+
+for.body7:                                        ; preds = %for.cond5
+  %mul = mul nsw i32 %x.1, 2
+  %idxprom = sext i32 %mul to i64
+  %arrayidx = getelementptr inbounds i8, i8* %add.ptr3, i64 %idxprom
+  %1 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %1 to i32
+  %sub = sub nsw i32 %mul, 1
+  %idxprom10 = sext i32 %sub to i64
+  %arrayidx11 = getelementptr inbounds i8, i8* %add.ptr3, i64 %idxprom10
+  %2 = load i8, i8* %arrayidx11, align 1
+  %conv2 = zext i8 %2 to i32
+  %add1 = add nsw i32 %conv, %conv2
+  %total2 = add nsw i32 %total1, %add1
+  %inc = add nsw i32 %x.1, 1
+  br label %for.cond5
+
+for.cond34:
+  ret i32 %total1
+}