10.2 Case Study 3

10.2 Case Study 3

10.2.1 The Program

This example presents an algorithm that matches partial or whole expression trees against a database of idiomatic expressions. The original design for this algorithm can be found in the article “Recognition and Selection of Idioms for Code Optimization” by Lawrence Snyder [Sn82]. The implementation is written in C++.

Snyder defines an idiom as “a construction used by programmers for a logically primitive operation for which no language primitive exists.” Twenty years ago, when Snyder wrote his paper, APL was the only language that was an obvious candidate for the approach to optimization he proposed. Other researchers had collected lists of idioms that commonly occurred in APL applications. Some APL language processors performed extremely limited recognition of a couple of these idioms.

Snyder proposes that an APL language processor (compiler or interpreter) should recognize idioms and evaluate the benefits of replacing them with library calls. He provides an algorithm that can recognize multiple idioms in a single expression and select which idioms should be replaced to achieve maximum benefit. Snyder’s recognition algorithm works in O(n log n) time, and the selection algorithm works in O(n) time.

The chief benefit of recognizing a complex expression and replacing it with a call to a runtime library procedure came from eliminating memory allocations and type conversions that were done “under the covers.” Every operation in an APL interpreter causes the allocation of storage for results. Since APL works best on arrays, large blocks of memory are continually being allocated and freed. In addition, there are frequent conversions between different data types (integer, real, etc.) and special representations of certain data structures (arithmetic progressions, sets, etc.).

While APL is not used much anymore, other languages have become popular, which can have similar characteristics. Both C++ and Java can cause frequent memory allocations and conversions to occur “behind the programmer’s back.” Thus, while Snyder’s algorithm is interesting on its own, it may also be useful to adapt to languages popular today.

The following technical details highlight Snyder’s approach. Idioms can overlap, and the algorithm handles this correctly. Variable operands of idioms are “free variables.” They can match constants, variables, or expressions. The algorithm handles these cases. Constants required for the correctness of an idiom are treated as functions with no arguments. Expression trees are assumed to be binary; however, the code would easily extend to trees having nodes of arbitrary degree.

The algorithm performs two passes over an expression tree. The first pass visits the nodes of the tree bottom-up and marks all the nodes with integers. The second pass visits the nodes top-down and performs the recognition and selection. The first pass assigns unique numbers to the roots of all identical subtrees.

Prior to the numbering phase, the expression is preprocessed into a form that makes rapid handling possible. All the nodes in the tree have been placed on linked lists such that nodes that have the same height are on the same list. Nodes at height 0 (i.e., the leaves) have been given integer codes that identify each distinct operand uniquely. Entries into a symbol table or constant table for these operands would be available and suitable for this purpose.

The constructor for the Expr class reads in the expression and puts it into a suitable binary form. Each node in the expression tree is represented by an instance of the Tree class.

The numbering phase processes all the nodes of the same height together. All nodes with the same height are sorted first on the assigned code of their left descendant, and then similarly on their right descendant, using a bucket sort. The numbering algorithm is found in the file number.c.

The database of idioms is stored in a table. Each entry is represented in prefix notation, without parentheses. The first and subsequent occurrences of an operand are represented by distinct codes. The constructor for the IdiomTable class reads in the table and puts it into a suitable binary form.

The matching phase performs a depth-first traversal of the expression tree. It performs all matches simultaneously, using a match descriptor to track the progress of a match. The descriptors are represented by instances of the Desc class. The descriptor tracks the initial node of the subtree that is matched and the identifiers of the nodes that are operands of the idiom.

Each time the match function is called on a node of the tree, it initiates descriptors for all idioms that might match the current node. Then it updates the descriptors for all matches in progress. Then it calls itself recursively to process the left and right children of that node. After returning from the recursive call, it determines which idioms matched the node and which to select. The match algorithm is found in the file match.c.

The code for the original program is listed as follows. The original algorithm uses origin-1 array indexing, while C++ uses origin-0 indexing. We tried to work around this issue by padding the arrays with an extra null element at the beginning. While this largely worked, it introduced several bugs, which are discussed in the sequel. The original algorithm also had ambiguous or undefined notation, as well as an inconsistent use of keyword delimiters and indenting to show control flow.

 /* Bucket.h */  #ifndef _Bucket_h_  #define _Bucket_h_  struct _bucket {      int link;      int head;  };  typedef struct _bucket Bucket;  extern int numBuckets;  #endif  ________________________________________________________  /* Select.h */  #ifndef _Select_h_  #define _Select_h_  class Select {  public:      // constructors and destructors      Select();      Select(int);      // accessors      inline int getVertex() { return _vertex; }      inline Select * getNext() { return _next; }      // mutators      inline void setVertex(int x) { _vertex= x; }      inline void setNext(Select * x) { _next= x; }  private:      int _vertex;      Select * _next;  };  #endif  ________________________________________________________  /* Opcode.h */  #ifndef _Opcode_h_  #define _Opcode_h_  extern char ** tagList;  extern int tagCount;  extern int lookupTag(char *);  /*----------------------------------------------------*/  #define NONE -1  #define F_FIRST 1  #define F_plus 1  #define F_minus 2  #define F_times 3  #define F_divide 4  #define F_mod 5  #define F_exp 6  #define F_log 7  #define F_and 8  #define F_or 9  #define F_nand 10  #define F_nor 11  #define F_lt 12  #define F_lteq 13  #define F_gt 14  #define F_gteq 15  #define F_eq 16  #define F_neq 17  #define F_plus_scan 18  #define F_times_scan 19  #define F_and_scan 20  #define F_or_scan 21  #define F_lt_scan 22  #define F_lteq_scan 23  #define F_eq_scan 24  #define F_neq_scan 25  #define F_plus_red 26  #define F_times_red 27  #define F_and_red 28  #define F_or_red 29  #define F_and_eq 30  #define F_plus_times 31  #define F_cprs 32  #define F_xpnd 33  #define F_rev 34  #define F_rot 35  #define F_form 36  #define F_shape 37  #define F_get 38  #define F_iota 39  #define F_ravel 40  #define F_splice 41  #define F_flip 42  #define F_trans 43  #define F_upgr 44  #define F_dngr 45  #define F_rep 46  #define F_value 47  #define F_find 48  #define F_memb 49  #define F_not 50  #define C_int 51  #define C_real 52  #define C_char 53  #define F_LAST 53  #define V_first_1 54  #define V_first_2 55  #define V_first_3 56  #define V_first_4 57  #define V_first_5 58  #define V_dup_1 59  #define V_dup_2 60  #define V_dup_3 61  #define V_dup_4 62  #define V_dup_5 63  #define DUP_FIRST 59  #define DUP_LAST 63  #define VARB_COUNT 5  #endif  ________________________________________________________  /* Desc.h */  #ifndef _Desc_h_  #define _Desc_h_  class Desc {  public:      // constructors and destructors      Desc();      Desc(int, int, int, int, Select *);      ~Desc();      // accessors      inline int getRow() { return _row; }      inline int getCol() { return _col; }      inline int getVertex() { return _vertex; }      inline int getBenefit() { return _benefit; }      inline Select * getChain() { return _chain; }      inline Desc * getNext() { return _next; }      inline Desc * getPrev() { return _prev; }      // mutators      inline void setRow(int x) { _row= x; }      inline void setCol(int x) { _col= x; }      inline void setVertex(int x) { _vertex= x; }      inline void setBenefit(int x) { _benefit= x; }      inline void setChain(Select * x) { _chain= x; }      inline void setNext(Desc * x) { _next= x; }      inline void setPrev(Desc * x) { _prev= x; }  private:      int _row;      int _col;      int _vertex;      int _benefit;      Select * _chain;      Desc * _next;      Desc * _prev;  };  #endif  ________________________________________________________  /* Tree.h */  #ifndef _Tree_h_  #define _Tree_h_  class Tree {  public:      // constructors and destructors      Tree();      Tree(int, int, int, int, int, char *, int,           Select *);      ~Tree();      // accessors      inline int getLeft() { return _left; }      inline int getRight() { return _right; }      inline int getLink() { return _link; }      inline int getNumber() { return _number; }      inline int getOpType() { return _opType; }      inline char * getOpName() { return _opName; }      inline int getBenefit() { return _benefit; }      inline Select * getSelect() { return _select; }      // mutators      inline void setLeft(int x) { _left= x; }      inline void setRight(int x) { _right= x ; }      inline void setLink(int x) { _link= x; }      inline void setNumber(int x) { _number= x; }      inline void setOpType(int x) { _opType= x; }      inline void setOpName(char *x) { _opName= x; }      inline void setBenefit(int x) { _benefit= x; }      inline void setSelect(Select *x) { _select= x; }  private:      int _left;      int _right;      int _link;      int _number;      int _opType;      char *_opName;      int _benefit;      Select *_select;  };  #endif  ________________________________________________________  /* Expr.h */  #ifndef _Expr_h_  #define _Expr_h_  class Expr {  public:      // constructors and destructors      Expr(char *);      Expr(int, int, Tree *, int *);      ~Expr();      // accessors      inline int getSize() { return _size; }      inline int getDepth() { return _depth; }      inline int getUnique() { return _unique; }      inline Tree * getTree() { return _tree; }      inline int * getHeight() { return _height; }      // mutators      inline void setSize(int x) { _size= x; }      inline void setDepth(int x) { _depth= x; }      inline void setUnique(int x) { _unique= x ; }      inline void setTree(Tree * x) { _tree= x; }      inline void setHeight(int * x) { _height= x; }  private:      int _size;      int _depth;      int _unique;      Tree * _tree;      int * _height;  };  #endif  ________________________________________________________  /* IdiomTable.h */  #ifndef _IdiomTable_h_  #define _IdiomTable_h_  class IdiomTable {  public:      // constructors and destructors      IdiomTable();      IdiomTable(char *);      ~IdiomTable();      // accessors      inline int ** getTable() { return _table; }      inline int getCount() { return _count; }      inline int getSize() { return _size; }      inline int getDepth() { return _depth; }      // mutators      inline void setTable(int **x) { _table= x; }      inline void setCount(int x) { _count= x; }      inline void setSize(int x) { _size= x; }      inline void setDepth(int x) { _depth= x; }      // workers      int idiomPayoff(int,int);      int isOpRepeated(int);      int isOpFunction(int);      int firstOccur(int);  private:      int ** _table;      int _count;      int _size;      int _depth;      int * _payoff;      int lookup(char *);  };  #endif  ________________________________________________________  /* Select.c */  #include "Select.h"  Select::Select() {      Select(0);  }  Select::Select(int vertex) {      _vertex= vertex;      _next= 0;  }  ________________________________________________________  /* Opcode.c */  #include <string.h>  int tagCount= 60;  char * tagList[] = { "NONE",  "F_plus", "F_minus", "F_times", "F_divide", "F_mod",  "F_exp", "F_log", "F_and", "F_or", "F_nand",  "F_nor", "F_lt", "F_lteq", "F_gt", "F_gteq",  "F_eq", "F_neq", "F_plus_scan", "F_times_scan",  "F_and_scan",  "F_or_scan", "F_lt_scan", "F_lteq_scan", "F_eq_scan",  "F_neq_scan", "F_plus_red", "F_times_red", "F_and_red",  "F_or_red", "F_and_eq",  "F_plus_times", "F_cprs", "F_xpnd", "F_rev", "F_rot",  "F_form", "F_shape", "F_get", "F_iota", "F_ravel",  "F_splice", "F_flip", "F_trans", "F_upgr", "F_dngr",  "F_rep", "F_value", "F_find", "F_memb", "F_not",  "C_int", "C_real", "C_char", "V_first_1", "V_first_2",  "V_first_3", "V_dup_1", "V_dup_2", "V_dup_3"  };  int lookupTag(char * token) {      int index= -1;      for ( int i= 0; i < tagCount; ++i ) {          if ( 0 == strcmp(token,tagList[i]) ) {              index= i;              break;          }      }      return index;  }  ________________________________________________________  /* Desc.c */  #include "Select.h"  #include "Desc.h"  Desc::Desc() {      Desc(0,0,0,0,0);  }  Desc::Desc(int vertex, int row, int col, int bene,             Select *chain) {     _vertex= vertex;     _row= row;     _col= col;     _benefit= 0;     _next= 0;     _prev= 0;     _chain= chain;  }  Desc::~Desc() {  }  ________________________________________________________  /* Tree.c */  #include "Select.h"  #include "Tree.h"  #include "Opcode.h"  Tree::Tree() {      Tree(0,0,0,0,0,0,0,0);  }  Tree::Tree( int left, int right, int link, int number,      int opType, char * opName, int benefit,      Select * select ) {      _left= left;      _right= right;      _link= link;      _number= number;      _opType= opType;      _opName= opName;      _benefit= benefit;      _select= select;  }  Tree::~Tree() { }  ________________________________________________________  /* Expr.c */  #include <stdio.h>  #include <stdlib.h>  #include <string.h>  #include "Select.h"  #include "Tree.h"  #include "Expr.h"  #include "Opcode.h"  Expr::Expr(char * fileName) {      int bufSize= 256;      char buffer[256];      char *tokens[128];      FILE * file= fopen(fileName,"r");      if( file == 0 ) {          fprintf(stderr,"Unable to open %s\n",fileName);          fflush(stderr);          exit(1);      }      fscanf(file, "%d\n", &_size);      fscanf(file, "%d\n", &_depth);      fscanf(file, "%d\n\n", &_unique);      _tree= new Tree[_size]; // need to add +1      _height= new int[_depth+1];      int tokenCtr= 0;      fgets(buffer, bufSize, file);      char * token= strtok(buffer, " ");      _height[tokenCtr++]= atoi(token);      while( token= strtok(NULL, " \n") ) {          _height[tokenCtr++]= atoi(token);      }      int row= 0;      tokenCtr= 0;      while ( 0 != fgets(buffer, bufSize, file) ) {          token= strtok(buffer, " ");          tokens[tokenCtr++]= token;          int k=0;          while( token= strtok(NULL, " \n") ) {              tokens[tokenCtr++]= token;          }          _tree[row].setLeft(atoi(tokens[0]));          _tree[row].setRight(atoi(tokens[1]));          _tree[row].setLink(atoi(tokens[2]));          _tree[row].setNumber(atoi(tokens[3]));          _tree[row].setOpType(lookupTag(tokens[4]));          _tree[row].setOpName(tokens[5]);      }      fclose(file);  }  Expr::Expr(int depth, int unique, Tree * tree, int * height)      { }  Expr::~Expr() { }  ________________________________________________________  /* IdiomTable.c */  #include <stdio.h>  #include <string.h>  #include <stdlib.h>  #include "IdiomTable.h"  #include "Opcode.h"  IdiomTable::IdiomTable(char *fileName) {      int bufSize= 256;      char buffer[256];      char * tokens[128];      FILE * file= fopen(fileName,"r");      if ( file == 0 ) {          fprintf(stderr,"Unable to open %s\n",fileName);          fflush(stderr);          exit(1);      }      fscanf(file, "%d\n", &_count);      fscanf(file, "%d\n", &_size);      _table= new (int *)[_count+1];      for ( int i=0; i < _count; ++i ) {          _table[i]= new int[_size+1];      }      _payoff= new int[_count+1];      int tokenCtr= 0;      fgets(buffer, bufSize, file);      char * token= strtok(buffer, " ");      _payoff[tokenCtr++]= atoi(token);      while( token= strtok(NULL, " \n") ) {          _payoff[tokenCtr++]= atoi(token);      }      int j= 0;      while ( 0 != fgets(buffer, bufSize, file) ) {          token= strtok(buffer, " ");          tokens[tokenCtr++]= token;          int k=0;          _table[j][k++]= lookupTag(token);          while( token= strtok(NULL, " \n") ) {              tokens[tokenCtr++]= token;              _table[j][k++]= lookupTag(token);          }          ++j;      }      for( int i=0; i<_count; ++i ) {          for( int j=0; j<_size; ++j ) {              fprintf(stderr,"%d ",_table[i][j]);          }          fprintf(stderr,"\n");      }      fclose(file);  }  int IdiomTable::idiomPayoff(int x, int y) {      return _payoff[x];  }  int IdiomTable::isOpRepeated(int x){      return 0;  }  int IdiomTable::isOpFunction(int x){      if( x >= F_FIRST && x <= F_LAST) {          return 1;      } else {          return 0;      }  }  int IdiomTable::firstOccur(int x){      return 0;  }  ________________________________________________________  /* number.c */  #include <stdio.h>  #include "Select.h"  #include "Tree.h"  #include "Bucket.h"  #include "Expr.h"  void numberTree( Expr * expr ) {      Tree *tree= expr->getTree();      int depth= expr->getDepth();      int * height= expr->getHeight();      int unique= expr->getUnique();      Bucket * bucket1= new Bucket[depth+1];      Bucket * bucket2= new Bucket[depth+1];      int b1, b2, left, right, node, lNum, rNum;      int b1Chain= 0;      int b2Chain= 0;      // for all levels of the tree      for( int i= 1; i <= depth; ++i ) {          // Bucket sort on left descendant          while( height[i] != 0 ) {              // for all nodes in one level              node= height[i];              // save ID of next node to process              height[i]= tree[node].getLink();              // if we have a left descendant get its              // leaf number              left= tree[node].getLeft();              if( left != 0 ) {                  lNum= tree[left].getNumber();                  // if there aren’t any nodes in the                  // chain of buckets yet                  // then initialize the chain                  if( bucket1[lNum].head == 0 ) {                      bucket1[lNum].link= b1Chain;                      b1Chain= lNum;                  }                  // Put node in bucket for nodes having                  // this left son                  tree[node].setLink(bucket1[lNum].head);                  bucket1[lNum].head= node;              }          }          // Bucket sort on right descendant          while( b1Chain != 0 ) {              b1= b1Chain;              b1Chain= bucket1[b1].link;              while( bucket1[b1].head != 0 ) {                  node= bucket1[b1].head;                  // save ID of next node to process                  bucket1[b1].head= tree[node].getLink();                  // if we have a right descendant get                  // its leaf number                  right= tree[node].getRight();                  if( right != 0 ) {                     rNum= tree[right].getNumber();                      // if there aren’t any nodes in                      // the chain of buckets                      // yet then initialize the chain                      if( bucket2[rNum].head == 0 ) {                          bucket2[rNum].link= b2Chain;                          b2Chain= rNum;                      }                      // Put node in bucket for nodes                      // having this right son                      tree[node].setLink(                                 bucket2[rNum].head);                      bucket2[rNum].head= node;                  }              }          }          // Assign unique numbers for each          // non-empty bucket          while( b2Chain != 0 ) {              b2= b2Chain;              b2Chain= bucket2[b2].link;              unique += 1;              while( bucket2[b2].head != 0 ) {                  node= bucket2[b2].head;                  tree[node].setNumber(unique);                  bucket2[b2].head= tree[node].getLink();              }          }      }  }  ________________________________________________________  /* match.c */  #include <stdio.h>  #include <stdlib.h>  #define max(a,b) (((a)>(b))?(a):(b))  #include "Select.h"  #include "Desc.h"  #include "Tree.h"  #include "IdiomTable.h"  #include "Expr.h"  Desc activeHead;  Desc *active;  Desc accumHead;  Desc *accum;  void match(int vertex, Expr *expr, IdiomTable *table) {      Tree * tree= expr->getTree();      int ** idiomTable= table->getTable();      int numIdioms= table->getCount();      int i, row, col, current, bene, best;      Desc suspendHead;      Desc *suspend;      Select selectHead;      Select *select;      Desc *newDesc, *desc;      Select *newSel, *chain, *link;      // descriptors of matches in progress that      // have reached a leaf      suspendHead.setNext(0);      accumHead.setNext(0);      // create match descriptors for all idioms that      // begin with the same op as the first op      // in the expression      for(i= 1; i <= numIdioms; ++i) {          if( idiomTable[i][0] == tree[vertex].                                  getOpType() ) {              newDesc= new Desc(vertex,i,1,0,0);              if( accumHead.getNext() == 0 ) {                  accum= newDesc;                  accumHead.setNext(accum);              } else {                  accum->setNext(newDesc);              }          }      }      // update matches in progress      while( (desc= activeHead.getNext()) != 0 ) {          row= desc->getRow();          col= desc->getCol();          current= desc->getVertex();          bene= desc->getBenefit();          chain= desc->getChain();          // three possible cases: the next token          // in the idiom is          // 1) a function matching the vertex          if( table->isOpFunction(idiomTable[row]                                          [col+1]) ) {              if( idiomTable[row][col+1] == tree[vertex].                                         getOpType() ) {                  // put new descriptor on                  // accumulated list                  newDesc= new Desc(current,row,col+1,                                    bene,chain);                  accum->setNext(newDesc);                  newDesc->setPrev(accum);              }          // 2) a repeated operand matching the vertex          } else if ( table->isOpRepeated(idiomTable[row]                                          [col+1]) ) {              if( tree[vertex].getNumber() ==                  tree[table->firstOccur(vertex)].                                         getNumber() ) {                  // put new descriptor on the                  // suspended list                  newDesc= new Desc(current,row,                                    col+1,bene,chain);                  if( suspendHead.getNext() == 0 ) {                      suspend= newDesc;                      suspendHead.setNext(suspend);                  } else {                      suspend->setNext(newDesc);                  }              }          // 3) the first instance of an operand          } else {              // put vertex at the end of the chain              // for this descriptor              newSel= new Select(vertex);              if( chain == 0 ) {                  chain= newSel;              } else {                  for( link=chain; link->getNext() != 0;                       link=link->getNext())                  { }                  link->setNext(newSel);              }              // put new descriptor on the suspended list              newDesc= new Desc(current,row,col+1,                                bene,chain);              if( suspendHead.getNext() == 0 ) {                  suspend= newDesc;                  suspendHead.setNext(suspend);              } else {                  suspend->setNext(newDesc);              }          }          activeHead.setNext(desc->getNext());          free((char *)desc);      }      activeHead.setNext(accumHead.getNext());      best= 0;      select= new Select(0);      selectHead.setNext(select);      // depth first traversal of descendants      // in expression      if( tree[vertex].getLeft() != 0 ) {          match(tree[vertex].getLeft(), expr, table);          best= tree[tree[vertex].getLeft()].getBenefit();          newSel= new Select(tree[vertex].getLeft());          if( selectHead.getNext() == 0 ) {              select= newSel;              selectHead.setNext(newSel);          } else {              select->setNext(newSel);          }      }      if( tree[vertex].getRight() != 0 ) {          match(tree[vertex].getRight(), expr, table);          best= tree[tree[vertex].getRight()].                                  getBenefit();          newSel= new Select(tree[vertex].getRight());          if( selectHead.getNext() == 0 ) {              select= newSel;              selectHead.setNext(select);          } else {              select->setNext(newSel);          }      }      accum= 0;      accumHead.setNext(accum);      while( (desc= activeHead.getNext()) != 0 ) {          row= desc->getRow();          col= desc->getCol();          bene= desc->getBenefit();          current= desc->getVertex();          chain= desc->getChain();          // was this descriptor initiated by this vertex?          if( current == vertex ) {              // yes, we have matched an idiom              if( best < table->idiomPayoff(vertex,row) +                                bene ) {                  select= new Select(row);                  selectHead.setNext(select);                  select->setNext(chain);              }              best= max(best, table->idiomPayoff(vertex,                                              row)+bene);          } else {              // no              newDesc= new Desc(current,row,col,                                            bene,chain);              if( accumHead.getNext() == 0 ) {                  accum= newDesc;                  accumHead.setNext(accum);              } else {                  accum->setNext(newDesc);              }          }          tree[vertex].setBenefit(best);          tree[vertex].setSelect(select);          activeHead.setNext(accumHead.getNext());          // reactivate suspended descriptors          while( (desc= suspendHead.getNext()) != 0 ) {              // update benefit field and move to              // active list              desc->setBenefit( desc->getBenefit() +                                              best);              if( activeHead.getNext() == 0 ) {                  activeHead.setNext(desc);              } else {                  active->setNext(desc);              }              suspendHead.setNext(desc->getNext());          }          activeHead.setNext(desc->getNext());          free((char *)desc);      }  }  ________________________________________________________  /* main.c */  #include <stdio.h>  #include <stdlib.h>  #include "IdiomTable.h"  #include "Select.h"  #include "Desc.h"  #include "Tree.h"  #include "Opcode.h"  #include "Expr.h"  void numberTree(Expr *);  void match(int, Expr *, IdiomTable *);  int main(int argc, char **argv ) {      Expr * expr= new Expr("test1.txt");      numberTree(expr);  //    IdiomTable * table= new IdiomTable("table.txt");  //    match(1, expr, table );  } 

10.2.2 Bug 1

10.2.2.1 The evidence

The first debugging session began by running the application. The test input and idiom database are shown as follows. The input expression in the first listing should match the first idiom in the database.

 9  6  3  -1 8 6 5 3 2 1  -1 -1 -1 -1 NONE "***"  2 9 0 0 F_cprs ""  3 4 9 0 F_trans ""  0 0 4 1 C_int "(1 1)"  5 0 0 0 F_lt_scan ""  6 7 0 0 F_and_eq ""  0 0 7 2 V_first_1 "M"  8 0 0 0 F_flip ""  0 0 0 2 V_dup_1 "M"  0 0 0 2 V_dup_1 "M"  8  13  -1 5 4 5 7 6 5 5 6  NONE NONE NONE NONE NONE NONE NONE NONE NONE NONE NONE NONE NONE  NONE F_cprs F_trans C_int F_lt_scan F_and_eq V_first_1 F_flip       V_dup_1 V_dup_1  NONE F_rot F_plus_red F_and_scan F_eq C_char V_first_1 V_dup_1  NONE F_cprs F_or F_neq V_first_1 C_char F_neq V_dup_1 F_rot       C_int V_dup_1 V_dup_1  NONE F_get V_first_1 F_upgr F_value F_plus C_int F_shape       V_first_2 F_trans F_find V_dup_2 V_dup_1  NONE F_plus V_first_1 F_plus_red F_and_scan F_not F_and_eq       V_first_2 F_trans V_dup_2  NONE F_times V_first_1 F_trans F_form F_rev F_shape V_dup_1       V_first_2  NONE F_cprs F_eq F_find V_first_1 V_dup_1 F_iota F_shape       V_dup_1 V_dup_1  NONE F_cprs F_ravel F_splice V_first_1 C_int F_ravel F_splice       V_dup_1 F_not V_dup_1 

We inserted some debugging output in the code to be able to observe the progress of the computation. In addition, we inserted code at the end of the numbering phase to see the values in the data structure.

 A: node 8  A: node 6  A: node 5  A: node 3  A: node 2  A: node 1  NODE LINK NUMBER     0    0      2     1    0      0     2    0      0     3    0      0     4    0      0     5    0      0     6    0      0     7    0      0     8    0      0     9    0      0    10    0      0 

10.2.2.2 The investigation

Since we have inserted trace code with labels A through J, and only the output with label A is displayed, most of the function is not being executed. Not surprisingly, the final output of the numbering phase is almost all zeros, since nothing happened.

We begin at the beginning and start by verifying that the input to the application is being read correctly. We insert the following code into the function that is reading the test case to find out if the data is being read correctly. It displays the values as they are extracted from a line of text and converted to integers.

 fprintf(stderr,"%d %d %d %d %d %s\n",      _tree[row].getLeft(), _tree[row].getRight(),      _tree[row].getLink(), _tree[row].getNumber(),      _tree[row].getOpType(), _tree[row].getOpName() ); 

When we rerun the application, we get the following additional output:

 EXPR  -1 -1 -1 -1 0 "***"  2 11 0 0 32  ""  3 4 11 0 43  ""  0 0 4 1 51  "1,1"  5 10 0 0 22  ""  6 7 10 0 30  ""  0 0 7 2 53  "M" 

 8 9 0 0 42  ""  0 0 9 2 53  "M"  0 0 0 3 0  ""  0 0 0 3 0  ""  0 0 0 2 53  "M" 

We compare this listing to the original test file and find everything satisfactory. So, we insert similar code at the end of the procedure to display the entire data structure as it will be seen by the numbering function. What we see is the following. Obviously, nothing is being stored into this structure.

 EXPR  0 0 0 0 0 (null)  0 0 0 0 0 (null)  0 0 0 0 0 (null)  0 0 0 0 0 (null)  0 0 0 0 0 (null)  0 0 0 0 0 (null)  0 0 0 0 0 (null)  0 0 0 0 0 (null)  0 0 0 0 0 (null)  0 0 0 0 0 (null) 

10.2.2.3 The fault and correction

The data that is being correctly read in and converted is not being stored as it should. We review the loop that performs the conversions and assignments and discover that the variable used to index the array of Tree nodes is never incremented. We insert the following statement to correct this oversight:

 row++; 

We review all the code that creates and handles this data structure.

We observe that the allocation of the array of Tree nodes does not include space for an extra pad element to compensate for the origin-1 indexing of the original algorithm. So, we adjust the allocation statement accordingly:

 tree= new Tree[_size+1]; 

After we make these changes, we recompile and rerun the application. We are now storing the data correctly.

In this round of debugging, we applied the following methods from Chapter 9:

• Generate a flow trace.

• Generate a variable snapshot.

We found two defects that had the following root causes, which are explained in Chapter 11:

• Missing operation—statement missing

• Initialization errors—aggregate allocated wrong size

10.2.3 Bug 2

10.2.3.1 The evidence

The next debugging session began by running the application again.

We turn off the debugging output in the Expr constructor, since it is now working. We get the following results from the next run:

 A: node 8  A: node 9  A: node 6  A: node 7  B: left 8, lNum 2  C: tree[7].link= 0  D: bucket1[2].head= 7  E: node 7  F: right 9, rNum 3  G: tree[7].link= -1  H: bucket2[3].head= 7  A: node 5  B: left 6, lNum 2  C: tree[5].link= 0  D: bucket1[2].head= 5  A: node 10  E: node 5  F: right 7, rNum 0  G: tree[5].link= 1075519240  H: bucket2[0].head= 5  A: node 3  A: node 4  B: left 5, lNum 0  C: tree[4].link= 1075519600  D: bucket1[0].head= 4  A: node 2  B: left 3, lNum 1  C: tree[2].link= 0  D: bucket1[1].head= 2  A: node 11  E: node 2  F: right 4, rNum 0  G: tree[2].link= 5  H: bucket2[0].head= 2  A: node 1  B: left 2, lNum 0  C: tree[1].link= 4  D: bucket1[0].head= 1  NODE LINK NUMBER     0   -1     -1     1    4      0     2    5      0     3    4      1     4 1075519600      0     5 1075519240      0     6    7      2     7   -1      0     8    9      2     9    0      3    10    0      3 

We are pleased to see some progress. The distribution of the letters in the trace shows that we are executing much of the numbering algorithm.

10.2.3.2 The investigation

Upon further investigation, we see that an invalid value of -1 is being assigned at the trace point G. All of our indices must be positive integers, so we know something has gone wrong by the time we reach this point.

The value being assigned comes from this expression:

 bucket2[rNum].head 

Since it has an invalid value, we search backward from this point in the function to places where the head field of a bucket is assigned.

We insert the following code after each trace point near a statement that modifies this field:

 for( k=0; k<depth+1; ++k )  fprintf(stderr,"%d ",bucket2[k].head);  fprintf(stderr,"\n"); 

Adding this code quickly uncovers a problem. Here is the output of running the application. The program terminates when it attempts to use the huge value for the node variable that is printed on the last line.

The values that are printed after each trace point are the values in the bucket2 variable. These are random values, which are the result of not initializing the array.

 A: node 8  A: node 2  B: left 3, lNum 0  1075519240 -1 0 -1 0 0 0  C: tree[2].link= 1075519600  1075519240 -1 0 -1 0 0 0  D: bucket1[0].head= 2  1075519240 -1 0 -1 0 0 0  A: node 6  A: node 2  B: left 3, lNum 0  1075519240 -1 0 -1 0 0 0  C: tree[2].link= 2  1075519240 -1 0 -1 0 0 0  D: bucket1[0].head= 2  1075519240 -1 0 -1 0 0 0  A: node 1075519600 

We insert code to initialize the bucket arrays (see next page), but we still have a problem with this data structure. The buckets are used to sort the nodes in the tree, and there must be as many bucket entries as there are nodes. The bucket values are all displaying as initialized to zero now, but there are not enough of them.

10.2.3.3 The fault and correction

There are two problems. First, the two bucket arrays are allocated to the depth of the expression tree, rather than the size of the tree. Second, those elements that are allocated are never properly initialized. The following code corrects the problem:

 Bucket * bucket1= new Bucket[size+1];  for( int k=0; k<=depth; ++k ) {      bucket1[k].head= 0;      bucket1[k].link= 0;  }  Bucket * bucket2= new Bucket[size+1];  for( k=0; k<=depth; ++k ) {      bucket2[k].head= 0;      bucket2[k].link= 0;  } 

In this round of debugging, we applied the following methods from Chapter 9:

• Generate a flow trace.

• Display data structures.

We found two defects that had the following root causes, which are explained in Chapter 11:

• Initialization error—aggregate allocated wrong size

• Initialization error—aggregate always uninitialized

10.2.4 Bug 3

10.2.4.1 The evidence

The next debugging session began by running the application again. Since we are making progress, we select a different test case to exercise the code.

 11  6  3  -1 7 6 5 4 2 1  -1 -1 -1 -1        NONE       "***"  2    3    0    0   F_times    ""  0    0    3    1   V_first_1  "M"  4    11   0    0   F_trans    ""  5    10   11   0   F_form     ""  6    9    10   0   F_rev      ""  7    8    9    0   F_shape    ""  0    0    8    1   V_dup_1    "M"  0    0    0    2   NONE       ""  0    0    0    2   NONE       ""  0    0    0    3   V_first_2  "V"  0    0    0    2   NONE       "" 

When we run the application, we obtain the following results:

 A: node 7  A: node 6  B: left 7, lNum 8  C: tree[6].link= 0  D: bucket1[8].head= 6  E: node 6  F: right 8, rNum 0  G: tree[6].link= 0  H: bucket2[0].head= 6  A: node 5  B: left 6, lNum 9  C: tree[5].link= 0  D: bucket1[9].head= 5  E: node 5  F: right 9, rNum 0  G: tree[5].link= 6  H: bucket2[0].head= 5  0 -1 -1  1 0 0  2 0 3  3 1 0  4 0 11  5 6 10  6 0 9  7 0 8  8 0 0  9 0 0  10 0 0  11 0 0 

The trace of the activities seems rather short. The final dump of the data structure shows that the link field (column 2) has hardly been touched, and the number field (column 3) has been corrupted from the original values in the test case.

10.2.4.2 The investigation

Since values that were read in correctly seem to have been overwritten, we suspect a memory corruption problem. We choose to link in a special library for dynamic memory allocation that may help us find the problem. We use the mpatrol system, which is an open-source library and a set of related open-source tools, available on a wide variety of systems. See Chapter 14 for more information about this tool.

We add the following statement to our source files:

 #include <mpatrol.h> 

We also change our Makefile to link in some extra libraries with this line:

 allmp: $(OBJ)       g++ -g $(OBJ) -lmpatrol -lbfd -liberty -o snyder.exe 

We recompile our application, rerun it, and get the following results:

 A: node 7  A: node -1 

This does not provide us with much information, so we rerun the application under the debugger.

 (gdb) run  Starting program: snyder.exe  A: node 7  A: node -1  Program received signal SIGSEGV, Segmentation fault.  0x0805f616 in getNumber__4Tree (this=0xb2b1a3d0) at Tree.h:19  19    inline int getNumber() { return _number; }  (gdb) bt  #0  0x0805f616 in getNumber__4Tree (this=0xb2b1a3d0) at Tree.h:19  #1  0x0804ac0b in numberTree__FP4Expr (expr=0x806f1b8) at number.c:53  #2  0x0804bcd8 in main (argc=1, argv=0xbffff9ac) at main.c:19  ....  (gdb) q 

We need to find out why the value assigned to the node variable is -1, which is invalid. We run the application in the debugger and set a breakpoint just before the trace output that identifies the incorrect value.

 (gdb) b number.c:42  Breakpoint 1 at 0x804ab84: file number.c, line 42.  (gdb) run  Breakpoint 1, numberTree__FP4Expr (expr=0x806f1b8) at number.c:42  42    node= height[i];  (gdb) p i  $1 = 1  (gdb) p height[i]  $2 = 7  (gdb) cont  A: node 7  Breakpoint 1, numberTree__FP4Expr (expr=0x806f1b8) at number.c:42  42    node= height[i];  (gdb) p i  $3 = 2  (gdb) p height[i]  $4 = -1  (gdb) p height[0]  $5 = -1  (gdb) p height[1]  $6 = 0  (gdb) p height[2]  $7 = -1  (gdb) p height[3]  $8 = 6  (gdb) p height[4]  $9 = -1  (gdb) p height[5]  $10 = 5  (gdb) p height[6]  $11 = -1  (gdb) p height[7]  $12 = 0  (gdb) q 

It appears that the values being inserted into the height array are being interspersed with incorrect values, or alternatively, that locations are being skipped as the values are being stored.

We look over the code in Expr.c and discover that the counter that tracks the location to store values is incremented twice each time a value is extracted from the input line.

We correct this problem (see following) and continue. We rebuild and rerun the application standalone, obtaining the following output:

 A: node 7  A: node 6  B: left 7, lNum 8  C: tree[6].link= 0  D: bucket1[8].head= 6  E: node 6  F: right 8, rNum 0  G: tree[6].link= 0  H: bucket2[0].head= 6  A: node 5  B: left 6, lNum 9  C: tree[5].link= 0  D: bucket1[9].head= 5  E: node 5  F: right 9, rNum 0  G: tree[5].link= 6  H: bucket2[0].head= 5  A: node 4  B: left 5, lNum 10  C: tree[4].link= 0  D: bucket1[10].head= 4  E: node 4  F: right 10, rNum 0  G: tree[4].link= 5  H: bucket2[0].head= 4  A: node 2  A: node 1  B: left 2, lNum 3  C: tree[1].link= 0  D: bucket1[3].head= 1  E: node 1  F: right 3, rNum 0  G: tree[1].link= 4  H: bucket2[0].head= 1  0 -1 -1  1 4 0  2 0 3  3 1 0  4 5 11  5 6 10  6 0 9  7 0 8  8 0 0  9 0 0  10 0 0  11 0 0 

The trace looks more interesting, and there are no more obviously incorrect values.

10.2.4.3 The fault and correction

The problem is corrected simply by removing the following statement from the processing of the height array:

 ++tokenCtr; 

In this round of debugging, we applied the following methods from Chapter 9:

• Display data structures.

• Generate a flow trace.

• Use runtime heap checking.

We found one defect that had the following root causes, explained in Chapter 11:

• Initialization errors—aggregate variable partially uninitialized

• Control-flow problems—statement executed too many times

10.2.5 Bug 4

10.2.5.1 The evidence

The next debugging session began by running the application. We modify the main program so that it now reads in and constructs the IdiomTable object. We also insert code to display this data structure after it is constructed.

Here is the initial output:

 0 0 0 0 0 0 0 0 0 0 0 0 0 -1  0 32 43 51 22 30 53 42 56 56 0 0 0 -1  0 35 26 20 16 52 53 56 0 0 0 0 0 -1  0 32 9 17 53 52 17 56 35 51 56 56 0 -1  0 38 53 44 47 1 51 37 54 43 48 57 56 -1  0 1 53 26 20 50 30 54 43 57 0 0 0 -1  0 3 53 43 36 34 37 56 54 0 0 0 0 -1  0 32 16 48 53 56 39 37 56 56 0 0 0 -1  0 32 40 41 53 51 40 41 56 50 56 0 0 -1 

10.2.5.2 The investigation

All the numbers look correct except the last columns. We hypothesize that we have made the same mistake we made before, which is to dimension the array for origin-0 indexing. We review the code that allocates the storage for the IdiomTable class and find three statements where this is true.

10.2.5.3 The fault and correction

The original algorithm used origin-1 indexing, but C++ naturally uses origin-0 indexing. We had tried to avoid problems in converting the algorithm by padding the arrays with an extra element. We did an incomplete job and did not pad the arrays in the IdiomTable object. We make the following changes:

 _table= new (int *)[_count+1];  ...  _table[i]= new int[_size+1];  ...  _payoff= new int[_count+1]; 

In this round of debugging, we applied the following method from Chapter 9:

• Display data structures.

We found several defects that all had the following root cause, explained in Chapter 11:

• Initialization errors—aggregate allocated wrong size

10.2.6 Bug 5

10.2.6.1 The evidence

The next debugging session began by reviewing code that we are about to enable. Before turning on the matching algorithm, we decide to read the whole function through, looking for problems. We start with the loop that creates match descriptors that begin with the same operation as the first operation in the expression.

 for(i= 1; i <= numIdioms; ++i) {      if( idiomTable[i][1] == tree[vertex].getOpType() ) {          newDesc= new Desc(vertex,i,1,0,0);          if( accumHead.getNext() == 0 ) {              accum= newDesc;              accumHead.setNext(accum);          } else {              accum->setNext(newDesc);          }      }  } 

10.2.6.2 The investigation

What catches our eye is that we are mostly using doubly linked lists in this application, and yet this code does not invoke a method to set a back pointer. In addition, the variable that tracks the leading edge of the list, accum, gets set only once, when the pointer that tracks the head of the list is null.

10.2.6.3 The fault and correction

We recall that we used the same head variable/frontier variable method for representing several linked lists used by the match algorithm: the accumulate list, the active list, the suspend list, and the selection chain. We review all the code that appends to one of these lists and find seven places that all have the same problem.

We change five of them from the structure listed next to the one that follows it. The other two update a list that does not have a back pointer, so the assignment to the previous field is not used.

 newObject= new Object(arguments);  if( listHead.getNext() == 0 ) {      listHead.setNext(frontier);  } else {      frontier->setNext(newObject);  }  newObject= new Object(arguments);  if( listHead.getNext() == 0 ) {      listHead.setNext(newObject);  } else {      frontier->setNext(newObject);      newObject->setPrev(frontier);  }  frontier= newObject; 

In this round of debugging, we applied the following method from Chapter 9:

• Read the source code.

We found several defects that had the following root causes, explained in Chapter 11:

• Reference errors—variable not assigned

• Control-flow problems—statement controlled by wrong control-flow condition

10.2.7 Bug 6

10.2.7.1 The evidence

The next debugging session began by running the application under the debugger, with the special memory allocation library linked in. We immediately run into a problem.

 (gdb) run  Starting program: snyder.exe  Program received signal SIGABRT, Aborted.  0x4010d801 in __kill () from /lib/i686/libc.so.6  (gdb) bt  #0  0x4010d801 in __kill () from /lib/i686/libc.so.6  #1  0x4010d5da in raise (sig=6) at ../sysdeps/posix/raise.c:27  #2  0x4010ed82 in abort () at ../sysdeps/generic/abort.c:88  #3  0x080547fc in __mp_checkinfo () at main.c:22  #4  0x0804c2b6 in __mp_fini () at main.c:22  #5  0x0805f786 in _fini ()  #6  0x4011022b in exit (status=0) at exit.c:54  #7  0x400fc180 in __libc_start_main (main=0x804bae0 <main>, argc=1,      ubp_av=0xbffff9ac, init=0x80498d8 <_init>, fini=0x805f768  <_fini>, rtld_fini=0x4000e184 <_dl_fini>, stack_end=0xbffff99c)      at ../sysdeps/generic/libc-start.c:129  (gdb) q 

10.2.7.2 The investigation

The application is dying in the memory allocation library. This is almost guaranteed to be some sort of memory corruption problem. Our first step is to change the test driver and turn off some of the processing steps. We will add them back in as we develop more confidence in them. int main(int argc, char **argv ) {

     Expr * expr= new Expr("test1.txt");  //    numberTree(expr);  //    IdiomTable * table= new IdiomTable("table.txt");  //    match(1, expr, table );  } 

When we comment out everything but the construction of the Expr object, the application runs to completion normally. The same is true when we put the call to the numberTree function back in. When we put the construction of the IdiomTable object back in, we get the original symptom. So, the problem is likely occurring in the function before the place where the symptom manifests itself (e.g., in numberTree). We take the call to the constructor for IdiomTable back out and turn on the display of the data structure on exit from numberTree. This results in the following output: exit numberTree()

 0 -1 -1  1 4 0  2 0 3  3 1 0  4 5 11  5 6 10  6 0 9  7 0 8  8 0 0  9 0 0  10 0 0  11 0 0 

The nonzero values in the original test case in column three (the unique node numbers) should be preserved on exit from this function. They are not being preserved, so we decide to check whether they were available on entry to the function. We add an identical display at the start of the numberTree function.

 enter numberTree()  0 -1 -1  1 0 0  2 0 3  3 1 0  4 0 11  5 0 10  6 0 9  7 0 8  8 0 0  9 0 0  10 0 0  11 0 0 

It is now clear that the input to this function was not what the original test case contained. So, we need to determine whether the data structure was ever created correctly. We insert code at the end of the constructor for the Expr object to display the data coming from the file as it is converted, and later to display the entire tree structure.

 exit Expr()  0 -1 -1  1 0 0  2 0 3  3 1 0  4 0 11  5 0 10  6 0 9  7 0 8  8 0 0  9 0 0  10 0 0  11 0 0 

We have located the problem. The data is being read and converted correctly but is not being stored where it belongs.

10.2.7.3 The fault and correction

How could the data be read in and converted correctly, but not stored in the data structure correctly? The answer is that as each line is read in and tokens are identified, those tokens are stored in a temporary array until they can all be converted and stored, and the location of the next place to save a token is kept in a variable tokenCtr.

As written, the counter is initialized to zero at the beginning of the outer loop, which processes one line of input per iteration. Unfortunately, it needs to be initialized at the beginning of the inner loop, which recognizes the tokens. The result of the error is that subsequent to the first iteration, tokens were being saved into memory following the temporary array, and the tokens from the first input line were being converted over and over. The problem is corrected simply by moving the following statement inside the loop that processes lines of input:

 tokenCtr= 0; 

In this round of debugging, we applied the following methods from Chapter 9:

• Generate a flow trace.

• Display data structures.

• Use runtime heap checking.

We found one defect that had the following root causes, explained in Chapter 11:

• Dynamic data-structure problems—array subscript out of bounds

• Control-flow problems—statement controlled by wrong control-flow condition

10.2.8 10.2.8 Bug 7

10.2.8.1 The evidence

The next debugging session began by running the application. We use the same test input and test driver as before. We obtain the following output, and then the program seems to go into an infinite loop:

 <number  [ 0] -1 -1 -1 -1  [ 1]  2 11  0  8  [ 2]  3  4  0  7  [ 3]  0  0  4  1  [ 4]  5 10  0  6  [ 5]  6  7  0  5  [ 6]  0  0  7  2  [ 7]  8  9  0  4  [ 8]  0  0  9  2  [ 9]  0  0  0  3  [10]  0  0  0  3  [11]  0  0  0  2  Table  0 0 0 0 0 0 0 0 0 0 0 0 0  0 32 43 51 22 30 54 42 57 57 0 0 0  0 35 26 20 16 53 54 57 0 0 0 0 0  0 32 9 17 54 53 17 57 35 51 57 57 0  0 38 54 44 47 1 51 37 55 43 48 58 57  0 1 54 26 20 50 30 55 43 58 0 0 0  0 3 54 43 36 34 37 57 55 0 0 0 0  0 32 16 48 54 57 39 37 57 57 0 0 0 

10.2.8.2 The investigation

We turn on the control-flow trace statements in the match function and rerun the application in the debugger. Here is a portion of the trace output:

 (gdb) run  Starting program: /home/metzger/src/idiom/evolve/b07/snyder.exe  ....  match: vertex= 1, tree[vertex].getOpType= 32  A: vertex= 1, row= 1, col= 1, bene= 0, chain= 0  A: vertex= 1, row= 3, col= 1, bene= 0, chain= 0  A: vertex= 1, row= 7, col= 1, bene= 0, chain= 0  A: vertex= 1, row= 8, col= 1, bene= 0, chain= 0  C: tree[1].getLeft()= 2, best= 0  match: vertex= 2, tree[vertex].getOpType= 43  B: curr= 1, row= 1, col= 1, bene= 0, chain= 0  0) idiomTable[1][2]= 43, isOpFunction= 1  1) curr= 1, row= 1, col+1= 2, bene= 0, chain= 0  B: curr= 1, row= 3, col= 1, bene= 0, chain= 0  0) idiomTable[3][2]= 9, isOpFunction= 1  B: curr= 1, row= 7, col= 1, bene= 0, chain= 0  0) idiomTable[7][2]= 16, isOpFunction= 1  B: curr= 1, row= 8, col= 1, bene= 0, chain= 0  0) idiomTable[8][2]= 40, isOpFunction= 1  C: tree[2].getLeft()= 3, best= 0  match: vertex= 3, tree[vertex].getOpType= 51  B: curr= 1, row= 1, col= 2, bene= 0, chain= 0  0) idiomTable[1][3]= 51, isOpFunction= 1  1) curr= 1, row= 1, col+1= 3, bene= 0, chain= 0  G: curr= 1, row= 1, col= 3, bene= 0, chain= 0; vertex= 3  K: tree[3]: benefit= 0, select= 804d370  G: curr= 1, row= 1, col= 3, bene= 0, chain= 0; vertex= 3  .... [infinite loop]  Program received signal SIGINT, Interrupt.  0x0804aa68 in match__FiP4ExprP10IdiomTable (vertex=3, expr=0x804cf78,      table=0x804d060) at match.c:306  306        while (0 != (desc = suspendHead.getNext ())) {  (gdb) bt  #0  0x0804aa68 in match__FiP4ExprP10IdiomTable (vertex=3,  expr=0x804cf78, table=0x804d060) at match.c:306  #1  0x0804a2f1 in match__FiP4ExprP10IdiomTable (vertex=2,  expr=0x804cf78, table=0x804d060) at match.c:179  #2  0x0804a2f1 in match__FiP4ExprP10IdiomTable (vertex=1,  expr=0x804cf78, table=0x804d060) at match.c:179  #3  0x0804aef6 in main (argc=1, argv=0xbffff9ac) at main.c:22  ....  (gdb) q 

We try executing in the debugger several times. Each time we generate an interrupt from the keyboard, we are somewhere in the loop that contains the two flow trace statements that are repeating infinitely.

We read the source code very carefully, comparing it to the algorithm design in the original paper.

We notice something disturbing. The author uses a pseudocode notation with Pascal-like keywords and indentation. Since he does not enclose every control-flow construct with delimiters, dangling else clauses could be subject to more than one interpretation. Nowhere in the paper does he define or reference the definition of the semantics of his notation. We had assumed that syntactic entities with the same level of nesting should be treated as being parallel. The more we read the pseudocode for this loop, the more we are convinced that this assumption is false.

10.2.8.3 The fault and correction

We rewrite the nested if-then-else statements in the loop that is running infinitely with the other interpretation of dangling else clauses. This changes the conditions under which the computation of the best-selection value was made. It also makes the code that saves the computation of the best-selection value independent of the match between the current node and the root of the matched idiom.

Since the dangling else problem occurs more than once in the algorithm design, we also modify conditions under which vertices are appended to the match descriptor.

In this round of debugging, we applied the following methods from Chapter 9:

• Read the source code.

• Generate a flow trace.

We found several defects that had the following root cause, explained in Chapter 11:

• Control-flow problems—statements controlled by wrong control-flow condition

10.2.9 Bug 8

10.2.9.1 The evidence

The next debugging session began by running the application. We used the same test input and driver. The results are listed as follows.

 match: vertex= 1, tree[vertex].getOpType= 3  A: vertex= 1, row= 6, col= 1, bene= 0, chain= 0  C: tree[1].getLeft()= 2, best= 0  match: vertex= 2, tree[vertex].getOpType= 54  B: curr= 1, row= 6, col= 1, bene= 0, chain= 0  0) idiomTable[6][2]= 54, isOpFunction= 1  1) curr= 1, row= 6, col+1= 2, bene= 0, chain= 0  G: curr= 1, row= 6, col= 2, bene= 0, chain= 0; vertex= 2  K: tree[2]: benefit= 0, select= 804d3d0  D: vertex= 1, best= 0  D1: 2  E: tree[1].getRight()= 3, best= 0  match: vertex= 3, tree[vertex].getOpType= 43  C: tree[3].getLeft()= 4, best= 0  match: vertex= 4, tree[vertex].getOpType= 36  C: tree[4].getLeft()= 5, best= 0  match: vertex= 5, tree[vertex].getOpType= 34  C: tree[5].getLeft()= 6, best= 0  match: vertex= 6, tree[vertex].getOpType= 37  C: tree[6].getLeft()= 7, best= 0  match: vertex= 7, tree[vertex].getOpType= 57  D: vertex= 6, best= 0  D1: 7  E: tree[6].getRight()= 8, best= 0  match: vertex= 8, tree[vertex].getOpType= 0  F: vertex= 6, best= 0  F1: 8  D: vertex= 5, best= 0  D1: 6  E: tree[5].getRight()= 9, best= 0  match: vertex= 9, tree[vertex].getOpType= 0  F: vertex= 5, best= 0  F1: 9  D: vertex= 4, best= 0  D1: 5  E: tree[4].getRight()= 10, best= 0  match: vertex= 10, tree[vertex].getOpType= 55  F: vertex= 4, best= 0  F1: 10  D: vertex= 3, best= 0  D1: 4  E: tree[3].getRight()= 11, best= 0  match: vertex= 11, tree[vertex].getOpType= 0  F: vertex= 3, best= 0  F1: 11  F: vertex= 1, best= 0  F1: 3 

We are not going into an infinite loop anymore. Unfortunately, we do not seem to be going into the loop that had the problem. The trace records with labels “G” and “K” occur only once each, and “H,” “I,” “J,” and “L” do not occur at all.

10.2.9.2 The investigation

We rerun the application under the debugger and set a breakpoint at the entry to the loop. It goes into the loop, so we set additional breakpoints at the if statement and the while loop that control almost all of the contents of the loop. The if statement is never true, and the while is never executed. The former symptom is the really worrisome one, since this code detects a match and computes the selection of the best match among several.

We decide to investigate the reason that the while loop is not being executed. Upon careful investigation of its body, we discover that we did not implement the fix for bug 5 in this loop. This is not keeping the loop from executing, of course, but at least we have fixed the bug without having to search for it. We also notice that this is the only loop that modifies an existing match descriptor, rather than creating a new one. We decide to make it work the same, in the interest of consistency.

Now we need to find out why the loop is not executing the key segments. We note that this loop processes items on the suspend list and that there are never any such items. We look at the code that should be putting items on this list. There are no trace records for the code that puts items on the suspend list.

10.2.9.3 The fault and correction

We compare the code to the original algorithm. We conclude that we have found yet two more places where we have been bitten by inconsistent indentation and dangling else clauses. We restructure the code with the other interpretation of conditional nesting and move on.

In this round of debugging, we applied the following methods from Chapter 9:

• Read the source code.

• Generate a flow trace.

We found two defects that had the following root cause, explained in Chapter 11:

• Control-flow problems—statements controlled by wrong control-flow condition

10.2.10 Bug 9

10.2.10.1 The evidence

The next debugging session began by running the application. We continue with the same test input and test driver. This is the control-flow trace we get from the match algorithm:

 match: vertex= 1, tree[vertex].getOpType= 3  A: vertex= 1, row= 6, col= 1, bene= 0, chain= 0  C: tree[1].getLeft()= 2, best= 0  match: vertex= 2, tree[vertex].getOpType= 54  B: curr= 1, row= 6, col= 1, bene= 0, chain= 0  D: vertex= 1, best= 0  D1: 2  E: tree[1].getRight()= 3, best= 0  match: vertex= 3, tree[vertex].getOpType= 43  C: tree[3].getLeft()= 4, best= 0  match: vertex= 4, tree[vertex].getOpType= 36  C: tree[4].getLeft()= 5, best= 0  match: vertex= 5, tree[vertex].getOpType= 34  C: tree[5].getLeft()= 6, best= 0  match: vertex= 6, tree[vertex].getOpType= 37  C: tree[6].getLeft()= 7, best= 0  match: vertex= 7, tree[vertex].getOpType= 57  D: vertex= 6, best= 0  D1: 7  E: tree[6].getRight()= 8, best= 0  match: vertex= 8, tree[vertex].getOpType= 0  F: vertex= 6, best= 0  F1: 8  D: vertex= 5, best= 0  D1: 6  E: tree[5].getRight()= 9, best= 0  match: vertex= 9, tree[vertex].getOpType= 0  F: vertex= 5, best= 0  F1: 9  D: vertex= 4, best= 0  D1: 5  E: tree[4].getRight()= 10, best= 0  match: vertex= 10, tree[vertex].getOpType= 55  F: vertex= 4, best= 0  F1: 10  D: vertex= 3, best= 0  D1: 4  E: tree[3].getRight()= 11, best= 0  match: vertex= 11, tree[vertex].getOpType= 0  F: vertex= 3, best= 0  F1: 11  F: vertex= 1, best= 0  F1: 3 

10.2.10.2 The investigation

We have grown tired of dealing with inconsistent indentation and dangling else problems. We decide to strip out all the debugging scaffolding, run the source through the indent utility, and compare the control structure to the published algorithm. When we do so, we decide that we now have control structures consistent with our new interpretation of the published notation.

Unfortunately, we are also convinced that the control flow of the published algorithm is wrong. The last part of the algorithm is supposed to move descriptors from the suspended list. This action occurs inside a loop that executes when there are items on the active list. If there is nothing on the active list, this loop will not execute, and no descriptors from the suspended list will be moved to the active list. No more active tasks means no more resumption of suspended tasks, which would become active. It is a catch-22.

10.2.10.3 The fault and correction

We move the enclosing brace so that the movement of items on the suspended list always occurs, even when the active list is empty.

Having found yet another error due to our problems interpreting the notation of the original algorithm, we decide to go over the entire listing one more time. We find two more problems.

The original algorithm has a statement in which the selection list is assigned the value “(0).” Everywhere else in this algorithm, items are put inside of parentheses to denote the creation of a list. We originally interpreted this as meaning “create a list with the integer 0 in it.” We note that every other value that is appended to this list is a valid node index. Zero is not a valid node index when origin-1 indexing is in use. Putting zero at the head of this list makes no sense, so we decide that either the author made a typographical error—“)” and “0” are on the same key—or he used his notation inconsistently. We change the assignment to be a null pointer.

The original paper presents two versions of the algorithm. The earlier one only performs matching. The later one performs matching and selection based on benefit analysis. The nodes that are appended to the suspended list are different in the first and second versions of the algorithm. We started with the first version and now decide to try the second one instead. The first version refers to variables “v” and “u” (our “vertex” and “current”); the second version refers to “u” and “u.”

In this round of debugging, we applied the following methods from Chapter 9:

• Read the source code.

• Generate a flow trace.

We found three defects that had the following root causes, which are explained in Chapter 11:

• Control-flow problems—statements controlled by wrong control-flow condition

• Initialization errors—simple variable initialized with wrong value

• Reference errors—wrong variable referenced

10.2.11 Bug 10

10.2.11.1 The evidence

The next debugging session began by running the application. The test output is shown as follows:

 match: vertex= 1, tree[vertex].getOpType= 3  A: vertex= 1, row= 6, col= 1, bene= 0, chain= 0  C: tree[1].getLeft()= 2, best= 0  match: vertex= 2, tree[vertex].getOpType= 54  B: curr= 1, row= 6, col= 1, bene= 0, chain= 0  4) curr= 1, row= 6, col+1= 2, bene= 0, chain= 804d150  L: current= 1, row= 6, col= 2, bene= 0, chain= 804d150  D: vertex= 1, best= 0  D1: 2  E: tree[1].getRight()= 3, best= 0  match: vertex= 3, tree[vertex].getOpType= 43  B: curr= 1, row= 6, col= 2, bene= 0, chain= 804d150  0) idiomTable[6][3]= 43, isOpFunction= 1  1) curr= 1, row= 6, col+1= 3, bene= 0, chain= 804d150  C: tree[3].getLeft()= 4, best= 0  match: vertex= 4, tree[vertex].getOpType= 36  B: curr= 1, row= 6, col= 3, bene= 0, chain= 804d150  0) idiomTable[6][4]= 36, isOpFunction= 1  1) curr= 1, row= 6, col+1= 4, bene= 0, chain= 804d150  C: tree[4].getLeft()= 5, best= 0  match: vertex= 5, tree[vertex].getOpType= 34  B: curr= 1, row= 6, col= 4, bene= 0, chain= 804d150  0) idiomTable[6][5]= 34, isOpFunction= 1  1) curr= 1, row= 6, col+1= 5, bene= 0, chain= 804d150  C: tree[5].getLeft()= 6, best= 0  match: vertex= 6, tree[vertex].getOpType= 37  B: curr= 1, row= 6, col= 5, bene= 0, chain= 804d150  0) idiomTable[6][6]= 37, isOpFunction= 1  1) curr= 1, row= 6, col+1= 6, bene= 0, chain= 804d150  C: tree[6].getLeft()= 7, best= 0  match: vertex= 7, tree[vertex].getOpType= 57  B: curr= 1, row= 6, col= 6, bene= 0, chain= 804d150  2) curr= 1, row= 6, col+1= 7, bene= 0, chain= 804d150  D: vertex= 6, best= 0  D1: 7  E: tree[6].getRight()= 8, best= 0  match: vertex= 8, tree[vertex].getOpType= 0  F: vertex= 6, best= 0  F1: 8  D: vertex= 5, best= 0  D1: 6  E: tree[5].getRight()= 9, best= 0  match: vertex= 9, tree[vertex].getOpType= 0  F: vertex= 5, best= 0  F1: 9  D: vertex= 4, best= 0  D1: 5  E: tree[4].getRight()= 10, best= 0  match: vertex= 10, tree[vertex].getOpType= 55  F: vertex= 4, best= 0 

 F1: 10  D: vertex= 3, best= 0  D1: 4  E: tree[3].getRight()= 11, best= 0  match: vertex= 11, tree[vertex].getOpType= 0  F: vertex= 3, best= 0  F1: 11  F: vertex= 1, best= 0  F1: 3 

We are very pleased with this listing. Nodes are being visited in the right order. Auxiliary linked lists are being created. The control-flow trace shows that many of the critical code sections are being executed when processing the nodes.

There are still two obvious problems. First, all the benefit calculations are yielding a result of zero. Second, significant portions of the algorithm are not being executed. In particular, the trace points G, H, I, J, K, and L are not found in the listing.

10.2.11.2 The investigation

We begin by looking at the statement that controls the first section that is not executed. The if statement includes a call to the function firstOccur. We have not looked at this before.

 int IdiomTable::firstOccur(int x) {      return 0;  } 

10.2.11.3 The fault and correction

This is an obvious omission. We decide that the function belongs in the Expr class, rather than the IdiomTable class, since it requires access to the elements of that class.

Here we provide an implementation to replace the stub:

 int Expr::firstOccur(int opcode) {      opcode -= VARB_COUNT;      int first= -1;      for( int i= 0; i <= _size; ++i ) {          if( opcode == _tree[i].getOpType()) {              first= i;              break;          }      }      return first;  } 

In this round of debugging, we applied the following methods from Chapter 9:

• Generate a flow trace.

• Read the code.

We found one defect that had the following root cause, explained in Chapter 11:

• Missing operation—statements are missing

10.2.11.4 Final test

The debugging process is not complete until the changes have been thoroughly tested. Listed as follows are eight test cases we ran and the output of the program resulting from those cases.

 9  6  3  -1 8 6 5 3 2 1  -1 -1 -1 -1 NONE "***"  2 9 0 0 F_cprs ""  3 4 9 0 F_trans ""  0 0 4 1 C_int "(1 1)"  5 0 0 0 F_lt_scan ""  6 7 0 0 F_and_eq ""  0 0 7 2 V_first_1 "M"  8 0 0 0 F_flip ""  0 0 0 2 V_dup_1 "M"  0 0 0 2 V_dup_1 "M"  IDIOM: 1  VARBS: 6 8 9  7  5  3  -1 5 4 3 2 1  -1 -1 -1 -1 NONE ""  2 7 0 0 F_rot ""  3 0 7 0 F_plus_red ""  4 0 0 0 F_and_scan ""  5 6 0 0 F_eq ""  0 0 6 1 C_char " "  0 0 0 2 V_first_1 "V"  0 0 0 2 V_dup_1 "V"  IDIOM: 2  VARBS: 6 7  11  5  4  -1 9 4 3 2 1  -1 -1 -1 -1 NONE "***"  2 11 0 0 F_cprs ""  3 6 11 0 F_or ""  4 5 6 0 F_neq ""  0 0 5 1 V_first_1 "V"  0 0 7 2 C_char " "  7 8 0 0 F_neq ""  0 0 8 1 V_dup_1 "V"  9 10 0 0 F_rot ""  0 0 10 3 C_int "1"  0 0 0 1 V_dup_1 "V"  0 0 0 1 V_dup_1 "V"  IDIOM: 3  VARBS: 4 7 10 11  12  6  4  -1 8 6 5 4 2 1  -1 -1 -1 -1 NONE "***"  2 3 0 0 F_get ""  0 0 3 1 V_first_1 "M"  4 0 0 0 F_upgr ""  5 9 0 0 F_value ""  6 7 9 0 F_plus ""  0 0 7 2 C_int "1"  8 0 10 0 F_shape ""  0 0 11 3 V_first_2 "K"  10 0 0 0 F_trans ""  11 12 0 0 F_find ""  0 0 12 3 V_dup_2 "K"  0 0 0 1 V_dup_1 "M"  IDIOM: 4  VARBS: 2 8 11 12  9  7  4  -1 9 7 6 5 4 2 1  -1 -1 -1 -1 NONE "***"  2 3 0 0 F_plus ""  0 0 3 1 V_first_1 "Qio"  4 0 0 0 F_plus_red ""  5 0 0 0 F_and_scan ""  6 0 0 0 F_not ""  7 8 0 0 F_and_eq ""  0 0 8 2 V_first_2 "M"  9 0 0 0 F_trans ""  0 0 0 2 V_dup_2 "M"  IDIOM: 5  VARBS: 2 7 9  8  6  3  -1 7 6 5 4 2 1  -1 -1 -1 -1 NONE "***"  2 3 0 0 F_times ""  0 0 3 1 V_first_1 "M"  4 0 0 0 F_trans ""  5 8 0 0 F_form ""  6 0 8 0 F_rev ""  7 0 0 0 F_shape ""  0 0 0 1 V_dup_1 "M"  0 0 0 3 V_first_2 "V"  IDIOM: 6  VARBS: 2 7 8  9  5  2  -1 8 4 3 2 1  -1 -1 -1 -1 NONE "***"  2 9 0 0 F_cprs ""  3 6 9 0 F_eq ""  4 5 6 0 F_find ""  0 0 5 1 V_first_1 "V"  0 0 7 1 V_dup_1 "V"  7 0 0 0 F_iota ""  8 0 0 0 F_shape ""  0 0 0 1 V_dup1 "V"  0 0 0 1 V_dup_1 "V"  IDIOM: 7  VARBS: 4 5 8 9  10  5  3  -1 10 4 3 2 1  -1 -1 -1 -1 NONE "***"  2 6 0 0 F_cprs ""  3 0 6 0 F_ravel ""  4 5 7 0 F_splice ""  0 0 5 1 V_first_1 "B"  0 0 8 2 C_int "1"  7 0 0 0 F_ravel ""  8 9 0 0 F_splice ""  0 0 9 1 V_dup_1 "B"  10 0 0 0 F_not ""  0 0 0 1 V_dup_1 "B"  IDIOM: 8  VARBS: 4 8 10 

10.2.11.5 Final source

The code for the final program is listed as follows. In the interest of brevity, we have omitted the source for the following files since we did not change them during our debugging activities:

• Bucket.h

• Select.h

• Opcode.h

• Desc.h

• Tree.h

• IdiomTable.h

• Select.c

• Opcode.c

• Desc.c

 ________________________________________________________  /* Expr.h */  #ifndef _Expr_h_  #define _Expr_h_  class Expr {  public:      // constructors and destructors      Expr(char *);      Expr(int, int, Tree *, int *);      ~Expr();      // accessors      inline int getSize() { return _size; }      inline int getDepth() { return _depth; }      inline int getUnique() { return _unique; }      inline Tree * getTree() { return _tree; }      inline int * getHeight() { return _height; }      // mutators      inline void setSize(int x) { _size= x; }      inline void setDepth(int x) { _depth= x; }      inline void setUnique(int x) { _unique= x ; }      inline void setTree(Tree * x) { _tree= x; }      inline void setHeight(int * x) { _height= x; }      // workers      int firstOccur(int);      void solution();  private:      int _size;      int _depth;      int _unique;      Tree * _tree;      int * _height;  };  #endif  ________________________________________________________  /* Tree.c */  #include "Select.h"  #include "Tree.h"  #include "Opcode.h"  Tree::Tree() {      Tree(0,0,0,0,0,0,0,0);  }  Tree::Tree( int left, int right, int link, int number,      int opType, char * opName, int benefit,      Select * select ) {      _left= left;      _right= right;      _link= link;      _number= number;      _opType= opType;      _opName= opName;      _benefit= benefit;      _select= select;  }  Tree::~Tree() {      delete _opName;      Select *p, *q;      for( p= _select; p != 0 ; p= q ) {           q= p->getNext();           delete p;      }  }  ________________________________________________________  /* Expr.c */  #include <stdio.h>  #include <stdlib.h>  #include <string.h>  #include <ctype.h>  #include "Select.h"  #include "Tree.h"  #include "Expr.h"  #include "Opcode.h"  //------------------------------------------------------ Expr::Expr(char * fileName) {      int bufSize= 256;      char buffer[256];      char *tokens[128];      FILE * file= fopen(fileName,"r");      if( file == 0 ) {          fprintf(stderr,"Unable to open %s\n",fileName);          fflush(stderr);          exit(1);      }      fscanf(file, "%d\n", &_size);      fscanf(file, "%d\n", &_depth);      fscanf(file, "%d\n\n", &_unique);      _tree= new Tree[_size+1];      _height= new int[_depth+1];      int tokenCtr= 0;      fgets(buffer, bufSize, file);      char * token= strtok(buffer, " ");      _height[tokenCtr++]= atoi(token);      while( token= strtok(NULL, " \n") ) {          if( !isdigit(token[0]) ) {              continue;          }          _height[tokenCtr++]= atoi(token);      }      int row= 0;      while ( 0 != fgets(buffer, bufSize, file) ) {          tokenCtr= 0;          buffer[strlen(buffer)-1]= ‘\0’;          token= strtok(buffer, " ");          tokens[tokenCtr++]= token;          int k=0;          while( token= strtok(NULL, " \n") ) {              tokens[tokenCtr++]= token;          }          _tree[row].setLeft(atoi(tokens[0]));          _tree[row].setRight(atoi(tokens[1]));          _tree[row].setLink(atoi(tokens[2]));          _tree[row].setNumber(atoi(tokens[3]));          _tree[row].setOpType(lookupTag(tokens[4]));          _tree[row].setOpName(tokens[4]);          _tree[row].setBenefit(0);          _tree[row].setSelect(0);  #ifdef DEBUG  fprintf(stderr,"%d %d %d %d %d %s\n",          _tree[row].getLeft(), _tree[row].getRight(),          _tree[row].getLink(), _tree[row].getNumber(),          _tree[row].getOpType(), _tree[row].getOpName() );  #endif          row++;      }      fclose(file);  }  //------------------------------------------------------ Expr::Expr(int depth, int unique, Tree * tree, int * height) {      _depth= depth;      _unique= unique;      _tree= tree;      _height= height;  }  //------------------------------------------------------ Expr::~Expr() {       delete _height;       delete _tree;  }  //------------------------------------------------------ int Expr::firstOccur(int opcode) {      opcode -= VARB_COUNT;      int first= -1;      for( int i= 0; i <= _size; ++i ) {           if( opcode == _tree[i].getOpType() ) {               first= i;               break;           }      }      return first;  }  ________________________________________________________  /* IdiomTable.c */  #include <stdio.h>  #include <string.h>  #include <stdlib.h>  #include "IdiomTable.h"  #include "Opcode.h"  //------------------------------------------------------ IdiomTable::IdiomTable(char *fileName) {      int bufSize= 256;      char buffer[256];      char * tokens[128];      FILE * file= fopen(fileName,"r");      if ( file == 0 ) {          fprintf(stderr,"Unable to open %s\n",fileName);          fflush(stderr);          exit(1);      }      fscanf(file, "%d\n", &_count);      fscanf(file, "%d\n", &_size);      _table= new (int *)[_count+1];      for ( int i=0; i <= _count; ++i ) {          _table[i]= new int[_size+1];      }      _payoff= new int[_count+1];      int tokenCtr= 0;      fgets(buffer, bufSize, file);      char * token= strtok(buffer, " ");      _payoff[tokenCtr++]= atoi(token);      while( token= strtok(NULL, " \n") ) {          _payoff[tokenCtr++]= atoi(token);      }      int j= 0;      while ( 0 != fgets(buffer, bufSize, file) ) {          token= strtok(buffer, " ");          tokens[tokenCtr++]= token;          int k=0;          _table[j][k++]= lookupTag(token);          while( token= strtok(NULL, " \n") ) {              tokens[tokenCtr++]= token;              _table[j][k++]= lookupTag(token);          }          ++j;      }  #ifdef DEBUG      fprintf(stderr,"Table\n");      for( int i= 0; i < _count; ++i ) {          for( int j= 0; j < _size; ++j ) {              fprintf(stderr,"%d ",_table[i][j]);          }          fprintf(stderr,"\n");      }  #endif      fclose(file);  }  //------------------------------------------------------ IdiomTable::~IdiomTable() {      delete _payoff;      for ( int i=0; i <= _count; ++i ) {          delete _table[i];      }      delete _table;  }  //------------------------------------------------------ int IdiomTable::idiomPayoff(int x, int y) {      return _payoff[y];  }  int IdiomTable::isOpRepeated(int x){      return x >= DUP_FIRST && x <= DUP_LAST;  }  int IdiomTable::isOpFunction(int x){      if( x >= F_FIRST && x <= F_LAST) {          return 1;      } else {          return 0;      }  }  ________________________________________________________  /* number.c */  #include <stdio.h>  #include "Select.h"  #include "Tree.h"  #include "Bucket.h"  #include "Expr.h"  //------------------------------------------------------ void numberTree( Expr * expr ) {      Tree *tree= expr->getTree();      int depth= expr->getDepth();      int size= expr->getSize();      int * height= expr->getHeight();      int unique= expr->getUnique();  #ifdef DEBUG_IN      fprintf(stderr,">number\n");      for( int i= 0; i<= expr->getSize(); ++i )          fprintf(stderr,"[%2d] %2d %2d %2d %2d\n",                          i, tree[i].getLeft(),                          tree[i].getRight(),                          tree[i].getLink(),tree[i].                          getNumber());      fprintf(stderr,"\n");  #endif      int k, b1, b2, left, right, node, lNum, rNum;      int b1Chain= 0;      int b2Chain= 0;      Bucket * bucket1= new Bucket[size+1];      for( int k=0; k<=size; ++k ) {          bucket1[k].head= 0;          bucket1[k].link= 0;      }      Bucket * bucket2= new Bucket[size+1];      for( k=0; k<=size; ++k ) {          bucket2[k].head= 0;          bucket2[k].link= 0;      }      // for all levels of the tree      for( int i= 1; i <= depth; ++i ) {  #ifdef DEBUG_TRACE  fprintf(stderr,          "A: height[%d]= %d\n", i, height[i]);  #endif          // Bucket sort on left descendant          while( height[i] != 0 ) {              // for all nodes in one level              node= height[i];  #if 0  fprintf(stderr,          "A: node %d\n", node);  #endif              // save ID of next node to process              height[i]= tree[node].getLink();              // if we have a left descendant get              // its leaf number              left= tree[node].getLeft();  #ifdef DEBUG_TRACE  fprintf(stderr,          "A2: tree[%d].getLeft = %d\n", node, left);  #endif              if( left != 0 ) {                  lNum= tree[left].getNumber(); // *  #ifdef DEBUG_TRACE  fprintf(stderr,          "B: left %d, lNum %d\n", left, lNum);  #endif                  // if there aren’t any nodes in                  // the chain of buckets yet                  // then initialize the chain                  if( bucket1[lNum].head == 0 ) {                      bucket1[lNum].link= b1Chain;                      b1Chain= lNum;                  }                 // Put node in bucket for nodes having                 // this left son                 tree[node].setLink(bucket1[lNum].head);  #ifdef DEBUG_TRACE  fprintf(stderr,          "C: tree[%d].link= %d\n",          node, bucket1[lNum].head);  #endif                 bucket1[lNum].head= node;  #ifdef DEBUG_TRACE  fprintf(stderr,          "D: bucket1[%d].head= %d\n", lNum, node);  #endif              }          }          // Bucket sort on right descendant          while( b1Chain != 0 ) {              b1= b1Chain;              b1Chain= bucket1[b1].link;              while( bucket1[b1].head != 0 ) {                  node= bucket1[b1].head;  #ifdef DEBUG_TRACE  fprintf(stderr,          "E: node %d\n", node);  #endif              // save ID of next node to process              bucket1[b1].head= tree[node].getLink();              // if we have a right descendant get              // its leaf number              right= tree[node].getRight();                  if( right != 0 ) {                      rNum= tree[right].getNumber();  #ifdef DEBUG_TRACE  fprintf(stderr,          "F: right %d, rNum %d\n", right, rNum);  #endif                      // if there aren’t any nodes in                      // the chain of buckets yet then                      // initialize the chain                      if( bucket2[rNum].head == 0 ) {                          bucket2[rNum].link= b2Chain;                          b2Chain= rNum;                      }                      // Put node in bucket for nodes                      // having this right son                      tree[node].setLink(bucket2[rNum].head);  #ifdef DEBUG_TRACE  fprintf(stderr,           "G: tree[%d].link= %d\n",           node, bucket2[rNum].head);  #endif                      bucket2[rNum].head= node;  #ifdef DEBUG_TRACE  fprintf(stderr,          "H: bucket2[%d].head= %d\n", rNum, node);  #endif                  }              }          }          // Assign unique numbers for each          // non-empty bucket          while( b2Chain != 0 ) {              b2= b2Chain;              b2Chain= bucket2[b2].link;              unique += 1;              while( bucket2[b2].head != 0 ) {                  node= bucket2[b2].head;                  tree[node].setNumber(unique);  #ifdef DEBUG_TRACE  fprintf(stderr,          "I: tree[%d].number= %d\n",node,unique);  #endif                  bucket2[b2].head= tree[node].getLink();  #ifdef DEBUG_TRACE  fprintf(stderr,          "J: bucket2[%d].head= %d\n",          b2,tree[node].getLink());  #endif              }          }      }  #ifdef DEBUG_OUT      fprintf(stderr,"<number\n");      for( int i= 0; i<= expr->getSize(); ++i )          fprintf(stderr,                  "[%2d] %2d %2d %2d %2d\n",                  i, tree[i].getLeft(),                  tree[i].getRight(),                  tree[i].getLink(),                  tree[i].getNumber());      fprintf(stderr,"\n");  #endif  }  ________________________________________________________  /* match.c */  #include <stdio.h>  #include <stdlib.h>  #define max(a,b) (((a)>(b))?(a):(b))  #define DEBUG_OUT 1  #include "Select.h"  #include "Desc.h"  #include "Tree.h"  #include "IdiomTable.h"  #include "Expr.h"  Desc activeHead;  Desc *active= 0;  Desc accumHead;  Desc *accum= 0;  //------------------------------------------------------ void match(int vertex, Expr *expr, IdiomTable *table) {      Tree * tree= expr->getTree();      int ** idiomTable= table->getTable();      int numIdioms= table->getCount();  #ifdef DEBUG_IN  fprintf(stderr,      "\nmatch: vertex= %d, tree[vertex].getOpType= %d\n",          vertex, tree[vertex].getOpType() );  #endif      int row, col, current, bene, best;      Desc *newDesc, *desc;      Select *newSel, *chain;  // descriptors of matches in progress that have  // reached a leaf      Desc suspendHead;      suspendHead.setNext(0);      Desc *suspend= 0;  // create match descriptors for all idioms that begin  // with the same op as the first op in the expression      accumHead.setNext(0);      for(int i= 1; i <= numIdioms; ++i) {          if( idiomTable[i][1] == tree[vertex].getOpType() ) {  #ifdef DEBUG_TRACE  fprintf(stderr,  "A: vertex= %d, row= %d, col= %d,bene= %d, chain= %x\n",          vertex,i,1,0,0);  #endif              newDesc= new Desc(vertex,i,1,0,0);              if( accumHead.getNext() == 0 ) {                  accumHead.setNext(newDesc);              } else {                  accum->setNext(newDesc);                  newDesc->setPrev(accum);              }              accum= newDesc;          }      }  // update matches in progress      while( 0 != (desc= activeHead.getNext() )) {          activeHead.setNext(desc->getNext());          current= desc->getVertex();          row= desc->getRow();          col= desc->getCol();          bene= desc->getBenefit();          chain= desc->getChain();          delete desc;  #ifdef DEBUG_TRACE  fprintf(stderr,  "B: curr= %d, row= %d, col= %d, bene= %d, chain= %x\n",          current,row,col,bene,chain);  #endif          int opcode= idiomTable[row][col+1];          if( table->isOpFunction(opcode) ) {  #ifdef DEBUG_TRACE  fprintf(stderr,  "0) idiomTable[%d][%d]= %d, isOpFunction= %d\n",          row, col+1, opcode,          table->isOpFunction(opcode));  #endif  // 1) a function or constant matching the vertex              if( opcode == tree[vertex].getOpType() ) {  #ifdef DEBUG_TRACE  fprintf(stderr,  "1)curr= %d, row= %d, col+1= %d, bene= %d, chain= %x\n",          current,row,col+1,bene,chain);  #endif  // put new descriptor on accumulated list                  newDesc= new Desc(current,row,col+1,                                    bene,chain);                  if( accumHead.getNext() == 0 ) {                      accumHead.setNext(newDesc);                  } else {                      accum->setNext(newDesc);                      newDesc->setPrev(accum);                  }                  accum= newDesc;              }  // 2) a repeated operand matching the vertex          } else if ( table->isOpRepeated(opcode) ) {  #ifdef DEBUG_TRACE  fprintf(stderr,  "2)curr= %d, row= %d, col+1= %d, bene= %d, chain= %x\n",          current,row,col+1,bene,chain);  #endif              if( tree[vertex].getNumber() ==                  tree[expr->firstOccur(opcode)].                             getNumber() ) {  // put new descriptor on the suspended list                  newDesc= new Desc(current,row,col+1,                                     bene,chain);                  if( suspendHead.getNext() == 0 ) {                      suspendHead.setNext(newDesc);                  } else {                      suspend->setNext(newDesc);                      newDesc->setPrev(suspend);                  }                  suspend= newDesc;  #ifdef DEBUG_TRACE  fprintf(stderr,  "3)curr= %d, row= %d, col+1= %d, bene= %d, chain= %x\n",          current,row,col+1,bene,chain);  #endif              }          } else {  // put vertex at the end of the chain for  // this descriptor              newSel= new Select(vertex);              if( chain == 0 ) {                  chain= newSel;              } else {                  Select * link;                  for( link=chain; link->getNext() != 0;                       link=link->getNext())                  { }                  link->setNext(newSel);              }  // put new descriptor on the suspended list              newDesc= new Desc(current,row,col+1,                                 bene,chain);              if( suspendHead.getNext() == 0 ) {                  suspendHead.setNext(newDesc);              } else {                  suspend->setNext(newDesc);                  newDesc->setPrev(suspend);              }              suspend= newDesc;  #ifdef DEBUG_TRACE  fprintf(stderr,  "4)curr= %d, row= %d, col+1= %d, bene= %d, chain= %x\n",          current,row,col+1,bene,chain);  #endif          }      }      activeHead.setNext(accumHead.getNext());      best= 0;      Select * select= 0;      Select selectHead;      selectHead.setNext(select);  // depth first traversal of descendants in expression      int left= tree[vertex].getLeft();      if( left != 0 ) {  #ifdef DEBUG_TRACE  fprintf(stderr,          "C: tree[%d].getLeft()= %d, best= %d\n",          vertex, left, best);  #endif          match(left, expr, table);          best= tree[left].getBenefit();  #ifdef DEBUG_TRACE  fprintf(stderr,          "\nD: vertex= %d, best= %d\n",          vertex,best);  #endif          newSel= new Select(left);          if( selectHead.getNext() == 0 ) {              selectHead.setNext(newSel);          } else {              select->setNext(newSel);          }          select= newSel;  #ifdef DEBUG_TRACE  fprintf(stderr,"D1: ");  for( Select *p= select; p != 0; p= p->getNext() ) {  fprintf(stderr,"%d ",p->getVertex()); }  fprintf(stderr,"\n");  #endif      }      int right= tree[vertex].getRight();      if( right != 0 ) {  #ifdef DEBUG_TRACE  fprintf(stderr,          "E: tree[%d].getRight()= %d, best= %d\n",          vertex, right, best);  #endif          match(right, expr, table);          best += tree[right].getBenefit();  #ifdef DEBUG_TRACE  fprintf(stderr,          "\nF: vertex= %d, best= %d\n",          vertex,best);  #endif          newSel= new Select(right);          if( selectHead.getNext() == 0 ) {              selectHead.setNext(newSel);          } else {              select->setNext(newSel);          }          select= newSel;  #ifdef DEBUG_TRACE  fprintf(stderr,"F1: ");  for( Select *p= select; p != 0; p= p->getNext() ) {  fprintf(stderr,"%d ",p->getVertex()); }  fprintf(stderr,"\n");  #endif      }      accum= 0;      accumHead.setNext(accum);      while( 0 != ( desc= activeHead.getNext()) )  {          activeHead.setNext(desc->getNext());          current= desc->getVertex();          row= desc->getRow();          col= desc->getCol();          bene= desc->getBenefit();          chain= desc->getChain();          delete desc;  #ifdef DEBUG_TRACE  fprintf(stderr,  "G: curr= %d, row= %d, col= %d, bene= %d, \          chain= %x; vertex= %d\n",          current,row,col,bene,chain,vertex);  #endif  // was this descriptor initiated by this vertex?          if( current == vertex ) {  #ifdef DEBUG_TRACE  fprintf(stderr,          "H: MATCH idiom= %d, vertex= %d\n",          row,vertex);  #endif              if( best < table->idiomPayoff(vertex,row) + bene ) {  #ifdef DEBUG_TRACE  fprintf(stderr,       "I: best= %d, idiomPayoff(%d,%d) = %d, bene= %d\n",       best, vertex, row,       table->idiomPayoff(vertex,row), bene);  #endif                  select= new Select(row);                  selectHead.setNext(select);                  select->setNext(chain);                  best= max(best, table->idiomPayoff(                            vertex,row)+bene);              }  #ifdef DEBUG_TRACE  fprintf(stderr,  "J: curr= %d, row= %d, col= %d, bene= %d, chain= %x\n",          current,row,col,bene,chain);  #endif          } else {              newDesc= new Desc(current,row,col,                                bene,chain);              if( accumHead.getNext() == 0 ) {                  accumHead.setNext(newDesc);              } else {                  accum->setNext(newDesc);                  newDesc->setPrev(accum);              }              accum= newDesc;          }          tree[vertex].setBenefit(best);          tree[vertex].setSelect(select);  #ifdef DEBUG_TRACE  fprintf(stderr,          "K: tree[%d]: benefit= %d, select= %x\n",          vertex,best,select);  #endif  #ifdef DEBUG_OUT  if( select != 0 && select->getNext() != 0 ) {  fprintf(stderr, "IDIOM: %d\n",select->getVertex());  fprintf(stderr, "VARBS: ");  for( select= select->getNext(); select != 0;       select= select->getNext()) {      fprintf(stderr,"%d ",select->getVertex()); }  fprintf(stderr,"\n");  }  #endif      }      activeHead.setNext(accumHead.getNext());      active= accum;  // reactivate suspended descriptors      while( 0 != (desc= suspendHead.getNext()) ) {          suspendHead.setNext(desc->getNext());          current= desc->getVertex();          row= desc->getRow();          col= desc->getCol();          bene= desc->getBenefit();          chain= desc->getChain();          delete desc;  #ifdef DEBUG_TRACE  fprintf(stderr,  "L:current= %d, row= %d, col= %d, bene= %d, chain=%x\n",          current,row,col,bene,chain);  #endif  // update benefit field and move to active list          newDesc= new Desc(current,row,col,                            bene+best,chain);          if( activeHead.getNext() == 0 ) {              activeHead.setNext(newDesc);          } else {              active->setNext(newDesc);              desc->setPrev(active);          }          active= newDesc;      }  }  ________________________________________________________  /* main.c */  #include <stdio.h>  #include <stdlib.h>  #include "IdiomTable.h"  #include "Select.h"  #include "Desc.h"  #include "Tree.h"  #include "Opcode.h"  #include "Expr.h"  void numberTree(Expr *);  void match(int, Expr *, IdiomTable *);  int main(int argc, char **argv ) {      Expr * expr= new Expr(argv[1]);      numberTree(expr);      IdiomTable * table= new IdiomTable("table.txt");      match(1, expr, table );  }