From bcc6205e83ec98f9b3d5704b79255a853a4ee8bd Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Thu, 30 Nov 2017 11:12:17 -0800 Subject: De-morgan's "and" law (#1297) (eqz X) and (eqz Y) === eqz (X or Y) Normally de-morgan's laws apply only to boolean vars, but for the and (but not or or xor) version, it works in all cases (both sides are true iff X and Y have all zero bits). --- src/passes/OptimizeInstructions.cpp | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) (limited to 'src') diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 37fb37ace..06f3d5b02 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -562,6 +562,32 @@ struct OptimizeInstructions : public WalkerPassop == AndInt32) { + // try de-morgan's AND law, + // (eqz X) and (eqz Y) === eqz (X or Y) + // Note that the OR and XOR laws do not work here, as these + // are not booleans (we could check if they are, but a boolean + // would already optimize with the eqz anyhow, unless propagating). + // But for AND, the left is true iff X and Y are each all zero bits, + // and the right is true if the union of their bits is zero; same. + if (auto* left = binary->left->dynCast()) { + if (left->op == EqZInt32) { + if (auto* right = binary->right->dynCast()) { + if (right->op == EqZInt32) { + // reuse one unary, drop the other + auto* leftValue = left->value; + left->value = binary; + binary->left = leftValue; + binary->right = right->value; + binary->op = OrInt32; + return left; + } + } + } + } + } + // for and and or, we can potentially conditionalize if (binary->op == AndInt32 || binary->op == OrInt32) { return conditionalizeExpensiveOnBitwise(binary); } -- cgit v1.2.3