/*

   +----------------------------------------------------------------------+

   | Zend Engine, Call Graph                                              |

   +----------------------------------------------------------------------+

   | 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>                                |

   +----------------------------------------------------------------------+

*/

#ifndef _SCDF_H

#define _SCDF_H

#include "zend_bitset.h"

typedef struct _scdf_ctx {

  zend_op_array *op_array;

  zend_ssa *ssa;

  zend_bitset instr_worklist;

  /* Represent phi-instructions through the defining var */

  zend_bitset phi_var_worklist;

  zend_bitset block_worklist;

  zend_bitset executable_blocks;

  /* 1 bit per edge, see scdf_edge(cfg, from, to) */

  zend_bitset feasible_edges;

  uint32_t instr_worklist_len;

  uint32_t phi_var_worklist_len;

  uint32_t block_worklist_len;

  struct {

    void (*visit_instr)(

      struct _scdf_ctx *scdf, zend_op *opline, zend_ssa_op *ssa_op);

    void (*visit_phi)(

      struct _scdf_ctx *scdf, const zend_ssa_phi *phi);

    void (*mark_feasible_successors)(

      struct _scdf_ctx *scdf, int block_num, zend_basic_block *block,

      zend_op *opline, zend_ssa_op *ssa_op);

  } handlers;

} scdf_ctx;

void scdf_init(zend_optimizer_ctx *ctx, scdf_ctx *scdf, zend_op_array *op_array, zend_ssa *ssa);

void scdf_solve(scdf_ctx *scdf, const char *name);

uint32_t scdf_remove_unreachable_blocks(const scdf_ctx *scdf);

/* Add uses to worklist */

static inline void scdf_add_to_worklist(const scdf_ctx *scdf, int var_num) {

  const zend_ssa *ssa = scdf->ssa;

  const zend_ssa_var *var = &ssa->vars[var_num];

  int use;

  zend_ssa_phi *phi;

  FOREACH_USE(var, use) {

    zend_bitset_incl(scdf->instr_worklist, use);

  } FOREACH_USE_END();

  FOREACH_PHI_USE(var, phi) {

    zend_bitset_incl(scdf->phi_var_worklist, phi->ssa_var);

  } FOREACH_PHI_USE_END();

}

sccp.c:scdf_add_to_worklist

Line

Count

Source

53

521k

static inline void scdf_add_to_worklist(const scdf_ctx *scdf, int var_num) {

54

521k

  const zend_ssa *ssa = scdf->ssa;

55

521k

  const zend_ssa_var *var = &ssa->vars[var_num];

56

521k

  int use;

57

521k

  zend_ssa_phi *phi;

58

1.02M

  FOREACH_USE(var, use) {

59

1.02M

    zend_bitset_incl(scdf->instr_worklist, use);

60

1.02M

  } FOREACH_USE_END();

61

652k

  FOREACH_PHI_USE(var, phi) {

62

652k

    zend_bitset_incl(scdf->phi_var_worklist, phi->ssa_var);

63

652k

  } FOREACH_PHI_USE_END();

64

521k

}

Unexecuted instantiation: scdf.c:scdf_add_to_worklist

/* This should usually not be necessary, however it's used for type narrowing. */

static inline void scdf_add_def_to_worklist(const scdf_ctx *scdf, int var_num) {

  const zend_ssa_var *var = &scdf->ssa->vars[var_num];

  if (var->definition >= 0) {

    zend_bitset_incl(scdf->instr_worklist, var->definition);

  } else if (var->definition_phi) {

    zend_bitset_incl(scdf->phi_var_worklist, var_num);

  }

}

Unexecuted instantiation: sccp.c:scdf_add_def_to_worklist

Unexecuted instantiation: scdf.c:scdf_add_def_to_worklist

static inline uint32_t scdf_edge(const zend_cfg *cfg, int from, uint32_t to) {

  const zend_basic_block *to_block = cfg->blocks + to;

  for (uint32_t i = 0; i < to_block->predecessors_count; i++) {

    uint32_t edge = to_block->predecessor_offset + i;

    if (cfg->predecessors[edge] == from) {

      return edge;

    }

  }

  ZEND_UNREACHABLE();

}

sccp.c:scdf_edge

Line

Count

Source

76

145k

static inline uint32_t scdf_edge(const zend_cfg *cfg, int from, uint32_t to) {

77

145k

  const zend_basic_block *to_block = cfg->blocks + to;

78

79

213k

  for (uint32_t i = 0; i < to_block->predecessors_count; i++) {

80

213k

    uint32_t edge = to_block->predecessor_offset + i;

81

82

213k

    if (cfg->predecessors[edge] == from) {

83

145k

      return edge;

84

145k

    }

85

213k

  }

86

0

  ZEND_UNREACHABLE();

87

0

}

scdf.c:scdf_edge

Line

Count

Source

76

100k

static inline uint32_t scdf_edge(const zend_cfg *cfg, int from, uint32_t to) {

77

100k

  const zend_basic_block *to_block = cfg->blocks + to;

78

79

136k

  for (uint32_t i = 0; i < to_block->predecessors_count; i++) {

80

136k

    uint32_t edge = to_block->predecessor_offset + i;

81

82

136k

    if (cfg->predecessors[edge] == from) {

83

100k

      return edge;

84

100k

    }

85

136k

  }

86

0

  ZEND_UNREACHABLE();

87

0

}

static inline bool scdf_is_edge_feasible(const scdf_ctx *scdf, int from, uint32_t to) {

  uint32_t edge = scdf_edge(&scdf->ssa->cfg, from, to);

  return zend_bitset_in(scdf->feasible_edges, edge);

}

sccp.c:scdf_is_edge_feasible

Line

Count

Source

89

145k

static inline bool scdf_is_edge_feasible(const scdf_ctx *scdf, int from, uint32_t to) {

90

145k

  uint32_t edge = scdf_edge(&scdf->ssa->cfg, from, to);

91

145k

  return zend_bitset_in(scdf->feasible_edges, edge);

92

145k

}

Unexecuted instantiation: scdf.c:scdf_is_edge_feasible

void scdf_mark_edge_feasible(scdf_ctx *scdf, int from, int to);

#endif