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

Source
/*
   +----------------------------------------------------------------------+
   | Zend Engine, SSA validation                                          |
   +----------------------------------------------------------------------+
   | Copyright © The PHP Group and Contributors.                          |
   +----------------------------------------------------------------------+
   | This source file is subject to the Modified BSD License that is      |
   | bundled with this package in the file LICENSE, and is available      |
   | through the World Wide Web at <https://www.php.net/license/>.        |
   |                                                                      |
   | SPDX-License-Identifier: BSD-3-Clause                                |
   +----------------------------------------------------------------------+
   | 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 *predecessors = &cfg->predecessors[block->predecessor_offset];
  for (uint32_t 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) {
  for (uint32_t 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) {
    uint32_t 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];
    uint32_t 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 (uint32_t 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) {
        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 (uint32_t 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-06-02 06:39

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