reducible.cpp 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378
  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 "dcc.h"
  7. #include "msvc_fixes.h"
  8. #include <algorithm>
  9. #include <cassert>
  10. #include <cstdio>
  11. #include <cstring>
  12. #include <stdint.h>
  13. static int numInt; /* Number of intervals */
  14. #define nonEmpty(q) (q != NULL)
  15. /* Returns whether the queue q is empty or not */
  16. bool trivialGraph(BB *G)
  17. {
  18. return G->edges.empty();
  19. }
  20. /* Returns whether the graph is a trivial graph or not */
  21. /* Returns the first element in the queue Q, and removes this element
  22. * from the list. Q is not an empty queue. */
  23. static BB *firstOfQueue (queue &Q)
  24. {
  25. assert(!Q.empty());
  26. BB *res=Q.front();
  27. Q.pop_front();
  28. return res;
  29. }
  30. /* Appends pointer to node at the end of the queue Q if node is not present
  31. * in this queue. Returns the queue node just appended. */
  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 nullptr;
  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. void interval::appendNodeInt(queue &pqH, BB *node)
  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 (nodes, node);
  64. /* Update currNode if necessary */
  65. if (currNode == nodes.end())
  66. 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 and !pqH.empty())
  70. {
  71. auto found_iter=std::find(pqH.begin(),pqH.end(),node);
  72. if(found_iter!=pqH.end())
  73. {
  74. 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 = this;
  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; /* ^ last interval in derivedGi->Ii */
  88. BB *h, /* Node being processed */
  89. *header, /* Current interval's header node */
  90. *succ; /* Successor basic block */
  91. queue H; /* Queue of possible header nodes */
  92. bool first = true; /* First pass through the loop */
  93. appendQueue (H, Gi); /* H = {first node of G} */
  94. Gi->beenOnH = true;
  95. Gi->reachingInt = BB::Create(nullptr,"",c); /* ^ empty BB */
  96. /* Process header nodes list H */
  97. while (!H.empty())
  98. {
  99. header = firstOfQueue (H);
  100. pI = new interval;
  101. pI->numInt = (uint8_t)numInt++;
  102. if (first) /* ^ to first interval */
  103. {
  104. Ii = J = pI;
  105. m_intervals.push_back(pI);
  106. }
  107. pI->appendNodeInt (H, header); /* pI(header) = {header} */
  108. /* Process all nodes in the current interval list */
  109. while ((h = pI->firstOfInt()) != nullptr)
  110. {
  111. /* Check all immediate successors of h */
  112. for (auto & elem : h->edges)
  113. {
  114. succ = elem.BBptr;
  115. succ->inEdgeCount--;
  116. if (succ->reachingInt == nullptr) /* first visit */
  117. {
  118. succ->reachingInt = header;
  119. if (succ->inEdgeCount == 0)
  120. pI->appendNodeInt (H, succ);
  121. else if (! succ->beenOnH) /* out edge */
  122. {
  123. appendQueue (H, succ);
  124. succ->beenOnH = true;
  125. pI->numOutEdges++;
  126. }
  127. }
  128. else /* node has been visited before */
  129. if (succ->inEdgeCount == 0)
  130. {
  131. if (succ->reachingInt == header or succ->inInterval == pI) /* same interval */
  132. {
  133. if (succ != header)
  134. pI->appendNodeInt (H, succ);
  135. }
  136. else /* out edge */
  137. pI->numOutEdges++;
  138. }
  139. else if (succ != header and succ->beenOnH)
  140. pI->numOutEdges++;
  141. }
  142. }
  143. /* Link interval I to list of intervals */
  144. if (! first)
  145. {
  146. m_intervals.push_back(pI);
  147. J->next = pI;
  148. J = pI;
  149. }
  150. else /* first interval */
  151. first = false;
  152. }
  153. }
  154. /* Displays the intervals of the graph Gi. */
  155. static void displayIntervals (interval *pI)
  156. {
  157. while (pI)
  158. {
  159. printf (" Interval #: %d\t#OutEdges: %d\n", pI->numInt, pI->numOutEdges);
  160. for(BB *node : pI->nodes)
  161. {
  162. if (node->correspInt == nullptr) /* real BBs */
  163. printf (" Node: %d\n", node->begin()->loc_ip);
  164. else // BBs represent intervals
  165. printf (" Node (corresp int): %d\n", node->correspInt->numInt);
  166. }
  167. pI = pI->next;
  168. }
  169. }
  170. /* Allocates space for a new derSeq node. */
  171. //static derSeq_Entry *newDerivedSeq()
  172. //{
  173. // return new derSeq_Entry;
  174. //}
  175. /* Frees the storage allocated for the queue q*/
  176. //static void freeQueue (queue &q)
  177. //{
  178. // q.clear();
  179. //}
  180. /* Frees the storage allocated for the interval pI */
  181. static void freeInterval (interval **pI)
  182. {
  183. interval *Iptr;
  184. while (*pI)
  185. {
  186. (*pI)->nodes.clear();
  187. Iptr = *pI;
  188. *pI = (*pI)->next;
  189. delete (Iptr);
  190. }
  191. }
  192. /* Frees the storage allocated by the derived sequence structure, except
  193. * for the original graph cfg (derivedG->Gi). */
  194. void freeDerivedSeq(derSeq &derivedG)
  195. {
  196. derivedG.clear();
  197. }
  198. derSeq_Entry::~derSeq_Entry()
  199. {
  200. freeInterval (&Ii);
  201. // if(Gi and Gi->nodeType == INTERVAL_NODE)
  202. // freeCFG (Gi);
  203. }
  204. /* Finds the next order graph of derivedGi->Gi according to its intervals
  205. * (derivedGi->Ii), and places it in derivedGi->next->Gi. */
  206. bool Function::nextOrderGraph (derSeq &derivedGi)
  207. {
  208. interval *Ii; /* Interval being processed */
  209. BB *BBnode; /* New basic block of intervals */
  210. bool sameGraph; /* Boolean, isomorphic graphs */
  211. /* Process Gi's intervals */
  212. derSeq_Entry &prev_entry(derivedGi.back());
  213. derivedGi.push_back(derSeq_Entry());
  214. derSeq_Entry &new_entry(derivedGi.back());
  215. sameGraph = true;
  216. BBnode = nullptr;
  217. std::vector<BB *> bbs;
  218. for(Ii = prev_entry.Ii; Ii != nullptr; Ii = Ii->next)
  219. {
  220. BBnode = BB::CreateIntervalBB(this);
  221. BBnode->correspInt = Ii;
  222. bbs.push_back(BBnode);
  223. const queue &listIi(Ii->nodes);
  224. /* Check for more than 1 interval */
  225. if (sameGraph and (listIi.size()>1))
  226. sameGraph = false;
  227. /* Find out edges */
  228. if (Ii->numOutEdges <= 0)
  229. continue;
  230. for(BB *curr : listIi)
  231. {
  232. for (size_t j = 0; j < curr->edges.size(); j++)
  233. {
  234. BB *successor_node = curr->edges[j].BBptr;
  235. if (successor_node->inInterval != curr->inInterval)
  236. BBnode->addOutEdgeInterval(successor_node->inInterval);
  237. }
  238. }
  239. }
  240. /* Convert list of pointers to intervals into a real graph.
  241. * Determines the number of in edges to each new BB, and places it
  242. * in numInEdges and inEdgeCount for later interval processing. */
  243. //curr = new_entry.Gi = bbs.front();
  244. new_entry.Gi = bbs.front();
  245. for(BB *curr : bbs)
  246. {
  247. for(TYPEADR_TYPE &edge : curr->edges)
  248. {
  249. BBnode = new_entry.Gi; /* BB of an interval */
  250. auto iter= std::find_if(bbs.begin(),bbs.end(),
  251. [&edge](BB *node)->bool { return edge.intPtr==node->correspInt;});
  252. if(iter==bbs.end())
  253. fatalError (INVALID_INT_BB);
  254. edge.BBptr = *iter;
  255. (*iter)->inEdges.push_back((BB *)nullptr);
  256. (*iter)->inEdgeCount++;
  257. }
  258. }
  259. return not sameGraph;
  260. }
  261. /* Finds the derived sequence of the graph derivedG->Gi (ie. cfg).
  262. * Constructs the n-th order graph and places all the intermediate graphs
  263. * in the derivedG list sequence. */
  264. bool Function::findDerivedSeq (derSeq &derivedGi)
  265. {
  266. derSeq::iterator iter=derivedGi.begin();
  267. assert(iter!=derivedGi.end());
  268. BB *Gi = iter->Gi; /* Current derived sequence graph */
  269. while (! trivialGraph (Gi))
  270. {
  271. /* Find the intervals of Gi and place them in derivedGi->Ii */
  272. iter->findIntervals(this);
  273. /* Create Gi+1 and check if it is equivalent to Gi */
  274. if (! nextOrderGraph (derivedGi))
  275. break;
  276. ++iter;
  277. Gi = iter->Gi;
  278. stats.nOrder++;
  279. }
  280. if (! trivialGraph (Gi))
  281. {
  282. ++iter;
  283. derivedGi.erase(iter,derivedGi.end()); /* remove Gi+1 */
  284. // freeDerivedSeq(derivedGi->next);
  285. // derivedGi->next = NULL;
  286. return false;
  287. }
  288. derivedGi.back().findIntervals (this);
  289. return true;
  290. }
  291. /* Displays the derived sequence and intervals of the graph G */
  292. void derSeq::display()
  293. {
  294. int n = 1; /* Derived sequence number */
  295. printf ("\nDerived Sequence Intervals\n");
  296. derSeq::iterator iter=this->begin();
  297. while (iter!=this->end())
  298. {
  299. printf ("\nIntervals for G%X\n", n++);
  300. displayIntervals (iter->Ii);
  301. ++iter;
  302. }
  303. }
  304. /* Checks whether the control flow graph, cfg, is reducible or not.
  305. * If it is not reducible, it is converted into an equivalent reducible
  306. * graph by node splitting. The derived sequence of graphs built from cfg
  307. * are returned in the pointer *derivedG.
  308. */
  309. derSeq * Function::checkReducibility()
  310. {
  311. derSeq * der_seq;
  312. uint8_t reducible; /* Reducible graph flag */
  313. numInt = 1; /* reinitialize no. of intervals*/
  314. stats.nOrder = 1; /* nOrder(cfg) = 1 */
  315. der_seq = new derSeq;
  316. der_seq->resize(1);
  317. der_seq->back().Gi = *m_actual_cfg.begin(); /*m_cfg.front()*/;
  318. reducible = findDerivedSeq(*der_seq);
  319. if (! reducible)
  320. {
  321. flg |= GRAPH_IRRED;
  322. m_actual_cfg.nodeSplitting();
  323. }
  324. return der_seq;
  325. }