idioms.cpp 8.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275
  1. /*****************************************************************************
  2. * dcc project machine idiom recognition
  3. * (C) Cristina Cifuentes
  4. ****************************************************************************/
  5. #include <cstring>
  6. #include <deque>
  7. #include "idiom.h"
  8. #include "idiom1.h"
  9. #include "epilogue_idioms.h"
  10. #include "call_idioms.h"
  11. #include "mov_idioms.h"
  12. #include "xor_idioms.h"
  13. #include "neg_idioms.h"
  14. #include "shift_idioms.h"
  15. #include "arith_idioms.h"
  16. #include "dcc.h"
  17. #include <boost/iterator/filter_iterator.hpp>
  18. /*****************************************************************************
  19. * JmpInst - Returns TRUE if opcode is a conditional or unconditional jump
  20. ****************************************************************************/
  21. bool JmpInst(llIcode opcode)
  22. {
  23. switch (opcode) {
  24. case iJMP: case iJMPF: case iJCXZ:
  25. case iLOOP: case iLOOPE:case iLOOPNE:
  26. case iJB: case iJBE: case iJAE: case iJA:
  27. case iJL: case iJLE: case iJGE: case iJG:
  28. case iJE: case iJNE: case iJS: case iJNS:
  29. case iJO: case iJNO: case iJP: case iJNP:
  30. return true;
  31. }
  32. return false;
  33. }
  34. /*****************************************************************************
  35. * findIdioms - translates LOW_LEVEL icode idioms into HIGH_LEVEL icodes.
  36. ****************************************************************************/
  37. void Function::findIdioms()
  38. {
  39. // int ip; /* Index to current icode */
  40. iICODE pEnd, pIcode; /* Pointers to end of BB and current icodes */
  41. int16_t delta;
  42. pIcode = Icode.begin();
  43. pEnd = Icode.end();
  44. Idiom1 i01(this);
  45. Idiom2 i02(this);
  46. Idiom3 i03(this);
  47. Idiom4 i04(this);
  48. Idiom13 i13(this);
  49. Idiom14 i14(this);
  50. Idiom17 i17(this);
  51. // xor idioms
  52. Idiom21 i21(this);
  53. Idiom7 i07(this);
  54. // or idioms
  55. Idiom10 i10(this);
  56. // neg idiom
  57. Idiom11 i11(this);
  58. Idiom16 i16(this);
  59. // shift idioms
  60. Idiom8 i08(this);
  61. Idiom12 i12(this);
  62. Idiom15 i15(this);
  63. Idiom9 i09(this);
  64. //arithmetic idioms
  65. Idiom5 i05(this);
  66. Idiom6 i06(this);
  67. Idiom18 i18(this);
  68. Idiom19 i19(this);
  69. Idiom20 i20(this);
  70. struct is_valid
  71. {
  72. bool operator()(ICODE &z) { return not z.invalid;}
  73. };
  74. typedef boost::filter_iterator<is_valid,iICODE> ifICODE;
  75. while (pIcode != pEnd)
  76. {
  77. switch (pIcode->ll()->opcode)
  78. {
  79. case iDEC: case iINC:
  80. if (i18.match(pIcode))
  81. advance(pIcode,i18.action());
  82. else if (i19.match(pIcode))
  83. advance(pIcode,i19.action());
  84. else if (i20.match(pIcode))
  85. advance(pIcode,i20.action());
  86. else
  87. pIcode++;
  88. break;
  89. case iPUSH:
  90. {
  91. /* Idiom 1 */
  92. // todo add other push idioms.
  93. advance(pIcode,i01(pIcode));
  94. break;
  95. }
  96. case iMOV:
  97. {
  98. if (i02.match(pIcode)) /* Idiom 2 */
  99. advance(pIcode,i02.action());
  100. else if (i14.match(pIcode)) /* Idiom 14 */
  101. advance(pIcode,i14.action());
  102. else if (i13.match(pIcode)) /* Idiom 13 */
  103. advance(pIcode,i13.action());
  104. else
  105. pIcode++;
  106. break;
  107. }
  108. case iCALL: case iCALLF:
  109. /* Check for library functions that return a long register.
  110. * Propagate this result */
  111. if (pIcode->ll()->src.proc.proc != 0)
  112. if ((pIcode->ll()->src.proc.proc->flg & PROC_ISLIB) &&
  113. (pIcode->ll()->src.proc.proc->flg & PROC_IS_FUNC))
  114. {
  115. if ((pIcode->ll()->src.proc.proc->retVal.type==TYPE_LONG_SIGN)
  116. || (pIcode->ll()->src.proc.proc->retVal.type == TYPE_LONG_UNSIGN))
  117. localId.newLongReg(TYPE_LONG_SIGN, rDX, rAX, pIcode/*ip*/);
  118. }
  119. /* Check for idioms */
  120. if (i03.match(pIcode)) /* idiom 3 */
  121. advance(pIcode,i03.action());
  122. else if (i17.match(pIcode)) /* idiom 17 */
  123. advance(pIcode,i17.action());
  124. else
  125. pIcode++;
  126. break;
  127. case iRET: /* Idiom 4 */
  128. case iRETF:
  129. advance(pIcode,i04(pIcode));
  130. break;
  131. case iADD: /* Idiom 5 */
  132. advance(pIcode,i05(pIcode));
  133. break;
  134. case iSAR: /* Idiom 8 */
  135. advance(pIcode,i08(pIcode));
  136. break;
  137. case iSHL:
  138. if (i15.match(pIcode)) /* idiom 15 */
  139. advance(pIcode,i15.action());
  140. else if (i12.match(pIcode)) /* idiom 12 */
  141. advance(pIcode,i12.action());
  142. else
  143. pIcode++;
  144. break;
  145. case iSHR: /* Idiom 9 */
  146. advance(pIcode,i09(pIcode));
  147. break;
  148. case iSUB: /* Idiom 6 */
  149. advance(pIcode,i06(pIcode));
  150. break;
  151. case iOR: /* Idiom 10 */
  152. advance(pIcode,i10(pIcode));
  153. break;
  154. case iNEG: /* Idiom 11 */
  155. if (i11.match(pIcode))
  156. advance(pIcode,i11.action());
  157. else if (i16.match(pIcode))
  158. advance(pIcode,i16.action());
  159. else
  160. pIcode++;
  161. break;
  162. case iNOP:
  163. (pIcode++)->invalidate();
  164. break;
  165. case iENTER: /* ENTER is equivalent to init PUSH bp */
  166. if (pIcode == Icode.begin()) //ip == 0
  167. {
  168. flg |= (PROC_HLL | PROC_IS_HLL);
  169. }
  170. pIcode++;
  171. break;
  172. case iXOR: /* Idiom 7 */
  173. if (i21.match(pIcode))
  174. advance(pIcode,i21.action());
  175. else if (i07.match(pIcode))
  176. advance(pIcode,i07.action());
  177. else
  178. ++pIcode;
  179. break;
  180. default:
  181. pIcode++;
  182. }
  183. }
  184. /* Check if number of parameter bytes match their calling convention */
  185. if ((flg & PROC_HLL) && (!args.sym.empty()))
  186. {
  187. args.m_minOff += (flg & PROC_FAR ? 4 : 2);
  188. delta = args.maxOff - args.m_minOff;
  189. if (cbParam != delta)
  190. {
  191. cbParam = delta;
  192. flg |= (CALL_MASK & CALL_UNKNOWN);
  193. }
  194. }
  195. }
  196. /* Sets up the TARGET flag for jump target addresses, and
  197. * binds jump target addresses to icode offsets. */
  198. void Function::bindIcodeOff()
  199. {
  200. int i; /* idx into icode array */
  201. iICODE pIcode; /* ptr icode array */
  202. uint32_t *p; /* for case table */
  203. if (Icode.empty()) /* No Icode */
  204. return;
  205. pIcode = Icode.begin();
  206. /* Flag all jump targets for BB construction and disassembly stage 2 */
  207. for(ICODE &c : Icode)
  208. {
  209. LLInst *ll=c.ll();
  210. if (ll->testFlags(I) && JmpInst(ll->opcode))
  211. {
  212. iICODE loc=Icode.labelSrch(ll->src.op());
  213. if (loc!=Icode.end())
  214. loc->ll()->setFlags(TARGET);
  215. }
  216. }
  217. /* Finally bind jump targets to Icode offsets. Jumps for which no label
  218. * is found (no code at dest. of jump) are simply left unlinked and
  219. * flagged as going nowhere. */
  220. //for (pIcode = Icode.begin(); pIcode!= Icode.end(); pIcode++)
  221. for(ICODE &icode : Icode)
  222. {
  223. LLInst *ll=icode.ll();
  224. if (not JmpInst(ll->opcode))
  225. continue;
  226. if (ll->testFlags(I) )
  227. {
  228. uint32_t found;
  229. if (! Icode.labelSrch(ll->src.op(), found))
  230. ll->setFlags( NO_LABEL );
  231. else
  232. ll->src.SetImmediateOp(found);
  233. }
  234. else if (ll->testFlags(SWITCH) )
  235. {
  236. p = ll->caseTbl.entries;
  237. for (int j = 0; j < ll->caseTbl.numEntries; j++, p++)
  238. Icode.labelSrch(*p, *p);
  239. }
  240. }
  241. }
  242. /** Performs idioms analysis, and propagates long operands, if any */
  243. void Function::lowLevelAnalysis ()
  244. {
  245. findIdioms(); // Idiom analysis - sets up some flags and creates some HIGH_LEVEL icodes
  246. propLong(); // Propagate HIGH_LEVEL idiom information for long operands
  247. }