control.cpp 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728
  1. /*********************************************************************
  2. * Description : Performs control flow analysis on the CFG
  3. * (C) Cristina Cifuentes
  4. ********************************************************************/
  5. #include "dcc.h"
  6. #include <stdio.h>
  7. #include <string.h>
  8. #if __BORLAND__
  9. #include <alloc.h>
  10. #else
  11. #include <malloc.h>
  12. #endif
  13. typedef struct list {
  14. Int nodeIdx; /* dfsLast index to the node */
  15. struct list *next;
  16. } nodeList;
  17. #define ancestor(a,b) ((a->dfsLastNum < b->dfsLastNum) && (a->dfsFirstNum < b->dfsFirstNum))
  18. /* there is a path on the DFST from a to b if the a was first visited in a
  19. * dfs, and a was later visited than b when doing the last visit of each
  20. * node. */
  21. static boolT isBackEdge (PBB p,PBB s)
  22. /* Checks if the edge (p,s) is a back edge. If node s was visited first
  23. * during the dfs traversal (ie. s has a smaller dfsFirst number) or s == p,
  24. * then it is a backedge.
  25. * Also incrementes the number of backedges entries to the header node. */
  26. {
  27. if (p->dfsFirstNum >= s->dfsFirstNum)
  28. {
  29. s->numBackEdges++;
  30. return (TRUE);
  31. }
  32. return (FALSE);
  33. }
  34. static Int commonDom (Int currImmDom, Int predImmDom, PPROC pProc)
  35. /* Finds the common dominator of the current immediate dominator
  36. * currImmDom and its predecessor's immediate dominator predImmDom */
  37. {
  38. if (currImmDom == NO_DOM)
  39. return (predImmDom);
  40. if (predImmDom == NO_DOM) /* predecessor is the root */
  41. return (currImmDom);
  42. while ((currImmDom != NO_DOM) && (predImmDom != NO_DOM) &&
  43. (currImmDom != predImmDom))
  44. {
  45. if (currImmDom < predImmDom)
  46. predImmDom = pProc->dfsLast[predImmDom]->immedDom;
  47. else
  48. currImmDom = pProc->dfsLast[currImmDom]->immedDom;
  49. }
  50. return (currImmDom);
  51. }
  52. static void findImmedDom (PPROC pProc)
  53. /* Finds the immediate dominator of each node in the graph pProc->cfg.
  54. * Adapted version of the dominators algorithm by Hecht and Ullman; finds
  55. * immediate dominators only.
  56. * Note: graph should be reducible */
  57. { PBB currNode;
  58. Int currIdx, j, predIdx;
  59. for (currIdx = 0; currIdx < pProc->numBBs; currIdx++)
  60. {
  61. currNode = pProc->dfsLast[currIdx];
  62. if (currNode->flg & INVALID_BB) /* Do not process invalid BBs */
  63. continue;
  64. for (j = 0; j < currNode->numInEdges; j++)
  65. {
  66. predIdx = currNode->inEdges[j]->dfsLastNum;
  67. if (predIdx < currIdx)
  68. currNode->immedDom = commonDom (currNode->immedDom,
  69. predIdx, pProc);
  70. }
  71. }
  72. }
  73. static void insertList (nodeList **l, Int n)
  74. /* Inserts the node n to the list l. */
  75. {
  76. nodeList *newNode;
  77. newNode = allocStruc(nodeList);
  78. memset(newNode, 0, sizeof(nodeList));
  79. newNode->nodeIdx = n;
  80. newNode->next = *l;
  81. *l = newNode;
  82. }
  83. static boolT inList (nodeList *l, Int n)
  84. /* Returns whether or not the node n (dfsLast numbering of a basic block)
  85. * is on the list l. */
  86. {
  87. while (l)
  88. if (l->nodeIdx == n)
  89. return (TRUE);
  90. else
  91. l = l->next;
  92. return (FALSE);
  93. }
  94. static void freeList (nodeList **l)
  95. /* Frees space allocated by the list l. */
  96. { nodeList *next;
  97. if (*l)
  98. {
  99. next = (*l)->next;
  100. free (*l);
  101. *l = next;
  102. }
  103. *l = NULL;
  104. }
  105. static boolT inInt(PBB n, queue *q)
  106. /* Returns whether the node n belongs to the queue list q. */
  107. {
  108. while (q)
  109. if (q->node == n)
  110. return (TRUE);
  111. else
  112. q = q->next;
  113. return (FALSE);
  114. }
  115. static void findEndlessFollow (PPROC pProc, nodeList *loopNodes, PBB head)
  116. /* Finds the follow of the endless loop headed at node head (if any).
  117. * The follow node is the closest node to the loop. */
  118. { nodeList *p;
  119. Int j, succ;
  120. head->loopFollow = MAX;
  121. p = loopNodes;
  122. while (p != NULL)
  123. {
  124. for (j = 0; j < pProc->dfsLast[p->nodeIdx]->numOutEdges; j++)
  125. {
  126. succ = pProc->dfsLast[p->nodeIdx]->edges[j].BBptr->dfsLastNum;
  127. if ((! inList(loopNodes, succ)) && (succ < head->loopFollow))
  128. head->loopFollow = succ;
  129. }
  130. p = p->next;
  131. }
  132. }
  133. static void findNodesInLoop(PBB latchNode,PBB head,PPROC pProc,queue *intNodes)
  134. /* Flags nodes that belong to the loop determined by (latchNode, head) and
  135. * determines the type of loop. */
  136. { Int i, headDfsNum, intNodeType, j;
  137. nodeList *loopNodes = NULL, p;
  138. Int immedDom, /* dfsLast index to immediate dominator */
  139. thenDfs, elseDfs; /* dsfLast index for THEN and ELSE nodes */
  140. PBB pbb;
  141. /* Flag nodes in loop headed by head (except header node) */
  142. headDfsNum = head->dfsLastNum;
  143. head->loopHead = headDfsNum;
  144. insertList (&loopNodes, headDfsNum);
  145. for (i = headDfsNum + 1; i < latchNode->dfsLastNum; i++)
  146. {
  147. if (pProc->dfsLast[i]->flg & INVALID_BB) /* skip invalid BBs */
  148. continue;
  149. immedDom = pProc->dfsLast[i]->immedDom;
  150. if (inList (loopNodes, immedDom) && inInt(pProc->dfsLast[i], intNodes))
  151. {
  152. insertList (&loopNodes, i);
  153. if (pProc->dfsLast[i]->loopHead == NO_NODE)/*not in other loop*/
  154. pProc->dfsLast[i]->loopHead = headDfsNum;
  155. }
  156. }
  157. latchNode->loopHead = headDfsNum;
  158. if (latchNode != head)
  159. insertList (&loopNodes, latchNode->dfsLastNum);
  160. /* Determine type of loop and follow node */
  161. intNodeType = head->nodeType;
  162. if (latchNode->nodeType == TWO_BRANCH)
  163. if ((intNodeType == TWO_BRANCH) || (latchNode == head))
  164. if ((latchNode == head) ||
  165. (inList (loopNodes, head->edges[THEN].BBptr->dfsLastNum) &&
  166. inList (loopNodes, head->edges[ELSE].BBptr->dfsLastNum)))
  167. {
  168. head->loopType = REPEAT_TYPE;
  169. if (latchNode->edges[0].BBptr == head)
  170. head->loopFollow = latchNode->edges[ELSE].BBptr->dfsLastNum;
  171. else
  172. head->loopFollow = latchNode->edges[THEN].BBptr->dfsLastNum;
  173. pProc->Icode.SetLlFlag(latchNode->start + latchNode->length - 1,
  174. JX_LOOP);
  175. }
  176. else
  177. {
  178. head->loopType = WHILE_TYPE;
  179. if (inList (loopNodes, head->edges[THEN].BBptr->dfsLastNum))
  180. head->loopFollow = head->edges[ELSE].BBptr->dfsLastNum;
  181. else
  182. head->loopFollow = head->edges[THEN].BBptr->dfsLastNum;
  183. pProc->Icode.SetLlFlag(head->start + head->length - 1, JX_LOOP);
  184. }
  185. else /* head = anything besides 2-way, latch = 2-way */
  186. {
  187. head->loopType = REPEAT_TYPE;
  188. if (latchNode->edges[THEN].BBptr == head)
  189. head->loopFollow = latchNode->edges[ELSE].BBptr->dfsLastNum;
  190. else
  191. head->loopFollow = latchNode->edges[THEN].BBptr->dfsLastNum;
  192. pProc->Icode.SetLlFlag(latchNode->start + latchNode->length - 1,
  193. JX_LOOP);
  194. }
  195. else /* latch = 1-way */
  196. if (latchNode->nodeType == LOOP_NODE)
  197. {
  198. head->loopType = REPEAT_TYPE;
  199. head->loopFollow = latchNode->edges[0].BBptr->dfsLastNum;
  200. }
  201. else if (intNodeType == TWO_BRANCH)
  202. {
  203. head->loopType = WHILE_TYPE;
  204. pbb = latchNode;
  205. thenDfs = head->edges[THEN].BBptr->dfsLastNum;
  206. elseDfs = head->edges[ELSE].BBptr->dfsLastNum;
  207. while (1)
  208. {
  209. if (pbb->dfsLastNum == thenDfs)
  210. {
  211. head->loopFollow = elseDfs;
  212. break;
  213. }
  214. else if (pbb->dfsLastNum == elseDfs)
  215. {
  216. head->loopFollow = thenDfs;
  217. break;
  218. }
  219. /* Check if couldn't find it, then it is a strangely formed
  220. * loop, so it is safer to consider it an endless loop */
  221. if (pbb->dfsLastNum <= head->dfsLastNum)
  222. {
  223. head->loopType = ENDLESS_TYPE;
  224. findEndlessFollow (pProc, loopNodes, head);
  225. break;
  226. }
  227. pbb = pProc->dfsLast[pbb->immedDom];
  228. }
  229. if (pbb->dfsLastNum > head->dfsLastNum)
  230. pProc->dfsLast[head->loopFollow]->loopHead = NO_NODE; /*****/
  231. pProc->Icode.SetLlFlag(head->start + head->length - 1, JX_LOOP);
  232. }
  233. else
  234. {
  235. head->loopType = ENDLESS_TYPE;
  236. findEndlessFollow (pProc, loopNodes, head);
  237. }
  238. freeList(&loopNodes);
  239. }
  240. static void findNodesInInt (queue **intNodes, Int level, interval *Ii)
  241. /* Recursive procedure to find nodes that belong to the interval (ie. nodes
  242. * from G1). */
  243. { queue *l;
  244. if (level == 1)
  245. for (l = Ii->nodes; l; l = l->next)
  246. appendQueue (intNodes, l->node);
  247. else
  248. for (l = Ii->nodes; l; l= l->next)
  249. findNodesInInt (intNodes, level - 1, l->node->correspInt);
  250. }
  251. static void structLoops(PPROC pProc, derSeq *derivedG)
  252. /* Algorithm for structuring loops */
  253. { interval *Ii;
  254. PBB intHead, /* interval header node */
  255. pred, /* predecessor node */
  256. latchNode; /* latching node (in case of loops) */
  257. Int i, /* counter */
  258. level = 0; /* derived sequence level */
  259. interval *initInt; /* initial interval */
  260. queue *intNodes; /* list of interval nodes */
  261. /* Structure loops */
  262. while (derivedG) /* for all derived sequences Gi */
  263. {
  264. level++;
  265. Ii = derivedG->Ii;
  266. while (Ii) /* for all intervals Ii of Gi */
  267. {
  268. latchNode = NULL;
  269. intNodes = NULL;
  270. /* Find interval head (original BB node in G1) and create
  271. * list of nodes of interval Ii. */
  272. initInt = Ii;
  273. for (i = 1; i < level; i++)
  274. initInt = initInt->nodes->node->correspInt;
  275. intHead = initInt->nodes->node;
  276. /* Find nodes that belong to the interval (nodes from G1) */
  277. findNodesInInt (&intNodes, level, Ii);
  278. /* Find greatest enclosing back edge (if any) */
  279. for (i = 0; i < intHead->numInEdges; i++)
  280. {
  281. pred = intHead->inEdges[i];
  282. if (inInt(pred, intNodes) && isBackEdge(pred, intHead))
  283. if (! latchNode)
  284. latchNode = pred;
  285. else
  286. {
  287. if (pred->dfsLastNum > latchNode->dfsLastNum)
  288. latchNode = pred;
  289. }
  290. }
  291. /* Find nodes in the loop and the type of loop */
  292. if (latchNode)
  293. {
  294. /* Check latching node is at the same nesting level of case
  295. * statements (if any) and that the node doesn't belong to
  296. * another loop. */
  297. if ((latchNode->caseHead == intHead->caseHead) &&
  298. (latchNode->loopHead == NO_NODE))
  299. {
  300. intHead->latchNode = latchNode->dfsLastNum;
  301. findNodesInLoop(latchNode, intHead, pProc, intNodes);
  302. latchNode->flg |= IS_LATCH_NODE;
  303. }
  304. }
  305. /* Next interval */
  306. Ii = Ii->next;
  307. }
  308. /* Next derived sequence */
  309. derivedG = derivedG->next;
  310. }
  311. }
  312. static boolT successor (Int s, Int h, PPROC pProc)
  313. /* Returns whether the BB indexed by s is a successor of the BB indexed by
  314. * h. Note that h is a case node. */
  315. { Int i;
  316. PBB header;
  317. header = pProc->dfsLast[h];
  318. for (i = 0; i < header->numOutEdges; i++)
  319. if (header->edges[i].BBptr->dfsLastNum == s)
  320. return (TRUE);
  321. return (FALSE);
  322. }
  323. static void tagNodesInCase (PBB pBB, nodeList **l, Int head, Int tail)
  324. /* Recursive procedure to tag nodes that belong to the case described by
  325. * the list l, head and tail (dfsLast index to first and exit node of the
  326. * case). */
  327. { Int current, /* index to current node */
  328. i;
  329. pBB->traversed = DFS_CASE;
  330. current = pBB->dfsLastNum;
  331. if ((current != tail) && (pBB->nodeType != MULTI_BRANCH) &&
  332. (inList (*l, pBB->immedDom)))
  333. {
  334. insertList (l, current);
  335. pBB->caseHead = head;
  336. for (i = 0; i < pBB->numOutEdges; i++)
  337. if (pBB->edges[i].BBptr->traversed != DFS_CASE)
  338. tagNodesInCase (pBB->edges[i].BBptr, l, head, tail);
  339. }
  340. }
  341. static void structCases(PPROC pProc)
  342. /* Structures case statements. This procedure is invoked only when pProc
  343. * has a case node. */
  344. { Int i, j;
  345. PBB caseHeader; /* case header node */
  346. Int exitNode = NO_NODE; /* case exit node */
  347. nodeList *caseNodes = NULL; /* temporary: list of nodes in case */
  348. /* Linear scan of the nodes in reverse dfsLast order, searching for
  349. * case nodes */
  350. for (i = pProc->numBBs - 1; i >= 0; i--)
  351. if (pProc->dfsLast[i]->nodeType == MULTI_BRANCH)
  352. {
  353. caseHeader = pProc->dfsLast[i];
  354. /* Find descendant node which has as immediate predecessor
  355. * the current header node, and is not a successor. */
  356. for (j = i + 2; j < pProc->numBBs; j++)
  357. {
  358. if ((!successor(j, i, pProc)) &&
  359. (pProc->dfsLast[j]->immedDom == i))
  360. if (exitNode == NO_NODE)
  361. exitNode = j;
  362. else if (pProc->dfsLast[exitNode]->numInEdges <
  363. pProc->dfsLast[j]->numInEdges)
  364. exitNode = j;
  365. }
  366. pProc->dfsLast[i]->caseTail = exitNode;
  367. /* Tag nodes that belong to the case by recording the
  368. * header field with caseHeader. */
  369. insertList (&caseNodes, i);
  370. pProc->dfsLast[i]->caseHead = i;
  371. for (j = 0; j < caseHeader->numOutEdges; j++)
  372. tagNodesInCase (caseHeader->edges[j].BBptr, &caseNodes, i,
  373. exitNode);
  374. if (exitNode != NO_NODE)
  375. pProc->dfsLast[exitNode]->caseHead = i;
  376. }
  377. }
  378. static void flagNodes (nodeList **l, Int f, PPROC pProc)
  379. /* Flags all nodes in the list l as having follow node f, and deletes all
  380. * nodes from the list. */
  381. { nodeList *p;
  382. p = *l;
  383. while (p)
  384. {
  385. pProc->dfsLast[p->nodeIdx]->ifFollow = f;
  386. p = p->next;
  387. free (*l);
  388. *l = p;
  389. }
  390. *l = NULL;
  391. }
  392. static void structIfs (PPROC pProc)
  393. /* Structures if statements */
  394. { Int curr, /* Index for linear scan of nodes */
  395. desc, /* Index for descendant */
  396. followInEdges, /* Largest # in-edges so far */
  397. follow; /* Possible follow node */
  398. nodeList *domDesc = NULL, /* List of nodes dominated by curr */
  399. *unresolved = NULL, /* List of unresolved if nodes */
  400. *l; /* Temporary list */
  401. PBB currNode, /* Pointer to current node */
  402. pbb;
  403. /* Linear scan of nodes in reverse dfsLast order */
  404. for (curr = pProc->numBBs - 1; curr >= 0; curr--)
  405. {
  406. currNode = pProc->dfsLast[curr];
  407. if (currNode->flg & INVALID_BB) /* Do not process invalid BBs */
  408. continue;
  409. if ((currNode->nodeType == TWO_BRANCH) &&
  410. (! (pProc->Icode.GetLlFlag(currNode->start + currNode->length - 1)
  411. & JX_LOOP)))
  412. {
  413. followInEdges = 0;
  414. follow = 0;
  415. /* Find all nodes that have this node as immediate dominator */
  416. for (desc = curr+1; desc < pProc->numBBs; desc++)
  417. {
  418. if (pProc->dfsLast[desc]->immedDom == curr) {
  419. insertList (&domDesc, desc);
  420. pbb = pProc->dfsLast[desc];
  421. if ((pbb->numInEdges - pbb->numBackEdges) >= followInEdges)
  422. {
  423. follow = desc;
  424. followInEdges = pbb->numInEdges - pbb->numBackEdges;
  425. }
  426. }
  427. }
  428. /* Determine follow according to number of descendants
  429. * immediately dominated by this node */
  430. if ((follow != 0) && (followInEdges > 1))
  431. {
  432. currNode->ifFollow = follow;
  433. if (unresolved)
  434. flagNodes (&unresolved, follow, pProc);
  435. }
  436. else
  437. insertList (&unresolved, curr);
  438. }
  439. freeList (&domDesc);
  440. }
  441. }
  442. void compoundCond (PPROC pproc)
  443. /* Checks for compound conditions of basic blocks that have only 1 high
  444. * level instruction. Whenever these blocks are found, they are merged
  445. * into one block with the appropriate condition */
  446. { Int i, j, k, numOutEdges;
  447. PBB pbb, t, e, obb, pred;
  448. PICODE picode, ticode;
  449. COND_EXPR *exp;
  450. TYPEADR_TYPE *edges;
  451. boolT change;
  452. change = TRUE;
  453. while (change)
  454. {
  455. change = FALSE;
  456. /* Traverse nodes in postorder, this way, the header node of a
  457. * compound condition is analysed first */
  458. for (i = 0; i < pproc->numBBs; i++)
  459. {
  460. pbb = pproc->dfsLast[i];
  461. if (pbb->flg & INVALID_BB)
  462. continue;
  463. if (pbb->nodeType == TWO_BRANCH)
  464. {
  465. t = pbb->edges[THEN].BBptr;
  466. e = pbb->edges[ELSE].BBptr;
  467. /* Check (X || Y) case */
  468. if ((t->nodeType == TWO_BRANCH) && (t->numHlIcodes == 1) &&
  469. (t->numInEdges == 1) && (t->edges[ELSE].BBptr == e))
  470. {
  471. obb = t->edges[THEN].BBptr;
  472. /* Construct compound DBL_OR expression */
  473. picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
  474. ticode = pproc->Icode.GetIcode(t->start + t->length -1);
  475. exp = boolCondExp (picode->ic.hl.oper.exp,
  476. ticode->ic.hl.oper.exp, DBL_OR);
  477. picode->ic.hl.oper.exp = exp;
  478. /* Replace in-edge to obb from t to pbb */
  479. for (j = 0; j < obb->numInEdges; j++)
  480. if (obb->inEdges[j] == t)
  481. {
  482. obb->inEdges[j] = pbb;
  483. break;
  484. }
  485. /* New THEN out-edge of pbb */
  486. pbb->edges[THEN].BBptr = obb;
  487. /* Remove in-edge t to e */
  488. for (j = 0; j < (e->numInEdges-1); j++)
  489. if (e->inEdges[j] == t)
  490. {
  491. memmove (&e->inEdges[j], &e->inEdges[j+1],
  492. (size_t)((e->numInEdges - j - 1) * sizeof(PBB)));
  493. break;
  494. }
  495. e->numInEdges--; /* looses 1 arc */
  496. t->flg |= INVALID_BB;
  497. if (pbb->flg & IS_LATCH_NODE)
  498. pproc->dfsLast[t->dfsLastNum] = pbb;
  499. else
  500. i--; /* to repeat this analysis */
  501. change = TRUE;
  502. }
  503. /* Check (!X && Y) case */
  504. else if ((t->nodeType == TWO_BRANCH) && (t->numHlIcodes == 1) &&
  505. (t->numInEdges == 1) && (t->edges[THEN].BBptr == e))
  506. {
  507. obb = t->edges[ELSE].BBptr;
  508. /* Construct compound DBL_AND expression */
  509. picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
  510. ticode = pproc->Icode.GetIcode(t->start + t->length -1);
  511. inverseCondOp (&picode->ic.hl.oper.exp);
  512. exp = boolCondExp (picode->ic.hl.oper.exp,
  513. ticode->ic.hl.oper.exp, DBL_AND);
  514. picode->ic.hl.oper.exp = exp;
  515. /* Replace in-edge to obb from t to pbb */
  516. for (j = 0; j < obb->numInEdges; j++)
  517. if (obb->inEdges[j] == t)
  518. {
  519. obb->inEdges[j] = pbb;
  520. break;
  521. }
  522. /* New THEN and ELSE out-edges of pbb */
  523. pbb->edges[THEN].BBptr = e;
  524. pbb->edges[ELSE].BBptr = obb;
  525. /* Remove in-edge t to e */
  526. for (j = 0; j < (e->numInEdges-1); j++)
  527. if (e->inEdges[j] == t)
  528. {
  529. memmove (&e->inEdges[j], &e->inEdges[j+1],
  530. (size_t)((e->numInEdges - j - 1) * sizeof(PBB)));
  531. break;
  532. }
  533. e->numInEdges--; /* looses 1 arc */
  534. t->flg |= INVALID_BB;
  535. if (pbb->flg & IS_LATCH_NODE)
  536. pproc->dfsLast[t->dfsLastNum] = pbb;
  537. else
  538. i--; /* to repeat this analysis */
  539. change = TRUE;
  540. }
  541. /* Check (X && Y) case */
  542. else if ((e->nodeType == TWO_BRANCH) && (e->numHlIcodes == 1) &&
  543. (e->numInEdges == 1) && (e->edges[THEN].BBptr == t))
  544. {
  545. obb = e->edges[ELSE].BBptr;
  546. /* Construct compound DBL_AND expression */
  547. picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
  548. ticode = pproc->Icode.GetIcode(t->start + t->length -1);
  549. exp = boolCondExp (picode->ic.hl.oper.exp,
  550. ticode->ic.hl.oper.exp, DBL_AND);
  551. picode->ic.hl.oper.exp = exp;
  552. /* Replace in-edge to obb from e to pbb */
  553. for (j = 0; j < obb->numInEdges; j++)
  554. if (obb->inEdges[j] == e)
  555. {
  556. obb->inEdges[j] = pbb;
  557. break;
  558. }
  559. /* New ELSE out-edge of pbb */
  560. pbb->edges[ELSE].BBptr = obb;
  561. /* Remove in-edge e to t */
  562. for (j = 0; j < (t->numInEdges-1); j++)
  563. if (t->inEdges[j] == e)
  564. {
  565. memmove (&t->inEdges[j], &t->inEdges[j+1],
  566. (size_t)((t->numInEdges - j - 1) * sizeof(PBB)));
  567. break;
  568. }
  569. t->numInEdges--; /* looses 1 arc */
  570. e->flg |= INVALID_BB;
  571. if (pbb->flg & IS_LATCH_NODE)
  572. pproc->dfsLast[e->dfsLastNum] = pbb;
  573. else
  574. i--; /* to repeat this analysis */
  575. change = TRUE;
  576. }
  577. /* Check (!X || Y) case */
  578. else if ((e->nodeType == TWO_BRANCH) && (e->numHlIcodes == 1) &&
  579. (e->numInEdges == 1) && (e->edges[ELSE].BBptr == t))
  580. {
  581. obb = e->edges[THEN].BBptr;
  582. /* Construct compound DBL_OR expression */
  583. picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
  584. ticode = pproc->Icode.GetIcode(t->start + t->length -1);
  585. inverseCondOp (&picode->ic.hl.oper.exp);
  586. exp = boolCondExp (picode->ic.hl.oper.exp,
  587. ticode->ic.hl.oper.exp, DBL_OR);
  588. picode->ic.hl.oper.exp = exp;
  589. /* Replace in-edge to obb from e to pbb */
  590. for (j = 0; j < obb->numInEdges; j++)
  591. if (obb->inEdges[j] == e)
  592. {
  593. obb->inEdges[j] = pbb;
  594. break;
  595. }
  596. /* New THEN and ELSE out-edges of pbb */
  597. pbb->edges[THEN].BBptr = obb;
  598. pbb->edges[ELSE].BBptr = t;
  599. /* Remove in-edge e to t */
  600. for (j = 0; j < (t->numInEdges-1); j++)
  601. if (t->inEdges[j] == e)
  602. {
  603. memmove (&t->inEdges[j], &t->inEdges[j+1],
  604. (size_t)((t->numInEdges - j - 1) * sizeof(PBB)));
  605. break;
  606. }
  607. t->numInEdges--; /* looses 1 arc */
  608. e->flg |= INVALID_BB;
  609. if (pbb->flg & IS_LATCH_NODE)
  610. pproc->dfsLast[e->dfsLastNum] = pbb;
  611. else
  612. i--; /* to repeat this analysis */
  613. change = TRUE;
  614. }
  615. }
  616. }
  617. }
  618. }
  619. void structure(PPROC pProc, derSeq *derivedG)
  620. /* Structuring algorithm to find the structures of the graph pProc->cfg */
  621. {
  622. /* Find immediate dominators of the graph */
  623. findImmedDom(pProc);
  624. if (pProc->hasCase)
  625. structCases(pProc);
  626. structLoops(pProc, derivedG);
  627. structIfs(pProc);
  628. }