reducible.cpp 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414
  1. /********************************************************************
  2. * Checks for reducibility of a graph by intervals, and
  3. * constructs an equivalent reducible graph if one is not found.
  4. * (C) Cristina Cifuentes
  5. ********************************************************************/
  6. #include <algorithm>
  7. #include <cassert>
  8. #include "dcc.h"
  9. #include <stdio.h>
  10. #include <malloc.h> /* For free() */
  11. #include <string.h>
  12. static int numInt; /* Number of intervals */
  13. #define nonEmpty(q) (q != NULL)
  14. /* Returns whether the queue q is empty or not */
  15. bool trivialGraph(BB *G)
  16. {
  17. return G->edges.empty();
  18. }
  19. /* Returns whether the graph is a trivial graph or not */
  20. /* Returns the first element in the queue Q, and removes this element
  21. * from the list. Q is not an empty queue. */
  22. static BB *firstOfQueue (queue &Q)
  23. {
  24. assert(!Q.empty());
  25. BB *res=Q.front();
  26. Q.pop_front();
  27. return res;
  28. }
  29. /* Appends pointer to node at the end of the queue Q if node is not present
  30. * in this queue. Returns the queue node just appended. */
  31. //lint -sem(appendQueue,custodial(1))
  32. queue::iterator appendQueue (queue &Q, BB *node)
  33. {
  34. auto iter=std::find(Q.begin(),Q.end(),node);
  35. if(iter!=Q.end())
  36. return iter;
  37. Q.push_back(node);
  38. iter=Q.end();
  39. --iter;
  40. return iter;
  41. }
  42. /* Returns the next unprocessed node of the interval list (pointed to by
  43. * pI->currNode). Removes this element logically from the list, by updating
  44. * the currNode pointer to the next unprocessed element. */
  45. BB *interval::firstOfInt ()
  46. {
  47. auto pq = currNode;
  48. if (pq == nodes.end())
  49. return 0;
  50. ++currNode;
  51. return *pq;
  52. }
  53. /* Appends node @node to the end of the interval list @pI, updates currNode
  54. * if necessary, and removes the node from the header list @pqH if it is
  55. * there. The interval header information is placed in the field
  56. * node->inInterval.
  57. * Note: nodes are added to the interval list in interval order (which
  58. * topsorts the dominance relation). */
  59. static void appendNodeInt (queue &pqH, BB *node, interval *pI)
  60. {
  61. queue::iterator pq; /* Pointer to current node of the list */
  62. /* Append node if it is not already in the interval list */
  63. pq = appendQueue (pI->nodes, node);
  64. /* Update currNode if necessary */
  65. if (pI->currNode == pI->nodes.end())
  66. pI->currNode = pq;
  67. /* Check header list for occurrence of node, if found, remove it
  68. * and decrement number of out-edges from this interval. */
  69. if (node->beenOnH && !pqH.empty())
  70. {
  71. auto found_iter=std::find(pqH.begin(),pqH.end(),node);
  72. if(found_iter!=pqH.end())
  73. {
  74. pI->numOutEdges -= (uint8_t)(*found_iter)->inEdges.size() - 1;
  75. pqH.erase(found_iter);
  76. }
  77. }
  78. /* Update interval header information for this basic block */
  79. node->inInterval = pI;
  80. }
  81. /* Finds the intervals of graph derivedGi->Gi and places them in the list
  82. * of intervals derivedGi->Ii.
  83. * Algorithm by M.S.Hecht. */
  84. void derSeq_Entry::findIntervals (Function *c)
  85. {
  86. interval *pI, /* Interval being processed */
  87. *J=0; /* ^ last interval in derivedGi->Ii */
  88. BB *h, /* Node being processed */
  89. *header, /* Current interval's header node */
  90. *succ; /* Successor basic block */
  91. int i; /* Counter */
  92. queue H; /* Queue of possible header nodes */
  93. boolT first = TRUE; /* First pass through the loop */
  94. appendQueue (H, Gi); /* H = {first node of G} */
  95. Gi->beenOnH = TRUE;
  96. Gi->reachingInt = BB::Create(0,"",c); /* ^ empty BB */
  97. /* Process header nodes list H */
  98. while (!H.empty())
  99. {
  100. header = firstOfQueue (H);
  101. pI = new interval;
  102. pI->numInt = (uint8_t)numInt++;
  103. if (first) /* ^ to first interval */
  104. Ii = J = pI;
  105. appendNodeInt (H, header, pI); /* pI(header) = {header} */
  106. /* Process all nodes in the current interval list */
  107. while ((h = pI->firstOfInt()) != NULL)
  108. {
  109. /* Check all immediate successors of h */
  110. for (i = 0; i < h->edges.size(); i++)
  111. {
  112. succ = h->edges[i].BBptr;
  113. succ->inEdgeCount--;
  114. if (succ->reachingInt == NULL) /* first visit */
  115. {
  116. succ->reachingInt = header;
  117. if (succ->inEdgeCount == 0)
  118. appendNodeInt (H, succ, pI);
  119. else if (! succ->beenOnH) /* out edge */
  120. {
  121. appendQueue (H, succ);
  122. succ->beenOnH = TRUE;
  123. pI->numOutEdges++;
  124. }
  125. }
  126. else /* node has been visited before */
  127. if (succ->inEdgeCount == 0)
  128. {
  129. if (succ->reachingInt == header || succ->inInterval == pI) /* same interval */
  130. {
  131. if (succ != header)
  132. appendNodeInt (H, succ, pI);
  133. }
  134. else /* out edge */
  135. pI->numOutEdges++;
  136. }
  137. else if (succ != header && succ->beenOnH)
  138. pI->numOutEdges++;
  139. }
  140. }
  141. /* Link interval I to list of intervals */
  142. if (! first)
  143. {
  144. J->next = pI;
  145. J = pI;
  146. }
  147. else /* first interval */
  148. first = false;
  149. }
  150. }
  151. /* Displays the intervals of the graph Gi. */
  152. static void displayIntervals (interval *pI)
  153. {
  154. while (pI)
  155. {
  156. printf (" Interval #: %ld\t#OutEdges: %ld\n", pI->numInt, pI->numOutEdges);
  157. #ifdef _lint
  158. for(auto iter=pI->nodes.begin(); iter!=pI->nodes.end(); ++iter)
  159. {
  160. BB *node(*iter);
  161. #else
  162. for(BB *node : pI->nodes)
  163. {
  164. #endif
  165. if (node->correspInt == NULL) /* real BBs */
  166. printf (" Node: %ld\n", node->begin()->loc_ip);
  167. else // BBs represent intervals
  168. printf (" Node (corresp int): %d\n", node->correspInt->numInt);
  169. }
  170. pI = pI->next;
  171. }
  172. }
  173. /* Allocates space for a new derSeq node. */
  174. static derSeq_Entry *newDerivedSeq()
  175. {
  176. return new derSeq_Entry;
  177. }
  178. /* Frees the storage allocated for the queue q*/
  179. static void freeQueue (queue &q)
  180. {
  181. q.clear();
  182. }
  183. /* Frees the storage allocated for the interval pI */
  184. static void freeInterval (interval **pI)
  185. {
  186. interval *Iptr;
  187. while (*pI)
  188. {
  189. (*pI)->nodes.clear();
  190. Iptr = *pI;
  191. *pI = (*pI)->next;
  192. delete (Iptr);
  193. }
  194. }
  195. /* Frees the storage allocated by the derived sequence structure, except
  196. * for the original graph cfg (derivedG->Gi). */
  197. void freeDerivedSeq(derSeq &derivedG)
  198. {
  199. derivedG.clear();
  200. }
  201. derSeq_Entry::~derSeq_Entry()
  202. {
  203. freeInterval (&Ii);
  204. // if(Gi && Gi->nodeType == INTERVAL_NODE)
  205. // freeCFG (Gi);
  206. }
  207. /* Finds the next order graph of derivedGi->Gi according to its intervals
  208. * (derivedGi->Ii), and places it in derivedGi->next->Gi. */
  209. bool Function::nextOrderGraph (derSeq &derivedGi)
  210. {
  211. interval *Ii; /* Interval being processed */
  212. BB *BBnode, /* New basic block of intervals */
  213. *curr, /* BB being checked for out edges */
  214. *succ /* Successor node */
  215. ;
  216. //queue *listIi; /* List of intervals */
  217. int i, /* Index to outEdges array */
  218. j; /* Index to successors */
  219. boolT sameGraph; /* Boolean, isomorphic graphs */
  220. /* Process Gi's intervals */
  221. derSeq_Entry &prev_entry(derivedGi.back());
  222. derivedGi.push_back(derSeq_Entry());
  223. derSeq_Entry &new_entry(derivedGi.back());
  224. Ii = prev_entry.Ii;
  225. sameGraph = TRUE;
  226. BBnode = 0;
  227. std::vector<BB *> bbs;
  228. while (Ii)
  229. {
  230. i = 0;
  231. bbs.push_back(BB::Create(-1, -1, INTERVAL_NODE, Ii->numOutEdges, this));
  232. BBnode = bbs.back();
  233. BBnode->correspInt = Ii;
  234. const queue &listIi(Ii->nodes);
  235. /* Check for more than 1 interval */
  236. if (sameGraph && (listIi.size()>1))
  237. sameGraph = FALSE;
  238. /* Find out edges */
  239. if (BBnode->edges.size() > 0)
  240. {
  241. #ifdef _lint
  242. for (auto ik=listIi.begin(); ik!=listIi.end(); ++ik)
  243. {
  244. BB *curr(*ik);
  245. #else
  246. for(BB *curr : listIi)
  247. {
  248. #endif
  249. for (j = 0; j < curr->edges.size(); j++)
  250. {
  251. succ = curr->edges[j].BBptr;
  252. if (succ->inInterval != curr->inInterval)
  253. BBnode->edges[i++].intPtr = succ->inInterval;
  254. }
  255. }
  256. }
  257. /* Next interval */
  258. Ii = Ii->next;
  259. }
  260. /* Convert list of pointers to intervals into a real graph.
  261. * Determines the number of in edges to each new BB, and places it
  262. * in numInEdges and inEdgeCount for later interval processing. */
  263. curr = new_entry.Gi = bbs.front();
  264. #ifdef _lint
  265. for (auto ik=bbs.begin(); ik!=bbs.end(); ++ik)
  266. {
  267. BB *curr(*ik);
  268. #else
  269. for(BB *curr : bbs)
  270. {
  271. #endif
  272. #ifdef _lint
  273. for (auto il=curr->edges.begin(); il!=curr->edges.end(); ++il)
  274. {
  275. TYPEADR_TYPE &edge(*il);
  276. #else
  277. for(TYPEADR_TYPE &edge : curr->edges)
  278. {
  279. #endif
  280. BBnode = new_entry.Gi; /* BB of an interval */
  281. auto iter= std::find_if(bbs.begin(),bbs.end(),
  282. [&edge](BB *node)->bool { return edge.intPtr==node->correspInt;});
  283. if(iter==bbs.end())
  284. fatalError (INVALID_INT_BB);
  285. edge.BBptr = *iter;
  286. (*iter)->inEdges.push_back((BB *)nullptr);
  287. (*iter)->inEdgeCount++;
  288. }
  289. }
  290. return (boolT)(! sameGraph);
  291. }
  292. /* Finds the derived sequence of the graph derivedG->Gi (ie. cfg).
  293. * Constructs the n-th order graph and places all the intermediate graphs
  294. * in the derivedG list sequence. */
  295. uint8_t Function::findDerivedSeq (derSeq &derivedGi)
  296. {
  297. BB *Gi; /* Current derived sequence graph */
  298. derSeq::iterator iter=derivedGi.begin();
  299. Gi = iter->Gi;
  300. while (! trivialGraph (Gi))
  301. {
  302. /* Find the intervals of Gi and place them in derivedGi->Ii */
  303. iter->findIntervals(this);
  304. /* Create Gi+1 and check if it is equivalent to Gi */
  305. if (! nextOrderGraph (derivedGi))
  306. break;
  307. ++iter;
  308. Gi = iter->Gi;
  309. stats.nOrder++;
  310. }
  311. if (! trivialGraph (Gi))
  312. {
  313. ++iter;
  314. derivedGi.erase(iter,derivedGi.end()); /* remove Gi+1 */
  315. // freeDerivedSeq(derivedGi->next);
  316. // derivedGi->next = NULL;
  317. return FALSE;
  318. }
  319. derivedGi.back().findIntervals (this);
  320. return TRUE;
  321. }
  322. /* Converts the irreducible graph G into an equivalent reducible one, by
  323. * means of node splitting. */
  324. static void nodeSplitting (std::list<BB *> &G)
  325. {
  326. fprintf(stderr,"Attempt to perform node splitting: NOT IMPLEMENTED\n");
  327. }
  328. /* Displays the derived sequence and intervals of the graph G */
  329. void derSeq::display()
  330. {
  331. int n = 1; /* Derived sequence number */
  332. printf ("\nDerived Sequence Intervals\n");
  333. derSeq::iterator iter=this->begin();
  334. while (iter!=this->end())
  335. {
  336. printf ("\nIntervals for G%lX\n", n++);
  337. displayIntervals (iter->Ii);
  338. ++iter;
  339. }
  340. }
  341. /* Checks whether the control flow graph, cfg, is reducible or not.
  342. * If it is not reducible, it is converted into an equivalent reducible
  343. * graph by node splitting. The derived sequence of graphs built from cfg
  344. * are returned in the pointer *derivedG.
  345. */
  346. derSeq * Function::checkReducibility()
  347. {
  348. derSeq * der_seq;
  349. uint8_t reducible; /* Reducible graph flag */
  350. numInt = 1; /* reinitialize no. of intervals*/
  351. stats.nOrder = 1; /* nOrder(cfg) = 1 */
  352. der_seq = new derSeq;
  353. der_seq->resize(1);
  354. der_seq->back().Gi = m_cfg.front();
  355. reducible = findDerivedSeq(*der_seq);
  356. if (! reducible)
  357. {
  358. flg |= GRAPH_IRRED;
  359. nodeSplitting (m_cfg);
  360. }
  361. return der_seq;
  362. }