home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / adaptor.zip / adapt.zip / adaptor / src / depgraph.c < prev    next >
Text File  |  1994-01-03  |  11KB  |  414 lines
  1. # include "DepGraph.h"
  2. # define yyALLOC(ptr, size)    if ((ptr = (tDepGraph) DepGraph_PoolFreePtr) >= (tDepGraph) DepGraph_PoolMaxPtr) \
  3.   ptr = DepGraph_Alloc (); \
  4.   DepGraph_PoolFreePtr += size;
  5. # define yyFREE(ptr, size)    
  6. # ifdef __cplusplus
  7. extern "C" {
  8. # include <stdio.h>
  9. # include "yyDGraph.w"
  10. # include "General.h"
  11. # include "Memory.h"
  12. # include "DynArray.h"
  13. # include "StringMe.h"
  14. # include "Idents.h"
  15. # include "Sets.h"
  16. }
  17. # else
  18. # include <stdio.h>
  19. # include "yyDGraph.w"
  20. # include "General.h"
  21. # include "Memory.h"
  22. # include "DynArray.h"
  23. # include "StringMe.h"
  24. # include "Idents.h"
  25. # include "Sets.h"
  26. # endif
  27.  
  28. /* line 82 "fortran.dg" */
  29.  
  30.  
  31. #define MaxDepGraphs      150
  32. #define MaxAllDepNode    3000
  33. #define MaxAllDepEdge   10000
  34.  
  35. tDepNode DepNodeArray [MaxAllDepNode];
  36. tDepEdge DepEdgeArray [MaxAllDepEdge];
  37.  
  38. int CountDepGraph;     /* counts graphs */
  39. int CountDepNode;      /* counts nodes of all graphs */
  40. int CountDepEdge;      /* counts edges of all graphs */
  41.  
  42. int CurrentDepGraph;   /* 1 .. CountDepGraph, current DepGraph */
  43.  
  44. typedef struct {
  45.     tTree ast;
  46.     int FirstNode;             /* points into DepNodeArray */
  47.     int FirstEdge;             /* points into DepEdgeArray */
  48.     int CountNode;             /* number of nodes in a DepGraph */
  49.     int CountEdge;             /* number of edges in a DepGraph */
  50.     } DepGraphRec;
  51.  
  52. DepGraphRec DepGraphArray [MaxDepGraphs];
  53.  
  54. /* help functions */
  55.  
  56. void DepGraphError (s)
  57. char * s;
  58. { fprintf (stderr,"Internal Error for Dependence Graph : %s\\n", s);
  59. }
  60.  
  61. void DepGraphOpenCheck ()     /* assert: there is an open graph */
  62. { if (CurrentDepGraph == 0)        /* no graph opened */
  63.      DepGraphError ("No open graph");
  64. }
  65.  
  66. void DepGraphLOpenCheck ()     /* assert: last created graph is open */
  67. { if (CurrentDepGraph != CountDepGraph)
  68.      DepGraphError ("last created graph must be open");
  69. }
  70.  
  71. void DepGraphCloseCheck ()    /* assert: all graphs are closed */
  72. { if (CurrentDepGraph != 0)
  73.      DepGraphError ("Already graph opened");
  74. }
  75.  
  76. void DepCreateGraph  (ast)
  77. tTree ast;
  78. {  if (CountDepGraph == MaxDepGraphs)
  79.       DepGraphError ("maximal number of dependence graphs");
  80.    DepGraphArray [CountDepGraph].ast = ast;
  81.    DepGraphArray [CountDepGraph].FirstNode = CountDepNode;
  82.    DepGraphArray [CountDepGraph].FirstEdge = CountDepEdge;
  83.    DepGraphArray [CountDepGraph].CountNode = 0;
  84.    DepGraphArray [CountDepGraph].CountEdge = 0;
  85.    CountDepGraph += 1;
  86.    CurrentDepGraph = CountDepGraph;
  87.    printf ("Graph has been opened, Id = %d\\n", CurrentDepGraph);
  88. } /* DepCreateGraph */
  89.  
  90. void DepCloseGraph ()
  91. {  DepGraphOpenCheck ();
  92.    printf ("Current Graph = %d will be closed\\n", CurrentDepGraph);
  93.    printf ("%d Nodes have been inserted \\n",
  94.                  DepGraphArray [CurrentDepGraph-1].CountNode);
  95.    printf ("Nodes created until now : %d\\n", CountDepNode);
  96.    CurrentDepGraph = 0;
  97. } /* DepCloseGraph */
  98.  
  99. void DepDestroyGraph (N)
  100. tTree N;
  101. { /* not realized yet */
  102. }
  103.  
  104. void DepOpenGraph (N)
  105. tTree N;
  106. {  short Found;
  107.    int DG;
  108.    DepGraphCloseCheck ();
  109.    DG = 0;
  110.    Found = 0;
  111.    while ((! Found) && (DG < CountDepGraph) )
  112.      {  Found = (DepGraphArray [DG].ast == N);
  113.         if (!Found) DG += 1;
  114.      }
  115.    if (!Found)
  116.       DepGraphError ("No Dependence Graph for AST");
  117.    CurrentDepGraph = DG+1;
  118.    printf ("Graph %d has been opened\n", CurrentDepGraph);
  119. } /* DepOpenGraph */
  120.  
  121. /* Inserting Node or Edge in a opened dependence graph */
  122.  
  123. DepNodeIndex DepGraphNodeInsert (DN)
  124. tDepNode DN;
  125. {  DepGraphLOpenCheck ();
  126.    if (CountDepNode == MaxAllDepNode)
  127.       DepGraphError ("Maximal Number of Nodes reached");
  128.    DepNodeArray [CountDepNode] = DN;
  129.    CountDepNode += 1;
  130.    DepGraphArray [CurrentDepGraph-1].CountNode += 1;
  131.    /* MaxDepNode is only a dummy check */
  132.    if (DepGraphArray [CurrentDepGraph-1].CountNode == MaxDepNode)
  133.       DepGraphError ("Maximal Number of Nodes for one Graph reached");
  134.    return (DepGraphArray [CurrentDepGraph-1].CountNode);
  135. } /* DepGraphNodeInsert */
  136.  
  137. DepEdgeIndex DepGraphEdgeInsert (DE)
  138. tDepEdge DE;
  139.  
  140. {  DepGraphLOpenCheck ();
  141.    if (CountDepEdge == MaxAllDepEdge)
  142.       DepGraphError ("Maximal Number of Edges reached");
  143.    DepEdgeArray [CountDepEdge] = DE;
  144.    CountDepEdge += 1;
  145.    DepGraphArray [CurrentDepGraph-1].CountEdge += 1;
  146.    if (DepGraphArray [CurrentDepGraph-1].CountEdge == MaxDepEdge)
  147.       DepGraphError ("Maximal Number of Edges for one Graph reached");
  148.    return (DepGraphArray [CurrentDepGraph-1].CountEdge);
  149. } /* DepGraphEdgeInsert */
  150.  
  151.  
  152. /* Queries for the nodes of a dependence graph */
  153.  
  154. void DepGraphAllNodes (count, Defs, Uses)
  155. int *count;
  156. DepNodeSet *Defs, *Uses;
  157. {  int i, first;
  158.    DepGraphOpenCheck ();
  159.    MakeSet (Defs, MaxDepNode);
  160.    MakeSet (Uses, MaxDepNode);
  161.    *count = DepGraphArray [CurrentDepGraph-1].CountNode;
  162.    first = DepGraphArray [CurrentDepGraph-1].FirstNode;
  163.    for (i=0;i<*count;i++)
  164.       { if (DepNodeArray [first+i]->DepNode.NodeKind == 0)  /* Use */
  165.            Include (Uses, i+1); /* note: indexes are numbered from 1 to n */
  166.         else if (DepNodeArray [first+i]->DepNode.NodeKind == 1)  /* Def */
  167.            Include (Defs, i+1);
  168.         else
  169.            { Include (Uses, i+1); Include (Defs, i+1); }
  170.       }
  171. }  /* DepGraphAllNodes */
  172.  
  173. void DepGraphGetForStmt (N, defs, uses)
  174. tTree N;  /* stands for a ACF:statement node in the abstract syntax */
  175. DepNodeSet *defs, *uses;
  176.  
  177. { int i, anz, first, kind;
  178.   tDepNode DN;
  179.   DepGraphOpenCheck ();
  180.   MakeSet (defs, MaxDepNode);
  181.   MakeSet (uses, MaxDepNode);
  182.   anz   = DepGraphArray[CurrentDepGraph-1].CountNode;
  183.   first = DepGraphArray[CurrentDepGraph-1].FirstNode;
  184.   for (i=0;i<anz;i++)
  185.     { DN = DepNodeArray [first+i];
  186.       if (DN->DepNode.Stat == N)
  187.         { if (DN->DepNode.NodeKind == 0)
  188.              Include (defs, i+1);
  189.            else if (DN->DepNode.NodeKind == 1)
  190.              Include (uses, i+1);
  191.            else { Include (defs, i+1); Include (uses, i+1); }
  192.         }
  193.     }
  194. } /* DepGraphGetForStmt */
  195.  
  196. DepNodeIndex DepGraphSearchNode ( ac )
  197. tTree ac;
  198.  
  199. {  int Pos;
  200.    DepGraphRec * PDG;
  201.    int First, Nodes;
  202.    short Found;
  203.    tDepNode tDN;
  204.  
  205.    DepGraphOpenCheck;
  206.    PDG = & (DepGraphArray[CurrentDepGraph]);
  207.    Nodes = PDG->CountNode;
  208.    First = PDG->FirstNode;
  209.    Found = 0; Pos = 1;
  210.    while ( (Pos <= Nodes) && (!Found) )
  211.      { tDN = DepNodeArray [First + Pos -1];
  212.        Found = (tDN->DepNode.Access == ac);
  213.        if (!Found) Pos += 1;
  214.      }
  215.    if (Found)
  216.       return (Pos);
  217.     else DepGraphError ("Dependence Node not found");
  218. } /* DepGraphSearchNode */
  219.  
  220. tDepNode DepGraphGetNode (DN)
  221. DepNodeIndex DN;
  222. {  DepGraphOpenCheck ();
  223.    if ( (DN <= 0) || (DN > DepGraphArray[CurrentDepGraph-1].CountNode) )
  224.       DepGraphError ("Illegal Dependence Node");
  225.    return (DepNodeArray [DepGraphArray[CurrentDepGraph-1].FirstNode+DN-1]);
  226. } /* DepGraphGetNode */
  227.  
  228. /* Queries for the edges of a dependence graph */
  229.  
  230. int DepGraphAllEdges ()
  231.  
  232. /* returns number of edges in the openend dependence graph */
  233.  
  234. { DepGraphOpenCheck ();
  235.   return (DepGraphArray[CurrentDepGraph].CountEdge);
  236. }  /* DepGraphAllEdges */
  237.  
  238. tDepEdge DepGraphGetEdge ( DE )
  239. DepEdgeIndex DE;
  240. {  DepGraphOpenCheck ();
  241.    if ( (DE <= 0) || (DE > DepGraphArray[CurrentDepGraph-1].CountEdge) )
  242.       DepGraphError ("Illegal Dependence Edge");
  243.    return (DepEdgeArray [DepGraphArray[CurrentDepGraph-1].FirstEdge+DE-1]);
  244. } /* DepGraphGetEdge */
  245.  
  246. void DepGraphSearchEdge ( DN1, DN2, found, DE)
  247. DepNodeIndex DN1, DN2;
  248. short *found;
  249. DepEdgeIndex DE;
  250.  
  251. {  int Pos;
  252.    DepGraphRec * PDG;
  253.    int First, Edges;
  254.    short Found;
  255.    tDepEdge tDE;
  256.  
  257.    DepGraphOpenCheck;
  258.    PDG = & (DepGraphArray[CurrentDepGraph]);
  259.    Edges = PDG->CountEdge;
  260.    First = PDG->FirstEdge;
  261.    Found = 0; Pos = 1;
  262.    while ( (Pos <= Edges) && (!Found) )
  263.      { tDE = DepEdgeArray [First + Pos];
  264.        Found =    (tDE->DepEdge.Source == DN1)
  265.                && (tDE->DepEdge.Target == DN2);
  266.        if (!Found) Pos += 1;
  267.      }
  268.    if (Found) DE = Pos;
  269. } /* DepGraphSearchEdge */
  270.  
  271.  
  272.  
  273. # define yyBlockSize 20480
  274.  
  275. typedef struct yysBlock {
  276.  char yyBlock [yyBlockSize];
  277.  struct yysBlock * yySuccessor;
  278. } yytBlock, * yytBlockPtr;
  279.  
  280. tDepGraph DepGraphRoot;
  281. unsigned long DepGraph_HeapUsed = 0;
  282.  
  283. static yytBlockPtr yyBlockList    = (yytBlockPtr) NoDepGraph;
  284. char * DepGraph_PoolFreePtr    = (char *) NoDepGraph;
  285. char * DepGraph_PoolMaxPtr    = (char *) NoDepGraph;
  286. static unsigned short yyMaxSize    = 0;
  287. unsigned short DepGraph_NodeSize [2 + 1] = { 0,
  288.  sizeof (yDepNode),
  289.  sizeof (yDepEdge),
  290. };
  291. char * DepGraph_NodeName [2 + 1] = {
  292.  "NoDepGraph",
  293.  "DepNode",
  294.  "DepEdge",
  295. };
  296. static DepGraph_tKind yyTypeRange [2 + 1] = { 0,
  297.  kDepNode,
  298.  kDepEdge,
  299. };
  300.  
  301. tDepGraph DepGraph_Alloc ()
  302. {
  303.  register yytBlockPtr yyBlockPtr = yyBlockList;
  304.  register int i;
  305.  
  306.  if (yyMaxSize == 0)
  307.   for (i = 1; i <= 2; i ++) {
  308.    DepGraph_NodeSize [i] = (DepGraph_NodeSize [i] + yyMaxAlign - 1) & yyAlignMasks [yyMaxAlign];
  309.    yyMaxSize = Max (DepGraph_NodeSize [i], yyMaxSize);
  310.   }
  311.  yyBlockList = (yytBlockPtr) Alloc (sizeof (yytBlock));
  312.  yyBlockList->yySuccessor = yyBlockPtr;
  313.  DepGraph_PoolFreePtr = yyBlockList->yyBlock;
  314.  DepGraph_PoolMaxPtr = DepGraph_PoolFreePtr + yyBlockSize - yyMaxSize + 1;
  315.  DepGraph_HeapUsed += yyBlockSize;
  316.  return (tDepGraph) DepGraph_PoolFreePtr;
  317. }
  318.  
  319. tDepGraph MakeDepGraph
  320. # if defined __STDC__ | defined __cplusplus
  321.  (DepGraph_tKind yyKind)
  322. # else
  323.  (yyKind) DepGraph_tKind yyKind;
  324. # endif
  325. {
  326.  register tDepGraph yyt;
  327.  yyALLOC (yyt, DepGraph_NodeSize [yyKind])
  328.  yyt->Kind = yyKind;
  329.  yyt->yyHead.yyMark = 0;
  330.  return yyt;
  331. }
  332.  
  333. bool DepGraph_IsType
  334. # if defined __STDC__ | defined __cplusplus
  335.  (register tDepGraph yyt, register DepGraph_tKind yyKind)
  336. # else
  337.  (yyt, yyKind) register tDepGraph yyt; register DepGraph_tKind yyKind;
  338. # endif
  339. {
  340.  return yyt != NoDepGraph && yyKind <= yyt->Kind && yyt->Kind <= yyTypeRange [yyKind];
  341. }
  342.  
  343.  
  344. tDepGraph mDepNode
  345. # if defined __STDC__ | defined __cplusplus
  346. (tIdent pName, int pNodeKind, tTree pAccess, tTree pStat, tTree pOuterLoops)
  347. # else
  348. (pName, pNodeKind, pAccess, pStat, pOuterLoops)
  349. tIdent pName;
  350. int pNodeKind;
  351. tTree pAccess;
  352. tTree pStat;
  353. tTree pOuterLoops;
  354. # endif
  355. {
  356.  register tDepGraph yyt;
  357.  yyALLOC (yyt, DepGraph_NodeSize [kDepNode])
  358.  yyt->Kind = kDepNode;
  359.  yyt->yyHead.yyMark = 0;
  360.  yyt->DepNode.Name = pName;
  361.  yyt->DepNode.NodeKind = pNodeKind;
  362.  yyt->DepNode.Access = pAccess;
  363.  yyt->DepNode.Stat = pStat;
  364.  yyt->DepNode.OuterLoops = pOuterLoops;
  365.  return yyt;
  366. }
  367.  
  368. tDepGraph mDepEdge
  369. # if defined __STDC__ | defined __cplusplus
  370. (int pSource, int pTarget, Predicate pPred)
  371. # else
  372. (pSource, pTarget, pPred)
  373. int pSource;
  374. int pTarget;
  375. Predicate pPred;
  376. # endif
  377. {
  378.  register tDepGraph yyt;
  379.  yyALLOC (yyt, DepGraph_NodeSize [kDepEdge])
  380.  yyt->Kind = kDepEdge;
  381.  yyt->yyHead.yyMark = 0;
  382.  yyt->DepEdge.Source = pSource;
  383.  yyt->DepEdge.Target = pTarget;
  384.  yyt->DepEdge.Pred = pPred;
  385.  return yyt;
  386. }
  387.  
  388. typedef tDepGraph * yyPtrtTree;
  389.  
  390. static FILE * yyf;
  391.  
  392. # define yyNil    0374
  393. # define yyNoLabel    0375
  394. # define yyLabelDef    0376
  395. # define yyLabelUse    0377
  396.  
  397. void BeginDepGraph ()
  398. {
  399. /* line 326 "fortran.dg" */
  400.  
  401. CountDepGraph   = 0;
  402. CurrentDepGraph = 0;
  403. CountDepNode    = 0;
  404. CountDepEdge    = 0;
  405.  
  406. }
  407.  
  408. void CloseDepGraph ()
  409. {
  410. /* line 333 "fortran.dg" */
  411.  
  412.  
  413. }
  414.