There is still room for improvement in the handling of multivalue
nodes in both passes, but the current algorithm is at least correct
and optimizes some simpler cases. In order to make future
optimizations of these passes easier and build confidence that the
current algorithms are correct, this CL also adds a script that
automatically and exhaustively generates interesting multivalue test
cases.
Details
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
Just looking for high-level feedback right now, especially on the inclusion of the script and generated test cases. Now that multivalue is testable, I will go back and clean up the previous patches in this chain.
llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp | ||
---|---|---|
839 | I am thinking of splitting the renaming and re-typing of these variables into a separate NFC patch. Thoughts? | |
llvm/test/CodeGen/WebAssembly/multivalue-stackify.py | ||
5 | I will add a comment to this file explaining what it does and why. |
Unit tests: fail. 61976 tests passed, 1 failed and 783 were skipped.
failed: LLVM.Bindings/Go/go.test
clang-tidy: unknown.
clang-format: pass.
Build artifacts: diff.json, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml
Unit tests: fail. 62079 tests passed, 3 failed and 784 were skipped.
failed: Clang.Driver/cc-print-options.c failed: LLVM.Transforms/ConstProp/fma.ll failed: LLVM.Transforms/InstSimplify/fp-nan.ll
clang-tidy: unknown.
clang-format: pass.
Build artifacts: diff.json, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml
@aheejin This should be properly rebased and ready for review as well. Sorry for all the messed up diffs!
Nice work! Sorry for the delayed reply. I like the test generation script and the autogenerated test case, and given the nature of the tests, I don't think there will be many changes to the generated results, so committing it shouldn't be a problem. With larger number of limits we can maybe use the script like a fuzzer or something too.
llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp | ||
---|---|---|
331 | Why is this? Is this related to multivalue? | |
llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp | ||
331 | Why is it impossible to place a def in a local if a subsequent def is stackified? This can't be possible? .functype pair_const () -> (i32, i64) call pair_const # only i64 is stackified use_i64 local.set 0 ... local.get 0 use_i32 | |
839 | Sounds good. But if that creates extra work, I'm OK with as is. | |
934 | If DefReg has multiple uses, can we create a new vreg to stackify that instead, as done in here? I'm not very sure how we can use tees here though. | |
llvm/test/CodeGen/WebAssembly/multivalue-stackify.py | ||
11 | What's the command to generate test results written in multivalue-stackify.ll? Do we need any options? If so, it'd be good to note that too. | |
21 | What do you mean by the abstract interpreter? An interpreter for ll file, or .s / wast file, or both? I don't fully understand what kind of interpreter you are planning to make and how you are gonna use it. And do you mean optimizing RegStackify further by 'embarking on'? | |
31 | It looks MAX_OPS and MAX_DEFS pertain to a whole program whereas MAX_USES is for a single instruction, right? How about renaming them to make it clear? | |
41 | Nit: This returns an op, but the name sounds it returns multiple of them.. can we rename it to make it clearer? | |
133 | Just curious, I agree this kind of program will not be very interesting, but why would it be nontrivial? Does that mean it poses some difficulties? | |
llvm/test/CodeGen/WebAssembly/multivalue.ll | ||
10–11 | We don't test packed pairs anymore? Is that because they don't have any differences in results from normal pairs? |
This patch is still mostly good, but it will have to be rebased on a different approach to supporting multivalue.
llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp | ||
---|---|---|
331 | The continue right after the DidEraseMI = true line used to continue the outer loop over the machine instructions. Since I added another level of looping, I needed to add a new continue referring to that loop here. | |
llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp | ||
331 | In principle, yes this is possible in some cases, but WebAssemblyExplicitLocals only knows how to place local.set instructions immediately after the instruction that defined the value being placed into a local. Generalizing this correctly would be a complex separate project. I changed this comment to point out that this is a limitation of ExplicitLocals. | |
934 | I'm not sure how that would work. Perhaps we can talk about it offline. | |
llvm/test/CodeGen/WebAssembly/multivalue-stackify.py | ||
11 | Added a code block with explicit commands. | |
21 | Actually, we need two abstract interpreters. One would interpret the LLVM IR or the internal data structure from which it is generated and one would interpret the emitted wasm instructions. The interpreters are abstract because they do not operate over concrete i32 values, but rather abstract representations of the program fragment semantics. We would would want to assert that each LLVM program and its corresponding wasm program have identical semantics. By "embarking on a rewrite" I just mean starting a rewrite of RegStackify, with the additional connotation that such a rewrite would be an interesting and long journey. | |
31 | Sounds good. Done. | |
41 | This function generates multiple ops, but one at a time. I think it is clearer to have a plural name here because the usage is for op in possible_ops(...). | |
133 | No, this filter exists only to reduce the number of programs. Defs with three uses are no more interesting than defs with two uses as far as stackification is concerned, so it's not worth emitting programs that have three uses of a def in addition to a program that has only two uses but is otherwise equivalent. | |
llvm/test/CodeGen/WebAssembly/multivalue.ll | ||
10–11 | Yeah, there was literally no difference in the backend so it didn't seem useful to test. |
Nice work!
llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp | ||
---|---|---|
331 | I don't think IMPLICIT_DEF will have ever have a multi-value def. Then can we check this and bail out right after the outer loop on starts? What I mean is for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) { MachineInstr &MI = *I++; assert(!WebAssembly::isArgument(MI.getOpcode())); if (MI.isDebugInstr() || MI.isLabel()) continue; // Maybe here? | |
llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp | ||
331 | Ah, you're right. | |
934 | Oh, nevermind. I was confused and thinking about the case when !MRI.hasOneDef(DefReg) instead. | |
939 | This does not currently seems to be able to handle a case that uses are spread across multiple consecutive instructions, such as r0, r1 = inst use r1 use r0 How about adding a TODO comment for this? | |
llvm/test/CodeGen/WebAssembly/multivalue-stackify.py | ||
133 | The location of the comments is messed up after updates ;( This comment was originally attached to the snippet below, and that's the reason why I asked about its 'nontriviality': # Reject nontrivial programs that have unused instructions if has_unused_op(program): return False |
llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp | ||
---|---|---|
331 | Nice idea! Done. | |
llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp | ||
939 | Can do. | |
llvm/test/CodeGen/WebAssembly/multivalue-stackify.py | ||
133 | Ah, in that case the answer is similar. It's wasteful to test a program with an unused instruction in addition to an identical program without that instruction. The "nontrivial" qualification is because some programs of a single unused instruction were explicitly allowed by the # Allow only multivalue single-op programs check. |
This patch is likely the reason for http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/38846
Testing: 0.. 10.. 20.. 30.. 40. FAIL: LLVM :: CodeGen/WebAssembly/PR40267.ll (17076 of 36117) ******************** TEST 'LLVM :: CodeGen/WebAssembly/PR40267.ll' FAILED ******************** Script: -- : 'RUN: at line 1'; /b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/llc < /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/CodeGen/WebAssembly/PR40267.ll -asm-verbose=false -verify-machineinstrs -disable-wasm-fallthrough-return-opt -wasm-disable-explicit-locals -wasm-keep-registers -- Exit Code: 1 Command Output (stderr): -- ================================================================= ==16208==ERROR: AddressSanitizer: use-after-poison on address 0x621000036798 at pc 0x000002d6b786 bp 0x7ffd1ab466b0 sp 0x7ffd1ab466a8 READ of size 8 at 0x621000036798 thread T0 #0 0x2d6b785 in operands_begin /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/CodeGen/MachineInstr.h:486:42 #1 0x2d6b785 in defs /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/CodeGen/MachineInstr.h:515:23 #2 0x2d6b785 in (anonymous namespace)::WebAssemblyRegStackify::runOnMachineFunction(llvm::MachineFunction&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp:926:37 #3 0x4581dfd in llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:73:13 #4 0x50ba4b0 in llvm::FPPassManager::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1482:27 #5 0x50bac07 in llvm::FPPassManager::runOnModule(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1518:16 #6 0x50bba71 in runOnModule /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1583:27 #7 0x50bba71 in llvm::legacy::PassManagerImpl::run(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1695:44 #8 0x9802a6 in compileModule(char**, llvm::LLVMContext&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llc/llc.cpp:617:8 #9 0x979a1f in main /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llc/llc.cpp:356:22 #10 0x7f1f109472e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0) #11 0x8d20e9 in _start (/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/llc+0x8d20e9) 0x621000036798 is located 2712 bytes inside of 4096-byte region [0x621000035d00,0x621000036d00) allocated by thread T0 here: #0 0x947cd4 in malloc /b/s/w/ir/cache/builder/src/third_party/llvm/compiler-rt/lib/asan/asan_malloc_linux.cpp:145:3 #1 0xc1a70a in safe_malloc /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/Support/MemAlloc.h:26:18 #2 0xc1a70a in Allocate /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/Support/AllocatorBase.h:85:12 #3 0xc1a70a in llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul>::StartNewSlab() /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/Support/Allocator.h:335:31 #4 0xc1a485 in llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul>::Allocate(unsigned long, llvm::Align) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/Support/Allocator.h:188:5 #5 0x455c6f3 in Allocate /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/Support/Allocator.h:202:12 #6 0x455c6f3 in operator new<llvm::MallocAllocator, 4096, 4096, 128> /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/Support/Allocator.h:446:20 #7 0x455c6f3 in llvm::MachineFunction::init() /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/CodeGen/MachineFunction.cpp:158:15 #8 0x45f1e12 in llvm::MachineModuleInfo::getOrCreateMachineFunction(llvm::Function const&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/CodeGen/MachineModuleInfo.cpp:250:14 #9 0x4581c2d in llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:45:29 #10 0x50ba4b0 in llvm::FPPassManager::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1482:27 #11 0x50bac07 in llvm::FPPassManager::runOnModule(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1518:16 #12 0x50bba71 in runOnModule /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1583:27 #13 0x50bba71 in llvm::legacy::PassManagerImpl::run(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1695:44 #14 0x9802a6 in compileModule(char**, llvm::LLVMContext&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llc/llc.cpp:617:8 #15 0x979a1f in main /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llc/llc.cpp:356:22 #16 0x7f1f109472e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
Why is this? Is this related to multivalue?
And Nit: We don't need {} for one-line ifs in LLVM :) I know it becomes a habit after working for a long time on Binaryen...