home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / ae / AE / ae.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-02-28  |  15.9 KB  |  717 lines
  1. /* AE program profiling system.
  2.    Code for GNU gcc compiler.
  3.    Copyright (C) 1989, 1990 by James R. Larus (larus@cs.wisc.edu)
  4.  
  5.    AE and AEC are free software; you can redistribute it and/or modify it
  6.    under the terms of the GNU General Public License as published by the
  7.    Free Software Foundation; either version 1, or (at your option) any
  8.    later version.
  9.  
  10.    AE and AEC are distributed in the hope that it will be useful, but
  11.    WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13.    General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with GNU CC; see the file COPYING.  If not, write to James R.
  17.    Larus, Computer Sciences Department, University of Wisconsin--Madison,
  18.    1210 West Dayton Street, Madison, WI 53706, USA or to the Free
  19.    Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21.  
  22. /* $Header: /var/home/larus/AE/AE/RCS/ae.c,v 2.3 90/02/14 15:44:28 larus Exp Locker: larus $ */
  23.  
  24.  
  25. /* AE profiling code is inserted into a function in two stages.  In
  26.    the first stage, the function is analyzed to find which pseudo
  27.    registers contain values used in address computations and which
  28.    instructions mark the beginning of interesting events (e.g., loops,
  29.    basic blocks).  This stage occurs after gcc has done most of its
  30.    optimization, but before pseudo register references are transformed
  31.    into hard registers.
  32.  
  33.    The second stage occurs just before instructions are written to the
  34.    assembler output file.  At each interesting instruction, we invoke a
  35.    routine that can output a schema event or add code to the function to
  36.    record a runtime event. */
  37.  
  38.  
  39. #include <stdio.h>
  40. #include "config.h"
  41. #include "rtl.h"
  42. #include "basic-block.h"
  43. #include "flags.h"
  44. #include "tree.h"
  45. #include "ae.h"
  46. #include "ae-machine.h"
  47. #include "schema.h"
  48.  
  49.  
  50. void ae_after_block_end ();
  51. void ae_before_block_end ();
  52. void ae_block_start ();
  53. void ae_function_end ();
  54. void ae_function_start ();
  55. void analyze_func_for_ae ();
  56. void analyze_loops ();
  57. void check_for_mem_refs ();
  58. int condjump_p ();
  59. list defns_reaching_insn ();
  60. int difficulty_of_insn ();
  61. int difficulty_of_pattern ();
  62. void ensure_value_is_known ();
  63. void find_defns_reaching_uses ();
  64. void find_insn_dependences ();
  65. void find_mem_refs ();
  66. rtx gen_rtx ();
  67. int get_max_uid ();
  68. int implicit_last_block ();
  69. int insn_marked_p ();
  70. rtx insn_or_label ();
  71. void jump_optimize ();
  72. rtx jump_target ();
  73. void mark_insn ();
  74. int multiway_jump_p ();
  75. rtx next_insn_or_label ();
  76. void reaching_defn_analysis ();
  77. void record_insn_effects ();
  78. int simplejump_p ();
  79.  
  80.  
  81. void abort ();
  82. void bzero ();
  83. void error ();
  84. void fflush ();
  85. void free ();
  86. char *malloc ();
  87.  
  88.  
  89. rtx *basic_block_end;
  90. rtx *basic_block_head;
  91. FILE *flow_dump_file;
  92. int max_regno;
  93. FILE *schema_out_file;
  94.  
  95.  
  96.  
  97. /* Entry N is information about instruction N. */
  98.  
  99. aux_insn_info *insn_info;
  100.  
  101.  
  102. /* Function's name. */
  103.  
  104. char *fun_name;
  105.  
  106.  
  107. /* Non-zero means write register value upon function entry. */
  108.  
  109. char record_reg_on_entry [FIRST_PSEUDO_REGISTER];
  110.  
  111.  
  112.  
  113. /* Initialize ae profiling of a function by collecting information
  114.    about the instructions and basic blocks. */
  115.  
  116. void
  117. ae_function (insns, asm_out_file, write_symbols, optimize, decl)
  118.      rtx insns;
  119.      FILE *asm_out_file;
  120.      enum debugger write_symbols;
  121.      int optimize;
  122.      tree decl;
  123. {
  124.   /* Get the function's name, as described by its rtl.
  125.      This may be different from the decl_name name used in the source file.
  126.      Derived from: ASSEMBLE_FUNCTION. */
  127.   rtx x = DECL_RTL (decl);
  128.   rtx n;
  129.   register int i;
  130.  
  131.   if (GET_CODE (x) != MEM)
  132.     abort ();
  133.   n = XEXP (x, 0);
  134.   if (GET_CODE (n) != SYMBOL_REF)
  135.     abort ();
  136.   fun_name = XSTR (n, 0);
  137.  
  138.   /* Initialize data structures. */
  139.   insn_info =
  140.     (aux_insn_info *) malloc (get_max_uid () * sizeof (aux_insn_info));
  141.   bzero (insn_info, get_max_uid () * sizeof (aux_insn_info));
  142.   initialize_look_ahead_buffer ();
  143.   bzero (record_reg_on_entry, FIRST_PSEUDO_REGISTER * sizeof (char));
  144.  
  145.   analyze_func_for_ae (insns, optimize);
  146. }
  147.  
  148.  
  149. /* Invoked after profiling a function. */
  150.  
  151. void
  152. ae_end_function ()
  153. {
  154.   if (n_basic_blocks == 0)
  155.     ae_function_start ();    /* Did not see any instructions */
  156.   record_insn_effects (NULL, NULL); /* Flush buffer */
  157.   if (implicit_last_block ())
  158.     {
  159.       /* Last instruction is cjump w/ fall-thru to implicit block. */
  160.       ae_block_start (NULL, n_basic_blocks, 1);
  161.       ae_before_block_end (NULL, n_basic_blocks);
  162.       ae_after_block_end (NULL, n_basic_blocks);
  163.     }
  164.   ae_function_end ();
  165.   free (insn_info);
  166.   fflush (schema_out_file);
  167. }
  168.  
  169.  
  170. /* Make a pass over the code for a function and find all which
  171.    instructions mark the beginning of interesting events. */
  172.  
  173. static void
  174. analyze_func_for_ae (insns, optimize)
  175.      rtx insns;
  176.      int optimize;
  177. {
  178.   register rtx insn, x;
  179.   register int i;
  180.  
  181.   if (!optimize)
  182.     /* We need the jump links, even if optimizations isn't turned on. */
  183.     jump_optimize (insns, 0, 0);
  184.  
  185.   /* Reanalysis the function's control flow (which may have changed since
  186.      flow analysis) and compute reaching definitions. */
  187.   reaching_defn_analysis (insns, max_regno, flow_dump_file);
  188.  
  189.   for (insn = insns; insn != NULL; insn = NEXT_INSN (insn))
  190.     if (REAL_INSN_P (insn))
  191.       check_for_mem_refs (insn);
  192.  
  193.   /* Mark the control flow graphs on the instructions. */
  194.   for (i = 0; i < n_basic_blocks; i++)
  195.     {
  196.       /* Mark first and last instruction or label in each basic block. */
  197.       mark_insn (basic_block_head [i], BLOCK_START_FLAG);
  198.       insn_info [INSN_UID (basic_block_head [i])].in_block = i;
  199.  
  200.       x = basic_block_end [i];
  201.       if (x != NULL)
  202.     {
  203.       mark_insn (x, BLOCK_END_FLAG);
  204.       if (GET_CODE (x) == CODE_LABEL)
  205.         ;
  206.       else if (GET_CODE (x) == JUMP_INSN && simplejump_p (x))
  207.         mark_insn (jump_target (x), JUMP_TARGET_FLAG);
  208.       else if (GET_CODE (x) == JUMP_INSN && condjump_p (x))
  209.         {
  210.           /* Record targets of conditional branch. */
  211.           mark_insn (jump_target (x), CJUMP_TARGET_FLAG);
  212.           /* Fall-thru block is target also. */
  213.           mark_insn (next_insn_or_label (x, 1), CJUMP_TARGET_FLAG);
  214.         }
  215.       else if (multiway_jump_p (x))
  216.         {
  217.           rtx body =  PATTERN (x);
  218.           register int vlen, j;
  219.  
  220.           vlen = XVECLEN (body, 0);
  221.           for (j = 0; j < vlen; j++)
  222.         mark_insn (XEXP (XVECEXP (body, 0, j), 0), CJUMP_TARGET_FLAG);
  223.         }
  224.     }
  225.     }
  226.  
  227.   /* Mark first and last instruction in function. */
  228.   if (n_basic_blocks > 0)
  229.     {
  230.       mark_insn (insn_or_label (basic_block_head [0], 1), FUNCTION_START_FLAG);
  231.       mark_insn (basic_block_end [n_basic_blocks - 1], FUNCTION_END_FLAG);
  232.     }
  233.  
  234.   analyze_loops (insns);
  235. }
  236.  
  237.  
  238. void
  239. mark_insn (insn, flag)
  240.      rtx insn;
  241.      int flag;
  242. {
  243.   if (insn != NULL)
  244.     insn_info [INSN_UID (insn)].flags |= flag;
  245. }
  246.  
  247.  
  248. int
  249. insn_marked_p (insn, flag)
  250.      rtx insn;
  251.      int flag;
  252. {
  253.   if (insn != NULL)
  254.     return (insn_info [INSN_UID (insn)].flags & flag);
  255.   else
  256.     return 0;
  257. }
  258.  
  259.  
  260. static rtx check_insn;        /* Too bad C doesn't have closures */
  261.  
  262.  
  263. /* Check whether an instruction accesses memory, and if so, mark the
  264.    instructions that produce operands for the load/store. */
  265.  
  266. static void
  267. check_for_mem_refs (insn)
  268.      rtx insn;
  269. {
  270.   void thunk_for_check_expr ();
  271.  
  272.   check_insn = insn;
  273.   APPLY_TO_EXP_IN_INSN (PATTERN (insn), e,
  274.             find_mem_refs (e, thunk_for_check_expr));
  275. }
  276.  
  277.  
  278. static void
  279. thunk_for_check_expr (exp, base, offset)
  280.      rtx exp, base, offset;
  281. {
  282.   if (REG_P (base))
  283.     ensure_value_is_known (check_insn, base);
  284.   if (offset && REG_P (offset))
  285.     ensure_value_is_known (check_insn, offset);
  286. }
  287.  
  288.  
  289. /* Traverse an rtx expression X and invoke FUN on each MEM reference.
  290.    Pass the expression, base, and offset as arguments. */
  291.  
  292. void
  293. find_mem_refs (x, fun)
  294.      register rtx x;
  295.      void (*fun) ();
  296. {
  297.   if (GET_CODE (x) == MEM)
  298.     {
  299.       register rtx em = XEXP (x, 0);
  300.  
  301.       if (REG_P (em))
  302.     fun (x, em, NULL);
  303.       else if (GET_CODE (em) == PLUS)
  304.     fun (x, XEXP (em, 0), XEXP (em, 1));
  305.       else if (GET_CODE (em) == MINUS)
  306.     fun (x, XEXP (em, 0),
  307.          gen_rtx (CONST_INT, VOIDmode, - XINT (XEXP (em, 1), 0)));
  308.       else if (CONSTANT_P (em))
  309.     fun (x, em, NULL);
  310.     }
  311.   else
  312.     APPLY_TO_EXP_IN_INSN (x, e, find_mem_refs (e, fun));
  313. }
  314.  
  315.  
  316.  
  317. /* Return the nth instruction or label *following* a given instruction.
  318.    Return NULL if there is no such object. */
  319.  
  320. rtx
  321. next_insn_or_label (insn, n)
  322.      register rtx insn;
  323.      register int n;
  324. {
  325.   for (insn = NEXT_INSN (insn) ; insn != NULL; insn = NEXT_INSN (insn))
  326.     if (!INSN_DELETED_P (insn)
  327.     && (REAL_INSN_P (insn) || GET_CODE (insn) == CODE_LABEL))
  328.       if (--n == 0)
  329.     return insn;
  330.  
  331.   return NULL;
  332. }
  333.  
  334.  
  335. /* Return the nth instruction or label *from* a given instruction
  336.    (0th => insn). Return NULL if there is no such object. */
  337.  
  338. rtx
  339. insn_or_label (insn, n)
  340.      register rtx insn;
  341.      int n;
  342. {
  343.   for ( ; insn != NULL; insn = NEXT_INSN (insn))
  344.     if (!INSN_DELETED_P (insn)
  345.     && (REAL_INSN_P (insn) || GET_CODE (insn) == CODE_LABEL))
  346.       if (--n <= 0)
  347.     return insn;
  348.  
  349.   return NULL;
  350. }
  351.  
  352.  
  353. /* Given an instruction, return the instruction at the head of its
  354.    block.  Return NULL if there is no such instruction. */
  355.  
  356. rtx
  357. find_block_head (insn)
  358.      rtx insn;
  359. {
  360.  
  361.   for ( ; insn != NULL; insn = PREV_INSN (insn))
  362.     if (insn_marked_p (insn, BLOCK_START_FLAG))
  363.       return insn;
  364.  
  365.   return NULL;
  366. }
  367.  
  368.  
  369. /* Return the instruction that is the target of a jump instruction. */
  370.  
  371. rtx
  372. jump_target (insn)
  373.      rtx insn;
  374. {
  375.   rtx p = PATTERN (insn);
  376.   rtx e = SET_SRC (p);
  377.  
  378.   if (GET_CODE (e) == LABEL_REF)
  379.     return XEXP (e, 0);
  380.   else if (GET_CODE (XEXP (e, 1)) == LABEL_REF)
  381.     return XEXP (XEXP (e, 1), 0);
  382.   else
  383.     return XEXP (XEXP (e, 2), 0);
  384. }
  385.  
  386.  
  387. /* Return non-zero if instruction is a multiway (not just conditional)
  388.    branch. */
  389.  
  390. int
  391. multiway_jump_p (insn)
  392.      rtx insn;
  393. {
  394.   if (GET_CODE (insn) == JUMP_INSN)
  395.     {
  396.       rtx body =  PATTERN (insn);
  397.       return (GET_CODE (body) == ADDR_VEC || GET_CODE (body) == ADDR_DIFF_VEC);
  398.     }
  399.   else
  400.     return 0;
  401. }
  402.  
  403.  
  404. /* Return non-zero if block in which INSN is the first instruction is
  405.    the target of a conditional jump. */
  406.  
  407. int
  408. cjump_target_p (insn)
  409.      rtx insn;
  410. {
  411.   rtx block_head = insn;
  412.  
  413.   if (block_head != NULL)
  414.     return (insn_marked_p (block_head, CJUMP_TARGET_FLAG));
  415.   else
  416.     return 0;
  417. }
  418.  
  419.  
  420. /* Given the first instruction of a block, return the block's number. */
  421.  
  422. int
  423. head_to_block_number (target_head)
  424.      register rtx target_head;
  425. {
  426.   return insn_info [INSN_UID (target_head)].in_block;
  427. }
  428.  
  429.  
  430.  
  431. /* Given an INSN that uses register REG, mark all instructions that
  432.    produce a value for REG so that we know its contents when executing
  433.    the schema.
  434.  
  435.    Instructions fall into three catagories:
  436.  
  437.    Easy.  Rx <- constant or Rx <- address
  438.  
  439.    Hard.  Rx <- Ry op Rz
  440.  
  441.    Impossible.  Rx <- mem [...]
  442.         Rx <- call (...)
  443.  
  444.    Easy instructions can obviously be calculated by the schema.
  445.    Impossible instructions require an event to record the value loaded
  446.    from memory.
  447.  
  448.    Hard instructions appear to require some effort.  If we know their
  449.    operands, we can obviously calculate their result in the schema.
  450.    Hence, we need to know Ry and Rz in the schema--which we ensure by
  451.    applying the process recursively.
  452.  
  453.    A cycle of hard instructions presents no problems since the initial
  454.    values must come from instructions outside of the cycle. */
  455.  
  456.  
  457. /* Ensure that the value of REG is known for instruction INSN. */
  458.  
  459. static void
  460. ensure_value_is_known (insn, reg)
  461.      rtx insn, reg;
  462. {
  463.   list defns = defns_reaching_insn (insn, reg);
  464.  
  465.   if (defns != NULL)
  466.     DOLIST (d, rtx, defns, find_insn_dependences (d))
  467.   else
  468.     find_defns_reaching_uses (insn, insn);
  469. }
  470.  
  471.  
  472. /* Find the dependences between `hard' instructions starting with the
  473.    given instruction. */
  474.  
  475. static void
  476. find_insn_dependences (insn)
  477.      register rtx insn;
  478. {
  479.   if (insn_marked_p (insn,
  480.              EASY_INSN_FLAG | HARD_INSN_FLAG | IMPOSSIBLE_INSN_FLAG))
  481.     /* Have already seen this instruction. */
  482.     return;
  483.  
  484.   switch (difficulty_of_insn (insn))
  485.     {
  486.     case EASY_INSN_FLAG:
  487.       mark_insn (insn, EASY_INSN_FLAG);
  488.       break;
  489.  
  490.     case HARD_INSN_FLAG:
  491.       mark_insn (insn, HARD_INSN_FLAG);
  492.       find_defns_reaching_uses (insn, insn);
  493.       break;
  494.  
  495.     case IMPOSSIBLE_INSN_FLAG:
  496.       mark_insn (insn, IMPOSSIBLE_INSN_FLAG);
  497.       break;
  498.  
  499.     default:
  500.       error ("Unknown instruction difficulty."); /*NOTREACHED*/
  501.     }
  502. }
  503.  
  504.  
  505. /* Return a value indicating the whether INSN is easy, hard, or impossible. */
  506.  
  507. static int
  508. difficulty_of_insn (insn)
  509.      rtx insn;
  510. {
  511.   return difficulty_of_pattern (PATTERN (insn));
  512. }
  513.  
  514.  
  515. static int
  516. difficulty_of_pattern (p)
  517.      rtx p;
  518. {
  519.   if (GET_CODE (p) == SET)
  520.     {
  521.       register rtx e = SET_SRC (p);
  522.  
  523.       while (1)
  524.     switch (GET_CODE (e))
  525.       {
  526.       case PLUS:
  527.       case MINUS:
  528.       case MULT:
  529.       case DIV:
  530.       case MOD:
  531.       case AND:
  532.       case IOR:
  533.       case LSHIFT:
  534.       case ASHIFT:
  535.       case LSHIFTRT:
  536.         return HARD_INSN_FLAG;
  537.  
  538.       case NEG:
  539.       case NOT:
  540.         return HARD_INSN_FLAG;
  541.  
  542.       case SYMBOL_REF:
  543.         return EASY_INSN_FLAG;
  544.  
  545.       case SIGN_EXTEND:
  546.         e = XEXP (e, 0);
  547.         break;
  548.  
  549.       case CONST:
  550.         {
  551.           /* Instruction is: rx <- @sym or rx <- @sym + c. */
  552.           rtx t = XEXP (e, 0);
  553.           rtx base, offset;
  554.  
  555.           if (GET_CODE (t) == PLUS)
  556.         {
  557.           base = XEXP (t, 0), offset = XEXP (t, 1);
  558.           if (GET_CODE (base) == SYMBOL_REF
  559.               && GET_CODE (offset) == CONST_INT)
  560.             return EASY_INSN_FLAG;
  561.           else
  562.             return IMPOSSIBLE_INSN_FLAG;
  563.         }
  564.           else if (GET_CODE (t) == SYMBOL_REF)
  565.         return EASY_INSN_FLAG;
  566.           else
  567.         return IMPOSSIBLE_INSN_FLAG;
  568.         }
  569.  
  570.       case CONST_INT:
  571.         return EASY_INSN_FLAG;
  572.  
  573.       case REG:
  574.       case SUBREG:
  575.         return HARD_INSN_FLAG;
  576.  
  577.       case LABEL_REF:
  578.         return EASY_INSN_FLAG;
  579.  
  580.       case CALL:
  581.         return IMPOSSIBLE_INSN_FLAG;
  582.  
  583.       default:
  584.         return IMPOSSIBLE_INSN_FLAG;
  585.       }
  586.     }
  587.   else if (GET_CODE (p) == PARALLEL)
  588.     {
  589.       register int i;
  590.       int difficulty = 0;
  591.  
  592.       /* Instruction is as difficult as the hardest piece. */
  593.       for (i = 0; i < XVECLEN (p, 0); i ++)
  594.     {
  595.       int d = difficulty_of_pattern (XVECEXP (p, 0, i));
  596.       if (d > difficulty)
  597.         difficulty = d;
  598.     }
  599.       return difficulty;
  600.     }
  601.   else
  602.     return IMPOSSIBLE_INSN_FLAG;
  603. }
  604.  
  605.  
  606. /* Given an INSN, find all *uses* of values contained in registers in the
  607.    instruction and ensure that their values is known. */
  608.  
  609. static void
  610. find_defns_reaching_uses (insn, x)
  611.      rtx insn, x;
  612. {
  613.   register int regno;
  614.  
  615.   switch (GET_CODE (x))
  616.     {
  617.     case LABEL_REF:
  618.     case SYMBOL_REF:
  619.     case CONST_INT:
  620.     case CONST:
  621.     case CONST_DOUBLE:
  622.     case CC0:
  623.     case PC:
  624.     case CLOBBER:
  625.     case ADDR_VEC:
  626.     case ADDR_DIFF_VEC:
  627.     case ASM_INPUT:
  628.       return;
  629.  
  630.     case SUBREG:
  631.       x = SUBREG_REG (x);
  632.       /* This isn't supposed to happen, but it does... */
  633.       if (GET_CODE (x) == MEM) goto default_case;
  634.       /* Fall through */
  635.  
  636.     case REG:
  637.       regno = REGNO (x);
  638.       {
  639.     list defns = defns_reaching_insn (insn, x);
  640.  
  641.     if (defns == NULL || REGISTER_DEFINED_IN_CALL (regno))
  642.       record_reg_on_entry [regno] = 1; /* Need value upon function entry */
  643.     DOLIST (d, rtx, defns, {find_insn_dependences (d);});
  644.       }
  645.       return;
  646.  
  647.     case INSN:
  648.     case CALL_INSN:
  649.     case JUMP_INSN:
  650.       find_defns_reaching_uses (insn, PATTERN (x));
  651.       return;
  652.  
  653.     case SET:
  654.       if (GET_CODE (SET_DEST (x)) == MEM)
  655.     /* If a store instruction, then get address of store */
  656.     find_defns_reaching_uses (insn, SET_DEST (x));
  657.       else
  658.     /* Otherwise, want the inputs to the computation */
  659.     find_defns_reaching_uses (insn, SET_SRC (x));
  660.       return;
  661.  
  662.     default:
  663.     default_case:
  664.       APPLY_TO_EXP_IN_INSN (x, e, find_defns_reaching_uses (insn, e));
  665.       return;
  666.     }
  667. }
  668.  
  669.  
  670.  
  671. /* List operations: */
  672.  
  673. list
  674. cons (head, tail)
  675.      int head;
  676.      list tail;
  677. {
  678.   register list x = (list) malloc (sizeof (list_cell));
  679.  
  680.   CAR (x) = head;
  681.   CDR (x) = tail;
  682.   return (x);
  683. }
  684.  
  685.  
  686. /* Pop and deallocate the first element in a list and return the tail
  687.    of the list. */
  688.  
  689. list
  690. cdr_n_free (lst)
  691.      list lst;
  692. {
  693.   list n;
  694.  
  695.   if (lst == NULL)
  696.     error ("Pop null list?");
  697.  
  698.   n = CDR (lst);
  699.   free (lst);
  700.   return n;
  701. }
  702.  
  703.  
  704. void
  705. free_list (lst)
  706.      register list lst;
  707. {
  708.   register list n;
  709.  
  710.   while (lst != NULL)
  711.     {
  712.       n = CDR (lst);
  713.       free (lst);
  714.       lst = n;
  715.     }
  716. }
  717.