summaryrefslogtreecommitdiff
path: root/fpoptimizer/logic_boolgroups.hh
diff options
context:
space:
mode:
Diffstat (limited to 'fpoptimizer/logic_boolgroups.hh')
-rw-r--r--fpoptimizer/logic_boolgroups.hh382
1 files changed, 382 insertions, 0 deletions
diff --git a/fpoptimizer/logic_boolgroups.hh b/fpoptimizer/logic_boolgroups.hh
new file mode 100644
index 0000000..a6e284e
--- /dev/null
+++ b/fpoptimizer/logic_boolgroups.hh
@@ -0,0 +1,382 @@
+#include "codetree.hh"
+
+namespace
+{
+ using namespace FUNCTIONPARSERTYPES;
+ using namespace FPoptimizer_CodeTree;
+
+ /***************************/
+ /* LOGIC (AND, OR, NOT) */
+ /***************************/
+
+ struct ComparisonSetBase
+ {
+ enum { Lt_Mask = 0x1, // 1=less
+ Eq_Mask = 0x2, // 2=equal
+ Le_Mask = 0x3, // 1+2 = Less or Equal
+ Gt_Mask = 0x4, // 4=greater
+ Ne_Mask = 0x5, // 4+1 = Greater or Less, i.e. Not equal
+ Ge_Mask = 0x6 }; // 4+2 = Greater or Equal
+ static int Swap_Mask(int m) { return (m&Eq_Mask)
+ | ((m&Lt_Mask) ? Gt_Mask : 0)
+ | ((m&Gt_Mask) ? Lt_Mask : 0); }
+ enum RelationshipResult
+ {
+ Ok,
+ BecomeZero,
+ BecomeOne,
+ Suboptimal
+ };
+ enum ConditionType
+ {
+ cond_or,
+ cond_and,
+ cond_mul,
+ cond_add
+ };
+ };
+
+ template<typename Value_t>
+ struct ComparisonSet: public ComparisonSetBase /* For optimizing And, Or */
+ {
+ struct Comparison
+ {
+ CodeTree<Value_t> a;
+ CodeTree<Value_t> b;
+ int relationship;
+
+ Comparison() : a(),b(), relationship() {}
+ };
+ std::vector<Comparison> relationships;
+ struct Item
+ {
+ CodeTree<Value_t> value;
+ bool negated;
+
+ Item() : value(), negated(false) {}
+ };
+ std::vector<Item> plain_set;
+ int const_offset;
+
+ ComparisonSet():
+ relationships(),
+ plain_set(),
+ const_offset(0)
+ {
+ }
+
+ RelationshipResult AddItem(
+ const CodeTree<Value_t>& a,
+ bool negated,
+ ConditionType type)
+ {
+ for(size_t c=0; c<plain_set.size(); ++c)
+ if(plain_set[c].value.IsIdenticalTo(a))
+ {
+ if(negated != plain_set[c].negated)
+ {
+ switch(type)
+ {
+ case cond_or:
+ return BecomeOne;
+ case cond_add:
+ plain_set.erase(plain_set.begin() + c);
+ const_offset += 1;
+ return Suboptimal;
+ case cond_and:
+ case cond_mul:
+ return BecomeZero;
+ }
+ }
+ return Suboptimal;
+ }
+ Item pole;
+ pole.value = a;
+ pole.negated = negated;
+ plain_set.push_back(pole);
+ return Ok;
+ }
+
+ /* Note: Trees are passed by-value so we can use swap() on them safely. */
+ RelationshipResult AddRelationship
+ (CodeTree<Value_t> a,
+ CodeTree<Value_t> b,
+ int reltype,
+ ConditionType type)
+ {
+ switch(type)
+ {
+ case cond_or:
+ if(reltype == 7) return BecomeOne;
+ break;
+ case cond_add:
+ if(reltype == 7) { const_offset += 1; return Suboptimal; }
+ break;
+ case cond_and:
+ case cond_mul:
+ if(reltype == 0) return BecomeZero;
+ break;
+ }
+
+ if(!(a.GetHash() < b.GetHash()))
+ {
+ a.swap(b);
+ reltype = Swap_Mask(reltype);
+ }
+
+ for(size_t c=0; c<relationships.size(); ++c)
+ {
+ if(relationships[c].a.IsIdenticalTo(a)
+ && relationships[c].b.IsIdenticalTo(b))
+ {
+ switch(type)
+ {
+ case cond_or:
+ {
+ int newrel = relationships[c].relationship | reltype;
+ if(newrel == 7) return BecomeOne;
+ relationships[c].relationship = newrel;
+ break;
+ }
+ case cond_and:
+ case cond_mul:
+ {
+ int newrel = relationships[c].relationship & reltype;
+ if(newrel == 0) return BecomeZero;
+ relationships[c].relationship = newrel;
+ break;
+ }
+ case cond_add:
+ {
+ int newrel_or = relationships[c].relationship | reltype;
+ int newrel_and = relationships[c].relationship & reltype;
+ if(newrel_or == 5 // < + >
+ && newrel_and == 0)
+ {
+ // (x<y) + (x>y) = x!=y
+ relationships[c].relationship = Ne_Mask;
+ return Suboptimal;
+ }
+ if(newrel_or == 7
+ && newrel_and == 0)
+ {
+ // (x<y) + (x>=y) = 1
+ // (x<=y) + (x>y) = 1
+ // (x=y) + (x!=y) = 1
+ const_offset += 1;
+ relationships.erase(relationships.begin()+c);
+ return Suboptimal;
+ }
+ if(newrel_or == 7
+ && newrel_and == Eq_Mask)
+ {
+ // (x<=y) + (x>=y) = 1 + (x=y)
+ relationships[c].relationship = Eq_Mask;
+ const_offset += 1;
+ return Suboptimal;
+ }
+ continue;
+ }
+ }
+ return Suboptimal;
+ }
+ }
+ Comparison comp;
+ comp.a = a;
+ comp.b = b;
+ comp.relationship = reltype;
+ relationships.push_back(comp);
+ return Ok;
+ }
+ };
+
+ template<typename Value_t, typename CondType> /* ComparisonSet::ConditionType */
+ bool ConstantFolding_LogicCommon(
+ CodeTree<Value_t>& tree, CondType cond_type, bool is_logical)
+ {
+ bool should_regenerate = false;
+ ComparisonSet<Value_t> comp;
+ for(size_t a=0; a<tree.GetParamCount(); ++a)
+ {
+ typename ComparisonSetBase::RelationshipResult
+ change = ComparisonSetBase::Ok;
+ const CodeTree<Value_t>& atree = tree.GetParam(a);
+ switch(atree.GetOpcode())
+ {
+ case cEqual:
+ change = comp.AddRelationship(atree.GetParam(0), atree.GetParam(1), ComparisonSetBase::Eq_Mask, cond_type);
+ break;
+ case cNEqual:
+ change = comp.AddRelationship(atree.GetParam(0), atree.GetParam(1), ComparisonSetBase::Ne_Mask, cond_type);
+ break;
+ case cLess:
+ change = comp.AddRelationship(atree.GetParam(0), atree.GetParam(1), ComparisonSetBase::Lt_Mask, cond_type);
+ break;
+ case cLessOrEq:
+ change = comp.AddRelationship(atree.GetParam(0), atree.GetParam(1), ComparisonSetBase::Le_Mask, cond_type);
+ break;
+ case cGreater:
+ change = comp.AddRelationship(atree.GetParam(0), atree.GetParam(1), ComparisonSetBase::Gt_Mask, cond_type);
+ break;
+ case cGreaterOrEq:
+ change = comp.AddRelationship(atree.GetParam(0), atree.GetParam(1), ComparisonSetBase::Ge_Mask, cond_type);
+ break;
+ case cNot:
+ change = comp.AddItem(atree.GetParam(0), true, cond_type);
+ break;
+ case cNotNot:
+ change = comp.AddItem(atree.GetParam(0), false, cond_type);
+ break;
+ default:
+ if(is_logical || IsLogicalValue(atree))
+ change = comp.AddItem(atree, false, cond_type);
+ }
+ switch(change)
+ {
+ ReplaceTreeWithZero:
+ tree.ReplaceWithImmed(0);
+ return true;
+ ReplaceTreeWithOne:
+ tree.ReplaceWithImmed(1);
+ return true;
+ case ComparisonSetBase::Ok: // ok
+ break;
+ case ComparisonSetBase::BecomeZero: // whole set was invalidated
+ goto ReplaceTreeWithZero;
+ case ComparisonSetBase::BecomeOne: // whole set was validated
+ goto ReplaceTreeWithOne;
+ case ComparisonSetBase::Suboptimal: // something was changed
+ should_regenerate = true;
+ break;
+ }
+ }
+ if(should_regenerate)
+ {
+ #ifdef DEBUG_SUBSTITUTIONS
+ std::cout << "Before ConstantFolding_LogicCommon: "; DumpTree(tree);
+ std::cout << "\n";
+ #endif
+
+ if(is_logical)
+ {
+ tree.DelParams(); // delete all params
+ }
+ else
+ {
+ // Delete only logical params
+ for(size_t a=tree.GetParamCount(); a-- > 0; )
+ {
+ const CodeTree<Value_t>& atree = tree.GetParam(a);
+ if(IsLogicalValue(atree))
+ tree.DelParam(a);
+ }
+ }
+
+ for(size_t a=0; a<comp.plain_set.size(); ++a)
+ {
+ if(comp.plain_set[a].negated)
+ {
+ CodeTree<Value_t> r;
+ r.SetOpcode(cNot);
+ r.AddParamMove(comp.plain_set[a].value);
+ r.Rehash();
+ tree.AddParamMove(r);
+ }
+ else if(!is_logical)
+ {
+ CodeTree<Value_t> r;
+ r.SetOpcode(cNotNot);
+ r.AddParamMove(comp.plain_set[a].value);
+ r.Rehash();
+ tree.AddParamMove(r);
+ }
+ else
+ tree.AddParamMove(comp.plain_set[a].value);
+ }
+ for(size_t a=0; a<comp.relationships.size(); ++a)
+ {
+ CodeTree<Value_t> r;
+ r.SetOpcode(cNop); // dummy
+ switch(comp.relationships[a].relationship)
+ {
+ case ComparisonSetBase::Lt_Mask: r.SetOpcode( cLess ); break;
+ case ComparisonSetBase::Eq_Mask: r.SetOpcode( cEqual ); break;
+ case ComparisonSetBase::Gt_Mask: r.SetOpcode( cGreater ); break;
+ case ComparisonSetBase::Le_Mask: r.SetOpcode( cLessOrEq ); break;
+ case ComparisonSetBase::Ne_Mask: r.SetOpcode( cNEqual ); break;
+ case ComparisonSetBase::Ge_Mask: r.SetOpcode( cGreaterOrEq ); break;
+ }
+ r.AddParamMove(comp.relationships[a].a);
+ r.AddParamMove(comp.relationships[a].b);
+ r.Rehash();
+ tree.AddParamMove(r);
+ }
+ if(comp.const_offset != 0)
+ tree.AddParam( CodeTreeImmed( Value_t(comp.const_offset) ) );
+ #ifdef DEBUG_SUBSTITUTIONS
+ std::cout << "After ConstantFolding_LogicCommon: "; DumpTree(tree);
+ std::cout << "\n";
+ #endif
+ return true;
+ }
+ /*
+ Note: One thing this does not yet do, is to detect chains
+ such as x=y & y=z & x=z, which could be optimized
+ to x=y & x=z.
+ */
+ return false;
+ }
+
+ /* ConstantFolding_AndLogic:
+ * (x > y) & (x >= y) --> (x > y)
+ * (x <= y) & (x >= y) --> (x = y)
+ * (x <= y) & (x > y) --> 0
+ * !x & !!x --> 0
+ * etc.
+ */
+ template<typename Value_t>
+ bool ConstantFolding_AndLogic(CodeTree<Value_t>& tree)
+ {
+ assert(tree.GetOpcode() == cAnd || tree.GetOpcode() == cAbsAnd);
+ return ConstantFolding_LogicCommon(tree, ComparisonSetBase::cond_and, true );
+ }
+
+ /* ConstantFolding_OrLogic:
+ * (x > y) | (x >= y) --> (x >= y)
+ * (x <= y) | (x >= y) --> 1
+ * (x <= y) | (x > y) --> 1
+ * !x | !!x --> 1
+ * etc.
+ */
+ template<typename Value_t>
+ bool ConstantFolding_OrLogic(CodeTree<Value_t>& tree)
+ {
+ assert(tree.GetOpcode() == cOr || tree.GetOpcode() == cAbsOr);
+ return ConstantFolding_LogicCommon(tree, ComparisonSetBase::cond_or, true );
+ }
+
+ /* ConstantFolding_AddLogic:
+ * (x <= y) + (x >= y) --> (x = y) + 1
+ * !x + !!x --> 1
+ * etc.
+ */
+ template<typename Value_t>
+ bool ConstantFolding_AddLogicItems(CodeTree<Value_t>& tree)
+ {
+ assert(tree.GetOpcode() == cAdd);
+ return ConstantFolding_LogicCommon(tree, ComparisonSetBase::cond_add, false );
+ }
+
+ /* ConstantFolding_MulLogic:
+ * (x <= y) * (x >= y) --> (x = y)
+ * (x > y) * (x >= y) --> (x > y)
+ * !x * !!x --> 0
+ * etc.
+ */
+ template<typename Value_t>
+ bool ConstantFolding_MulLogicItems(CodeTree<Value_t>& tree)
+ {
+ assert(tree.GetOpcode() == cMul);
+ return ConstantFolding_LogicCommon(tree, ComparisonSetBase::cond_mul, false );
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-04 03:04:37 +0000