control.cpp 24 KB

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