Quick Search:

Mode

Context

Displaying 3 lines of context. None | Less | More | Full

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.65
 
1.66
 
MAIN:ragge:20090606111635
 
optim2.c
_>4343 
 4444 #define mktemp(n, t)    mklnode(TEMP, 0, n, t)
 4545 
<> 46+/* main switch for new things not yet ready for all-day use */
  47+/* #define ENABLE_NEW */
  48+
  49+
4650 static int dfsnum;
 4751 
 4852 void saveip(struct interpass *ip);
     
 !
6973 void removephi(struct p2env *p2e, struct labelinfo *,struct bblockinfo *bbinfo);
 7074 void remunreach(struct p2env *);
 7175 
<> 76+/* create "proper" basic blocks, add labels where needed (so bblocks have labels) */
  77+/* run before bb generate */
  78+static void add_labels(struct p2env*) ;
  79+
  80+/* Perform trace scheduling, try to get rid of gotos as much as possible */
  81+void TraceSchedule(struct p2env*) ;
  82+
  83+#ifdef ENABLE_NEW
  84+static void do_cse(struct p2env* p2e) ;
  85+#endif
  86+
  87+/* Walk the complete set, performing a function on each node.
  88+ * if type is given, apply function on only that type */
  89+void WalkAll(struct p2env* p2env, void (*f) (NODE*, void*), void* arg, int type) ;
  90+
  91+void BBLiveDead(struct basicblock* bblock, int what, unsigned int variable) ;
  92+
  93+/* Fill the live/dead code */
  94+void LiveDead(struct p2env* p2env, int what, unsigned int variable) ;
  95+
7296 #ifdef PCC_DEBUG
 7397 void printflowdiagram(struct p2env *,struct labelinfo *labinfo,struct bblockinfo *bbinfo,char *);
 7498 #endif
     
 !
88112         if (xdeljumps)
 89113                 deljumps(p2e); /* Delete redundant jumps and dead code */
 90114 
<> 115+        if (xssaflag)
  116+                add_labels(p2e) ;
  117+#ifdef ENABLE_NEW
  118+        do_cse(p2e);
  119+#endif
  120+
91121 #ifdef PCC_DEBUG
 92122         if (b2debug) {
 93123                 printf("links after deljumps\n");
     
 !
131161                 removephi(p2e,&labinfo,&bbinfo);
 132162 
 133163                 BDEBUG(("Calling remunreach\n"));
<>134 -                remunreach(p2e);
  164+/*              remunreach(p2e); */
135165                 
 136166                 /*
 137167                  Recalculate basic blocks and cfg that was destroyed
 138168                  by removephi
 139169                  */
<> 170+                /* first, clean up all what deljumps should have done, and more */
140171 
<> 172+                /*TODO: add the basic blocks done by the ssa code by hand.
  173+                 * The trace scheduler should not change the order in which blocks
  174+                 * are executed or what data is calculated. Thus, the BBlock order
  175+                 * should remain correct.
  176+                 */
  177+
  178+#ifdef ENABLE_NEW
141179                 DLIST_INIT(&p2e->bblocks, bbelem);
 142180                 bblocks_build(p2e, &labinfo, &bbinfo);
 143181                 BDEBUG(("Calling cfg_build\n"));
 144182                 cfg_build(p2e, &labinfo);
 145183 
<> 184+                TraceSchedule(p2e);
146185 #ifdef PCC_DEBUG
<> 186+                printflowdiagram(p2e, &labinfo, &bbinfo,"sched_trace");
  187+
  188+                if (b2debug) {
  189+                        printf("after tracesched\n");
  190+                        printip(ipole);
  191+                        fflush(stdout) ;
  192+                }
  193+#endif
  194+#endif
  195+
  196+                /* Now, clean up the gotos we do not need any longer */
  197+                if (xdeljumps)
  198+                        deljumps(p2e); /* Delete redundant jumps and dead code */
  199+
  200+                DLIST_INIT(&p2e->bblocks, bbelem);
  201+                bblocks_build(p2e, &labinfo, &bbinfo);
  202+                BDEBUG(("Calling cfg_build\n"));
  203+                cfg_build(p2e, &labinfo);
  204+
  205+#ifdef PCC_DEBUG
147206                 printflowdiagram(p2e, &labinfo, &bbinfo,"no_phi");
 148207 
 149208                 if (b2debug) {
     
 !
548607                             labinfo->size)
 549608                                 comperr("Label out of range: %d",
 550609                                         bb->last->ip_node->n_left->n_lval);
<>551 -                        
  610+
552611                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
 553612                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 554613                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
     
 !
10231082         }
 10241083 }
 10251084 
<> 1085+enum pred_type {
  1086+    pred_unknown    = 0,
  1087+    pred_goto       = 1,
  1088+    pred_cond       = 2,
  1089+    pred_falltrough = 3,
  1090+} ;
  1091+
10261092 void
 10271093 removephi(struct p2env *p2e, struct labelinfo *labinfo,struct bblockinfo *bbinfo)
 10281094 {
     
 !
10331099         struct interpass *ip;
 10341100         struct interpass *pip;
 10351101         TWORD n_type;
<>1036 -        int complex;
  1102+
  1103+        enum pred_type complex = pred_unknown ;
  1104+
10371105         int label=0;
 10381106         int newlabel;
 10391107         
     
 !
10471115                                 
 10481116                                 pip=bbparent->last;
 10491117                                 
<>1050 -                                complex = 0;
  1118+                                complex = pred_unknown ;
10511119                                 
 10521120                                 BDEBUG(("removephi: %p in %d",pip,bb->dfnum));
<> 1121+
10531122                                 if (pip->type == IP_NODE && pip->ip_node->n_op == GOTO) {
 10541123                                         BDEBUG((" GOTO "));
 10551124                                         label=pip->ip_node->n_left->n_lval;
<>1056 -                                        complex=1;
  1125+                                        complex = pred_goto ;
10571126                                 } else if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
 10581127                                         BDEBUG((" CBRANCH "));
 10591128                                         label=pip->ip_node->n_right->n_lval;
 10601129                                         
 10611130                                         if (bb==labinfo->arr[label - p2e->ipp->ip_lblnum])
<>1062 -                                                complex=2;
 1063 -                                }       
  1131+                                                complex = pred_cond ;
  1132+                                        else
  1133+                                                complex = pred_falltrough ;
  1134+
  1135+                                        } else if (DLIST_PREV(bb, bbelem) == bbparent) {
  1136+                                                complex = pred_falltrough ;
  1137+                                        } else {
  1138+                                            /* PANIC */
  1139+                                            comperr("Assumtion blown in rem-phi") ;
  1140+                                        }
10641141       
<>1065 -                                BDEBUG((" Complex: %d\n",complex));
  1142+                                        BDEBUG((" Complex: %d\n",complex)) ;
10661143 
<>1067 -                                if (complex > 0) {
 1068 -                                        /*
 1069 -                                         This destroys basic block calculations.
 1070 -                                         Maybe it shoud not
 1071 -                                        */
 1072 -                                        ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
 1073 -                                        DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 1074 -                                        
 1075 -                                        newlabel=getlab2();
 1076 -                                        
 1077 -                                        ip = tmpalloc(sizeof(struct interpass));
 1078 -                                        ip->type = IP_DEFLAB;
 1079 -                                        /* Line number?? ip->lineno; */
 1080 -                                        ip->ip_lbl = newlabel;
 1081 -                                        DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 1082 -                                        
 1083 -                                        SLIST_FOREACH(phi,&bb->phi,phielem) {
 1084 -                                                if (phi->intmpregno[i]>0) {
 1085 -                                                        n_type=phi->n_type;
 1086 -                                                        ip = ipnode(mkbinode(ASSIGN,
  1144+                                        switch (complex) {
  1145+                                          case pred_goto:
  1146+                                                /* gotos can only go to this place. No bounce tab needed */
  1147+                                                SLIST_FOREACH(phi,&bb->phi,phielem) {
  1148+                                                        if (phi->intmpregno[i]>0) {
  1149+                                                                n_type=phi->n_type;
  1150+                                                                ip = ipnode(mkbinode(ASSIGN,
10871151                                                                      mktemp(phi->newtmpregno, n_type),
 10881152                                                                      mktemp(phi->intmpregno[i],n_type),
 10891153                                                                      n_type));
 10901154                                         
<>1091 -                                                        DLIST_INSERT_BEFORE((bb->first), ip, qelem);
 1092 -                                                }
 1093 -                                        }
 1094 -                                        
 1095 -                                        if (complex==1)
 1096 -                                                pip->ip_node->n_left->n_lval=newlabel;
 1097 -                                        
 1098 -                                        if (complex==2)
 1099 -                                                pip->ip_node->n_right->n_lval=newlabel;
 1100 -                                        
 1101 -                                } else {
 1102 -                                        /* Construct move */
 1103 -                                        SLIST_FOREACH(phi,&bb->phi,phielem) {
 1104 -                                                if (phi->intmpregno[i]>0) {
 1105 -                                                        n_type=phi->n_type;
 1106 -                                                        ip = ipnode(mkbinode(ASSIGN,
 1107 -                                                             mktemp(phi->newtmpregno, n_type),
 1108 -                                                             mktemp(phi->intmpregno[i],n_type),
 1109 -                                                             n_type));
  1155+                                                                DLIST_INSERT_BEFORE((bbparent->last), ip, qelem);
  1156+                                                        }
  1157+                                                }
  1158+                                            break ;
  1159+                                          case pred_cond:
  1160+                                                /* Here, we need a jump pad */
  1161+                                                newlabel=getlab2();
11101162                                 
<>1111 -                                                        /* Insert move at bottom of parent basic block */
 1112 -                                                        DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
 1113 -                                                }
 1114 -                                        }
 1115 -                                }
  1163+                                                ip = tmpalloc(sizeof(struct interpass));
  1164+                                                ip->type = IP_DEFLAB;
  1165+                                                /* Line number?? ip->lineno; */
  1166+                                                ip->ip_lbl = newlabel;
  1167+                                                DLIST_INSERT_BEFORE((bb->first), ip, qelem);
  1168+
  1169+
  1170+                                                SLIST_FOREACH(phi,&bb->phi,phielem) {
  1171+                                                        if (phi->intmpregno[i]>0) {
  1172+                                                                n_type=phi->n_type;
  1173+                                                                ip = ipnode(mkbinode(ASSIGN,
  1174+                                                                     mktemp(phi->newtmpregno, n_type),
  1175+                                                                     mktemp(phi->intmpregno[i],n_type),
  1176+                                                                     n_type));
  1177+                                        
  1178+                                                                DLIST_INSERT_BEFORE((bb->first), ip, qelem);
  1179+                                                        }
  1180+                                                }
  1181+                                                /* add a jump to us */
  1182+                                                ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
  1183+                                                DLIST_INSERT_BEFORE((bb->first), ip, qelem);
  1184+                                                pip->ip_node->n_right->n_lval=newlabel;
  1185+                                            break ;
  1186+                                          case pred_falltrough:
  1187+                                                if (bb->first->type == IP_DEFLAB) {
  1188+                                                    label = bb->first->ip_lbl;
  1189+                                                    BDEBUG(("falltrough label %d\n", label));
  1190+                                                } else {
  1191+                                                    comperr("BBlock has no label?") ;
  1192+                                                }
  1193+
  1194+                                                /*
  1195+                                                 * add a jump to us. We _will_ be, or already have, added code in between.
  1196+                                                 * The code is created in the wrong order and switched at the insert, thus
  1197+                                                 * comming out correctly
  1198+                                                 */
  1199+
  1200+                                                ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
  1201+                                                DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
  1202+
  1203+                                                /* Add the code to the end, add a jump to us. */
  1204+                                                SLIST_FOREACH(phi,&bb->phi,phielem) {
  1205+                                                        if (phi->intmpregno[i]>0) {
  1206+                                                                n_type=phi->n_type;
  1207+                                                                ip = ipnode(mkbinode(ASSIGN,
  1208+                                                                        mktemp(phi->newtmpregno, n_type),
  1209+                                                                        mktemp(phi->intmpregno[i],n_type),
  1210+                                                                        n_type));
  1211+        
  1212+                                                                DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
  1213+                                                        }
  1214+                                                }
  1215+                                            break ;
  1216+                                          default:
  1217+                                            comperr("assumption blown, complex is %d\n", complex) ;
  1218+                                }
  1219+
11161220                                 i++;
 11171221                         }
 11181222                         break;
     
 !
11901294                             ipplg->ipp_name, ipplg->ipp_vis ? "(local)" : "");
 11911295                         for (i = 0; i < NIPPREGS; i++)
 11921296                                 printf("%s0x%lx", i? ":" : " ",
<>1193 -                                    (long)ipplg->ipp_regs[i]);
  1297+                                    (long) ipplg->ipp_regs[i]);
11941298                         printf(" autos %d mintemp %d minlbl %d\n",
 11951299                             ipplg->ipp_autos, ipplg->ip_tmpnum, ipplg->ip_lblnum);
 11961300                         break;
     
 !
12001304                             epplg->ipp_name, epplg->ipp_vis ? "(local)" : "");
 12011305                         for (i = 0; i < NIPPREGS; i++)
 12021306                                 printf("%s0x%lx", i? ":" : " ",
<>1203 -                                    (long)epplg->ipp_regs[i]);
  1307+                                    (long) epplg->ipp_regs[i]);
12041308                         printf(" autos %d mintemp %d minlbl %d\n",
 12051309                             epplg->ipp_autos, epplg->ip_tmpnum, epplg->ip_lblnum);
 12061310                         break;
     
 !
13751479         fprintf(flowdiagramfile,"}\n");
 13761480         fclose(flowdiagramfile);
 13771481 }
<> 1482+
13781483 #endif
<_ 1484+
  1485+/* walk all the programm */
  1486+void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type)
  1487+{
  1488+        struct interpass *ipole = &p2e->ipole;
  1489+        struct interpass *ip ;
  1490+        if (0 != type) {
  1491+                DLIST_FOREACH(ip, ipole, qelem) {
  1492+                        if (ip->type == IP_NODE && ip->ip_node->n_op == type)
  1493+                                walkf(ip->ip_node, f, arg) ;
  1494+                }
  1495+        } else {
  1496+                DLIST_FOREACH(ip, ipole, qelem) {
  1497+                        if (ip->type == IP_NODE)
  1498+                                walkf(ip->ip_node, f, arg) ;
  1499+                }
  1500+        }
  1501+}
  1502+#if 0
  1503+static int is_goto_label(struct interpass*g, struct interpass* l)
  1504+{
  1505+        if (!g || !l)
  1506+                return 0 ;
  1507+        if (g->type != IP_NODE) return 0 ;
  1508+        if (l->type != IP_DEFLAB) return 0 ;
  1509+        if (g->ip_node->n_op != GOTO) return 0 ;
  1510+        if (g->ip_node->n_left->n_lval != l->ip_lbl) return 0 ;
  1511+        return 1 ;
  1512+}
  1513+#endif
  1514+
  1515+/*
  1516+ * iterate over the basic blocks.
  1517+ * In case a block has only one successor and that one has only one pred, and the link is a goto:
  1518+ * place the second one immediately behind the first one (in terms of nodes, means cut&resplice).
  1519+ * This should take care of a lot of jumps.
  1520+ * one problem: Cannot move the first or last basic block (prolog/epilog). This is taken care of by
  1521+ * moving block #1 to #2, not #2 to #1
  1522+ * More complex (on the back cooker;) : first coalesc the inner loops (L1 cache), then go from inside out.
  1523+ */
  1524+
  1525+static unsigned long count_blocks(struct p2env* p2e)
  1526+{
  1527+        struct basicblock* bb ;
  1528+        unsigned long count = 0 ;
  1529+        DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
  1530+                ++count ;
  1531+        }
  1532+        return count ;
  1533+}
  1534+
  1535+struct block_map {
  1536+        struct basicblock* block ;
  1537+        unsigned long index ;
  1538+        unsigned long thread ;
  1539+} ;
  1540+
  1541+static unsigned long map_blocks(struct p2env* p2e, struct block_map* map, unsigned long count)
  1542+{
  1543+        struct basicblock* bb ;
  1544+        unsigned long indx = 0 ;
  1545+        int ignore = 2 ;
  1546+        unsigned long thread ;
  1547+        unsigned long changes ;
  1548+
  1549+        DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
  1550+                map[indx].block = bb ;
  1551+                map[indx].index = indx ;
  1552+
  1553+                /* ignore the first 2 labels, maybe up to 3 BBs */
  1554+                if (ignore) {
  1555+                        if (bb->first->type == IP_DEFLAB)
  1556+                                --ignore;
  1557+
  1558+                        map[indx].thread = 1 ;  /* these are "fixed" */
  1559+                } else
  1560+                        map[indx].thread = 0 ;
  1561+
  1562+                indx++ ;
  1563+        }
  1564+
  1565+        thread = 1 ;
  1566+        do {
  1567+                changes = 0 ;
  1568+                
  1569+                for (indx=0; indx < count; indx++) {
  1570+                        /* find block without trace */
  1571+                        if (map[indx].thread == 0) {
  1572+                                /* do new thread */
  1573+                                struct cfgnode *cnode ;
  1574+                                struct basicblock *block2 = 0;
  1575+                                unsigned long i ;
  1576+                                unsigned long added ;
  1577+                                
  1578+                                BDEBUG (("new thread %ld at block %ld\n", thread, indx)) ;
  1579+
  1580+                                bb = map[indx].block ;
  1581+                                do {
  1582+                                        added = 0 ;
  1583+
  1584+                                        for (i=0; i < count; i++) {
  1585+                                                if (map[i].block == bb && map[i].thread == 0) {
  1586+                                                        map[i].thread = thread ;
  1587+
  1588+                                                        BDEBUG(("adding block %ld to trace %ld\n", i, thread)) ;
  1589+
  1590+                                                        changes ++ ;
  1591+                                                        added++ ;
  1592+
  1593+                                                        /*
  1594+                                                         * pick one from followers. For now (simple), pick the
  1595+                                                         * one who is directly following us. If none of that exists,
  1596+                                                         * this code picks the last one.
  1597+                                                         */
  1598+
  1599+                                                        SLIST_FOREACH(cnode, &bb->children, cfgelem) {
  1600+                                                                block2=cnode->bblock ;
  1601+#if 1
  1602+                                                                if (i+1 < count && map[i+1].block == block2)
  1603+                                                                        break/* pick that one */
  1604+#else
  1605+                                                                if (block2) break ;
  1606+#endif
  1607+                                                        }
  1608+
  1609+                                                        if (block2)
  1610+                                                                bb = block2 ;
  1611+                                                }
  1612+                                        }
  1613+                                } while (added) ;
  1614+                                thread++ ;
  1615+                        }
  1616+                }
  1617+        } while (changes);
  1618+
  1619+        /* Last block is also a thread on it's own, and the highest one. */
  1620+/*
  1621+        thread++ ;
  1622+        map[count-1].thread = thread ;
  1623+*/
  1624+        if (b2debug) {
  1625+                printf("Threads\n");
  1626+                for (indx=0; indx < count; indx++) {
  1627+                        printf("Block #%ld (lbl %d) Thread %ld\n", indx, map[indx].block->first->ip_lbl, map[indx].thread);
  1628+                }
  1629+        }
  1630+        return thread ;
  1631+}
  1632+
  1633+
  1634+void TraceSchedule(struct p2env* p2e)
  1635+{
  1636+        struct block_map* map ;
  1637+        unsigned long block_count = count_blocks(p2e);
  1638+        unsigned long i ;
  1639+        unsigned long threads;
  1640+        struct interpass *front, *back ;
  1641+
  1642+        map = tmpalloc(block_count * sizeof(struct block_map));
  1643+
  1644+        threads = map_blocks(p2e, map, block_count) ;
  1645+
  1646+        back = map[0].block->last ;
  1647+        for (i=1; i < block_count; i++) {
  1648+                /* collect the trace */
  1649+                unsigned long j ;
  1650+                unsigned long thread = map[i].thread ;
  1651+                if (thread) {
  1652+                        BDEBUG(("Thread %ld\n", thread)) ;
  1653+                        for (j=i; j < block_count; j++) {
  1654+                                if (map[j].thread == thread) {
  1655+                                        front = map[j].block->first ;
  1656+
  1657+                                        BDEBUG(("Trace %ld, old BB %ld, next BB %ld\t",
  1658+                                                thread, i, j)) ;
  1659+                                        BDEBUG(("Label %d\n", front->ip_lbl)) ;
  1660+                                        DLIST_NEXT(back, qelem) = front ;
  1661+                                        DLIST_PREV(front, qelem) = back ;
  1662+                                        map[j].thread = 0 ;     /* done */
  1663+                                        back = map[j].block->last ;
  1664+                                        DLIST_NEXT(back, qelem) = 0 ;
  1665+                                }
  1666+                        }
  1667+                }
  1668+        }
  1669+        DLIST_NEXT(back, qelem) = &(p2e->ipole) ;
  1670+        DLIST_PREV(&p2e->ipole, qelem) = back ;
  1671+}
  1672+
  1673+static void add_labels(struct p2env* p2e)
  1674+{
  1675+        struct interpass *ipole = &p2e->ipole ;
  1676+        struct interpass *ip ;
  1677+
  1678+        DLIST_FOREACH(ip, ipole, qelem) {
  1679+                if (ip->type == IP_NODE && ip->ip_node->n_op == CBRANCH) {
  1680+                        struct interpass *n = DLIST_NEXT(ip, qelem);
  1681+                        if (n && n->type != IP_DEFLAB) {
  1682+                                int newlabel=getlab2() ;
  1683+
  1684+                                BDEBUG(("add_label L%d\n", newlabel));
  1685+
  1686+                                struct interpass* lab = tmpalloc(sizeof(struct interpass));
  1687+                                lab->type = IP_DEFLAB;
  1688+                                /* Line number?? ip->lineno; */
  1689+                                lab->ip_lbl = newlabel;
  1690+                                DLIST_INSERT_AFTER(ip, lab, qelem);
  1691+                        }
  1692+                }
  1693+        }
  1694+}
  1695+
  1696+/* node map */
  1697+#ifdef ENABLE_NEW
  1698+struct node_map {
  1699+        NODE* node ;            /* the node */
  1700+        unsigned int node_num/* node is equal to that one */
  1701+        unsigned int var_num ;  /* node computes this variable */
  1702+} ;
  1703+
  1704+static unsigned long nodes_counter ;
  1705+static void node_map_count_walker(NODE* n, void* x)
  1706+{
  1707+        nodes_counter ++ ;
  1708+}
  1709+
  1710+static void do_cse(struct p2env* p2e)
  1711+{
  1712+        nodes_counter = 0 ;
  1713+        WalkAll(p2e, node_map_count_walker, 0, 0) ;
  1714+        BDEBUG(("Found %ld nodes\n", nodes_counter)) ;
  1715+}
  1716+#endif
  1717+
FishEye: Open Source License registered to PCC.
Your maintenance has expired. You can renew your license at http://www.atlassian.com/fisheye/renew
Atlassian FishEye, CVS analysis. (Version:1.6.3 Build:build-336 2008-11-04) - Administration - Page generated 2014-08-29 18:06 +0200