/src/php-src/Zend/Optimizer/ssa_integrity.c

Source
/*
   +----------------------------------------------------------------------+
   | Zend Engine, SSA validation                                          |
   +----------------------------------------------------------------------+
   | Copyright (c) The PHP Group                                          |
   +----------------------------------------------------------------------+
   | This source file is subject to version 3.01 of the PHP license,      |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | https://www.php.net/license/3_01.txt                                 |
   | If you did not receive a copy of the PHP license and are unable to   |
   | obtain it through the world-wide-web, please send a note to          |
   | license@php.net so we can mail you a copy immediately.               |
   +----------------------------------------------------------------------+
   | Authors: Nikita Popov <nikic@php.net>                                |
   +----------------------------------------------------------------------+
*/

#include "Optimizer/zend_optimizer_internal.h"

/* The ssa_verify_integrity() function ensures that that certain invariants of the SSA form and
 * CFG are upheld and prints messages to stderr if this is not the case. */

static inline bool is_in_use_chain(zend_ssa *ssa, int var, int check) {
  int use;
  FOREACH_USE(&ssa->vars[var], use) {
    if (use == check) {
      return true;
    }
  } FOREACH_USE_END();
  return false;
}

static inline bool is_in_phi_use_chain(zend_ssa *ssa, int var, zend_ssa_phi *check) {
  zend_ssa_phi *phi;
  FOREACH_PHI_USE(&ssa->vars[var], phi) {
    if (phi == check) {
      return true;
    }
  } FOREACH_PHI_USE_END();
  return false;
}

static inline bool is_used_by_op(zend_ssa *ssa, int op, int check) {
  zend_ssa_op *ssa_op = &ssa->ops[op];
  return (ssa_op->op1_use == check)
    || (ssa_op->op2_use == check)
    || (ssa_op->result_use == check);
}

static inline bool is_defined_by_op(zend_ssa *ssa, int op, int check) {
  zend_ssa_op *ssa_op = &ssa->ops[op];
  return (ssa_op->op1_def == check)
    || (ssa_op->op2_def == check)
    || (ssa_op->result_def == check);
}

static inline bool is_in_phi_sources(zend_ssa *ssa, zend_ssa_phi *phi, int check) {
  int source;
  FOREACH_PHI_SOURCE(phi, source) {
    if (source == check) {
      return true;
    }
  } FOREACH_PHI_SOURCE_END();
  return false;
}

static inline bool is_in_predecessors(zend_cfg *cfg, zend_basic_block *block, int check) {
  int i, *predecessors = &cfg->predecessors[block->predecessor_offset];
  for (i = 0; i < block->predecessors_count; i++) {
    if (predecessors[i] == check) {
      return true;
    }
  }
  return false;
}

static inline bool is_in_successors(zend_basic_block *block, int check) {
  int s;
  for (s = 0; s < block->successors_count; s++) {
    if (block->successors[s] == check) {
      return true;
    }
  }
  return false;
}

static inline bool is_var_type(uint8_t type) {
  return (type & (IS_CV|IS_VAR|IS_TMP_VAR)) != 0;
}

static inline bool is_defined(const zend_ssa *ssa, const zend_op_array *op_array, int var) {
  const zend_ssa_var *ssa_var = &ssa->vars[var];
  return ssa_var->definition >= 0 || ssa_var->definition_phi || var < op_array->last_var;
}

#define FAIL(...) do { \
  if (status == SUCCESS) { \
    fprintf(stderr, "\nIn function %s::%s (%s):\n", \
      op_array->scope ? ZSTR_VAL(op_array->scope->name) : "", \
      op_array->function_name ? ZSTR_VAL(op_array->function_name) : "{main}", extra); \
  } \
  fprintf(stderr, __VA_ARGS__); \
  status = FAILURE; \
} while (0)

#define VARFMT "%d (%s%s)"
#define VAR(i) \
  (i), (ssa->vars[i].var < op_array->last_var ? "CV $" : "TMP"), \
  (ssa->vars[i].var < op_array->last_var ? ZSTR_VAL(op_array->vars[ssa->vars[i].var]) : "")

#define INSTRFMT "%d (%s)"
#define INSTR(i) \
  (i), (zend_get_opcode_name(op_array->opcodes[i].opcode))

void ssa_verify_integrity(zend_op_array *op_array, zend_ssa *ssa, const char *extra) {
  zend_cfg *cfg = &ssa->cfg;
  zend_ssa_phi *phi;
  int i;
  zend_result status = SUCCESS;

  /* Vars */
  for (i = 0; i < ssa->vars_count; i++) {
    zend_ssa_var *var = &ssa->vars[i];
    int use;
    uint32_t type = ssa->var_info[i].type;

    if (var->definition < 0 && !var->definition_phi && i > op_array->last_var) {
      if (var->use_chain >= 0) {
        FAIL("var " VARFMT " without def has op uses\n", VAR(i));
      }
      if (var->phi_use_chain) {
        FAIL("var " VARFMT " without def has phi uses\n", VAR(i));
      }
    }
    if (var->definition >= 0 && var->definition_phi) {
      FAIL("var " VARFMT " has both def and def_phi\n", VAR(i));
    }
    if (var->definition >= 0) {
      if (!is_defined_by_op(ssa, var->definition, i)) {
        FAIL("var " VARFMT " not defined by op " INSTRFMT "\n",
            VAR(i), INSTR(var->definition));
      }
    }
    if (var->definition_phi) {
      if (var->definition_phi->ssa_var != i) {
        FAIL("var " VARFMT " not defined by given phi\n", VAR(i));
      }
    }

    /* Floyd's cycle detection algorithm, applied for use chain. */
    use = var->use_chain;
    int second_use = use;
    while (use >= 0 && second_use >= 0) {
      use = zend_ssa_next_use(ssa->ops, var - ssa->vars, use);
      second_use = zend_ssa_next_use(ssa->ops, var - ssa->vars, second_use);
      if (second_use < 0) {
        break;
      }
      second_use = zend_ssa_next_use(ssa->ops, var - ssa->vars, second_use);
      if (use == second_use) {
        FAIL("cycle in uses of " VARFMT "\n", VAR(i));
        goto finish;
      }
    }

    FOREACH_USE(var, use) {
      if (!is_used_by_op(ssa, use, i)) {
        fprintf(stderr, "var " VARFMT " not in uses of op %d\n", VAR(i), use);
      }
    } FOREACH_USE_END();

    /* Floyd's cycle detection algorithm, applied for phi nodes. */
    phi = var->phi_use_chain;
    zend_ssa_phi *second_phi = phi;
    while (phi && second_phi) {
      phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, phi);
      second_phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, second_phi);
      if (!second_phi) {
        break;
      }
      second_phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, second_phi);
      if (phi == second_phi) {
        FAIL("cycle in phi uses of " VARFMT "\n", VAR(i));
        goto finish;
      }
    }

    FOREACH_PHI_USE(var, phi) {
      if (!is_in_phi_sources(ssa, phi, i)) {
        FAIL("var " VARFMT " not in phi sources of %d\n", VAR(i), phi->ssa_var);
      }
    } FOREACH_PHI_USE_END();

    if ((type & (MAY_BE_ARRAY_KEY_ANY-MAY_BE_ARRAY_EMPTY)) && !(type & MAY_BE_ARRAY_OF_ANY)) {
      FAIL("var " VARFMT " has array key type but not value type\n", VAR(i));
    }
    if ((type & MAY_BE_ARRAY_OF_ANY) && !(type & (MAY_BE_ARRAY_KEY_ANY-MAY_BE_ARRAY_EMPTY))) {
      FAIL("var " VARFMT " has array value type but not key type\n", VAR(i));
    }
    if ((type & MAY_BE_REF) && ssa->var_info[i].ce) {
      FAIL("var " VARFMT " may be ref but has ce\n", VAR(i));
    }
  }

  /* Instructions */
  FOREACH_INSTR_NUM(i) {
    zend_ssa_op *ssa_op = &ssa->ops[i];
    zend_op *opline = &op_array->opcodes[i];
    if (is_var_type(opline->op1_type)) {
      if (ssa_op->op1_use < 0 && ssa_op->op1_def < 0) {
        FAIL("var op1 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
      }
    } else {
      if (ssa_op->op1_use >= 0 || ssa_op->op1_def >= 0) {
        FAIL("non-var op1 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
      }
    }
    if (is_var_type(opline->op2_type)) {
      if (ssa_op->op2_use < 0 && ssa_op->op2_def < 0) {
        FAIL("var op2 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
      }
    } else {
      if (ssa_op->op2_use >= 0 || ssa_op->op2_def >= 0) {
        FAIL("non-var op2 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
      }
    }
    if (is_var_type(opline->result_type)) {
      if (ssa_op->result_use < 0 && ssa_op->result_def < 0) {
        FAIL("var result of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
      }
    } else {
      if (ssa_op->result_use >= 0 || ssa_op->result_def >= 0) {
        FAIL("non-var result of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
      }
    }

    if (ssa_op->op1_use >= 0) {
      if (ssa_op->op1_use >= ssa->vars_count) {
        FAIL("op1 use %d out of range\n", ssa_op->op1_use);
      }
      if (!is_defined(ssa, op_array, ssa_op->op1_use)) {
        FAIL("op1 use of " VARFMT " in " INSTRFMT " is not defined\n",
            VAR(ssa_op->op1_use), INSTR(i));
      }
      if (!is_in_use_chain(ssa, ssa_op->op1_use, i)) {
        FAIL("op1 use of " VARFMT " in " INSTRFMT " not in use chain\n",
            VAR(ssa_op->op1_use), INSTR(i));
      }
      if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_use].var) {
        FAIL("op1 use of " VARFMT " does not match op %d of " INSTRFMT "\n",
            VAR(ssa_op->op1_use), VAR_NUM(opline->op1.var), INSTR(i));
      }
    }
    if (ssa_op->op2_use >= 0) {
      if (ssa_op->op2_use >= ssa->vars_count) {
        FAIL("op2 use %d out of range\n", ssa_op->op2_use);
      }
      if (!is_defined(ssa, op_array, ssa_op->op2_use)) {
        FAIL("op2 use of " VARFMT " in " INSTRFMT " is not defined\n",
            VAR(ssa_op->op2_use), INSTR(i));
      }
      if (!is_in_use_chain(ssa, ssa_op->op2_use, i)) {
        FAIL("op2 use of " VARFMT " in " INSTRFMT " not in use chain\n",
            VAR(ssa_op->op2_use), INSTR(i));
      }
      if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_use].var) {
        FAIL("op2 use of " VARFMT " does not match op %d of " INSTRFMT "\n",
            VAR(ssa_op->op2_use), VAR_NUM(opline->op2.var), INSTR(i));
      }
    }
    if (ssa_op->result_use >= 0) {
      if (ssa_op->result_use >= ssa->vars_count) {
        FAIL("result use %d out of range\n", ssa_op->result_use);
      }
      if (!is_defined(ssa, op_array, ssa_op->result_use)) {
        FAIL("result use of " VARFMT " in " INSTRFMT " is not defined\n",
            VAR(ssa_op->result_use), INSTR(i));
      }
      if (!is_in_use_chain(ssa, ssa_op->result_use, i)) {
        FAIL("result use of " VARFMT " in " INSTRFMT " not in use chain\n",
          VAR(ssa_op->result_use), INSTR(i));
      }
      if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_use].var) {
        FAIL("result use of " VARFMT " does not match op %d of " INSTRFMT "\n",
            VAR(ssa_op->result_use), VAR_NUM(opline->result.var), INSTR(i));
      }
    }
    if (ssa_op->op1_def >= 0) {
      if (ssa_op->op1_def >= ssa->vars_count) {
        FAIL("op1 def %d out of range\n", ssa_op->op1_def);
      }
      if (ssa->vars[ssa_op->op1_def].definition != i) {
        FAIL("op1 def of " VARFMT " in " INSTRFMT " invalid\n",
            VAR(ssa_op->op1_def), INSTR(i));
      }
      if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_def].var) {
        FAIL("op1 def of " VARFMT " does not match op %d of " INSTRFMT "\n",
            VAR(ssa_op->op1_def), VAR_NUM(opline->op1.var), INSTR(i));
      }
    }
    if (ssa_op->op2_def >= 0) {
      if (ssa_op->op2_def >= ssa->vars_count) {
        FAIL("op2 def %d out of range\n", ssa_op->op2_def);
      }
      if (ssa->vars[ssa_op->op2_def].definition != i) {
        FAIL("op2 def of " VARFMT " in " INSTRFMT " invalid\n",
            VAR(ssa_op->op2_def), INSTR(i));
      }
      if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_def].var) {
        FAIL("op2 def of " VARFMT " does not match op %d of " INSTRFMT "\n",
            VAR(ssa_op->op2_def), VAR_NUM(opline->op2.var), INSTR(i));
      }
    }
    if (ssa_op->result_def >= 0) {
      if (ssa_op->result_def >= ssa->vars_count) {
        FAIL("result def %d out of range\n", ssa_op->result_def);
      }
      if (ssa->vars[ssa_op->result_def].definition != i) {
        FAIL("result def of " VARFMT " in " INSTRFMT " invalid\n",
            VAR(ssa_op->result_def), INSTR(i));
      }
      if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_def].var) {
        FAIL("result def of " VARFMT " does not match op %d of " INSTRFMT "\n",
            VAR(ssa_op->result_def), VAR_NUM(opline->result.var), INSTR(i));
      }
    }
  } FOREACH_INSTR_NUM_END();

  /* Phis */
  FOREACH_PHI(phi) {
    unsigned num_sources = NUM_PHI_SOURCES(phi);
    for (i = 0; i < num_sources; i++) {
      int source = phi->sources[i];
      if (source < 0) {
        FAIL(VARFMT " negative source\n", VAR(phi->ssa_var));
      }
      if (!is_in_phi_use_chain(ssa, source, phi)) {
        FAIL(VARFMT " not in phi use chain of %d\n", VAR(phi->ssa_var), source);
      }
      if (ssa->vars[source].var != ssa->vars[phi->ssa_var].var) {
        FAIL(VARFMT " source of phi for " VARFMT "\n", VAR(source), VAR(phi->ssa_var));
      }
      if (phi->use_chains[i]) {
        int j;
        for (j = i + 1; j < num_sources; j++) {
          if (phi->sources[j] == source && phi->use_chains[j]) {
            FAIL("use chain for source " VARFMT " of phi " VARFMT
              " at %d despite earlier use\n", VAR(source), VAR(phi->ssa_var), j);
          }
        }
      }
    }
    if (ssa->vars[phi->ssa_var].definition_phi != phi) {
      FAIL(VARFMT " does not define this phi\n", VAR(phi->ssa_var));
    }
  } FOREACH_PHI_END();

  /* Blocks */
  for (i = 0; i < cfg->blocks_count; i++) {
    zend_basic_block *block = &cfg->blocks[i];
    int *predecessors = &cfg->predecessors[block->predecessor_offset];
    int s, j;

    if (i != 0 && block->start < (block-1)->start + (block-1)->len) {
      FAIL("Block %d start %d smaller previous end %d\n",
        i, block->start, (block-1)->start + (block-1)->len);
    }
    if (i != cfg->blocks_count-1 && block->start + block->len > (block+1)->start) {
      FAIL("Block %d end %d greater next start %d\n",
        i, block->start + block->len, (block+1)->start);
    }

    for (j = block->start; j < block->start + block->len; j++) {
      if (cfg->map[j] != i) {
        FAIL("Instr " INSTRFMT " not associated with block %d\n", INSTR(j), i);
      }
    }

    if (!(block->flags & ZEND_BB_REACHABLE)) {
      if (ssa->blocks[i].phis) {
        FAIL("Unreachable block %d has phis\n", i);
      }
      continue;
    }

    for (s = 0; s < block->successors_count; s++) {
      zend_basic_block *next_block;
      if (block->successors[s] < 0) {
        FAIL("Successor number %d of %d negative", s, i);
      }
      next_block = &cfg->blocks[block->successors[s]];
      if (!(next_block->flags & ZEND_BB_REACHABLE)) {
        FAIL("Successor %d of %d not reachable\n", block->successors[s], i);
      }
      if (!is_in_predecessors(cfg, next_block, i)) {
        FAIL("Block %d predecessors missing %d\n", block->successors[s], i);
      }
    }

    for (j = 0; j < block->predecessors_count; j++) {
      if (predecessors[j] >= 0) {
        int k;
        zend_basic_block *prev_block = &cfg->blocks[predecessors[j]];
        if (!(prev_block->flags & ZEND_BB_REACHABLE)) {
          FAIL("Predecessor %d of %d not reachable\n", predecessors[j], i);
        }
        if (!is_in_successors(prev_block, i)) {
          FAIL("Block %d successors missing %d\n", predecessors[j], i);
        }
        for (k = 0; k < block->predecessors_count; k++) {
          if (k != j && predecessors[k] == predecessors[j]) {
            FAIL("Block %d has duplicate predecessor %d\n", i, predecessors[j]);
          }
        }
      }
    }
  }

finish:
  if (status == FAILURE) {
    zend_dump_op_array(op_array, ZEND_DUMP_SSA, "at SSA integrity verification", ssa);
    ZEND_ASSERT(0 && "SSA integrity verification failed");
  }
}

Coverage Report

Created: 2026-01-18 06:48

Line	Count	Source
1		/*
2		+----------------------------------------------------------------------+
3		\| Zend Engine, SSA validation \|
4		+----------------------------------------------------------------------+
5		\| Copyright (c) The PHP Group \|
6		+----------------------------------------------------------------------+
7		\| This source file is subject to version 3.01 of the PHP license, \|
8		\| that is bundled with this package in the file LICENSE, and is \|
9		\| available through the world-wide-web at the following url: \|
10		\| https://www.php.net/license/3_01.txt \|
11		\| If you did not receive a copy of the PHP license and are unable to \|
12		\| obtain it through the world-wide-web, please send a note to \|
13		\| license@php.net so we can mail you a copy immediately. \|
14		+----------------------------------------------------------------------+
15		\| Authors: Nikita Popov <nikic@php.net> \|
16		+----------------------------------------------------------------------+
17		*/
18
19		#include "Optimizer/zend_optimizer_internal.h"
20
21		/* The ssa_verify_integrity() function ensures that that certain invariants of the SSA form and
22		* CFG are upheld and prints messages to stderr if this is not the case. */
23
24	122k	static inline bool is_in_use_chain(zend_ssa *ssa, int var, int check) {
25	122k	int use;
26	287k	FOREACH_USE(&ssa->vars[var], use) {
27	287k	if (use == check) {
28	122k	return true;
29	122k	}
30	287k	} FOREACH_USE_END();
31	0	return false;
32	122k	}
33
34	49.4k	static inline bool is_in_phi_use_chain(zend_ssa ssa, int var, zend_ssa_phi check) {
35	49.4k	zend_ssa_phi *phi;
36	107k	FOREACH_PHI_USE(&ssa->vars[var], phi) {
37	107k	if (phi == check) {
38	49.4k	return true;
39	49.4k	}
40	107k	} FOREACH_PHI_USE_END();
41	0	return false;
42	49.4k	}
43
44	122k	static inline bool is_used_by_op(zend_ssa *ssa, int op, int check) {
45	122k	zend_ssa_op *ssa_op = &ssa->ops[op];
46	122k	return (ssa_op->op1_use == check)
47	28.5k	\|\| (ssa_op->op2_use == check)
48	921	\|\| (ssa_op->result_use == check);
49	122k	}
50
51	96.4k	static inline bool is_defined_by_op(zend_ssa *ssa, int op, int check) {
52	96.4k	zend_ssa_op *ssa_op = &ssa->ops[op];
53	96.4k	return (ssa_op->op1_def == check)
54	91.5k	\|\| (ssa_op->op2_def == check)
55	91.4k	\|\| (ssa_op->result_def == check);
56	96.4k	}
57
58	49.4k	static inline bool is_in_phi_sources(zend_ssa ssa, zend_ssa_phi phi, int check) {
59	49.4k	int source;
60	188k	FOREACH_PHI_SOURCE(phi, source) {
61	188k	if (source == check) {
62	49.4k	return true;
63	49.4k	}
64	188k	} FOREACH_PHI_SOURCE_END();
65	0	return false;
66	49.4k	}
67
68	31.4k	static inline bool is_in_predecessors(zend_cfg cfg, zend_basic_block block, int check) {
69	31.4k	int i, *predecessors = &cfg->predecessors[block->predecessor_offset];
70	41.6k	for (i = 0; i < block->predecessors_count; i++) {
71	41.6k	if (predecessors[i] == check) {
72	31.4k	return true;
73	31.4k	}
74	41.6k	}
75	0	return false;
76	31.4k	}
77
78	31.4k	static inline bool is_in_successors(zend_basic_block *block, int check) {
79	31.4k	int s;
80	41.6k	for (s = 0; s < block->successors_count; s++) {
81	41.6k	if (block->successors[s] == check) {
82	31.4k	return true;
83	31.4k	}
84	41.6k	}
85	0	return false;
86	31.4k	}
87
88	366k	static inline bool is_var_type(uint8_t type) {
89	366k	return (type & (IS_CV\|IS_VAR\|IS_TMP_VAR)) != 0;
90	366k	}
91
92	122k	static inline bool is_defined(const zend_ssa ssa, const zend_op_array op_array, int var) {
93	122k	const zend_ssa_var *ssa_var = &ssa->vars[var];
94	122k	return ssa_var->definition >= 0 \|\| ssa_var->definition_phi \|\| var < op_array->last_var;
95	122k	}
96
97	0	#define FAIL(...) do { \
98	0	if (status == SUCCESS) { \
99	0	fprintf(stderr, "\nIn function %s::%s (%s):\n", \
100	0	op_array->scope ? ZSTR_VAL(op_array->scope->name) : "", \
101	0	op_array->function_name ? ZSTR_VAL(op_array->function_name) : "{main}", extra); \
102	0	} \
103	0	fprintf(stderr, __VA_ARGS__); \
104	0	status = FAILURE; \
105	0	} while (0)
106
107		#define VARFMT "%d (%s%s)"
108		#define VAR(i) \
109	0	(i), (ssa->vars[i].var < op_array->last_var ? "CV $" : "TMP"), \
110	0	(ssa->vars[i].var < op_array->last_var ? ZSTR_VAL(op_array->vars[ssa->vars[i].var]) : "")
111
112		#define INSTRFMT "%d (%s)"
113		#define INSTR(i) \
114		(i), (zend_get_opcode_name(op_array->opcodes[i].opcode))
115
116	841	void ssa_verify_integrity(zend_op_array op_array, zend_ssa ssa, const char *extra) {
117	841	zend_cfg *cfg = &ssa->cfg;
118	841	zend_ssa_phi *phi;
119	841	int i;
120	841	zend_result status = SUCCESS;
121
122		/* Vars */
123	134k	for (i = 0; i < ssa->vars_count; i++) {
124	134k	zend_ssa_var *var = &ssa->vars[i];
125	134k	int use;
126	134k	uint32_t type = ssa->var_info[i].type;
127
128	134k	if (var->definition < 0 && !var->definition_phi && i > op_array->last_var) {
129	4.69k	if (var->use_chain >= 0) {
130	0	FAIL("var " VARFMT " without def has op uses\n", VAR(i));
131	0	}
132	4.69k	if (var->phi_use_chain) {
133	0	FAIL("var " VARFMT " without def has phi uses\n", VAR(i));
134	0	}
135	4.69k	}
136	134k	if (var->definition >= 0 && var->definition_phi) {
137	0	FAIL("var " VARFMT " has both def and def_phi\n", VAR(i));
138	0	}
139	134k	if (var->definition >= 0) {
140	96.4k	if (!is_defined_by_op(ssa, var->definition, i)) {
141	0	FAIL("var " VARFMT " not defined by op " INSTRFMT "\n",
142	0	VAR(i), INSTR(var->definition));
143	0	}
144	96.4k	}
145	134k	if (var->definition_phi) {
146	29.2k	if (var->definition_phi->ssa_var != i) {
147	0	FAIL("var " VARFMT " not defined by given phi\n", VAR(i));
148	0	}
149	29.2k	}
150
151		/* Floyd's cycle detection algorithm, applied for use chain. */
152	134k	use = var->use_chain;
153	134k	int second_use = use;
154	147k	while (use >= 0 && second_use >= 0) {
155	109k	use = zend_ssa_next_use(ssa->ops, var - ssa->vars, use);
156	109k	second_use = zend_ssa_next_use(ssa->ops, var - ssa->vars, second_use);
157	109k	if (second_use < 0) {
158	96.0k	break;
159	96.0k	}
160	13.1k	second_use = zend_ssa_next_use(ssa->ops, var - ssa->vars, second_use);
161	13.1k	if (use == second_use) {
162	0	FAIL("cycle in uses of " VARFMT "\n", VAR(i));
163	0	goto finish;
164	0	}
165	13.1k	}
166
167	256k	FOREACH_USE(var, use) {
168	256k	if (!is_used_by_op(ssa, use, i)) {
169	0	fprintf(stderr, "var " VARFMT " not in uses of op %d\n", VAR(i), use);
170	0	}
171	256k	} FOREACH_USE_END();
172
173		/* Floyd's cycle detection algorithm, applied for phi nodes. */
174	134k	phi = var->phi_use_chain;
175	134k	zend_ssa_phi *second_phi = phi;
176	142k	while (phi && second_phi) {
177	40.6k	phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, phi);
178	40.6k	second_phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, second_phi);
179	40.6k	if (!second_phi) {
180	31.7k	break;
181	31.7k	}
182	8.82k	second_phi = zend_ssa_next_use_phi(ssa, var - ssa->vars, second_phi);
183	8.82k	if (phi == second_phi) {
184	0	FAIL("cycle in phi uses of " VARFMT "\n", VAR(i));
185	0	goto finish;
186	0	}
187	8.82k	}
188
189	183k	FOREACH_PHI_USE(var, phi) {
190	183k	if (!is_in_phi_sources(ssa, phi, i)) {
191	0	FAIL("var " VARFMT " not in phi sources of %d\n", VAR(i), phi->ssa_var);
192	0	}
193	183k	} FOREACH_PHI_USE_END();
194
195	134k	if ((type & (MAY_BE_ARRAY_KEY_ANY-MAY_BE_ARRAY_EMPTY)) && !(type & MAY_BE_ARRAY_OF_ANY)) {
196	0	FAIL("var " VARFMT " has array key type but not value type\n", VAR(i));
197	0	}
198	134k	if ((type & MAY_BE_ARRAY_OF_ANY) && !(type & (MAY_BE_ARRAY_KEY_ANY-MAY_BE_ARRAY_EMPTY))) {
199	0	FAIL("var " VARFMT " has array value type but not key type\n", VAR(i));
200	0	}
201	134k	if ((type & MAY_BE_REF) && ssa->var_info[i].ce) {
202	0	FAIL("var " VARFMT " may be ref but has ce\n", VAR(i));
203	0	}
204	134k	}
205
206		/* Instructions */
207	169k	FOREACH_INSTR_NUM(i) {
208	169k	zend_ssa_op *ssa_op = &ssa->ops[i];
209	169k	zend_op *opline = &op_array->opcodes[i];
210	169k	if (is_var_type(opline->op1_type)) {
211	93.7k	if (ssa_op->op1_use < 0 && ssa_op->op1_def < 0) {
212	0	FAIL("var op1 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
213	0	}
214	93.7k	} else {
215	28.3k	if (ssa_op->op1_use >= 0 \|\| ssa_op->op1_def >= 0) {
216	0	FAIL("non-var op1 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
217	0	}
218	28.3k	}
219	169k	if (is_var_type(opline->op2_type)) {
220	27.8k	if (ssa_op->op2_use < 0 && ssa_op->op2_def < 0) {
221	0	FAIL("var op2 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
222	0	}
223	94.1k	} else {
224	94.1k	if (ssa_op->op2_use >= 0 \|\| ssa_op->op2_def >= 0) {
225	0	FAIL("non-var op2 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
226	0	}
227	94.1k	}
228	169k	if (is_var_type(opline->result_type)) {
229	91.4k	if (ssa_op->result_use < 0 && ssa_op->result_def < 0) {
230	0	FAIL("var result of " INSTRFMT " does not use/def an ssa var\n", INSTR(i));
231	0	}
232	91.4k	} else {
233	30.5k	if (ssa_op->result_use >= 0 \|\| ssa_op->result_def >= 0) {
234	0	FAIL("non-var result of " INSTRFMT " uses or defs an ssa var\n", INSTR(i));
235	0	}
236	30.5k	}
237
238	169k	if (ssa_op->op1_use >= 0) {
239	93.7k	if (ssa_op->op1_use >= ssa->vars_count) {
240	0	FAIL("op1 use %d out of range\n", ssa_op->op1_use);
241	0	}
242	93.7k	if (!is_defined(ssa, op_array, ssa_op->op1_use)) {
243	0	FAIL("op1 use of " VARFMT " in " INSTRFMT " is not defined\n",
244	0	VAR(ssa_op->op1_use), INSTR(i));
245	0	}
246	93.7k	if (!is_in_use_chain(ssa, ssa_op->op1_use, i)) {
247	0	FAIL("op1 use of " VARFMT " in " INSTRFMT " not in use chain\n",
248	0	VAR(ssa_op->op1_use), INSTR(i));
249	0	}
250	93.7k	if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_use].var) {
251	0	FAIL("op1 use of " VARFMT " does not match op %d of " INSTRFMT "\n",
252	0	VAR(ssa_op->op1_use), VAR_NUM(opline->op1.var), INSTR(i));
253	0	}
254	93.7k	}
255	169k	if (ssa_op->op2_use >= 0) {
256	27.8k	if (ssa_op->op2_use >= ssa->vars_count) {
257	0	FAIL("op2 use %d out of range\n", ssa_op->op2_use);
258	0	}
259	27.8k	if (!is_defined(ssa, op_array, ssa_op->op2_use)) {
260	0	FAIL("op2 use of " VARFMT " in " INSTRFMT " is not defined\n",
261	0	VAR(ssa_op->op2_use), INSTR(i));
262	0	}
263	27.8k	if (!is_in_use_chain(ssa, ssa_op->op2_use, i)) {
264	0	FAIL("op2 use of " VARFMT " in " INSTRFMT " not in use chain\n",
265	0	VAR(ssa_op->op2_use), INSTR(i));
266	0	}
267	27.8k	if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_use].var) {
268	0	FAIL("op2 use of " VARFMT " does not match op %d of " INSTRFMT "\n",
269	0	VAR(ssa_op->op2_use), VAR_NUM(opline->op2.var), INSTR(i));
270	0	}
271	27.8k	}
272	169k	if (ssa_op->result_use >= 0) {
273	921	if (ssa_op->result_use >= ssa->vars_count) {
274	0	FAIL("result use %d out of range\n", ssa_op->result_use);
275	0	}
276	921	if (!is_defined(ssa, op_array, ssa_op->result_use)) {
277	0	FAIL("result use of " VARFMT " in " INSTRFMT " is not defined\n",
278	0	VAR(ssa_op->result_use), INSTR(i));
279	0	}
280	921	if (!is_in_use_chain(ssa, ssa_op->result_use, i)) {
281	0	FAIL("result use of " VARFMT " in " INSTRFMT " not in use chain\n",
282	0	VAR(ssa_op->result_use), INSTR(i));
283	0	}
284	921	if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_use].var) {
285	0	FAIL("result use of " VARFMT " does not match op %d of " INSTRFMT "\n",
286	0	VAR(ssa_op->result_use), VAR_NUM(opline->result.var), INSTR(i));
287	0	}
288	921	}
289	169k	if (ssa_op->op1_def >= 0) {
290	4.90k	if (ssa_op->op1_def >= ssa->vars_count) {
291	0	FAIL("op1 def %d out of range\n", ssa_op->op1_def);
292	0	}
293	4.90k	if (ssa->vars[ssa_op->op1_def].definition != i) {
294	0	FAIL("op1 def of " VARFMT " in " INSTRFMT " invalid\n",
295	0	VAR(ssa_op->op1_def), INSTR(i));
296	0	}
297	4.90k	if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_def].var) {
298	0	FAIL("op1 def of " VARFMT " does not match op %d of " INSTRFMT "\n",
299	0	VAR(ssa_op->op1_def), VAR_NUM(opline->op1.var), INSTR(i));
300	0	}
301	4.90k	}
302	169k	if (ssa_op->op2_def >= 0) {
303	78	if (ssa_op->op2_def >= ssa->vars_count) {
304	0	FAIL("op2 def %d out of range\n", ssa_op->op2_def);
305	0	}
306	78	if (ssa->vars[ssa_op->op2_def].definition != i) {
307	0	FAIL("op2 def of " VARFMT " in " INSTRFMT " invalid\n",
308	0	VAR(ssa_op->op2_def), INSTR(i));
309	0	}
310	78	if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_def].var) {
311	0	FAIL("op2 def of " VARFMT " does not match op %d of " INSTRFMT "\n",
312	0	VAR(ssa_op->op2_def), VAR_NUM(opline->op2.var), INSTR(i));
313	0	}
314	78	}
315	169k	if (ssa_op->result_def >= 0) {
316	91.4k	if (ssa_op->result_def >= ssa->vars_count) {
317	0	FAIL("result def %d out of range\n", ssa_op->result_def);
318	0	}
319	91.4k	if (ssa->vars[ssa_op->result_def].definition != i) {
320	0	FAIL("result def of " VARFMT " in " INSTRFMT " invalid\n",
321	0	VAR(ssa_op->result_def), INSTR(i));
322	0	}
323	91.4k	if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_def].var) {
324	0	FAIL("result def of " VARFMT " does not match op %d of " INSTRFMT "\n",
325	0	VAR(ssa_op->result_def), VAR_NUM(opline->result.var), INSTR(i));
326	0	}
327	91.4k	}
328	169k	} FOREACH_INSTR_NUM_END();
329
330		/* Phis */
331	53.3k	FOREACH_PHI(phi) {
332	53.3k	unsigned num_sources = NUM_PHI_SOURCES(phi);
333	78.6k	for (i = 0; i < num_sources; i++) {
334	49.4k	int source = phi->sources[i];
335	49.4k	if (source < 0) {
336	0	FAIL(VARFMT " negative source\n", VAR(phi->ssa_var));
337	0	}
338	49.4k	if (!is_in_phi_use_chain(ssa, source, phi)) {
339	0	FAIL(VARFMT " not in phi use chain of %d\n", VAR(phi->ssa_var), source);
340	0	}
341	49.4k	if (ssa->vars[source].var != ssa->vars[phi->ssa_var].var) {
342	0	FAIL(VARFMT " source of phi for " VARFMT "\n", VAR(source), VAR(phi->ssa_var));
343	0	}
344	49.4k	if (phi->use_chains[i]) {
345	8.82k	int j;
346	17.0k	for (j = i + 1; j < num_sources; j++) {
347	8.24k	if (phi->sources[j] == source && phi->use_chains[j]) {
348	0	FAIL("use chain for source " VARFMT " of phi " VARFMT
349	0	" at %d despite earlier use\n", VAR(source), VAR(phi->ssa_var), j);
350	0	}
351	8.24k	}
352	8.82k	}
353	49.4k	}
354	53.3k	if (ssa->vars[phi->ssa_var].definition_phi != phi) {
355	0	FAIL(VARFMT " does not define this phi\n", VAR(phi->ssa_var));
356	0	}
357	53.3k	} FOREACH_PHI_END();
358
359		/* Blocks */
360	24.1k	for (i = 0; i < cfg->blocks_count; i++) {
361	23.3k	zend_basic_block *block = &cfg->blocks[i];
362	23.3k	int *predecessors = &cfg->predecessors[block->predecessor_offset];
363	23.3k	int s, j;
364
365	23.3k	if (i != 0 && block->start < (block-1)->start + (block-1)->len) {
366	0	FAIL("Block %d start %d smaller previous end %d\n",
367	0	i, block->start, (block-1)->start + (block-1)->len);
368	0	}
369	23.3k	if (i != cfg->blocks_count-1 && block->start + block->len > (block+1)->start) {
370	0	FAIL("Block %d end %d greater next start %d\n",
371	0	i, block->start + block->len, (block+1)->start);
372	0	}
373
374	146k	for (j = block->start; j < block->start + block->len; j++) {
375	123k	if (cfg->map[j] != i) {
376	0	FAIL("Instr " INSTRFMT " not associated with block %d\n", INSTR(j), i);
377	0	}
378	123k	}
379
380	23.3k	if (!(block->flags & ZEND_BB_REACHABLE)) {
381	1.14k	if (ssa->blocks[i].phis) {
382	0	FAIL("Unreachable block %d has phis\n", i);
383	0	}
384	1.14k	continue;
385	1.14k	}
386
387	53.6k	for (s = 0; s < block->successors_count; s++) {
388	31.4k	zend_basic_block *next_block;
389	31.4k	if (block->successors[s] < 0) {
390	0	FAIL("Successor number %d of %d negative", s, i);
391	0	}
392	31.4k	next_block = &cfg->blocks[block->successors[s]];
393	31.4k	if (!(next_block->flags & ZEND_BB_REACHABLE)) {
394	0	FAIL("Successor %d of %d not reachable\n", block->successors[s], i);
395	0	}
396	31.4k	if (!is_in_predecessors(cfg, next_block, i)) {
397	0	FAIL("Block %d predecessors missing %d\n", block->successors[s], i);
398	0	}
399	31.4k	}
400
401	53.6k	for (j = 0; j < block->predecessors_count; j++) {
402	31.4k	if (predecessors[j] >= 0) {
403	31.4k	int k;
404	31.4k	zend_basic_block *prev_block = &cfg->blocks[predecessors[j]];
405	31.4k	if (!(prev_block->flags & ZEND_BB_REACHABLE)) {
406	0	FAIL("Predecessor %d of %d not reachable\n", predecessors[j], i);
407	0	}
408	31.4k	if (!is_in_successors(prev_block, i)) {
409	0	FAIL("Block %d successors missing %d\n", predecessors[j], i);
410	0	}
411	83.3k	for (k = 0; k < block->predecessors_count; k++) {
412	51.8k	if (k != j && predecessors[k] == predecessors[j]) {
413	0	FAIL("Block %d has duplicate predecessor %d\n", i, predecessors[j]);
414	0	}
415	51.8k	}
416	31.4k	}
417	31.4k	}
418	22.1k	}
419
420	841	finish:
421	841	if (status == FAILURE) {
422	0	zend_dump_op_array(op_array, ZEND_DUMP_SSA, "at SSA integrity verification", ssa);
423		ZEND_ASSERT(0 && "SSA integrity verification failed");
424	0	}
425	841	}