// Copyright © Tavian Barnes <tavianator@tavianator.com>
// SPDX-License-Identifier: 0BSD
/**
* The expression optimizer. Different optimization levels are supported:
*
* -O1: basic logical simplifications, like folding (-true -and -foo) to -foo.
*
* -O2: dead code elimination and data flow analysis. struct df_domain is used
* to record data flow facts that are true at various points of evaluation.
* Specifically, struct df_domain records the state before an expression is
* evaluated (opt->before), and after an expression returns true
* (opt->after_true) or false (opt->after_false). Additionally, opt->impure
* records the possible state before any expression with side effects is
* evaluated.
*
* -O3: expression re-ordering to reduce expected cost. In an expression like
* (-foo -and -bar), if both -foo and -bar are pure (no side effects), they can
* be re-ordered to (-bar -and -foo). This is profitable if the expected cost
* is lower for the re-ordered expression, for example if -foo is very slow or
* -bar is likely to return false.
*
* -O4/-Ofast: aggressive optimizations that may affect correctness in corner
* cases. The main effect is to use impure to determine if any side-effects are
* reachable at all, and skipping the traversal if not.
*/
#include "opt.h"
#include "color.h"
#include "config.h"
#include "ctx.h"
#include "diag.h"
#include "eval.h"
#include "exec.h"
#include "expr.h"
#include "pwcache.h"
#include <errno.h>
#include <limits.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
static char *fake_and_arg = "-a";
static char *fake_or_arg = "-o";
static char *fake_not_arg = "!";
/**
* The data flow domain for predicates.
*/
enum df_pred {
/** The bottom state (unreachable). */
PRED_BOTTOM = 0,
/** The predicate is known to be false. */
PRED_FALSE = 1 << false,
/** The predicate is known to be true. */
PRED_TRUE = 1 << true,
/** The top state (unknown). */
PRED_TOP = PRED_FALSE | PRED_TRUE,
};
/** Make a predicate known. */
static void constrain_pred(enum df_pred *pred, bool value) {
*pred &= 1 << value;
}
/** Compute the join (union) of two predicates. */
static void pred_join(enum df_pred *dest, enum df_pred src) {
*dest