Adding folding rules for commutive bitwise operations (xor/or/and). (#6358)
This change adds the following reassociations:
* `A | (b | C) = b | (A | C)`
* `A ^ (b ^ C) = b ^ (A ^ C)`
* `A & (b & C) = b & (A & C)`
Where A and C are constants
diff --git a/source/opt/folding_rules.cpp b/source/opt/folding_rules.cpp
index 8c4fd0e..ee2f24e 100644
--- a/source/opt/folding_rules.cpp
+++ b/source/opt/folding_rules.cpp
@@ -679,6 +679,15 @@
case spv::Op::OpISub:
FOLD_OP(-);
break;
+ case spv::Op::OpBitwiseXor:
+ FOLD_OP(^);
+ break;
+ case spv::Op::OpBitwiseOr:
+ FOLD_OP(|);
+ break;
+ case spv::Op::OpBitwiseAnd:
+ FOLD_OP(&);
+ break;
default:
assert(false && "Unexpected operation");
break;
@@ -2700,6 +2709,56 @@
return RedundantBinaryOpWithZeroOperand(0, 0);
}
+FoldingRule ReassociateCommutiveOp() {
+ return [](IRContext* context, Instruction* inst,
+ const std::vector<const analysis::Constant*>& constants) {
+ const analysis::Type* type =
+ context->get_type_mgr()->GetType(inst->type_id());
+ uint32_t width = ElementWidth(type);
+ if (width != 32) return false;
+
+ analysis::ConstantManager* const_mgr = context->get_constant_mgr();
+ const analysis::Constant* const_input1 = ConstInput(constants);
+ if (!const_input1) return false;
+ Instruction* other_inst = NonConstInput(context, constants[0], inst);
+
+ if (other_inst->opcode() == inst->opcode()) {
+ std::vector<const analysis::Constant*> other_constants =
+ const_mgr->GetOperandConstants(other_inst);
+ const analysis::Constant* const_input2 = ConstInput(other_constants);
+ if (!const_input2) return false;
+
+ Instruction* non_const_input =
+ NonConstInput(context, other_constants[0], other_inst);
+ uint32_t merged_id = PerformOperation(const_mgr, inst->opcode(),
+ const_input1, const_input2);
+
+ if (merged_id == 0) return false;
+ inst->SetInOperands(
+ {{SPV_OPERAND_TYPE_ID, {non_const_input->result_id()}},
+ {SPV_OPERAND_TYPE_ID, {merged_id}}});
+ return true;
+ }
+
+ return false;
+ };
+}
+
+// A | (b | C) = b | (A | C)
+// A ^ (b ^ C) = b ^ (A ^ C)
+// A & (b & C) = b & (A & C)
+// Where A and C are constants
+static const constexpr spv::Op ReassociateCommutiveBitwiseOps[] = {
+ spv::Op::OpBitwiseOr, spv::Op::OpBitwiseXor, spv::Op::OpBitwiseAnd};
+FoldingRule ReassociateCommutiveBitwise(spv::Op op) {
+ assert(std::find(std::begin(ReassociateCommutiveBitwiseOps),
+ std::end(ReassociateCommutiveBitwiseOps),
+ op) != std::end(ReassociateCommutiveBitwiseOps) &&
+ "Wrong opcode.");
+ (void)op;
+ return ReassociateCommutiveOp();
+}
+
// Returns true if all elements in |c| are 1.
bool IsAllInt1(const analysis::Constant* c) {
if (auto composite = c->AsCompositeConstant()) {
@@ -3103,6 +3162,8 @@
rules_[op].push_back(RedundantBinaryLhs0(op));
for (auto op : RedundantBinaryLhs0To0Ops)
rules_[op].push_back(RedundantBinaryLhs0To0(op));
+ for (auto op : ReassociateCommutiveBitwiseOps)
+ rules_[op].push_back(ReassociateCommutiveBitwise(op));
rules_[spv::Op::OpSDiv].push_back(RedundantSUDiv());
rules_[spv::Op::OpUDiv].push_back(RedundantSUDiv());
rules_[spv::Op::OpSMod].push_back(RedundantSUMod());
diff --git a/test/opt/fold_test.cpp b/test/opt/fold_test.cpp
index 163f207..00c52f7 100644
--- a/test/opt/fold_test.cpp
+++ b/test/opt/fold_test.cpp
@@ -6674,6 +6674,221 @@
4, false)
));
+INSTANTIATE_TEST_SUITE_P(ReassociateCommutiveBitwiseTest, MatchingInstructionFoldingTest,
+ ::testing::Values(
+ // Test case 0: fold (n ^ 248) ^ 31 = n ^ 231
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_248 = OpConstant %uint 248\n" +
+ "%uint_31 = OpConstant %uint 31\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_231:%\\w+]] = OpConstant [[uint]] 231\n" +
+ "; CHECK: %2 = OpBitwiseXor [[uint]] %4 [[uint_231]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseXor %uint %4 %uint_248\n" +
+ "%2 = OpBitwiseXor %uint %3 %uint_31\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 1: fold 31 ^ (n ^ 248) = n ^ 231
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_248 = OpConstant %uint 248\n" +
+ "%uint_31 = OpConstant %uint 31\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_231:%\\w+]] = OpConstant [[uint]] 231\n" +
+ "; CHECK: %2 = OpBitwiseXor [[uint]] %4 [[uint_231]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseXor %uint %4 %uint_248\n" +
+ "%2 = OpBitwiseXor %uint %uint_31 %3\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 2: fold (248 ^ n) ^ 31 = n ^ 231
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_248 = OpConstant %uint 248\n" +
+ "%uint_31 = OpConstant %uint 31\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_231:%\\w+]] = OpConstant [[uint]] 231\n" +
+ "; CHECK: %2 = OpBitwiseXor [[uint]] %4 [[uint_231]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseXor %uint %uint_248 %4\n" +
+ "%2 = OpBitwiseXor %uint %3 %uint_31\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 3: fold 31 ^ (248 ^ n) = n ^ 231
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_248 = OpConstant %uint 248\n" +
+ "%uint_31 = OpConstant %uint 31\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_231:%\\w+]] = OpConstant [[uint]] 231\n" +
+ "; CHECK: %2 = OpBitwiseXor [[uint]] %4 [[uint_231]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseXor %uint %uint_248 %4\n" +
+ "%2 = OpBitwiseXor %uint %uint_31 %3\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 4: fold 3 | (n | 193) = n | 195
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_193 = OpConstant %uint 193\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_195:%\\w+]] = OpConstant [[uint]] 195\n" +
+ "; CHECK: %2 = OpBitwiseOr [[uint]] %4 [[uint_195]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseOr %uint %4 %uint_193\n" +
+ "%2 = OpBitwiseOr %uint %uint_3 %3\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 5: fold (n | 193) | 3 = n | 195
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_193 = OpConstant %uint 193\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_195:%\\w+]] = OpConstant [[uint]] 195\n" +
+ "; CHECK: %2 = OpBitwiseOr [[uint]] %4 [[uint_195]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseOr %uint %4 %uint_193\n" +
+ "%2 = OpBitwiseOr %uint %3 %uint_3\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 6: fold 3 | (193 | n) = n | 195
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_193 = OpConstant %uint 193\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_195:%\\w+]] = OpConstant [[uint]] 195\n" +
+ "; CHECK: %2 = OpBitwiseOr [[uint]] %4 [[uint_195]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseOr %uint %uint_193 %4\n" +
+ "%2 = OpBitwiseOr %uint %uint_3 %3\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 7: fold (193 | n) | 3 = n | 195
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_193 = OpConstant %uint 193\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_195:%\\w+]] = OpConstant [[uint]] 195\n" +
+ "; CHECK: %2 = OpBitwiseOr [[uint]] %4 [[uint_195]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseOr %uint %uint_193 %4\n" +
+ "%2 = OpBitwiseOr %uint %3 %uint_3\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 8: fold 65520 & (n & 4095) = n & 4080
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_65520 = OpConstant %uint 65520\n" +
+ "%uint_4095 = OpConstant %uint 4095\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_4080:%\\w+]] = OpConstant [[uint]] 4080\n" +
+ "; CHECK: %2 = OpBitwiseAnd [[uint]] %4 [[uint_4080]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseAnd %uint %4 %uint_4095\n" +
+ "%2 = OpBitwiseAnd %uint %uint_65520 %3\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 9: fold (n & 4095) & 65520 = n & 4080
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_65520 = OpConstant %uint 65520\n" +
+ "%uint_4095 = OpConstant %uint 4095\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_4080:%\\w+]] = OpConstant [[uint]] 4080\n" +
+ "; CHECK: %2 = OpBitwiseAnd [[uint]] %4 [[uint_4080]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseAnd %uint %4 %uint_4095\n" +
+ "%2 = OpBitwiseAnd %uint %3 %uint_65520\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 10: fold 65520 & (4095 & n) = n & 4080
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_65520 = OpConstant %uint 65520\n" +
+ "%uint_4095 = OpConstant %uint 4095\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_4080:%\\w+]] = OpConstant [[uint]] 4080\n" +
+ "; CHECK: %2 = OpBitwiseAnd [[uint]] %4 [[uint_4080]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseAnd %uint %uint_4095 %4\n" +
+ "%2 = OpBitwiseAnd %uint %uint_65520 %3\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true),
+
+ // Test case 11: fold (4095 & n) & 65520 = n & 4080
+ InstructionFoldingCase<bool>(
+ Header() +
+ "%uint_65520 = OpConstant %uint 65520\n" +
+ "%uint_4095 = OpConstant %uint 4095\n" +
+ "; CHECK: [[uint:%\\w+]] = OpTypeInt 32 0\n" +
+ "; CHECK: [[uint_4080:%\\w+]] = OpConstant [[uint]] 4080\n" +
+ "; CHECK: %2 = OpBitwiseAnd [[uint]] %4 [[uint_4080]]\n" +
+ "%main = OpFunction %void None %void_func\n" +
+ "%main_lab = OpLabel\n" +
+ "%n = OpVariable %_ptr_uint Function\n" +
+ "%4 = OpLoad %uint %n\n" +
+ "%3 = OpBitwiseAnd %uint %uint_4095 %4\n" +
+ "%2 = OpBitwiseAnd %uint %3 %uint_65520\n" +
+ "OpReturn\n" +
+ "OpFunctionEnd",
+ 2, true)
+));
+
INSTANTIATE_TEST_SUITE_P(ReciprocalFDivTest, MatchingInstructionFoldingTest,
::testing::Values(
// Test case 0: scalar reicprocal
