control.cpp 24 KB

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