control.cpp 25 KB

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