treeform.C

Go to the documentation of this file.

// treeform.C

/*
 * LEGO Treegion Formation Tool
 * by Bill Havanki
 * based on code by Sanjeev Banerjia
 *
 * Initiated February 27, 1997
 * Completed (first version) March 19, 1997
 *
 * Syntax:
 * treeform [options] <input Rebel file> [<output Rebel file>]
 *   input Rebel file - Rebel file where treegions will be formed
 *   output Rebel file - Rebel file with treegions formed
 *                       (default = rebelfile_tree.el)
 *
 * 5/15/97 WAH:  Added support for tail duplication.
 * 5/16/97 WAH:  Added support for hammock conversion.
 * 5/19/97 WAH:  Changed to using knobs.
 * 6/12/97 WAH:  Added h_max_height_expansion and h_max_code_expansion
 *               knobs.
 * 6/13/97 WAH:  Added saplings_by_weight knob.
 * 6/16/97 WAH:  Finished hammock conversion knob implementations.
 * 7/22/97 WAH:  Added traceunform, RemoveTreeAttributes, treereform functions;
 *               treegions will be placed where root was, not at end.
 * 7/23/97 WAH:  Proc is now flagged with HAS_TREE.
 * 9/18/97 WAH:  Fixed treeid incrementing.
 * 10/2/97 WAH:  Moved construction algorithms from IR to here; added
 *               blockmap attribute creation.
 * 10/28/97 WAH: Added knob to control whether blocks with setjmp may
 *               be tail duplicated.
 * 1/22/98 WAH:  Proc is now flagged with HAS_HB if hammocks are made.
 * 3/23/98 WAH:  Updated dag usage.
 * 4/6/98 WAH:   Reduced machine instantiations to one per treeform call.
 * 4/13/98 WAH:  Switched to LEGO Util version of TailDuplicate.
 * 11/20/98 MDJ: Fixed bug in treeform(), no longer sensitive to the order of 
 *               BB within a procedure.
 */

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include "lego.H"
#include "legoMach.H"
#include "legoUtil.H"
#include "legoDAG.H"
#include "treeform.H"
#include "hyperform.H"
#include "TinkerKnobs.H"

#include "loopdetect.H" //HZ for loop edge detection

//#define TREEFORM_DEBUG
#ifdef TREEFORM_DEBUG
#define dprintf(s) fprintf s
#define OUTF stderr
#else
#define dprintf(s)
#endif // TREEFORM_DEBUG

// === CONSTRUCTION =================================================

#define LEGOTREE_FULL (0)
#define LEGOTREE_LINEAR (1)

/*
 * AddBranchAccAttrs
 *   proc = procedure to add branch accuracy attributes to 
 *
 * Add branch accuracy attributes to each conditional branch in this 
 * procedure based on profiling data stored in BRaNCH_PT and branch.acc
 */
static void
AddBranchAccAttrs (legoProc *proc, char *branch_pt_file, char *branch_acc_file)
{

char pname[1000];
int found;
int size, profile, mapping, node_id, accesses, correct, incorrect;
float accuracy; 

  int region_count=proc->GetCount();
  for(int j=0;j<region_count;j++)
    {
      legoRegion *region_ptr=(legoRegion *)proc->GetItem(j);
      if (IS_BLOCK( region_ptr->GetRegionType() ) ) {
        opList *entry_op_list=region_ptr->GetEntryOpsPtr();
        legoOp *op_ptr=entry_op_list->GetOpPtr();
        for(;op_ptr!=NULL;op_ptr=op_ptr->GetNextLink())
          {
            int op_code=op_ptr->GetOpcode();
            //if(op_code==BRCT)
            if(op_ptr->IsBRCONDOp())
              {
                FILE *branch_pt_fp = fopen(branch_pt_file,"r");
                FILE *branch_acc_fp = fopen(branch_acc_file,"r");
                found = FALSE;
                while(fscanf(branch_pt_fp,"Proc:%s size=%d\n",&pname,&size)==2)
                  {
                    if (strcmp(pname, "_MaiN") == 0) {
                      strcpy(pname, "_main");
                    }
                    fscanf(branch_pt_fp,"profile\tmapping\tnode_id\n");
                    if (strcmp(pname, proc->GetProcName()) == 0) {
                      for(int i=0;i<size;i++)
                        {
                          fscanf(branch_pt_fp,"%d\t%d\t%d\n",&profile,&mapping,&node_id);
                          if (node_id == op_ptr->GetOpId()) {
                            for (int m=0; m<mapping; m++) {
                              fscanf(branch_acc_fp,"%d\t%d\t%d\t%d\t%f\n",&i,&accesses,&correct,&incorrect,&accuracy);
                            }
                            // here is the accuracy info for this BRCT
                            fscanf(branch_acc_fp,"%d\t%d\t%d\t%d\t%f\n",&i,&accesses,&correct,&incorrect,&accuracy);
                            legoOprd *oprd = new legoOprd;
                            oprd->SetOprdType (OT_LITERAL_F);
                            oprd->SetLiteralFloat (accuracy);
                            
                            AddLcAttribute ("branch_acc", oprd, op_ptr, (legoProc *) FindParentRegionType (RT_PROC, op_ptr));

                            oprd = new legoOprd;
                            oprd->SetOprdType (OT_LITERAL_I);
                            oprd->SetLiteralInteger (i);
                            
                            AddLcAttribute ("branch_mapping", oprd, op_ptr, (legoProc *) FindParentRegionType (RT_PROC, op_ptr));

                            found = TRUE;
                            break;
                          } 
                        }
                    }
                    else {
                      for(int i=0;i<size;i++)
                        {
                          fscanf(branch_pt_fp,"%d\t%d\t%d\n",&profile,&mapping,&node_id);
                        }
                    }
                    if (found) break; 
                  }
                fclose(branch_pt_fp);
                fclose(branch_acc_fp);
              }
          }
      }
      else { // otherwise this is a treegion
        int treegion_bb_count=region_ptr->GetCount();
        for(int k=0;k<treegion_bb_count;k++) {
          legoRegion *treegion_bb_ptr=(legoRegion *)region_ptr->GetItem(k);
          opList *entry_op_list=treegion_bb_ptr->GetEntryOpsPtr();
          legoOp *op_ptr=entry_op_list->GetOpPtr();
          for(;op_ptr!=NULL;op_ptr=op_ptr->GetNextLink())
            {
              int op_code=op_ptr->GetOpcode();
              //if(op_code==BRCT)
              if(op_ptr->IsBRCONDOp())
                {
                FILE *branch_pt_fp = fopen(branch_pt_file,"r");
                FILE *branch_acc_fp = fopen(branch_acc_file,"r");
                found = FALSE;
                while(fscanf(branch_pt_fp,"Proc:%s size=%d\n",&pname,&size)==2)
                  {
                    if (strcmp(pname, "_MaiN") == 0) {
                      strcpy(pname, "_main");
                    }
                    fscanf(branch_pt_fp,"profile\tmapping\tnode_id\n");
                    if (strcmp(pname, proc->GetProcName()) == 0) {
                      for(int i=0;i<size;i++)
                        {
                          fscanf(branch_pt_fp,"%d\t%d\t%d\n",&profile,&mapping,&node_id);
                          if (node_id == op_ptr->GetOpId()) {
                            for (int m=0; m<mapping; m++) {
                              fscanf(branch_acc_fp,"%d\t%d\t%d\t%d\t%f\n",&i,&accesses,&correct,&incorrect,&accuracy);
                            }
                            // here is the accuracy info for this BRCT
                            fscanf(branch_acc_fp,"%d\t%d\t%d\t%d\t%f\n",&i,&accesses,&correct,&incorrect,&accuracy);
                            legoOprd *oprd = new legoOprd;
                            oprd->SetOprdType (OT_LITERAL_F);
                            oprd->SetLiteralFloat (accuracy);
                            
                            AddLcAttribute ("branch_acc", oprd, op_ptr, (legoProc *) FindParentRegionType (RT_PROC, op_ptr));

                            oprd = new legoOprd;
                            oprd->SetOprdType (OT_LITERAL_I);
                            oprd->SetLiteralInteger (i);
                            
                            AddLcAttribute ("branch_mapping", oprd, op_ptr, (legoProc *) FindParentRegionType (RT_PROC, op_ptr));

                            found = TRUE;
                            break;
                          } 
                        }
                    }
                    else {
                      for(int i=0;i<size;i++)
                        {
                          fscanf(branch_pt_fp,"%d\t%d\t%d\n",&profile,&mapping,&node_id);
                        }
                    }
                    if (found) break; 
                  }
                fclose(branch_pt_fp);
                fclose(branch_acc_fp);
                }
            }
        }
      }
    } 
} // end AddBranchAccAttrs

/*
 * DFS
 *   tree = treegion to construct
 *   begin = first block in tree
 *   treetype = as in construct
 *   returns:  tree saplings
 *
 * Performs a standard recursive DFS (depth-first-search) of the block.
 * First, this block is checked, and a ref to it is added if needed.
 * Then, its successors are searched; this adds to the chain of refs of
 * those that cannot be integrated.  This list is returned.
 */
static regionList *
DFS (legoTreegion *tree, legoRegion *begin, int treetype)
{
  enum regionTypes type;
  regionList *localparents, *localchildren;

  regionList *list, *newlist, *nowlist, *temp;
  legoRegion *now;
  legoRegion *nextopparent, *pregion, *bestregion = NULL;
  int i, dontintegrate;
  double weight;
  int removed = FALSE;
  legoRegion *predecessor; 

  list = NULL;
  nowlist = new regionList (begin);  // list of blocks left to consider
  //  parlist = new regionList (beginpar);  // list of parents for those blocks

  while (nowlist != NULL)
    {
      now = nowlist->GetRegionPtr();

      // Dequeue nowlist and parlist immediately!
      temp = nowlist;
      nowlist = nowlist->GetNextListPtr();
      temp->SetNextListPtr (NULL);
      delete temp;

      type = now->GetRegionType();
      dontintegrate = 0;

      dprintf ((OUTF, "DFS: on block %d, type %d.\n", now->GetRegionId(),
                type));

      // Before doing anything, make sure now isn't already in
      // a treegion.
      for (pregion = now->GetParentPtr(); pregion->GetRegionType() != RT_PROC;
           pregion = pregion->GetParentPtr())
        if (pregion->GetRegionType() == RT_TREE) break;

      if (pregion->GetRegionType() == RT_TREE)
        {
          dprintf ((OUTF, "DFS: can't integrate - in a tree already!\n"));
          dontintegrate = 1;
        } // end if

      // First check this one - if it has more than two previous
      // regions, it's no good.  If it isn't a block, it's no good.
      if ((dontintegrate == 0) && !(IS_BLOCK(type)))
        {
          dprintf ((OUTF, "DFS: can't integrate - not a block!\n"));
          dontintegrate = 1;
        } // end if

      localparents = now->GetParents();
      if ((dontintegrate == 0) && localparents != NULL &&
          localparents->GetRegionPtr() != NULL)
        {
          // mdj - 5/15/99: Need to break treegions at setjump/longjump 
          // boundaries. Don't integrate if previous block contained a 
          // setjump
          if ((localparents != NULL) && (localparents->GetRegionPtr() != NULL)
              && (now != tree->GetRoot()) && 
              (FindLcAttribute( "set_jmp_present", 
                               localparents->GetRegionPtr()) != NULL))
            {
              // previous block contains setjump. Next block must be a treeRoot
              dprintf ((OUTF, "DFS: can't integrate - set_jmp_present in previousblock!\n"));
              dontintegrate = 1;
            } // end if
        }
      if ((dontintegrate == 0) && localparents != NULL &&
          localparents->GetRegionPtr() != NULL)
        {
          // there is one previous op ... maybe can't integrate
          localparents = localparents->GetNextListPtr();
          if (localparents != NULL && localparents->GetRegionPtr() != NULL
              && now != tree->GetRoot())
            {
              // there is 2+ prev ops and it's not the root - can't integrate
              dprintf ((OUTF, "DFS: can't integrate - multiple inedges!\n"));
              dontintegrate = 1;
            } // end if
        } // end if
      
      if ((dontintegrate)) {
        newlist = new regionList (now);
        //        cerr << "Adding block " << now->GetRegionId() << " to regionList; BlockPtr = " << now << "\n";
        if (list != NULL)
          list->Concatenate (newlist);
        else
          list = newlist;
        
        continue;  // while (nowlist != NULL)
      } // end if
      
      dprintf ((OUTF, "DFS: integrating block %d...\n", now->GetRegionId()));
      // there is exactly one inedge ... can add after removing from current
      // parent.

      // First, see if now can be removed completely (merged with predecessor)
      if (now != tree->GetRoot()) {
        // if we will be able to remove, will need predecessor
        // (there will be only one predecessor if can be removed)
        predecessor = now->GetParents()->GetRegionPtr(); 
        removed = RemoveUncondBranch(now);
      } // end if
      
      if (removed) { 
        localchildren = predecessor->GetChildren(); 
        bestregion = NULL; weight = -1.0;
      }
      else { // Add to tree without merging
        pregion = now->GetParentPtr();
        if (pregion != NULL)
          for (i = 0; i < pregion->GetCount(); i++)
            if (pregion->GetItem(i) == (void *) now)
              {
                pregion->Detach(i);
                break;
              } // end if (, for, if)
        tree->AddItem (now);
        now->SetParentPtr (tree);
        
        // Loop through successors of now.
        dprintf ((OUTF, "DFS: <<<\nDFS: Ready to enqueue successors of %d...\n",
                  now->GetRegionId()));
        
        localchildren = now->GetChildren(); bestregion = NULL; weight = -1.0;
      }
      while (localchildren != NULL)
        {
          nextopparent = localchildren->GetRegionPtr();
          if (nextopparent != NULL)
            {
              if (treetype == LEGOTREE_FULL)
                {
                  //          newlist = DFS (nextopparent, now, treetype);
                  //          if (list != NULL)
                  //            list->Concatenate (newlist);    
                  //          else
                  //            list = newlist;
                  // Add nextopparent to nowlist et al.
                  newlist = new regionList (nextopparent);
                  newlist->SetNextListPtr (nowlist);
                  nowlist = newlist;
                  dprintf ((OUTF, "DFS: enqueued region %d.\n",
                            nextopparent->GetRegionId()));
                } // end if
              else  // treetype == LEGOTREE_LINEAR
                {
                  if (nextopparent->GetWeight() > weight)
                    {
                      weight = nextopparent->GetWeight();
                      bestregion = nextopparent;
                    } // end if
                } // end else
              localchildren = localchildren->GetNextListPtr();
            } // end if

        } // end while

      if (treetype == LEGOTREE_LINEAR && bestregion != NULL)
        {
          int addedexitopalready = 0;

          // Recurse on the best region.
          dprintf ((OUTF, "DFS: Best child is region %d!\n",
                    bestregion->GetRegionId()));
          //      newlist = DFS (bestregion, now, treetype);
          newlist = new regionList (bestregion);
          newlist->SetNextListPtr (nowlist);
          nowlist = newlist;
          dprintf ((OUTF, "DFS: enqueued region %d.\n",
                    bestregion->GetRegionId()));

          // Also add leftover children to list.
          if (removed) { 
            localchildren = predecessor->GetChildren(); 
          }
          else {
            localchildren = now->GetChildren();
          }
          while (localchildren != NULL)
            {
              nextopparent = localchildren->GetRegionPtr();
              if (nextopparent != NULL && nextopparent != bestregion)
                {
                  newlist = new regionList (nextopparent);

                  if (list != NULL)
                    list->Concatenate (newlist);
                  else
                    list = newlist;
                } // end if
              localchildren = localchildren->GetNextListPtr();
            } // end while
        } // end if

      dprintf ((OUTF, "DFS: Done enqueueing successors of %d.\nDFS: >>>\n",
                now->GetRegionId()));
    } // end while
  return list;
} // end DFS

/*
 * Construct
 *   tree = treegion to construct
 *   start = first basic block to go from
 *   treetype = LEGOTREE_FULL for full treegion, LEGOTREE_LINEAR for
 *     linear regions
 *
 * From start, builds a single entry acyclic region or treegion.
 * It also records those basic blocks which could not be added to
 * the treegion as the treegion children.
 */
void
Construct (legoTreegion *tree, legoRegion *start,
           int treetype = LEGOTREE_FULL)
{
  enum regionTypes type;

  // Basic initialization...
  tree->SetInEdgesPtr (NULL);
  tree->SetOutEdgesPtr (NULL);
  tree->SetFlagPtr (NULL);
  tree->SetEntryOpsPtr (NULL);
  tree->SetExitOpsPtr (NULL);
  tree->SetRegionAttrListPtr (NULL);

  // Bail if nowhere to start or if start is not a block.
  if (start == NULL)
    return;
  type = start->GetRegionType();
  if (!(IS_BLOCK(type)))
    return;
  tree->SetRoot (start);

  // Now, do a DFS search from start down to the succeeding
  // basic blocks.
  tree->SetSaplings (DFS (tree, start, treetype));

  tree->RefreshOpsAndEdges();
  return;
} // end Construct

/*
 * ContinueConstruction
 *   tree = treegion to construct
 *
 * Continues to build upon the current treegion, also updating the
 * treegion saplings.
 */
static void
ContinueConstruction (legoTreegion *tree)
{
  enum regionTypes type;
  int i, originalcount;
  legoRegion *treeblock, *tbchild;
  regionList *tbkids, *list;
  unsigned index;

  // First, blow away all exit ops and saplings.
  delete tree->GetExitOpsPtr();
  tree->SetExitOpsPtr (NULL);
  delete tree->GetSaplings(); tree->SetSaplings (NULL);

  // Now, for each block in the treegion, DFS on each child not in
  // the tree.
  originalcount = tree->GetCount();
  for (i = 0; i < originalcount; i++)
    {
      treeblock = (legoRegion *) tree->GetItem(i);
      tbkids = treeblock->GetChildren();
      while (tbkids != NULL)
        {
          tbchild = tbkids->GetRegionPtr();
          // Update tbkids now, DFS call can corrupt this entry if block 
          // is remove during RemoveUncondBranch() in DFS()
          tbkids = tbkids->GetNextListPtr();
          if (tbchild != NULL)
            // Try to find tbchild in treegion.
            index = tree->Search (tbchild);

          if (index == MAX_UNSIGNED)  // no match => not in tree => DFS it
            {
              list = DFS (tree, tbchild, LEGOTREE_FULL);
              if (tree->GetSaplings() != NULL)
                tree->GetSaplings()->Concatenate (list);
              else
                if (list != NULL)
                  tree->SetSaplings (new regionList (*list));
            } // end if

        } // end while

    } // end for

  tree->RefreshOpsAndEdges();
  return;
} // end ContinueConstruction

/*
 * Deconstruct
 *   tree = treegion to deconstruct
 *
 * Empties a treegion, marking the component blocks with the treegion id. After
 * this method finishes, the treegion may be removed from its container and
 * deleted.
 */
void
Deconstruct (legoTreegion *tree)
{
  legoRegion *region, *pregion;
  legoProc *proc;
  int i, count;
  unsigned treeloc;

  for (region = tree->GetParentPtr();
       region != NULL && region->GetRegionType() != RT_PROC;
       region = region->GetParentPtr())
    /* do nothing */;
  if (region == NULL)
    {
      LegoNonFatal ("Deconstruct (treegion)",
                    "Can't find proc of treegion %d.", tree->GetRegionId());
      return;
    } // end if
  proc = (legoProc *) region;
  pregion = tree->GetParentPtr();  // not NULL, or would have stopped be4

  // Now, detach each region from treegion and place into trace container.
  count = tree->GetCount();
  for (i = 0; i < count; i++)
    {
      region = (legoRegion *) tree->GetItem(0);  // 0, not i, since will Detach

      treeloc = pregion->Search (tree);
      if (treeloc == MAX_UNSIGNED)
        {
          LegoNonFatal ("Deconstruct (treegion)",
                        "Couldn't find treegion %d in proc.",
                        tree->GetRegionId());
          return;
        } // end if
      tree->Detach (0);
      pregion->Insert (region, treeloc);
      region->SetParentPtr (pregion);
    } // end for

  return;
} // end Deconstruct

/*
 * Reconstruct
 *   tree = treegion to reconstruct
 *   root = root block of treegion
 *
 * Reforms a treegion starting from the root block by following "tree"
 * attributes with the same id.
 */
static void
Reconstruct (legoTreegion *tree, legoRegion *root)
{
  legoRegion *region, *pregion, *nextregion;
  attrs *treeattr;
  regionList *treelist, *temp, *regionchildren;
  unsigned index;
  int treeid;
  
  // Basic initialization ...
  tree->SetInEdgesPtr (NULL);
  tree->SetOutEdgesPtr (NULL);
  tree->SetFlagPtr (NULL);
  tree->SetEntryOpsPtr (NULL);
  tree->SetExitOpsPtr (NULL);
  tree->SetRegionAttrListPtr (NULL);
  
  //  SetWeight (root->GetWeight());
  tree->SetWeight (0.0);

  // Bail if nowhere to start or if root is not a block.
  if (root == NULL)
    return;
  if (!(IS_BLOCK(root->GetRegionType())))
    return;

  tree->SetRoot (root);
  pregion = root->GetParentPtr();
  if (pregion == NULL)
    {
      LegoNonFatal ("Reconstruct (treegion)",
                    "Couldn't find parent region of region %d.",
                    root->GetRegionId());
      return;
    } // end if

  // Set up DFS queue and proceed.
  treelist = new regionList (root);
  while (treelist != NULL)
    {
      region = treelist->GetRegionPtr();
      temp = treelist;
      treelist = treelist->GetNextListPtr();
      temp->SetNextListPtr (NULL);
      delete temp;

      treeattr = FindLcAttribute ("tree", region);
      if (treeattr == NULL || treeattr->GetAttrOprdPtr() == NULL)
        {
          
          dprintf ((OUTF, "legoTreegion::Reconstruct: Couldn't find tree "
                   "attribute of region %d.\n", region->GetRegionId()));
          if (region == root)
            {
              LegoNonFatal ("Reconstruct (treegion)",
                            "Root %d lacks tree attribute.",
                            root->GetRegionId());
              return;
            } // end if
          else
            continue;
        } // end if

      if (region == root)
        {
          treeid = treeattr->GetAttrOprdPtr()->GetLiteralInteger();
          dprintf ((OUTF, "legoTreegion::Reconstruct: Rebuilding treegion "
                    "%d.\n", treeid));
          tree->SetRegionId (treeid);
        } // end if
      else if (treeattr->GetAttrOprdPtr()->GetLiteralInteger() != treeid)
        {
          dprintf ((OUTF, "legoTreegion::Reconstruct: Region %d belongs "
                    "to a different treegion.\n", region->GetRegionId()));
          continue;
        } // end else if

      // Move region from pregion to treegion.
      index = pregion->Search (region);
      if (index == MAX_UNSIGNED)
        {
          LegoNonFatal ("Reconstruct (treegion)",
                        "Couldn't find region %d in region %d.",
                        region->GetRegionId(), pregion->GetRegionId());
          break;
        } // end if

      dprintf ((OUTF, "legoTreegion::Reconstruct: Moving block %d into "
                "trace.\n", region->GetRegionId()));
      pregion->Detach (index);
      tree->AddItem (region);
      region->SetParentPtr (tree);

      // Queue up the successors of region for consideration next.
      for (regionchildren = region->GetChildren();
           regionchildren != NULL;
           regionchildren = regionchildren->GetNextListPtr())
        {
          nextregion = regionchildren->GetRegionPtr();
          if (nextregion == NULL) continue;
          if (nextregion->IsContainedIn (tree)) continue;

          temp = new regionList (nextregion);
          temp->SetNextListPtr (treelist);
          treelist = temp;
        } // end for
      
    } // end while
  
  dprintf ((OUTF, "Reconstruct: Stopping treegion.\n"));
  tree->RefreshOpsAndEdges();
  return;
} // end Reconstruct

// === FORMATION ====================================================

/*
 * RegionRemoveTreeAttributes
 *   region = region within which attributes are removed
 *   proc = proc which contains region
 *
 * Removes region "tree" attributes from region and recursively
 * from its components.
 */
static void
RegionRemoveTreeAttributes (legoRegion *region, legoProc *proc)
{
  RemoveLcAttribute ("tree", region, proc);

  if (IS_BLOCK(region->GetRegionType()))
    return;
  for (int i = 0; i < region->GetCount(); i++)
    RegionRemoveTreeAttributes ((legoRegion *) region->GetItem(i), proc);

  return;
} // end RegionRemoveTreeAttributes

/*
 * RemoveTreeAttributes
 *   proc = procedure within which attributes are removed
 *
 * Removes region "tree" attributes from all regions in a proc.
 */
static void
RemoveTreeAttributes (legoProc *proc)
{
  RegionRemoveTreeAttributes ((legoRegion *) proc, proc);
} // end RemoveTreeAttributes

// Slightly modified from list_scheduler::DescendantofBlock()
// 
// descendantofblock: Returns YES if this operation 
// belongs to a block which is a descendant of the 
// block identified by a pointer of value input_block_int. 
int descendantofblock( int input_block_int, legoOp *op )
{
  
  legoRegion *block_ptr, *root_block_ptr;
  regionList *region_list;
  int block_int;
  legoTreegion *treegion; 

  block_ptr = (legoRegion *) op->GetParentBlockPtr();
  block_int = (int) block_ptr;
  
  treegion = (legoTreegion *) FindParentRegionType (RT_TREE, op);
  root_block_ptr = treegion->GetRoot();
  while ( (block_int != input_block_int) && (block_ptr != NULL) ) {
    if (block_ptr == root_block_ptr)
      break;
    region_list = block_ptr->GetParents();
    // blocks in a treegion have one and only one parent, except root block 
    // which has no parents. 
    if (region_list != NULL) {
      block_ptr = region_list->GetRegionPtr();
      block_int = (int) block_ptr;
    }
    else {
      block_ptr = NULL;
      block_int = 0;
    }
  }
  
  if (block_int == input_block_int) {
    return TRUE;
  }
  else {
    return FALSE;
  }
}

void 
lineartreesfromtreegions (legoTreegion *tree)
{

  legoRegion *root, *child, *best_child, *current_block, *bb_for_new_tree;
  double weight; 
  int children_in_tree_count, max_region_id, i;
  regionList *children, *bbs_for_new_tree, *last_bb_for_new_tree; 
  legoProc *parentproc; 
  legoTreegion *new_tree; 

  root = tree->GetRoot();
  
  // Figure out if root has more than one child within the treegion (that 
  // is not also the root block)
  current_block = root; 
  while (current_block != NULL) {
    best_child = NULL; 
    weight = -1.0;
    children_in_tree_count = 0;
    for (children = current_block->GetChildren();
         children != NULL; 
         children = children->GetNextListPtr()) {
      child = children->GetRegionPtr();
      if ((child->GetParentPtr() == tree) &&
          (child != tree->GetRoot())) {
        children_in_tree_count++;
        if (child->GetWeight() > weight) {
          weight = child->GetWeight();
          best_child = child;
        }
      }
    }
    
    // Split off treegion(s) if children_in_tree_count > 1
    if (children_in_tree_count > 1) {
      for (children = current_block->GetChildren();
           children != NULL; 
           children = children->GetNextListPtr()) {
        child = children->GetRegionPtr();
        if ((child->GetParentPtr() == tree) &&
            (child != tree->GetRoot())) {
          // split off another treegion if not best_child
          if (child != best_child) {
            parentproc = (legoProc *) FindParentRegionType (RT_PROC, tree);
            max_region_id = (parentproc->FindMaxRegionId())->GetRegionId();
            new_tree = new legoTreegion (++max_region_id);
            parentproc->AddItem (new_tree);
            new_tree->SetParentPtr (parentproc);
            
            //HZ: set new_tree's weight
            new_tree->SetWeight(child->GetWeight());
            
            bbs_for_new_tree = NULL;
            for (i = 0; i < tree->GetCount(); i++) {
              if (descendantofblock((int) child, (legoOp*)((legoRegion *)tree->GetItem(i))->GetItem(0))) {
                if (bbs_for_new_tree == NULL) {
                  bbs_for_new_tree = new regionList();
                  bbs_for_new_tree->SetRegionPtr((legoRegion *)tree->GetItem(i));
                  last_bb_for_new_tree = bbs_for_new_tree;
                }
                else {
                  last_bb_for_new_tree->SetNextListPtr(new regionList());
                  last_bb_for_new_tree = last_bb_for_new_tree->GetNextListPtr();
                  last_bb_for_new_tree->SetRegionPtr((legoRegion *)tree->GetItem(i));
                }
              }
            }
            for (;
                 bbs_for_new_tree != NULL;
                 bbs_for_new_tree = bbs_for_new_tree->GetNextListPtr()) {
              bb_for_new_tree = bbs_for_new_tree->GetRegionPtr(); 
              // detach from original tree
              for (i = 0; i < tree->GetCount(); i++) {
                if (tree->GetItem(i) == (void *) bb_for_new_tree) {
                  tree->Detach(i);
                  break;
                }
              }
              new_tree->AddItem (bb_for_new_tree);
              bb_for_new_tree->SetParentPtr (new_tree);
              if (bb_for_new_tree == child) {
                new_tree->SetRoot(bb_for_new_tree);
              }
            }
            new_tree->RefreshOps();
            new_tree->RefreshEdges();
          }
          tree->RefreshOps();
          tree->RefreshEdges();
        }
      }
    }
    current_block = best_child;
  }
}

/* Adds an attribute to each op in treegion having their original basic block ids 
   When Ops are speculated, those attributes keep info about where they are 
   exactly originated added by Emre Ozer in 04/22/1999
*/

void AddBBIdAttribute(legoProc *proc)
{
  legoTreegion *Region;
  legoBB       *BBlock;
  legoOp       *Op;
  legoOprd     *Oprd;
  attrs        *attr;
  int          BlockId;

  for(int i=0;i < proc->GetCount();i++) {
       Region=(legoTreegion *) proc->GetItem(i);
       for(int j=0; j<Region->GetCount();j++) {
          BBlock= (legoBB *) Region->GetItem(j);
          BlockId=BBlock->GetRegionId();
          for(int k=0;k<BBlock->GetCount();k++) {
            Op=(legoOp *) BBlock->GetItem(k);
            Oprd=new legoOprd;
            Oprd->SetOprdType(OT_LITERAL_I);
            Oprd->SetLiteralInteger(BlockId);
            Oprd->SetOprdDataType(DT_I);
            Oprd->SetIntValue(0);
            Oprd->SetNextOprdPtr((legoOprd *)NULL);
            Oprd->SetPrevOprdPtr((legoOprd *)NULL);
            Oprd->SetParentOpPtr((legoOp *)NULL);                  
            Oprd->SetParentAttrPtr((attrs *)NULL);
            Oprd->SetValid(1);
            AddLcAttribute("Original-Block-ID",Oprd,Op,proc);
          }
       }
  }
}



/*
 * treeform - form treegions
 *   proc = procedure within which to form treegions
 *   treeid = first treegion id - 1 ( = max region id of proc's module)
 *   K = pointer to knobs
 *   st = statistics of treegions formed
 *
 * Forms treegions in the given proc, with ids starting from treeid.
 * The various flags trigger whether certain formation options are
 * followed. If st is NULL, no statistics are logged.
 *   Parameter final: see the comments inside the function
 */
void
treeform (legoProc *proc, int& treeid, knobs *K, tree_stats *st = NULL, bool final =
true)
{
  regionList *unprocessed, *unptail, *temp, *saplist;
  legoRegion *currentregion, *parentregion;
  legoTreegion *tree;
  machine *mach = NULL;
  int RegionType, i, codesize, codesizeorig;
  int did_a_hammock = 0;
  int did_a_tail_duplication = 0, did_a_tail_duplication_sometime = 0;
  unsigned rootindex;

  char do_td, do_cascades, saplings_by_weight, do_hammocks, do_slrs, td_sj;
  int max_incoming_edges, max_path_count;
  double max_code_expansion, h_max_height_expansion, h_max_code_expansion;
  double h_max_opcount;
  double miss_predict_penalty;
  char *branch_acc_file;
  char *branch_pt_file;
  char use_branch_profile;
  long block_count;
  opList *exitopl, *out_cmerges; 
  legoRegion *root_block_ptr, *block_ptr; 
  opEdges *exit_edge;
  double weight, frequency; 
  
  int inp_start = FindFirstOutGoingReg(proc);
  int inp_end = FindLastOutGoingReg(proc);

  dprintf(( OUTF, "treeform: In proc %s...\n", proc->GetProcName() ));
  // Before we begin, flag the proc.
  AddFlag (HAS_TREE, proc);
  // dag builder and tree-traversal scheduling require that treegions 
  // consist only of BBs
  UnBindSB(proc);

  // Read in knobs.
  K->SetDefaultPanel ("rform/tree");
  K->Read ("t/d-do", do_td);
  K->Read ("t/d-max-code-expansion", max_code_expansion);
  K->Read ("t/d-merge-cascade", do_cascades);
  K->Read ("t/d-max-incoming-edges", max_incoming_edges);
  K->Read ("t/d-max-path-count", max_path_count);
  K->Read ("t/d-saplings-by-weight", saplings_by_weight);
  K->Read ("t/d-setjmps", td_sj);
  K->Read ("hammock-do", do_hammocks);
  K->Read ("hammock-max-height-expansion", h_max_height_expansion);
  K->Read ("hammock-max-code-expansion", h_max_code_expansion);
  K->Read ("hammock-max-opcount", h_max_opcount);
  K->Read ("slr-do", do_slrs);
  K->Read ("use-branch-profile", use_branch_profile);
  K->Read ("branch-acc-file", branch_acc_file);
  K->Read ("branch-pt-file", branch_pt_file);
  K->Read ("branch-miss-predict-penalty", miss_predict_penalty);

  if (st != NULL)  // get original op count
    st->op_count += proc->GetOpCount();

  if (do_hammocks) mach = new machine (K);  // make machine if necessary

  RemoveTreeAttributes (proc);  // remove old tree attributes

  if (use_branch_profile) {
    // need to add attributes for the branch accuracies based on profiling
    AddBranchAccAttrs(proc, branch_pt_file, branch_acc_file);
  }

  unprocessed = new regionList ((legoRegion *) proc->GetEntryOpsPtr()
                                ->GetOpPtr()->GetParentBlockPtr());
  unptail = unprocessed;

  while ( unprocessed != NULL )
    {
      // Dequeue the first region from the list.
      while (unprocessed != NULL && unprocessed->GetRegionPtr() == NULL)
        {  // skipping nullified entries
          dprintf ((OUTF, "treeform: Removing nullified queue entry.\n"));
          temp = unprocessed; unprocessed = unprocessed->GetNextListPtr();
          temp->SetNextListPtr (NULL); delete temp;
        } // end while
      if (unprocessed == NULL) break;
      dprintf(( OUTF, "treeform: Dequeueing region %d for tree building.\n",
                 unprocessed->GetRegionPtr()->GetRegionId() ));
      currentregion = unprocessed->GetRegionPtr();
      temp = unprocessed;
      unprocessed = unprocessed->GetNextListPtr();
      if (unprocessed == NULL) unptail = NULL;
      temp->SetNextListPtr (NULL);
      delete temp;

      // If the dequeued region has already been processed, continue.
      for (parentregion = currentregion->GetParentPtr();
           parentregion->GetRegionType() != RT_PROC;
           parentregion = parentregion->GetParentPtr())
        if (parentregion->GetRegionType() == RT_TREE) break;

      if (parentregion->GetRegionType() == RT_TREE)
        continue;

      // Make a new treegion and add it to the proc.
      dprintf(( OUTF, "treeform: Building new tree.\n" ));
      parentregion = currentregion->GetParentPtr();
      if (parentregion != NULL)
        rootindex = parentregion->Search (currentregion);
      else
        rootindex = MAX_UNSIGNED;

      tree = new legoTreegion (++treeid);
      proc->AddItem (tree);
      tree->SetParentPtr (proc);
      if (!do_slrs)
        Construct (tree, currentregion);
      else
        Construct (tree, currentregion, LEGOTREE_LINEAR);

// 11/20/98 mdj - seems like we always want to AddItem() here. Otherwise this 
// code is sensitive to the order of BB regions in a proc and crashes after 
// UNBindSB(). 
//      if (rootindex != MAX_UNSIGNED && parentregion->GetCount() < rootindex) {
//      cerr << "\n\n\n\n*** parentregion->GetCount() = " << parentregion->GetCount() << " < rootindex = " << rootindex << " ***\n" ;
//      parentregion->Insert (currentregion, rootindex);
//      }
//      else
//      proc->AddItem (tree);
//      tree->SetParentPtr (proc);
      
      for (codesizeorig = 0, i = 0; i < tree->GetCount(); i++)
        codesizeorig += ((legoRegion *) tree->GetItem(i))->GetCount();

      did_a_hammock = did_a_tail_duplication =
        ((do_td || do_hammocks) ? 1 : 0);
      did_a_tail_duplication_sometime = 0;
      while (did_a_hammock == 1 || did_a_tail_duplication == 1)
        {
          did_a_hammock = did_a_tail_duplication = 0;
          for (codesize = 0, i = 0; i < tree->GetCount(); i++)
            codesize += ((legoRegion *)
                         tree->GetItem(i))->GetCount();

          // === HAMMOCK CONVERSION ===
          // Must be modified when full hyperblocks are used in LEGO.

          while (do_hammocks)
            {
              // Find a sapling worthy of hammock conversion.
              hammock_info *hinfo;
              legoRegion *bestsap = NULL, *candsap, *hammock;
              regionList *rl;
              int subtreesize, hcroot;

              for (i = 0; i < tree->GetCount(); i++)
                {
                  // Destroying h->S, h->T, h->E, h->J blocks seems to fuck 
                  // up things such as ParentBlockPtrs of Ops. So I will 
                  // just leave them as orphaned blocks now and mark them.
                  // Now need to skip these. 
//                if (((legoRegion *)tree->GetItem(i))->IsMarked(RM_GENERAL))
//                  continue; 
                  hinfo = DetectHammock ((legoRegion *) tree->GetItem(i));
                  if (!(hinfo->HammockDetected()))
                    {
                      delete hinfo;  // internal block or no hammock off leaf
                      continue;
                    } // end if

                  candsap = hinfo->J;
                  if (candsap->GetParentPtr()->GetRegionType() == RT_TREE)
                    continue;  // can't pull in a treegion root!

                  // Add criteria here.
                  if (h_max_height_expansion > 0.0)
                    {
                      dag *DAG;
                      VectorList::iterator Front, Back;
                      legoOp *hop;
                      int height, height_orig, height_CMPP, height_side, max;

                      height = 0;  // height of entire hammock
                      height_orig = 0;  // ht. of S - ht. of 1st CMPP in S

                      for (hop = (legoOp *) hinfo->S->GetItem(0);
                           hop->IsCMPPOp() == false;   
                         //HZ:   hop->GetOpcode() < CMPP ||
                         //    hop->GetOpcode() > FCMPP_D_TRUE_AC_AC;
                           hop = hop->GetNextLink()) /* do nothing */;
                      // hop points to first CMPP in S

                      // Knobs are available...
#ifdef IA64_SUPPORT                   
                      DAG = new dag (mach, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
                      DAG = new dag (mach, K, 0, 0, 0, 0, 0, 0);
#endif
                      
                      hinfo->S->SetDAG (DAG);
                      DAG->ConstructDag (hinfo->S);
                      DAG->SetNodeHeights();
                      for (max = 0, Front = DAG->GetList()->begin(),
                             Back = DAG->GetList()->end(); Front != Back;
                           Front++)
                        {
                          if ((*Front).GetHeight() > max)
                            max = (*Front).GetHeight();
                          if ((*Front).GetOp() == hop)
                            height_CMPP = (*Front).GetHeight();
                        } // end for
                      height = max;
                      if (hinfo->S->GetRegionType() == RT_BB)
                        height_orig = max - 1; // for CMPP
                      else
                        height_orig = max - height_CMPP + 1;
                      dprintf ((OUTF, "treeform: S has height %d, original "
                                "height %d.\n", height, height_orig));
                      delete DAG; hinfo->S->SetDAG (NULL);

                      //DAG = new dag (mach, K);
#ifdef IA64_SUPPORT                   
                      DAG = new dag (mach, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
                      DAG = new dag (mach, K, 0, 0, 0, 0, 0, 0);
#endif
                      
                      hinfo->T->SetDAG (DAG);
                      DAG->ConstructDag (hinfo->T);
                      DAG->SetNodeHeights();
                      for (max = 0, Front = DAG->GetList()->begin(),
                             Back = DAG->GetList()->end(); Front != Back;
                           Front++)
                        if ((*Front).GetHeight() > max)
                          max = (*Front).GetHeight();
                      height_side = max;
                      dprintf ((OUTF, "treeform: T has height %d.\n",
                                height_side));
                      delete DAG; hinfo->T->SetDAG (NULL);

                      //DAG = new dag (mach, K);
#ifdef IA64_SUPPORT                   
                      DAG = new dag (mach, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
                      DAG = new dag (mach, K, 0, 0, 0, 0, 0, 0);
#endif
                      
                      hinfo->J->SetDAG (DAG);
                      DAG->ConstructDag (hinfo->J);
                      DAG->SetNodeHeights();
                      for (max = 0, Front = DAG->GetList()->begin(),
                             Back = DAG->GetList()->end(); Front != Back;
                           Front++)
                        if ((*Front).GetHeight() > max)
                          max = (*Front).GetHeight();
                      height += max;
                      dprintf ((OUTF, "treeform: New S+J height is %d.\n",
                                height));
                      delete DAG; hinfo->J->SetDAG (NULL);

                      if (!(hinfo->IsDelta()))
                        {
                          //DAG = new dag (mach, K);
#ifdef IA64_SUPPORT                   
                              DAG = new dag (mach, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
                              DAG = new dag (mach, K, 0, 0, 0, 0, 0, 0);
#endif
                            
                          hinfo->E->SetDAG (DAG);
                          DAG->ConstructDag (hinfo->E);
                          DAG->SetNodeHeights();
                          for (max = 0, Front = DAG->GetList()->begin(),
                                 Back = DAG->GetList()->end(); Front != Back;
                               Front++)
                            if ((*Front).GetHeight() > max)
                              max = (*Front).GetHeight();
                          if (max > height_side)
                            height_side = max;
                          dprintf ((OUTF, "treeform: New (E) side height "
                                    "is %d.\n", height_side));
                          delete DAG; hinfo->E->SetDAG (NULL);
                        } // end if

                      height += height_side;
                      dprintf ((OUTF, "treeform: Final height is %d.\n",
                                height));
                      if ((double) height > (double) height_orig *
                          h_max_height_expansion) continue;
                    } // end if

                  if (h_max_code_expansion > 0.0)
                    {
                      int opct_orig, opct;
                      legoOprd *oprd;

                      if (hinfo->S->GetRegionType() != RT_HB)
                        {
                          opct_orig = hinfo->S->GetCount();
                        } // end if
                      else
                        {
                          opct_orig = 1;  // count branch eliminated before
                          // Count ops up to the first predicated op.
                          legoOp *tempop = (legoOp *) (hinfo->S->GetItem(0));
                          oprd = tempop->GetPredOprdPtr();
                          for (int j = 0; j < hinfo->S->GetCount(); j++)
                            {
                              if (oprd != NULL && oprd->GetOprdType()
                                  != OT_LITERAL_P)
                                break;
                              tempop = tempop->GetNextLink();
                              oprd = tempop->GetPredOprdPtr();
                              opct_orig++;
                            } // end for
                        } // end else

                      opct = hinfo->S->GetCount() + hinfo->T->GetCount()
                        + hinfo->J->GetCount() - 6;
                      if (!(hinfo->IsDelta()))
                        opct += (hinfo->E->GetCount() - 3);
                      if ((double) opct > (double) opct_orig *
                          h_max_code_expansion) continue;
                    } // end if

                  if (h_max_opcount > 0.0) {
                    if (hinfo->T->GetOpCount() > h_max_opcount) continue;
                    if (!(hinfo->IsDelta()))
                      if (hinfo->E->GetOpCount() > h_max_opcount) continue;
                  }

                  bestsap = candsap; break;  // passes all tests => OK
                } // end for
              if (bestsap == NULL)
                {
                  dprintf((OUTF,"treeform: Could not find sapling worthy of "
                           "hammock conversion.\n"));
                  break;  // out of for loop
                } // end if

              dprintf ((OUTF, "treeform: Merge targeted for h-c is %d.\n",
                        bestsap->GetRegionId()));

              // Hammock convert, then continue construction.
              hcroot = (tree->GetRoot() == hinfo->S);
              // Before continuing, remove hinfo->S and hinfo->J from the
              // unprocessed queue so they don't try to spawn new treegions.
              for (temp = unprocessed; temp != NULL;
                   temp = temp->GetNextListPtr())
                if (temp->GetRegionPtr() == hinfo->J ||
                    temp->GetRegionPtr() == hinfo->S)
                  {
                    dprintf ((OUTF, "treeform: Nullifying queue entry for "
                              "region %d.\n",
                              temp->GetRegionPtr()->GetRegionId()));
                    temp->SetRegionPtr (NULL);
                  } // end if
              if ((hammock = IfConvertHammock (hinfo, K)) == NULL)
                {
                  dprintf ((OUTF, "treeform: Hammock conversion failed.\n"));
                  exit (10);
                  break;
                } // end if
              if (did_a_hammock == 0)
                {
                  did_a_hammock = 1;
                  AddFlag (HAS_HB, proc);
                } // end if
              if (hcroot) tree->SetRoot (hammock);
              ContinueConstruction (tree);  // continue building the tree

            } // end while

          // === END HAMMOCK CONVERSION ===

          // === TAIL DUPLICATION ===

          // If we can tail-duplicate, try it here and continue construction.
          while (do_td)
            {
              // Find a sapling worthy of tail duplication.
              legoRegion *bestsap = NULL, *bestsapparent = NULL, *duplicate,
                *candsap;
              regionList *rl;
              edgeList *el;
              opEdges *edge;
              int qualifies, i;
              double maxsapweight = -1.0;

              saplist = tree->GetSaplings();
              if (saplist == NULL) break;

              if (max_path_count > 0)
                {
                  opList *opl;

                  tree->RefreshExitOps();
                  for (i = 0, opl = tree->GetExitOpsPtr(); opl != NULL;
                       i++, opl = opl->GetNextListPtr()) /* do nothing */;
                  if (i > max_path_count)
                    {
                      dprintf ((OUTF, "treeform: Ending tail duplication "
                                "with %d paths.\n", i));
                      break;
                    } // end if
                } // end if

              for (temp = saplist; temp != NULL; temp = temp->GetNextListPtr())
                {
                  candsap = temp->GetRegionPtr();

                  // Destroying h->S, h->T, h->E, h->J blocks seems to fuck 
                  // up things such as ParentBlockPtrs of Ops. So I will 
                  // just leave them as orphaned blocks now and mark them.
                  // Now need to skip these. 
//                if (candsap->IsMarked(RM_GENERAL))
//                  continue; 
                  
                  if (candsap->GetParentPtr()->GetRegionType() != RT_PROC)
                    continue;  // sapling can't be in treegion already

                  if (saplings_by_weight &&
                      candsap->GetWeight() <= maxsapweight)
                    continue;  // use highest weight sapling

                  // Treegion must end with a block containing a setjmp. Don't 
                  // Continue duplication after a setjmp. 
                  if (FindLcAttribute( "set_jmp_present", 
                                      candsap->GetParents()->GetRegionPtr())
                      != NULL) 
                    continue;  

                  if (!td_sj)  // look for setjmp
                    {
                      legoOp *sjop;
                      legoOprd *sjoprd = NULL;

                      for (sjop = candsap->GetEntryOpsPtr()->GetOpPtr();
                           sjop != NULL; sjop = sjop->GetNextLink())
                        {
                          if (sjop->IsPBRROp() == false) continue;
                              //sjop->GetOpcode() != PBRR) continue;
                          sjoprd = sjop->GetSrcOprdPtr();
                          if (sjoprd->GetOprdType() != OT_LITERAL_L) continue;
                          if (strstr (sjoprd->GetLiteralLabel(), "setjmp")
                              != NULL) break;  // found setjmp
                          else
                            sjoprd = NULL;
                        } // end for
                      if (sjoprd != NULL) continue;
                    } // end if

                  if (max_code_expansion > 0.0)
                    {
                      if ((double) (codesize + 2 * candsap->GetCount()) >
                          max_code_expansion * ((double) codesizeorig))
                        continue;  // can't exceed code expansion limits
                    } // end if

                  //              candsap->SetChildren (NULL);
                  if (candsap->GetChildren() == NULL)
                    {
                      bestsap = candsap;  // if end of proc, definitely!
                      if (saplings_by_weight) continue;
                      else break;
                    } // end if

                  if (do_cascades)
                    {
                      for (i = 0, rl = candsap->GetChildren(); rl != NULL;
                           rl = rl->GetNextListPtr()) i++;
                      if (i == 1)  // if merge leads only to one place and ...
                        {
                          for (i = 0,
                                 rl = candsap->GetChildren()->GetRegionPtr()
                                 ->GetParents(); rl != NULL;
                               rl = rl->GetNextListPtr()) i++;
                          if (i > 1)
                            {
                              bestsap = candsap;  // if merge cascade, yes!
                              break;
                            } // end if
                        } // end if
                    } // end if

                  qualifies = 1;
                  for (rl = candsap->GetParents(); rl != NULL;
                       rl = rl->GetNextListPtr())
                    {
                      if (rl->GetRegionPtr()->GetParentPtr() !=
                          (legoRegion *) tree)
                        qualifies = 0;  // sapling no parents outside tree
                    } // end for
                  if (!qualifies) continue;

                  if (max_incoming_edges >= 2)
                    {
                      for (i = 0, el = candsap->GetInEdgesPtr(); el != NULL;
                           el = el->GetNextListPtr()) i++;
                      if (i > max_incoming_edges)
                        continue;  // can't have too many inedges
                    } // end if

                  bestsap = candsap;  // passes all tests => OK
                  if (!saplings_by_weight) break;
                  maxsapweight = candsap->GetWeight(); continue;
                } // end for
              if (bestsap == NULL)
                {
                  dprintf((OUTF,"treeform: Could not find sapling worthy of "
                           "tail duplication.\n"));
                  break;  // out of for loop
                } // end if

              dprintf ((OUTF, "treeform: Merge targeted for t-d is %d.\n",
                        bestsap->GetRegionId()));

              // Find some parent of bestsap in the tree.
              for (temp = bestsap->GetParents(); temp != NULL;
                   temp = temp->GetNextListPtr())
                {
                  if (!(temp->GetRegionPtr()->IsContainedIn (tree)))
                    continue;  // parent must be in tree
                  bestsapparent = temp->GetRegionPtr(); break;
                } // end for
              if (bestsapparent == NULL)
                {
                  LegoNonFatal ("treeform", "Could not find parent of "
                           "sapling %d worthy of tail duplication.",
                           bestsap->GetRegionId());
                  break;  // out of for loop
                } // end if
              dprintf ((OUTF, "treeform: T-d off block %d.\n",
                        bestsapparent->GetRegionId()));

              // Find the op in bestsapparent leading to the sapling.
              for (el = bestsapparent->GetOutEdgesPtr(); el != NULL;
                   el = el->GetNextListPtr())
                {
                  edge = el->GetEdgePtr();
                  if ((legoRegion *) (edge->GetToOpPtr()->GetParentBlockPtr())
                      == bestsap)
                    break;
                } // end for
              if (el == NULL)
                {
                  LegoNonFatal ("treeform", "Could not find exit op of "
                           "parent of sapling %d worthy of tail "
                           "duplication.", bestsap->GetRegionId());
                  break;  // out of for loop
                } // end if

              // Tail duplicate, and add duplicate to bestsap's container.
              duplicate = TailDuplicate (bestsap, edge);
              //duplicate = bestsap->TailDuplicate (edge);
              //          bestsap->GetParentPtr()->AddItem (duplicate);
              //          duplicate->SetParentPtr (bestsap->GetParentPtr());
              if (duplicate == NULL)
                {
                  dprintf ((OUTF, "treeform: Tail duplication failed.\n"));
                  exit (10);
                  break;
                } // end if
              if (duplicate == bestsap)
                dprintf ((OUTF, "treeform: Ah! Worthy sapling isn't "
                          "merge!\n"));
              else
                {
                  legoOprd *mapoprd;
                  attrs *oldattr;

                  mapoprd = new legoOprd;
                  mapoprd->SetOprdType (OT_LITERAL_I);
                  oldattr = FindLcAttribute ("blockmap", bestsap);
                  if (oldattr == NULL)
                    mapoprd->SetLiteralInteger (bestsap->GetRegionId());
                  else
                    mapoprd->SetLiteralInteger (oldattr->GetAttrOprdPtr()
                                                ->GetLiteralInteger());
                  AddLcAttribute ("blockmap", mapoprd, duplicate, proc);
                  int removed = RemoveUncondBranch(duplicate);
                  if (removed) {
                    for (temp = unprocessed; temp != NULL;
                         temp = temp->GetNextListPtr())
                      if (temp->GetRegionPtr() == duplicate )
                        {
                          dprintf ((OUTF, "treeform: Nullifying queue entry for "
                                    "region %d.\n",
                                    duplicate->GetRegionId()));
                          temp->SetRegionPtr (NULL);
                        } // end if
                  }
                  removed = RemoveUncondBranch(bestsap);
                  if (removed) {
                    for (temp = unprocessed; temp != NULL;
                         temp = temp->GetNextListPtr())
                      if (temp->GetRegionPtr() == bestsap )
                        {
                          dprintf ((OUTF, "treeform: Nullifying queue entry for "
                                    "region %d.\n",
                                    bestsap->GetRegionId()));
                          temp->SetRegionPtr (NULL);
                        } // end if
                  }
                } // end else

              dprintf ((OUTF, "treeform: Duplicate is block %d.\n",
                        duplicate->GetRegionId()));

              did_a_tail_duplication = 1;
              did_a_tail_duplication_sometime = 1;
              ContinueConstruction (tree);  // continue building the tree

            } // end while
          // === END TAIL DUPLICATION ===
        } // end big while loop

      if (st != NULL)
        {
          legoRegion *block;
          int i;
          long opct;
          double rtwt;

          st->tree_count++;
          st->block_count += tree->GetCount();
          
          for (exitopl = tree->GetExitOpsPtr(); 
               exitopl != NULL;
               exitopl = exitopl->GetNextListPtr()) {
            // cerr << "\nExit op (OpId = " << exitopl->GetOpPtr()->GetOpId() << ")\n";
            st->path_count++;
            // Assuming only one exit op per block at this point 
            // (during treeform)
            if (exitopl->GetOpPtr()->IsBRCONDOp()
                //HZ:    (exitopl->GetOpPtr()->GetOpcode() == BRCT) || 
                //(exitopl->GetOpPtr()->GetOpcode() == BRCF)
                    ) {
              weight = 0;
              for (out_cmerges = exitopl->GetOpPtr()->GetOutListPtr();
                   out_cmerges != NULL;
                   out_cmerges = out_cmerges->GetNextListPtr()) {
                if ((((legoRegion *) out_cmerges->GetOpPtr()
                      ->GetParentBlockPtr())->GetParentPtr() != tree) || 
                    (((legoRegion *) out_cmerges->GetOpPtr()
                      ->GetParentBlockPtr()) == tree->GetRoot())) {
                  exit_edge = FindControlEdge(exitopl->GetOpPtr(), 
                                              out_cmerges->GetOpPtr(), 1);
                  frequency = (double) FindEdgeFrequency(exit_edge);
                  if (frequency == -1) {
                    LegoNonFatal ("treeform", "Edge has no frequency.\n");
                  }
                  weight += frequency;
                }
              }
            }
            else { // BRUs, DUMMY_BRs, RTSs always fully exit treegion
              weight = ((legoRegion *) exitopl->GetOpPtr()->GetParentBlockPtr())->GetWeight();
            }
            // cerr << "Weight = " << weight << "\n";
            st->dynamic_path_count += weight; 
            // Find the number of blocks in this path
            for (block_count = 1, 
                 root_block_ptr = tree->GetRoot(), 
                 block_ptr = (legoRegion *) exitopl->GetOpPtr()->GetParentBlockPtr();
                 block_ptr != root_block_ptr; 
                 block_count++, 
                 block_ptr = block_ptr->GetParents()->GetRegionPtr()) {
              ; // Just count blocks
            }
            // cerr << "Blocks in path = " << block_count << "\n";          
            st->path_blocks += block_count; 
            st->dynamic_path_blocks += (block_count * weight);
          }
          
          rtwt = tree->GetRoot()->GetWeight();
          opct = 0;
          if (tree->GetCount() >= WTSIZE)
            {
              LegoFatal ("treeform", "%d blocks in tree is too big. "
                         "Recompile with a larger value of WTSIZE.",
                         tree->GetCount());
              //              exit(2);
            } // end if
          (st->block_stats[tree->GetCount()].i)++;
          (st->block_stats[tree->GetCount()].d) += rtwt;
          for (i = 0; i < tree->GetCount(); i++)
            {
              block = (legoRegion *) tree->GetItem(i);
              opct += block->GetOpCount();
              st->op_count_expanded += block->GetOpCount();
            } // end for
          if (opct >= WTSIZE)
            {
              LegoFatal ("treeform", "%d ops in tree is too big. "
                         "Recompile with a larger value of WTSIZE.",
                         opct);
              //              exit(2);
            } // end if
          (st->op_stats[opct].i)++;
          (st->op_stats[opct].d) += rtwt;
          st->total_weight += rtwt;
          
        } // end if

      
      //HZ: 
      //In the finding of the best treegion dup candidates, the procedure
      // treeform will be called several times
      // If I do this fullyresolePredicates very time, I will end up with
      // duplicated CMPPs in duplicated treegions:
      //e.g. tree1 has an CMPP <p112, p113> = ..., p111 in BB a and 
      //               an duped CMPP <p112, p113> = ..., p115 in BB b
      // Then in scheduling, if these two CMPPs are moved in the same BB, this
      // output deps will mess the program semantics.
      
      //So I will delay this fullyresolvepredicates call until the last time by
      //using a parameter final
      //
      
      // FullyResolvePredicates in the new treegion
      ClearMarks (RM_GENERAL, tree);
      if(final == true)
      {
          FullyResolvePredicates( tree->GetRoot(), NULL );
          ClearMarks (RM_GENERAL, tree);
      }

      // Add tree attributes to regions in treegion.
      for (i = 0; i < tree->GetCount(); i++)
        {
          legoOprd *treeidoprd, *oprd;

          treeidoprd = new legoOprd();
          treeidoprd->SetOprdType (OT_LITERAL_I);
          treeidoprd->SetLiteralInteger (treeid);
          if ((legoRegion *) tree->GetItem(i) == tree->GetRoot())
            {  // mark root!
              oprd = treeidoprd->AddOprd();
              oprd->SetOprdType (OT_LITERAL_I);
              oprd->SetLiteralInteger (1);
            } // end if
          AddLcAttribute ("tree", treeidoprd,
                          (legoRegion *) tree->GetItem(i), proc);
        } // end for

      // Add all saplings not in a tree already to the unprocessed list.

      for (saplist = tree->GetSaplings(); saplist != NULL;
           saplist = saplist->GetNextListPtr())
        {
          dprintf(( OUTF, "treeform: Examining sapling region %d.\n",
                     saplist->GetRegionPtr()->GetRegionId() ));

          // If the sapling belongs to another tree, continue.
          for (parentregion = saplist->GetRegionPtr()->GetParentPtr();
               parentregion->GetRegionType() != RT_PROC;
               parentregion = parentregion->GetParentPtr())
            if (parentregion->GetRegionType() == RT_TREE) break;

          if (parentregion->GetRegionType() == RT_TREE)
            continue;

          // Enqueue the unprocessed sapling into the list.
          dprintf(( OUTF, "treeform: Enqueueing sapling region %d.\n",
                     saplist->GetRegionPtr()->GetRegionId() ));
          temp = new regionList (saplist->GetRegionPtr());

          if ( unptail == NULL )
            unptail = unprocessed = temp;
          else
            {
              unptail->SetNextListPtr (temp);
              unptail = temp;
            } // end else
        } // end for

      treeid = (proc->FindMaxRegionId())->GetRegionId();  // next id (-1)
    } // end while
  
  if (did_a_tail_duplication_sometime)
    {
      dprintf ((OUTF, "treeform: Refreshing all.\n"));
      proc->RefreshAll();
    } // end if

  delete mach;  // destroy machine

  dprintf(( OUTF, "treeform: Done with proc %s.\n\n", proc->GetProcName() ));

  AddBBIdAttribute(proc);  // Emre Ozer: Attach  an attribute of original BB ids to each Op in a treegion    
    
  //HZ: Set all the weights of the treegions
  for(int tree_i = 0; tree_i < proc->GetCount(); tree_i++)
  {
      legoTreegion * tree1_ptr = (legoTreegion *)proc->GetItem(tree_i);
      tree1_ptr->SetWeight(tree1_ptr->GetRoot()->GetWeight());
  }
  if(proc->GetWeight() == 0)
      proc->SetWeight(((legoTreegion *)proc->GetItem(0))->GetWeight());
  
  return;
} // end treeform

/*
 * RegionTreeUnform
 *   region = region to look within for treegions
 *
 * Searches region and (recursively) components for treegions and deconstructs
 * those it finds.
 */
static void
RegionTreeUnform (legoRegion *region)
{
  int i;
  unsigned treeloc;
  legoRegion *component;

  for (i = 0; i < region->GetCount(); i++)
    {
      component = (legoRegion *) region->GetItem (i);
      switch (component->GetRegionType())
        {
        case RT_BB:
        case RT_SB:
        case RT_HB:
          break;
        case RT_LOOP:
        case RT_LOOPBODY:
        case RT_TRACE:
          RegionTreeUnform (component);
          break;
        case RT_TREE:
          // Deconstruct!
          Deconstruct ((legoTreegion *) component);
          treeloc = region->Search (component);
          if (treeloc == MAX_UNSIGNED)
            {
              LegoNonFatal ("RegionTreeUnform", "Can't find treegion %d in "
                            "region %d.\b", component->GetRegionId(),
                            region->GetRegionId());
              break;
            } // end if
          region->Detach (treeloc);
          delete component;
          i = -1; break;  // reset for loop
        } // end switch
    } // end for

  return;
} // end RegionTreeUnform

/*
 * treeunform
 *   proc = procedure within which to unform treegions
 *
 * Removes treegions from a procedure via deconstruction.
 */
void
treeunform (legoProc *proc)
{
  RegionTreeUnform (proc);

  // Before we quit, unflag the proc.
  RemoveFlag (HAS_TREE, proc);
  return;
} // end treeunform

/*
 * RegionTreeReform
 *   region = region to look within for treegions
 *   st = see tracereform
 *
 * Searches region and (recursively) components for treegion roots and
 * reconstructs those it can.
 */
static void
RegionTreeReform (legoRegion *region, tree_stats *st)
{
  int i;
  legoRegion *component;

  for (i = 0; i < region->GetCount(); i++)
    {
      component = (legoRegion *) region->GetItem (i);
      switch (component->GetRegionType())
        {
        case RT_BB:
        case RT_SB:
        case RT_HB:
          {
            legoTreegion *tree;
            legoRegion *parentregion;
            attrs *treeattr;
            legoOprd *treeattroprd;
            unsigned treeloc;

            dprintf ((OUTF, "treereform: Looking at block %d.\n",
                      component->GetRegionId()));
            treeattr = FindLcAttribute ("tree", component);
            if (treeattr == NULL)
              {
                dprintf ((OUTF, "treereform: No tree attribute found.\n"));
                break;
              } // end if
            treeattroprd = treeattr->GetAttrOprdPtr();
            if (treeattroprd == NULL ||
                treeattroprd->GetNextOprdPtr() == NULL ||
                treeattroprd->GetNextOprdPtr()->GetLiteralInteger() != 1)
              {
                dprintf ((OUTF, "treereform: Tree attribute found, but "
                          "not root.\n"));
                break;
              } // end if

            // Make a new treegion and add it to the proc.
            dprintf(( OUTF, "treereform: Building new treegion.\n" ));
            parentregion = component->GetParentPtr();
            if (parentregion != NULL)
              treeloc = parentregion->Search (component);
            else
              treeloc = MAX_UNSIGNED;

            tree = new legoTreegion (0);  // temporary id - Reconstruct gets it
            Reconstruct (tree, component);
            dprintf(( OUTF, "treereform: Treegion location is index %u.\n",
                      treeloc));
            if (treeloc != MAX_UNSIGNED)
              parentregion->Insert (tree, treeloc);
            else
              parentregion->AddItem (tree);
            tree->SetParentPtr (parentregion);

            if (st != NULL)
              {
                legoRegion *block;
                int i;
                long opct;
                double rtwt;

                st->tree_count++;
                st->block_count += tree->GetCount();
                rtwt = tree->GetRoot()->GetWeight();
                opct = 0;
                if (tree->GetCount() >= WTSIZE)
                  {
                    LegoFatal ("treereform", "%d blocks in tree is too "
                               "big. Recompile with a larger value of "
                               "WTSIZE.", tree->GetCount());
                    //              exit(2);
                  } // end if
                (st->block_stats[tree->GetCount()].i)++;
                (st->block_stats[tree->GetCount()].d) += rtwt;
                for (i = 0; i < tree->GetCount(); i++)
                  {
                    block = (legoRegion *) tree->GetItem(i);
                    opct += block->GetOpCount();
                    st->op_count_expanded += block->GetOpCount();
                  } // end for
                if (opct >= WTSIZE)
                  {
                    LegoFatal ("treereform", "%d ops in tree is too "
                               "big. Recompile with a larger value of "
                               "WTSIZE.", opct);
                    exit(2);
                  } // end if
                (st->op_stats[opct].i)++;
                (st->op_stats[opct].d) += rtwt;
                st->total_weight += rtwt;
              } // end if

          } // end block
          break;
        case RT_LOOP:
        case RT_LOOPBODY:
        case RT_TRACE:
          RegionTreeReform (component, st);
          break;
        case RT_TREE:
          break;  // already done!
        } // end switch
    } // end for

  return;
} // end RegionTreeUnform

/*
 * treereform
 *   proc = procedure within which to reform treegions
 *   st = statistics of traces formed
 *
 * Adds treegions to a procedure via reconstruction.
 */
void
treereform (legoProc *proc, tree_stats *st = NULL)
{
  dprintf(( OUTF, "treereform: In proc %s...\n", proc->GetProcName() ));
  // Before we begin, flag the proc.
  AddFlag (HAS_TREE, proc);

  RegionTreeReform (proc, st);
  return;
} // end treereform



//HZ:
void copy_opEdges(opEdges * orig, opEdges * dest, 
        int newEdgeId = -1, int newFromOpId = -1,
          legoOp *newFromOpPtr = NULL, int newToOpId = -1,
          legoOp *newToOpPtr = NULL)
{
    //    fprintf(stderr,"Creating OPEDGES %p\n",this);
    dest->SetEdgeType(orig->GetEdgeType());
    if (newEdgeId != -1)
      dest->SetEdgeId(newEdgeId);
    else
      dest->SetEdgeId(orig->GetEdgeId());  
    dest->SetOldEdgeId(orig->GetOldEdgeId());
    if (newFromOpId != -1)
      dest->SetFromOpId(newFromOpId);
    else
      dest->SetFromOpId(orig->GetFromOpId()); 
    if (newFromOpPtr != NULL)
      dest->SetFromOpPtr(newFromOpPtr);
    else
      dest->SetFromOpPtr(orig->GetFromOpPtr());
    dest->SetSrcPort(orig->GetSrcPort());
    dest->SetAltSrcPort(orig->GetAltSrcPort());
    dest->SetSrcPortType(orig->GetSrcPortType());
    if (newToOpId != -1)
      dest->SetToOpId(newToOpId);
    else
      dest->SetToOpId(orig->GetToOpId());  
    if (newToOpPtr != NULL)
      dest->SetToOpPtr(newToOpPtr);
    else
      dest->SetToOpPtr(orig->GetToOpPtr());  
    dest->SetDestPort(orig->GetDestPort());
    dest->SetAltDestPort(orig->GetAltDestPort());
    dest->SetDestPortType(orig->GetDestPortType());
    dest->SetEdgeUsage(orig->GetEdgeUsage());
    dest->SetEdgeStatus(orig->GetEdgeStatus());
    dest->SetEdgeLat(orig->GetEdgeLat());
    dest->SetEdgeOmega(orig->GetEdgeOmega());
    if (orig->GetEdgeAttrListPtr() != NULL)
      dest->SetEdgeAttrListPtr(new attrList (*(orig->GetEdgeAttrListPtr())));
    else
      dest->SetEdgeAttrListPtr(NULL);
//    dest->SetMarkfield(orig->GetMarkfield());
    dest->SetNextOpEdgePtr(NULL);  // will be changed anyway
}       

//Calculate the estimated execution time of the treegion constructed from
// par_tree with tail duplication of cand_tree.
// 1. calculate the ave. max dependence height of the treegion constructed from
// par_tree with tail duplication of cand_tree. Considering the generic case,
// the cand_tree duplication could duplicate the whole cand_tree or just the
// root of the cand_tree (selected by parameter dup_tree).                      
// The parameter proc is the parent ptr containing both par_tree and cand_tree.
// 2. Calculate the width effect of the resource contention
// 3. Calculate the estimated execution time 
double tree_est_time(legoProc * proc, legoTreegion * par_tree, legoTreegion *
        cand_tree, legoTreegion * par_tree2, knobs *K, tree_stats *st, int td_type)
{
    int inp_start = FindFirstOutGoingReg(proc);
    int inp_end = FindLastOutGoingReg(proc);
        
    legoModule * modu_tmp = new legoModule;
    modu_tmp->AddItem(proc);
    LegoWrite(modu_tmp, "temp_temp.el");
    modu_tmp->Detach(0); //detach the proc
    delete modu_tmp;
    modu_tmp = new legoModule;
    LegoRead("temp_temp.el", modu_tmp);
    legoProc * proc_tmp = (legoProc *) modu_tmp->GetItem(0);
    legoTreegion * tree_p = NULL;
    legoTreegion * tree_c = NULL;
    legoTreegion * tree_p2 = NULL;
    int i;
    for(i = 0; i < proc_tmp->GetCount(); i++)
    {
        if(((legoTreegion *) proc_tmp->GetItem(i))->GetRegionId() == par_tree->GetRegionId())
            tree_p = (legoTreegion *) proc_tmp->GetItem(i);
        if(((legoTreegion *) proc_tmp->GetItem(i))->GetRegionId() == cand_tree->GetRegionId())
            tree_c = (legoTreegion *) proc_tmp->GetItem(i);
        if(td_type == 3)
        {
            if(((legoTreegion *) proc_tmp->GetItem(i))->GetRegionId() == par_tree2->GetRegionId())
                tree_p2 = (legoTreegion *) proc_tmp->GetItem(i);
        }
        if(td_type !=3 && tree_p && tree_c) break;
        if(td_type == 3 && tree_p && tree_c && tree_p2) break;
    }
    
    legoRegion * root1 = tree_p->GetRoot();
    legoRegion * root2 = tree_c->GetRoot();
    
    legoRegion * root3 = NULL;
    if(td_type == 3)
        root3 = tree_p2->GetRoot();
        
/*              
    //1. Construct a new legoProc containing only par_tree and cand_tree
    legoModule * modu_tmp = new legoModule();
    legoProc * proc_tmp = new legoProc(proc->GetProcName(), 1);
    
    modu_tmp->AddItem(proc_tmp);
    proc_tmp->SetParentPtr(modu_tmp);
    proc_tmp->SetWeight(proc->GetWeight());
    
    legoTreegion * tree_p = new legoTreegion(1);
    legoTreegion * tree_c = new legoTreegion(2);
    
    proc_tmp->AddItem(tree_p);
    tree_p->SetParentPtr(proc_tmp);
    tree_p->SetWeight(par_tree->GetWeight());
    proc_tmp->AddItem(tree_c);       
    tree_c->SetParentPtr(proc_tmp);
    tree_c->SetWeight(cand_tree->GetWeight());
    
    //1a. copy all the BBs and the ops
    int bb_i;
    legoOp * bb_prev_op = NULL;
    for(bb_i = 0; bb_i < par_tree->GetCount(); bb_i++)
    {
        legoBB * bb_t = (legoBB *) par_tree->GetItem(bb_i);
        legoBB * bb_p = new legoBB(bb_t->GetRegionId());
        for(int op_i =0; op_i < bb_t->GetCount(); op_i++)
        {
            legoOp *op_p = new legoOp(0);
            copy_legoOp((legoOp *)bb_t->GetItem(op_i), op_p);
            op_p->SetParentBlockPtr(bb_p);
            bb_p->AddItem(op_p);
            if(op_i != 0)
            {
                op_p->SetPrevLink(bb_prev_op);
                bb_prev_op->SetNextLink(op_p);
                op_p->SetListOpPtr(bb_prev_op);
            }
            else
                op_p->SetListOpPtr(NULL);
            bb_prev_op = op_p;
        }
        bb_p->SetWeight(bb_t->GetWeight());
        tree_p->AddItem(bb_p);
        bb_p->SetParentPtr(tree_p);
    }
    
    tree_p->SetRoot((legoRegion *)tree_p->GetItem(0));
    
    for(bb_i = 0; bb_i < cand_tree->GetCount(); bb_i++)
    {
        legoBB * bb_t = (legoBB *) cand_tree->GetItem(bb_i);
        legoBB * bb_p = new legoBB(bb_t->GetRegionId());
        for(int op_i =0; op_i < bb_t->GetCount(); op_i++)
        {
            legoOp *op_p = new legoOp(0);
            copy_legoOp((legoOp *)bb_t->GetItem(op_i), op_p);
            op_p->SetParentBlockPtr(bb_p);
            bb_p->AddItem(op_p);
            if(op_i != 0)
            {
                op_p->SetPrevLink(bb_prev_op);
                bb_prev_op->SetNextLink(op_p);
                op_p->SetListOpPtr(bb_prev_op);
            }
            else
                op_p->SetListOpPtr(NULL);
            bb_prev_op = op_p;
        }
        bb_p->SetWeight(bb_t->GetWeight());
        tree_c->AddItem(bb_p);
        bb_p->SetParentPtr(tree_c);
    }
    
    tree_c->SetRoot((legoRegion *)tree_c->GetItem(0));
    
    proc_tmp->SetListOpPtr(bb_prev_op);    
    
    //1b. copy & reconstruct the edge dictionaries
    opEdges * edge_dict = NULL;
    opEdges * head = NULL;
    opEdges * old_dict = proc->GetEdgeDictionary();
    while(old_dict != NULL)
    {
        int from_BB_id =
                ((legoRegion *) old_dict->GetFromOpPtr()->GetParentBlockPtr())->GetRegionId();
        int to_BB_id =
                ((legoRegion *) old_dict->GetToOpPtr()->GetParentBlockPtr())->GetRegionId();
        bool from_in_tmp = false;
        bool to_in_tmp = false;
        int i;
        for(i = 0; i <  tree_p->GetCount(); i++)
        {
            if(from_BB_id == ((legoRegion *)tree_p->GetItem(i))->GetRegionId())
                from_in_tmp = true;
            if(to_BB_id == ((legoRegion *)tree_p->GetItem(i))->GetRegionId())
                to_in_tmp = true;
            if(from_in_tmp && to_in_tmp) break;
        }
        for(i = 0; i <  tree_c->GetCount(); i++)
        {
            if(from_BB_id == ((legoRegion *)tree_c->GetItem(i))->GetRegionId())
                from_in_tmp = true;
            if(to_BB_id == ((legoRegion *)tree_c->GetItem(i))->GetRegionId())
                to_in_tmp = true;
            if(from_in_tmp && to_in_tmp) break;
        }
        if(from_in_tmp && to_in_tmp)
        {
            //find the correct opPtr
            int from_op_id = old_dict->GetFromOpPtr()->GetOpId();
            int to_op_id = old_dict->GetToOpPtr()->GetOpId();
            legoOp * from_op = NULL;
            legoOp * to_op = NULL;
            
            for(i = 0; i <  tree_p->GetCount(); i++)
            {
                legoRegion * region1 = (legoRegion *) tree_p->GetItem(i);
                for(int j = 0; j < region1->GetCount(); j++)
                {
                    if(from_op_id == ((legoOp *)region1->GetItem(j))->GetOpId())
                    {
                        from_op = (legoOp *)region1->GetItem(j);
                    }
                    if(to_op_id == ((legoOp *)region1->GetItem(j))->GetOpId())
                    {
                        to_op = (legoOp *)region1->GetItem(j);
                    }
                    if(from_op && to_op) break;
                }
                if(from_op && to_op) break;
            }
            for(i = 0; i <  tree_c->GetCount(); i++)
            {
                legoRegion * region1 = (legoRegion *) tree_c->GetItem(i);
                for(int j = 0; j < region1->GetCount(); j++)
                {
                    if(from_op_id == ((legoOp *)region1->GetItem(j))->GetOpId())
                    {
                        from_op = (legoOp *)region1->GetItem(j);
                    }
                    if(to_op_id == ((legoOp *)region1->GetItem(j))->GetOpId())
                    {
                        to_op = (legoOp *)region1->GetItem(j);
                    }
                    if(from_op && to_op) break;
                }
                if(from_op && to_op) break;
            }
            if(head == NULL)
            {
                edge_dict = new opEdges();
                head = edge_dict;
            }
            else
            {
                edge_dict->SetNextOpEdgePtr(new opEdges());
                edge_dict = edge_dict->GetNextOpEdgePtr();
            }
            copy_opEdges(old_dict, edge_dict, -1, -1, from_op, -1, to_op);
        }
        old_dict = old_dict->GetNextOpEdgePtr();
    }    
    
    proc_tmp->SetEdgeDictionary(head);
    
    //1c. refresh the in_op/out_op list for each op (in/outListPtr) based on the opid
    for(bb_i = 0; bb_i < tree_p->GetCount(); bb_i++)
    {
        legoBB * bb_t = (legoBB *) tree_p->GetItem(bb_i);
        for(int op_i =0; op_i < bb_t->GetCount(); op_i++)
        {
            legoOp * op_p = (legoOp *)bb_t->GetItem(op_i);
            opList * inl, * outl;
            for(inl = op_p->GetInListPtr(); inl != NULL; inl = inl->GetNextListPtr())
            {
                legoOp * opptr = NULL;
                int inl_opid = inl->GetOpId();
                opptr = find_op(proc_tmp, inl_opid);
                if(opptr != NULL)
                   inl->SetOpPtr(opptr);
            }
            for(outl = op_p->GetOutListPtr(); outl != NULL; outl = outl->GetNextListPtr())
            {
                legoOp * opptr = NULL;
                int outl_opid = outl->GetOpId();
                opptr = find_op(proc_tmp, outl_opid);
                if(opptr != NULL)
                   outl->SetOpPtr(opptr);
            }
        }
    }
    for(bb_i = 0; bb_i < tree_c->GetCount(); bb_i++)
    {
        legoBB * bb_t = (legoBB *) tree_c->GetItem(bb_i);
        for(int op_i =0; op_i < bb_t->GetCount(); op_i++)
        {
            legoOp * op_p = (legoOp *)bb_t->GetItem(op_i);
            opList * inl, * outl;
            for(inl = op_p->GetInListPtr(); inl != NULL; inl = inl->GetNextListPtr())
            {
                legoOp * opptr = NULL;
                int inl_opid = inl->GetOpId();
                opptr = find_op(proc_tmp, inl_opid);
                if(opptr != NULL)
                    inl->SetOpPtr(opptr);
            }
            for(outl = op_p->GetOutListPtr(); outl != NULL; outl = outl->GetNextListPtr())
            {
                legoOp * opptr = NULL;
                int outl_opid = outl->GetOpId();
                opptr = find_op(proc_tmp, outl_opid);
                if(opptr != NULL)
                    outl->SetOpPtr(opptr);
            }
        }
    }
    
    //1d. refresh exit/entry oplists, entry/exit edges (in/out lists) at the BB
    // level, treegion level, and proc level
    for(bb_i = 0; bb_i < tree_p->GetCount(); bb_i++)
    {
        ((legoBB *)tree_p->GetItem(bb_i))->RefreshAll();
    }
    for(bb_i = 0; bb_i < tree_c->GetCount(); bb_i++)
    {
        ((legoBB *)tree_c->GetItem(bb_i))->RefreshAll();
    }
    
    //tree_p->RefreshAll();
    //tree_c->RefreshAll();
    
    proc_tmp->RefreshAll();
    
    //1e. the attribute dictionary
    attrs * attsPtr = new attrs();
    proc_tmp->SetAttrDictionary(attsPtr);
    
        //  legoModule * temp_M;
        //  temp_M = new legoModule();
        //  temp_M->AddItem(proc_tmp);
        //  LegoWrite(temp_M, "teeeee.el");
        //  delete temp_M;    
*/    
    
    //2. Tail dup the cand_tree
    double weight = 0;
    int num_edges = 0;
    legoRegion * cand_region = tree_c->GetRoot();
    edgeList * out_list; 
    opEdges *cand_edges = NULL;
    for(out_list = tree_p->GetOutEdgesPtr(); out_list != NULL; out_list =
            out_list->GetNextListPtr())
    {
        opEdges * edges_ptr1 = out_list->GetEdgePtr();
        if(edges_ptr1->GetToOpPtr()->GetParentBlockPtr() == cand_region)
        {
            num_edges++;
            double edge_weight = (double) FindEdgeFrequency (edges_ptr1);
            if( edge_weight >= weight)
            {
                cand_edges = edges_ptr1;
                weight = edge_weight;
            }
        }
    }
    assert(cand_edges != NULL);
    
    //LegoWrite(modu_tmp, "teeeee1.el");
    
    TreeDuplicate(tree_c, cand_edges, cand_region, tree_p);        
    
    //LegoWrite(modu_tmp, "teeeee2.el");
    
    //3. TreeUnform and Form again
    int tree_p_id = tree_p->GetRegionId();
    if(td_type == 1)
    {
                unsigned origloc1 = proc_tmp->Search(tree_p);
                unsigned origloc2 = proc_tmp->Search(tree_c);
                if(origloc1 > origloc2) origloc1 = origloc1 - 1;
                
                Deconstruct(tree_p);
                unsigned treeloc1= proc_tmp->Search(tree_p);
                proc_tmp->Detach(treeloc1);
                delete tree_p;
                Deconstruct(tree_c);
                unsigned treeloc2 = proc_tmp->Search(tree_c);
                proc_tmp->Detach(treeloc2);
                delete tree_c;
                
                legoTreegion * tree_new = new legoTreegion(tree_p_id);
                proc_tmp->Insert(tree_new, origloc1);
                tree_new->SetParentPtr(proc_tmp);
                Construct(tree_new, root1);     
                tree_new->SetWeight(root1->GetWeight());
    }
    else if (td_type == 2 || td_type == 4)
    {
                unsigned origloc1 = proc_tmp->Search(tree_p);
                unsigned origloc2 = proc_tmp->Search(tree_c);
                Deconstruct(tree_p);
                unsigned treeloc1= proc_tmp->Search(tree_p);
                proc_tmp->Detach(treeloc1);
                delete tree_p;
                
                //Do this because the duplicated BBs are still in tree_c
                int tree_c_id = tree_c->GetRegionId();
                Deconstruct(tree_c);
                unsigned treeloc2 = proc_tmp->Search(tree_c);
                proc_tmp->Detach(treeloc2);
                delete tree_c;
                
                legoTreegion * tree_new = new legoTreegion(tree_p_id);
                proc_tmp->Insert(tree_new, origloc1);
                tree_new->SetParentPtr(proc_tmp);
                Construct(tree_new, root1);     
                tree_new->SetWeight(root1->GetWeight());
                
                legoTreegion * tree_c_new = new legoTreegion(tree_c_id);        
                proc_tmp->Insert(tree_c_new, origloc2);
                tree_c_new->SetParentPtr(proc_tmp);
                Construct(tree_c_new, root2);
                tree_c_new->SetWeight(root2->GetWeight());
    }
    else if(td_type == 3)
    {
                unsigned origloc1 = proc_tmp->Search(tree_p);
                unsigned origloc2 = proc_tmp->Search(tree_c);
                unsigned origloc3 = proc_tmp->Search(tree_p2);
                if(origloc1 > origloc2) origloc1 = origloc1 - 1;
                if(origloc3 > origloc2) origloc3 = origloc3 - 1;
        
                int tree_p2_id = tree_p2->GetRegionId();
                Deconstruct(tree_p);
                unsigned treeloc1= proc_tmp->Search(tree_p);
                proc_tmp->Detach(treeloc1);
                delete tree_p;
                Deconstruct(tree_c);
                unsigned treeloc2 = proc_tmp->Search(tree_c);
                proc_tmp->Detach(treeloc2);
                delete tree_c;
                Deconstruct(tree_p2);
                unsigned treeloc3 = proc_tmp->Search(tree_p2);
                proc_tmp->Detach(treeloc3);
                delete tree_p2;
                
                legoTreegion * tree_new = new legoTreegion(tree_p_id);
                proc_tmp->Insert(tree_new, origloc1);
                tree_new->SetParentPtr(proc_tmp);
                Construct(tree_new, root1);     
                tree_new->SetWeight(root1->GetWeight());
                
                legoTreegion * tree_new2 = new legoTreegion(tree_p2_id);
                proc_tmp->Insert(tree_new2, origloc3);
                tree_new2->SetParentPtr(proc_tmp);
                Construct(tree_new2, root3);    
                tree_new2->SetWeight(root3->GetWeight());
    }
//    treeunform(proc_tmp);
    
    //LegoWrite(modu_tmp, "teeeee3.el");
    
//    int treeid = (proc_tmp->FindMaxRegionId())->GetRegionId();
    
//    treeform(proc_tmp, treeid, K, st, false);
    
    //LegoWrite(modu_tmp, "teeeee4.el");
    
    //assert(proc_tmp->GetCount() <= 2);
    assert(proc_tmp->GetCount() <= proc->GetCount());
    
    
    legoTreegion * tree1 = (legoTreegion *)root1->GetParentPtr();
    //legoTreegion * tree1 = (legoTreegion *) proc_tmp->GetItem(0);
    
    
    //4. Calculate the ave max dependence height of the resulting treegion
    machine * Mach1 = new machine(K);
    //construct the DDG for the candidate pairs, calculate the heuristic
    //dag * DDG1 = new dag(Mach1, K);
    dag * DDG1;
#ifdef IA64_SUPPORT                   
        DDG1 = new dag (Mach1, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
        DDG1 = new dag (Mach1, K, 0, 0, 0, 0, 0, 0);
#endif
    
    DDG1->ConstructDag(tree1);
    DDG1->ResetNodeHeights();
    DDG1->MaxHeights();    
    
    //ofstream os1("teeee1.txt");
    //DDG1->PrintDag(os1);
    //os1.close();    
    
    double ave_m_h1 = DDG1->GetAveMaxHeight();
    double ave_time1 = ave_m_h1 * root1->GetWeight();
    
    //double ave_m_h2 = 0;
    //double width2 = 0;
    //double ave_time2 = 0;
    //if(proc_tmp->GetCount() == 2) //two treegions remain after the tail dup (a merge point with more than 2
                                  //incoming edges
    /*
    if(proc_tmp->GetCount() == proc->GetCount())
    {
        legoTreegion * tree2 = (legoTreegion *)root2->GetParentPtr(); 
        //legoTreegion * tree2 = (legoTreegion *) proc_tmp->GetItem(1);
        assert(tree1 != tree2);
        dag * DDG2 = new dag(Mach1, K);
        DDG2->ConstructDag(tree2);
        DDG2->ResetNodeHeights();
        DDG2->MaxHeights();
        ave_m_h2 = DDG2->GetAveMaxHeight();
        //width2 = tree2->GetOpCount() * 1.0 / (Mach1->GetNumSlots() - 1); 
                //DDG2->GetAveWidth() * 1.0 / (Mach1->GetNumSlots() - 1);
        //width2 = (width2 - (int)width2 > 0.09)?(int)(width2 + 1):width2;
        //if(ave_m_h2 > width2) 
            ave_time2 = ave_m_h2 * tree2->GetRoot()->GetWeight();
        //else 
        //    ave_time2 = width2 * tree2->GetRoot()->GetWeight();
        if(tree2->GetRoot()->GetWeight() <= 0)
            ave_time2 = 0;
        
        delete DDG2;
    }
    */
    double ave_time3 = 0;
    if(td_type == 3)
    {
        legoTreegion * tree3 = (legoTreegion *) root3->GetParentPtr();
        assert(tree3 != tree1);
        dag * DDG3;
#ifdef IA64_SUPPORT                   
        DDG3 = new dag (Mach1, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
        DDG3 = new dag (Mach1, K, 0, 0, 0, 0, 0, 0);
#endif
        //dag * DDG3 = new dag(Mach1, K);
        DDG3->ConstructDag(tree3);
        DDG3->ResetNodeHeights();
        DDG3->MaxHeights();
        ave_time3 = DDG3->GetAveMaxHeight() * root3->GetWeight();
        delete DDG3;
    }       
    //5. Return the result from step 4
    delete DDG1;
    delete Mach1;
    delete modu_tmp;
    return(ave_time1 + ave_time3);   
}

// HZ: 08/31/01 
// Duplicate the sipling regions of the candidate region and the candiate region
// itself as long as all of them are in the treegion source_region.
// 
// As this this function calls itself recursively, by setting the input
// parameters as:
//  source_region = the treegion needs to be duplicated
//  dup_edge = one of the entry edge to the treegion
//  candidate_region = root of the treegion,
//  parenttree = the parent treegion to be expanded
// this function will do the tail duplication at treegion level.
// The return value will be the duplicate of the root block
legoRegion * TreeDuplicate(legoTreegion *source_region, opEdges *dup_edge,
        legoRegion *candidate_region, legoTreegion * par_tree)
{
    // Find parent proc.
    //legoProc * parentproc = (legoProc *) FindParentRegionType (RT_PROC, sourceregion);
    //if (parentproc == NULL)
      //LegoFatal ("TailDuplicate", "Can't find parent proc of region %d.",
        //       sourceregion->GetRegionId());
    assert(candidate_region->GetParentPtr() == source_region);
    
    //duplicate the candidate block    
    legoRegion * duplicate = TailDuplicate (candidate_region, dup_edge);
    
    //Duplicate candidate's child blocks 
    if(duplicate == NULL) 
    {
        cout << "<TreeDup> TailDup returns NULL\n";
        return NULL;
    }
    
    edgeList * out_list = duplicate->GetOutEdgesPtr();
    int num_out_list = 0;
    while (out_list != NULL)
    {
        opEdges * edges_ptr = out_list->GetEdgePtr();
        if((edges_ptr != NULL) && (((legoRegion *) edges_ptr->GetToOpPtr()->GetParentBlockPtr())->GetParentPtr() ==
                source_region))
        {
            if(edges_ptr->GetToOpPtr()->GetParentBlockPtr() != source_region->GetRoot())
            {
                TreeDuplicate(source_region, edges_ptr,
                    (legoRegion *) edges_ptr->GetToOpPtr()->GetParentBlockPtr(), par_tree);
                //cout << "I am here\n";
            }
        }
        num_out_list++;
        int temp_i;
        for(out_list = duplicate->GetOutEdgesPtr(), temp_i = 0; temp_i < num_out_list; out_list =
            out_list->GetNextListPtr(), temp_i++);

    }
    return (duplicate);
}

typedef struct tree_pair_
{
    legoTreegion * par_tree;  //the parent treegion
    legoTreegion * cand_tree; //the candidate treegion that can be duplicated
    int td_type; // here we define 4 types of possible tail dup candidate
                 // type 1: par_tree dominates cand_tree and there are 2 entry
                 //  edges of  cand_tree
                 // type 2: par_tree dominates cand_tree and there are more than
                 // 2 entry edges of cand_tree
                 // type 3: par_tree does not dominate candtree and there are 2
                 // entry edges of cand_tree
                 // type 4: par_tree does not dominate cand_tree and there are
                 // more than 2 edges of cand_tree
                 // we will calculate the expected exe. time based on its type
    legoTreegion * par_tree2; // the second parent treegion when td_type is 3
} tree_pair;


static int n_proc = 0;

//Find all the acyclic td (tail duplication) candidates in the proc and write them out in a text
// file (stdout)

void Td_Candidates (legoProc *proc, int& treeid, knobs *K, tree_stats *st = NULL)
{
    int inp_start = FindFirstOutGoingReg(proc);
    int inp_end = FindLastOutGoingReg(proc);
    
    //1. forming the natural treegions (treegion formation without tail
    //  duplication.
    treeform(proc, treeid, K, st, false);
    
    //detect loop edges in the proc
    // Find the dominators.
    proc->FindDominators();

    // Mark backedges and loop headers.
    markbackedgesandloopheaders (proc);
        
    n_proc++;
    //if(n_proc != 2) return;
    
    //if(strcmp(proc->GetProcName(), "_getcode") != 0) return;
    //cout << "I am here\n";
    
    //2. Put all possible merge points into a list
    vector<tree_pair *> cand_list;
    for(unsigned i = 0; i < proc->GetCount(); i++)
    {
        //go through the treegions
        legoTreegion * tree1 = (legoTreegion *)proc->GetItem(i);
        
        //speed up
        if(tree1->GetRoot()->GetWeight() == 0) continue;
        
        
        edgeList * out_list1;
        for(out_list1 = tree1->GetOutEdgesPtr(); out_list1 != NULL; out_list1 =
            out_list1->GetNextListPtr())
        {
            opEdges * edges_ptr1 = out_list1->GetEdgePtr();
            
            if(edges_ptr1 == NULL) continue;
            if(edges_ptr1->IsMarked(EM_BACK)) continue;
            
                   //check for the switch-case statement
                   legoOp * br_op_ptr = edges_ptr1->GetFromOpPtr();
                   attrList * atl1 = NULL;
                   bool sw = false;
                   //HZ:if(br_op_ptr->GetOpcode() == BRU)
                   if(br_op_ptr->IsBRUOp())
                   {
                       for (atl1 = br_op_ptr->GetOpAttrListPtr(); atl1 != NULL;
                         atl1 = atl1->GetNextListPtr())
                              if (atl1->GetAttrType() == ATTR_TBLNAME)
                              {
                                 sw = true;
                                 break;
                              }
                   }
                   if (sw == true) continue;        
            
            legoRegion * cand_region1 = (legoRegion *) edges_ptr1->GetToOpPtr()->GetParentBlockPtr();
            int  qualifies = 1;
    
            edgeList * in_list1;
            int num_in_edges = 0; //used to determine the td_type if qualifies
            for(in_list1 = cand_region1->GetInEdgesPtr(); in_list1 != NULL;
                    in_list1 = in_list1->GetNextListPtr())
            {
                opEdges * edges_ptr2 = in_list1->GetEdgePtr();
                if(edges_ptr2 == NULL) continue;
                if(edges_ptr2->IsMarked(EM_BACK))
                        qualifies = 0;
                num_in_edges++;
            }
                    
            if(cand_region1->GetChildren() == NULL)
            {
                qualifies = 1;
            }
            
            if(tree1 == (legoTreegion *)cand_region1->GetParentPtr())
            {
                qualifies = 0;
                cout << "<treeform_one_by_one> Backedge unselected.\n";
            }
            
            if (qualifies) 
            {
                if(FindEdgeFrequency(edges_ptr1) > 0)
                {
                    //To speedup the processing: check whether the pair has been in the
                    // list already (through a different edge). Anyway we will choose the
                    // best edge when we do the tail dup based on par_reg_id and
                    // cand_reg_id
                    vector <tree_pair *>::iterator pos_1;
                    bool in_cd_list = false;
                    for(pos_1 = cand_list.begin(); pos_1 != cand_list.end(); pos_1++)
                    {
                        if((*pos_1)->par_tree == tree1 && (*pos_1)->cand_tree ==
                                (legoTreegion *)cand_region1->GetParentPtr())
                        {
                            in_cd_list = true;
                            break;
                        }
                    }
                    if(in_cd_list) continue;
                    
                    
                    //insert the pair into the list
                    tree_pair * tp_ptr;
                    tp_ptr = new tree_pair;
                    tp_ptr->par_tree = tree1;
                    tp_ptr->cand_tree = (legoTreegion *)cand_region1->GetParentPtr();
                
                    //set the td_type here
                    bool dom = true;
                    regionList * rl;
                    legoTreegion * par2 = NULL;
                    for (rl = cand_region1->GetParents(); rl != NULL; rl = rl->GetNextListPtr())
                    {
                        par2 = (legoTreegion *) rl->GetRegionPtr()->GetParentPtr();
                        if (par2 != (legoRegion *) tree1)
                        {
                            dom = false;  // par_tree does not dominate cand_tree
                            break;
                        }
                    } // end for
                    tp_ptr->td_type = 0;
                    tp_ptr->par_tree2 = NULL;
                    if(dom == true && num_in_edges == 2) tp_ptr->td_type = 1;
                    else if(dom == true && num_in_edges > 2) tp_ptr->td_type = 2;
                    else if(dom == false && num_in_edges == 2) 
                    {
                        tp_ptr->td_type = 3;
                        tp_ptr->par_tree2 = par2;
                    }
                    else if(dom == false && num_in_edges > 2) tp_ptr->td_type = 4;
                
                    cand_list.push_back(tp_ptr);
                }
            }   //end if(qualifies)    
        }//end for out_list1 (go through the outedge list of the treegion)
    }//end for i (go through treegions)
    
    //3. sort the cand_list based on the priority of each candidate, select the best candidate and remove
    //  it from the list.
    cout << "Proc: " << proc->GetProcName() <<
             " Number of possible tail dups: " << cand_list.size() << endl;
    
    if(cand_list.empty()) 
    {
        cout << "<treeform_one_by_one> No candidate merge point is found. \n";
        return; //no need to dup, as no candidate is found
    }
            
    machine * Mach1 = new machine(K);
    vector<tree_pair *>::iterator pos;
    
    //construct the DDG for the candidate pairs, calculate the heuristic
    for(pos = cand_list.begin(); pos != cand_list.end(); pos++)
    {
        assert((*pos)->td_type >= 1 && (*pos)->td_type <=4);
        
        //if((*pos)->par_tree->GetRegionId() == 131 && (*pos)->cand_tree->GetRegionId() ==
        //      135)
        //{
        //    int kkkkkk = 11;
        //}
        
        
        //dag * DDG1 = new dag(Mach1, K);
        dag * DDG1;
#ifdef IA64_SUPPORT                   
        DDG1 = new dag (Mach1, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
        DDG1 = new dag (Mach1, K, 0, 0, 0, 0, 0, 0);
#endif
        
        //dag * DDG2 = new dag(Mach1, K);
        dag * DDG2;
#ifdef IA64_SUPPORT                   
        DDG2 = new dag (Mach1, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
        DDG2 = new dag (Mach1, K, 0, 0, 0, 0, 0, 0);
#endif
        
        DDG1->ConstructDag((*pos)->par_tree);
        DDG1->ResetNodeHeights();
        DDG1->MaxHeights();
            //ofstream os1("teeee2.txt");
            //DDG1->PrintDag(os1);
            //os1.close();
        double ave_m_h1 = DDG1->GetAveMaxHeight();
        //int n_path1 = DDG1->GetNumPath();
        double ave_time1 = ave_m_h1 * (*pos)->par_tree->GetRoot()->GetWeight(); 
                
        DDG2->ConstructDag((*pos)->cand_tree);
        DDG2->ResetNodeHeights();
        DDG2->MaxHeights();
        double ave_m_h2 = DDG2->GetAveMaxHeight();
        //int n_path2 = DDG2->GetNumPath();
        double ave_time2 = 0;
        if((*pos)->td_type == 1 || (*pos)->td_type == 3)
        {           
            ave_time2 = ave_m_h2 * (*pos)->cand_tree->GetRoot()->GetWeight(); 
        }
        else
        {
            //find the edge freq
            opEdges * cand_edges = NULL;
            double weight = 0;
            edgeList * out_list;
            legoRegion * cand_region1 = (*pos)->cand_tree->GetRoot();
            for(out_list = (*pos)->par_tree->GetOutEdgesPtr(); out_list != NULL; out_list =
                    out_list->GetNextListPtr())
            {
                opEdges * edges_ptr1 = out_list->GetEdgePtr();
                if(edges_ptr1->GetToOpPtr()->GetParentBlockPtr() == cand_region1)
                {
                    double edge_weight = (double) FindEdgeFrequency (edges_ptr1);
                    if( edge_weight >= weight)
                    {
                        cand_edges = edges_ptr1;
                        weight = edge_weight;
                    }
                }
            }
            assert(cand_edges != NULL);
            
            ave_time2 = ave_m_h2 * weight;
        }
        double ave_time3 = 0;
        if((*pos)->td_type == 3)
        {
            //dag * DDG3 = new dag(Mach1, K);
            dag * DDG3;
#ifdef IA64_SUPPORT                   
                DDG3 = new dag (Mach1, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
                DDG3 = new dag (Mach1, K, 0, 0, 0, 0, 0, 0);
#endif
            
            DDG3->ConstructDag((*pos)->par_tree2);
            DDG3->ResetNodeHeights();
            DDG3->MaxHeights();
            double ave_m_h3 = DDG3->GetAveMaxHeight();
            ave_time3 = ave_m_h3 * (*pos)->par_tree2->GetRoot()->GetWeight();   
            delete DDG3;
        }
        //calculating the max dep height for the case when cand_tree is duplicated can appended to par_tree
        double ave_time_td;
        ave_time_td = tree_est_time(proc, (*pos)->par_tree, (*pos)->cand_tree,
                (*pos)->par_tree2, K, NULL,
                (*pos)->td_type);
        
        delete DDG2;
        delete DDG1;
        
        double eff = (ave_time1 + ave_time2 + ave_time3 - ave_time_td) / (*pos)->cand_tree->GetOpCount();
        
        cout << "Proc: " << proc->GetProcName() << " Tree Id: " << (*pos)->par_tree->GetRegionId() << " To Tree Id: " <<
            (*pos)->cand_tree->GetRegionId() << endl;
        cout << "ave exe time 1: " << ave_time1 << " ave exe time 2: " <<
                ave_time2 << "ave exe time 3: " << ave_time3 <<
                " ave exe time td: " << ave_time_td << endl;
        if((*pos)->td_type == 3)
            cout << "Efficiency: " << eff << " code size incr: " <<
                (*pos)->cand_tree->GetOpCount() - 1 << " td_type: " << (*pos)->td_type 
                <<" par2_id: " << (*pos)->par_tree2->GetRegionId() << endl;
        else
            cout << "Efficiency: " << eff << " code size incr: " <<
                (*pos)->cand_tree->GetOpCount() - 1 << " td_type: " << (*pos)->td_type 
                <<" par2_id: " << 0 << endl;
            
    }
    delete Mach1;
    
    //free the memory allocated by cand_list
    for(pos = cand_list.begin(); pos != cand_list.end(); pos++)
    {
        delete (*pos);
    }
    
    //clear the loop marks
    ClearMarks(EM_BACK, proc->GetEdgeDictionary());
    /*
    pos = cand_list.begin();
    
    
    
    //pos++;
    //pos++;
    //pos++;
    //pos++;
    //pos++;
    //pos++;
    //pos++;
    //pos++;
        
    (*pos)->processed = true;
    
    cout << "Selected: Proc: " << proc->GetProcName() << " Tree Id: " << (*pos)->par_tree->GetRegionId() << " To Tree Id: " <<
            (*pos)->cand_tree->GetRegionId() << endl;
    cout << "   Base size increase: " << (*pos)->cand_tree->GetOpCount() - 1 << endl;
    cout << "Weight of the treegion: " << (*pos)->cand_tree->GetRoot()->GetWeight() << endl;

    pos++;
    cout << "Next: Proc: " << proc->GetProcName() << " Tree Id: " << (*pos)->par_tree->GetRegionId() << " To Tree Id: " <<
            (*pos)->cand_tree->GetRegionId() << endl;
    cout << "   Base size increase: " << (*pos)->cand_tree->GetOpCount() - 1 << endl;
    pos--;
    
    
    //4. tail dup the best candidate
    legoTreegion * par_tree = (*pos)->par_tree;
    legoTreegion * cand_tree = (*pos)->cand_tree;
    legoRegion * cand_region = (*pos)->cand_tree->GetRoot();
    opEdges * cand_edges = NULL;
    double weight = 0;
    int num_edges = 0;
    edgeList * out_list;
    for(out_list = par_tree->GetOutEdgesPtr(); out_list != NULL; out_list =
            out_list->GetNextListPtr())
    {
        opEdges * edges_ptr1 = out_list->GetEdgePtr();
        if(edges_ptr1->GetToOpPtr()->GetParentBlockPtr() == cand_region)
        {
            num_edges++;
            double edge_weight = (double) FindEdgeFrequency (edges_ptr1);
            if( edge_weight >= weight)
            {
                cand_edges = edges_ptr1;
                weight = edge_weight;
            }
        }
    }
    assert(cand_edges != NULL);
    TreeDuplicate(cand_tree, cand_edges, cand_region, par_tree);
    
    //5. TreeUnForm
    treeunform(proc);
    treeid = (proc->FindMaxRegionId())->GetRegionId();
    
    //6. Forming the treegion again  (go back to step 2 until the code size limit is reached)
    // (or go back to step 2 to reform the list due to the changes from the tail duplication? yes, as
    // treeunform makes the treegion pointers outdated)
    treeform(proc, treeid, K, st);
    */
}


//Treeform_opt:
//Treegion formation with best code efficiency in terms of tail duplication.
//Methodology: Based on the calculation of the code size efficiency of the td (tail dup)
//candidate, if the resulting efficiency is greater than a threshold, the tail duplication
//will be performed.

void Treeform_opt (legoProc *proc, int& treeid, knobs *K, tree_stats *st = NULL, double
        eff_threshold = 1000)
{
    int inp_start = FindFirstOutGoingReg(proc);
    int inp_end = FindLastOutGoingReg(proc);
    bool no_more_td_cand = false;
    machine * Mach1 = new machine(K);
   //1. forming the natural treegions (treegion formation without tail
   //  duplication. skiped if the source rebel file is known to be natural treegion formed
   //treeform(proc, treeid, K, st, false);

    int start_i = 0;
    while(no_more_td_cand == false)
    {
    
        //detect loop edges in the proc
        // Find the dominators.
        proc->FindDominators();

        // Mark backedges and loop headers.
        markbackedgesandloopheaders (proc);
        
        
        //2. Find a tail duplication candidate
        bool find_candidate = false;
        double efficiency;
        legoTreegion * tree1 = NULL, * tree2 = NULL, * par_tree2 = NULL;
        opEdges * cand_edges = NULL;
        int td_type = 0;
        
        //To speed up the simulation
        //No need to start the search from every treegion
        //Instead continue from the last iteration
        
            //for(unsigned i = 0; i < proc->GetCount(); i++)
            for(unsigned i = start_i; i < proc->GetCount(); i++)
            {
                //go through the treegions
               tree1 = (legoTreegion *)proc->GetItem(i);
               
               //speed up
               if(tree1->GetRoot()->GetWeight() == 0) continue;
               
               edgeList * out_list1;
               for(out_list1 = tree1->GetOutEdgesPtr(); out_list1 != NULL; out_list1 =
                   out_list1->GetNextListPtr())
               {
                   opEdges * edges_ptr1 = out_list1->GetEdgePtr();
            
                   if(edges_ptr1 == NULL) continue;
                   if(edges_ptr1->IsMarked(EM_BACK)) continue;
                   
                   //check for the switch-case statement
                   legoOp * br_op_ptr = edges_ptr1->GetFromOpPtr();
                   attrList * atl1 = NULL;
                   bool sw = false;
                   //HZ: if(br_op_ptr->GetOpcode() == BRU)
                   if(br_op_ptr->IsBRUOp())
                   {
                       for (atl1 = br_op_ptr->GetOpAttrListPtr(); atl1 != NULL;
                         atl1 = atl1->GetNextListPtr())
                              if (atl1->GetAttrType() == ATTR_TBLNAME)
                              {
                                 sw = true;
                                 break;
                              }
                   }
                   if (sw == true) continue;               
                                        
                   legoRegion * cand_region1 = (legoRegion *) edges_ptr1->GetToOpPtr()->GetParentBlockPtr();
                   int  qualifies = 1;
                   
                    edgeList * in_list1;
                    int num_in_edges = 0; //used to determine the td_type if qualifies
                    for(in_list1 = cand_region1->GetInEdgesPtr(); in_list1 != NULL;
                            in_list1 = in_list1->GetNextListPtr())
                    {
                        opEdges * edges_ptr2 = in_list1->GetEdgePtr();
                        if(edges_ptr2 == NULL) continue;
                        if(edges_ptr2->IsMarked(EM_BACK))
                                qualifies = 0;
                        num_in_edges++;
                    }
                   
                   if(cand_region1->GetChildren() == NULL)
                   {
                       qualifies = 1;
                   }
            
                   if(tree1 == (legoTreegion *)cand_region1->GetParentPtr())
                   {
                       qualifies = 0;
                       //cout << "<treeform_one_by_one> Backedge unselected.\n";
                   }
            
                   if (qualifies) 
                   {
                       double edge_f = FindEdgeFrequency(edges_ptr1);
                       cand_edges = edges_ptr1;
                       if(edge_f > 0)
                       {
                           tree2 = (legoTreegion *)cand_region1->GetParentPtr();    
                           //insert the pair into the list
                           
                           //set the td_type here
                           bool dom = true;
                           regionList * rl;
                           par_tree2 = NULL;
                           legoTreegion * par2 = NULL;
                           for (rl = cand_region1->GetParents(); rl != NULL; rl = rl->GetNextListPtr())
                           {
                               par2 = (legoTreegion *) rl->GetRegionPtr()->GetParentPtr();
                               if (par2 != (legoRegion *) tree1)
                               {
                                   dom = false;  // par_tree does not dominate cand_tree
                                   break;
                               }
                            } // end for
                            if(dom == true && num_in_edges == 2) td_type = 1;
                            else if(dom == true && num_in_edges > 2) td_type = 2;
                            else if(dom == false && num_in_edges == 2) 
                            {
                                td_type = 3;
                                par_tree2 = par2;
                            }
                            else if(dom == false && num_in_edges > 2) td_type = 4;
                                       
                           //dag * DDG1 = new dag(Mach1, K);
                            dag * DDG1;
#ifdef IA64_SUPPORT                   
                                DDG1 = new dag (Mach1, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
                                DDG1 = new dag (Mach1, K, 0, 0, 0, 0, 0, 0);
#endif
                            
                       
                           DDG1->ConstructDag(tree1);
                           DDG1->ResetNodeHeights();
                           DDG1->MaxHeights();
                       
                           double ave_m_h1 = DDG1->GetAveMaxHeight();
                       
                           //c_p->ave_t1 = ave_m_h1 * tree1->GetRoot()->GetWeight();
                           double ave_t1 = ave_m_h1 * tree1->GetRoot()->GetWeight();
                       
                           //dag * DDG2 = new dag(Mach1, K);
                           dag * DDG2;
#ifdef IA64_SUPPORT                   
                                DDG2 = new dag (Mach1, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
                                DDG2 = new dag (Mach1, K, 0, 0, 0, 0, 0, 0);
#endif
                           
                           DDG2->ConstructDag(tree2);
                           DDG2->ResetNodeHeights();
                           DDG2->MaxHeights();
                       
                           double ave_m_h2 = DDG2->GetAveMaxHeight();
                           double ave_t2 = 0;
                           if(td_type == 1 || td_type == 3)
                           {
                               ave_t2 = ave_m_h2 * tree2->GetRoot()->GetWeight();
                           }
                           else
                           {
                               ave_t2 = ave_m_h2 * edge_f;
                           }
                           double ave_t3 = 0;
                           if(td_type == 3)
                           {
                               //dag * DDG3 = new dag(Mach1, K);
                               dag * DDG3;
#ifdef IA64_SUPPORT                   
                                DDG3 = new dag (Mach1, K, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT                  
                                DDG3 = new dag (Mach1, K, 0, 0, 0, 0, 0, 0);
#endif
                               
                               DDG3->ConstructDag(par_tree2);
                               DDG3->ResetNodeHeights();
                               DDG3->MaxHeights();
                               ave_t3 = DDG3->GetAveMaxHeight() * par_tree2->GetRoot()->GetWeight();
                               delete DDG3;                            
                           }
                       
                           //c_p->ave_t2 = ave_m_h2 * tree2->GetRoot()->GetWeight();
                           //double ave_t2 = ave_m_h2 * tree2->GetRoot()->GetWeight();
                           //c_p->ave_td = tree_est_time(proc, tree1, tree2, K);
                           double ave_td = tree_est_time(proc, tree1, tree2, par_tree2,
                               K, NULL, td_type);
                           //c_p->efficiency = (c_p->ave_t1 + c_p->ave_t2 - c_p->ave_td) / tree2->GetOpCount();
                           efficiency = (ave_t1 + ave_t2 + ave_t3 - ave_td) / tree2->GetOpCount();
                           
                           if(efficiency > eff_threshold)
                           {
                               find_candidate = true;
                           }
                           
                           //also include the case when the size increase is
                           //zero
                           //if(efficiency > 50 && tree2->GetOpCount() == 1)
                           //{
                           //    find_candidate = true;
                           //}
                           
                           //also if the actual code size increase is zero
                           //current do not consider them
                           delete DDG1;
                           delete DDG2;                
                       } //end if(edge_f > 0)
                    }   //end if(qualifies)    
                    if(find_candidate) break;               
               }//end for out_list1 (go through the outedge list of the treegion)
               if(find_candidate) 
               {
                   if (i > 1)
                     start_i = i - 1;
                   break;
               }
           }//end for i (go through treegions)
           
        //clear the loop marks     
        ClearMarks(EM_BACK, proc->GetEdgeDictionary());
           
        if(find_candidate == false) 
        {
            no_more_td_cand = true;
            break;  
        }
        //3. tail dup the candidate
        cout << "Proc: " << proc->GetProcName() << " Tree Id: " << tree1->GetRegionId() << " To Tree Id: " <<
            tree2->GetRegionId() << endl;
        
        cout << "Efficiency: " << efficiency << " code size incr: " <<
                tree2->GetOpCount() - 1 << endl;
        
        //4. tail dup the candidate
        assert(cand_edges != NULL);
        TreeDuplicate(tree2, cand_edges, tree2->GetRoot(), tree1);
    
        //5. TreeUnForm & reform
        legoRegion * root_new = tree1->GetRoot();
        int tree1_id = tree1->GetRegionId();
        
            if(td_type == 1)
            {
                unsigned origloc1 = proc->Search(tree1);
                unsigned origloc2 = proc->Search(tree2);
                if(origloc1 > origloc2) origloc1 = origloc1 - 1;
                
                Deconstruct(tree1);
                unsigned treeloc1= proc->Search(tree1);
                proc->Detach(treeloc1);
                delete tree1;
                Deconstruct(tree2);
                unsigned treeloc2 = proc->Search(tree2);
                proc->Detach(treeloc2);
                delete tree2;
                
                legoTreegion * tree_new = new legoTreegion(tree1_id);
                proc->Insert(tree_new, origloc1);
                tree_new->SetParentPtr(proc);
                Construct(tree_new, root_new);
                tree_new->SetWeight(root_new->GetWeight());
            }
            else if (td_type == 2 || td_type == 4)
            {
                unsigned origloc1 = proc->Search(tree1);
                unsigned origloc2 = proc->Search(tree2);
                
                Deconstruct(tree1);
                unsigned treeloc1= proc->Search(tree1);
                proc->Detach(treeloc1);
                delete tree1;
                
                int tree2_id = tree2->GetRegionId();
                legoRegion * root_c = tree2->GetRoot();
                Deconstruct(tree2);
                unsigned treeloc2 = proc->Search(tree2);
                proc->Detach(treeloc2);
                delete tree2;
                
                legoTreegion * tree_new = new legoTreegion(tree1_id);
                proc->Insert(tree_new, origloc1);
                tree_new->SetParentPtr(proc);
                Construct(tree_new, root_new);          
                tree_new->SetWeight(root_new->GetWeight());
                
                legoTreegion * tree2_new = new legoTreegion(tree2_id);  
                proc->Insert(tree2_new, origloc2);
                tree2_new->SetParentPtr(proc);
                Construct(tree2_new, root_c);
                tree2_new->SetWeight(root_c->GetWeight());
            }
            else if(td_type == 3)
            {
                unsigned origloc1 = proc->Search(tree1);
                unsigned origloc2 = proc->Search(tree2);
                unsigned origloc3 = proc->Search(par_tree2);
                if(origloc1 > origloc2) origloc1 = origloc1 - 1;
                if(origloc3 > origloc2) origloc3 = origloc3 - 1;
                
                Deconstruct(tree1);
                unsigned treeloc1= proc->Search(tree1);
                proc->Detach(treeloc1);
                delete tree1;
                Deconstruct(tree2);
                unsigned treeloc2 = proc->Search(tree2);
                proc->Detach(treeloc2);
                delete tree2;
                
                legoRegion * root_new_2 = par_tree2->GetRoot();
                int root_id_2 = par_tree2->GetRegionId();
                Deconstruct(par_tree2);
                unsigned treeloc3 = proc->Search(par_tree2);
                proc->Detach(treeloc3);
                delete par_tree2;
                
                
                legoTreegion * tree_new = new legoTreegion(tree1_id);
                proc->Insert(tree_new, origloc1);
                tree_new->SetParentPtr(proc);
                Construct(tree_new, root_new);
                tree_new->SetWeight(root_new->GetWeight());
                
                legoTreegion * tree_new_2 = new legoTreegion(root_id_2);
                proc->Insert(tree_new_2, origloc3);
                tree_new_2->SetParentPtr(proc);
                Construct(tree_new_2, root_new_2);
                tree_new_2->SetWeight(root_new_2->GetWeight());
            }
        
        //treeunform(proc);
        //treeid = (proc->FindMaxRegionId())->GetRegionId();
    }
        
    delete Mach1;
}

---