Page MenuHomePhabricator

[DAGCombiner] Remove a bunch of redundant AddToWorklist calls.
Needs RevisionPublic

Authored by deadalnix on Wed, Aug 21, 7:54 AM.

Details

Summary

This comes as a first step toward processing the DAG nodes in topological orders. Doing so ensure that arguments of a node are combined before the node itself is combined, which exposes ore opportunities for optimization and/or reduce the amount of patterns a node has to match for.

DAGCombiner adding nodes to the worklist is various places causes the nodes to be in a different order from what is expected. In addition, this is reduant because these nodes end up being added to the worklist anyways due to the machinery at line 1621.

Diff Detail

Event Timeline

deadalnix created this revision.Wed, Aug 21, 7:54 AM
Herald added a project: Restricted Project. · View Herald TranscriptWed, Aug 21, 7:54 AM

I'm not sure how (if at all) to review patches like this?
Just accept that none of the existing tests change and the diff seems sane?

I'm not sure how (if at all) to review patches like this?
Just accept that none of the existing tests change and the diff seems sane?

I'm not sure what is the policy specifically for LLVM. This is what I would do. The fact that no test case change and they are all passing is a confirmation that these addition are indeed redundant (or possibly that tests cases are missing, but it doesn't looks like it in this case).

I was unaware of that tool. That's brilliant. Will do.

deadalnix marked 4 inline comments as done.Sun, Aug 25, 2:54 PM

Ok, I found a handful of cases that are not coevered by the test suite. I'll investigate if adding test coverage is possible, if it is do so. If not, then I'll remove any modification from that diff.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
10968 ↗(On Diff #216402)

This guy is not covered.

10979 ↗(On Diff #216402)

These guys are not covered either.

19198 ↗(On Diff #216402)

This is not covered either.

19503 ↗(On Diff #216402)

Not covered.

deadalnix updated this revision to Diff 217109.Mon, Aug 26, 4:00 AM

Restore calls that are not tested.

RKSimon accepted this revision.Mon, Aug 26, 7:00 AM

LGTM cheers - before committing please can you put a TODO next to the restored AddToWorklist calls mentioning they have no code coverage?

This revision is now accepted and ready to land.Mon, Aug 26, 7:00 AM
This revision was automatically updated to reflect the committed changes.

Thanks - still LGTM

My instrumented stage 2 build fails after this commit with this script.

> ./build-llvm.py --no-update --pgo --targets X86
...
[2240/2679] Building CXX object tools/clang/lib/Serialization/CMakeFiles/obj.clangSerialization.dir/ASTReader.cpp.o
FAILED: tools/clang/lib/Serialization/CMakeFiles/obj.clangSerialization.dir/ASTReader.cpp.o
/home/nathan/cbl/git/tc-build/build/llvm/stage1/bin/clang++  -DCLANG_VENDOR="\"ClangBuiltLinux \"" -DGTEST_HAS_RTTI=0 -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Itools/clang/lib/Serialization -I/home/nathan/cbl/git/tc-build/llvm-project/clang/lib/Serialization -I/home/nathan/cbl/git/tc-build/llvm-project/clang/include -Itools/clang/include -I/usr/include/libxml2 -Iinclude -I/home/nathan/cbl/git/tc-build/llvm-project/llvm/include -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -std=c++14 -w -fdiagnostics-color -ffunction-sections -fdata-sections -fprofile-generate='/home/nathan/cbl/git/tc-build/build/llvm/stage2/profiles' -fno-common -Woverloaded-virtual -Wno-nested-anon-types -O3 -DNDEBUG    -fno-exceptions -fno-rtti -MD -MT tools/clang/lib/Serialization/CMakeFiles/obj.clangSerialization.dir/ASTReader.cpp.o -MF tools/clang/lib/Serialization/CMakeFiles/obj.clangSerialization.dir/ASTReader.cpp.o.d -o tools/clang/lib/Serialization/CMakeFiles/obj.clangSerialization.dir/ASTReader.cpp.o -c /home/nathan/cbl/git/tc-build/llvm-project/clang/lib/Serialization/ASTReader.cpp
fatal error: error in backend: Cannot select: 0xfe3cc48: i64 = shl 0x117c5360, Constant:i64<32>
  0x117c5360: i64,ch = load<(load 4 from %ir.255 + 12), zext from i32> 0x104ce840, 0x119702e0, undef:i64
    0x119702e0: i64 = add nuw 0x1196e8d8, Constant:i64<4>
      0x1196e8d8: i64 = add 0x117ced30, Constant:i64<16>
        0x117ced30: i64,ch = load<(dereferenceable load 8 from %ir.32, !tbaa !9)> 0x104ce840, FrameIndex:i64<2>, undef:i64
          0x119d4430: i64 = FrameIndex<2>
          0x119d3a08: i64 = undef
        0x119d4228: i64 = Constant<16>
      0x10385118: i64 = Constant<4>
    0x119d3a08: i64 = undef
  0x11a762d0: i64 = Constant<32>
In function: _ZN5clang9ASTReader22ParseDiagnosticOptionsERKN4llvm11SmallVectorImLj64EEEbRNS_17ASTReaderListenerE
clang-10: error: clang frontend command failed with exit code 70 (use -v to see invocation)
ClangBuiltLinux clang version 10.0.0 (git://github.com/llvm/llvm-project b7075e40f3c2244073fed1bf64f922165987f68a) (based on LLVM 10.0.0svn)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/nathan/cbl/git/tc-build/build/llvm/stage1/bin
clang-10: note: diagnostic msg: PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
clang-10: note: diagnostic msg:
********************

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang-10: note: diagnostic msg: /tmp/ASTReader-e6c71c.cpp
clang-10: note: diagnostic msg: /tmp/ASTReader-e6c71c.sh
clang-10: note: diagnostic msg:

********************
...
> git -C llvm-project bisect log
# bad: [8679ef4e46a4d7b46a521a905d60357854117d43] [driver] add a new option `-gen-cdb-fragment-path` to emit a fragment of a compilation database for each compilation
# good: [894b8d1d85a13fe106411c996e26e571c00dbb78] FileManager: Factor duplicated code in getBufferForFile, NFC
git bisect start 'origin/master' '894b8d1d85a'
# good: [f899bf135fc5b7bb030b90da686d9d89bb97d18f] Fix windows build after r369894
git bisect good f899bf135fc5b7bb030b90da686d9d89bb97d18f
# good: [442a5765ce0c1594874a44f7aa210dfd0e0c5c35] [PowerPC] add tests for fma with negated ops; NFC
git bisect good 442a5765ce0c1594874a44f7aa210dfd0e0c5c35
# bad: [7305397a142a60d104e02ef1046b4289f957da95] TestFunctionStarts.py: add synchronization
git bisect bad 7305397a142a60d104e02ef1046b4289f957da95
# good: [e30b71f9dc0fdf12c3ea2ce4541ca8ce4af2aa67] Fix -dA flag, it is not a preprocessor flag.
git bisect good e30b71f9dc0fdf12c3ea2ce4541ca8ce4af2aa67
# bad: [3ba0f3c9b7f1c0227ed7771168fa9362cfea213e] [NFC] Add comments to some bool arguments for better readability
git bisect bad 3ba0f3c9b7f1c0227ed7771168fa9362cfea213e
# bad: [b7075e40f3c2244073fed1bf64f922165987f68a] [DAGCombiner] Remove a bunch of redundant AddToWorklist calls.
git bisect bad b7075e40f3c2244073fed1bf64f922165987f68a
# first bad commit: [b7075e40f3c2244073fed1bf64f922165987f68a] [DAGCombiner] Remove a bunch of redundant AddToWorklist calls.

rtrieu added a subscriber: rtrieu.Mon, Aug 26, 7:03 PM

I have reverted this in r370006.

C-Reduce has created the following testcase:

$ cat run.sh
clang \ 
"-cc1" \
"-triple" "x86_64-unknown-linux-gnu" \
"-emit-obj" \
"-fprofile-instrument=llvm" \
"-fprofile-instrument-path=/dev/null" \
"-O3" \
"-x" "c++" "test.ii"

$ cat test.ii
struct c {
  int *b;
  int operator[](long g) {
    return b[g];
  }
};

struct i {
  unsigned j : 32;
  unsigned k : 32;
  unsigned l : 32;
  unsigned m : 32;
};

c q;
i o;

void fn1() {
  o.j = 1;
  o.k = q[1];
  o.l = q[1];
  o.m = q[1];
}

$ ./run.sh
fatal error: error in backend: Cannot select: 0x6169578: i64 = shl 0x61696b0, Constant:i64<32>
  0x61696b0: i64,ch = load<(dereferenceable load 4 from `i128* getelementptr inbounds (%struct.i, %struct.i* @o, i64 0, i32 0)` + 12), zext from i32> 0x6057d28, 0x6165cc0, undef:i64
    0x6165cc0: i64 = add nuw 0x6169100, Constant:i64<4>
      0x6169100: i64 = add 0x61693d8, Constant:i64<8>
        0x61693d8: i64,ch = load<(load 8 from got)> 0x6057d28, 0x61692a0, undef:i64
          0x61692a0: i64 = X86ISD::WrapperRIP TargetGlobalAddress:i64<%struct.i* @o> 0 [TF=5]
            0x6166270: i64 = TargetGlobalAddress<%struct.i* @o> 0 [TF=5]
          0x6165d90: i64 = undef
        0x6168cf0: i64 = Constant<8>
      0x6166340: i64 = Constant<4>
    0x6165d90: i64 = undef
  0x61697e8: i64 = Constant<32>
In function: _Z3fn1v
craig.topper added inline comments.Mon, Aug 26, 7:30 PM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
5391

Why is this one unnecessary?

5457

And this one?

RKSimon reopened this revision.Tue, Aug 27, 5:46 AM
This revision is now accepted and ready to land.Tue, Aug 27, 5:46 AM
RKSimon requested changes to this revision.Tue, Aug 27, 5:46 AM
This revision now requires changes to proceed.Tue, Aug 27, 5:46 AM

@nathanchance Thanks for this. Having a test case will help tremendously. Sorry for the inconvenience.

@nathanchance Thanks for this. Having a test case will help tremendously. Sorry for the inconvenience.

Pretty sure the two spots I marked yesterday are the cause of the failure.