home *** CD-ROM | disk | FTP | other *** search
/ Total Destruction / Total_Destruction.iso / addons / Lccwin32.exe / Lccwin32 / lccpub / src / analysis.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-11-13  |  25.6 KB  |  1,085 lines
  1. #include "c.h"
  2. //#define DOPRINTF
  3. #ifndef DOPRINTF
  4. #define PrintRegister(a)
  5. #define PrintTemporary(a)
  6. #endif
  7. //#include <malloc.h>
  8. extern void qsort(void *, size_t, size_t, int (*)(const void *, const void *));
  9. static int maxdepth,hasDangerousOp;
  10. typedef struct tagSymbolList SymbolList;
  11.  
  12. struct tagSymbolList {
  13.     struct tagSymbolList *Next;
  14.     Symbol sym;
  15. };
  16.  
  17. SymbolList *SymbolsHead;
  18.  
  19. typedef struct tagAssignmentSymbolList {
  20.     struct tagAssignmentSymbolList *Next;
  21.     SymbolList *lhs;
  22.     SymbolList *rhs;
  23.     Node node;
  24. } AssignmentDescriptor;
  25.  
  26. AssignmentDescriptor *AssignmentsList;
  27.  
  28. typedef struct tagLexicalBlock {
  29.     struct tagLexicalBlock *Next;
  30.     struct tagLexicalBlock *Down;
  31.     struct tagLexicalBlock *Up;
  32.     Code cp;
  33. } LexicalBlock;
  34.  
  35. Code CurrentLexicalBlock;
  36. typedef struct tagbasicCodeBlock {
  37.     struct tagbasicCodeBlock *Next;
  38.     int Label;
  39.     int NrOfSuccessors;
  40.     int *Successors;
  41.     int NrOfPredecessors;
  42.     int *Predecessors;
  43.     AssignmentDescriptor *DefUse;
  44.     SymbolList *Symbols;
  45.     Coordinate src;
  46.     LexicalBlock *lexicalblock;
  47.     unsigned EndsWithJump:1;
  48.     unsigned hasCalls:1;
  49.     unsigned hasBlockMove:1;
  50.     unsigned hasMul:1;
  51.     unsigned hasDivision;
  52. } basicCodeBlock;
  53.  
  54. Symbol equated (Symbol);
  55.  
  56.  
  57. SymbolList *AssignedSymbols;
  58. #ifdef DOPRINTF
  59. #define Printf2(a,b) printf(a,b)
  60. #define Printf3(a,b,c) printf(a,b,c)
  61. #else
  62. #define Printf2(a,b)
  63. #define Printf3(a,b,c)
  64. #endif
  65.  
  66. SymbolList *AddSymbolToSymbolList(SymbolList **sl,Symbol s)
  67. {
  68.     SymbolList *newsl;
  69.  
  70. //    if (s->generated || s->temporary) return *sl;
  71.     if (s) {
  72.         NEW0(newsl,FUNC);
  73.         newsl->Next = *sl;
  74.         *sl = newsl;
  75.         newsl->sym = s;
  76.         return newsl;
  77.     }
  78.     return *sl;
  79. }
  80.  
  81. AssignmentDescriptor *AddAssignment(SymbolList *l,SymbolList *sl,Node n)
  82. {
  83.     AssignmentDescriptor *ad;
  84.  
  85.     NEW0(ad,FUNC);
  86.     ad->lhs = l;
  87.     ad->rhs = sl;
  88.     ad->node = n;
  89.     ad->Next = AssignmentsList;
  90.     AssignmentsList = ad;
  91.     return(ad);
  92. }
  93. static void treedump(Node p,int level)
  94. {
  95.     printf( "%s(", IR->x._opname[p->op]);
  96.     if (IR->x._arity[p->op] == 0 && p->syms[0])
  97.         printf( "%s", p->syms[0]->name);
  98.     else if (IR->x._arity[p->op] == 1)
  99.         treedump(p->kids[0],level+1);
  100.     else if (IR->x._arity[p->op] == 2) {
  101.         treedump(p->kids[0],level+1);
  102.         printf( ", ");
  103.         treedump(p->kids[1],level+1);
  104.     }
  105.     printf( ")");
  106. }
  107.  
  108. extern void GenBlockDebugInfo(Code cp);
  109. static void     fixup1(Node p);
  110.  
  111. basicCodeBlock StartBlock;
  112. static int unsafe;
  113. #define MAXSUCCESORS 1000
  114. static short successorsTable[MAXSUCCESORS];
  115. static int succIdx,currentLabel,endswithjump,hasCalls;
  116. static basicCodeBlock *RootBlock,*lastBlock;
  117. static Node BlockNodes;
  118. #define MAXALIAS 200
  119. #define MAXJUMPNODES 4096
  120. typedef struct tagAlias {
  121.     unsigned short label;
  122.     unsigned short alias;
  123.     Node plabel;
  124. } alias,*Alias;
  125. static Node JumpNodeTable[MAXJUMPNODES];
  126. static int JumpNodeIndex;
  127.  
  128. static Alias AliasTable;
  129. static int AliasTableSize;
  130. static int aliasIndex;
  131. static void ClearAliasTable(void)
  132. {
  133.     if (AliasTableSize == 0)
  134.         return;
  135.     memset(AliasTable,0,AliasTableSize*sizeof(alias));
  136. }
  137.  
  138. static void AddLabelAlias(int label,Node plabel)
  139. {
  140.     Alias a;
  141.  
  142.     if (AliasTable == NULL) {
  143.         AliasTable = (Alias)malloc(MAXALIAS * sizeof(alias));
  144.         memset(AliasTable,0,MAXALIAS *sizeof(alias));
  145.         AliasTableSize = MAXALIAS;
  146.     }
  147.     if (aliasIndex >= AliasTableSize) {
  148.         AliasTable = (Alias)realloc(AliasTable,(AliasTableSize+MAXALIAS)*sizeof(alias));
  149.         memset(AliasTable+AliasTableSize,0,MAXALIAS*sizeof(alias));
  150.         AliasTableSize += MAXALIAS;
  151.     }
  152.     a = &AliasTable[aliasIndex];
  153.     aliasIndex++;
  154.     a->alias = plabel->syms[0]->u.l.label;
  155.     a->label = label;
  156.     a->plabel = plabel;
  157. }
  158.  
  159. static void AddJumpNode(Node p)
  160. {
  161.     if (JumpNodeIndex >= MAXJUMPNODES) {
  162.         printf("Overflow in jump node table");
  163.         return;
  164.     }
  165.     JumpNodeTable[JumpNodeIndex] = p;
  166.     JumpNodeIndex++;
  167. }
  168. #ifdef DOPRINTF
  169. void PrintRegister(Node p)
  170. {
  171.     if (p->syms[RX] && p->x.registered) {
  172.         Printf2("%s ",p->syms[RX]->x.name);
  173.     }
  174. }
  175. static void PrintTemporary(Symbol s)
  176. {
  177.     if (s->computed) {
  178.         if (s->scope == GLOBAL)
  179.             Printf2("global ",0);
  180.         else if( s->sclass == STATIC)
  181.             Printf2("static ",0);
  182.         else if (s->sclass == EXTERN)
  183.             Printf2("extern ",0);
  184.         else {
  185.             Printf2("local ",0);
  186.         }
  187.         Printf2("%s ",s->x.name);
  188.         if (s->x.ArraySymbol)
  189.             Printf2("%s ",s->x.ArraySymbol->name);
  190.     }
  191.     else
  192.         Printf2("%s ",s->name);
  193. }
  194. #endif
  195. static void FinishBlock(void)
  196. {
  197.     basicCodeBlock *rvp;
  198.  
  199.     NEW0(rvp,FUNC);
  200.     if (RootBlock == NULL) {
  201.         RootBlock = rvp;
  202.     }
  203.     else {
  204.         lastBlock->Next = rvp;
  205.     }
  206.     lastBlock = rvp;
  207.     rvp->NrOfSuccessors = succIdx;
  208.     if (succIdx) {
  209.         rvp->Successors = allocate(succIdx * sizeof(int),FUNC);
  210.         memcpy(rvp->Successors,successorsTable,succIdx*sizeof(short));
  211.     }
  212.     rvp->src = src;
  213.     rvp->Label = currentLabel;
  214.     rvp->EndsWithJump = endswithjump;
  215.     rvp->hasCalls = hasCalls;
  216.     rvp->DefUse = AssignmentsList;
  217.     AssignmentsList = NULL;
  218.     rvp->Symbols = SymbolsHead;
  219.     SymbolsHead = NULL;
  220.     hasCalls = endswithjump = succIdx = 0;
  221. }
  222.  
  223.  
  224. static int FindSymbols(Node p,int level)
  225. {
  226.     Node kid;
  227.     int skip,op,result=0;
  228.     Symbol s;
  229.     Symbol n;
  230.     AssignmentDescriptor *ad;
  231.  
  232.     if (p == NULL) return 0;
  233.     if (p->x.analyzed) return 0;
  234.     p->x.analyzed = 1;
  235.     if (level > maxdepth) maxdepth = level;
  236.     op = generic(p->op);
  237.     if (op != LABEL && BlockNodes == NULL)
  238.         BlockNodes = p;
  239.     switch (op) {
  240.     case LABEL:
  241.         if (p->syms[0]->ref == 0.0) {
  242.             Printf2("Label _$%s not used",p->syms[0]->name);
  243.             p->syms[0]->u.l.label = 0;
  244.             return 1;
  245.         }
  246. #ifdef DOPRINTF
  247.         if (p->syms[0]->u.l.label == cfunc->u.f.label)
  248.             Printf2("_functionExit:",0);
  249.         else Printf2("_$%d:",p->syms[0]->u.l.label);
  250. #endif
  251.         if (BlockNodes == NULL) {
  252.             Printf2("Label _$%d empty",currentLabel);
  253.             AddLabelAlias(currentLabel,p);
  254.             result = 1;
  255.         }
  256.         else FinishBlock();
  257.         currentLabel = p->syms[0]->u.l.label;
  258.         BlockNodes = NULL;
  259.         break;
  260.     case JUMP:
  261.         Printf2("%s ","goto");
  262.         if (p->kids[0] && p->kids[0]->syms[0]) {
  263.             n = equated(p->kids[0]->syms[0]);
  264. #ifdef DOPRINTF
  265.             if (n->u.l.label == cfunc->u.f.label)
  266.                 Printf2(" _functionExit",0);
  267.             else Printf2(" _$%d ",n->u.l.label);
  268. #endif
  269.             if (succIdx >= MAXSUCCESORS) {
  270.                 printf("Overflow in number of successors\n");
  271.             }
  272.             else {
  273.                 successorsTable[succIdx] = n->u.l.label;
  274.                 succIdx++;
  275.             }
  276.             AddJumpNode(p);
  277.         }
  278.         endswithjump = 1;
  279.         break;
  280.     case EQ:
  281.     case LE:
  282.     case NE:
  283.     case LT:
  284.     case GE:
  285.     case GT:
  286.         Printf2("if (",0);
  287.         FindSymbols(p->kids[0],level+1);
  288.         FindSymbols(p->kids[1],level+1);
  289.         Printf2("%s ) goto ",opname(p->op));
  290.         if (p->syms[0]) {
  291.             n = equated(p->syms[0]);
  292.             Printf2("_$%d ",n->u.l.label);
  293.             if (succIdx >= MAXSUCCESORS) {
  294.                 printf("Overflow in number of successors\n");
  295.             }
  296.             else {
  297.                 successorsTable[succIdx] = n->u.l.label;
  298.                 succIdx++;
  299.             }
  300.         }
  301.         AddJumpNode(p);
  302.         p->x.unsafe = unsafe;
  303.         return result;
  304.     case ASGN:
  305.         if (p->op == ASGNB) {
  306.             unsafe = 1;
  307.             hasDangerousOp = 1;
  308.             p->x.unsafe = 1;
  309.         }
  310.         kid = p->kids[0];
  311.         skip = 0;
  312.         if (generic(kid->op) == AND) {
  313.             kid = p->kids[1];
  314.             skip = 1;
  315.         }
  316.         s = kid->syms[0];
  317.         if (isaddrop(kid->op)) {
  318.             SymbolsHead = AddSymbolToSymbolList(&SymbolsHead,s);
  319.             ad = AddAssignment(SymbolsHead,NULL,p);
  320.             SymbolsHead = NULL;
  321.             PrintTemporary(s);
  322.  
  323.             Printf2("= ",0);
  324.             FindSymbols(kid->kids[0],level+2);
  325.             if (!skip)
  326.                 FindSymbols(p->kids[1],level+1);
  327.             ad->rhs = SymbolsHead;
  328.             SymbolsHead = NULL;
  329.             return 0;
  330.         }
  331.         else if (generic(kid->op) == INDIR) {
  332.             FindSymbols(p->kids[0],level+1);
  333.             SymbolsHead = AddSymbolToSymbolList(&SymbolsHead,s);
  334.             ad = AddAssignment(SymbolsHead,NULL,p);
  335.             SymbolsHead = NULL;
  336.  
  337.             Printf2("= ",0);
  338.             FindSymbols(p->kids[1],level+1);
  339.             Printf2("Assignment through pointer ",0);
  340.             ad->rhs = SymbolsHead;
  341.             SymbolsHead = NULL;
  342.             return 0;
  343.         }
  344.         else if (kid->op == ADDP ||
  345.             kid->op == SUB) {
  346.             Printf2("Array/struct ",0);
  347.             {
  348.                 SymbolsHead = AddSymbolToSymbolList(&SymbolsHead,s);
  349.                 ad = AddAssignment(SymbolsHead,NULL,p);
  350.                 SymbolsHead = NULL;
  351.                 FindSymbols(p->kids[0],level+1);
  352.                 Printf2("= ",0);
  353.                 FindSymbols(p->kids[1],level+1);
  354.             }
  355.             ad->rhs = SymbolsHead;
  356.             SymbolsHead = NULL;
  357.             return 0;
  358.         }
  359.         SymbolsHead = AddSymbolToSymbolList(&SymbolsHead,s);
  360.         ad = AddAssignment(SymbolsHead,NULL,p);
  361.         SymbolsHead = NULL;
  362.         FindSymbols(p->kids[0],level+1);
  363.         FindSymbols(p->kids[1],level+1);
  364.         ad->rhs = SymbolsHead;
  365.         SymbolsHead = NULL;
  366.         break;
  367.     case AND:
  368.         return 0;
  369.     case CALL:
  370.         if (p->x.intrinsic == 0) {
  371.             hasCalls = 1;
  372.             unsafe = 1;
  373.             p->x.unsafe = 1;
  374.         }
  375.         if (p->kids[0]->syms[0]) {
  376.             Printf2("%s() ",p->kids[0]->syms[0]->name);
  377.             return 0;
  378.         }
  379.         else {
  380.             FindSymbols(p->kids[0],level+1);
  381.             FindSymbols(p->kids[1],level+1);
  382.         }
  383.         break;
  384.     case CNST:
  385.         if (p->syms[0]->addressed == 0) {
  386.             if (p->syms[0]->type == inttype) {
  387.                 Printf2("%s ",p->syms[0]->name);
  388.             }
  389.             else Printf2("constant %s ",p->syms[0]->name);
  390.             return 0;
  391.         }
  392.         else
  393.             Printf2("static data %s\n",p->syms[0]->name);
  394.         break;
  395.     case ARG:
  396.         if (p->x.intrinsicArg == 0) {
  397.             unsafe = 1;
  398.             p->x.unsafe = 1;
  399.         }
  400.         FindSymbols(p->kids[0],level+1);
  401.         FindSymbols(p->kids[1],level+1);
  402. #ifdef DOPRINTF
  403.         Printf2("PUSH",0);
  404.         PrintRegister(p);
  405. #endif
  406.         if (p->op == ARGB) {
  407.             hasDangerousOp = 1;
  408.             unsafe = 1;
  409.             p->x.unsafe = 1;
  410.         }
  411.         return 0;
  412.     case LOAD:
  413.     case INDIR:
  414. #ifdef DOPRINTF
  415.         Printf2("%s ",opname(p->op));
  416.         PrintRegister(p);
  417. #endif
  418.         FindSymbols(p->kids[0],level+1);
  419.         FindSymbols(p->kids[1],level+1);
  420.         p->x.unsafe = unsafe;
  421.         return 0;
  422.     case ADDRG:
  423.     case ADDRF:
  424.     case ADDRL:
  425. #ifdef DOPRINTF
  426.         if (p->syms[0]->isconstant) {
  427.             if (p->syms[0]->x.ArraySymbol)
  428.                 Printf2("Table %s ",p->syms[0]->x.ArraySymbol->name);
  429.             else
  430.                 Printf2("static data _$%s ",p->syms[0]->name);
  431.         }
  432.         else if (p->syms[0]->name[0] >= '0' &&
  433.             p->syms[0]->name[0] <= '9') {
  434.             PrintTemporary(p->syms[0]);
  435.         }
  436.         else
  437.             Printf2("%s ",p->syms[0]->name);
  438.         PrintRegister(p);
  439. #endif
  440.         SymbolsHead = AddSymbolToSymbolList(&SymbolsHead,p->syms[0]);
  441.         p->x.unsafe = unsafe;
  442.         return 0;
  443.     default:
  444.         if (op == DIV || op == RSH || op == LSH | op == MOD) {
  445.             if (p->op != DIVD) {
  446.                 unsafe = 1;
  447.                 if (p->op == DIVI || p->op == MODI)
  448.                     hasDangerousOp = 1;
  449.                 p->x.unsafe = 1;
  450.                 p->kids[0]->x.unsafe = 1;
  451.                 p->kids[1]->x.unsafe = 1;
  452.             }
  453.         }
  454.         FindSymbols(p->kids[0],level+1);
  455.         FindSymbols(p->kids[1],level+1);
  456.  
  457.     }
  458. #ifdef DOPRINTF
  459.     Printf2("%s ",opname(p->op));
  460.     PrintRegister(p);
  461. #endif
  462.     p->x.unsafe = unsafe;
  463.     return result;
  464. }
  465. static int SymbolSortFn(const void *f1, const void *f2)
  466. {
  467.     Symbol s1, s2;
  468.     s1 = *(Symbol *) f1;
  469.     s2 = *(Symbol *) f2;
  470.     if (s1->ref > s2->ref)
  471.         return (-1);
  472.     else if (s1->ref < s2->ref)
  473.         return (1);
  474.     else
  475.         return (0);
  476. }
  477.  
  478. static Symbol RegisterVars[5];
  479. static int maxRegisterVars;
  480. void SetupRegisterVariables(void)
  481. {
  482.     int nrOfSym,i,k,l,RegistersAllocated;
  483.     Symbol *FunctionLocals,n;
  484.  
  485.     SetRegistersMasks();
  486.     maxRegisterVars = 0;
  487.     if (vmask[0] == 0)
  488.         return;
  489.     nrOfSym = 0;
  490.     if (cfunc->u.f.callee) {
  491.         Printf2("Function arguments:\n",0);
  492.         i = 0;
  493.         while (cfunc->u.f.callee[i]) {
  494.             n = cfunc->u.f.callee[i];
  495.             Printf3("[%2d] %s ",i,n->name);
  496.             if (n->addressed) Printf2("addressed ",0);
  497. //            printf("%s Usage %f\n",n->name,n->ref);
  498.             i++;
  499.             nrOfSym++;
  500.         }
  501.     }
  502.     FunctionLocals = FunctionInfo.cp->u.block.locals;
  503.     if (OptimizeFlag == 0 && FunctionLocals) {
  504.         i = 0;
  505.         while (FunctionLocals[i]) {
  506.             n = FunctionLocals[i];
  507.             if (n->sclass == REGISTER)
  508.                 n->sclass = AUTO;
  509.             i++;
  510.         }
  511.         return;
  512.     }
  513.     if (FunctionLocals) {
  514.         Printf2("Local variables:\n",0);
  515.         i = 0;
  516.         while (FunctionLocals[i]) {
  517.             n = FunctionLocals[i];
  518.             Printf3("[%2d] %s ",i,n->name);
  519.             if (n->addressed) Printf2("addressed ",0);
  520. //            printf("%s Usage %f\n",n->name,n->ref);
  521.             i++;
  522.             nrOfSym++;
  523.         }
  524.  
  525.     }
  526.     if (nrOfSym) {
  527. //        printf("Function %s:\n",cfunc->name);
  528.         FunctionLocals = (Symbol *)allocate((1+nrOfSym)*sizeof(Symbol),FUNC);
  529.         memset(FunctionLocals,0,(1+nrOfSym)*sizeof(Symbol));
  530.         k = 0;
  531.         if (cfunc->u.f.callee) {
  532.             i = 0;
  533.             while (cfunc->u.f.callee[i]) {
  534.                 n = cfunc->u.f.callee[i];
  535.                 if (n->addressed == 0 &&
  536.                     n->type->size == 4 &&
  537.                     isscalar(n->type) &&
  538.                     unqual(n->type)->op > DOUBLE) {
  539.                     FunctionLocals[k++] = n;
  540.                 }
  541.                 i++;
  542.             }
  543.         }
  544.         if (FunctionInfo.cp->u.block.locals) {
  545.             i = 0;
  546.             while (FunctionInfo.cp->u.block.locals[i]) {
  547.                 n = FunctionInfo.cp->u.block.locals[i];
  548.                 if (n->addressed == 0 &&
  549.                     isscalar(n->type) &&
  550.                     n->type->size == 4 &&
  551.                     unqual(n->type)->op > DOUBLE) {
  552.                     FunctionLocals[k++] = n;
  553.                 }
  554.                 i++;
  555.             }
  556.         }
  557.         if (k) {
  558.             if (k > 1)
  559.                 qsort(FunctionLocals,k,sizeof(Symbol),SymbolSortFn);
  560.             Printf2("Best three symbols to register: ",0);
  561. #if 0
  562.             for (i=0; i<k;i++) {
  563.                 int j,last,first;
  564.  
  565.                 last = FunctionLocals[i]->lastuse;
  566.                 first = FunctionLocals[i]->firstuse;
  567.                 for (j=i; j<k; j++) {
  568.                     if (FunctionLocals[j]->firstuse > last ||
  569.                         FunctionLocals[j]->lastuse < first) {
  570.                         printf("Disjoint variables %s [%4d] (%d %d) %s [%4d] (%d %d)\n",
  571.  
  572.                             FunctionLocals[j]->name,
  573.                             FunctionLocals[j]->src.y,
  574.                             FunctionLocals[j]->firstuse,
  575.                             FunctionLocals[j]->lastuse,
  576.                             FunctionLocals[i]->name,
  577.                             FunctionLocals[i]->src.y,
  578.                             FunctionLocals[i]->firstuse,
  579.                             FunctionLocals[i]->lastuse);
  580.                     }
  581.                 }
  582.             }
  583. #endif
  584.             RegistersAllocated = 0;
  585.             for (i=0; RegistersAllocated<3 && i < k; i++) {
  586.                 n = FunctionLocals[i];
  587.                 if (n->ref < 2.0) break;
  588.                 if (n->x.aliased)
  589.                     continue;
  590.                 l = n->sclass;
  591.                 n->sclass = REGISTER;
  592.                 Printf2("%s ",FunctionLocals[i]->name);
  593.                 if (!askregvar(n,rmap[ttob(n->type)])) {
  594.                     n->sclass = l;
  595.                     break;
  596.                 }
  597. #if 1
  598.                 else {
  599.                     int z,last,first;
  600.                     FunctionInfo.hasRegisterVars = 1;
  601.                     RegisterVars[maxRegisterVars++] = n;
  602.                     RegistersAllocated++;
  603.                     if (IntermediateLanguageFile) {
  604.                         fprintf(ilFile,"; %s --> %s\n",n->name,n->x.name);
  605.                     }
  606.                     last = n->lastuse;
  607.                     first = n->firstuse;
  608.                     if (last && first
  609.                         && first != last
  610.                         && !FunctionInfo.hasgotos)
  611.                     for (z=i+1; z<k;z++) {
  612.                         Symbol s = FunctionLocals[z];
  613.                         if (s->firstuse > last ||
  614.                             s->lastuse < first) {
  615.                             if (s->firstuse != s->lastuse &&
  616.                                 s->x.isArgument == 0  &&
  617.                                 s->sclass != REGISTER) {
  618. #if 0
  619.                                 printf("[%4d] aliasing %s to %s [%d]",
  620.                                     s->src.y,
  621.                                     s->name,n->name,z);
  622.                                 printf(" reg %s\n",n->x.name);
  623. #endif
  624.                                 s->x.regnode = n->x.regnode;
  625.                                 s->x.regnode->vbl = s;
  626.                                 s->x.name = n->x.name;
  627.                                 s->x.aliased = 1;
  628.                                 s->sclass = REGISTER;
  629.                                 RegisterVars[maxRegisterVars++] = s;
  630.                                 if (IntermediateLanguageFile) {
  631.                                     fprintf(ilFile,"; %s aliased to %s --> %s\n",s->name,n->name,n->x.name);
  632.                                 }
  633.                                 break;
  634.                             }
  635.                         }
  636.                     }
  637.                 }
  638. #endif
  639.             }
  640.         }
  641.         Printf2("\n",0);
  642.     }
  643. }
  644.  
  645. void SaturateUnsafe(Node p)
  646. {
  647.     if (p == NULL) return;
  648.     p->x.unsafe = 1;
  649.     p->x.dangerousChildren = 1;
  650.     SaturateUnsafe(p->kids[0]);
  651.     SaturateUnsafe(p->kids[1]);
  652. }
  653.  
  654. void ReplaceReg(Node p,Symbol oldreg,Symbol newreg)
  655. {
  656.     if (p == NULL) return;
  657.     if (p->syms[2] && p->syms[2]->x.name == oldreg->x.name)
  658.         p->syms[2] = newreg;
  659.     ReplaceReg(p->kids[0],oldreg,newreg);
  660.     ReplaceReg(p->kids[1],oldreg,newreg);
  661. }
  662.  
  663. typedef struct {
  664.     Node conditional;
  665.     Node Jump;
  666.     Code cpJump;
  667. }jmpInfo;
  668.  
  669. #define relink(a, b) ((b)->x.prev = (a), (a)->x.next = (b))
  670.  
  671. int BuildBasicBlocks(void)
  672. {
  673.     int i,l,showline;
  674.     Code cp,previous;
  675.     Node p,last,watchout,forest;
  676.     Symbol n;
  677.     jmpInfo jInfo;
  678.     struct node sentinel;
  679.     int result = 1;
  680.  
  681. #ifdef DOPRINTF
  682.     char tmpbuf[256];
  683.     int k=0;
  684.     sprintf(tmpbuf,"\nFunction %s",cfunc->name);
  685.     printf("%s ",tmpbuf);
  686.     for (i=0; i<(signed)(75-strlen(tmpbuf));i++)
  687.         printf("-");
  688.     printf("\n");
  689. #endif
  690.     endswithjump = hasCalls = currentLabel = succIdx = 0;
  691.     i = 1;
  692.     showline = 0;
  693.     memset(&StartBlock,0,sizeof(basicCodeBlock));
  694.     memset(&jInfo,0,sizeof(jmpInfo));
  695.     ClearAliasTable();
  696.     BlockNodes = NULL;
  697.     aliasIndex = 0;
  698.     JumpNodeIndex = 0;
  699.     memset(JumpNodeTable,0,sizeof(JumpNodeTable));
  700.     previous = NULL;
  701.     watchout = last = NULL;
  702.     AssignmentsList = NULL;
  703.     SymbolsHead = NULL;
  704.     unsafe = 0;
  705.     for (cp = codehead.next; cp; cp = cp->next) {
  706.         switch (cp->kind) {
  707.         case Defpoint:
  708.             src = cp->u.point.src;
  709.             showline = 1;
  710.             break;
  711.         case Gen:
  712.         case Jump:
  713.             watchout = NULL;
  714.         case Label:
  715.             if (cp->kind == Label)
  716.                 unsafe = 0;
  717.             if (showline) {
  718.                 Printf2("\nLine %d\n",src.y);
  719.                 showline = 0;
  720.             }
  721.             forest = cp->u.forest;
  722.             relink(&sentinel, &sentinel);
  723.             for (p = forest; p; p = p->link)
  724.                 linearize(p, &sentinel);
  725.             forest = sentinel.x.next;
  726.             assert(forest);
  727.             sentinel.x.next->x.prev = NULL;
  728.             sentinel.x.prev->x.next = NULL;
  729.             for (p=forest;p;p=p->x.next) {
  730.                 if (cp->kind == Jump && last && p->x.next == NULL) {
  731.                     int op = generic(last->op);
  732.                     if (op == EQ || op == LE || op == NE ||
  733.                         op == LT || op == GE || op == GT) {
  734. //                        printf("--- %s --- ",p->kids[0]->syms[0]->name);
  735. //                        printf("%s\n",last->syms[0]->name);
  736.                         jInfo.conditional = last;
  737.                         jInfo.cpJump = cp;
  738.                         jInfo.Jump = p;
  739.                         watchout = last;
  740.                     }
  741.                 }
  742.                 else if (cp->kind == Label && watchout) {
  743.                     int op;
  744.                     if (p->syms[0]->u.l.label == watchout->syms[0]->u.l.label) {
  745. //                        printf("foundit: %d: jump=%d\n",p->syms[0]->u.l.label,
  746. //                            last->kids[0]->syms[0]->u.l.label);
  747.                         assert(jInfo.cpJump);
  748.                         assert(jInfo.cpJump->prev);
  749.                         assert(JumpNodeTable[JumpNodeIndex-1] == jInfo.Jump);
  750.                         assert(JumpNodeTable[JumpNodeIndex-2] == jInfo.conditional);
  751.                         assert(jInfo.cpJump->u.forest->x.next == NULL);
  752.                         /* change the sense of the jcc */
  753.                         switch (jInfo.conditional->op) {
  754.                         case EQI:
  755.                             op = NEI;
  756.                             break;
  757.                         case LEI:
  758.                             op = GTI;
  759.                             break;
  760.                         case LEU:
  761.                             op = GTU;
  762.                             break;
  763.                         case NEI:
  764.                             op = EQI;
  765.                             break;
  766.                         case LTI:
  767.                             op = GEI;
  768.                             break;
  769.                         case LTU:
  770.                             op = GEU;
  771.                             break;
  772.                         case GEI:
  773.                             op = LTI;
  774.                             break;
  775.                         case GEU:
  776.                             op = LTU;
  777.                             break;
  778.                         case GTI:
  779.                             op = LEI;
  780.                             break;
  781.                         case GTU:
  782.                             op = LEU;
  783.                             break;
  784.                         default:
  785.                             goto bailout;
  786.                         }
  787.                         jInfo.conditional->op = op;
  788.                         jInfo.conditional->syms[0] = jInfo.Jump->kids[0]->syms[0];
  789.                         /* erase the jump */
  790.                         jInfo.cpJump->prev->next = jInfo.cpJump->next;
  791.                         jInfo.cpJump->next->prev = jInfo.cpJump->prev;
  792.                         /* fixup the jump table */
  793.                         JumpNodeTable[--JumpNodeIndex] = NULL;
  794.                         JumpNodeTable[--JumpNodeIndex] = NULL;
  795.                         JumpNodeTable[JumpNodeIndex++] = jInfo.conditional;
  796.                         succIdx -= 2; // erase the jump from the successors table
  797.                         successorsTable[succIdx] = successorsTable[succIdx+1];
  798.                         succIdx++;
  799.                         successorsTable[succIdx] = 0;
  800.                         endswithjump = 0;
  801.                     }
  802. bailout:
  803.                     memset(&jInfo,0,sizeof(jmpInfo));
  804.                     watchout = NULL;
  805.                 }
  806.                 else watchout = NULL;
  807. #ifdef DOPRINTF
  808.                 treedump(p,0);
  809.                 printf("\n[%3d] ",k++);
  810. #endif
  811.                 maxdepth = 0;
  812.                 hasDangerousOp = 0;
  813.                 FindSymbols(p,1);
  814.                 if (hasDangerousOp) {
  815.                     SaturateUnsafe(p);
  816.                     unsafe = 1;
  817.                 }
  818. #if 0
  819. //                printf("maxdepth=%d\n",maxdepth);
  820.                 if (0 && maxdepth > 7 && hasDangerousOp) {
  821.                     warning(
  822. "expression too complicated for the optimizer. (depth=%d)\nno optimizations for function %s\n",
  823.                     maxdepth,cfunc->name);
  824.                     unsafe = 1;
  825.                     for (i=0;i<maxRegisterVars;i++) {
  826.                         n = RegisterVars[i];
  827.                         n->x.name = stringf("%d",n->x.offset);
  828.                         n->x.regnode->vbl = NULL;
  829.                         n->x.regnode = NULL;
  830.                         n->sclass= AUTO;
  831.                     }
  832.                     result = 0;
  833.                     maxRegisterVars = 0;
  834.                     goto exitit;
  835.                 }
  836. #endif
  837.                 p->x.unsafe = unsafe;
  838.                 Printf2("\n",0);
  839.                 last = p;
  840.             }
  841.             break;
  842.         case Switch:
  843.             l = cp->u.swtch.size;
  844.             if (l + succIdx >= MAXSUCCESORS) {
  845.                 printf("Overflow in switch\n");
  846.                 l = MAXSUCCESORS - l;
  847.             }
  848.             Printf2("switch size %d \n",cp->u.swtch.size);
  849.             for (i=0; i<l;i++) {
  850.                 cp->u.swtch.labels[i]->ref += 1.0;
  851.                 n = equated(cp->u.swtch.labels[i]);
  852.                 successorsTable[succIdx] = n->u.l.label;
  853.                 succIdx++;
  854.             }
  855.             break;
  856.  
  857.         }
  858.         previous = cp;
  859.     }
  860.     FinishBlock();
  861.     return result;
  862. }
  863. //enum { EAX=0, ECX=1, EDX=2, EBX=3, ESI=6, EDI=7 };
  864. extern Symbol intreg[];
  865. void AnalyzeSecondPass(void)
  866. {
  867.     int i,k,l,ialias,op,lastpoint,z,swapRegs;
  868.     Code cp;
  869.     Node p,last;
  870.     Symbol lab,oldreg[2],newreg[2],lastLabel;
  871. #ifdef DOPRINTF
  872.     basicCodeBlock *rvpB=&StartBlock;
  873.     AssignmentDescriptor *asl;
  874.     SymbolList *rhs;
  875. #endif
  876.     i = 0;
  877.     while (i < aliasIndex) {
  878.         ialias = AliasTable[i].alias;
  879.         lastpoint = i;
  880.         p = AliasTable[i].plabel;
  881.         if (p->x.next || p->x.prev) {
  882.             printf("inner label\n");
  883.         }
  884.         i++;
  885.         while (ialias == AliasTable[i].label) {
  886.             ialias = AliasTable[i].alias;
  887.             i++;
  888.         }
  889.         lab = findlabel(ialias);
  890.         for (k=0; k<JumpNodeIndex;k++) {
  891.             p = JumpNodeTable[k];
  892.             if (p == NULL)
  893.                 continue;
  894.             op = generic(p->op);
  895.             if (op == JUMP)
  896.                 l = p->kids[0]->syms[0]->u.l.label;
  897.             else
  898.                 l = p->syms[0]->u.l.label;
  899.             if (l == 0)
  900.                 printf("l == 0?????");
  901.             for (z=lastpoint; z<i;z++) {
  902.                 if (l == AliasTable[z].label) {
  903.                     if (op == JUMP) {
  904.                         p->kids[0]->syms[0]->u.l.equatedto = lab;
  905.                         p->kids[0]->syms[0] = lab;
  906.                     }
  907.                     else {
  908.                         p->syms[0]->u.l.equatedto = lab;
  909.                         p->syms[0] = lab;
  910.                     }
  911.                     JumpNodeTable[k] = NULL;
  912.                     break;
  913.                 }
  914.             }
  915.         }
  916.     }
  917.     for (i=0; i<JumpNodeIndex;i++) {
  918.         if (JumpNodeTable[i]) {
  919.             char *n;
  920.             p = JumpNodeTable[i];
  921.             op = generic(p->op);
  922.             if (op == JUMP) {
  923.                 l = p->kids[0]->syms[0]->u.l.label;
  924.                 n = p->kids[0]->syms[0]->name;
  925.             }
  926.             else {
  927.                 l = p->syms[0]->u.l.label;
  928.                 n = p->syms[0]->name;
  929.             }
  930.             if (l == 0) {
  931.                 printf("Label _$%s not changed!!!!\n",n);
  932.             }
  933.         }
  934.     }
  935.     swapRegs = 0;
  936.     if (FunctionInfo.leafFunction
  937.         && FunctionInfo.memmove == 0
  938.         && FunctionInfo.hasBlockMove == 0) {
  939.         if ((usedmask[0] & (1 << 1)) == 0 &&
  940.             (usedmask[0] & (1 << 7))) {
  941.             /* swap edi with ecx */
  942.             oldreg[0] = intreg[7];
  943.             newreg[0] = intreg[1];
  944.             swapRegs = 1;
  945.             usedmask[0] |= (1 << 1);
  946.             usedmask[0] &= ~(1 << 7);
  947.             if (IntermediateLanguageFile) {
  948.                 fprintf(ilFile,"; interchanging edi with ecx\n");
  949.             }
  950.         }
  951.         if ((usedmask[0] & (1 << 1)) == 0 &&
  952.             (usedmask[0] & (1 << 6))) {
  953.             /* swap esi with ecx */
  954.             oldreg[swapRegs] = intreg[6];
  955.             newreg[swapRegs] = intreg[1];
  956.             swapRegs++;
  957.             usedmask[0] |= (1 << 1);
  958.             usedmask[0] &= ~(1 << 6);
  959.             if (IntermediateLanguageFile) {
  960.                 fprintf(ilFile,"; interchanging esi with ecx\n");
  961.             }
  962.         }
  963.     }
  964.     /*
  965.     Redo the list of nodes to erase the unnecessary labels
  966.     */
  967.     lastLabel = NULL;
  968.     for (cp = codehead.next; cp; cp = cp->next) {
  969.         // This time follow only Jump/Gen/Label Code nodes
  970.         switch (cp->kind) {
  971.         case Jump:
  972.         case Gen:
  973.         case Label:
  974.             // Follow all the nodes of this forest
  975.             last = NULL;
  976.             for (p=cp->u.forest;p;p=p->x.next) {
  977.                 if (generic(p->op) == LABEL) {    // If it is a LABEL node
  978.                     // If it has been erased by the loops above
  979.                     lab = p->syms[0];
  980.                     if (lab->u.l.equatedto || lab->u.l.label == 0) {
  981.                         Printf2("Erasing label %s\n",p->syms[0]->name);
  982.                         //If is a middle node unlink it
  983.                         if (last) {
  984.                             last->x.next = p->x.next;
  985.                             if (p->x.next)
  986.                                 p->x.next->x.prev = last;
  987.                         }
  988.                         else {
  989.                             // This is the first node in the forest
  990.                             if (p->x.next) // If there are more nodes
  991.                                 cp->u.forest = p->x.next; // unlink
  992.                             else {
  993.                                 // No more nodes. Delete the forest
  994.                                 cp->prev->next = cp->next;
  995.                                 cp->next->prev = cp->prev;
  996.                             }
  997.                         }
  998.                     }
  999.                     else {
  1000.                         lastLabel = lab;
  1001.                     }
  1002.                 }
  1003.                 if (swapRegs)
  1004.                     for (i=0; i<swapRegs;i++)
  1005.                         ReplaceReg(p,oldreg[i],newreg[i]);
  1006.                 // Keep the pointer to the last node
  1007.                 last = p;
  1008.             }
  1009.             break;
  1010. #ifdef DOPRINTF
  1011.         case Blockbeg:{
  1012.                 Symbol         *p = cp->u.block.locals;
  1013.                 if (*p == NULL) break;
  1014.                 Printf2("Scope %d:\n",cp->u.block.x.offset);
  1015.                 for (; *p; p++) {
  1016.                     Printf2("%s",(*p)->name);
  1017.                     if (p[1]) Printf2(",",0);
  1018.                 }
  1019.                 Printf2("\n",0);
  1020.             }
  1021.             break;
  1022. #endif
  1023.         }
  1024.     }
  1025.     if (lastLabel) {
  1026.         cfunc->u.f.label = lastLabel->u.l.label;
  1027.     }
  1028. #ifdef DOPRINTF
  1029.     rvpB = RootBlock;
  1030.     printf("\nControl flow analysis\n");
  1031.     while (rvpB) {
  1032.         printf("Block %d line %d:",rvpB->Label,rvpB->src.y);
  1033.         if (rvpB->hasCalls) printf("Has calls ");
  1034.         else printf("no calls ");
  1035.         if (rvpB->NrOfSuccessors) {
  1036.             printf(" %d successors: ",rvpB->NrOfSuccessors);
  1037.             for (i=0; i<rvpB->NrOfSuccessors;i++) {
  1038.                 printf(" %d ",rvpB->Successors[i]);
  1039.             }
  1040.         }
  1041.         if (rvpB->EndsWithJump)
  1042.             printf(" end: JUMP");
  1043.         printf("\n");
  1044.         if (rvpB->NrOfPredecessors) {
  1045.             printf("Predecessors %d:",rvpB->NrOfPredecessors);
  1046.             for (i=0; i<rvpB->NrOfPredecessors;i++) {
  1047.                 printf(" %d",rvpB->Predecessors[i]);
  1048.             }
  1049.             printf("\n");
  1050.         }
  1051.         else if (rvpB->Label && rvpB->Next) {
  1052. //            printf("Block %d has no predecessors?\n",rvpB->Label);
  1053.         }
  1054.         asl = rvpB->DefUse;
  1055.         while (asl) {
  1056.             if (asl->lhs) {
  1057.                 printf(" %s =",asl->lhs->sym->name);
  1058.             }
  1059.             else
  1060.                 printf("Uses: ");
  1061.             rhs = asl->rhs;
  1062.             while (rhs) {
  1063.                 if (rhs->sym->scope == CONSTANTS)
  1064.                     printf("constant ");
  1065.                 printf(" %s",rhs->sym->name);
  1066.                 rhs = rhs->Next;
  1067.             }
  1068.             Printf2("\n",0);
  1069.             asl = asl->Next;
  1070.         }
  1071.         if (rvpB->DefUse)
  1072.             printf("\n");
  1073.         rvpB = rvpB->Next;
  1074.     }
  1075.     if (aliasIndex) {
  1076.         printf("Label alias table\n");
  1077.         for (i=0; i<aliasIndex;i++) {
  1078.             printf("%d --> %d\n",AliasTable[i].label,AliasTable[i].alias);
  1079.         }
  1080.     }
  1081. #endif
  1082.     lastBlock = RootBlock = NULL;
  1083. }
  1084.  
  1085.