control.cpp 22 KB

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