This is an archive of the discontinued LLVM Phabricator instance.

[WebAssembly] Fix RegStackify and ExplicitLocals to handle multivalue
ClosedPublic

Authored by tlively on Jan 17 2020, 12:00 AM.

Details

Summary

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.

Diff Detail

Event Timeline

tlively created this revision.Jan 17 2020, 12:00 AM
tlively marked 2 inline comments as done.

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: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

tlively updated this revision to Diff 238923.Jan 17 2020, 4:09 PM
  • Add script doc comment and update string formatting

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!

aheejin added a comment.EditedJan 23 2020, 9:28 AM

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?
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...

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?

tlively planned changes to this revision.Feb 3 2020, 2:42 PM

This patch is still mostly good, but it will have to be rebased on a different approach to supporting multivalue.

tlively updated this revision to Diff 243072.Feb 6 2020, 8:44 PM
aheejin added a comment.EditedFeb 7 2020, 10:42 PM
  • Have you had a chance to see my previous set of comments?
  • Do we need to reapply D71484 and D71496?
tlively updated this revision to Diff 244545.Feb 13 2020, 4:04 PM
tlively marked 7 inline comments as done.
  • Address comments
tlively marked 2 inline comments as done.Feb 13 2020, 4:07 PM
tlively added inline comments.
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.

aheejin accepted this revision.Feb 14 2020, 3:29 PM

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
This revision is now accepted and ready to land.Feb 14 2020, 3:29 PM
tlively marked 3 inline comments as done.Feb 18 2020, 2:48 PM
tlively added inline comments.
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 revision was automatically updated to reflect the committed changes.
vitalybuka added a subscriber: vitalybuka.EditedFeb 19 2020, 2:08 PM

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)
llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp