package bap-std

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

Basic block.

Logically block consists of a set of phi nodes, a sequence of definitions and a sequence of out-coming edges, aka jumps. A colloquial term for this three entities is a block element.

The order of Phi-nodes can be specified in any order, as they execute simultaneously . Definitions are stored in the order of execution. Jumps are specified in the order in which they should be taken, i.e., jmp_n is taken only after jmp_n-1 and if and only if the latter was not taken. For example, if block ends with N jumps, where each n-th jump have destination named t_n and condition c_n then it would have the semantics as per the following OCaml program:

            if c_1 then jump t_1 else
            if c_2 then jump t_2 else
            if c_N then jump t_N else
            stop
type t = blk term
type elt = [
  1. | `Def of def term
  2. | `Phi of phi term
  3. | `Jmp of jmp term
]

Union type for all element types

val create : ?tid:tid -> unit -> t

create () creates a new empty block.

val lift : cfg -> block -> blk term list

lift block takes a basic block of assembly instructions and lifts it to a list of blk terms. The first term in the list is the entry.

val from_insn : insn -> blk term list

from_insn insn creates an IR representation of a single machine instruction insn.

val split_while : t -> f:(def term -> bool) -> t * t

split_while blk ~f splits blk into two block: the first block holds all definitions for which f p is true and has the same tid as blk. The second block is freshly created and holds the rest definitions (if any). All successors of the blk become successors of the second block, which becomes the successor of the first block.

Note: if f def is true for all blocks, then the second block will not contain any definitions, i.e., the result would be the same as of split_bot function.

val split_after : t -> def term -> t * t

split_after blk def creates two new blocks, where the first block contains all defintions up to def inclusive, the second contains the rest.

Note: if def is not in a blk then the first block will contain all the defintions, and the second block will be empty.

val split_before : t -> def term -> t * t

split_before blk def is like split_after but def will fall into the second blk

val split_top : t -> t * t

split_top blk returns two blocks, where first block shares the same tid as blk and has all $\Phi$-nodes of blk, but has only one destination, namely the second block. Second block has new tidentity, but inherits all definitions and jumps from the blk.

val split_bot : t -> t * t

split_top blk returns two blocks, where first block shares the same tid as blk, has all $\Phi$-nodes and definitions from blk, but has only one destination, namely the second block. Second block has new tidentity, all jumps from the blk.

val elts : ?rev:bool -> t -> elt seq

elts ~rev blk return all elements of the blk. if rev is false or left unspecified, then elements are returned in the following order: $\Phi$-nodes, defs (in normal order), jmps in the order in which they will be taken. If rev is true, the order will be the following: all jumps in the opposite order, then definitions in the opposite order, and finally $\Phi$-nodes.

val map_exp : ?skip:[ `phi | `def | `jmp ] list -> t -> f:(exp -> exp) -> t

map_exp b ~f applies function f for each expression in block b. By default function f will be applied to all values of type exp, including right hand sides of phi-nodes, definitions, jump conditions and targets. If skip parameter is specified, then terms of corresponding kind will be skipped, i.e., function f will not be applied to them.

val substitute : ?skip:[ `phi | `def | `jmp ] list -> t -> exp -> exp -> t

substitute ?skip blk x y substitutes each occurrence of expression x with expression y in block blk. The substitution is performed deeply. If skip parameter is specified, then terms of corresponding kind will be left untouched.

val map_lhs : ?skip:[ `phi | `def ] list -> t -> f:(var -> var) -> t

map_lhs blk ~f applies f to every left hand side variable in def and phi subterms of blk. If skip parameter is specified, then terms of corresponding kind will be left untouched. E.g., map_lhs ~skip:[`phi] ~f:(substitute vars) will perform a substitution only on definitions (and will ignore phi-nodes)

val find_var : t -> var -> [ `Phi of phi term | `Def of def term ] option

find_var blk var finds a last definition of a variable var in a block blk.

val defines_var : t -> var -> bool

defines_var blk x true if there exists such phi term or def term with left hand side equal to x

val free_vars : t -> Var.Set.t

free_vars blk returns a set of variables that occurs free in block blk. A variable is free, if it occurs unbound in the expression and there is no preceding definition of this variable in a block blk.

val uses_var : t -> var -> bool

uses_var blk x true if variable x is in free_vars blk. If you need to call this function on several variables it is better to compute free_vars explicitly and use Set.mem function.

val occurs : t -> after:tid -> tid -> bool

occurs blk after:x def if def is occurs after definition def in blk.

module Builder : sig ... end

Builder interface.

include Regular.Std.Regular.S with type t := t
val t_of_sexp : Sexplib.Sexp.t -> t
val sexp_of_t : t -> Sexplib.Sexp.t
val bin_t : t Core_kernel.Std.Bin_prot.Type_class.t
val bin_read_t : t Core_kernel.Std.Bin_prot.Read.reader
val __bin_read_t__ : (int -> t) Core_kernel.Std.Bin_prot.Read.reader
val bin_reader_t : t Core_kernel.Std.Bin_prot.Type_class.reader
val bin_size_t : t Core_kernel.Std.Bin_prot.Size.sizer
val bin_write_t : t Core_kernel.Std.Bin_prot.Write.writer
val bin_writer_t : t Core_kernel.Std.Bin_prot.Type_class.writer
val to_string : t -> string
val str : unit -> t -> string
val pps : unit -> t -> string
val ppo : Core_kernel.Std.out_channel -> t -> unit
val pp_seq : Format.formatter -> t Core_kernel.Std.Sequence.t -> unit
val pp : Format.formatter -> 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 Core_kernel.Or_error.t
module Replace_polymorphic_compare : sig ... end
type comparator_witness
val validate_lbound : min:t Core_kernel.Maybe_bound.t -> t Core_kernel.Validate.check
val validate_ubound : max:t Core_kernel.Maybe_bound.t -> t Core_kernel.Validate.check
val validate_bound : min:t Core_kernel.Maybe_bound.t -> max:t Core_kernel.Maybe_bound.t -> t Core_kernel.Validate.check
val comparator : (t, comparator_witness) Core_kernel.Comparator.comparator
module Map : sig ... end
module Set : sig ... end
val hash : t -> int
val hashable : t Core_kernel.Std.Hashable.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.Std.bigstring -> t
val to_bigstring : ?ver:string -> ?fmt:string -> t -> Core_kernel.Std.bigstring
val blit_to_bigstring : ?ver:string -> ?fmt:string -> Core_kernel.Std.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