diff options
| -rw-r--r-- | src/passes/MemoryPacking.cpp | 69 | ||||
| -rw-r--r-- | src/support/space.h | 84 | ||||
| -rw-r--r-- | test/example/space.cpp | 115 | ||||
| -rw-r--r-- | test/example/space.txt | 1 | ||||
| -rw-r--r-- | test/passes/memory-packing_all-features.txt | 38 | ||||
| -rw-r--r-- | test/passes/memory-packing_all-features.wast | 38 |
6 files changed, 339 insertions, 6 deletions
diff --git a/src/passes/MemoryPacking.cpp b/src/passes/MemoryPacking.cpp index 27168942a..3ab170ea9 100644 --- a/src/passes/MemoryPacking.cpp +++ b/src/passes/MemoryPacking.cpp @@ -32,12 +32,15 @@ #include "ir/module-utils.h" #include "ir/utils.h" #include "pass.h" +#include "support/space.h" #include "wasm-binary.h" #include "wasm-builder.h" #include "wasm.h" namespace wasm { +namespace { + // A subsection of an orginal memory segment. If `isZero` is true, memory.fill // will be used instead of memory.init for this range. struct Range { @@ -74,8 +77,6 @@ const size_t MEMORY_FILL_SIZE = 9; // data.drop: 2 byte opcode + ~1 byte index immediate const size_t DATA_DROP_SIZE = 3; -namespace { - Expression* makeGtShiftedMemorySize(Builder& builder, Module& module, MemoryInit* curr) { return builder.makeBinary( @@ -97,6 +98,7 @@ struct MemoryPacking : public Pass { uint32_t maxSegments; void run(PassRunner* runner, Module* module) override; + bool canOptimize(const std::vector<Memory::Segment>& segments); void optimizeBulkMemoryOps(PassRunner* runner, Module* module); void getSegmentReferrers(Module* module, std::vector<Referrers>& referrers); void dropUnusedSegments(std::vector<Memory::Segment>& segments, @@ -125,10 +127,15 @@ void MemoryPacking::run(PassRunner* runner, Module* module) { return; } + auto& segments = module->memory.segments; + + if (!canOptimize(segments)) { + return; + } + maxSegments = module->features.hasBulkMemory() ? 63 : uint32_t(WebLimitations::MaxDataSegments); - auto& segments = module->memory.segments; // For each segment, a list of bulk memory instructions that refer to it std::vector<Referrers> referrers(segments.size()); @@ -176,6 +183,62 @@ void MemoryPacking::run(PassRunner* runner, Module* module) { } } +bool MemoryPacking::canOptimize(const std::vector<Memory::Segment>& segments) { + // One segment is always ok to optimize, as it does not have the potential + // problems handled below. + if (segments.size() <= 1) { + return true; + } + // Check if it is ok for us to optimize. + Address maxAddress = 0; + for (auto& segment : segments) { + if (!segment.isPassive) { + auto* c = segment.offset->dynCast<Const>(); + // If an active segment has a non-constant offset, then what gets written + // cannot be known until runtime. That is, the active segments are written + // out at startup, in order, and one may trample the data of another, like + // + // (data (i32.const 100) "a") + // (data (i32.const 100) "\00") + // + // It is *not* ok to optimize out the zero in the last segment, as it is + // actually needed, it will zero out the "a" that was written earlier. And + // if a segment has an imported offset, + // + // (data (i32.const 100) "a") + // (data (global.get $x) "\00") + // + // then we can't tell if that last segment will end up overwriting or not. + // The only case we can easily handle is if there is just a single + // segment, which we handled earlier. (Note that that includes the main + // case of having a non-constant offset, dynamic linking, in which we have + // a single segment.) + if (!c) { + return false; + } + // Note the maximum address so far. + maxAddress = std::max( + maxAddress, Address(c->value.getInteger() + segment.data.size())); + } + } + // All active segments have constant offsets, known at this time, so we may be + // able to optimize, but must still check for the trampling problem mentioned + // earlier. + // TODO: optimize in the trampling case + DisjointSpans space; + for (auto& segment : segments) { + if (!segment.isPassive) { + auto* c = segment.offset->cast<Const>(); + Address start = c->value.getInteger(); + DisjointSpans::Span span{start, start + segment.data.size()}; + if (space.addAndCheckOverlap(span)) { + return false; + } + } + } + return true; +} + bool MemoryPacking::canSplit(const Memory::Segment& segment, const Referrers& referrers) { if (segment.isPassive) { diff --git a/src/support/space.h b/src/support/space.h new file mode 100644 index 000000000..9d940c872 --- /dev/null +++ b/src/support/space.h @@ -0,0 +1,84 @@ +/* + * Copyright 2020 WebAssembly Community Group participants + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef wasm_support_space_h +#define wasm_support_space_h + +#include "utilities.h" +#include <wasm.h> + +namespace wasm { + +struct DisjointSpans { + // A span of form [a, b), i.e., that does not include the end point. + struct Span { + Address left, right; + + bool checkOverlap(const Span& other) const { + return !(left >= other.right || right <= other.left); + } + }; + + struct SortByLeft { + bool operator()(const Span& left, const Span& right) const { + return left.left < right.left || + (left.left == right.left && left.right < right.right); + } + }; + + // The spans seen so far. Guaranteed to be disjoint. + std::set<Span, SortByLeft> spans; + + // Adds an item and checks overlap while doing so, returning true if such + // overlap exists. + bool addAndCheckOverlap(Span span) { + // Insert the new span. We can then find its predecessor and successor. + // They are disjoint by assumption, so the question is then does the new + // span overlap with them, or not. + decltype(spans)::iterator iter; + bool inserted; + std::tie(iter, inserted) = spans.insert(span); + if (!inserted) { + // This exact span was already there, so there is definite overlap. + return true; + } + // Check predecessor and successor, if they exist. + if (iter != spans.begin() && std::prev(iter)->checkOverlap(span)) { + return true; + } + if (std::next(iter) != spans.end() && std::next(iter)->checkOverlap(span)) { + return true; + } + return false; + } + + // Inefficient - mostly for testing. + void add(Span span) { addAndCheckOverlap(span); } + + // Inefficient - mostly for testing. + bool checkOverlap(Span span) { + bool existsBefore = spans.find(span) != spans.end(); + auto hasOverlap = addAndCheckOverlap(span); + if (!existsBefore) { + spans.erase(span); + } + return hasOverlap; + } +}; + +} // namespace wasm + +#endif // wasm_support_space_h diff --git a/test/example/space.cpp b/test/example/space.cpp new file mode 100644 index 000000000..33256eedf --- /dev/null +++ b/test/example/space.cpp @@ -0,0 +1,115 @@ +#include <cassert> +#include <iostream> + +#include <support/space.h> + +using namespace wasm; + +using Span = DisjointSpans::Span; + +int main() { + // No spans + { + DisjointSpans root; + // Nothing in root + assert(!root.checkOverlap(Span{0, 100})); + } + // One span + { + DisjointSpans root; + root.add(Span{0, 100}); + // It is there + assert(root.checkOverlap(Span{0, 100})); + } + { + DisjointSpans root; + root.add(Span{40, 60}); + // Exact match + assert(root.checkOverlap(Span{40, 60})); + // No overlap + assert(!root.checkOverlap(Span{20, 30})); + // Touching, but no overlap + assert(!root.checkOverlap(Span{20, 40})); + // Overlap + assert(root.checkOverlap(Span{20, 41})); + assert(root.checkOverlap(Span{40, 41})); + // Internal + assert(root.checkOverlap(Span{45, 50})); + // Touches other side + assert(root.checkOverlap(Span{45, 60})); + // Overlaps on other side + assert(root.checkOverlap(Span{45, 70})); + // Just inside. + assert(root.checkOverlap(Span{59, 60})); + // Just outside + assert(!root.checkOverlap(Span{60, 61})); + // Totally outside + assert(!root.checkOverlap(Span{70, 80})); + } + // Two spans, different subtrees + { + DisjointSpans root; + root.add(Span{30, 40}); + root.add(Span{60, 70}); + assert(!root.checkOverlap(Span{10, 20})); + assert(!root.checkOverlap(Span{10, 30})); + assert(root.checkOverlap(Span{10, 40})); + assert(root.checkOverlap(Span{35, 40})); + assert(!root.checkOverlap(Span{40, 60})); + assert(!root.checkOverlap(Span{45, 55})); + assert(root.checkOverlap(Span{50, 61})); + assert(root.checkOverlap(Span{50, 100})); + assert(root.checkOverlap(Span{60, 70})); + assert(root.checkOverlap(Span{60, 61})); + assert(!root.checkOverlap(Span{70, 80})); + assert(!root.checkOverlap(Span{70, 100})); + } + // Two spans, same subtree + { + DisjointSpans root; + root.add(Span{30, 40}); + root.add(Span{40, 45}); + assert(!root.checkOverlap(Span{10, 20})); + assert(!root.checkOverlap(Span{10, 30})); + assert(root.checkOverlap(Span{10, 40})); + assert(root.checkOverlap(Span{35, 40})); + assert(root.checkOverlap(Span{40, 41})); + assert(root.checkOverlap(Span{35, 45})); + assert(!root.checkOverlap(Span{45, 100})); + } + // "Pixels" + { + const int N = 40; + for (int i = 0; i < N; i++) { + DisjointSpans root; + for (int j = 0; j < N; j++) { + // add all pixels but the i-th + if (j != i) { + root.add(Span{j, j + 1}); + } + } + for (int j = 0; j < N; j++) { + if (j != i) { + assert(root.checkOverlap(Span{j, j + 1})); + } else { + assert(!root.checkOverlap(Span{j, j + 1})); + } + } + assert(root.checkOverlap(Span{10, N + 10})); + assert(!root.checkOverlap(Span{N + 10, N + 20})); + } + } + // Large numbers. + { + DisjointSpans root; + assert(!root.checkOverlap(Span{2948, 2949})); + root.add(Span{2948, 2949}); + assert(root.checkOverlap(Span{2948, 2949})); + assert(root.checkOverlap(Span{2940, 2949})); + assert(root.checkOverlap(Span{2948, 2959})); + assert(root.checkOverlap(Span{0, 18766})); + assert(!root.checkOverlap(Span{2000, 2001})); + assert(!root.checkOverlap(Span{3000, 3001})); + } + std::cout << "success.\n"; +} diff --git a/test/example/space.txt b/test/example/space.txt new file mode 100644 index 000000000..b32bb74d2 --- /dev/null +++ b/test/example/space.txt @@ -0,0 +1 @@ +success. diff --git a/test/passes/memory-packing_all-features.txt b/test/passes/memory-packing_all-features.txt index bc9139f74..2d183860c 100644 --- a/test/passes/memory-packing_all-features.txt +++ b/test/passes/memory-packing_all-features.txt @@ -7,9 +7,13 @@ (import "env" "memoryBase" (global $memoryBase i32)) ) (module - (type $none_=>_none (func)) (import "env" "memory" (memory $0 2048 2048)) (data (global.get $memoryBase) "waka this cannot be optimized\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00we don\'t know where it will go") + (import "env" "memoryBase" (global $memoryBase i32)) +) +(module + (type $none_=>_none (func)) + (memory $0 1 1) (data (i32.const 1024) "waka this CAN be optimized") (data (i32.const 1107) "we DO know where it will go") (data (i32.const 2057) "zeros before") @@ -17,7 +21,6 @@ (data (i32.const 4000) "zeros\00in\00the\00middle") (data (i32.const 4035) "nice skip here") (data (i32.const 4066) "another\00but no") - (import "env" "memoryBase" (global $memoryBase i32)) (func $nonzero-size-init-of-active-will-trap (block (drop @@ -1506,6 +1509,37 @@ ) ) (module + (memory $0 1 1) + (data (i32.const 1024) "x") + (data (i32.const 1024) "\00") +) +(module + (memory $0 1 1) + (data (i32.const 1024) "x") +) +(module + (memory $0 1 1) + (data (i32.const 1024) "x") +) +(module + (memory $0 1 1) + (data (i32.const 1024) "x") + (data (i32.const 1024) "\00") + (data (i32.const 4096) "\00") +) +(module + (import "env" "memory" (memory $0 1 1)) + (data (i32.const 1024) "x") + (data (global.get $memoryBase) "\00") + (import "env" "memoryBase" (global $memoryBase i32)) +) +(module + (import "env" "memory" (memory $0 1 1)) + (data (i32.const 1024) "\00") + (data (global.get $memoryBase) "x") + (import "env" "memoryBase" (global $memoryBase i32)) +) +(module (type $none_=>_none (func)) (import "env" "memory" (memory $mimport$0 1 1)) (data passive "skipped") diff --git a/test/passes/memory-packing_all-features.wast b/test/passes/memory-packing_all-features.wast index 3ee0bd5e7..9355c6dfa 100644 --- a/test/passes/memory-packing_all-features.wast +++ b/test/passes/memory-packing_all-features.wast @@ -15,6 +15,10 @@ (import "env" "memoryBase" (global $memoryBase i32)) (data (global.get $memoryBase) "waka this cannot be optimized\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00we don't know where it will go") +) + +(module + (memory 1 1) (data (i32.const 1024) "waka this CAN be optimized\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00we DO know where it will go") @@ -495,7 +499,39 @@ (data.drop 0) ) ) - +(module + (memory $0 1 1) + (data (i32.const 1024) "x") + (data (i32.const 1024) "\00") ;; this tramples the "x", and so must be kept. +) +(module + (memory $0 1 1) + (data (i32.const 1024) "x") + (data (i32.const 1025) "\00") +) +(module + (memory $0 1 1) + (data (i32.const 1024) "x") + (data (i32.const 1023) "\00") +) +(module + (memory $0 1 1) + (data (i32.const 1024) "x") + (data (i32.const 1024) "\00") ;; when we see one bad thing, we give up + (data (i32.const 4096) "\00") +) +(module + (import "env" "memory" (memory $0 1 1)) + (import "env" "memoryBase" (global $memoryBase i32)) + (data (i32.const 1024) "x") + (data (global.get $memoryBase) "\00") ;; this could trample, or not +) +(module + (import "env" "memory" (memory $0 1 1)) + (import "env" "memoryBase" (global $memoryBase i32)) + (data (i32.const 1024) "\00") ;; this could trample, or not + (data (global.get $memoryBase) "x") +) (module (import "env" "memory" (memory 1 1)) (data passive "skipped\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00included") |