idioms.cpp 8.4 KB

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