control.cpp 21 KB

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