nodes.h

Go to the documentation of this file.

#include "misc.h"
#include "timerange.h" 

// #include "segment.h"

#ifndef NODES_H
#define NODES_H

#include "instr.h"
#include "var_access.h"
#include "vars.h"
#include "labels.h"
#include "directives.h"
#include "stringlist.h"

#include <vector>
#include <string>

typedef enum NEXT_ASM_TOKEN_TYPE { OPCODE, OPERAND };

class CCDGNode;
class CGuestInfo;
class CFG_Node;
class CPred;
class CCode;
class Infinite_Nodes;
class CLoop;

class CCDGNodeList {
  CCDGNode * Node;
  char Name[STR_SIZE];
  NODE_TYPE Type;
  CCDGNodeList * Next, * Prev;
  TRUTH_VALUE_TYPE TV;
  int Trunc;
  CFG_Node * Parent;
 public:
  CCDGNodeList() { 
    Node = NULL; Next = Prev = NULL; TV = TV_A; Trunc = 0; 
    Name[0] = '\0'; Parent = NULL;
  }
  CCDGNodeList(CCDGNode * node, TRUTH_VALUE_TYPE tv, int trunc=0);
  CCDGNodeList(char * name, NODE_TYPE type, TRUTH_VALUE_TYPE tv);
  CCDGNodeList(CCDGNodeList * orig);
  CCDGNodeList * Copy_Subgraph();
  CCDGNodeList * Add_Node(CCDGNode * p, TRUTH_VALUE_TYPE tv, int trunc=0);
  
  CCDGNodeList * Add_Node(char * name, NODE_TYPE type, TRUTH_VALUE_TYPE tv);
  CCDGNodeList * Add_Node(char * start, bool before);
  CCDGNodeList * Add_NodeList(CCDGNodeList * nl);
  CCDGNodeList * Insert_Node(CCDGNode * new_node, CCDGNode * ref, bool before,
                 TRUTH_VALUE_TYPE tv=TV_ANY);

  void Set_Next(CCDGNodeList * next) { 
      Next = next; 
  }

  CCDGNodeList * Get_Next() { return Next; };
  CCDGNodeList * Advance_To_Next_Guest(CGuestInfo * cur_gst, 
                       GUEST_STATE_TYPE & which_guest, 
                       CCDGNode * * nxt_gst_node, 
                       bool skip_all_preds,
                       bool skip_ABL_pred);
  
  void Set_Prev(CCDGNodeList * prev) { Prev = prev; }
  CCDGNodeList * Get_Prev() { return Prev; };
  
  CCDGNode * Get_Node() { if (this) return Node; else return NULL; };
  void Set_Node(CCDGNode * node) { Node = node; };
  char * Get_Name() { return Name; };
  CCDGNodeList * Get_Last();
  NODE_TYPE Get_Type() { return Type; };
  TRUTH_VALUE_TYPE Get_TV() { return TV; };

  void Append_Suffix_To_Names(char * str);
  
  void Set_Trunc(int trunc) { Trunc = trunc; }
  int Get_Trunc() { return Trunc; }
  
  CInstr * MakeNormOp(int instrclass,long best,long worst,char *oper1=NULL,char *oper2=NULL, char *oper3=NULL);
  CCDGNodeList * Remove_Node(int number);
  CCDGNodeList * Remove_Node(CCDGNode * p);
  bool Already_Contains(CCDGNode * node);
  CCDGNode * Find_Node(const char * name, NODE_TYPE type, bool dir_forward=true);
  CCDGNode * Find_Nodes_Branching_Here(char * name, CCDGNodeList * * nodelist, 
                       bool find_all);
  CCDGNode * Find_Nodes_Branching_Here(CCDGNode * node, CCDGNodeList
                       * * nodelist, bool find_all);

  int Num_Nodes_Branching_Here(char * name);
  int Num_Nodes_Branching_Here(CCDGNode * node);
  CCDGNode * Process_Multiple_Merge_Points(CCDGNode * node);

  CCDGNode * Find_Node_Before_Inc(const char * name, NODE_TYPE type, 
                  CCDGNodeList * end_lp);
  CCDGNode * Find_Node_Skipping_Here( void );

  void Extract_Dirs(char * asm_filename);
  void Label_Nodes();
  void Find_Vars();
  void Virtualize_Registers();
  
  void Gen_Jitter_Plots(char * base_filename);
  void Gen_Graphs();
  void Plot_Segments(char * base_filename);
  void Gen_GnuPlot_Driver(char * orig_filename, PLOT_TYPE plot);
  void Gen_Code(char * orig_filename);
  
  bool Verify_Jumps_Can_Be_Ignored(CCDGNode * ret_node);

  CCDGNodeList * Build_CDGs_From_Flat_Code();

  void Build_CFGs_From_Flat_Code();
  void Add_Exit(CCDGNodeList * exit);
  //  CCDGNodeList * Build_CDGs_From_CFGs();
  CCDGNodeList * Build_CDGs_via_CFGs() __attribute__ ((deprecated));
  CCDGNode * Find_Common_Ancestor();

  void Do_STA(bool include_guest=TRUE);
  void Find_Segments(long max_jitter);
  void Pad_Jitter(bool pad_host, bool pad_guest);
  void Find_Blocking_IO_Loops();
  void Pad_Leaving_Loop_Intact(long cocall_period,
                   bool look_for_unique_loop, 
                   char* loop_name_passed);
  void Prepare_Pad_And_Transform_Loop(CCDGNode* cur_node, long cocall_period,
                      CPred* final_pred, bool loop_specific_code);

  void Reallocate_Regs(REALLOC_TYPE realloc_method);
  void Convert_PC_Relative_Branches();
  void Convert_Local_Labels_And_Branches();

  CCDGNodeList * Guard(int reg, int bit, bool exec_condition);
  CCDGNodeList * New_Guard(int reg, int bit, bool exec_condition);
  CCDGNodeList * Add_NodeList(char * start, bool before);
  
  void Pr_Info(); 
  void Pr_Name();
  void Pr_Type();
  
  void Output_Debug();
  void Output_Debug_Names();
  void Print_Directives();
  void Set_Visited (bool v);
  long Count_Instrs();
  
  CCDGNodeList * Build_CDGs_via_CFGs(char * filename);
  CCDGNode * Get_Node_With_Label(char *label);

  void Handle_Start();
  void Handle_Default();


  void Handle_Ctrans();
  void Handle_Utrans();
  void Handle_Skip();
  void Handle_Utrans_Routine();
  CCDGNodeList * Handle_Utrans_Return();

  void Set_Parent(CFG_Node *p_parent)
  {   Parent=p_parent;     
  }
  CFG_Node * Get_Parent()
  {   return Parent;  
  }


  CFG_Node * Build_CFG_Node_Tree(int *n,CFG_Node *parent,CFG_Node *prev);

  void Set_Name(char * p_name);

  /* 
     void Build_CFG_VCG(char * filename);     
     void Build_CFG_VCG(ofstream &vcg_stream, int i);
  */
  void Fix_Call_Nodes();
  void Fix_Branch_Targets();
  void Fix_Short_Branches();

  void Open_CFG_VCG_File(char * CFG_VCG_filename);
  void Add_To_CFG_VCG_File(char * CFG_VCG_filename);
  void Close_CFG_VCG_File(char * CFG_VCG_filename);
  void Build_CFG_VCG_File(int i, char * CFG_VCG_filename);
  void Build_CFG_VCG_File(int i, bool f, char * CFG_VCG_filename);

  // these functions don't seem to be implemented anywhere:  
  // void Open_CFG_File();
  // void Add_To_CFG_File();
  // void CCDGNodeList :: Close_CFG_File();

  void Build_CFG_VCG(int i);
  void Build_CFG_VCG(int i, bool f);
  //void Open_CFG_VCG_File(char * CFG_VCG_filename);
  //void Add_To_CFG_VCG_File(char * CFG_VCG_filename);
  //void Close_CFG_VCG_File(char * CFG_VCG_filename);
  //void Build_CFG_VCG_File(int i, char * CFG_VCG_filename);
  //void Build_CFG_VCG_File(int i, bool f, char * CFG_VCG_filename);
  CCDGNodeList * Build_CDGs_for_Proc(CCDGNodeList * proc, CCDGNodeList * recent_nodes_end, CCDGNodeList * exit);
  CCDGNodeList * Build_CFGs_and_CDGs(CCDGNodeList * recent_procs, 
                     char * source_filename);

  CCDGNodeList * Add_Exit_Node();

  char * Get_Function_Name();

  CCDGNodeList * Compute_Code_End(bool begin);
  void Fix_Infinite_Blocks(CCDGNodeList * start, CCDGNodeList * exit);
  Infinite_Nodes * Get_Infinite_Nodes();
  void Reset_Infinite_Nodes();
  void Embed_CSource(); 

};

CCDGNodeList * Add_Node(CCDGNodeList * recent_nodes, char * start, bool before);


class CCDGNode {
public:
  std::string* Pre_Comments;
  std::string* Post_Comments;

  void Calculate_Segment_Times();

private:
  bool SegTimeVisited; 

  CTimeRange StartTimeFromSegmentStart;

  CTimeRange EndTimeFromSegmentStart;




protected:
  char Name[STR_SIZE];
  CStringList * Aliases; 
  int HorG;
  CTimeRange Duration;
  CTimeRange Start, End;




  CLabelCell * Label;
  bool RT;
  long TargetTime;
  NODE_TYPE Type;
  INT_OVHD_TYPE IntOvhdType;
  int SerNum;
  CCDGNode * Parent;
  CProc * Procedure;
  CCDGNodeList * Children;
  bool Visited;
  bool DFS_Visited;
  int HorPos;
  CRegAccess RegDef, RegUse;
  CDir * PrecedingDirs, * FollowingDirs;
  CCDGNode * Copy;
  int Size;
  int SubgraphSize;
  vector<string> CSourceLines; 
 public:
  CCDGNode();
  virtual ~CCDGNode() {};
  CCDGNode(CCDGNode &orig, CCDGNode &parent);
  CCDGNode * Copy_Derived(CCDGNode &parent);
  //    CCDGNode * Copy_w_Derived_Info();
  
  CCDGNode(char * name);
  bool Check(void);
  void Add_Aliases(CLabelList * alias_list);
  CStringList * Get_Aliases() { return Aliases; };
  void PreTraverse_C_C(char * (*func) (char *, const char *), 
               const char * char_arg);  
  void TraverseMethod_V_N(void (*func) (CCDGNode *), bool pre);
  void TraverseMethod_V_N_N(void (*func) (CCDGNode *, CCDGNode *), 
                CCDGNode * node_arg, bool pre);
  
  void Set_Name(char * name) { 
    assert(strlen(name)<STR_SIZE); 
    strcpy(Name, name); 
  };
  char * Get_Name() { return Name; };
  char * Get_Type_String() {
    return NodeType_Names[(this && Type)? Type : UNINIT];
  }; 
  void Print_Name_And_Type(ostream  &s) {
    if (this)
      s << Get_Name() << " " << Get_Type_String() << " "
    << (int) this << " ";
    else
      s << "Null Pointer ";
  };
  void Append_Suffix_To_Name(char * str);
  void Append_Suffix_To_Name_For_Subgraph(const char * str);
  void Append_Numbered_Suffix_To_Name(char * str, int n);
  
  void Find_Blocking_IO_Loops();
  // This function identifies each blocking I/O loops in the subgraph rooted
  // by this node and sets its IsBlockingIOLoop flag.

  void Fix_Branch_Targets();
  void Fix_Short_Branches();

  void Label_Node(float * next_section);
  void Label_This_Node(CCDGNode * prev_node);
  void Append_LabelCell(TRUTH_VALUE_TYPE tv, float section, float section_end);
  void Set_Label(char * label) { Label = new CLabelCell(label); };
  CLabelCell * Get_Label() { return Label; };
  
  int Get_Size() { // Return size of node in bytes
    //    Set_Size(); // always have a fresh version of Size
    return Size; 
  };
  int Get_SubgraphSize() { // Return size of subgraph rooted by this node in bytes
    Set_Size(); // Always have a fresh version.  This also sets SubgraphSize.
    return SubgraphSize;
  }
  virtual void Set_Size(void);  // function to calculate node size, is
  // overridden by derived classes.

  void Set_Size(int s) { Size = s; };
  
  CCDGNode * Get_Parent() { return Parent; };
  void Set_Parent(CCDGNode * parent) { Parent = parent; }; 
  
  void Add_Child(CCDGNode * child, TRUTH_VALUE_TYPE tv, int hg_select=INVALID);
  void Add_Children(CCDGNodeList * children, TRUTH_VALUE_TYPE tv, int hg_select=INVALID);
  void Add_Child(char * name, NODE_TYPE type, TRUTH_VALUE_TYPE tv);
  CCDGNode * Clone_Child(CCDGNode * orig_child, CCDGNode * ref, POS_TYPE pos, 
             TRUTH_VALUE_TYPE tv=TV_A);
  bool Insert_Child(CCDGNode * new_child, CCDGNode * ref, bool before);
  void Insert_Children(CCDGNodeList * new_children, CCDGNode * ref, bool before);
  void Insert_Padding_Children(char * name_base, long cycles, TRUTH_VALUE_TYPE side, 
                   bool delay_loop_ok);

  CCDGNodeList * Get_Children() { return Children; }
  CCDGNodeList * Get_First_Child(TRUTH_VALUE_TYPE tv=TV_ANY);
  CCDGNodeList * Get_Last_Child(TRUTH_VALUE_TYPE tv=TV_ANY, 
                int hg_sel=INVALID);
  bool Remove_Child(CCDGNode * victim);
  bool Move_Child(CCDGNode * mover, bool to_end);
  //    CCDGNodeList * Get_Last_Child();
  void Find_Children(CCDGNodeList * n);
  bool Copy_And_Integrate_Subgraph(int target_time, CCDGNodeList * new_code,
                   int seg_num);

  CCDGNode * Find_Common_Ancestor(CCDGNode * n);
  bool Has_Ancestor(CCDGNode * n);
  TRUTH_VALUE_TYPE Find_Childs_TV(CCDGNode * n);
  void Pr_Children(); 
  int Get_Num_Children(TRUTH_VALUE_TYPE tv); // This function returns the 
  // number of children of a given truth value for this node. Use TV_ANY
  // to count the total number of children.
  CCDGNode * Get_Older_Sibling(bool in_same_loop=FALSE);
  CCDGNode * Get_Younger_Sibling(bool same_parent=FALSE);
  CCDGNode * Get_Older_Sibling(bool same_parent, int h_or_g, bool RT);
  CCDGNode * Get_Sibling_At(CTimeRange * t);
  CLoop * Get_Enclosing_Loop();
  bool Reaches(CCDGNode * that);
  bool Dominates(CCDGNode * that);

  TRUTH_VALUE_TYPE Find_TV() { return Get_Parent()->Find_Childs_TV(this); };

  CProc * Get_Procedure() { return Procedure; };
  void Set_Procedure(CProc * p);
  void Set_Procedure_For_Subgraph(CProc * p);

  int Get_SerNum() { return SerNum; };
  CTimeRange * Get_Start() { return &Start; };
  CTimeRange * Get_End() { 
    assert (Duration.Get_Worst() != INVALID);
    assert (Duration.Get_Worst() != UNKNOWN);
    End = Start + Duration; 
    --End; 
    return &End; 
  };
  CCDGNode * Split(long when);
  void Set_Start(CTimeRange tr) { Start = tr; };
  
  void Set_TargetTime(long cy) { TargetTime = cy; };
  long Get_TargetTime() { return TargetTime; };
    
  CTimeRange * Get_Duration(bool include_unknown_loop_iter=FALSE) {
     return &Duration; 
  }
     
  void Mark_as_Host() { HorG = HOST; };
  void Mark_as_Guest() { HorG = GUEST; };
  void Mark_Subgraph_as_Guest();
  void Mark_HorG(int which) { HorG = which; };
  int Get_HorG() { return HorG; };
  bool Is_Host() { return (HorG == HOST); };
  bool Is_Guest() { return (HorG == GUEST); };
  bool Is_Program_Halt();

  void Mark_as_RT() { RT = TRUE; };
  void Mark_as_NRT() { RT = FALSE; };
  bool Get_RT() { return RT; };
  bool Is_RT() { return (RT == TRUE); };
  bool Is_NRT() { return (RT == FALSE); };

  bool Ends_In_Uncond_Branch(); // returns true if this node is a CCode
  // which ends in an unconditional branch
    
  CDir * Get_PrecedingDirs() { return PrecedingDirs; };
  CDir * Get_FollowingDirs() { return FollowingDirs; };
    
  void Add_PrecedingDir(char * text);
  void Add_FollowingDir(char * text);
  
  void Add_PrecedingDir(CDir *Directive);
  void Add_FollowingDir(CDir *Directive);
  
  INT_OVHD_TYPE Get_IntOvhdType() { return IntOvhdType; };
  void Set_IntOvhdType(INT_OVHD_TYPE ov) { IntOvhdType = ov; };
  void Mark_If_Discrete_Guest();
  
  void Gen_Graph(ofstream &ostream, int level);
  
  void Output_Debug(ostream &stream, bool do_full=TRUE);
  void Output_Code(ostream &stream);
  void Output_VCG(ostream &stream);
  
  void Pr_Info();
  void Pr_Name(bool t);
  
  NODE_TYPE Get_Type() { return Type;}
  void Set_Type(NODE_TYPE type) { Type = type; }
  void Pr_Type();
  
  void Set_Visited(bool v) { Visited = v; };
  bool Get_Visited() { return Visited; };
  
  bool Is_DFS_Visited() { return DFS_Visited; };
  void Set_DFS_Visited() { DFS_Visited = true; }

  void Set_HorPos(int hp) { HorPos = hp; };
  int Get_HorPos() { return HorPos; };
  
  void Calculate_Node_Duration(bool include_guests=TRUE);

  void Calculate_Node_Start(CTimeRange * par_start, bool include_guests=TRUE);
  
  void Find_Hosts(CTimeRange * Target, CGuestInfo * RII);
  void Delete_Following_Guests();
  void Delete_This_And_Following_Guests( void );
  CLoop * Find_First_Loop(long t_start, long t_stop);
  
  void Summarize_Register_DefUse_Info();
  void Find_Vars();
  bool Always_Defined(int reg);
  CRegAccess * Get_RegDef() { 
    //      assert(!registers_virtualized); 
    return &RegDef; 
  }
  CRegAccess * Get_RegUse() {
    //    assert(!registers_virtualized); 
    return &RegUse; 
  }
  CVar * Find_Prev_Ref(int reg,  CInstr * instr, bool local_instr, 
               bool look_across_loop_back, bool skip_this_node);
  void Analyze_Instruction(CInstr * instr);
  
  int Get_NumInstrs();
  long Pad(long padding_needed);
  void Set_Node_Jump_Target(char * target);
  void Insert_Padding(char * name_base, long cycles, bool pad_before, 
              bool delay_loop_ok);
  CCDGNodeList * Create_Padding_Nodes(char * name, long amount);
  CCDGNode * Get_Copy() { return Copy; };
  CCDGNode * Get_Copy(CCDGNode * parent);
  CCDGNode * Get_Last_Copy();
  CCDGNodeList * Guard(int reg, int bit, bool skip_if_set, int cond_br_type);
  CCDGNode * Find_FSM_Loop();  // look for an infinite loop holding an FSM

  void Debug_Final_Step(int n,CCDGNode * parent, TRUTH_VALUE_TYPE tv);

  CCDGNode * Get_Sibling_Before(CCDGNode * node, bool before);

  void Embed_CSource(); 

};

extern void Find_Blocking_IO_Loop(CCDGNode * n);
extern CCDGNode * Create_Padding_Node(char * name, long amount);

extern CCDGNode * Create_Derived_CDGNode(NODE_TYPE type, char * name);

class CSegmentList;
class CPred;
class CCall;

class CCode : public CCDGNode {
  CInstr * Instr;
  int NumInstrs;
  CCode * Pred[MAX_PREDECESSORS], * Succ[MAX_SUCCESSORS];
  CCDGNodeList * node_list;
  bool Infinite_Block;
  bool Visited;
public:
  CCode() : CCDGNode() {
    this->Set_Type(CODE); 
    Instr = NULL;
    NumInstrs = 0;
    for (int i=0; i<MAX_PREDECESSORS; i++)
      Pred[i] = NULL;
    for (int i=0; i<MAX_SUCCESSORS; i++)
      Succ[i] = NULL;
    Infinite_Block=true;
    Visited=false;
  };
  CCode(char * name) : CCDGNode(name) { 
    this->Set_Type(CODE); 
    Instr = NULL;
    NumInstrs = 0;
    if (trace_const)
      cout << " Code ";
    for (int i=0; i<MAX_PREDECESSORS; i++)
      Pred[i] = NULL;
    for (int i=0; i<MAX_SUCCESSORS; i++)
      Succ[i] = NULL;
    Infinite_Block=true;
    Visited=false;
  };
  CCode(const CCode & orig, CCDGNode &Parent);
  ~CCode();
  
  // instruction manipulation
  void Add_Instr_Frag(char * instr_frag);
  void Add_Instr(CInstr * instr);
  CInstr * Get_Instr() { return Instr; };
  void Set_Instr(CInstr * instr) { Instr = instr; };
  CInstr * Get_Last_Instr() { return Instr ? Instr->Get_Last() : NULL; };
  int Get_NumInstrs() { return NumInstrs; };
  void Set_NumInstrs();
  void Set_NumInstrs(int n) { NumInstrs = n; };
  void Inc_NumInstrs() { 
    NumInstrs++; 
    ((CCDGNode *)this)->Calculate_Node_Duration(); 
  };
  CVar * Find_Prev_Ref(int reg,  CInstr * instr, bool local_instr, 
               bool look_across_loop_back);
  void Prepend_Instr(CInstr * instr) {
    assert (instr);
    Instr->Set_Prev(instr);
    instr->Set_Next(Instr);
    Instr = instr;
    if (!Instr->Is_Pseudo())
      NumInstrs++;
    instr->Set_Node((CCDGNode *)this);
    // do def-use?
  };

  void Make_Jump_Node(char * target, char * node_name_root);
  CCDGNode * Split(long when, bool when_is_offset=false);
  CCode * Split_After_Byte(int where);
  CPred * Split_Off_Cond_Branch();
  CCode * Split_Off_Uncond_Branch();
  bool Contains_Call( void );
  CCall * Split_Off_Call( void );
  void Set_Size(void);
  CTimeRange * Get_Duration(bool include_unknown_loop_iter) ;
  void Output_Code(ostream &stream);
  void Output_VCG(ostream &stream);
  void Make_Loop_Control_Var_Fuser(CLoop * guest_loop, CLoop * host_loop);
  
  CCode * Get_Next_Pred(CCode * cur);
  CCode * Get_Next_Succ(CCode * cur);
  CCode * Get_Next_Succ(CCode * cur, bool value);
  
  bool Add_Pred(CCode * p); 
  bool Add_Succ(CCode * p); 
  void Clear_Pred_Succ();
  void Set_Is_Infinite_Block()
    {   Infinite_Block=true;
    }
  void Reset_Is_Infinite_Block()
    {   Infinite_Block=false;
    }
  bool Is_Infinite_Block()
    {   return Infinite_Block;
    }
  void Set_Visited()
    {   Visited=true;
    }
  void Reset_Visited()
    {   Visited=false;
    }
  bool Is_Visited()
    {   return Visited;
    }
  bool Is_Succ_Empty();

  bool Is_Succ_Present(CCode *node);

  void Set_Node_List(CCDGNodeList *p_node_list)
    {   node_list=p_node_list;
    }
  CCDGNodeList *Get_Node_List()
    {   return node_list;
    }
  bool Has_2_Succ()
    {   CCode * next1 , * next2;
    next1 = Get_Next_Succ(NULL);
    if(next1)
      next2 = Get_Next_Succ(next1);
    if(next1 && next2)
      return true;
    return false;
    };
  bool Has_Succ(CCode * node)
    {   CCode * next=NULL;
    while((next=Get_Next_Succ(next))!=NULL)
      if(next==node)
    return true;
    return false;
    };

  void DFS_Search(bool is_start);
  void Mark_Infinite_Blocks();
};

class CPred : public CCDGNode {
  CInstr * Branch;
  int ClosesLoop;
  long TruncDuration;
  int NumPadNodes;
public:
  CPred() : CCDGNode() {
    Branch = NULL;
    ClosesLoop = 0;
    TruncDuration = INVALID;
    NumPadNodes = 0;
  };
    CPred(char * name) : CCDGNode(name) { 
        this->Set_Type(PRED); 
        //      Branch[0] = '\0'; 
        Branch = new CInstr;
        ClosesLoop = 0;
        NumPadNodes = 0;
        if (trace_const)
            cout << " CPred ";
    };
    CPred(const CPred &orig, CCDGNode &parent);
    ~CPred();

    void Set_Size(void);
    int Get_Child_Subgraph_Size(TRUTH_VALUE_TYPE tv);
    void Set_Branch(char * branch);
    void Set_Branch(CInstr * branch) { 
      Branch = branch; 
      Branch->Set_Node(this);
      if (branch->Get_IS_Index() != INVALID_UC)
        Set_Size();
    };
    CInstr * Get_Branch() { return Branch; };
    void Set_ClosesLoop(int closes_loop) { ClosesLoop = closes_loop; };
    int Get_ClosesLoop() { return ClosesLoop; };
    void Add_Loop_To_Close(CCDGNode * child, TRUTH_VALUE_TYPE tv);

    void Extend_Segment(CSegmentList * seg, long max_jitter);
    void Set_TruncDuration(long t) { TruncDuration = t; };
    long Get_TruncDuration() { return TruncDuration; };

    CTimeRange Get_Duration(TRUTH_VALUE_TYPE tv);
    CTimeRange * Get_Duration() { return ((CCDGNode *) this)->Get_Duration(); };
    void Calculate_Node_Duration(bool include_guests=TRUE);
    CTimeRange Calculate_Node_Duration(TRUTH_VALUE_TYPE tv, 
                       bool include_guests=TRUE);

    CVar * Find_Prev_Ref(int reg,  CInstr * instr, bool local_instr, 
                 bool look_across_loop_back);
    long Pad(long padding_needed);
    void Pad(long padding_needed, TRUTH_VALUE_TYPE tv);
    int Get_New_Pad_Number();

    void Output_Code(ostream &stream);
    // Generate code for this CPred, including all children.
    void Output_Child_Code(ostream &stream, TRUTH_VALUE_TYPE tv, CCDGNode * start);
    // Generate code for all children of this CPred with a truth value of tv beginning
    // with node TV. Does NOT print out the CPred branch instruction.
    void Output_VCG(ostream &stream);
};

class CMultiPred : public CCDGNode {
  char Branch[STR_SIZE];
  int ClosesLoop;
 public:
  CMultiPred(char * name) : CCDGNode(name) { 
    this->Set_Type(MULTIPRED); 
    Branch[0] = '\0'; 
    ClosesLoop = 0;
    if (trace_const)
      cout << " Pred ";
  };
  ~CMultiPred();
    void Set_Size(void);
  void Set_Branch(char * branch) { 
    assert (strlen(branch) < STR_SIZE);
    strcpy(Branch, branch); 
  };
  char * Get_Branch() { return Branch; };
  void Set_ClosesLoop(int closes_loop) { ClosesLoop = closes_loop; };
  int Get_ClosesLoop() { return ClosesLoop; };
};

class CLTXList;
class CHostInfo;
class CLoop : public CCDGNode {
  int IterCount; 
  CTimeRange IterPeriod; 
  CInstr * LCB; 
  CVar * InductionVar;
  CInstr * CompareInstr;
  CLTXList * Transforms;
  bool IsBlockingIOLoop;
  int LIV_InitialValue;
  int LIV_Delta;
  int LIV_FinalValue;
public:
  CLoop() : CCDGNode() {
    IterCount = INVALID;
    InductionVar = NULL;
    CompareInstr = NULL;
    Transforms = NULL;
    LCB = NULL;
    IsBlockingIOLoop = false;
    LIV_InitialValue = LIV_Delta = LIV_FinalValue = 0;
  }
  CLoop(char * name) : CCDGNode(name) { 
    if (trace_const)
      cout << " CLoop "; 
    this->Set_Type(LOOP); 
    IterCount = INVALID;
    CompareInstr = NULL;
    Transforms = NULL;
    LCB = NULL;
    IsBlockingIOLoop = false;
  }
  CLoop(const CLoop & orig, CCDGNode &parent);
  ~CLoop();
  CLoop * Copy_Only_Node(void);
  void Adopt_Children(CCDGNode * first, CCDGNode * last);
  void Set_Size(void);

  bool Iteration_Info_Valid();
  CTimeRange * Get_Duration(bool include_unknown_loop_iter=FALSE) {
    return &Duration;
  }
  
  void Set_IterCount(int count) { IterCount = count; };
  int Get_IterCount() { return IterCount; };
  void Set_Iterations(int count);
  CTimeRange * Get_IterPeriod() { return &IterPeriod; };
  int Get_IterPeriod_w_LCB(void) { 
    if (!LCB) 
      Get_LCB(); // initialize it!
    return IterPeriod.Get_Worst() - LCB->Get_Duration()->Get_Worst(); 
  };
  void Extend_Segment(CSegmentList * seg, long max_jitter);
  void Gen_Jitter_Plot(ofstream & plot_stream);
  CVar * Find_Prev_Ref(int reg,  CInstr * instr, bool local_instr, bool look_across_loop_back);

  void Find_Control_Info();
  void Print_Control_Info(ostream & stream);
  CInstr * Get_CompareInstr(void) { return CompareInstr; };
  CInstr * Get_LCB(void);
  CPred * Get_LoopClosingPredicate(void);
  void Calculate_Node_Duration(bool include_guests=true);
  void Find_Hosts(CTimeRange * Target, CGuestInfo * RII);
  
  CLTXList * Get_Transforms() { return Transforms; };
  void Add_Transform(CHostInfo * ltx);
  void Update_Remaining_Transformations(CHostInfo * cur_ltx, 
                    CCDGNode * new_loop);
  
  long Pad(long padding_needed);
  void Peel_Iteration(POS_TYPE pos);
  CLoop * Split(int iteration);
  void Make_Guarded(CInstr * guard_instr, bool invert);
  CLoop * Make_Guarded_Copy( void );
  void Fuse_Loop_Control(CLoop * guest_loop);
  void Output_Code(ostream &stream);
  
  bool Get_IsBlockingIOLoop();
  void Set_IsBlockingIOLoop(bool b);

  bool Copy_And_Integrate_Subgraph(int t, CCDGNodeList * new_code, int seg_num);
};

class CIrrLoop : public CCDGNode {
  int IterCount;
  int InductionVar;
 public:
  CIrrLoop(char * name) : CCDGNode(name) { 
    if (trace_const)
      cout << " CIrrLoop "; 
    this->Set_Type(IRRLOOP); 
    IterCount = -1;
  }
  ~CIrrLoop();
  void Set_Size(void);
  void Set_IterCount(int count) { IterCount = count; };
  int Get_IterCount() { return IterCount; };
};

// class CVar;
class CProc : public CCDGNode {
  CSegmentList * Segments;
  CCDGNodeList * Nodes; 
  int NumInstrs;
  CVar HostVars, GuestVars;
  CRegAccess HostRegs, GuestRegs;
  long BestCaseAdjust;
  int FrameSize;
  THREAD_TYPE ThreadType;    
  PROC_TYPE ProcedureType; 
  bool BranchesStale;  
  bool STAStale;
  bool DFAStale;         
  bool LabelsStale;      
  bool Integrating;      
 
 public:
  CProc(char * name);
  ~CProc();
  void Gen_Jitter_Plot(char * filename);
  void Gen_Segment_Plot(char * filename);
  void Gen_Graph(char * filename);
  void Pad_Jitter(bool pad_host, bool pad_guest);
  void Set_Size(void);

  bool Get_BranchesStale(void);  
  bool Get_STAStale(void);       
  bool Get_DFAStale(void);       
  bool Get_LabelsStale(void);    

  void Set_BranchesStale(bool val);  
  void Set_STAStale(bool val);       
  void Set_DFAStale(bool val);       
  void Set_LabelsStale(bool val);    
  void Set_Integrating(bool val);
  bool Get_Integrating();


  CRegAccess * Get_Regs(int which) {
    switch (which) {
    case HOST: 
      return &HostRegs; break;
    case GUEST: 
      return &GuestRegs; break;
    default: 
            assert(0);
    };
    return NULL;
  };
  
  void Create_Var_File();
  CVar * Get_Vars(int which) { 
    switch (which) {
    case HOST: 
      return &HostVars; 
      break;
    case GUEST: 
      return &GuestVars; 
      break;
    default: 
      assert(0);
      break;
    };
    return NULL;
  };
  int Count_Vars(int which);
  void Print_Interference_Matrix(int which);
  //    int Count_Regs(int which, bool include_system);
  void Label_Procedure(void);
  void Find_Segments(long max_jitter);
  CSegmentList * Get_Segments() { return Segments; };
  void Set_Nodes(CCDGNodeList * n) { Nodes = n; };
  CCDGNodeList * Get_Nodes() { return Nodes; }; // List of Nodes in the procedure
  CLoop * Get_Next_Loop(CLoop * prev_loop, int h_or_g);
  
  void Set_NumInstrs(int n) { NumInstrs = n; };
  int Get_NumInstrs() { return NumInstrs; };
  
  void Do_STA(bool include_guest=TRUE);
  void Set_BestCaseAdjust(long t) { BestCaseAdjust = t; };
  void Add_To_BestCaseAdjust(long t) { BestCaseAdjust += t; };
  long Get_BestCaseAdjust() { 
    // HACK - watch out for rescheduling
    if (resched_often) 
      return 0; 
    else 
      return BestCaseAdjust; 
  };
  
  void QND_Save_Callee_Saved_Regs();
  void QND_Restore_Callee_Saved_Regs();
  void Set_FrameSize(int s) { FrameSize = s; };
  int  Get_FrameSize(void) { return FrameSize; };
  THREAD_TYPE Get_ThreadType(){ return ThreadType; }
  PROC_TYPE  Get_ProcedureType(){ return ProcedureType; }
  void Set_ThreadType(THREAD_TYPE type){ ThreadType = type; } 
  void Set_ProcedureType(PROC_TYPE type){ ProcedureType = type; }
  void Find_Interference(int which);
  void Reallocate_Regs_AVR_QND();
  void Reallocate_Regs_Alpha_QND();
  void Color_Registers();
  //    int Reassign_Var(CVar * fresh, CVar * stale);
  void Output_Code(ostream &stream);
  void Output_Code(char * fname);
  void Pad_Blocking_Loops_To_CoCallPeriod(long cocall_period, 
                       bool look_for_unique_loop, 
                       char* loop_name_passed);
};

class CCall : public CCDGNode {
  CInstr * Branch;

  CVar* DefVar[MAX_REG+1]; 

  CVar* UseVar[MAX_REG+1];

 public:
  CCall(char * name);
  ~CCall();


  CCall(CCode * code);

  void Set_Size(void);
    
  void Set_Branch(char * branch);
  void Set_Branch(CInstr * branch) { Branch = branch; Branch->Set_Node(this); };
  CInstr * Get_Branch() { return Branch; }
  CVar * Find_Prev_Ref(int reg,  CInstr * instr, bool local_instr, 
               bool look_across_loop_back);
  CVar * Find_DefVar(int reg) {
    for (int i = 0; i <= MAX_REG; i++)
      if (DefVar[i] && (DefVar[i]->Get_RegNumber() == reg))
        return DefVar[i];
    return NULL;
  }
  void Add_DefVar(CVar * var) {
    for (int i = 0; i <= MAX_REG; i++)
      if (DefVar[i] == NULL) {
    DefVar[i] = var;
    return;
      }
    // error, too many vars to fit in set
    assert(0);
  }
  
  CVar * Find_UseVar(int reg) {
    for (int i = 0; i <= MAX_REG; i++)
      if (UseVar[i] && (UseVar[i]->Get_RegNumber() == reg))
        return UseVar[i];
    return NULL;
  }
  void Add_UseVar(CVar * var) {
    for (int i = 0; i <= MAX_REG; i++)
      if (UseVar[i] == NULL) {
    UseVar[i] = var;
    return;
      }
    // error, too many vars to fit in set
    assert(0);
  }
  void Output_Code(ostream &stream);
  void Output_VCG(ostream &stream); 
};


CCDGNodeList * Parse_File(char * filename);
CCDGNodeList * Build_CDGs(CCDGNodeList * nodes);

extern char NodeType_Names[][10];

#endif // NODES_H

---