idioms.cpp 8.3 KB

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