control.cpp 23 KB

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