This is an archive of the discontinued LLVM Phabricator instance.

CSE on GEP indices
ClosedPublic

Authored by jingyue on Apr 22 2014, 4:19 PM.

Details

Summary

Add an optimization that eliminates common sub-expressions in a group of similar GEPs.

Diff Detail

Event Timeline

jingyue updated this revision to Diff 8753.Apr 22 2014, 4:19 PM
jingyue retitled this revision from to CSE on GEP indices.
jingyue updated this object.
jingyue edited the test plan for this revision. (Show Details)
jingyue added reviewers: hfinkel, eliben, jholewinski.
jingyue added a subscriber: Unknown Object (MLST).

As we discussed in http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-April/072305.html, I made this transformation target-independent, and added more tests. Looking forward to your feedback!

eliben added inline comments.Apr 24 2014, 11:05 AM
lib/Target/NVPTX/NVPTXTargetMachine.cpp
150–166

Since this pass is not target independent, I'm not sure this is the right place to put it. It makes more sense to add it as part of a custom compiler optimization pipeline, or maybe even in opt itself?

Note that the other passes added here are in fact NVPTX specific. Also the GVN vs. CSE logic seems out of place here. We already have a place where optimization pipeline contents are customized according to the optimization level - opt itself :)

We can add it under a off-by-default flag to PassManagerBuilder, until others experiment with the pass. If it proves beneficial for other archs, it may be enabled by default down the road.

lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp
2

Inconsistent comment line length

99

Make the flag name consistent with pass name

114

s/constants/constant/

122

Do you mean "minus" here? The dash is unclear as it can be just part of the sentence

131

Document "Find"

205

Consistent name - separate / split

211

ditto

227

Do you assert somewhere that users passed here have at least two operands?

271

surgery :) ?

279

s/i/I/ and s/e/E/

319

Maybe asserting OpNo < 2 here is more inclusive?

384

I, E

417

You can do this even if the offset doesn't need extraction? Is this OK?

442

I think a comment here would be useful

451

I, E

550

Where do you modify Changed?

test/Transforms/SeparateConstantOffsetFromGEP/NVPTX/gvn-pre.ll
1 ↗(On Diff #8753)

Can you change the directory name to be consistent the pass name? [I mean s/Constant/Const/]

2 ↗(On Diff #8753)

Woudln't it be much more useful to test this on IR->IR level with opt?

test/Transforms/LoopStrengthReduce/ has some examples of tests that use opt with tripel flags to provide target info

hfinkel edited edge metadata.Apr 24 2014, 11:14 AM
  • Original Message -----

From: "Eli Bendersky" <eliben@google.com>
To: jingyue@google.com, hfinkel@anl.gov, eliben@google.com, "justin holewinski" <justin.holewinski@gmail.com>
Cc: llvm-commits@cs.uiuc.edu
Sent: Thursday, April 24, 2014 1:06:05 PM
Subject: Re: [PATCH] CSE on GEP indices

Comment at: lib/Target/NVPTX/NVPTXTargetMachine.cpp:150
@@ -149,5 +149,3 @@

addPass(createNVPTXFavorNonGenericAddrSpacesPass());
  • // The FavorNonGenericAddrSpaces pass may remove instructions and

leave some

  • // values unused. Therefore, we run a DCE pass right afterwards.

We could

  • // remove unused values in an ad-hoc manner, but it requires

manual work and

  • // might be error-prone.

+ addPass(createSeparateConstOffsetFromGEPPass());
+ // The SeparateConstOffsetFromGEP pass creates variadic bases that

can be used

Since this pass is not target independent, I'm not sure this is the
right place to put it. It makes more sense to add it as part of a
custom compiler optimization pipeline, or maybe even in opt itself?

Why do you say this? As I see it, this pass is essentially LSR for the unrolled portion of multidimensional loop nests. And I asked them to add the TTI checks and move it because it is target independent. Because of the complex addressing modes available on x86, I'm not sure it will help there, but I suspect it will prove useful for several other targets (PPC, for example).

However, like LSR, it is not a canonicalization transformation, so it belongs, along with LSR, as a backend IR pass.

-Hal

Note that the other passes added here are in fact NVPTX specific.
Also the GVN vs. CSE logic seems out of place here. We already have
a place where optimization pipeline contents are customized
according to the optimization level - opt itself :)

We can add it under a off-by-default flag to PassManagerBuilder,
until others experiment with the pass. If it proves beneficial for
other archs, it may be enabled by default down the road.

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:1
@@ +1,2 @@
+===-- SeparateConstOffsetFromGEP.cpp - -------------------*- C++
-*-===

+//

Inconsistent comment line length

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:98
@@ +97,3 @@
+
+static cl::opt<bool> DisableSplitGEP("disable-split-gep",
cl::init(false),
+ cl::desc("Do not split GEPs for

CSE"),

Make the flag name consistent with pass name

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:113
@@ +112,3 @@
+/ index, and tries to find a constant integer that can be hoisted
to the
+
/ outermost level of the expression as an addition. Not every
constants in an
+/// expression can jump out. e.g., we cannot transform (b * (a + 5))

to (b * a +

s/constants/constant/

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:121
@@ +120,3 @@
+ / numeric value of the extracted constant offset (0 if failed),
and a
+
/ new index representing the remainder (equal to the original
index - the

+ /// constant offset).

Do you mean "minus" here? The dash is unclear as it can be just part
of the sentence

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:130
@@ +129,3 @@
+ Instruction *IP);
+ static int64_t Find(Value *Idx, const DataLayout *DL);

+

Document "Find"

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:204
@@ +203,3 @@
+INITIALIZE_PASS_BEGIN(
+ SeparateConstOffsetFromGEP, "split-gep",
+ "Split GEPs to a variadic base and a constant offset for better

CSE", false,

Consistent name - separate / split

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:210
@@ +209,3 @@
+INITIALIZE_PASS_END(
+ SeparateConstOffsetFromGEP, "split-gep",
+ "Split GEPs to a variadic base and a constant offset for better

CSE", false,

ditto

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:226
@@ +225,3 @@
+ if (ConstantOffset != 0) return ConstantOffset;
+ ConstantOffset = find(Usr->getOperand(1));
+ // If Usr is a sub operator, negate the constant offset found in

the right

Do you assert somewhere that users passed here have at least two
operands?

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:270
@@ +269,3 @@
+ If we found a non-zero constant offset, adds it to the path for
future
+
analysis and surgery. Zero is a valid constant offset, but
doesn't help

+ // this optimization.

surgery :) ?

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:278
@@ +277,3 @@
+unsigned ConstantOffsetExtractor::FindFirstUse(User *U, Value *Used)
{
+ for (unsigned i = 0, e = U->getNumOperands(); i < e; ++i) {

+ if (U->getOperand(i) == Used)

s/i/I/ and s/e/E/

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:318
@@ +317,3 @@
+ unsigned OpNo = FindFirstUse(U, C); U->getOperand(OpNo) == C
+ assert(OpNo != (unsigned)-1 && "UserChain wasn't built
correctly");
+ Value *TheOther = U->getOperand(1 - OpNo);
The other operand of

U

Maybe asserting OpNo < 2 here is more inclusive?

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:383
@@ +382,3 @@
+ gep_type_iterator GTI = gep_type_begin(*GEP);
+ for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i,
++GTI) {

+ if (isa<SequentialType>(*GTI)) {

I, E

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:416
@@ +415,3 @@
+ trace into these casts.
+ if (GEP->isInBounds()) {
+
Doing this to inbounds GEPs is safe because their indices are

guaranteed

You can do this even if the offset doesn't need extraction? Is this
OK?

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:441
@@ +440,3 @@
+ TargetTransformInfo &TTI = getAnalysis<TargetTransformInfo>();
+ if (!TTI.isLegalAddressingMode(GEP->getType()->getElementType(),
+ /*BaseGV=*/nullptr,

AccumulativeByteOffset,

I think a comment here would be useful

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:450
@@ +449,3 @@
+ gep_type_iterator GTI = gep_type_begin(*GEP);
+ for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i,
++GTI) {

+ if (isa<SequentialType>(*GTI)) {

I, E

Comment at: lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp:549
@@ +548,3 @@
+ }
+ return Changed;

+}

Where do you modify Changed?

Comment at:
test/Transforms/SeparateConstantOffsetFromGEP/NVPTX/gvn-pre.ll:1
@@ +1,2 @@
+; RUN: llc < %s -march=nvptx -mcpu=sm_20 | FileCheck %s

+; RUN: llc < %s -march=nvptx64 -mcpu=sm_20 | FileCheck %s

Can you change the directory name to be consistent the pass name? [I
mean s/Constant/Const/]

Comment at:
test/Transforms/SeparateConstantOffsetFromGEP/NVPTX/gvn-pre.ll:2
@@ +1,3 @@
+; RUN: llc < %s -march=nvptx -mcpu=sm_20 | FileCheck %s
+; RUN: llc < %s -march=nvptx64 -mcpu=sm_20 | FileCheck %s

+

Woudln't it be much more useful to test this on IR->IR level with
opt?

test/Transforms/LoopStrengthReduce/ has some examples of tests that
use opt with tripel flags to provide target info

http://reviews.llvm.org/D3462

jingyue updated this revision to Diff 8831.Apr 24 2014, 10:51 PM
jingyue edited edge metadata.

all comments addressed. PTAL

ConstantOffsetExtractor::find now traces into two more operators: sext and zext. For safety, we only traces into sext/zext when its operand is guaranteed not to overflow. e.g., we can safely transform "sext (add nsw a, 5)" into "add nsw (sext a), 5".

Added a new unit test in split-gep.ll to test the above transformation.

Passed "make -C test".

jingyue added inline comments.Apr 24 2014, 11:10 PM
include/llvm/LinkAllPasses.h
56

This file is changed because I did a "git rebase master". These changes won't be in the final commit.

lib/Target/NVPTX/NVPTXTargetMachine.cpp
150–166

As discussed offline, we add this pass and its clean up passes (-dce, -early-cse, and -gvn) in NVPTXTargetMachine.cpp for now. If this pass turned out to really benefit other targets, we can move that in TargetPassConfig.

lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp
2

done

99

done

114

done

122

done

131

done

205

done

211

done

227

done

271

done. explicitly say rebuildWithoutConstantOffset

279

done

319

done

384

done

417

This is OK in the sense that the program still behaves as before. Almost all such sext/zext are added by clang and some optimizations (e.g. instcombine) to make their lives easier (http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-April/072242.html). They are unnecessary anyway.

Shortcutting sext/zext makes ConstantOffsetExtractor::find much easier to implement, so I am inclined to keep this logic.

442

done

451

done

550

good catch. done

test/Transforms/SeparateConstantOffsetFromGEP/NVPTX/gvn-pre.ll
1 ↗(On Diff #8753)

done

2 ↗(On Diff #8753)

done. I added an IR test and kept the PTX test with a different check-prefix.

eliben accepted this revision.Apr 25 2014, 4:14 PM
eliben edited edge metadata.

Some more minor comments. Otherwise, LGTM.

lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp
170

It would be nice to document the structure of UserChain. E.g. [0] is the discovered constant, etc. A simple example could also be useful here.

342

OpNo < 2 covers you, you don't need != (unsigned)-1 too.

357

I find this comment a bit confusing when looking at rebuildLeafWithoutConstantOffset, which doesn't insert a 0 but just leaves the constant out.

test/Transforms/SeparateConstOffsetFromGEP/NVPTX/split-gep.ll
62

I'd also add a test where there are common bits, to make sure we don't cause a miscompilation.

This revision is now accepted and ready to land.Apr 25 2014, 4:14 PM
jingyue updated this revision to Diff 8861.Apr 25 2014, 8:49 PM
jingyue edited edge metadata.

All comments addressed.

Hal and Justin, do you have more to add? Looking forward to your feedback.

lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp
170

done

342

done

357

The comment was still describing an old implementation. good catch. Thanks!

test/Transforms/SeparateConstOffsetFromGEP/NVPTX/split-gep.ll
62

Modified function @or to cover this case

Hal and Justin, does this patch look good to you guys as well?

  • Original Message -----

From: "Jingyue Wu" <jingyue@google.com>
To: jingyue@google.com, "justin holewinski" <justin.holewinski@gmail.com>, hfinkel@anl.gov, eliben@google.com
Cc: llvm-commits@cs.uiuc.edu
Sent: Tuesday, April 29, 2014 10:56:18 PM
Subject: Re: [PATCH] CSE on GEP indices

Hal and Justin, does this patch look good to you guys as well?

Fine by me.

-Hal

http://reviews.llvm.org/D3462

Committed in r207783.

jingyue closed this revision.May 1 2014, 12:50 PM