home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 357_01 / cstar1.exe / PH.C < prev    next >
C/C++ Source or Header  |  1991-06-18  |  15KB  |  714 lines
  1. /*
  2.     C* Peephole optimizer.
  3.  
  4.     source:  ph.c
  5.     started: October 26, 1985
  6.     version:
  7.         February 22, 1989
  8.  
  9.     PUBLIC DOMAIN SOFTWARE
  10.  
  11.     The CSTAR program was placed in    the public domain on June 15, 1991,
  12.     by its author and sole owner,
  13.  
  14.         Edward K. Ream
  15.         1617 Monroe Street
  16.         Madison, WI 53711
  17.         (608) 257-0802
  18.  
  19.     CSTAR may be used for any commercial or non-commercial purpose.
  20.  
  21.     See cstar.h or cstar.c for a DISCLAIMER OF WARRANTIES.
  22. */
  23. #include "cstar.h"
  24.  
  25. /*
  26.     Declare routines of this file.
  27. */
  28. void        peep_hole    (void);
  29.  
  30. static void        c_delete    (register struct node *p);
  31. static struct node *    peep0        (register struct node *p);
  32. static struct node *    peep1        (register struct node *p);
  33. static struct node *    peep2        (register struct node *p);
  34. static struct node *    peep3        (register struct node *p);
  35. static struct node *    peep4        (register struct node *p);
  36. static struct node *    peep5        (register struct node *p);
  37. static struct node *    dec_ref        (register struct node *p);
  38. static int         bxx2byy        (int code);
  39.  
  40.  
  41. /*
  42.     ----- P E E P H O L E    R O U T I N E S ----
  43. */
  44.  
  45. /*
  46.     Unlink node p from doubly-linked code list.
  47. */
  48. static void
  49. c_delete(register struct node *p)
  50. {
  51.     TRACEP("c_delete", printf("(%p)\n", p));
  52.  
  53.     if (p == NULL) {
  54.         return;
  55.     }
  56.  
  57.     /* Remove the forward link to p. */
  58.     if (p -> c_back == NULL) {
  59.         code_head = p -> c_next;
  60.     }
  61.     else {
  62.         (p -> c_back) -> c_next = p -> c_next;
  63.     }
  64.  
  65.     /* Remove the back link to p. */
  66.     if (p -> c_next == NULL) {
  67.         code_tail = p -> c_back;
  68.     }
  69.     else {
  70.         (p -> c_next) -> c_back = p -> c_back;
  71.     }
  72. }
  73.  
  74. /*
  75.     Peephole optimizer loop.
  76.  
  77.     All subsidiary routines must set changed as follows:
  78.  
  79.     changed:    TRUE if any optimization was performed.
  80.  
  81.     This almost always finishes in two passes over the code.
  82.         
  83. */
  84. static int changed;
  85. static int advanced;
  86. static int pass;
  87.  
  88. void
  89. peep_hole(void)
  90. {
  91.     register struct node *p;
  92.     register int g_chg;
  93.  
  94.     TRACE("nopeep",    printf("\n>> Disabling Peep Hole...\n\n"); return;);
  95.  
  96.     TRACE("peep_hole", printf("\n>> Peep Hole Optimizer...\n\n"));
  97.  
  98.     pass = 0;
  99.     do {
  100.         g_chg = FALSE;
  101.         changed = FALSE;
  102.         pass++;
  103.  
  104.         p = code_head;
  105.  
  106.         TRACEP("peep_hole", printf("p=%p, pass %d\n\n", p, pass));
  107.  
  108.         while (p) {
  109.             if (changed) {
  110.                 g_chg = TRUE;
  111.  
  112.                 /* Try to avoid multiple passes. */
  113.                 if (p -> c_back) {
  114.                     p = p -> c_back;
  115.                 }
  116.             }
  117.             changed = FALSE;
  118.  
  119.             p = peep0(p);    if (changed) {continue;}
  120.             p = peep1(p);    if (changed) {continue;}
  121.             p = peep2(p);    if (changed) {continue;}
  122.             p = peep3(p);    if (changed) {continue;}
  123.             p = peep4(p);    if (changed) {continue;}
  124.             p = peep5(p);    if (changed) {continue;}
  125.  
  126.             p = p -> c_next;
  127.         }
  128.     } while (g_chg);
  129. }
  130.  
  131. /*
  132.     Peephole optimization 0
  133.  
  134.     X_CLR:    convert clr.l dx to moveq.l #0,dx
  135.     X_MOVE:    delete move to self--compiler never uses flags based on this
  136.         convert long constant move into A to int if possible
  137.     X_TST:    delete test following move or arithmetic (move to self 
  138.         deleted first) provided that argument matches.  MOVEA
  139.         is no problem since TST A doesn't work anyhow
  140.     X_ADD/ADDA: if constant is added to areg, and const is over 8
  141.         and within -32768 to +32767, convert to LEA.
  142.     X_OLABEL:    delete if reference count is 0
  143.  
  144.     Eliminate redundant moves and tests
  145. */
  146. static struct node *
  147. peep0(register struct node *p)
  148. {
  149.     register struct node *q, *t;
  150.     register struct node *arg1;
  151.     register long value;
  152.  
  153.     TRACEP("peep0v", printf("(%p)\n", p));
  154.  
  155.     switch(p -> c_code) {
  156.     case X_CLR:
  157.         if (pass == 1) {
  158.             if (p -> c_len1 == 4 && is_dloc(p -> c_arg1)) {
  159.                 p -> c_arg2 = p -> c_arg1;
  160.                 p -> c_arg1 = zero_loc;
  161.                 p -> c_code = X_MOVEQ;
  162.             }
  163.         }
  164.         break;
  165.  
  166.     case X_MOVE:
  167.         /*
  168.             NOTE: we never use move-to-self to set the flags, since
  169.             it is useless for that purpose.  In any event, if such
  170.             a move did precede an X_TST, it would be gone before
  171.             the attempt to remove the X_TST was completed.
  172.         */
  173.         if (pass == 1) {
  174.             arg1 = p -> c_arg1;
  175.             if (is_equiv(arg1, p -> c_arg2) &&
  176.                         !has_effect(arg1 -> n_mode)) {
  177.                 q = p -> c_next;
  178.                 c_delete(p);
  179.                 changed = TRUE;
  180.                 return q;
  181.             }
  182.             if (is_zloc(arg1) && !is_aloc(p -> c_arg2)) {
  183.                 p -> c_arg1 = p -> c_arg2;
  184.                 p -> c_arg2 = NULL;
  185.                 p -> c_code = X_CLR;
  186.             }
  187.             else if (p -> c_len1 == 4 && is_aloc(p -> c_arg2) &&
  188.                             is_cloc(arg1)) {
  189.                 if (!arg1 -> n_cid && arg1 -> n_const < 32767 &&
  190.                         arg1 -> n_const >= -32768L) {
  191.                     TRACEP("peep0",
  192.                         printf("change a0 long move"));
  193.                     p -> c_len1 = 2;
  194.                 }
  195.             }
  196.         }
  197.         break;
  198.  
  199.     case X_TST:
  200.         /* note that X_TST is not applied to an aloc */
  201.         /* note that X_MOVE and X_ADD might not set the flags */
  202.         arg1 = p -> c_arg1;
  203.         q = p;
  204.         while (q = q -> c_back) {
  205.             switch(q -> c_code) {
  206.             case O_LINENUM:
  207.                 continue;
  208.                 /* labels should NOT be skipped! */
  209.  
  210.             case X_MOVE:
  211.             case X_ADD:
  212.             case X_SUB:
  213.             case X_EOR:
  214.             case X_OR:
  215.             case X_AND:
  216.             case X_MULS:
  217.             case X_MULU:
  218.             case X_DIVS:
  219.             case X_DIVU:
  220.             case X_EXT:
  221.                 TRACEP("peep0",
  222.                     printf("X_TST binary: ");
  223.                     pr_loc(arg1);
  224.                     printf(","); pr_loc(q -> c_arg2);
  225.                     printf("; ");
  226.                     printf("%d,%d\n", p -> c_len1,
  227.                             q -> c_len1);
  228.                 );
  229.  
  230.                 if (is_equiv(arg1, q -> c_arg2)) {
  231.                     if (p -> c_len1 != q -> c_len1) {
  232.                         break;
  233.                     }
  234.                     q = p -> c_next;
  235.                     c_delete(p);
  236.                     changed = TRUE;
  237.                     return q;
  238.                 }
  239.                 break;
  240.             case X_NEG:
  241.             case X_NOT:
  242.             case X_TST:
  243.                 if (is_equiv(arg1, q -> c_arg1)) {
  244.                     if (p -> c_len1 != q -> c_len1) {
  245.                         break;
  246.                     }
  247.                     q = p -> c_next;
  248.                     c_delete(p);
  249.                     changed = TRUE;
  250.                     return q;
  251.                 }
  252.                 break;
  253.             }
  254.             break;
  255.         }
  256.         break;
  257.  
  258.     case O_LABEL:
  259.         if (p -> c_refcount == 0) {
  260.             changed = TRUE;
  261.  
  262.             TRACEP("peep0", printf("remove label: %p\n", p));
  263.  
  264.             q = p -> c_next;
  265.             c_delete(p);
  266.             return q;
  267.         }
  268.         break;
  269.  
  270.     case X_ADD:
  271.     case X_ADDA:
  272.         if (pass != 1) {
  273.             break;
  274.         }
  275.         arg1 = p -> c_arg1;
  276.         if (is_aloc(p -> c_arg2) &&
  277.               !arg1 -> n_cid && is_cloc(arg1)) {
  278.         }
  279.         else {
  280.             break;
  281.         }
  282.  
  283.         TRACEP("peep0", printf("check constant ADDA %p\n", p));
  284.  
  285.         value = arg1 -> n_const;
  286.         if (value < 0) {
  287.             if (value >= -8) {
  288.                 p -> c_code = X_SUBQ;
  289.                 arg1 -> n_const = -value;
  290.             }
  291.             else if (value >= -32768) {
  292.                 p -> c_len1 = 0;
  293.                 p -> c_code = X_LEA;
  294.                 arg1 -> n_mode = EA_MODE;
  295.                 arg1 -> n_reg1 =
  296.                     p -> c_arg2 -> n_reg1;
  297.             }
  298.         }
  299.         else if (value == 0) {
  300.             q = p -> c_next;
  301.             changed = TRUE;
  302.             c_delete(p);
  303.             return q;
  304.         }
  305.         else {
  306.             if (value <= 8) {
  307.                 p -> c_code = X_ADDQ;
  308.             }
  309.             else if (value <= 32767) {
  310.                 p -> c_len1 = 0;
  311.                 p -> c_code = X_LEA;
  312.                 arg1 -> n_mode = EA_MODE;
  313.                 arg1 -> n_reg1 =
  314.                     p -> c_arg2 -> n_reg1;
  315.             }
  316.         }
  317.         break;
  318.     }
  319.     return p;
  320. }    
  321.  
  322. /*
  323.     Peephole optimization 1
  324.  
  325.     Merge adjacent internal labels.
  326. */
  327. static struct node *
  328. peep1(register struct node *p1)
  329. {
  330.     register int count, type;
  331.     register struct node *p2, *q;
  332.  
  333.     TRACEP("peep1v", printf("(%p)\n", p1));
  334.  
  335.     /* Internal label node ? */
  336.     if (p1 -> c_code != O_LABEL) {
  337.         return p1;
  338.     }
  339.     p2 = p1 -> c_next;
  340.  
  341.     while (p2 && p2 -> c_code == O_LINENUM) {
  342.         p2 = p2 -> c_next;
  343.     }
  344.  
  345.     if (p2 == NULL || p2 -> c_code != O_LABEL) {
  346.         return p1;
  347.     }
  348.  
  349.     /* Replace all references to p1 by references to p2. */
  350.     count = 0;
  351.     for (q = code_head; q; q = q -> c_next) {
  352.         type = q -> c_code;
  353.         if (type == X_BRA || is_bxx(type)) {
  354.             if (q -> c_arg1 == p1) {
  355.                 count++;
  356.                 q -> c_arg1 = p2;
  357.             }
  358.         }
  359.     }
  360.     if (count != p1 -> c_refcount) {
  361.         fatal("peep1: mismatched reference counts");
  362.     }
  363.  
  364.     /* Do the optimization. */
  365.     TRACEP("peep1", printf("merge adjacent labels: %p, %p\n", p1, p2));
  366.  
  367.     changed  = TRUE;
  368.     (p2 -> c_refcount) += count;
  369.     c_delete(p1);
  370.     return p2;
  371. }
  372.  
  373. /*
  374.     Peephole optimization 2
  375.  
  376.     Replace            bxx    lab1
  377.                 ...
  378.             lab1:      bra    lab2
  379.                 ...
  380.             lab2:    
  381.     by
  382.                 bxx    lab2
  383.                 ...
  384.             lab1:    bra    lab2
  385.                 ...
  386.             lab2:
  387.  
  388.     Increment the refcount of lab2 and decrement refcount of lab1.
  389.     Eliminate lab1 if its reference count falls to zero.
  390.  
  391.     Cycles of jumps in this context indicate potential infinite loops;
  392.     if the cycle closes, there is no way out.
  393.                 
  394.     TERMINATION PROOF:  if this optimization encounters a closed cycle,
  395.     it fails and generates an error.  If it encounters an open cycle,
  396.     it carries the branch reference forward to the end of the cycle,
  397.     and thus eliminates the cycle, and will not succeed again at that
  398.     same place.
  399.  
  400.     At the present time, all other optimizations remove some code,
  401.     so restoring a pattern visible to this one requires removal
  402.     of code and must terminate.  This does not rule out the possibility
  403.     of a cyclic interaction between this one and some future optimizer
  404.     that only rearranges code.
  405. */
  406. static struct node *
  407. peep2(register struct node *p)
  408. {
  409.     register struct node *q, *target;
  410.     register int type;
  411.  
  412.     TRACEP("peep2v", printf("(%p)\n", p));
  413.  
  414. #ifdef DEBUG
  415.     if (p == NULL) {
  416.         g_error(NULL, "peep2: shouldn't happen");
  417.         return p;
  418.     }
  419. #endif /* DEBUG */
  420.  
  421.     type = p -> c_code;
  422.  
  423.     if (type != X_BRA && !is_bxx(type)) {
  424.         return p;
  425.     }
  426.  
  427.     /* the current node is a jump of some sort */
  428.     target = NULL;
  429.     q = p -> c_arg1;
  430.     while (q) {
  431.         TRACEP("peep2v", printf("mark:   q=%p\n", q));
  432.  
  433. #ifdef DEBUG
  434.         type = q -> c_code;
  435.         if (type != O_LABEL && type != O_ULABEL) {
  436.             fatal("peep2: jump to a non-label");
  437.         }
  438. #endif /* DEBUG */
  439.  
  440.         /* Check for cycle and mark the label node. */
  441.         if (q -> c_mark) {
  442.             /* Disable optimization. */
  443.             g_help(NULL, "closed cycle of branches!");
  444.             target = NULL;
  445.             break;
  446.         }
  447.         else {
  448.             q -> c_mark = TRUE;
  449.         }
  450.  
  451.         /* See if the next instruction is an unconditional branch. */
  452.         do {
  453.             q = q -> c_next;
  454.         }
  455.         while (q && q -> c_code == O_LINENUM); 
  456.  
  457.         if (q == NULL || (q -> c_code != X_BRA)) {
  458.             break;
  459.         }
  460.  
  461.         /* We have (another) jump to an unconditional jump. */
  462.         target = q = q -> c_arg1;
  463.         TRACEP("peep2", printf("new target=%p\n", target));
  464.     }
  465.  
  466.     /* Unmark all the marked nodes before the optimization. */
  467.     for (q = p -> c_arg1; q && q -> c_mark ;q = q -> c_arg1) {
  468.  
  469.         TRACEP("peep2v", printf("unmark: q=%p\n", q));
  470.  
  471.         q -> c_mark = FALSE;
  472.  
  473.         do {
  474.             q = q -> c_next;
  475.         }
  476.         while (q && q -> c_code == O_LINENUM); 
  477.  
  478.         if (q == NULL || (q -> c_code != X_BRA)) {
  479.             break;
  480.         }
  481.     }
  482.  
  483.     /* Do the optimization. */
  484.     if (target) {
  485.  
  486.         TRACEP("peep2",
  487.             printf("retarget branch: %p to %p\n", p, target));
  488.  
  489.         (void) dec_ref(p -> c_arg1);
  490.         p -> c_arg1 = target;
  491.         target -> c_refcount++;
  492.         changed = TRUE;
  493.     }
  494.         
  495.     /* This optimization never alters the code pointer. */
  496.     return p;
  497. }
  498.  
  499. /*
  500.     Peephole optimization 3--flip polarity of certain conditional branches
  501.  
  502.     Replace            bxx    lab1
  503.                 bra    lab2
  504.             lab1:
  505.     by
  506.                 byy    lab2
  507.             lab1:
  508.  
  509.     Also adjust and possibly remove lab1.
  510. */
  511. static struct node *
  512. peep3(register struct node *p)
  513. {
  514.     register struct node *q1, *q2;
  515.  
  516.     TRACEP("peep3v", printf("(%p)\n", p));
  517.  
  518.     /* Conditional jump */
  519.     if (!is_bxx(p -> c_code)) {
  520.         return p;
  521.     }
  522.  
  523.     /* Followed by an unconditional jump? */
  524.     q1 = p -> c_next;
  525.  
  526.     while (q1 && q1 -> c_code == O_LINENUM) {
  527.         q1 = q1 -> c_next;
  528.     }
  529.     if (q1 == NULL || q1 -> c_code != X_BRA) {
  530.         return p;
  531.     }
  532.  
  533.     /* Followed by the target of the first jump? */
  534.     q2 = q1 -> c_next;
  535.     if (q2 == NULL || q2 != p -> c_arg1) {
  536.         return p;
  537.     }
  538.  
  539.     /* Do the optimization. */
  540.     TRACEP("peep3",
  541.         printf("switching bxx polarity: %p\n", p);
  542.         printf("p=%p, q1=%p, q2=%p\n", p, q1, q2));
  543.  
  544.     changed = TRUE;
  545.     p -> c_code = bxx2byy(p -> c_code);
  546.     p -> c_arg1 = q1 -> c_arg1;
  547.     c_delete(q1);
  548.     (void) dec_ref(q2);
  549.  
  550.     return p;
  551. }
  552.  
  553. /*
  554.     Peephole optimization 4--delete jump to immediately following label
  555.  
  556.     Replace            jmp    lab1
  557.             lab1:
  558.  
  559.     by        lab1:
  560.  
  561.     Decrement the reference count of lab1 and eliminate lab1 if
  562.     its reference count falls to zero.
  563. */
  564. static struct node *
  565. peep4(register struct node *p)
  566. {
  567.     register int type;
  568.     register struct node *q;
  569.  
  570.     TRACEP("peep4v", printf("(%p)\n", p));
  571.  
  572.     type = p -> c_code;
  573.  
  574.     if (type != X_BRA && !is_bxx(type)) {
  575.         return p;    /* it's not a jump */
  576.     }
  577.  
  578.     /* Does the jump go to the next instruction? */
  579.     q = p -> c_next;
  580.     while (q && q -> c_code == O_LINENUM) {
  581.         q = q -> c_next;
  582.     }
  583.  
  584.     if (q && /* (struct node *) */ p -> c_arg1 == q) {
  585.  
  586.  
  587.         TRACEP("peep4",
  588.             printf("remove jump to next: %p\n", p);
  589.             printf("p=%p, q=%p\n", p, q));
  590.  
  591.         c_delete(p);    /* delete the jump */
  592.         q = dec_ref(q);    /* and maybe the label as well */
  593.         changed = TRUE;
  594.         return q;
  595.     }
  596.     else {
  597.         return p;
  598.     }
  599. }
  600.  
  601. /*
  602.     Peephole optimization 5--remove unreachable code
  603.  
  604.     i.e.,  all code between an unconditional jump and
  605.     the next label having any references
  606. */
  607. static struct node *
  608. peep5(register struct node *p)
  609. {
  610.     register struct node *q;
  611.     register int type;
  612.  
  613.     TRACEP("peep5v", printf("(%p)\n", p));
  614.  
  615.     /* Do we have an unconditional jump? */
  616.     if (p -> c_code != X_BRA) {
  617.         return p;
  618.     }
  619.  
  620.     /* Remove the next instruction until it is a label with references */
  621.     /* Adjust reference counts when removing branches! */
  622.     q = p -> c_next;
  623.     while (q) {
  624.         type = q -> c_code;
  625.         if (type == X_BRA || is_bxx(type)) {
  626.             (void) dec_ref(q -> c_arg1);
  627.         }
  628.         else if (type == O_LABEL || type == O_ULABEL) {
  629.             if (q -> c_refcount) {
  630.                 TRACEP("peep5v", printf("label found, stop\n"));
  631.                 break;
  632.             }
  633.         }
  634.         TRACEP("peep5", printf("remove unreachable code: %p\n", q));
  635.  
  636.         changed = TRUE;
  637.         c_delete(q);
  638.         q = q -> c_next;
  639.     }
  640.     return p;
  641. }
  642.  
  643. /*
  644.     Return the negation of a conditional jump code.
  645. */
  646. static int
  647. bxx2byy(int code)
  648. {
  649.     TRACEP("bxx2byy", printf("(%d)\n", code));
  650.  
  651.     switch(code) {
  652.     case X_BEQ:    return X_BNE;
  653.     case X_BNE:    return X_BEQ;
  654.  
  655.     case X_BLT:    return X_BGE;
  656.     case X_BGE:    return X_BLT;
  657.  
  658.     case X_BGT:    return X_BLE;
  659.     case X_BLE:    return X_BGT;
  660.  
  661.     case X_BHI:    return X_BLS;    /* Note */
  662.     case X_BLS:    return X_BHI;
  663.  
  664.     case X_BCC:    return X_BCS;
  665.     case X_BCS:    return X_BCC;
  666.  
  667.     case X_BVC:    return X_BVS;
  668.     case X_BVS:    return X_BVC;
  669.  
  670.     case X_BPL:    return X_BMI;
  671.     case X_BMI:    return X_BPL;
  672.  
  673.     default:
  674.         printf("bxx2byy: bad code %d\n", code);
  675.         return code;
  676.     }
  677. }
  678.  
  679. /*
  680.     Decrement the referece count of a label node and
  681.     remove the label if it falls to zero.
  682.  
  683.     Return the pointer to the label node or the following node
  684.     if the label node was eliminated.
  685. */
  686. static struct node *
  687. dec_ref(register struct node * p)
  688. {
  689.     register struct node *q;
  690.  
  691.     TRACEP("dec_ref", printf("(%p)\n", p));
  692.  
  693. #ifdef DEBUG
  694.     if (    (p == NULL) || 
  695.         (p -> c_code != O_LABEL && p -> c_code != O_ULABEL) ||
  696.         (p -> c_refcount) <= 0
  697.        ) {
  698.         fatal("decref: shouldn't happen");
  699.     }
  700. #endif
  701.  
  702.     p -> c_refcount--;
  703.     if (p -> c_refcount == 0) {
  704.         changed    = TRUE;
  705.         TRACE("dec_ref", printf("remove label: %p\n", p));
  706.         q = p -> c_next;
  707.         c_delete(p);
  708.         return q;
  709.     }
  710.     else {
  711.         return p;
  712.     }
  713. }
  714.