# HG changeset patch
# User Thinker K.F. Li <thinker@codemud.net>
# Date 1284090223 -28800
# Node ID cf0d2482762455eea80ab900fcf600cf170a83be
# Parent  566b62a49462efc89ee873d6d3cc15d11bcf8537
Tree traveling and manipulation functions

diff -r 566b62a49462 -r cf0d24827624 src/Makefile
--- a/src/Makefile	Thu Sep 09 18:23:50 2010 +0800
+++ b/src/Makefile	Fri Sep 10 11:43:43 2010 +0800
@@ -9,11 +9,11 @@
 cospy.so: $(PLUGIN_OBJECT_FILES)
 	$(GCC) -shared $^ -o $@
 
-test:	cospy.so
-	$(GCC) -fplugin=`pwd`/cospy.so $(CFLAGS) -c test.c
+test:	cospy.so test.c
+	$(GCC) -fplugin=`pwd`/cospy.so $(CFLAGS) -o test-bin test.c
 
 clean:
-	for i in *~ *.o *.so; do \
+	for i in *~ *.o *.so test-bin; do \
 		if [ -e $$i ]; then \
 			echo "delete $$i"; \
 			rm -f $$i; \
diff -r 566b62a49462 -r cf0d24827624 src/cospy.c
--- a/src/cospy.c	Thu Sep 09 18:23:50 2010 +0800
+++ b/src/cospy.c	Fri Sep 10 11:43:43 2010 +0800
@@ -110,15 +110,29 @@
     }
 }
 
+/*! \defgroup tree_travel Tree traveling and manipulation tools.
+ * @{
+ */
+typedef struct _stmt_link {
+    tree stmt;
+    struct _stmt_link *parent;
+} stmt_link;
+
 /*! \brief Trival tree of GIMPLE code with a callback.
  *
  * walk_code_free() would call the function given by cb with
  * expression and data as arguments.  The cb is called only for the
  * node with tree code value given by accept_code.
+ *
+ * \param accept_code is tree code of nodes that calling cb for or -1
+ *		to call cb for every node.
+ * \param visit is true for traveling and false for cleaning.
  */
 static void
-walk_code_tree(tree expr, int accept_code,
-	  void (*cb)(tree, void *), void *data) {
+_walk_code_tree(tree expr, int accept_code,
+		void (*cb)(tree, void *, stmt_link *), void *data,
+		stmt_link *parent, bool visit) {
+    stmt_link me = {expr, parent};
     int code;
     tree child;
     int i, sz;
@@ -127,10 +141,15 @@
     if(expr == NULL)
 	return;
     
+    TREE_VISITED(expr) = visit;
+    
+    if(TREE_VISITED(expr))
+	return;
+
     code = TREE_CODE(expr);
 
-    if(accept_code && code == accept_code)
-	cb(expr, data);
+    if(cb && (accept_code == -1 || code == accept_code))
+	cb(expr, data, parent);
 
     switch(code) {
     case ERROR_MARK:		/* 0 */
@@ -194,14 +213,14 @@
 	sz = TREE_OPERAND_LENGTH(expr);
 	for(i = 0; i < sz; i++) {
 	    child = TREE_OPERAND(expr, i);
-	    walk_code_tree(child, accept_code, cb, data);
+	    _walk_code_tree(child, accept_code, cb, data, &me, visit);
 	}
 	break;
 	
     case BIND_EXPR:
 	/* See BIND_EXPR in tree.def */
 	child = BIND_EXPR_BODY(expr);
-	walk_code_tree(child, accept_code, cb, data);
+	_walk_code_tree(child, accept_code, cb, data, &me, visit);
 	break;
 	
     case CALL_EXPR:
@@ -295,7 +314,7 @@
 	sz = TREE_OPERAND_LENGTH(expr);
 	for(i = 0; i < sz; i++) {
 	    child = TREE_OPERAND(expr, i);
-	    walk_code_tree(child, accept_code, cb, data);
+	    _walk_code_tree(child, accept_code, cb, data, &me, visit);
 	}
 	break;
 	
@@ -305,7 +324,7 @@
 	    !tsi_end_p(stmt_itr);
 	    tsi_next(&stmt_itr)) {
 	    child = tsi_stmt(stmt_itr);
-	    walk_code_tree(child, accept_code, cb, data);
+	    _walk_code_tree(child, accept_code, cb, data, &me, visit);
 	}
 	break;
 	
@@ -352,24 +371,92 @@
 	sz = TREE_OPERAND_LENGTH(expr);
 	for(i = 0; i < sz; i++) {
 	    child = TREE_OPERAND(expr, i);
-	    walk_code_tree(child, accept_code, cb, data);
+	    _walk_code_tree(child, accept_code, cb, data, &me, visit);
 	}
 	break;
     }
 }
 
 static void
-found_call(tree expr, void *data) {
+walk_code_tree(tree expr, int accept_code,
+	       void (*cb)(tree, void *, stmt_link *), void *data) {
+    _walk_code_tree(expr, accept_code, cb, data, NULL, true);
+    
+    /* cleaning visited flag for every node */
+    _walk_code_tree(expr, -1, NULL, NULL, NULL, false);
+}
+
+static void
+tree_insert_before_stmt(tree new_node, tree old_node, tree parent) {
+    tree_stmt_iterator itr;
+    tree visit;
+
+    for(itr = tsi_start(parent); !tsi_end_p(itr); tsi_next(&itr)) {
+	visit = tsi_stmt(itr);
+	if(visit == old_node) {
+	    tsi_link_before(&itr, new_node, TSI_SAME_STMT);
+	    TREE_VISITED(new_node) = true;
+	    break;
+	}
+    }
+}
+
+static void
+tree_insert_before_arg(tree new_node, tree old_node, tree parent) {
+    tree visit;
+    tree compound;
+    int len;
+    int i;
+
+    len = TREE_OPERAND_LENGTH(parent);
+    for(i = 0; i < len; i++) {
+	visit = TREE_OPERAND(parent, i);
+	if(visit == old_node) {
+	    compound = build2(COMPOUND_EXPR, TREE_TYPE(old_node),
+			      new_node, old_node);
+	    TREE_VISITED(compound) = true;
+	    TREE_OPERAND(parent, i) = compound;
+	    break;
+	}
+    }
+}
+
+/*! \brief Insert a new node before an old node under a parent.
+ *
+ * \param new_node is the node to be inserted.
+ * \param old_node is the node where the new one being inserted before.
+ * \param parent is the parent node of old_node.
+ */
+static void
+tree_insert_before(tree new_node, tree old_node, tree parent) {
+    int pcode;
+
+    pcode = TREE_CODE(parent);
+    if(pcode == STATEMENT_LIST)
+	tree_insert_before_stmt(new_node, old_node, parent);
+    else
+	tree_insert_before_arg(new_node, old_node, parent);
+}
+
+/* @} */
+
+/*! \brief Called for found CALL_EXPR in a tree when trevaling.
+ */
+static void
+found_call(tree expr, void *data, stmt_link *parent_link) {
     tree addr;
     tree fn, fn_name;
+    tree parent = parent_link->stmt;
 
     addr = TREE_OPERAND(expr, 1);
     fn = TREE_OPERAND(addr, 0);
     fn_name = DECL_NAME(fn);
     
-    printf("    CALL %s:%s:%d\n", IDENTIFIER_POINTER(fn_name),
+    printf("    CALL %s:%s:%d from a %d\n",
+	   IDENTIFIER_POINTER(fn_name),
 	   EXPR_FILENAME(expr),
-	   EXPR_LINENO(expr));
+	   EXPR_LINENO(expr),
+	   TREE_CODE(parent));
 }
 
 /*! \brief Find all call expression in a code block.