Added a new llvm-canon tool which aims to transform LLVM Modules into a canonical form by reordering and renaming instructions while preserving the same semantics. This tool makes it easier to spot semantic differences while diffing two modules which have undergone different transformation passes.
Details
Diff Detail
Time | Test | |
---|---|---|
3,210 ms | x64 debian > libarcher.critical::critical.c Script:
--
: 'RUN: at line 15'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -fopenmp -pthread -fno-experimental-isel -g -O1 -fsanitize=thread -I /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests -I /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/runtime/src -L /var/lib/buildkite-agent/builds/llvm-project/build/lib -Wl,-rpath,/var/lib/buildkite-agent/builds/llvm-project/build/lib /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/critical/critical.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/critical/Output/critical.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/critical/Output/critical.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/critical/Output/critical.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/critical/critical.c
| |
2,710 ms | x64 debian > libarcher.parallel::parallel-simple.c Script:
--
: 'RUN: at line 15'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -fopenmp -pthread -fno-experimental-isel -g -O1 -fsanitize=thread -I /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests -I /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/runtime/src -L /var/lib/buildkite-agent/builds/llvm-project/build/lib -Wl,-rpath,/var/lib/buildkite-agent/builds/llvm-project/build/lib /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/parallel/parallel-simple.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-simple.c.tmp -latomic && env OMP_TOOL_VERBOSE_INIT=stderr env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-simple.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-simple.c.tmp.log 2>&1 | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/parallel/parallel-simple.c --check-prefixes CHECK,TSAN_ON
| |
3,030 ms | x64 debian > libarcher.parallel::parallel-simple2.c Script:
--
: 'RUN: at line 15'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -fopenmp -pthread -fno-experimental-isel -g -O1 -fsanitize=thread -I /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests -I /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/runtime/src -L /var/lib/buildkite-agent/builds/llvm-project/build/lib -Wl,-rpath,/var/lib/buildkite-agent/builds/llvm-project/build/lib /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/parallel/parallel-simple2.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-simple2.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-simple2.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/parallel/Output/parallel-simple2.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/parallel/parallel-simple2.c
| |
2,960 ms | x64 debian > libarcher.races::critical-unrelated.c Script:
--
: 'RUN: at line 13'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -fopenmp -pthread -fno-experimental-isel -g -O1 -fsanitize=thread -I /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests -I /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/runtime/src -L /var/lib/buildkite-agent/builds/llvm-project/build/lib -Wl,-rpath,/var/lib/buildkite-agent/builds/llvm-project/build/lib /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/races/critical-unrelated.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/critical-unrelated.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/deflake.bash /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/critical-unrelated.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/critical-unrelated.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/races/critical-unrelated.c
| |
2,680 ms | x64 debian > libarcher.races::lock-nested-unrelated.c Script:
--
: 'RUN: at line 13'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -fopenmp -pthread -fno-experimental-isel -g -O1 -fsanitize=thread -I /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests -I /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/runtime/src -L /var/lib/buildkite-agent/builds/llvm-project/build/lib -Wl,-rpath,/var/lib/buildkite-agent/builds/llvm-project/build/lib /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/races/lock-nested-unrelated.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-nested-unrelated.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/deflake.bash /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-nested-unrelated.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-nested-unrelated.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/races/lock-nested-unrelated.c
| |
View Full Test Results (20 Failed) |
Event Timeline
tools/llvm-canon/canonicalizer.cpp | ||
---|---|---|
235 ↗ | (On Diff #214431) | Isn't this a reference to a pointer? I think you meant auto *OP. The reason I'm saying this is because you use dyn_cast below, and yet dyn_cast doesn't work with references. |
298 ↗ | (On Diff #214431) | Guidelines suggest using auto * when copying pointers. https://llvm.org/docs/CodingStandards.html#beware-unnecessary-copies-with-auto |
329 ↗ | (On Diff #214431) | typo: flag |
Seems like a great idea!
Could we have an option to only rename without reordering? I have found, in the past, some issue that were order sensitive, but rarely name sensitive, and it would be great to be able to debug those.
Also, in my personal implementation I had missed anonymous types and anonymous global variable, I don't know if we captured those here.
Note that I'm not sure if we can name all metadata or function attribute lists.
First of all, thank you for your valuable feedback!
Sure, will run clang-format!
When it comes to tests, I don't have any plan yet. I am not sure if testing every scenario is the best solution here - the canonicalization techniques may change easily as these are my 'best' approaches.
Can you think of any way how to test it sensibly?
I will take a look at PHI nodes and move the pass to Transforms.
I will add the option to run just naming or reordering - both stages are independent. We also haven't considered anonymous types and anonymous global variables.
I would like to thank everyone for your valuable feedback! I have fixed the code and moved the pass to lib/Tranfroms/Utils. I hope I have correctly integrated the pass with the rest of the LLVM (we should have some checklist for that).
tools/llvm-canon/canonicalizer.cpp | ||
---|---|---|
88 ↗ | (On Diff #214431) | You are right, this number cannot be generated by srand. We want the canonicalization to be deterministic. |
We have been experimenting with various ways of reordering output instructions hoping to add it now, but it looks to be much tougher than we thought. We hope to add it in a next commit.
@hfinkel
Now the canonicalizer sorts values in PHI nodes. After a discussion, I have decided not to remove duplicates. Those duplicates could come from some other passes and in my opinion, the canonicalizer should make them stand out instead of removing them.
Values are sorted alphabetically according to canonicalized names of corresponding basic blocks.
I am open to suggestions. I would like to ask for a final review of the updated diff. Especially I would like to know if I have integrated the pass with the rest of the LLVM correctly.
Now the canonicalizer sorts values in PHI nodes. After a discussion, I have decided not to remove duplicates. Those duplicates could come from some other passes and in my opinion, the canonicalizer should make them stand out instead of removing them.
I suppose that you mean that, if passes are introducing duplicates, that's something that we'd rather fix? That might be true. I'm okay with proceeding on this basis. If we need the deduplicating behavior we'll find out.
Yes, this is exactly what I meant . We will see how this works, as you said alternatively we can add that later.
Does the rest of the code look good to you? I will need someone to commit this patch for me (I don't have commit rights).
Gentle ping ;)
I would like to ask someone to commit this for me. I don't have commit rights.
Some initial comments.
In general:
- Don't spell out type if you just used *cast<???>
- Don't drop */& after auto
- Do end files with newline
- Consider small-size optimization. Please try to see if some of these std::string can be replaced with reasonably-sized llvm::SmallString<?>
- Please consider preallocating some strings
- This needs a bit more refactoring i think
docs/Passes.rst | ||
---|---|---|
693 ↗ | (On Diff #216009) | Too many - |
include/llvm/Transforms/Utils/IRCanonicalizer.h | ||
96 ↗ | (On Diff #216009) | Please make sure that files end with newlines |
lib/Transforms/Utils/IRCanonicalizer.cpp | ||
37–45 ↗ | (On Diff #216009) | Should these have defaults? |
57–78 ↗ | (On Diff #216009) | runOnFunction() ? |
73 ↗ | (On Diff #216009) | if(auto *PN = dyn_cast<PHINode>(&I)) |
150–170 ↗ | (On Diff #216009) | This block will result in most of memory nagging in this pass. |
151 ↗ | (On Diff #216009) | Can you make any reasonable guess as to what would be 90'th percentile of Operand string length? |
166 ↗ | (On Diff #216009) | It would be really good to predict+preallocate the size here. |
183 ↗ | (On Diff #216009) | const int& output = ? |
190 ↗ | (On Diff #216009) | auto* CI |
219 ↗ | (On Diff #216009) | Same comments as for the previous function |
263 ↗ | (On Diff #216009) | auto* IOP |
270 ↗ | (On Diff #216009) | const int Code = ? |
277 ↗ | (On Diff #216009) | const auto *CI |
305 ↗ | (On Diff #216009) | auto* |
306 ↗ | (On Diff #216009) | auto* |
331–335 ↗ | (On Diff #216009) | I'm sensing a repetitive pattern. I think you want to refactor it. |
388 ↗ | (On Diff #216009) | auto* |
427–430 ↗ | (On Diff #216009) | llvm::less_first |
504 ↗ | (On Diff #216009) | !I->user_empty() ? |
I don't know the current process but I think you should ask for them and commit it yourself so that you get the credit (and the blame :-P ) for this work.
PL
lib/Transforms/Utils/IRCanonicalizer.cpp | ||
---|---|---|
37–45 ↗ | (On Diff #216009) | They are all false by default, this is why I haven't explicitly stated their value. I don't think this will change in the future. |
57–78 ↗ | (On Diff #216009) | Yes! I don't know why I haven't changed this any earlier. |
166 ↗ | (On Diff #216009) | Changed to standard for-loop and moved to the end of the function. |
331–335 ↗ | (On Diff #216009) | The pattern only repeats for creating the operand list. |
Updated the diff for the new revision, refactored naming functions, accepted suggestions by lebedev.
Thank you for the review! @lebedev.ri
Is the code ready for the mainline?
Just a drive by comment from someone interested in this pass.
docs/Passes.rst | ||
---|---|---|
697 ↗ | (On Diff #222320) | It looks like this sentence is not finished. |
First of all, I am sorry for such a late reply (had many things going on recently). I have updated the patch for the upstream version of the LLVM. Thanks to @aykevl I have corrected the docs/Passes.rst file. Additionaly, I have added a new flag which enables/disables sorting and reordering operands in commutative instructions.
In the meantime, the project has been presented at the LLVM Developers' Meeting 2019 in San Jose. You may want to check out the slides or watch the presentation.
I would like to thank everyone who came to the presentation for all the valuable feedback and support! It was really nice to see you all.
Hopefully, the code looks good now. I would like to ask for further comments and eventual LGTM so the code can be committed to the mainline.
I've got a few nits. Will do a second pass shortly.
llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | ||
---|---|---|
176 | get this to conform to llvm style (ie OutputFootprint) | |
179 | Output as well. | |
235 | nit: auto *IOP | |
327 | nit: HasCanonicalName | |
371 | not: auto *IOP | |
422 | not: auto *VOP | |
440 | nit: Position | |
462 | nit: LHS and RHS | |
518 | for (const auto &OP : I->operands()) if (isa<Instruction>(OP)) return false; // Found non-immediate operand (instruction). | |
549 | unsigned Count = 0; for (const auto &B : *Func) { for (const auto &E : B) { if (&E == I) Outputs.insert(Count); Count++; } } | |
563 | nit: auto *U and auto *UI |
llvm/include/llvm/Transforms/Utils/IRCanonicalizer.h | ||
---|---|---|
1 ↗ | (On Diff #257243) | Does this need to be a separate header? Can the class be contained in a anonymous namespace in the .cpp file (IRCanonicalizer.cpp) like some of the other passes? |
61 ↗ | (On Diff #257243) | Is there any significance of this magic number? Can you either set this by a cl::opt or generated at runtime (maybe something using srand (time(NULL))) ? |
Thank you @plotfi for review! I will update the diff in a second.
llvm/include/llvm/Transforms/Utils/IRCanonicalizer.h | ||
---|---|---|
61 ↗ | (On Diff #257243) | There is no significance in this particular number but it needs to be consistent among all canonicalized modules (so this shouldn't be set by cl::opt or randomly generated). I have used particularly this number since it has been used in many other places in LLVM, for example here. |
llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll | ||
---|---|---|
6 | consider making the last 3 check lines "CHECK-NEXT" | |
tools/llvm-canon/canonicalizer.cpp | ||
88 ↗ | (On Diff #214431) | Ah yes, that makes a lot of sense. The MIR Canonicalizer ran into the same sort of issue. That's why the value-numbering-esque rewrite of it doesn't hash certain types of MachineOperands that might be different run to run. |
@plotfi Should I create a new review so that the HarborMaster will be able run the builds after the fix?
If updating this review did not trigger it, go ahead and create a new one. Sorry for the late reply @mpaszkowski.
Updated the patch to for the new version of LLVM. Currently the pass still utilizes the legacy pass manager. The pass will be ported to the new pass manager in a separate review.