| #include <iostream> |
| |
| #include "analysis/bits-bounds-lattice.h" |
| #include "analysis/bits-bounds-transfer-function.h" |
| #include "analysis/cfg.h" |
| #include "analysis/lattice.h" |
| #include "analysis/liveness-transfer-function.h" |
| #include "analysis/monotone-analyzer.h" |
| #include "analysis/reaching-definitions-transfer-function.h" |
| #include "analysis/stack-lattice.h" |
| #include "ir/find_all.h" |
| #include "print-test.h" |
| #include "wasm.h" |
| #include "gtest/gtest.h" |
| |
| using namespace wasm; |
| using namespace wasm::analysis; |
| |
| using CFGTest = PrintTest; |
| |
| TEST_F(CFGTest, Print) { |
| auto moduleText = R"wasm( |
| (module |
| (func $foo |
| (drop |
| (i32.const 0) |
| ) |
| (drop |
| (if (result i32) |
| (i32.const 1) |
| (block |
| (loop $loop |
| (br_if $loop |
| (i32.const 2) |
| ) |
| ) |
| (i32.const 3) |
| ) |
| (return |
| (i32.const 4) |
| ) |
| ) |
| ) |
| ) |
| ) |
| )wasm"; |
| |
| auto cfgText = R"cfg(;; preds: [], succs: [1, 5] |
| 0: |
| 0: i32.const 0 |
| 1: drop |
| 2: i32.const 1 |
| |
| ;; preds: [0], succs: [2] |
| 1: |
| |
| ;; preds: [1, 2], succs: [3, 2] |
| 2: |
| 3: i32.const 2 |
| 4: br_if $loop |
| |
| ;; preds: [2], succs: [4] |
| 3: |
| 5: loop $loop |
| |
| ;; preds: [3], succs: [6] |
| 4: |
| 6: i32.const 3 |
| 7: block |
| |
| ;; preds: [0], succs: [] |
| 5: |
| 8: i32.const 4 |
| 9: return |
| |
| ;; preds: [4], succs: [] |
| 6: |
| 10: drop |
| 11: block |
| )cfg"; |
| |
| Module wasm; |
| parseWast(wasm, moduleText); |
| |
| CFG cfg = CFG::fromFunction(wasm.getFunction("foo")); |
| |
| std::stringstream ss; |
| cfg.print(ss); |
| |
| EXPECT_EQ(ss.str(), cfgText); |
| } |
| |
| TEST_F(CFGTest, CallBlock) { |
| // Verify that a call instruction ends the current basic block. Even if the |
| // call has no control flow edges inside the function (no catches it can |
| // reach), we still end a basic block with the call, so that we preserve the |
| // property of basic blocks ending in possibly-control-flow-transferring |
| // instructions. |
| auto moduleText = R"wasm( |
| (module |
| (func $foo |
| (drop |
| (i32.const 0) |
| ) |
| (call $bar) |
| (drop |
| (i32.const 1) |
| ) |
| ) |
| (func $bar) |
| ) |
| )wasm"; |
| |
| auto cfgText = R"cfg(;; preds: [], succs: [1] |
| 0: |
| 0: i32.const 0 |
| 1: drop |
| 2: call $bar |
| |
| ;; preds: [0], succs: [] |
| 1: |
| 3: i32.const 1 |
| 4: drop |
| 5: block |
| )cfg"; |
| |
| Module wasm; |
| parseWast(wasm, moduleText); |
| |
| CFG cfg = CFG::fromFunction(wasm.getFunction("foo")); |
| |
| std::stringstream ss; |
| cfg.print(ss); |
| |
| EXPECT_EQ(ss.str(), cfgText); |
| } |
| |
| TEST_F(CFGTest, LinearLiveness) { |
| auto moduleText = R"wasm( |
| (module |
| (func $bar |
| (local $a (i32)) |
| (local $b (i32)) |
| (local $c (i32)) |
| (local.set $a |
| (i32.const 1) |
| ) |
| (drop |
| (local.get $a) |
| ) |
| (local.set $b |
| (local.get $a) |
| ) |
| (local.set $c |
| (i32.const 1) |
| ) |
| (drop |
| (local.get $c) |
| ) |
| ) |
| ) |
| )wasm"; |
| |
| auto analyzerText = R"analyzer(CFG Analyzer |
| CFG Block: 0 |
| Input State: 000 |
| Predecessors: |
| Successors: |
| Intermediate States (reverse order): |
| 000 |
| block |
| 000 |
| drop |
| 000 |
| local.get $2 |
| 001 |
| local.set $2 |
| 000 |
| i32.const 1 |
| 000 |
| local.set $1 |
| 000 |
| local.get $0 |
| 100 |
| drop |
| 100 |
| local.get $0 |
| 100 |
| local.set $0 |
| 000 |
| i32.const 1 |
| 000 |
| End |
| )analyzer"; |
| |
| Module wasm; |
| parseWast(wasm, moduleText); |
| |
| CFG cfg = CFG::fromFunction(wasm.getFunction("bar")); |
| size_t numLocals = wasm.getFunction("bar")->getNumLocals(); |
| |
| FiniteIntPowersetLattice lattice(numLocals); |
| LivenessTransferFunction transferFunction; |
| |
| MonotoneCFGAnalyzer<FiniteIntPowersetLattice, LivenessTransferFunction> |
| analyzer(lattice, transferFunction, cfg); |
| analyzer.evaluate(); |
| |
| std::stringstream ss; |
| analyzer.print(ss); |
| |
| EXPECT_EQ(ss.str(), analyzerText); |
| } |
| |
| TEST_F(CFGTest, NonlinearLiveness) { |
| auto moduleText = R"wasm( |
| (module |
| (func $bar |
| (local $a (i32)) |
| (local $b (i32)) |
| (local.set $a |
| (i32.const 1) |
| ) |
| (if |
| (i32.eq |
| (local.get $a) |
| (i32.const 2) |
| ) |
| (local.set $b |
| (i32.const 4) |
| ) |
| (drop |
| (local.get $a) |
| ) |
| ) |
| ) |
| ) |
| )wasm"; |
| |
| auto analyzerText = R"analyzer(CFG Analyzer |
| CFG Block: 0 |
| Input State: 10 |
| Predecessors: |
| Successors: 1 2 |
| Intermediate States (reverse order): |
| 10 |
| i32.eq |
| 10 |
| i32.const 2 |
| 10 |
| local.get $0 |
| 10 |
| local.set $0 |
| 00 |
| i32.const 1 |
| 00 |
| CFG Block: 1 |
| Input State: 00 |
| Predecessors: 0 |
| Successors: 3 |
| Intermediate States (reverse order): |
| 00 |
| local.set $1 |
| 00 |
| i32.const 4 |
| 00 |
| CFG Block: 2 |
| Input State: 00 |
| Predecessors: 0 |
| Successors: 3 |
| Intermediate States (reverse order): |
| 00 |
| drop |
| 00 |
| local.get $0 |
| 10 |
| CFG Block: 3 |
| Input State: 00 |
| Predecessors: 2 1 |
| Successors: |
| Intermediate States (reverse order): |
| 00 |
| block |
| 00 |
| End |
| )analyzer"; |
| |
| Module wasm; |
| parseWast(wasm, moduleText); |
| |
| CFG cfg = CFG::fromFunction(wasm.getFunction("bar")); |
| size_t numLocals = wasm.getFunction("bar")->getNumLocals(); |
| |
| FiniteIntPowersetLattice lattice(numLocals); |
| LivenessTransferFunction transferFunction; |
| |
| MonotoneCFGAnalyzer<FiniteIntPowersetLattice, LivenessTransferFunction> |
| analyzer(lattice, transferFunction, cfg); |
| analyzer.evaluate(); |
| |
| std::stringstream ss; |
| analyzer.print(ss); |
| |
| EXPECT_EQ(ss.str(), analyzerText); |
| } |
| |
| TEST_F(CFGTest, FinitePowersetLatticeFunctioning) { |
| |
| std::vector<std::string> initialSet = {"a", "b", "c", "d", "e", "f"}; |
| FinitePowersetLattice<std::string> lattice(std::move(initialSet)); |
| |
| auto element1 = lattice.getBottom(); |
| |
| EXPECT_TRUE(element1.isBottom()); |
| EXPECT_FALSE(element1.isTop()); |
| |
| lattice.add(&element1, "c"); |
| lattice.add(&element1, "d"); |
| lattice.add(&element1, "a"); |
| |
| EXPECT_FALSE(element1.isBottom()); |
| EXPECT_FALSE(element1.isTop()); |
| |
| auto element2 = element1; |
| lattice.remove(&element2, "c"); |
| EXPECT_EQ(lattice.compare(element1, element2), LatticeComparison::GREATER); |
| lattice.add(&element2, "f"); |
| EXPECT_EQ(lattice.compare(element1, element2), |
| LatticeComparison::NO_RELATION); |
| |
| std::stringstream ss; |
| element1.print(ss); |
| EXPECT_EQ(ss.str(), "101100"); |
| ss.str(std::string()); |
| element2.print(ss); |
| EXPECT_EQ(ss.str(), "100101"); |
| ss.str(std::string()); |
| element2.makeLeastUpperBound(element1); |
| element2.print(ss); |
| EXPECT_EQ(ss.str(), "101101"); |
| } |
| |
| TEST_F(CFGTest, BlockIndexes) { |
| auto moduleText = R"wasm( |
| (module |
| (func $foo |
| (if |
| (i32.const 1) |
| (block |
| (drop |
| (i32.const 2) |
| ) |
| (drop |
| (i32.const 3) |
| ) |
| ) |
| ) |
| ) |
| ) |
| )wasm"; |
| |
| Module wasm; |
| parseWast(wasm, moduleText); |
| |
| auto* func = wasm.getFunction("foo"); |
| CFG cfg = CFG::fromFunction(func); |
| CFGBlockIndexes indexes(cfg); |
| |
| // The body of the function is an if. An if is a control flow structure and so |
| // it has no basic block (it can contain multiple ones). |
| auto* iff = func->body->cast<If>(); |
| EXPECT_EQ(indexes.get(iff), indexes.InvalidBlock); |
| |
| // The constant 1 is in the entry block. |
| EXPECT_EQ(indexes.get(iff->condition), Index(0)); |
| |
| // The dropped constants 2 and three are in another block, together. |
| auto* block = iff->ifTrue->cast<Block>(); |
| EXPECT_EQ(indexes.get(block->list[0]), Index(1)); |
| EXPECT_EQ(indexes.get(block->list[1]), Index(1)); |
| } |
| |
| TEST_F(CFGTest, LinearReachingDefinitions) { |
| auto moduleText = R"wasm( |
| (module |
| (func $bar |
| (local $a (i32)) |
| (local $b (i32)) |
| (local $c (i32)) |
| (local.set $a |
| (i32.const 1) |
| ) |
| (drop |
| (local.get $a) |
| ) |
| (local.set $b |
| (local.get $a) |
| ) |
| (drop |
| (local.get $c) |
| ) |
| (local.set $c |
| (i32.const 1) |
| ) |
| (local.set $a |
| (i32.const 2) |
| ) |
| ) |
| ) |
| )wasm"; |
| |
| Module wasm; |
| parseWast(wasm, moduleText); |
| |
| Function* func = wasm.getFunction("bar"); |
| CFG cfg = CFG::fromFunction(func); |
| |
| LocalGraph::GetSetses getSetses; |
| LocalGraph::Locations locations; |
| ReachingDefinitionsTransferFunction transferFunction( |
| func, getSetses, locations); |
| |
| MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>, |
| ReachingDefinitionsTransferFunction> |
| analyzer(transferFunction.lattice, transferFunction, cfg); |
| |
| // TODO: Make evaluating function entry point more automatic (i.e. part of |
| // existing evaluate call). |
| analyzer.evaluateFunctionEntry(func); |
| analyzer.evaluateAndCollectResults(); |
| |
| FindAll<LocalSet> foundSets(func->body); |
| FindAll<LocalGet> foundGets(func->body); |
| |
| LocalGet* getA1 = foundGets.list[0]; |
| LocalGet* getA2 = foundGets.list[1]; |
| LocalGet* getC = foundGets.list[2]; |
| LocalSet* setA1 = foundSets.list[0]; |
| |
| LocalGraph::GetSetses expectedResult; |
| expectedResult[getA1].insert(setA1); |
| expectedResult[getA2].insert(setA1); |
| expectedResult[getC].insert(nullptr); |
| |
| EXPECT_EQ(expectedResult, getSetses); |
| } |
| |
| TEST_F(CFGTest, ReachingDefinitionsIf) { |
| auto moduleText = R"wasm( |
| (module |
| (func $bar |
| (local $a (i32)) |
| (local $b (i32)) |
| (local.set $a |
| (i32.const 1) |
| ) |
| (if |
| (i32.eq |
| (local.get $a) |
| (i32.const 2) |
| ) |
| (local.set $b |
| (i32.const 3) |
| ) |
| (local.set $a |
| (i32.const 4) |
| ) |
| ) |
| (drop |
| (local.get $b) |
| ) |
| (drop |
| (local.get $a) |
| ) |
| ) |
| ) |
| )wasm"; |
| |
| Module wasm; |
| parseWast(wasm, moduleText); |
| |
| Function* func = wasm.getFunction("bar"); |
| CFG cfg = CFG::fromFunction(func); |
| |
| LocalGraph::GetSetses getSetses; |
| LocalGraph::Locations locations; |
| ReachingDefinitionsTransferFunction transferFunction( |
| func, getSetses, locations); |
| |
| MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>, |
| ReachingDefinitionsTransferFunction> |
| analyzer(transferFunction.lattice, transferFunction, cfg); |
| analyzer.evaluateFunctionEntry(func); |
| analyzer.evaluateAndCollectResults(); |
| |
| FindAll<LocalSet> foundSets(func->body); |
| FindAll<LocalGet> foundGets(func->body); |
| |
| LocalGet* getA1 = foundGets.list[0]; |
| LocalGet* getB = foundGets.list[1]; |
| LocalGet* getA2 = foundGets.list[2]; |
| LocalSet* setA1 = foundSets.list[0]; |
| LocalSet* setB = foundSets.list[1]; |
| LocalSet* setA2 = foundSets.list[2]; |
| |
| LocalGraph::GetSetses expectedResult; |
| expectedResult[getA1].insert(setA1); |
| expectedResult[getB].insert(nullptr); |
| expectedResult[getB].insert(setB); |
| expectedResult[getA2].insert(setA1); |
| expectedResult[getA2].insert(setA2); |
| |
| EXPECT_EQ(expectedResult, getSetses); |
| } |
| |
| TEST_F(CFGTest, ReachingDefinitionsLoop) { |
| auto moduleText = R"wasm( |
| (module |
| (func $bar (param $a (i32)) (param $b (i32)) |
| (loop $loop |
| (drop |
| (local.get $a) |
| ) |
| (local.set $a |
| (i32.add |
| (i32.const 1) |
| (local.get $a) |
| ) |
| ) |
| (br_if $loop |
| (i32.le_u |
| (local.get $a) |
| (i32.const 7) |
| ) |
| ) |
| ) |
| (local.set $b |
| (i32.sub |
| (local.get $b) |
| (local.get $a) |
| ) |
| ) |
| ) |
| ) |
| )wasm"; |
| |
| Module wasm; |
| parseWast(wasm, moduleText); |
| |
| Function* func = wasm.getFunction("bar"); |
| CFG cfg = CFG::fromFunction(func); |
| |
| LocalGraph::GetSetses getSetses; |
| LocalGraph::Locations locations; |
| ReachingDefinitionsTransferFunction transferFunction( |
| func, getSetses, locations); |
| |
| MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>, |
| ReachingDefinitionsTransferFunction> |
| analyzer(transferFunction.lattice, transferFunction, cfg); |
| analyzer.evaluateFunctionEntry(func); |
| analyzer.evaluateAndCollectResults(); |
| |
| FindAll<LocalSet> foundSets(func->body); |
| FindAll<LocalGet> foundGets(func->body); |
| |
| LocalGet* getA1 = foundGets.list[0]; |
| LocalGet* getA2 = foundGets.list[1]; |
| LocalGet* getA3 = foundGets.list[2]; |
| LocalGet* getB = foundGets.list[3]; |
| LocalGet* getA4 = foundGets.list[4]; |
| LocalSet* setA = foundSets.list[0]; |
| |
| LocalGraph::GetSetses expectedResult; |
| expectedResult[getA1].insert(nullptr); |
| expectedResult[getA1].insert(setA); |
| expectedResult[getA2].insert(nullptr); |
| expectedResult[getA2].insert(setA); |
| expectedResult[getA3].insert(setA); |
| expectedResult[getB].insert(nullptr); |
| expectedResult[getA4].insert(setA); |
| |
| EXPECT_EQ(expectedResult, getSetses); |
| } |
| |
| TEST_F(CFGTest, StackLatticeFunctioning) { |
| FiniteIntPowersetLattice contentLattice(4); |
| StackLattice<FiniteIntPowersetLattice> stackLattice(contentLattice); |
| |
| // These are constructed as expected references to compare everything else. |
| StackLattice<FiniteIntPowersetLattice>::Element expectedStack = |
| stackLattice.getBottom(); |
| FiniteIntPowersetLattice::Element expectedStackElement = |
| contentLattice.getBottom(); |
| |
| StackLattice<FiniteIntPowersetLattice>::Element firstStack = |
| stackLattice.getBottom(); |
| StackLattice<FiniteIntPowersetLattice>::Element secondStack = |
| stackLattice.getBottom(); |
| |
| for (size_t i = 0; i < 4; i++) { |
| FiniteIntPowersetLattice::Element temp = contentLattice.getBottom(); |
| for (size_t j = 0; j <= i; j++) { |
| temp.set(j, true); |
| } |
| firstStack.push(temp); |
| secondStack.push(temp); |
| if (i < 2) { |
| expectedStack.push(temp); |
| } |
| } |
| |
| EXPECT_EQ(stackLattice.compare(firstStack, secondStack), |
| LatticeComparison::EQUAL); |
| |
| for (size_t j = 0; j < 4; ++j) { |
| expectedStackElement.set(j, true); |
| } |
| |
| EXPECT_EQ(contentLattice.compare(secondStack.pop(), expectedStackElement), |
| LatticeComparison::EQUAL); |
| expectedStackElement.set(3, false); |
| EXPECT_EQ(contentLattice.compare(secondStack.pop(), expectedStackElement), |
| LatticeComparison::EQUAL); |
| |
| EXPECT_EQ(stackLattice.compare(firstStack, secondStack), |
| LatticeComparison::GREATER); |
| EXPECT_EQ(stackLattice.compare(secondStack, firstStack), |
| LatticeComparison::LESS); |
| |
| EXPECT_EQ(stackLattice.compare(secondStack, expectedStack), |
| LatticeComparison::EQUAL); |
| |
| { |
| expectedStack.stackTop().set(0, false); |
| expectedStack.stackTop().set(2, true); |
| FiniteIntPowersetLattice::Element temp = expectedStack.pop(); |
| expectedStack.stackTop().set(3, true); |
| expectedStack.push(temp); |
| |
| FiniteIntPowersetLattice::Element temp2 = contentLattice.getBottom(); |
| temp2.set(1, true); |
| temp2.set(3, true); |
| expectedStack.push(temp2); |
| } |
| |
| StackLattice<FiniteIntPowersetLattice>::Element thirdStack = |
| stackLattice.getBottom(); |
| { |
| FiniteIntPowersetLattice::Element temp = contentLattice.getBottom(); |
| temp.set(0, true); |
| temp.set(3, true); |
| FiniteIntPowersetLattice::Element temp2 = contentLattice.getBottom(); |
| temp2.set(1, true); |
| temp2.set(2, true); |
| FiniteIntPowersetLattice::Element temp3 = contentLattice.getBottom(); |
| temp3.set(1, true); |
| temp3.set(3, true); |
| thirdStack.push(std::move(temp)); |
| thirdStack.push(std::move(temp2)); |
| thirdStack.push(std::move(temp3)); |
| } |
| |
| EXPECT_EQ(stackLattice.compare(secondStack, thirdStack), |
| LatticeComparison::NO_RELATION); |
| |
| EXPECT_EQ(stackLattice.compare(thirdStack, expectedStack), |
| LatticeComparison::EQUAL); |
| |
| EXPECT_EQ(thirdStack.makeLeastUpperBound(secondStack), true); |
| |
| { |
| expectedStack.stackTop().set(0, true); |
| FiniteIntPowersetLattice::Element temp = expectedStack.pop(); |
| expectedStack.stackTop().set(0, true); |
| expectedStack.push(temp); |
| } |
| |
| EXPECT_EQ(stackLattice.compare(thirdStack, expectedStack), |
| LatticeComparison::EQUAL); |
| } |
| |
| // TODO: Add more thorough test cases for max bits analysis. |
| TEST_F(CFGTest, MaxBitsAnalysis) { |
| auto moduleText = R"wasm( |
| (module |
| (func $bar (param $x (i32)) |
| (local.set $x (i32.mul (i32.const 1234) (i32.const 432))) |
| (local.set $x (i32.add (i32.const 64) (i32.const 32))) |
| (local.set $x (i32.xor (i32.const 123) (i32.const 47))) |
| ) |
| ) |
| )wasm"; |
| |
| Module wasm; |
| parseWast(wasm, moduleText); |
| |
| Function* func = wasm.getFunction("bar"); |
| CFG cfg = CFG::fromFunction(func); |
| |
| MaxBitsLattice maxBitsLattice; |
| StackLattice<MaxBitsLattice> lattice(maxBitsLattice); |
| |
| MaxBitsTransferFunction transferFunction(maxBitsLattice); |
| MonotoneCFGAnalyzer<StackLattice<MaxBitsLattice>, MaxBitsTransferFunction> |
| analyzer(lattice, transferFunction, cfg); |
| analyzer.evaluateAndCollectResults(); |
| |
| for (auto cfgBlock = cfg.begin(); cfgBlock != cfg.end(); ++cfgBlock) { |
| for (auto expr = cfgBlock->begin(); expr != cfgBlock->end(); ++expr) { |
| std::cout << ShallowExpression{*expr} << " " |
| << transferFunction.exprMaxBounds[*expr] << std::endl; |
| } |
| } |
| } |
