package bap-std

  1. Overview
  2. Docs
package bap-std
Legend:
Library
Module
Module type
Parameter
Class
Class type

Subroutine.

type t = sub term

Subroutine is a set of blocks. The first block of a function is considered an entry block.

val create : ?args:arg term list -> ?blks:blk term list -> ?tid:tid -> ?name:string -> unit -> t

create ?name () creates a new subroutine.

Creates a subroutine that includes given arguments and blocks. The order of the terms is preserved with the first block being the entry block. No references between blocks are added, so the blocks shall be correctly linked and be reachable from the entry block.

If tid is not specied then a fresh one is generated. if name is not specified then a fresh name is derived from the tid.

  • since 2.3.0 has the [args] optional parameter
  • since 2.3.0 has the [blks] optional parameter
val lift : block -> cfg -> sub term

lift entry takes an basic block of assembler instructions, as an entry and lifts it to the subroutine term.

val name : t -> string

name sub returns a subroutine name

val with_name : t -> string -> t

updates subroutine name

val ssa : t -> t

ssa sub returns sub in SSA form. If program is already in SSA, then do nothing (see also is_ssa). The underlying algorithm produces a semi-pruned SSA form. To represent different versions of the same variable we use variable versions. Any definition of a variable increases its version number. So, the zero version is reserved for variables that weren't defined before the first use.

val is_ssa : t -> bool

is_ssa sub is true if sub was transformed into an SSA form. This is O(1) predicate that doesn't really check, that a subroutine is in an SSA form, so it is a responsibility of a user to preserve the SSA form on any transformation.

val free_vars : t -> Var.Set.t

free_vars sub computes a set of variables that are free in a given subroutine sub. The variable is considered free if it is used before defined or is not locally bound. If sub is in an SSA form, then the set is computed trivially, thanks to a naming scheme. If program is not in an SSA form, then a BFS on a dominators tree is used.

val to_graph : t -> Graphs.Tid.t

to_graph sub builds a graph of subroutine sub.

Graph nodes are block term identifiers and edges are labeled with term identifiers of the jmp terms that correspond to the given edge.

  • since 2.1 the returned graph contains two pseudo-nodes

Graphs.Tid.start and Graphs.Tid.exit so that all nodes that has in-degree 0 or that start a strongly connected component are connected to the start node (the same for exit but on the reversed graph.

Edges from start to other nodes are labeled with the Graphs.Tid.start tid.

Edges from nodes to the exit node are labeled with the Graphs.Tid.exit tid.

val to_cfg : t -> Graphs.Ir.t

to_cfg sub builds a graph representation of a subroutine sub. All graph operations are mapped to corresponding Term operations. See Graphlib.Ir for more information.

val of_cfg : Graphs.Ir.t -> t

of_cfg cfg extracts a sub term from a given graph cfg. Since Graphlib.Ir module builds term incrementally this operation is just a projection, i.e., it has O(0) complexity.

val compute_liveness : t -> (tid, Var.Set.t) Graphlib.Std.Solution.t

compute_liveness sub computes a set of live variables for each block.

For a block b and solution s = compute_liveness sub, Solution.get s (Term.tid b) is a set of variables that are live at the _exit_ from this block.

A set of variables that are live (free) in the whole subroutine is the set of variables that are live at the Graphs.Tid.start node.

When the subroutine is in the SSA form then the phi-nodes have the following semantics.

Informally, a phi-node defines the values on the corresponding edges of the predecessors.

  • since 2.1
  • since 2.5.0 supports SSA
  • before 2.5.0

    the subroutine must not be in the SSA form

  • deprecated [since 2022-03] use Live.compute
val flatten : t -> t

flatten sub returns sub in flattened form in which all operands are trivial. @see Blk.flatten for more information about flattening.

  • since 2.5.0
val aliases : string list tag

other names for the given subroutine.

val const : unit tag

A subroutine doesn't examine any values except its arguments, and have no effects except the return value. Basically this is just slightly more strict class than the pure attribute below, since function is not allowed to read global memory. Note that a function that has pointer arguments and examines the data pointed to is not const. Likewise, a function that calls a non-const function usually is not be const. It does not make sense for a const function to return void

val pure : unit tag

A subroutine have no effects except the return value and their return value depends only on the parameters and/or global variables.

val stub : unit tag

A subroutine is a stub

val extern : unit tag

A subroutine is visible outside of the compilation unit

val leaf : unit tag

a subroutine doesn't contain any calls in any disguise, i.e., no longjmps, indirect calls, exceptions, etc.

val malloc : unit tag

A subroutine is malloc-like, i.e., the pointer P returned by the subroutine cannot alias any other pointer valid when the function returns, and moreover no pointers to valid objects occur in any storage addressed by P.

val noreturn : unit tag

A subroutine will not return (either loop infinitely or abort a program)

val returns_twice : unit tag

A subroutine may return more than one time. Examples of such functions are setjmp and vfork

val nothrow : unit tag

A subroutine doesn't throw exceptions

val entry_point : unit tag

a subroutine is the binary entry point

val intrinsic : unit tag

a subroutine is an intrinisic or special instruction not a real subroutine.

  • since 2.5.0
module Builder : sig ... end

Subroutine builder

val pp_slots : string list -> Stdlib.Format.formatter -> t -> unit

pp_slots names prints slots that are in names.

include Regular.Std.Regular.S with type t := t
val bin_size_t : t Bin_prot.Size.sizer
val bin_write_t : t Bin_prot.Write.writer
val bin_read_t : t Bin_prot.Read.reader
val __bin_read_t__ : (int -> t) Bin_prot.Read.reader
val bin_shape_t : Bin_prot.Shape.t
val bin_writer_t : t Bin_prot.Type_class.writer
val bin_reader_t : t Bin_prot.Type_class.reader
val bin_t : t Bin_prot.Type_class.t
val t_of_sexp : Sexplib0__.Sexp.t -> t
val sexp_of_t : t -> Sexplib0__.Sexp.t
val to_string : t -> string
val str : unit -> t -> string
val pps : unit -> t -> string
val ppo : Core_kernel.Out_channel.t -> t -> unit
val pp_seq : Stdlib.Format.formatter -> t Core_kernel.Sequence.t -> unit
val pp : Base__.Formatter.t -> t -> unit
val (>=) : t -> t -> bool
val (<=) : t -> t -> bool
val (=) : t -> t -> bool
val (>) : t -> t -> bool
val (<) : t -> t -> bool
val (<>) : t -> t -> bool
val equal : t -> t -> bool
val compare : t -> t -> int
val min : t -> t -> t
val max : t -> t -> t
val ascending : t -> t -> int
val descending : t -> t -> int
val between : t -> low:t -> high:t -> bool
val clamp_exn : t -> min:t -> max:t -> t
val clamp : t -> min:t -> max:t -> t Base__.Or_error.t
type comparator_witness
val validate_lbound : min:t Base__.Maybe_bound.t -> t Base__.Validate.check
val validate_ubound : max:t Base__.Maybe_bound.t -> t Base__.Validate.check
val validate_bound : min:t Base__.Maybe_bound.t -> max:t Base__.Maybe_bound.t -> t Base__.Validate.check
module Replace_polymorphic_compare : sig ... end
val comparator : (t, comparator_witness) Core_kernel__Comparator.comparator
module Map : sig ... end
module Set : sig ... end
val hash_fold_t : Ppx_hash_lib.Std.Hash.state -> t -> Ppx_hash_lib.Std.Hash.state
val hash : t -> Ppx_hash_lib.Std.Hash.hash_value
val hashable : t Core_kernel__.Hashtbl.Hashable.t
module Table : sig ... end
module Hash_set : sig ... end
module Hash_queue : sig ... end
type info = string * [ `Ver of string ] * string option
val version : string
val size_in_bytes : ?ver:string -> ?fmt:string -> t -> int
val of_bytes : ?ver:string -> ?fmt:string -> Regular.Std.bytes -> t
val to_bytes : ?ver:string -> ?fmt:string -> t -> Regular.Std.bytes
val blit_to_bytes : ?ver:string -> ?fmt:string -> Regular.Std.bytes -> t -> int -> unit
val of_bigstring : ?ver:string -> ?fmt:string -> Core_kernel.bigstring -> t
val to_bigstring : ?ver:string -> ?fmt:string -> t -> Core_kernel.bigstring
val blit_to_bigstring : ?ver:string -> ?fmt:string -> Core_kernel.bigstring -> t -> int -> unit
module Io : sig ... end
module Cache : sig ... end
val add_reader : ?desc:string -> ver:string -> string -> t Regular.Std.reader -> unit
val add_writer : ?desc:string -> ver:string -> string -> t Regular.Std.writer -> unit
val available_readers : unit -> info list
val default_reader : unit -> info
val set_default_reader : ?ver:string -> string -> unit
val with_reader : ?ver:string -> string -> (unit -> 'a) -> 'a
val available_writers : unit -> info list
val default_writer : unit -> info
val set_default_writer : ?ver:string -> string -> unit
val with_writer : ?ver:string -> string -> (unit -> 'a) -> 'a
val default_printer : unit -> info option
val set_default_printer : ?ver:string -> string -> unit
val with_printer : ?ver:string -> string -> (unit -> 'a) -> 'a
val find_reader : ?ver:string -> string -> t Regular.Std.reader option
val find_writer : ?ver:string -> string -> t Regular.Std.writer option
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct