Simplicissimus simplification rules are implemented as class templates that, given an expression template, determine if the rule is safe to apply and what the result of an application of the rule is. Simplification rules are standalone classes that may easily be inserted into any simplification stage.
It is important to note that a simplifier is only as useful as the simplification (rewrite) rules it contains. It is also only correct if each individual rule is written to preserve the semantics of any expression template it may be applied to.
Rule Concept Any class that models the Rule concept may be used as a simplification rule. Rules customarily have the postfix ``Simp'' to signify that they are simplification rules. The requirements of a rule are as follows:
Validator parameterized by an expression template. This member class has a single constant value (either an enum or a static const member variable) named valid, which evaluates true if this rule can safely applied to the given expression template.
Result parameterized by an expression template. This member class has a single typedef, result, which contains the result of applying this simplification rule to the given expression template. The Result class will never be instantiated with an expression template where the corresponding Validator's valid value evaluates false.
typedef, rule_class, that
indicates the membership to a certain set of rules. The
StandardRuleClass tag specifies a normal rule (which
models the Rule concept) and the
RuleGroupClass tag specifies a rule group.
IdentitySimp Rule The IdentitySimp class shown below models the Rule concept and performs the trivial X --> X simplification. Since this simplification is always applicable, the valid member of the Validator member template is always true. The result member of the Result member template is equivalent to the expression template it is given.
struct IdentitySimp {
typedef StandardRuleClass rule_class;
template<typename ExprT>
struct Validator { static const bool valid = true; };
template<typename ExprT>
struct Result { typedef ExprT result; };
};
LeftQuasiIdentitySimp Rule The LeftQuasiIdentitySimp rule illustrated below is more complex (and more realistic) than the previously described IdentitySimp rule. A left quasi-identity simplification (such as 0+x --> x) requires that 0 be the left quasi-identity of the + operation. This additional constraint is validated by performing the algebraic concept check GetLeftQuasiIdentity and comparing the left quasi-identity value (if any exists) with the left-hand side of the binary operation. If they match, this rule may be safe to apply.
However, we must also consider the effect of removing this operation entirely. For instance, when simplifying 0+x --> x, we will no longer perform the + operation. Therefore, we must ensure that + has no side effects by checking the BinaryOpTraits structure's has_side_effects. Then, we know it is safe to apply the rule.
The Result member template can safely return the right-hand operand as the result of this simplification (because Result will not be instantiated if valid evaluated false).
struct LeftQuasiIdentitySimp
{
public:
typedef StandardRuleClass rule_class;
template<typename ExprT>
struct Validator { static const bool valid = false; };
template<typename Op, typename Identity, typename RHS>
struct Validator< Expr< BinaryExpr<Op, Identity, RHS> > >
{
private:
typedef typename Expr<
BinaryExpr<Op, Identity, RHS>
>::types
ExprTypes;
typedef typename GetLeftQuasiIdentity<ExprTypes>::id
RealId;
static const bool has_side_effects =
TO_BOOL<
typename BinaryOpTraits<
Op,
typename Identity::result_type,
typename RHS::result_type
>::has_side_effects
>::RET;
public:
static const bool valid =
EQUAL<Identity, RealId>::RET && !has_side_effects;
};
template<typename ExprT> struct Result;
template<typename Op, typename Identity, typename RHS>
struct Result< Expr< BinaryExpr<Op, Identity, RHS> > >
{
typedef RHS result;
};
}
Rule Group Concept Rule groups allow several simplification rules (each of which
models the Rule concept) to be joined together and
accessed via one rule group. The rule group may choose, based on an
expression template to be simplified, which - if any - rules may be
applied to the expression template. For instance, if a group of rules
only operates on binary expressions, then none of the rules will be
applied to a unary expression template.
The rule group concept is characterized by the following:
rule_class which will
be equal to RuleGroupClass to designate this as a rule
class.
MightApplyTo which is parameterized by an expression
template and contains a single member type, rule_iter,
which points to the first rule in a list of rules that should be
applied to the given expression template. If no rules should be
applied, rule_iter should be equal to
FinalRuleIter. Rule iterators are described in the
following section.
Rule iterators are classes containing the following two member types:
rule type is a rule or rule group (i.e., a
class that models the Rule or Rule Group
concept).
next type is a rule iterator representing the
next rule in the sequence. The next type will equal
FinalRuleIter if this is the last rule in the sequence.
BinaryRuleGroup Rule Group The following BinaryRuleGroup class is a rule group
which will only apply its rules (which start at the rule iterator
BinaryRulesIter) if the expression template being
simplified is a binary expression. It is assumed that all rules in the
sequence starting at BinaryRulesIter operate on binary
expressions.
struct BinaryRuleGroup
{
typedef RuleGroupClass rule_class;
template<typename ExprT>
struct MightApplyTo
{
typedef FinalRuleIter rule_iter;
};
template<typename BinOp, typename X, typename Y>
struct MightApplyTo< Expr< BinaryExpr<BinOp, X, Y> > >
{
typedef BinaryRulesIter rule_iter;
};
};
A rule (or rule group) must be added into a specific simplification stage for it to have a chance at being applied by the simplifier. The three standard simplification stages are:
[presimp] Presimplification is generally concerned with the conversion from specialty forms to a more general, often algebraic form. A common example of a presimplification rule is to split a-b into a + (-b) (this avoids adding the rules a + (-a) --> 0 and a - a --> 0 separately).
[simp] Simplification is the primary simplification stage, where most of the reductions are performed. Generally, specialized functions or platform-specific optimizations won't be performed at this stage. For example, a left quasi-identity simplification would be applied at this stage.
[postsimp]. Postsimplification generally consists of simplifications where algebraic forms are reverted back to specialized functions which will execute more quickly. The rule a + (-b) --> a - b would belong in this stage of simplification.
A rule MyNewRule may be added into a simplification stage by defining the preprocessor macro NEW_RULE to MyNewRule and then including the add_[stage]_rule.h header file, where [stage] is one of the simplification stage abbreviations (presimp, simp or postsimp, respectively). The following code illustrates the addition of the LeftQuasiIdentitySimp rule into the primary simplification stage (simp).
#define NEW_RULE LeftQuasiIdentitySimp #include <simplifier/add_simp_rule.h> #undef NEW_RULE