main.cc

c到DHL的转换工具

/* file "main.cc" of the structure program for SUIF */

/*  Copyright (c) 1994 Stanford University

    All rights reserved.

    This software is provided under the terms described in
    the "suif_copyright.h" include file. */

#include <suif_copyright.h>

/*
 *  This file contains the main program for the structure program for
 *  SUIF.
 */

#define RCS_BASE_FILE main_cc

#include <suif1.h>
#include <useful.h>

RCS_BASE(
    "$Id: main.cc,v 1.1.1.1 1998/06/16 15:18:59 brm Exp $")

INCLUDE_SUIF_COPYRIGHT

/*----------------------------------------------------------------------*
    Begin Documentation
 *----------------------------------------------------------------------*

                Summary
                -------

        The structure program builds structured control flow
        (tree_ifs, tree_loops, and tree_fors) out of unstructured
        control flow (branches and labels) where it can be done in a
        natural way.  It also turns tree_loops into tree_fors when
        they are in the right form.


 *----------------------------------------------------------------------*
    End Documentation
 *----------------------------------------------------------------------*/
/*----------------------------------------------------------------------*
    Begin Private Type Definitions
 *----------------------------------------------------------------------*/

struct arc_info
  {
    boolean broken;
    instruction *start_instr;
    instruction *end_instr;

    boolean operator==(const arc_info &) const  { return FALSE; }
  };

DECLARE_DLIST_CLASS(arc_info_list, arc_info);

/*----------------------------------------------------------------------*
    End Private Type Definitions
 *----------------------------------------------------------------------*/
/*----------------------------------------------------------------------*
    Begin Public Global Variables
 *----------------------------------------------------------------------*/

/*----------------------------------------------------------------------*
    End Public Global Variables
 *----------------------------------------------------------------------*/
/*----------------------------------------------------------------------*
    Begin Private Global Variables
 *----------------------------------------------------------------------*/

/*----------------------------------------------------------------------*
    End Private Global Variables
 *----------------------------------------------------------------------*/
/*----------------------------------------------------------------------*
    Begin Public Function Declarations
 *----------------------------------------------------------------------*/

extern int main(int argc, char *argv[]);

/*----------------------------------------------------------------------*
    End Public Function Declarations
 *----------------------------------------------------------------------*/
/*----------------------------------------------------------------------*
    Begin Private Function Declarations
 *----------------------------------------------------------------------*/

static void usage(void);
static void structure_control_on_node_list(tree_node_list *node_list);
static void structure_list_internal(tree_node_list *node_list,
                                    arc_info_list *arc_stack);
static void handle_label_instr(in_lab *the_label_instr,
                               arc_info_list *arc_stack);
static void handle_branch_instr(in_bj *the_bj, arc_info_list *arc_stack);
static void handle_mbr_instr(in_mbr *the_mbr, arc_info_list *arc_stack);
static void build_if(arc_info *the_info);
static void build_do(arc_info *the_info);
static in_lab *split_out(in_lab *target, in_bj *focus);
static void rename_inners(instruction_list *i_list, instruction_list_e *start,
                          instruction *end, label_sym *new_label,
                          label_sym *old_label);
static void move_nodes(tree_node *before, tree_node *after,
                       tree_node_list *new_list);
static void destroy_node(tree_node *old_node);
static boolean is_if_else_boundary(in_bj *the_bj, arc_info_list *arc_stack);
static void force_same_list(tree_node *node1, tree_node *node2);

/*----------------------------------------------------------------------*
    End Private Function Declarations
 *----------------------------------------------------------------------*/
/*----------------------------------------------------------------------*
    Begin Public Function Implementations
 *----------------------------------------------------------------------*/

extern int main(int argc, char *argv[])
  {
    start_suif(argc, argv);

    if ((argc < 3) || (argc % 2 != 1))
        usage();

    for (int arg_num = 1; arg_num < argc; arg_num += 2)
        fileset->add_file(argv[arg_num], argv[arg_num + 1]);

    fileset->reset_iter();
    while (TRUE)
      {
        file_set_entry *fse = fileset->next_file();
        if (fse == NULL)
            break;
        fse->reset_proc_iter();
        while (TRUE)
          {
            proc_sym *this_proc_sym = fse->next_proc();
            if (this_proc_sym == NULL)
                break;
            this_proc_sym->read_proc(TRUE, FALSE);
            structure_control_on_node_list(this_proc_sym->block()->body());
            this_proc_sym->write_proc(fse);
            this_proc_sym->flush_proc();
          }
      }

    exit_suif();
    return 0;
  }

/*----------------------------------------------------------------------*
    End Public Function Implementations
 *----------------------------------------------------------------------*/
/*----------------------------------------------------------------------*
    Begin Private Function Implementations
 *----------------------------------------------------------------------*/

static void usage(void)
  {
    fprintf(stderr, "usage: %s <infile> <outfile> { <infile> <outfile> }*\n",
            _suif_prog_base_name);
    exit(1);
  }

static void structure_control_on_node_list(tree_node_list *node_list)
  {
    arc_info_list arc_stack;

    build_label_info(node_list);
    structure_list_internal(node_list, &arc_stack);
    remove_label_info(node_list);

    arc_info_list_iter arc_iter(&arc_stack);
    while (!arc_iter.is_empty())
      {
        arc_info this_info = arc_iter.step();
        assert(this_info.end_instr == NULL);
      }
  }

static void structure_list_internal(tree_node_list *node_list,
                                    arc_info_list *arc_stack)
  {
    tree_node_list_iter node_iter(node_list);
    while (!node_iter.is_empty())
      {
        tree_node *this_node = node_iter.step();
        switch (this_node->kind())
          {
            case TREE_INSTR:
              {
                tree_instr *this_tree_instr = (tree_instr *)this_node;
                instruction *this_instr = this_tree_instr->instr();
                switch (this_instr->opcode())
                  {
                    case io_btrue:
                    case io_bfalse:
                    case io_jmp:
                      {
                        in_bj *the_bj = (in_bj *)this_instr;

                        /* Handle if-else boundary case */
                        if (is_if_else_boundary(the_bj, arc_stack))
                          {
                            label_info *info = get_lab_info(the_bj->target());

                            (void)(arc_stack->pop());
                            do
                              {
                                this_node = node_iter.step();
                                assert(this_node->is_instr());
                                this_tree_instr = (tree_instr *)this_node;
                                this_instr = this_tree_instr->instr();
                              } while (this_instr->opcode() == io_mrk);

                            arc_info this_arc_info;
                            this_arc_info.broken = FALSE;
                            this_arc_info.start_instr = this_instr;
                            this_arc_info.end_instr = info->definition;
                            arc_stack->push(this_arc_info);
                          }
                        else
                          {
                            handle_branch_instr(the_bj, arc_stack);
                          }

                        break;
                      }
                    case io_lab:
                      {
                        in_lab *the_label_instr = (in_lab *)this_instr;
                        handle_label_instr(the_label_instr, arc_stack);
                        break;
                      }
                    case io_mbr:
                      {
                        in_mbr *the_mbr = (in_mbr *)this_instr;
                        handle_mbr_instr(the_mbr, arc_stack);
                        break;
                      }
                    default:
                        break;
                  }
                break;
              }
            case TREE_LOOP:
              {
                tree_loop *the_loop = (tree_loop *)this_node;
                structure_control_on_node_list(the_loop->body());
                structure_control_on_node_list(the_loop->test());
                break;
              }
            case TREE_FOR:
              {
                tree_for *the_for = (tree_for *)this_node;
                structure_control_on_node_list(the_for->body());
                structure_control_on_node_list(the_for->landing_pad());
                break;
              }
            case TREE_IF:
              {
                tree_if *the_if = (tree_if *)this_node;
                structure_control_on_node_list(the_if->header());
                structure_control_on_node_list(the_if->then_part());
                structure_control_on_node_list(the_if->else_part());
                break;
              }
            case TREE_BLOCK:
              {
                tree_block *the_block = (tree_block *)this_node;
                structure_list_internal(the_block->body(), arc_stack);
                break;
              }
            default:
                assert(FALSE);
          }
      }
  }

static void handle_label_instr(in_lab *the_label_instr,
                               arc_info_list *arc_stack)
  {
    label_sym *the_label_sym = the_label_instr->label();
    label_info *info = get_lab_info(the_label_sym);

    int forward_count = info->forward_jumps.count();
    boolean is_top = TRUE;
    arc_info_list_e *follow_stack = arc_stack->head();
    while (forward_count > 0)
      {
        assert(follow_stack != NULL);
        arc_info_list_e *next_stack_e = follow_stack->next();
        if (follow_stack->contents.end_instr == the_label_instr)
          {
            if (is_top && (!follow_stack->contents.broken))
                build_if(&(follow_stack->contents));
            arc_stack->remove(follow_stack);
            delete follow_stack;
            --forward_count;
          }
        else
          {
            follow_stack->contents.broken = TRUE;
            is_top = FALSE;
          }
        follow_stack = next_stack_e;
      }

    instruction_list_iter backward_iter(&(info->backward_jumps));
    while (!backward_iter.is_empty())
      {
        instruction *this_instr = backward_iter.step();
        arc_info this_arc_info;
        this_arc_info.broken = FALSE;
        this_arc_info.start_instr = the_label_instr;
        this_arc_info.end_instr = this_instr;
        arc_stack->push(this_arc_info);
      }
  }

static void handle_branch_instr(in_bj *the_bj, arc_info_list *arc_stack)
  {
    if (is_backward_branch(the_bj))
      {
        boolean is_top = TRUE;
        arc_info_list_e *follow_stack = arc_stack->head();
        while (TRUE)
          {
            assert(follow_stack != NULL);
            arc_info_list_e *next_stack_e = follow_stack->next();
            if (follow_stack->contents.end_instr == the_bj)
              {
                if (is_top && (!follow_stack->contents.broken))
                    build_do(&(follow_stack->contents));
                arc_stack->remove(follow_stack);
                delete follow_stack;
                return;
              }
            else
              {
                follow_stack->contents.broken = TRUE;
                is_top = FALSE;
              }
            follow_stack = next_stack_e;
          }
      }
    else
      {
        arc_info this_arc_info;
        this_arc_info.broken = FALSE;
        this_arc_info.start_instr = the_bj;
        this_arc_info.end_instr = get_lab_info(the_bj->target())->definition;
        arc_stack->push(this_arc_info);
      }
  }

static void handle_mbr_instr(in_mbr *the_mbr, arc_info_list *arc_stack)
  {
    int backward_count = num_mbr_back_labs(the_mbr);
    arc_info_list_e *follow_stack = arc_stack->head();
    while (backward_count > 0)
      {
        assert(follow_stack != NULL);
        arc_info_list_e *next_stack_e = follow_stack->next();
        if (follow_stack->contents.end_instr == the_mbr)
          {
            arc_stack->remove(follow_stack);
            delete follow_stack;
            --backward_count;
          }
        else
          {
            follow_stack->contents.broken = TRUE;
          }
        follow_stack = next_stack_e;
      }

    unsigned num_labs = the_mbr->num_labs();
    for (unsigned lab_num = 0; lab_num < num_labs; ++lab_num)
      {
        label_sym *this_label = the_mbr->label(lab_num);
        if (!mbr_lab_is_backward(the_mbr, this_label))
          {
            arc_info this_arc_info;
            this_arc_info.broken = TRUE;
            this_arc_info.start_instr = the_mbr;
            this_arc_info.end_instr = get_lab_info(this_label)->definition;
            arc_stack->push(this_arc_info);
          }
      }

    if (!mbr_lab_is_backward(the_mbr, the_mbr->default_lab()))
      {
        arc_info this_arc_info;
        this_arc_info.broken = TRUE;
        this_arc_info.start_instr = the_mbr;
        this_arc_info.end_instr =
                get_lab_info(the_mbr->default_lab())->definition;
        arc_stack->push(this_arc_info);
      }
  }

static void build_if(arc_info *the_info)
  {
    assert(!the_info->broken);
    assert((the_info->start_instr->opcode() == io_btrue) ||
           (the_info->start_instr->opcode() == io_bfalse) ||
           (the_info->start_instr->opcode() == io_jmp) ||
           (the_info->start_instr->opcode() == io_lab));
    assert(the_info->end_instr != NULL);
    assert(the_info->end_instr->opcode() == io_lab);

    in_lab *end_label_instr = (in_lab *)(the_info->end_instr);
    tree_node *end_node = end_label_instr->owner();

    tree_node_list *parent_list = end_node->parent();

    tree_node_list *new_header = new tree_node_list;
    tree_node_list *new_then = new tree_node_list;
    tree_node_list *new_else = new tree_node_list;

    label_sym *jumpto_sym;
    in_bj *start_bj;
    if (the_info->start_instr->opcode() == io_lab)
      {
        in_lab *jumpto_lab_instr = (in_lab *)(the_info->start_instr);
        jumpto_sym = jumpto_lab_instr->label();
        label_info *jumpto_info = get_lab_info(jumpto_sym);
        assert(jumpto_info->forward_jumps.count() == 1);
        assert(jumpto_info->backward_jumps.is_empty());
        instruction *start_instr = jumpto_info->forward_jumps.head()->contents;