control.cpp 22 KB

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