control.cpp 23 KB

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