Page MenuHomePhabricator

[InstCombine] Simplify chain of GEP with constant indices
Needs ReviewPublic

Authored by huangjd on Nov 1 2022, 5:03 PM.

Details

Summary

Simplify chain of GEP in the form of GEP (GEP ... (GEP (GEP p C1) X1) ... Xn) C2 where C1 and C2 are constants by splitting GEP p C1 and breaking its user depedency, allowing visitGEPofGEP to reassociate the cloned inner GEP to outer GEP and perform constant index merging.

Example code that is optimized

struct S {
    char padding[123];
    int x;
};

int* P(S* s) {
    return (int*)((char*)&s->x + s->x - offsetof(S, x));
}

originally generates

P(S*):                                # @P(S*)
        movslq  124(%rdi), %rax
        addq    %rdi, %rax
        addq    $124, %rax
        addq    $-124, %rax
        retq

Now generates

P(S*):                                # @P(S*)
	movslq	124(%rdi), %rax
	addq	%rdi, %rax
	retq

Diff Detail

Unit TestsFailed

TimeTest
60,040 msx64 debian > Clang.CodeGenCXX::microsoft-abi-dynamic-cast.cpp
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/clang -cc1 -internal-isystem /var/lib/buildkite-agent/builds/llvm-project/build/lib/clang/16.0.0/include -nostdsysteminc -no-opaque-pointers -emit-llvm -O1 -o - -fexceptions -triple=i386-pc-win32 /var/lib/buildkite-agent/builds/llvm-project/clang/test/CodeGenCXX/microsoft-abi-dynamic-cast.cpp | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/clang/test/CodeGenCXX/microsoft-abi-dynamic-cast.cpp
60,080 msx64 debian > MLIR.Examples/standalone::test.toy
Script: -- : 'RUN: at line 1'; /usr/bin/cmake /var/lib/buildkite-agent/builds/llvm-project/mlir/examples/standalone -G "Ninja" -DCMAKE_CXX_COMPILER=/usr/bin/clang++ -DCMAKE_C_COMPILER=/usr/bin/clang -DLLVM_ENABLE_LIBCXX=OFF -DMLIR_DIR=/var/lib/buildkite-agent/builds/llvm-project/build/lib/cmake/mlir -DLLVM_USE_LINKER=lld -DPython3_EXECUTABLE="/usr/bin/python3.9"

Event Timeline

huangjd created this revision.Nov 1 2022, 5:03 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 1 2022, 5:03 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
huangjd requested review of this revision.Nov 1 2022, 5:03 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 1 2022, 5:03 PM
huangjd edited the summary of this revision. (Show Details)Nov 1 2022, 5:04 PM

This is essentially forward propagation (with multi-use) and is a generally a good way to reduce dependence height. For instance it can be used to enable reassociation and LICM:

for (k = .... ;k++) {

for (i = ....  ; i++) {

      b = (a+i);
      call(b);
      y = b + k + x;
    }

}

>

for (k = .... ;k++) {

for (i = ....  ; i++) {

      b = (a+i);
      call(b);
      y  = (a + i) + k + x;
    }

}

>

for (k = .... ;k++) {

for (i = ....  ; i++) {

      b = (a+i);
      call(b);
      y  = (a + k) + i + x;
    }

}

>

for (k = .... ;k++) {

tmp = a + k;
for (i = ....  ; i++) {
      b = (a+i);
      call(b);
      y  = tmp + k + x;
    }

}

y  = tmp + k + x;

should be

y  = tmp + i + x;
}

}

spatel added a comment.Nov 8 2022, 7:15 AM

Please pre-commit the baseline tests as an NFC patch, so we'll just show the test diffs here.

See D137664 for baseline

huangjd updated this revision to Diff 474109.Nov 8 2022, 4:43 PM

Merged after adding baseline

uabelho added a subscriber: uabelho.Dec 1 2022, 9:49 PM