idioms.cpp 8.5 KB

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