Main Page | Class List | File List | Class Members | File Members

node.c File Reference

#include "tarski.h"

Go to the source code of this file.

Functions

Fnode * new_node (Operator_t type, Fnode *lchild, Fnode *rchild)
 Create a new node of a give type with left and right children as specified.
Fnode * new_node_raw (Operator_t type, Fnode *lchild, Fnode *rchild)
 Allocate a new node with params.
char * string_register (char *aString)
 Register a new string with the global database of string.
Fnode * node_register (Fnode *aNode)
 Test if a node with aNode's type, left and right children exists in the global database of nodes.
int node_cmp (Fnode *aNode, Fnode *bNode)
 Straightforward compare function for Formulas.
int node_hash (Fnode *aNode, int modulus)
 Straightforward hash function for formulas.
Fnode * node_dup (Net_t *net, Fnode *formula, char *suf, st_table *processedTable)
 Duplicate a node and all its TFI, with prefix pre attached to each variable name from the original formulas names.
int node_test_is_boolean (Fnode *A)
 Test if a node is a Boolean.
int node_test_is_scalar (Fnode *A)
 Test if a node is a scalar.
F TRUE ()
 Returns the Boolean TRUE node.
F FALSE ()
 Returns the Boolean FALSE node.
F si (char *name)
 Returns a scaler PI node with given name.
F bi (char *name)
 Returns a Boolean PI node with given name.
F sr (char *name)
 Returns a scaler reg node with given name.
F br (char *name)
 Returns a Boolean Reg node with given name.
F sc (char *name)
 Returns a scalar constant with given name.
F bc (char *name)
 Returns a boolean constant with given name.
F uif2 (char *name, F arg1, F arg2)
 Return a UIF of given name, takes 2 args.
F uir3 (char *name, F arg1, F arg2, F arg3)
 Return a relation of given name, takes 3 args.
F uif3 (char *name, F arg1, F arg2, F arg3)
 Return a UIF of given name, takes 3 args.
F uif (char *name, F arg)
 Return a UIF of given name, arg.
F assign (char *name, F arg)
 Create an assignment node.
F mux (F c, F D1, F D0)
 Create a mux node, first arg is cond, second is if, third is else.
int Node_HasLeftChildNode (Fnode *node)
 Check if a node has a left node; use for avoiding valgrind warnings.
int Node_HasRightChildNode (Fnode *node)
 Check if a node has a right node; use for avoiding valgrind warnings.
Fnode * cons (Fnode *a, Fnode *b)
 Lisp-style cons function.
Fnode * car (Fnode *a)
 List-style car function.
Fnode * cdr (Fnode *a)
 List-style cdr function.
F list (F startNode,...)
 Create a list from the arguments.
int listlength (F aList)
 Return the length of a list.
F ri (char *name, F restrictedList)
 Create a new scalar input whose range is restricted to the set of scalar constants in the list provided.
F restrict (F aNode, F restrictedList)
 Take a scalar node and restrict it to the range provided in the list given.
Fnode * nn (Operator_t a, Fnode *b, Fnode *c)
 Creates a new node with less typing.
Fnode * rn (Fnode *aNode)
 Create/return a new node with less typing.
char * rs (char *aString)
 Create/return a new string with less typing.
Fnode * Mux_ThenInput (Fnode *aNode)
 Get the then input to a mux.
Fnode * Mux_ElseInput (Fnode *aNode)
 Get the else input.
Fnode * Reg_InitFunc (Fnode *node)
 Get the init input for a reg.
Fnode * Reg_NsFunc (Fnode *node)
 Get the NS input for a reg.
Fnode * Func_FirstArg (Fnode *node)
 Get the First Argument of a Function.
Fnode * Func_SecondArg (Fnode *node)
 Get the Second Argument of a Function.
Fnode * Func_ThirdArg (Fnode *node)
 Get the Third Argument of a Function.
Fnode * Func_NextArg (Fnode *func_node, Fnode *rchild_node)
 Iterative Function to get the Next Argument.
st_table * nodeGetSupport (F aNode)
 Get support for a node - everything down to PIs and Regs.
void nodeGetSupportRecur (F aNode, st_table *result, st_table *processedTable)
 Function to get support for a node, proceeds recursively.
void reg (F aReg, F nextState, F initState)
 Shorthand for setting up the next state and initial state functions for a node.
Fnode * node_GetUnique (Fnode *aNode)
 Return the unique node from the unique node table.
void NodeAssignRegister (F reg, F init_state, F next_state)
 Sets up the initial and next state functions of a register.

Variables

F Fnil
st_table * nodeHash = ( st_table * ) 0
st_table * stringHash = ( st_table * ) 0
char * typeString []

Function Documentation

F assign (  char *  name,
F  arg
) 
 

Create an assignment node.

Prob not ever needed, since the need for assigns seems to be an artefact of uclid.

Definition at line 863 of file node.c.

References Assign_c, new_node(), F::raw, and rs().

F bc (  char *  name  ) 
 

Returns a boolean constant with given name.

Tricky - need this to be a node that holds its value, but its value can be arbitrary. Implemented via some logic. Different from sc which creates a single node with that constant explicitly defined by the name field.

Definition at line 757 of file node.c.

References bi(), br(), and reg().

F bi (  char *  name  ) 
 

Returns a Boolean PI node with given name.

Definition at line 643 of file node.c.

References BooleanPI_c, nil, nn(), F::raw, and rs().

Referenced by bc(), build_dlx_uclid_impl(), and build_dlx_uclid_superscalar().

F br (  char *  name  ) 
 

Returns a Boolean Reg node with given name.

Need to tack on the init-ns list (e.g., with <<)

Definition at line 716 of file node.c.

References BooleanReg_c, nil, nn(), F::raw, and rs().

Referenced by bc(), build_dlx_uclid_compare(), build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), build_double_instr(), build_fold_unfold_wrapper(), and build_single_instr().

Fnode* car (  Fnode *  a  ) 
 

List-style car function.

Definition at line 981 of file node.c.

References Fnode::lchild.

Fnode* cdr (  Fnode *  a  ) 
 

List-style cdr function.

Definition at line 994 of file node.c.

References Fnode::rchild.

Fnode* cons (  Fnode *  a,
Fnode *  b
) 
 

Lisp-style cons function.

Definition at line 962 of file node.c.

References Fnode::lchild, Fnode::rchild, and Fnode::type.

F FALSE (   ) 
 

Returns the Boolean FALSE node.

Definition at line 609 of file node.c.

References FALSE_c, nil, nn(), and F::raw.

Referenced by build_dlx_uclid_compare(), build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), build_double_instr(), build_fold_unfold_wrapper(), and build_single_instr().

Fnode* Func_FirstArg (  Fnode *  node  ) 
 

Get the First Argument of a Function.

Definition at line 1260 of file node.c.

References Func_c, Fnode::rchild, Fnode::type, and UnaryFunc_c.

Referenced by Node_PrintVHDL(), and ReplaceWritewithRead().

Fnode* Func_NextArg (  Fnode *  func_node,
Fnode *  rchild_node
) 
 

Iterative Function to get the Next Argument.

Definition at line 1317 of file node.c.

References Func_c, Fnode::lchild, nil, Fnode::type, and UnaryFunc_c.

Fnode* Func_SecondArg (  Fnode *  node  ) 
 

Get the Second Argument of a Function.

Definition at line 1275 of file node.c.

References Func_c, Fnode::rchild, and Fnode::type.

Referenced by ReplaceWritewithRead().

Fnode* Func_ThirdArg (  Fnode *  node  ) 
 

Get the Third Argument of a Function.

Definition at line 1296 of file node.c.

References Func_c, Fnode::rchild, and Fnode::type.

F list (  F  startNode,
  ...
) 
 

Create a list from the arguments.

Currently checks to make sure all arguments are scalars; this may be overly conservative for some applications.

Definition at line 1011 of file node.c.

References Fnil, List_c, new_node(), and F::raw.

Referenced by build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), uif(), uif2(), and uif3().

int listlength (  F  aList  ) 
 

Return the length of a list.

Definition at line 1047 of file node.c.

References F::raw, F::rchild(), and F::type().

F mux (  F  c,
F  D1,
F  D0
) 
 

Create a mux node, first arg is cond, second is if, third is else.

Definition at line 883 of file node.c.

References Mux_c, new_node(), and F::raw.

Referenced by build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), build_double_instr(), build_fold_unfold_wrapper(), build_single_instr(), restrict(), and ri().

Fnode* Mux_ElseInput (  Fnode *  aNode  ) 
 

Get the else input.

Definition at line 1215 of file node.c.

References Mux_c, Fnode::rchild, and Fnode::type.

Referenced by Net_CheckBurchFeasibility(), Net_ConstantPropagation(), and Node_PrintVHDL().

Fnode* Mux_ThenInput (  Fnode *  aNode  ) 
 

Get the then input to a mux.

Definition at line 1200 of file node.c.

References Fnode::lchild, Mux_c, Fnode::rchild, and Fnode::type.

Referenced by Net_CheckBurchFeasibility(), Net_ConstantPropagation(), and Node_PrintVHDL().

Fnode* new_node (  Operator_t  type,
Fnode *  lchild,
Fnode *  rchild
) 
 

Create a new node of a give type with left and right children as specified.

Need to take care that we don't created different nodes for single variable formulas repeatedly. This is what the call to node_register is for. lchild and rchild must be legal nodes, or a string (for lchild) or nil.

Definition at line 78 of file node.c.

References new_node_raw(), and node_register().

Referenced by assign(), list(), mux(), Net_DoBryantReduction(), nn(), uif(), uif2(), and uif3().

Fnode* new_node_raw (  Operator_t  type,
Fnode *  lchild,
Fnode *  rchild
) 
 

Allocate a new node with params.

Definition at line 99 of file node.c.

References Fnode::lchild, Fnode::rchild, and Fnode::type.

Referenced by AddReadatEnd(), Net_ConstantPropagation(), new_node(), Fnode::operator &(), Fnode::operator!(), Fnode::operator%(), Fnode::operator==(), and Fnode::operator|().

Fnode* nn (  Operator_t  a,
Fnode *  b,
Fnode *  c
) 
 

Creates a new node with less typing.

See also:
new_node()

Definition at line 1156 of file node.c.

References new_node().

Referenced by bi(), br(), FALSE(), sc(), si(), sr(), and TRUE().

int node_cmp (  Fnode *  aNode,
Fnode *  bNode
) 
 

Straightforward compare function for Formulas.

Not complete, but assuming children are reasonably canonical, the check is reasonable, and covers the impt case, namely PIs. Note that st expects -1, 0, +1, based on whether one node is less, equal or greater.

Definition at line 229 of file node.c.

References Fnode::lchild, Fnode::rchild, and Fnode::type.

Referenced by AddReadatEnd(), cube::cube(), Net_ConstrainInput(), Net_CreateFromFormula(), Net_CreateFromFormulaArray(), Net_DoBryantReduction(), node_register(), nodeComputeBdd(), nodeGetSupport(), and ReplaceWritewithRead().

Fnode* node_dup (  Net_t *  net,
Fnode *  formula,
char *  suf,
st_table *  processedTable
) 
 

Duplicate a node and all its TFI, with prefix pre attached to each variable name from the original formulas names.

Definition at line 284 of file node.c.

References Net_t.

Referenced by node_array_tfe().

Fnode* node_GetUnique (  Fnode *  aNode  ) 
 

Return the unique node from the unique node table.

Definition at line 1424 of file node.c.

References nodeHash.

Referenced by Net_ConstantPropagation().

int node_hash (  Fnode *  aNode,
int  modulus
) 
 

Straightforward hash function for formulas.

Could be heavily optimized, but formula manipulation is unlikely to be on the critical path.

Definition at line 264 of file node.c.

References Fnode::lchild, Fnode::rchild, and Fnode::type.

Referenced by AddReadatEnd(), cube::cube(), Net_ConstrainInput(), Net_CreateFromFormula(), Net_CreateFromFormulaArray(), Net_DoBryantReduction(), node_register(), nodeComputeBdd(), nodeGetSupport(), and ReplaceWritewithRead().

int Node_HasLeftChildNode (  Fnode *  node  ) 
 

Check if a node has a left node; use for avoiding valgrind warnings.

Definition at line 904 of file node.c.

References Fnode::type.

Referenced by Net_PopulateFields().

int Node_HasRightChildNode (  Fnode *  node  ) 
 

Check if a node has a right node; use for avoiding valgrind warnings.

Definition at line 931 of file node.c.

References Fnode::type.

Referenced by Net_PopulateFields().

Fnode* node_register (  Fnode *  aNode  ) 
 

Test if a node with aNode's type, left and right children exists in the global database of nodes.

If so, free node, and return representative. Otherwise, dup the node, insert it. aNode is always freed!

Definition at line 155 of file node.c.

References Fnode::lchild, node_cmp(), node_hash(), nodeHash, Fnode::rchild, and Fnode::type.

Referenced by new_node(), and rn().

int node_test_is_boolean (  Fnode *  A  ) 
 

Test if a node is a Boolean.

Definition at line 544 of file node.c.

References Fnode::type.

Referenced by nodeComputeBdd(), nodeGetSupportRecur(), Fnode::operator &(), Fnode::operator!(), Fnode::operator%(), F::operator()(), Fnode::operator==(), Fnode::operator^(), and Fnode::operator|().

int node_test_is_scalar (  Fnode *  A  ) 
 

Test if a node is a scalar.

Definition at line 571 of file node.c.

References Fnode::type.

Referenced by Fnode::operator%(), and Fnode::operator==().

void NodeAssignRegister (  F  reg,
F  init_state,
F  next_state
) 
 

Sets up the initial and next state functions of a register.

Definition at line 1441 of file node.c.

References reg().

st_table* nodeGetSupport (  F  aNode  ) 
 

Get support for a node - everything down to PIs and Regs.

Definition at line 1338 of file node.c.

References node_cmp(), node_hash(), and nodeGetSupportRecur().

Referenced by test_bdd().

void nodeGetSupportRecur (  F  aNode,
st_table *  result,
st_table *  processedTable
) 
 

Function to get support for a node, proceeds recursively.

Needs more thought on how to handle scalar ops, but for now focus just on boolean case.

See also:
nodeGetSupport()

Definition at line 1362 of file node.c.

References F::lchild(), node_test_is_boolean(), Operator_t, F::raw, F::rchild(), and F::type().

Referenced by nodeGetSupport().

void reg (  F  aReg,
F  nextState,
F  initState
) 
 

Shorthand for setting up the next state and initial state functions for a node.

Definition at line 1407 of file node.c.

Referenced by bc(), and NodeAssignRegister().

Fnode* Reg_InitFunc (  Fnode *  node  ) 
 

Get the init input for a reg.

Definition at line 1230 of file node.c.

References BooleanReg_c, Fnode::rchild, ScalarReg_c, and Fnode::type.

Referenced by Net_CheckBurchFeasibility(), Net_CollectMuxes(), and Node_PrintVHDL().

Fnode* Reg_NsFunc (  Fnode *  node  ) 
 

Get the NS input for a reg.

Definition at line 1245 of file node.c.

References BooleanReg_c, Fnode::rchild, ScalarReg_c, and Fnode::type.

Referenced by Net_CheckBurchFeasibility(), Net_CollectMuxes(), and Node_PrintVHDL().

F restrict (  F  aNode,
F  restrictedList
) 
 

Take a scalar node and restrict it to the range provided in the list given.

We see the need for this e.g. in the 

    	dlx example from uclid, where 
    	next\fdType\ := itype(next\[fdInstr\]);
    	and fdInstr is given by
    	  (  Fetch Stage *)
     init\fdInstr\ := fdi0;    (  initially arbitrary *)
     next\fdInstr\ := case
       stall: fdInstr;         (  Stalling *)
       default: imem(pPC);     (  Read from instruction memory *)
     esac;

Definition at line 1121 of file node.c.

References F::lchild(), mux(), F::raw, F::rchild(), and F::type().

Referenced by build_dlx_uclid_impl(), build_dlx_uclid_spec(), and build_dlx_uclid_superscalar().

F ri (  char *  name,
F  restrictedList
) 
 

Create a new scalar input whose range is restricted to the set of scalar constants in the list provided.

Definition at line 1070 of file node.c.

References F::lchild(), mux(), F::raw, F::rchild(), si(), and F::type().

Referenced by build_dlx_uclid_impl(), and build_dlx_uclid_superscalar().

Fnode* rn (  Fnode *  aNode  ) 
 

Create/return a new node with less typing.

See also:
register_node()

Definition at line 1172 of file node.c.

References node_register().

Referenced by Fnode::operator &(), Fnode::operator!(), Fnode::operator%(), Fnode::operator==(), and Fnode::operator|().

char* rs (  char *  aString  ) 
 

Create/return a new string with less typing.

See also:
register_string()

Definition at line 1186 of file node.c.

References string_register().

Referenced by assign(), bi(), br(), sc(), si(), sr(), uif(), uif2(), and uif3().

F sc (  char *  name  ) 
 

Returns a scalar constant with given name.

Definition at line 735 of file node.c.

References nil, nn(), F::raw, rs(), and ScalarConst_c.

Referenced by build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), build_double_instr(), build_single_instr(), and uir3().

F si (  char *  name  ) 
 

Returns a scaler PI node with given name.

Definition at line 624 of file node.c.

References nil, nn(), F::raw, rs(), and ScalarPI_c.

Referenced by build_dlx_uclid_compare(), build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), build_double_instr(), build_fold_unfold_wrapper(), build_single_instr(), Net_ReplaceWritewithRead(), and ri().

F sr (  char *  name  ) 
 

Returns a scaler reg node with given name.

Need to add the init-NS node list later (e.g., using <<)

Definition at line 696 of file node.c.

References nil, nn(), F::raw, rs(), and ScalarReg_c.

Referenced by build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), build_double_instr(), build_fold_unfold_wrapper(), and build_single_instr().

char* string_register (  char *  aString  ) 
 

Register a new string with the global database of string.

Takes a char , returns a pointer to that string in the global database (stringHash). Does not free the string passed in. Create a duplicate the first time a string is added.

Definition at line 123 of file node.c.

References stringHash.

Referenced by rs().

F TRUE (   ) 
 

Returns the Boolean TRUE node.

Definition at line 594 of file node.c.

References nil, nn(), F::raw, and TRUE_c.

Referenced by build_dlx_uclid_compare(), build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), build_double_instr(), and build_single_instr().

F uif (  char *  name,
F  arg
) 
 

Return a UIF of given name, arg.

Definition at line 842 of file node.c.

References Fnil, Func_c, list(), new_node(), F::raw, and rs().

Referenced by build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), build_double_instr(), and build_single_instr().

F uif2 (  char *  name,
F  arg1,
F  arg2
) 
 

Return a UIF of given name, takes 2 args.

Definition at line 779 of file node.c.

References Fnil, Func_c, list(), new_node(), F::raw, and rs().

Referenced by build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), build_double_instr(), build_fold_unfold_wrapper(), and build_single_instr().

F uif3 (  char *  name,
F  arg1,
F  arg2,
F  arg3
) 
 

Return a UIF of given name, takes 3 args.

Definition at line 820 of file node.c.

References Fnil, Func_c, list(), new_node(), F::raw, and rs().

Referenced by build_dlx_uclid_impl(), build_dlx_uclid_spec(), build_dlx_uclid_superscalar(), build_double_instr(), build_single_instr(), and uir3().

F uir3 (  char *  name,
F  arg1,
F  arg2,
F  arg3
) 
 

Return a relation of given name, takes 3 args.

Definition at line 799 of file node.c.

References sc(), and uif3().

Referenced by build_dlx_uclid_impl(), build_dlx_uclid_spec(), and build_dlx_uclid_superscalar().

Variable Documentation

F Fnil
 

AutomaticEnd**************************************************************

Definition at line 30 of file node.c.

Referenced by list(), uif(), uif2(), and uif3().

st_table* nodeHash = ( st_table * ) 0
 

Definition at line 31 of file node.c.

Referenced by node_GetUnique(), and node_register().

st_table* stringHash = ( st_table * ) 0
 

Definition at line 32 of file node.c.

Referenced by string_register().

char* typeString[]
 

Initial value:

 {
  "Undef",
  "LIST", 
  "PAIR", 
  "SI", 
  "BI", 
  "SR", 
  "BR", 
  "IntSV", 
  "IntBV", 
  "Assign",
  "And",
  "Or",
  "Not",
  "Iff",
  "TRUE",
  "FALSE",
  "Mux",
  "EQ", 
  "UIF1", 
  "UIF", 
  "Reln", 
  "Const", 
}

Definition at line 36 of file node.c.

Generated on Thu Oct 11 11:47:29 2007 for Tarski by  doxygen 1.3.9.1