style
diff --git a/src/support/permutations.h b/src/support/permutations.h
index 4e6cc18..601057b 100644
--- a/src/support/permutations.h
+++ b/src/support/permutations.h
@@ -55,10 +55,14 @@
std::vector<std::vector<Index>> ret;
std::vector<Index> curr;
curr.resize(size);
- for (auto& x : curr) x = 0;
+ for (auto& x : curr) {
+ x = 0;
+ }
while (1) {
std::set<Index> set;
- for (auto x : curr) set.insert(x);
+ for (auto x : curr) {
+ set.insert(x);
+ }
if (set.size() == size) {
ret.push_back(curr); // this is indeed a permutation
}
@@ -66,9 +70,13 @@
Index toBump = size - 1;
while (1) {
curr[toBump]++;
- if (curr[toBump] < size) break;
+ if (curr[toBump] < size) {
+ break;
+ }
// an overflow
- if (toBump == 0) return ret; // all done
+ if (toBump == 0) {
+ return ret; // all done
+ }
curr[toBump] = 0;
toBump--;
}
diff --git a/src/tools/wasm-analyze.cpp b/src/tools/wasm-analyze.cpp
index db7f0bd..3278218 100644
--- a/src/tools/wasm-analyze.cpp
+++ b/src/tools/wasm-analyze.cpp
@@ -17,21 +17,22 @@
//
// Expression analyzer utility
//
-// Superoptimization is based on Bansal, Sorav; Aiken, Alex (21–25 October 2006): "Automatic Generation of Peephole Superoptimizers".
+// Superoptimization is based on Bansal, Sorav; Aiken, Alex (21–25 October
+// 2006): "Automatic Generation of Peephole Superoptimizers".
//
+#include "ast/cost.h"
+#include "ast_utils.h"
#include "support/colors.h"
#include "support/command-line.h"
#include "support/file.h"
#include "support/hash.h"
#include "support/permutation.h"
-#include "wasm-s-parser.h"
-#include "wasm-traversal.h"
-#include "wasm-printing.h"
#include "wasm-interpreter.h"
#include "wasm-io.h"
-#include "ast_utils.h"
-#include "ast/cost.h"
+#include "wasm-printing.h"
+#include "wasm-s-parser.h"
+#include "wasm-traversal.h"
using namespace cashew;
using namespace wasm;
@@ -42,13 +43,37 @@
// special values to make sure to consider in execution hashing
#define NUM_LIMITS 6
-static int32_t LIMIT_I32S[NUM_LIMITS] = { std::numeric_limits<int32_t>::min(), std::numeric_limits<int32_t>::max(), int32_t(std::numeric_limits<uint32_t>::min()), int32_t(std::numeric_limits<uint32_t>::max()), 0xfffff, -0xfffff };
-static int64_t LIMIT_I64S[NUM_LIMITS] = { std::numeric_limits<int64_t>::min(), std::numeric_limits<int64_t>::max(), int64_t(std::numeric_limits<uint64_t>::min()), int64_t(std::numeric_limits<uint64_t>::max()), 0xfffffLL, -0xfffffLL };
-static float LIMIT_F32S[NUM_LIMITS] = { std::numeric_limits<float>::min(), std::numeric_limits<float>::max(), std::numeric_limits<float>::quiet_NaN(), std::numeric_limits<float>::infinity(), float(0xfffff), float(-0xfffff) };
-static double LIMIT_F64S[NUM_LIMITS] = { std::numeric_limits<double>::min(), std::numeric_limits<double>::max(), std::numeric_limits<double>::quiet_NaN(), std::numeric_limits<double>::infinity(), double(0xfffff), double(-0xfffff) };
+static int32_t LIMIT_I32S[NUM_LIMITS] = {
+ std::numeric_limits<int32_t>::min(),
+ std::numeric_limits<int32_t>::max(),
+ int32_t(std::numeric_limits<uint32_t>::min()),
+ int32_t(std::numeric_limits<uint32_t>::max()),
+ 0xfffff,
+ -0xfffff};
+static int64_t LIMIT_I64S[NUM_LIMITS] = {
+ std::numeric_limits<int64_t>::min(),
+ std::numeric_limits<int64_t>::max(),
+ int64_t(std::numeric_limits<uint64_t>::min()),
+ int64_t(std::numeric_limits<uint64_t>::max()),
+ 0xfffffLL,
+ -0xfffffLL};
+static float LIMIT_F32S[NUM_LIMITS] = {std::numeric_limits<float>::min(),
+ std::numeric_limits<float>::max(),
+ std::numeric_limits<float>::quiet_NaN(),
+ std::numeric_limits<float>::infinity(),
+ float(0xfffff),
+ float(-0xfffff)};
+static double LIMIT_F64S[NUM_LIMITS] = {
+ std::numeric_limits<double>::min(),
+ std::numeric_limits<double>::max(),
+ std::numeric_limits<double>::quiet_NaN(),
+ std::numeric_limits<double>::infinity(),
+ double(0xfffff),
+ double(-0xfffff)};
#define MAX_SMALL 260
-#define NUM_SMALLS (MAX_SMALL + MAX_SMALL + 1) /* negatives, positives, and zero */
+#define NUM_SMALLS \
+ (MAX_SMALL + MAX_SMALL + 1) /* negatives, positives, and zero */
#define NUM_SPECIALS (NUM_LIMITS + NUM_SMALLS)
@@ -67,27 +92,30 @@
}
}
- HashedExpression(const HashedExpression& other) : expr(other.expr), hash(other.hash) {}
+ HashedExpression(const HashedExpression& other)
+ : expr(other.expr), hash(other.hash) {}
};
struct ExpressionHasher {
- size_t operator()(const HashedExpression value) const {
- return value.hash;
- }
+ size_t operator()(const HashedExpression value) const { return value.hash; }
};
struct ExpressionComparer {
bool operator()(const HashedExpression a, const HashedExpression b) const {
- if (a.hash != b.hash) return false;
+ if (a.hash != b.hash)
+ return false;
return ExpressionAnalyzer::equal(a.expr, b.expr);
}
};
// expression -> a count
-class ExpressionIntMap : public std::unordered_map<HashedExpression, size_t, ExpressionHasher, ExpressionComparer> {};
+class ExpressionIntMap : public std::unordered_map<HashedExpression,
+ size_t,
+ ExpressionHasher,
+ ExpressionComparer> {};
// global expression state
-Module global; // a module that persists til the end
+Module global; // a module that persists til the end
ExpressionIntMap freqs; // expression -> its frequency
// Normalize an expression, replacing irrelevant bits with
@@ -103,11 +131,13 @@
Normalizer(Module& wasm) : wasm(wasm), builder(wasm) {}
Expression* parentCopy(Expression* curr) {
- return ExpressionManipulator::flexibleCopy(curr, wasm, [&](Expression* curr) { return this->copy(curr); });
+ return ExpressionManipulator::flexibleCopy(
+ curr, wasm, [&](Expression* curr) { return this->copy(curr); });
}
Expression* copy(Expression* curr) {
- // For now, we only handle math-type expressions: having a return value and no side effects
+ // For now, we only handle math-type expressions: having a return value
+ // and no side effects
// TODO: do more stuff, modeling side effects etc.
if (!isConcreteWasmType(curr->type)) {
return builder.makeUnreachable();
@@ -132,23 +162,29 @@
// consider the general case of an arbitrary expression here
return builder.makeGetLocal(nextLocal++, curr->type);
}
- if (curr->is<Host>() || curr->is<Call>() || curr->is<CallImport>() || curr->is<CallIndirect>() || curr->is<GetGlobal>() || curr->is<Load>() || curr->is<Return>() || curr->is<Break>() || curr->is<Switch>()) {
+ if (curr->is<Host>() || curr->is<Call>() || curr->is<CallImport>() ||
+ curr->is<CallIndirect>() || curr->is<GetGlobal>() ||
+ curr->is<Load>() || curr->is<Return>() || curr->is<Break>() ||
+ curr->is<Switch>()) {
return builder.makeUnreachable();
}
return nullptr; // allow the default copy to proceed
}
} normalizer(wasm);
- auto* ret = ExpressionManipulator::flexibleCopy(expr, wasm, [&](Expression* curr) { return normalizer.copy(curr); });
+ auto* ret = ExpressionManipulator::flexibleCopy(
+ expr, wasm, [&](Expression* curr) { return normalizer.copy(curr); });
- if (!isConcreteWasmType(ret->type) || normalizer.nextLocal >= MAX_LOCAL || Measurer::measure(ret) > MAX_EXPRESSION_SIZE) {
+ if (!isConcreteWasmType(ret->type) || normalizer.nextLocal >= MAX_LOCAL ||
+ Measurer::measure(ret) > MAX_EXPRESSION_SIZE) {
return nullptr;
}
return ret;
}
// Scan an expression for local types. Assumes it has MAX_LOCAL locals at most
-struct ScanLocals : public WalkerPass<PostWalker<ScanLocals, Visitor<ScanLocals>>> {
+struct ScanLocals
+ : public WalkerPass<PostWalker<ScanLocals, Visitor<ScanLocals>>> {
WasmType localTypes[MAX_LOCAL];
ScanLocals(Expression* expr) {
@@ -165,10 +201,12 @@
};
// Remap locals
-struct RemapLocals : public WalkerPass<PostWalker<RemapLocals, Visitor<RemapLocals>>> {
+struct RemapLocals
+ : public WalkerPass<PostWalker<RemapLocals, Visitor<RemapLocals>>> {
std::vector<Index>& mapping;
- RemapLocals(Expression* expr, std::vector<Index>& mapping) : mapping(mapping) {
+ RemapLocals(Expression* expr, std::vector<Index>& mapping)
+ : mapping(mapping) {
walk(expr);
}
@@ -186,17 +224,19 @@
struct ScanSettings {
Index* totalExpressions;
bool adviseOnly;
- ScanSettings(Index* totalExpressions, bool adviseOnly) : totalExpressions(totalExpressions), adviseOnly(adviseOnly) {}
+ ScanSettings(Index* totalExpressions, bool adviseOnly)
+ : totalExpressions(totalExpressions), adviseOnly(adviseOnly) {}
};
// Scan a module for expressions
-struct Scan : public WalkerPass<PostWalker<Scan, UnifiedExpressionVisitor<Scan>>> {
+struct Scan
+ : public WalkerPass<PostWalker<Scan, UnifiedExpressionVisitor<Scan>>> {
ScanSettings settings;
Scan(ScanSettings settings) : settings(settings) {}
void doWalkFunction(Function* func) {
- //std::cout << " [" << func->name << ']' << '\n';
+ // std::cout << " [" << func->name << ']' << '\n';
walk(func->body);
}
@@ -205,7 +245,8 @@
// which is ephemeral TODO: avoid keeping them alive til the end of
// module processing to reduce peak mem usage?
auto* normalized = normalize(curr, *getModule());
- if (!normalized) return;
+ if (!normalized)
+ return;
if (!settings.adviseOnly) {
(*settings.totalExpressions)++; // this is relevant, count it
}
@@ -216,16 +257,19 @@
iter->second++; // just increment it
}
} else {
- // create a persistent copy in the global module TODO: avoid the rehash here
+ // create a persistent copy in the global module TODO: avoid the rehash
+ // here
auto* copy = ExpressionManipulator::copy(normalized, global);
freqs[HashedExpression(copy)] = settings.adviseOnly ? 0 : 1;
#if 1
- // add the permutations on the locals as well, with freq 0, as we just want to use them as optimization targets,
- // we don't need to optimize them, we optimize the canonical first form.
+ // add the permutations on the locals as well, with freq 0, as we just
+ // want to use them as optimization targets, we don't need to optimize
+ // them, we optimize the canonical first form.
ScanLocals scanner(copy);
if (scanner.localTypes[1] != none) {
struct PermutationsLister {
- std::vector<std::vector<std::vector<Index>>> list; // index => list of permutations of that size
+ std::vector<std::vector<std::vector<Index>>>
+ list; // index => list of permutations of that size
PermutationsLister() {
list.resize(MAX_LOCAL + 1);
for (size_t i = 1; i < MAX_LOCAL + 1; i++) {
@@ -258,24 +302,31 @@
// Generate local values deterministically, using a seed
class LocalGenerator {
Index seed;
+
public:
LocalGenerator(Index seed) : seed(seed) {}
Literal get(Index index, WasmType type) {
// use low indexes to ensure we get representation of a few special values
// TODO: get each of the MAX_LOCALS to all of its NUM_SPECIALS values
- int64_t special = seed; // start with 0-NS having them all taking the same value
+ int64_t special =
+ seed; // start with 0-NS having them all taking the same value
if (special >= NUM_SPECIALS) { // then give each a range for itself
special = int64_t(seed) - int64_t(NUM_SPECIALS * (index + 1));
}
if (special >= 0 && special < NUM_SPECIALS) {
if (special < NUM_LIMITS) {
switch (type) {
- case i32: return Literal(LIMIT_I32S[special]);
- case i64: return Literal(LIMIT_I64S[special]);
- case f32: return Literal(LIMIT_F32S[special]);
- case f64: return Literal(LIMIT_F64S[special]);
- default: WASM_UNREACHABLE();
+ case i32:
+ return Literal(LIMIT_I32S[special]);
+ case i64:
+ return Literal(LIMIT_I64S[special]);
+ case f32:
+ return Literal(LIMIT_F32S[special]);
+ case f64:
+ return Literal(LIMIT_F64S[special]);
+ default:
+ WASM_UNREACHABLE();
}
} else {
special -= NUM_LIMITS;
@@ -283,11 +334,16 @@
special -= MAX_SMALL;
assert(special >= -MAX_SMALL && special <= MAX_SMALL);
switch (type) {
- case i32: return Literal(int32_t(special));
- case i64: return Literal(int64_t(special));
- case f32: return Literal(float(special));
- case f64: return Literal(double(special));
- default: WASM_UNREACHABLE();
+ case i32:
+ return Literal(int32_t(special));
+ case i64:
+ return Literal(int64_t(special));
+ case f32:
+ return Literal(float(special));
+ case f64:
+ return Literal(double(special));
+ default:
+ WASM_UNREACHABLE();
}
}
}
@@ -297,16 +353,20 @@
case i32:
case f32: {
auto ret = Literal(rehash(base, Index(type)));
- if (type == f32) ret = ret.castToF32();
+ if (type == f32)
+ ret = ret.castToF32();
return ret;
}
case i64:
case f64: {
- auto ret = Literal(rehash(base, Index(type)) | (int64_t(rehash(base, Index(type + 1000))) << 32));
- if (type == f64) ret = ret.castToF64();
+ auto ret = Literal(rehash(base, Index(type)) |
+ (int64_t(rehash(base, Index(type + 1000))) << 32));
+ if (type == f64)
+ ret = ret.castToF64();
return ret;
}
- default: WASM_UNREACHABLE();
+ default:
+ WASM_UNREACHABLE();
}
}
};
@@ -316,12 +376,14 @@
// Execute the expression over a set of local values
class Runner : public ExpressionRunner<Runner> {
LocalGenerator& localGenerator;
+
public:
Runner(LocalGenerator& localGenerator) : localGenerator(localGenerator) {}
Flow visitLoop(Loop* curr) {
// loops might be infinite, so must be careful
- // but we can't tell if non-infinite, since we don't have state, so loops are just impossible to optimize for now
+ // but we can't tell if non-infinite, since we don't have state, so loops
+ // are just impossible to optimize for now
trap("loop");
WASM_UNREACHABLE();
}
@@ -357,24 +419,26 @@
abort(); // we should not see this
}
- void trap(const char* why) override {
- throw TrapException();
- }
+ void trap(const char* why) override { throw TrapException(); }
};
// Calculate a hash value based on executing an expression
struct ExecutionHasher {
- std::unordered_map<size_t, std::vector<Expression*>> hashClasses; // hash value => list of expressions that have it, so they may be equal
+ std::unordered_map<size_t, std::vector<Expression*>>
+ hashClasses; // hash value => list of expressions that have it, so they may
+ // be equal
void note(Expression* expr) {
size_t hash;
try {
hash = doHash(expr);
} catch (TrapException& e) {
- // we don't bother trying to handle things that trap TODO: maybe abort the whole thing, move try out, for speed?
+ // we don't bother trying to handle things that trap TODO: maybe abort the
+ // whole thing, move try out, for speed?
return;
}
- hashClasses[hash].push_back(expr); // we depend on expr being unique, so the classes are mathematical sets
+ hashClasses[hash].push_back(expr); // we depend on expr being unique, so the
+ // classes are mathematical sets
}
size_t doHash(Expression* expr) {
@@ -392,15 +456,30 @@
hash = rehash(hash, 4);
hash = rehash(hash, flow.value.type);
switch (flow.value.type) {
- case f32: flow.value = flow.value.castToI32(); break;
- case f64: flow.value = flow.value.castToI64(); break;
- default: {}
+ case f32:
+ flow.value = flow.value.castToI32();
+ break;
+ case f64:
+ flow.value = flow.value.castToI64();
+ break;
+ default: {
+ }
}
switch (flow.value.type) {
- case none: hash = rehash(hash, 5); hash = rehash(hash, 6); break;
- case i32: hash = rehash(hash, flow.value.geti32()); hash = rehash(hash, 7); break;
- case i64: hash = rehash(hash, flow.value.geti64()); hash = rehash(hash, flow.value.geti64() >> 32); break;
- default: WASM_UNREACHABLE();
+ case none:
+ hash = rehash(hash, 5);
+ hash = rehash(hash, 6);
+ break;
+ case i32:
+ hash = rehash(hash, flow.value.geti32());
+ hash = rehash(hash, 7);
+ break;
+ case i64:
+ hash = rehash(hash, flow.value.geti64());
+ hash = rehash(hash, flow.value.geti64() >> 32);
+ break;
+ default:
+ WASM_UNREACHABLE();
}
}
}
@@ -414,9 +493,12 @@
}
// can our optimizer do better on a than b?
-static bool alreadyOptimizable(Expression* input, WasmType localTypes[MAX_LOCAL], Expression* output) {
+static bool alreadyOptimizable(Expression* input,
+ WasmType localTypes[MAX_LOCAL],
+ Expression* output) {
Module temp;
- // make a single function that receives the expressions locals and returns its output
+ // make a single function that receives the expressions locals and returns its
+ // output
auto* func = new Function();
func->name = Name("temp");
func->result = input->type;
@@ -442,7 +524,8 @@
// Given two expressions that hashing suggests might be the same, try
// harder directly on the two to prove or disprove equivalence
bool looksValid(Expression* a, Expression* b) {
- if (a->type != b->type) return false; // hash collision, these are not even the same type
+ if (a->type != b->type)
+ return false; // hash collision, these are not even the same type
// local types must be identical, otherwise the rule isn't even valid to apply
ScanLocals aScanner(a), bScanner(b);
for (Index i = 0; i < MAX_LOCAL; i++) {
@@ -458,12 +541,14 @@
Flow aFlow = Runner(localGenerator).visit(a);
Flow bFlow = Runner(localGenerator).visit(b);
// TODO: breaking
- if (aFlow.value != bFlow.value) return false;
+ if (aFlow.value != bFlow.value)
+ return false;
}
// let's see if this possible optimization is already something our
// optimizer can do: if we optimize the input, do we get something
// as good or better than the output?
- if (alreadyOptimizable(a, aScanner.localTypes, b)) return false;
+ if (alreadyOptimizable(a, aScanner.localTypes, b))
+ return false;
// we see no reason these two should not be joined together in holy optimony
return true;
}
@@ -487,15 +572,21 @@
}
} generalizer(wasm);
- return ExpressionManipulator::flexibleCopy(expr, wasm, [&](Expression* curr) { return generalizer.copy(curr); });
+ return ExpressionManipulator::flexibleCopy(
+ expr, wasm, [&](Expression* curr) { return generalizer.copy(curr); });
}
-int main(int argc, const char *argv[]) {
+int main(int argc, const char* argv[]) {
// receive arguments
std::vector<std::string> filenames;
- Options options("wasm-analyze", "Analyze a set of wasm modules. Provide a set of input files, optionally split by 'advice:' (in which case files afterwards are just advice, used to find optimization outputs but not inputs we focus on optimizing)");
- options.add_positional("INFILES", Options::Arguments::N,
- [&](Options *o, const std::string &argument) {
+ Options options(
+ "wasm-analyze",
+ "Analyze a set of wasm modules. Provide a set of input files, optionally "
+ "split by 'advice:' (in which case files afterwards are just advice, used "
+ "to find optimization outputs but not inputs we focus on optimizing)");
+ options.add_positional("INFILES",
+ Options::Arguments::N,
+ [&](Options* o, const std::string& argument) {
filenames.push_back(argument);
});
options.parse(argc, argv);
@@ -550,8 +641,8 @@
}
#endif
- // perform execution hashing, looking for expressions that are functionally equivalent,
- // so one can be optimized to the other
+ // perform execution hashing, looking for expressions that are functionally
+ // equivalent, so one can be optimized to the other
std::cerr << "[hashing executions]\n";
@@ -574,7 +665,8 @@
}
std::cout << " num relevant expressions: " << total << '\n';
}
- std::cout << " num execution classes: " << executionHasher.hashClasses.size() << '\n';
+ std::cout << " num execution classes: " << executionHasher.hashClasses.size()
+ << '\n';
{
size_t max = 0;
for (auto& pair : executionHasher.hashClasses) {
@@ -585,15 +677,17 @@
// Detailed output
{
- // a rule is a connection between one pattern and another, which we think may be equivalent to it,
- // and which may provide a measured benefit
- // TODO: test rules on more random inputs, trying to prove they are not equivalent?
+ // a rule is a connection between one pattern and another, which we think
+ // may be equivalent to it, and which may provide a measured benefit
+ // TODO: test rules on more random inputs, trying to prove they are not
+ // equivalent?
struct Rule {
Expression* from;
Expression* to;
size_t benefit;
- Rule(Expression* from, Expression* to, size_t benefit) : from(from), to(to), benefit(benefit) {}
+ Rule(Expression* from, Expression* to, size_t benefit)
+ : from(from), to(to), benefit(benefit) {}
};
std::vector<Rule> rules;
@@ -603,23 +697,32 @@
for (auto& pair : executionHasher.hashClasses) {
auto& clazz = pair.second;
Index size = clazz.size();
- if (size < 2) continue;
+ if (size < 2)
+ continue;
// consider all pairs, since some may be spurious hash collisions
for (Index i = 0; i < size; i++) {
auto* iExpr = clazz[i];
auto iFreq = freqs[iExpr];
- if (iFreq == 0) continue; // no frequency means no benefit to optimize it; this expression is just a target of optimization, not an origin
+ if (iFreq == 0)
+ continue; // no frequency means no benefit to optimize it; this
+ // expression is just a target of optimization, not an
+ // origin
Index iSize = calcWeight(iExpr);
Expression* best = nullptr;
Index bestSize = -1;
for (Index j = 0; j < size; j++) {
- if (i == j) continue;
+ if (i == j)
+ continue;
auto* jExpr = clazz[j];
Index jSize = calcWeight(jExpr);
// we are looking for a rule where i => j, so we need j to be smaller
- if (iSize <= jSize) continue; // TODO: for equality, look not just at size, but cost etc.
- // a likely candidate, if direct attempts to prove they differ fail, this is worth reporting to the user
- if (best && jSize >= bestSize) continue; // we can't do better
+ if (iSize <= jSize)
+ continue; // TODO: for equality, look not just at size, but cost
+ // etc.
+ // a likely candidate, if direct attempts to prove they differ fail,
+ // this is worth reporting to the user
+ if (best && jSize >= bestSize)
+ continue; // we can't do better
if (looksValid(iExpr, jExpr)) {
best = jExpr;
bestSize = jSize;
@@ -631,15 +734,16 @@
}
}
- // Many rules are part of a more general pattern, for example x + 1 + 1 === x + 2 is
- // closely related to x + 1 + 2 === x + 3. The generalized rule is what the human would
- // write in the optimizer, so to assess the benefit of rules, we must generalize in
- // our output.
+ // Many rules are part of a more general pattern, for example x + 1 + 1 ===
+ // x + 2 is closely related to x + 1 + 2 === x + 3. The generalized rule is
+ // what the human would write in the optimizer, so to assess the benefit of
+ // rules, we must generalize in our output.
std::cerr << "[generalizing]\n";
struct GeneralizedRule : public Rule {
- std::vector<Rule*> rules; // the specific rules underlying this generalization
+ std::vector<Rule*>
+ rules; // the specific rules underlying this generalization
GeneralizedRule(Expression* from, Rule* rule) : Rule(from, nullptr, 0) {
addRule(rule);
@@ -652,13 +756,20 @@
};
// hashed from expression => the generalized rules for that expression
- std::unordered_map<HashedExpression, GeneralizedRule, ExpressionHasher, ExpressionComparer> generalizedRules;
+ std::unordered_map<HashedExpression,
+ GeneralizedRule,
+ ExpressionHasher,
+ ExpressionComparer>
+ generalizedRules;
for (auto& rule : rules) {
- auto generalizedFrom = HashedExpression(generalize(rule.from, global)); // TODO: save memory, don't use global unless needed?
+ auto generalizedFrom = HashedExpression(generalize(
+ rule.from,
+ global)); // TODO: save memory, don't use global unless needed?
auto iter = generalizedRules.find(generalizedFrom);
if (iter == generalizedRules.end()) {
- generalizedRules.emplace(generalizedFrom, GeneralizedRule(generalizedFrom.expr, &rule));
+ generalizedRules.emplace(generalizedFrom,
+ GeneralizedRule(generalizedFrom.expr, &rule));
} else {
iter->second.addRule(&rule);
}
@@ -676,14 +787,19 @@
auto ruleSorter = [](const Rule* a, const Rule* b) {
// primary sorting criteria is the size benefit
auto diff = int64_t(a->benefit) - int64_t(b->benefit);
- if (diff > 0) return true;
- if (diff < 0) return false;
+ if (diff > 0)
+ return true;
+ if (diff < 0)
+ return false;
return size_t(a->from) < size_t(b->from);
};
- std::sort(sortedGeneralizedRules.begin(), sortedGeneralizedRules.end(), [&ruleSorter](const GeneralizedRule* a, const GeneralizedRule* b) {
- return ruleSorter(a, b);
- });
+ std::sort(
+ sortedGeneralizedRules.begin(),
+ sortedGeneralizedRules.end(),
+ [&ruleSorter](const GeneralizedRule* a, const GeneralizedRule* b) {
+ return ruleSorter(a, b);
+ });
std::cout << "sorted possible optimization rules:\n";
@@ -691,15 +807,23 @@
size_t i = 0;
for (auto* item : sortedGeneralizedRules) {
- std::cout << "\n[generalized rule " << (i++) << ": benefit: " << item->benefit << ", (" << (100*double(item->benefit)/totalWeight) << "%)], input pattern:\n" << item->from << '\n';
+ std::cout << "\n[generalized rule " << (i++)
+ << ": benefit: " << item->benefit << ", ("
+ << (100 * double(item->benefit) / totalWeight)
+ << "%)], input pattern:\n"
+ << item->from << '\n';
// show the specific rules underlying the generalized one
std::sort(item->rules.begin(), item->rules.end(), ruleSorter);
for (auto* rule : item->rules) {
- std::cout << "\n[child specific rule benefit: " << rule->benefit << ", (" << (100*double(rule->benefit)/totalWeight) << "%)], possible rule:\n" << rule->from << "\n =->\n" << rule->to << '\n';
+ std::cout << "\n[child specific rule benefit: " << rule->benefit
+ << ", (" << (100 * double(rule->benefit) / totalWeight)
+ << "%)], possible rule:\n"
+ << rule->from << "\n =->\n"
+ << rule->to << '\n';
}
}
}
- // TODO TODO: if all execution hashes of expr are the same, it might be constant (avoids needing to have all constants hashed)
+ // TODO TODO: if all execution hashes of expr are the same, it might be
+ // constant (avoids needing to have all constants hashed)
}
-
