sh_treg_combine.cc 48 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636
  1. /* An SH specific RTL pass that tries to combine comparisons and redundant
  2. condition code register stores across multiple basic blocks.
  3. Copyright (C) 2013-2015 Free Software Foundation, Inc.
  4. This file is part of GCC.
  5. GCC is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 3, or (at your option)
  8. any later version.
  9. GCC is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with GCC; see the file COPYING3. If not see
  15. <http://www.gnu.org/licenses/>. */
  16. #include "config.h"
  17. #include "system.h"
  18. #include "coretypes.h"
  19. #include "machmode.h"
  20. #include "predict.h"
  21. #include "vec.h"
  22. #include "hashtab.h"
  23. #include "hash-set.h"
  24. #include "tm.h"
  25. #include "hard-reg-set.h"
  26. #include "input.h"
  27. #include "function.h"
  28. #include "dominance.h"
  29. #include "cfg.h"
  30. #include "cfgrtl.h"
  31. #include "cfganal.h"
  32. #include "lcm.h"
  33. #include "cfgbuild.h"
  34. #include "cfgcleanup.h"
  35. #include "basic-block.h"
  36. #include "df.h"
  37. #include "rtl.h"
  38. #include "insn-config.h"
  39. #include "insn-codes.h"
  40. #include "emit-rtl.h"
  41. #include "recog.h"
  42. #include "tree-pass.h"
  43. #include "target.h"
  44. #include "symtab.h"
  45. #include "inchash.h"
  46. #include "tree.h"
  47. #include "optabs.h"
  48. #include "flags.h"
  49. #include "statistics.h"
  50. #include "double-int.h"
  51. #include "real.h"
  52. #include "fixed-value.h"
  53. #include "alias.h"
  54. #include "wide-int.h"
  55. #include "expmed.h"
  56. #include "dojump.h"
  57. #include "explow.h"
  58. #include "calls.h"
  59. #include "varasm.h"
  60. #include "stmt.h"
  61. #include "expr.h"
  62. #include <algorithm>
  63. #include <list>
  64. #include <vector>
  65. /*
  66. This pass tries to optimize for example this:
  67. mov.l @(4,r4),r1
  68. tst r1,r1
  69. movt r1
  70. tst r1,r1
  71. bt/s .L5
  72. into something simpler:
  73. mov.l @(4,r4),r1
  74. tst r1,r1
  75. bf/s .L5
  76. Such sequences can be identified by looking for conditional branches and
  77. checking whether the ccreg is set before the conditional branch
  78. by testing another register for != 0, which was set by a ccreg store.
  79. This can be optimized by eliminating the redundant comparison and
  80. inverting the branch condition. There can be multiple comparisons in
  81. different basic blocks that all end up in the redunant test insn before the
  82. conditional branch. Some example RTL ...
  83. Example 1)
  84. ----------
  85. [bb 3]
  86. (set (reg:SI 147 t) (eq:SI (reg:SI 173) (const_int 0)))
  87. (set (reg:SI 167) (xor:SI (reg:SI 147 t) (const_int 1)))
  88. -> bb 5
  89. [bb 4]
  90. (set (reg:SI 147 t) (eq:SI (reg:SI 177) (const_int 0)))
  91. (set (reg:SI 167) (reg:SI 147 t))
  92. -> bb 5
  93. [bb 5]
  94. (set (reg:SI 147 t) (eq:SI (reg:SI 167) (const_int 0)))
  95. (set (pc) (if_then_else (ne (reg:SI 147 t) (const_int 0))
  96. (label_ref:SI 50) (pc)))
  97. In [bb 4] elimination of the comparison would require inversion of the branch
  98. condition and compensation of other BBs.
  99. Instead the comparison in [bb 3] can be replaced with the comparison in [bb 5]
  100. by using a reg-reg move. In [bb 4] a logical not is used to compensate the
  101. inverted condition.
  102. [bb 3]
  103. (set (reg:SI 167) (reg:SI 173))
  104. -> bb 5
  105. [BB 4]
  106. (set (reg:SI 147 t) (eq:SI (reg:SI 177) (const_int 0)))
  107. (set (reg:SI 167) (reg:SI 147 t))
  108. -> bb 5
  109. [bb 5]
  110. (set (reg:SI 147 t) (eq:SI (reg:SI 167) (const_int 0)))
  111. (set (pc) (if_then_else (ne (reg:SI 147 t) (const_int 0)))
  112. (label_ref:SI 50) (pc)))
  113. Example 2)
  114. ----------
  115. [bb 3]
  116. (set (reg:SI 147 t) (gt:SI (reg:SI 173) (reg:SI 175)))
  117. (set (reg:SI 167) (reg:SI 147 t))
  118. -> bb 5
  119. [bb 4]
  120. (set (reg:SI 147 t) (gt:SI (reg:SI 177) (reg:SI 179)))
  121. (set (reg:SI 167) (reg:SI 147 t))
  122. -> bb 5
  123. [bb 5]
  124. (set (reg:SI 147 t) (eq:SI (reg:SI 167) (const_int 0)))
  125. (set (pc) (if_then_else (ne (reg:SI 147 t) (const_int 0))
  126. (label_ref:SI 51) (pc)))
  127. The common comparison is factored out and the branch condition is inverted:
  128. [bb 3]
  129. (set (reg:SI 167) (reg:SI 173))
  130. (set (reg:SI 200) (reg:SI 175))
  131. -> bb 5
  132. [bb 4]
  133. (set (reg:SI 167) (reg:SI 177))
  134. (set (reg:SI 200) (reg:SI 179))
  135. -> bb 5
  136. [bb 5]
  137. (set (reg:SI 147 t) (gt:SI (reg:SI 167) (reg:SI 200)))
  138. (set (pc) (if_then_else (eq (reg:SI 147 t) (const_int 0))
  139. (label_ref:SI 51) (pc)))
  140. Example 3)
  141. ----------
  142. [bb 3]
  143. (set (reg:SI 147 t) (gt:SI (reg:SI 173) (reg:SI 175)))
  144. (set (reg:SI 167) (reg:SI 147 t))
  145. -> bb 5
  146. [bb 4]
  147. (set (reg:SI 147 t) (ge:SI (reg:SI 179) (reg:SI 177)))
  148. (set (reg:SI 167) (reg:SI 147 t))
  149. -> bb 5
  150. [bb 5]
  151. (set (reg:SI 147 t) (eq:SI (reg:SI 167) (const_int 0)))
  152. (set (pc) (if_then_else (ne (reg:SI 147 t) (const_int 0))
  153. (label_ref:SI 51) (pc)))
  154. The T bit lifetime is extended and the branch condition is inverted:
  155. [bb 3]
  156. (set (reg:SI 147 t) (gt:SI (reg:SI 173) (reg:SI 175)))
  157. -> bb 5
  158. [bb 4]
  159. (set (reg:SI 147 t) (ge:SI (reg:SI 179) (reg:SI 177)))
  160. -> bb 5
  161. [bb 5]
  162. (set (pc) (if_then_else (eq (reg:SI 147 t) (const_int 0))
  163. (label_ref:SI 51) (pc)))
  164. Example 4)
  165. ----------
  166. [bb 3]
  167. (set (reg:SI 147 t) (eq:SI (reg:SI 173) (const_int 5)))
  168. (set (reg:SI 167) (reg:SI 147 t))
  169. -> bb 5
  170. [bb 4]
  171. (set (reg:SI 147 t) (eq:SI (reg:SI 176) (const_int 5)))
  172. (set (reg:SI 167) (xor:SI (reg:SI 147 t) (const_int 1)))
  173. -> bb 5
  174. [bb 5]
  175. (set (reg:SI 147 t) (eq:SI (reg:SI 167) (const_int 0)))
  176. (set (pc) (if_then_else (ne (reg:SI 147 t) (const_int 0))
  177. (label_ref:SI 50) (pc)))
  178. In this case the comparisons are the same and could be combined, but the
  179. branch condition is different for [bb 3] and [bb 5]. Since the comparison
  180. is not a zero comparison, we can't negate one of the operands. The best thing
  181. we can do here is to eliminate the comparison before the cbranch and invert
  182. the ccreg in one of the BBs. On SH2A this will utilize the 'nott' instruction.
  183. [bb 3]
  184. (set (reg:SI 147 t) (eq:SI (reg:SI 173) (const_int 5)))
  185. -> bb 5
  186. [bb 4]
  187. (set (reg:SI 147 t) (eq:SI (reg:SI 176) (const_int 5)))
  188. (set (reg:SI 147 t) (xor:SI (reg:SI 147 t) (const_int 1)))
  189. -> bb 5
  190. [bb 5]
  191. (set (pc) (if_then_else (eq (reg:SI 147 t) (const_int 0)) // inverted
  192. (label_ref:SI 50) (pc)))
  193. In order to handle cases such as above the RTL pass does the following:
  194. - Find the ccreg sets (comparisons) and ccreg stores
  195. (inverting and non-inverting) in all related BBs.
  196. - If the comparison types in the BBs are all the same, try to combine the
  197. comparisons in the BBs and replace the zero comparison before the cbranch
  198. with the common comparison.
  199. - If the cstores are the same, move the comparison before the cbranch
  200. and replace the comparisons in the BBs with reg-reg copies to get the
  201. operands in place (create new pseudo regs).
  202. - If the cstores differ and the comparison is a test against zero,
  203. use reg-reg copies for the dominating cstores and logical not cstores
  204. for the subordinate cstores.
  205. - If the comparison types in the BBs are not the same, or the first approach
  206. doesn't work out for some reason, try to eliminate the comparison before the
  207. cbranch by extending the lifetime of the ccreg by leaving the individual
  208. comparisons but eliminating the cstores.
  209. If the cstores are all the same this is straight forward.
  210. If they're not, try to reverse the ccreg for the subordinate cstore type
  211. and eliminate the dominating one.
  212. */
  213. // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  214. // Helper functions
  215. #define log_msg(...)\
  216. do { if (dump_file != NULL) fprintf (dump_file, __VA_ARGS__); } while (0)
  217. #define log_insn(i)\
  218. do { if (dump_file != NULL) print_rtl_single (dump_file, \
  219. (const_rtx)i); } while (0)
  220. #define log_rtx(r)\
  221. do { if (dump_file != NULL) print_rtl (dump_file, (const_rtx)r); } while (0)
  222. #define log_return(retval, ...)\
  223. do { if (dump_file != NULL) fprintf (dump_file, __VA_ARGS__); \
  224. return retval; } while (0)
  225. #define log_return_void(...)\
  226. do { if (dump_file != NULL) fprintf (dump_file, __VA_ARGS__); \
  227. return; } while (0)
  228. struct set_of_reg
  229. {
  230. // The insn where the search stopped or NULL.
  231. rtx_insn *insn;
  232. // The set rtx of the specified reg if found, NULL_RTX otherwise.
  233. // Notice that the set rtx can also be in a parallel.
  234. const_rtx set_rtx;
  235. // The set source operand rtx if found, NULL_RTX otherwise.
  236. rtx
  237. set_src (void) const
  238. {
  239. return set_rtx == NULL_RTX ? NULL_RTX : XEXP (set_rtx, 1);
  240. }
  241. // The set destination operand rtx if found, NULL_RTX otherwise.
  242. rtx
  243. set_dst (void) const
  244. {
  245. return set_rtx == NULL_RTX ? NULL_RTX : XEXP (set_rtx, 0);
  246. }
  247. bool
  248. empty (void) const
  249. {
  250. return insn == NULL_RTX || set_rtx == NULL_RTX;
  251. }
  252. };
  253. // Given a reg rtx and a start insn find the insn (in the same basic block)
  254. // that sets the reg.
  255. static set_of_reg
  256. find_set_of_reg_bb (rtx reg, rtx_insn *insn)
  257. {
  258. set_of_reg result = { insn, NULL_RTX };
  259. if (!REG_P (reg) || insn == NULL)
  260. return result;
  261. for (result.insn = insn; result.insn != NULL;
  262. result.insn = prev_nonnote_insn_bb (result.insn))
  263. {
  264. if (BARRIER_P (result.insn))
  265. return result;
  266. if (!NONJUMP_INSN_P (result.insn))
  267. continue;
  268. if (reg_set_p (reg, result.insn))
  269. {
  270. result.set_rtx = set_of (reg, result.insn);
  271. if (result.set_rtx == NULL_RTX || GET_CODE (result.set_rtx) != SET)
  272. result.set_rtx = NULL_RTX;
  273. return result;
  274. }
  275. }
  276. return result;
  277. }
  278. static bool
  279. reg_dead_after_insn (const_rtx reg, const_rtx insn)
  280. {
  281. return find_regno_note (insn, REG_DEAD, REGNO (reg)) != NULL_RTX;
  282. }
  283. static bool
  284. reg_unused_after_insn (const_rtx reg, const_rtx insn)
  285. {
  286. return find_regno_note (insn, REG_UNUSED, REGNO (reg)) != NULL_RTX;
  287. }
  288. // Check whether the two specified basic blocks are adjacent, i.e. there's no
  289. // other basic block in between them.
  290. static bool
  291. is_adjacent_bb (basic_block a, basic_block b)
  292. {
  293. basic_block bb0[] = { a, b };
  294. basic_block bb1[] = { b, a };
  295. for (int i = 0; i < 2; ++i)
  296. for (edge_iterator ei = ei_start (bb0[i]->succs);
  297. !ei_end_p (ei); ei_next (&ei))
  298. if (ei_edge (ei)->dest == bb1[i])
  299. return true;
  300. return false;
  301. }
  302. // Internal function of trace_reg_uses.
  303. static void
  304. trace_reg_uses_1 (rtx reg, rtx_insn *start_insn, basic_block bb, int& count,
  305. std::vector<basic_block>& visited_bb, rtx abort_at_insn)
  306. {
  307. if (bb == NULL)
  308. return;
  309. if (std::find (visited_bb.begin (), visited_bb.end (), bb)
  310. != visited_bb.end ())
  311. log_return_void ("[bb %d] already visited\n", bb->index);
  312. visited_bb.push_back (bb);
  313. if (BB_END (bb) == NULL_RTX)
  314. log_return_void ("[bb %d] BB_END is null\n", bb->index);
  315. if (start_insn == NULL_RTX)
  316. log_return_void ("[bb %d] start_insn is null\n", bb->index);
  317. rtx end_insn = NEXT_INSN (BB_END (bb));
  318. if (end_insn == NULL_RTX)
  319. log_return_void ("[bb %d] end_insn is null\n", bb->index);
  320. for (rtx_insn *i = NEXT_INSN (start_insn); i != end_insn; i = NEXT_INSN (i))
  321. {
  322. if (INSN_P (i))
  323. {
  324. if (NONDEBUG_INSN_P (i)
  325. && (reg_overlap_mentioned_p (reg, PATTERN (i))
  326. || (CALL_P (i) && find_reg_fusage (i, USE, reg))))
  327. {
  328. log_msg ("found use in [bb %d] at insn:\n", bb->index);
  329. log_insn (i);
  330. log_msg ("\n");
  331. count += 1;
  332. }
  333. // Stop following this BB if the reg is set or dies along the way.
  334. if (reg_set_p (reg, i) || reg_dead_after_insn (reg, i))
  335. return;
  336. }
  337. if (abort_at_insn != NULL_RTX && abort_at_insn == i)
  338. return;
  339. }
  340. for (edge_iterator ei = ei_start (bb->succs); !ei_end_p (ei); ei_next (&ei))
  341. {
  342. basic_block succ_bb = ei_edge (ei)->dest;
  343. trace_reg_uses_1 (reg, BB_HEAD (succ_bb), succ_bb, count, visited_bb,
  344. abort_at_insn);
  345. }
  346. }
  347. // Trace uses of the specified reg in all basic blocks that are reachable from
  348. // the specified insn. If 'abort_at_insn' is not null, abort the trace at
  349. // that insn. If the insn 'abort_at_insn' uses the specified reg, it is also
  350. // counted.
  351. static int
  352. trace_reg_uses (rtx reg, rtx_insn *start_insn, rtx abort_at_insn)
  353. {
  354. log_msg ("\ntrace_reg_uses\nreg = ");
  355. log_rtx (reg);
  356. log_msg ("\nstart_insn = ");
  357. log_insn (start_insn);
  358. int count = 0;
  359. std::vector<basic_block> visited_bb;
  360. visited_bb.reserve (32);
  361. trace_reg_uses_1 (reg, start_insn, BLOCK_FOR_INSN (start_insn),
  362. count, visited_bb, abort_at_insn);
  363. return count;
  364. }
  365. static bool
  366. is_conditional_insn (rtx_insn* i)
  367. {
  368. if (! (INSN_P (i) && NONDEBUG_INSN_P (i)))
  369. return false;
  370. rtx p = PATTERN (i);
  371. return GET_CODE (p) == SET && GET_CODE (XEXP (p, 1)) == IF_THEN_ELSE;
  372. }
  373. // FIXME: Remove dependency on SH predicate function somehow.
  374. extern int t_reg_operand (rtx, machine_mode);
  375. extern int negt_reg_operand (rtx, machine_mode);
  376. // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  377. // RTL pass class
  378. class sh_treg_combine : public rtl_opt_pass
  379. {
  380. public:
  381. sh_treg_combine (gcc::context* ctx, bool split_insns, const char* name);
  382. virtual ~sh_treg_combine (void);
  383. virtual bool gate (function *);
  384. virtual unsigned int execute (function *);
  385. private:
  386. // Type of ccreg store that is supported.
  387. enum cstore_type_t
  388. {
  389. cstore_normal = 0,
  390. cstore_inverted = 1,
  391. cstore_unknown = -1
  392. };
  393. // Type of branch condition that is supported.
  394. enum branch_condition_type_t
  395. {
  396. branch_if_true = 1,
  397. branch_if_false = 0,
  398. unknown_branch_condition = -1
  399. };
  400. // For each basic block there can be a trace entry which consists of an
  401. // insn that sets the ccreg (usually a comparison) and a ccreg store.
  402. struct bb_entry
  403. {
  404. basic_block bb;
  405. set_of_reg setcc;
  406. set_of_reg cstore;
  407. cstore_type_t cstore_type;
  408. std::vector<set_of_reg> cstore_reg_reg_copies;
  409. bb_entry (basic_block b)
  410. : bb (b), setcc (), cstore (), cstore_type (cstore_unknown) { }
  411. rtx comparison_rtx (void) const { return setcc.set_src (); }
  412. };
  413. // A ccreg trace for a conditional branch.
  414. struct cbranch_trace
  415. {
  416. rtx_insn *cbranch_insn;
  417. rtx* condition_rtx_in_insn;
  418. branch_condition_type_t cbranch_type;
  419. // The comparison against zero right before the conditional branch.
  420. set_of_reg setcc;
  421. // All BBs that are related to the cbranch. The last BB in the list is
  422. // the BB of the cbranch itself and might be empty.
  423. std::list<bb_entry> bb_entries;
  424. cbranch_trace (rtx_insn *insn)
  425. : cbranch_insn (insn),
  426. condition_rtx_in_insn (NULL),
  427. cbranch_type (unknown_branch_condition),
  428. setcc ()
  429. {
  430. if (is_conditional_insn (cbranch_insn))
  431. condition_rtx_in_insn = &XEXP (XEXP (PATTERN (cbranch_insn), 1), 0);
  432. else if (rtx x = pc_set (cbranch_insn))
  433. condition_rtx_in_insn = &XEXP (XEXP (x, 1), 0);
  434. }
  435. basic_block bb (void) const { return BLOCK_FOR_INSN (cbranch_insn); }
  436. rtx
  437. branch_condition_rtx (void) const
  438. {
  439. return condition_rtx_in_insn != NULL ? *condition_rtx_in_insn : NULL;
  440. }
  441. rtx&
  442. branch_condition_rtx_ref (void) const
  443. {
  444. // Before anything gets to invoke this function, there are other checks
  445. // in place to make sure that we have a known branch condition and thus
  446. // the ref to the rtx in the insn.
  447. gcc_assert (condition_rtx_in_insn != NULL);
  448. return *condition_rtx_in_insn;
  449. }
  450. bool
  451. can_invert_condition (void) const
  452. {
  453. // The branch condition can be inverted safely only if the condition
  454. // reg is dead after the cbranch.
  455. return reg_dead_after_insn (XEXP (branch_condition_rtx (), 0),
  456. cbranch_insn);
  457. }
  458. };
  459. static const pass_data default_pass_data;
  460. // Tells whether modified or newly added insns are to be split at the end
  461. // of the pass.
  462. const bool m_split_insns;
  463. // rtx of the ccreg that is obtained from the target.
  464. rtx m_ccreg;
  465. // Newly added or modified insns.
  466. std::vector<rtx> m_touched_insns;
  467. // Given an rtx determine whether it's a comparison with a constant zero.
  468. static bool is_cmp_eq_zero (const_rtx i);
  469. // Update the stored mode of the ccreg from the given branch condition rtx.
  470. void update_ccreg_mode (const_rtx cond);
  471. // Given an rtx, figure out the branch condition, assuming that it is
  472. // in canonical form:
  473. // (ne (reg) (const_int 0))
  474. // (eq (reg) (const_int 0))
  475. branch_condition_type_t branch_condition_type (const_rtx cond) const;
  476. // Return true if the specified rtx is either a normal ccreg or
  477. // a negated form of the ccreg.
  478. bool is_normal_ccreg (const_rtx x) const;
  479. bool is_inverted_ccreg (const_rtx x) const;
  480. // Given a reg rtx and a start insn rtx, try to find the insn in the same
  481. // basic block that sets the specified reg.
  482. // Return how the search ended and the insn where it stopped or NULL_RTX.
  483. enum record_return_t
  484. {
  485. set_found,
  486. set_not_found,
  487. other_set_found
  488. };
  489. record_return_t record_set_of_reg (rtx reg, rtx_insn *start_insn,
  490. bb_entry& e);
  491. // Tells whether the cbranch insn of the specified bb_entry can be removed
  492. // safely without triggering any side effects.
  493. bool can_remove_cstore (const bb_entry& e,
  494. const cbranch_trace& trace) const;
  495. // Tells whether the setcc insn of the specified bb_entry can be removed
  496. // safely without triggering any side effects.
  497. bool can_remove_comparison (const bb_entry& e,
  498. const cbranch_trace& trace) const;
  499. // Tells whether the two specified comparison rtx can be combined into a
  500. // single comparison.
  501. bool can_combine_comparisons (const_rtx x, const_rtx y) const;
  502. // Tells whether the ccreg usage can be extended from the bb_entry on until
  503. // the final cbranch of the trace.
  504. bool can_extend_ccreg_usage (const bb_entry& e,
  505. const cbranch_trace& trace) const;
  506. // Create an insn rtx that performs a logical not (test != 0) on the src_reg
  507. // and stores the result in dst_reg.
  508. rtx make_not_reg_insn (rtx dst_reg, rtx src_reg) const;
  509. // Create an insn rtx that inverts the ccreg.
  510. rtx_insn *make_inv_ccreg_insn (void) const;
  511. // Adds the specified insn to the set of modified or newly added insns that
  512. // might need splitting at the end of the pass.
  513. rtx touched_insn (rtx i);
  514. // Try to invert the branch condition of the specified trace.
  515. bool try_invert_branch_condition (cbranch_trace& trace);
  516. // Try to optimize a cbranch trace by combining comparisons in BBs and
  517. // eliminate the cstores.
  518. bool try_combine_comparisons (cbranch_trace& trace,
  519. int cstore_count, int inv_cstore_count,
  520. cstore_type_t dominating_cstore);
  521. // Try to optimize a cbranch trace by eliminating the cstores in BBs only.
  522. bool try_eliminate_cstores (cbranch_trace& trace,
  523. int cstore_count, int inv_cstore_count,
  524. cstore_type_t dominating_cstore);
  525. // Given a branch insn, try to optimize its branch condition.
  526. // If any insns are modified or added they are added to 'm_touched_insns'.
  527. void try_optimize_cbranch (rtx_insn *i);
  528. };
  529. const pass_data sh_treg_combine::default_pass_data =
  530. {
  531. RTL_PASS, // type
  532. "", // name (overwritten by the constructor)
  533. OPTGROUP_NONE, // optinfo_flags
  534. TV_OPTIMIZE, // tv_id
  535. 0, // properties_required
  536. 0, // properties_provided
  537. 0, // properties_destroyed
  538. 0, // todo_flags_start
  539. TODO_df_finish | TODO_df_verify // todo_flags_finish
  540. };
  541. sh_treg_combine::sh_treg_combine (gcc::context* ctx, bool split_insns,
  542. const char* name)
  543. : rtl_opt_pass (default_pass_data, ctx),
  544. m_split_insns (split_insns),
  545. m_ccreg (NULL_RTX)
  546. {
  547. // Overwrite default name in pass_data base class.
  548. this->name = name;
  549. }
  550. sh_treg_combine::~sh_treg_combine (void)
  551. {
  552. }
  553. void sh_treg_combine::update_ccreg_mode (const_rtx cond)
  554. {
  555. if (REG_P (XEXP (cond, 0)) && REGNO (XEXP (cond, 0)) != REGNO (m_ccreg))
  556. return;
  557. machine_mode m = GET_MODE (XEXP (cond, 0));
  558. if (m == GET_MODE (m_ccreg))
  559. return;
  560. PUT_MODE (m_ccreg, m);
  561. log_msg ("updated ccreg mode: ");
  562. log_rtx (m_ccreg);
  563. log_msg ("\n");
  564. }
  565. bool
  566. sh_treg_combine::is_cmp_eq_zero (const_rtx i)
  567. {
  568. return i != NULL_RTX && GET_CODE (i) == EQ
  569. && REG_P (XEXP (i, 0)) && XEXP (i, 1) == const0_rtx;
  570. }
  571. sh_treg_combine::branch_condition_type_t
  572. sh_treg_combine::branch_condition_type (const_rtx cond) const
  573. {
  574. if (cond == NULL_RTX)
  575. return unknown_branch_condition;
  576. if (GET_CODE (cond) == NE
  577. && REG_P (XEXP (cond, 0)) && REGNO (XEXP (cond, 0)) == REGNO (m_ccreg)
  578. && XEXP (cond, 1) == const0_rtx)
  579. return branch_if_true;
  580. else if (GET_CODE (cond) == EQ
  581. && REG_P (XEXP (cond, 0)) && REGNO (XEXP (cond, 0)) == REGNO (m_ccreg)
  582. && XEXP (cond, 1) == const0_rtx)
  583. return branch_if_false;
  584. else
  585. return unknown_branch_condition;
  586. }
  587. bool
  588. sh_treg_combine::is_normal_ccreg (const_rtx x) const
  589. {
  590. return t_reg_operand (const_cast<rtx> (x), VOIDmode);
  591. }
  592. bool
  593. sh_treg_combine::is_inverted_ccreg (const_rtx x) const
  594. {
  595. return negt_reg_operand (const_cast<rtx> (x), VOIDmode);
  596. }
  597. sh_treg_combine::record_return_t
  598. sh_treg_combine::record_set_of_reg (rtx reg, rtx_insn *start_insn,
  599. bb_entry& new_entry)
  600. {
  601. log_msg ("\n[bb %d]\n", new_entry.bb->index);
  602. if (start_insn == NULL_RTX)
  603. log_return (set_not_found, "set of reg not found. empty BB?\n");
  604. new_entry.cstore_type = cstore_unknown;
  605. for (rtx_insn *i = start_insn; i != NULL; )
  606. {
  607. new_entry.cstore = find_set_of_reg_bb (reg, i);
  608. if (new_entry.cstore.set_src () == NULL_RTX)
  609. log_return (set_not_found, "set of reg not found (cstore)\n");
  610. log_insn (new_entry.cstore.insn);
  611. log_msg ("\n");
  612. if (is_normal_ccreg (new_entry.cstore.set_src ()))
  613. {
  614. log_msg ("normal condition store\n");
  615. new_entry.cstore_type = cstore_normal;
  616. }
  617. else if (is_inverted_ccreg (new_entry.cstore.set_src ()))
  618. {
  619. log_msg ("inverted condition store\n");
  620. new_entry.cstore_type = cstore_inverted;
  621. }
  622. else if (REG_P (new_entry.cstore.set_src ()))
  623. {
  624. // If it's a reg-reg copy follow the copied reg.
  625. new_entry.cstore_reg_reg_copies.push_back (new_entry.cstore);
  626. reg = new_entry.cstore.set_src ();
  627. i = new_entry.cstore.insn;
  628. log_msg ("reg-reg copy. tracing ");
  629. log_rtx (reg);
  630. log_msg ("\n");
  631. continue;
  632. }
  633. else
  634. log_return (other_set_found, "not a condition store\n");
  635. gcc_assert (new_entry.cstore_type != cstore_unknown);
  636. // Now see how the ccreg was set.
  637. // For now it must be in the same BB.
  638. log_msg ("tracing ccreg\n");
  639. new_entry.setcc =
  640. find_set_of_reg_bb (m_ccreg,
  641. prev_nonnote_insn_bb (new_entry.cstore.insn));
  642. // If cstore was found but setcc was not found continue anyway, as
  643. // for some of the optimization types the setcc is irrelevant.
  644. if (new_entry.setcc.set_src () == NULL_RTX)
  645. log_return (set_found, "set of ccreg not found\n");
  646. else if (GET_CODE (new_entry.setcc.set_rtx) == SET)
  647. {
  648. // Also allow insns that set the ccreg, but are not true comparison
  649. // insns, as long as they are sets and not e.g. clobbers.
  650. log_insn (new_entry.setcc.insn);
  651. log_msg ("\n");
  652. return set_found;
  653. }
  654. else
  655. // If cstore was found but setcc was not found continue anyway, as
  656. // for some of the optimization types the setcc is irrelevant.
  657. log_return (set_found, "unknown set of ccreg\n");
  658. }
  659. log_return (set_not_found, "set of reg not found\n");
  660. }
  661. bool
  662. sh_treg_combine::can_remove_cstore (const bb_entry& e,
  663. const cbranch_trace& trace) const
  664. {
  665. if (volatile_insn_p (PATTERN (e.cstore.insn)))
  666. {
  667. log_msg ("can't remove insn\n");
  668. log_insn (e.cstore.insn);
  669. log_return (false, "\nbecause it's volatile\n");
  670. }
  671. // On SH there are parallel patterns which store the ccreg multiple times.
  672. // In this case it's not safe.
  673. rtx cstore_pat = PATTERN (e.cstore.insn);
  674. if (GET_CODE (cstore_pat) == PARALLEL)
  675. for (int i = 0; i < XVECLEN (cstore_pat, 0); ++i)
  676. {
  677. rtx x = XVECEXP (cstore_pat, 0, i);
  678. // It's the cstore set that we're referring to, ignore that one.
  679. if (x != e.cstore.set_rtx
  680. && GET_CODE (x) == SET && reg_referenced_p (m_ccreg, x))
  681. {
  682. log_msg ("can't remove insn\n");
  683. log_insn (e.cstore.insn);
  684. log_return (false, "\nbecause it's a multiple ccreg store\n");
  685. }
  686. }
  687. // If the cstore sets the ccreg (e.g. negc) and the ccreg is used afterwards
  688. // it's not safe.
  689. if (modified_in_p (m_ccreg, e.cstore.insn)
  690. && !(reg_dead_after_insn (m_ccreg, e.cstore.insn)
  691. || reg_unused_after_insn (m_ccreg, e.cstore.insn)))
  692. {
  693. log_msg ("can't remove insn\n");
  694. log_insn (e.cstore.insn);
  695. log_return (false, "\nbecause it sets the ccreg\n");
  696. }
  697. // If the cstore destination reg is copied around check the reg-reg
  698. // copies. At every reg-reg copy the copied reg must be dead and there
  699. // must not be a usage of the copied regs between the reg-reg copies.
  700. // Otherwise we assume that the result of the cstore is used in some
  701. // other way.
  702. rtx_insn *prev_insn = e.cstore.insn;
  703. for (std::vector<set_of_reg>::const_reverse_iterator i =
  704. e.cstore_reg_reg_copies.rbegin ();
  705. i != e.cstore_reg_reg_copies.rend (); ++i)
  706. {
  707. if (!reg_dead_after_insn (i->set_src (), i->insn))
  708. {
  709. log_msg ("can't remove insn\n");
  710. log_insn (i->insn);
  711. log_return (false, "\nbecause source of reg-reg copy doesn't die\n");
  712. }
  713. if (reg_used_between_p (i->set_src (), prev_insn, i->insn))
  714. {
  715. log_msg ("can't remove insn\n");
  716. log_insn (i->insn);
  717. log_return (false, "\nbecause reg %d is otherwise used\n",
  718. REGNO (i->set_src ()));
  719. }
  720. prev_insn = i->insn;
  721. }
  722. // The cstore_dst reg must die after the test before the cbranch, otherwise
  723. // it's not safe to remove the cstore.
  724. // If the cstore destination reg is copied around check the effective
  725. // destination reg of the cstore. The reg-reg copies are recorded in
  726. // reverse order, i.e. the most recent reg-reg copy in the insn list
  727. // comes first.
  728. rtx cstore_dst = e.cstore_reg_reg_copies.empty ()
  729. ? e.cstore.set_dst ()
  730. : e.cstore_reg_reg_copies.front ().set_dst ();
  731. if (!reg_dead_after_insn (cstore_dst, trace.setcc.insn))
  732. {
  733. log_msg ("can't remove insn\n");
  734. log_insn (e.cstore.insn);
  735. log_return (false, "\nbecause its effective target reg %d doesn't die "
  736. "after trace.setcc.insn\n", REGNO (cstore_dst));
  737. }
  738. // Also check that the cstore_dst reg is not used in other reachable code
  739. // paths before it dies.
  740. // Count the uses of the effective cstore_dst reg (i.e. the last known reg
  741. // that holds the cstore value after reg-reg copies) in all BBs that can be
  742. // reached from bb_entry's BB including the BB of the cstore insn.
  743. // If we get more than 1 uses we assume that it's used somewhere else and is
  744. // not safe to be removed.
  745. int cstore_dst_use_count = trace_reg_uses (cstore_dst, e.cstore.insn,
  746. trace.setcc.insn);
  747. if (cstore_dst_use_count > 1)
  748. {
  749. log_msg ("can't remove insn\n");
  750. log_insn (e.cstore.insn);
  751. log_return (false, "\nbecause its effective target reg %d is used "
  752. "in %d other places\n", REGNO (cstore_dst),
  753. cstore_dst_use_count - 1);
  754. }
  755. return true;
  756. }
  757. bool
  758. sh_treg_combine::can_remove_comparison (const bb_entry& e,
  759. const cbranch_trace&/* trace*/) const
  760. {
  761. // If the ccreg is used otherwise between the comparison and the cstore,
  762. // it's not safe.
  763. if (reg_used_between_p (m_ccreg, e.setcc.insn, e.cstore.insn))
  764. {
  765. log_msg ("can't remove insn\n");
  766. log_insn (e.setcc.insn);
  767. log_return (false, "\nbecause the ccreg is used otherwise\n");
  768. }
  769. if (!reg_dead_after_insn (m_ccreg, e.cstore.insn)
  770. && !reg_unused_after_insn (m_ccreg, e.cstore.insn))
  771. {
  772. log_msg ("can't remove insn\n");
  773. log_insn (e.cstore.insn);
  774. log_return (false, "\nbecause ccreg is not dead or unused afterwards\n");
  775. }
  776. // On SH there are also multiple set patterns that can be used for
  777. // comparisons, such as "shll". It's not safe to remove those.
  778. if (multiple_sets (e.setcc.insn))
  779. {
  780. log_msg ("can't remove insn\n");
  781. log_insn (e.cstore.insn);
  782. log_return (false, "\nbecause it's a multiple set\n");
  783. }
  784. return true;
  785. }
  786. rtx
  787. sh_treg_combine::make_not_reg_insn (rtx dst_reg, rtx src_reg) const
  788. {
  789. // On SH we can do only SImode and DImode comparisons.
  790. if (! (GET_MODE (src_reg) == SImode || GET_MODE (src_reg) == DImode))
  791. return NULL;
  792. // On SH we can store the ccreg into an SImode or DImode reg only.
  793. if (! (GET_MODE (dst_reg) == SImode || GET_MODE (dst_reg) == DImode))
  794. return NULL;
  795. start_sequence ();
  796. emit_insn (gen_rtx_SET (VOIDmode, m_ccreg,
  797. gen_rtx_fmt_ee (EQ, SImode, src_reg, const0_rtx)));
  798. if (GET_MODE (dst_reg) == SImode)
  799. emit_move_insn (dst_reg, m_ccreg);
  800. else if (GET_MODE (dst_reg) == DImode)
  801. {
  802. emit_move_insn (gen_lowpart (SImode, dst_reg), m_ccreg);
  803. emit_move_insn (gen_highpart (SImode, dst_reg), const0_rtx);
  804. }
  805. else
  806. gcc_unreachable ();
  807. rtx i = get_insns ();
  808. end_sequence ();
  809. return i;
  810. }
  811. rtx_insn *
  812. sh_treg_combine::make_inv_ccreg_insn (void) const
  813. {
  814. start_sequence ();
  815. rtx_insn *i = emit_insn (gen_rtx_SET (VOIDmode, m_ccreg,
  816. gen_rtx_fmt_ee (XOR, GET_MODE (m_ccreg),
  817. m_ccreg, const1_rtx)));
  818. end_sequence ();
  819. return i;
  820. }
  821. rtx
  822. sh_treg_combine::touched_insn (rtx i)
  823. {
  824. m_touched_insns.push_back (i);
  825. return i;
  826. }
  827. bool
  828. sh_treg_combine::can_combine_comparisons (const_rtx x, const_rtx y) const
  829. {
  830. if (GET_CODE (x) != GET_CODE (y))
  831. return false;
  832. rtx x_op0 = XEXP (x, 0);
  833. rtx x_op1 = XEXP (x, 1);
  834. rtx y_op0 = XEXP (y, 0);
  835. rtx y_op1 = XEXP (y, 1);
  836. if (!REG_P (x_op0) || !REG_P (y_op0))
  837. return false;
  838. if (GET_MODE (x_op0) != GET_MODE (y_op0))
  839. return false;
  840. // rtx_equal_p also compares the reg numbers which we do not care about
  841. // here, as long as both are regs and the modes are the same.
  842. if (REG_P (x_op1))
  843. return REG_P (y_op1) && GET_MODE (x_op1) == GET_MODE (y_op1);
  844. return rtx_equal_p (x_op1, y_op1);
  845. }
  846. bool
  847. sh_treg_combine::can_extend_ccreg_usage (const bb_entry& e,
  848. const cbranch_trace& trace) const
  849. {
  850. // Check if the ccreg is not modified by other insins in the BB path until
  851. // the final cbranch of the trace.
  852. // Start checking after the cstore that follows the setcc, assuming that
  853. // the cstore will be removed.
  854. // The assumption here is that the specified bb_entry's BB is a direct
  855. // predecessor of the trace.cbranch_insn's BB.
  856. if (e.bb != trace.bb () && !is_adjacent_bb (e.bb, trace.bb ()))
  857. log_return (false,
  858. "can't extend ccreg usage -- [bb %d] and [bb %d] are not adjacent\n",
  859. e.bb->index, trace.bb ()->index);
  860. if (e.cstore.empty ())
  861. log_return (false, "can't extend ccreg usage -- no cstore\n");
  862. // The entry's cstore is in the same BB as the final cbranch.
  863. if (e.bb == trace.bb ())
  864. {
  865. if (reg_set_between_p (m_ccreg, e.cstore.insn, trace.setcc.insn))
  866. log_return (false,
  867. "can't extend ccreg usage -- it's modified between e.cstore.insn "
  868. "and trace.setcc.insn");
  869. else
  870. return true;
  871. }
  872. // The entry's cstore and the final cbranch are in different BBs.
  873. if (reg_set_between_p (m_ccreg, e.cstore.insn, NEXT_INSN (BB_END (e.bb))))
  874. log_return (false,
  875. "can't extend ccreg usage -- it's modified in [bb %d]", e.bb->index);
  876. if (reg_set_between_p (m_ccreg, PREV_INSN (BB_HEAD (trace.bb ())),
  877. trace.setcc.insn))
  878. log_return (false,
  879. "can't extend ccreg usage -- it's modified in [bb %d]",
  880. trace.bb ()->index);
  881. return true;
  882. }
  883. bool
  884. sh_treg_combine::try_invert_branch_condition (cbranch_trace& trace)
  885. {
  886. log_msg ("inverting branch condition\n");
  887. rtx& comp = trace.branch_condition_rtx_ref ();
  888. rtx_code rev_cmp_code = reversed_comparison_code (comp, trace.cbranch_insn);
  889. if (rev_cmp_code == UNKNOWN)
  890. log_return (false, "reversed_comparison_code = UNKNOWN\n");
  891. validate_change (trace.cbranch_insn, &comp,
  892. gen_rtx_fmt_ee (rev_cmp_code,
  893. GET_MODE (comp), XEXP (comp, 0),
  894. XEXP (comp, 1)),
  895. 1);
  896. if (verify_changes (num_validated_changes ()))
  897. confirm_change_group ();
  898. else
  899. log_return (false, "verify_changed failed\n");
  900. touched_insn (trace.cbranch_insn);
  901. return true;
  902. }
  903. bool
  904. sh_treg_combine::try_combine_comparisons (cbranch_trace& trace,
  905. int cstore_count,
  906. int inv_cstore_count,
  907. cstore_type_t dominating_cstore)
  908. {
  909. log_msg ("\ntry_combine_comparisons\n");
  910. // This function will always try to create new pseudos.
  911. if (!can_create_pseudo_p ())
  912. log_return (false, "can't create pseudos\n");
  913. // Check that all ccset insns are comparisons and all comparison types in
  914. // all BBs are the same and could be combined into one single comparison.
  915. rtx comp = NULL_RTX;
  916. rtx comp_insn = NULL_RTX;
  917. for (std::list<bb_entry>::const_iterator i = trace.bb_entries.begin ();
  918. i != trace.bb_entries.end (); ++i)
  919. {
  920. int i_empty_count = i->setcc.empty () + i->cstore.empty ();
  921. // A completly empty entry is OK (could be the BB of the cbranch).
  922. if (i_empty_count == 2)
  923. continue;
  924. // Otherwise we need both, the setcc and the cstore.
  925. if (i_empty_count != 0)
  926. log_return (false, "bb entry is not a setcc cstore pair\n");
  927. rtx other_comp = i->comparison_rtx ();
  928. if (!COMPARISON_P (other_comp))
  929. {
  930. log_msg ("setcc is not a comparison:\n");
  931. log_rtx (other_comp);
  932. log_return (false, "\n");
  933. }
  934. if (comp_insn == NULL_RTX)
  935. {
  936. comp = other_comp;
  937. comp_insn = i->setcc.insn;
  938. }
  939. else if (!can_combine_comparisons (comp, other_comp))
  940. return false;
  941. // The goal here is to eliminate all cstores and comparisons in the BBs.
  942. // Thus check if every cstore can actually be removed safely.
  943. if (!can_remove_cstore (*i, trace) || !can_remove_comparison (*i, trace))
  944. return false;
  945. }
  946. // FIXME: The first operand of the comparison must be a simple reg.
  947. // This effectively prohibits combining div0s comparisons such as
  948. // (lt:SI (xor:SI (reg:SI) (reg:SI)))
  949. if (!REG_P (XEXP (comp, 0)))
  950. {
  951. log_msg ("comparison operand 0\n");
  952. log_rtx (XEXP (comp, 0));
  953. log_return (false, "\nis not a reg\n");
  954. }
  955. rtx comp_op0 = gen_reg_rtx (GET_MODE (XEXP (comp, 0)));
  956. rtx comp_op1 = REG_P (XEXP (comp, 1))
  957. ? gen_reg_rtx (GET_MODE (XEXP (comp, 1)))
  958. : XEXP (comp, 1);
  959. // If there are both, inverting and non-inverting cstores, they can only
  960. // be eliminated if the comparison can be inverted. We assume that the
  961. // comparison insns that we find are already minimal and canonicalized.
  962. // There is one special case though, where an integer comparison
  963. // (eq (reg) (const_int 0))
  964. // can be inverted with a sequence
  965. // (set (t) (eq (reg) (const_int 0))
  966. // (set (reg) (t))
  967. // (eq (reg) (const_int 0))
  968. //
  969. // FIXME: On SH2A it might be better to use the nott insn in this case,
  970. // i.e. do the try_eliminate_cstores approach instead.
  971. if (inv_cstore_count != 0 && cstore_count != 0)
  972. {
  973. if (make_not_reg_insn (comp_op0, comp_op0) == NULL_RTX)
  974. log_return (false, "make_not_reg_insn failed.\n");
  975. for (std::list<bb_entry>::const_iterator i = trace.bb_entries.begin ();
  976. i != trace.bb_entries.end (); ++i)
  977. {
  978. if (i->setcc.empty () || i->cstore.empty ())
  979. continue;
  980. if (i->cstore_type != dominating_cstore
  981. && !is_cmp_eq_zero (i->comparison_rtx ()))
  982. {
  983. log_msg ("can't invert comparison in insn\n");
  984. log_insn (i->setcc.insn);
  985. log_return (false,
  986. "\nbecause it's not a (eq (reg) (const_int 0))\n");
  987. }
  988. }
  989. }
  990. if (dominating_cstore == cstore_normal
  991. && !try_invert_branch_condition (trace))
  992. return false;
  993. // Replace the test insn before the cbranch with the common comparison.
  994. // Instead of creating a new insn from scratch we copy the common comparison
  995. // pattern. This simplifies handling parallel comparison patterns, such as
  996. // FP comparisons on SH, which have an extra use on FPSCR.
  997. log_msg ("installing common comparison in [bb %d]\n", trace.bb ()->index);
  998. rtx common_comp_pat = copy_rtx (PATTERN (comp_insn));
  999. rtx common_comp = const_cast<rtx> (set_of (m_ccreg, common_comp_pat));
  1000. gcc_assert (common_comp != NULL_RTX);
  1001. XEXP (XEXP (common_comp, 1), 0) = comp_op0;
  1002. XEXP (XEXP (common_comp, 1), 1) = comp_op1;
  1003. log_rtx (common_comp_pat);
  1004. log_msg ("\n");
  1005. rtx common_comp_insn = touched_insn (emit_insn_after (common_comp_pat,
  1006. trace.setcc.insn));
  1007. if (REG_P (comp_op0))
  1008. add_reg_note (common_comp_insn, REG_DEAD, copy_rtx (comp_op0));
  1009. if (REG_P (comp_op1))
  1010. add_reg_note (common_comp_insn, REG_DEAD, copy_rtx (comp_op1));
  1011. delete_insn (trace.setcc.insn);
  1012. // Replace comparison and cstore insns with reg-reg moves in all BBs.
  1013. for (std::list<bb_entry>::const_iterator i = trace.bb_entries.begin ();
  1014. i != trace.bb_entries.end (); ++i)
  1015. {
  1016. if (i->setcc.empty () || i->cstore.empty ())
  1017. continue;
  1018. rtx i_comp_op0 = XEXP (i->comparison_rtx (), 0);
  1019. rtx i_comp_op1 = XEXP (i->comparison_rtx (), 1);
  1020. if (i->cstore_type == dominating_cstore)
  1021. {
  1022. log_msg ("replacing comparison and cstore with reg move "
  1023. "in [bb %d]\n", i->bb->index);
  1024. rtx new_i = touched_insn (
  1025. emit_insn_after (gen_move_insn (comp_op0, i_comp_op0),
  1026. i->setcc.insn));
  1027. if (REG_P (i_comp_op0)
  1028. && reg_dead_after_insn (i_comp_op0, i->setcc.insn))
  1029. add_reg_note (new_i, REG_DEAD, copy_rtx (i_comp_op0));
  1030. // If the second operand is a reg, have to emit a move insn.
  1031. // Otherwise assume it's a const_int and just reference it.
  1032. if (REG_P (comp_op1))
  1033. {
  1034. new_i = touched_insn (
  1035. emit_insn_after (gen_move_insn (comp_op1, i_comp_op1),
  1036. i->setcc.insn));
  1037. if (reg_dead_after_insn (i_comp_op1, i->setcc.insn))
  1038. add_reg_note (new_i, REG_DEAD, copy_rtx (i_comp_op1));
  1039. }
  1040. }
  1041. else
  1042. {
  1043. log_msg ("replacing comparison and cstore with inverting reg move "
  1044. "in [bb %d]\n", i->bb->index);
  1045. rtx new_i = make_not_reg_insn (comp_op0, i_comp_op0);
  1046. if (REG_P (i_comp_op0)
  1047. && reg_dead_after_insn (i_comp_op0, i->setcc.insn))
  1048. add_reg_note (new_i, REG_DEAD, copy_rtx (i_comp_op0));
  1049. touched_insn (emit_insn_after (new_i, i->setcc.insn));
  1050. }
  1051. delete_insn (i->cstore.insn);
  1052. delete_insn (i->setcc.insn);
  1053. }
  1054. return true;
  1055. }
  1056. bool
  1057. sh_treg_combine::try_eliminate_cstores (cbranch_trace& trace,
  1058. int cstore_count, int inv_cstore_count,
  1059. cstore_type_t dominating_cstore)
  1060. {
  1061. log_msg ("\ntry_eliminate_cstores\n");
  1062. for (std::list<bb_entry>::const_iterator i = trace.bb_entries.begin ();
  1063. i != trace.bb_entries.end (); ++i)
  1064. {
  1065. // A completly empty entry is OK (could be the BB of the cbranch).
  1066. if (i->setcc.empty () && i->cstore.empty ())
  1067. continue;
  1068. // We're going to eliminate cstores, but for that they have to be
  1069. // there. We don't care about the setcc in this case.
  1070. if (i->cstore.empty ())
  1071. log_return (false, "bb entry cstore empty -- aborting\n");
  1072. // The goal here is to eliminate all cstores in the BBs and extend the
  1073. // ccreg usage.
  1074. if (!can_extend_ccreg_usage (*i, trace))
  1075. return false;
  1076. // If the cstore can't be removed we can keep it around as long as
  1077. // it doesn't modify the ccreg.
  1078. if (!can_remove_cstore (*i, trace)
  1079. && modified_in_p (m_ccreg, i->cstore.insn))
  1080. log_return (false, "cstore sets ccreg -- aborting\n");
  1081. }
  1082. // If there are both, inverting and non-inverting cstores, we'll have to
  1083. // invert the ccreg as a replacement for one of them.
  1084. if (cstore_count != 0 && inv_cstore_count != 0)
  1085. {
  1086. rtx_insn *i = make_inv_ccreg_insn ();
  1087. if (recog_memoized (i) < 0)
  1088. {
  1089. log_msg ("failed to match ccreg inversion insn:\n");
  1090. log_rtx (PATTERN (i));
  1091. log_return (false, "\naborting\n");
  1092. }
  1093. }
  1094. if (dominating_cstore == cstore_normal
  1095. && !try_invert_branch_condition (trace))
  1096. return false;
  1097. // Eliminate cstores in all BBs.
  1098. for (std::list<bb_entry>::const_iterator i = trace.bb_entries.begin ();
  1099. i != trace.bb_entries.end (); ++i)
  1100. {
  1101. if (i->cstore.empty ())
  1102. continue;
  1103. if (i->cstore_type == dominating_cstore)
  1104. log_msg ("removing cstore in [bb %d]\n", i->bb->index);
  1105. else
  1106. {
  1107. log_msg ("replacing cstore with ccreg inversion in [bb %d]\n",
  1108. i->bb->index);
  1109. touched_insn (
  1110. emit_insn_after (make_inv_ccreg_insn (), i->cstore.insn));
  1111. }
  1112. if (can_remove_cstore (*i, trace))
  1113. delete_insn (i->cstore.insn);
  1114. }
  1115. log_msg ("removing test insn before cbranch\n");
  1116. delete_insn (trace.setcc.insn);
  1117. return true;
  1118. }
  1119. void
  1120. sh_treg_combine::try_optimize_cbranch (rtx_insn *insn)
  1121. {
  1122. cbranch_trace trace (insn);
  1123. log_msg ("\n\n--------------------------------------\n");
  1124. log_msg ("found cbranch insn in [bb %d]:\n", trace.bb ()->index);
  1125. log_insn (insn);
  1126. trace.cbranch_type = branch_condition_type (trace.branch_condition_rtx ());
  1127. if (trace.cbranch_type == branch_if_true)
  1128. log_msg ("condition: branch if true\n");
  1129. else if (trace.cbranch_type == branch_if_false)
  1130. log_msg ("condition: branch if false\n");
  1131. else
  1132. {
  1133. log_msg ("unknown branch condition\n");
  1134. log_rtx (trace.branch_condition_rtx ());
  1135. log_return_void ("\n");
  1136. }
  1137. update_ccreg_mode (trace.branch_condition_rtx ());
  1138. // Scan the insns backwards for an insn that sets the ccreg by testing a
  1139. // reg against zero like
  1140. // (set (reg ccreg) (eq (reg) (const_int 0)))
  1141. // The testing insn could also be outside of the current basic block, but
  1142. // for now we limit the search to the current basic block.
  1143. trace.setcc = find_set_of_reg_bb (m_ccreg, prev_nonnote_insn_bb (insn));
  1144. if (trace.setcc.set_src () == NULL_RTX)
  1145. log_return_void ("could not find set of ccreg in current BB\n");
  1146. if (!is_cmp_eq_zero (trace.setcc.set_src ())
  1147. && !is_inverted_ccreg (trace.setcc.set_src ()))
  1148. {
  1149. log_msg ("unsupported set of ccreg in current BB: ");
  1150. log_rtx (trace.setcc.set_src ());
  1151. log_return_void ("\n");
  1152. }
  1153. rtx trace_reg = XEXP (trace.setcc.set_src (), 0);
  1154. log_msg ("set of ccreg:\n");
  1155. log_insn (trace.setcc.insn);
  1156. // See if we can remove the trace.setcc insn safely.
  1157. if (reg_used_between_p (m_ccreg, trace.setcc.insn, trace.cbranch_insn))
  1158. log_return_void ("ccreg used between testing insn and branch insn\n");
  1159. if (volatile_insn_p (PATTERN (trace.setcc.insn)))
  1160. {
  1161. log_msg ("can't remove insn\n");
  1162. log_insn (trace.setcc.insn);
  1163. log_return_void ("\nbecause it's volatile\n");
  1164. }
  1165. // If the ccreg is inverted before cbranch try inverting the branch
  1166. // condition.
  1167. if (is_inverted_ccreg (trace.setcc.set_src ()))
  1168. {
  1169. if (!trace.can_invert_condition ())
  1170. log_return_void ("branch condition can't be inverted - aborting\n");
  1171. if (try_invert_branch_condition (trace))
  1172. delete_insn (trace.setcc.insn);
  1173. return;
  1174. }
  1175. // Now that we have an insn which tests some reg and sets the condition
  1176. // reg before the conditional branch, try to figure out how that tested
  1177. // reg was formed, i.e. find all the insns that set the tested reg in
  1178. // some way.
  1179. // The tested reg might be set in multiple basic blocks so we need to
  1180. // check all basic blocks which can reach this current basic block.
  1181. // If the set of reg is an inverting or non-inverting store of the condition
  1182. // register, check how the ccreg value was obtained.
  1183. log_msg ("\ntracing ");
  1184. log_rtx (trace_reg);
  1185. log_msg ("\n");
  1186. // First check the basic block where the conditional branch is in.
  1187. // If we find it here there's no point in checking other BBs.
  1188. trace.bb_entries.push_front (bb_entry (trace.bb ()));
  1189. record_return_t res =
  1190. record_set_of_reg (trace_reg, prev_nonnote_insn_bb (trace.setcc.insn),
  1191. trace.bb_entries.front ());
  1192. if (res == other_set_found)
  1193. log_return_void ("other set found - aborting trace\n");
  1194. else if (res == set_not_found)
  1195. {
  1196. // It seems the initial search in the BB of the conditional branch
  1197. // didn't find anything. Now look in all predecessor BBs.
  1198. for (edge_iterator ei = ei_start (trace.bb ()->preds);
  1199. !ei_end_p (ei); ei_next (&ei))
  1200. {
  1201. edge e = ei_edge (ei);
  1202. trace.bb_entries.push_front (bb_entry (e->src));
  1203. res = record_set_of_reg (trace_reg, BB_END (e->src),
  1204. trace.bb_entries.front ());
  1205. if (res != set_found)
  1206. log_return_void ("set not found - aborting trace\n");
  1207. }
  1208. }
  1209. if (dump_file != NULL)
  1210. {
  1211. log_msg ("\ncbranch trace summary:\n");
  1212. for (std::list<bb_entry>::const_iterator i = trace.bb_entries.begin ();
  1213. i != trace.bb_entries.end (); ++i)
  1214. {
  1215. log_msg ("\n[bb %d]\n", i->bb->index);
  1216. if (!i->setcc.empty ())
  1217. {
  1218. log_rtx (i->setcc.set_rtx);
  1219. log_msg ("\n");
  1220. }
  1221. if (!i->cstore.empty ())
  1222. {
  1223. log_rtx (i->cstore.set_rtx);
  1224. log_msg ("\n");
  1225. }
  1226. for (std::vector<set_of_reg>::const_reverse_iterator j =
  1227. i->cstore_reg_reg_copies.rbegin ();
  1228. j != i->cstore_reg_reg_copies.rend (); ++j)
  1229. {
  1230. log_rtx (j->set_rtx);
  1231. log_msg ("\n");
  1232. }
  1233. }
  1234. log_rtx (trace.setcc.set_rtx);
  1235. log_msg ("\n");
  1236. log_rtx (PATTERN (trace.cbranch_insn));
  1237. log_msg ("\n");
  1238. }
  1239. // Check that we don't have any empty BBs.
  1240. // Only the BB with the cbranch may be empty.
  1241. for (std::list<bb_entry>::const_iterator i = trace.bb_entries.begin ();
  1242. i != trace.bb_entries.end (); ++i)
  1243. if (i->setcc.empty () && i->cstore.empty () && i->bb != trace.bb ())
  1244. log_return_void ("\n[bb %d] is empty - aborting.\n", i->bb->index);
  1245. // Determine the dominating cstore type
  1246. // FIXME: Try to take the probabilities of the BBs into account somehow.
  1247. int cstore_count = 0;
  1248. int inv_cstore_count = 0;
  1249. for (std::list<bb_entry>::const_iterator i = trace.bb_entries.begin ();
  1250. i != trace.bb_entries.end (); ++i)
  1251. {
  1252. if (i->cstore_type == cstore_normal)
  1253. cstore_count += 1;
  1254. else if (i->cstore_type == cstore_inverted)
  1255. inv_cstore_count += 1;
  1256. }
  1257. log_msg ("cstore count = %d inverted cstore count = %d\n",
  1258. cstore_count, inv_cstore_count);
  1259. // This puts a priority on inverting cstores.
  1260. cstore_type_t dominating_cstore = inv_cstore_count >= cstore_count
  1261. ? cstore_inverted
  1262. : cstore_normal;
  1263. if (dominating_cstore == cstore_inverted)
  1264. log_msg ("will try to eliminate inverted cstore\n");
  1265. else if (dominating_cstore == cstore_normal)
  1266. {
  1267. log_msg ("will try to eliminate normal cstore\n");
  1268. if (!trace.can_invert_condition ())
  1269. log_return_void ("branch condition can't be inverted - aborting\n");
  1270. }
  1271. else
  1272. gcc_unreachable ();
  1273. if (try_combine_comparisons (trace, cstore_count, inv_cstore_count,
  1274. dominating_cstore))
  1275. return;
  1276. try_eliminate_cstores (trace, cstore_count, inv_cstore_count,
  1277. dominating_cstore);
  1278. }
  1279. bool
  1280. sh_treg_combine::gate (function *)
  1281. {
  1282. return optimize > 0;
  1283. }
  1284. unsigned int
  1285. sh_treg_combine::execute (function *fun)
  1286. {
  1287. unsigned int ccr0 = INVALID_REGNUM;
  1288. unsigned int ccr1 = INVALID_REGNUM;
  1289. if (targetm.fixed_condition_code_regs (&ccr0, &ccr1)
  1290. && ccr0 != INVALID_REGNUM)
  1291. {
  1292. // Initially create a reg rtx with VOIDmode.
  1293. // When the first conditional branch is discovered, the mode is changed
  1294. // to the mode that is actually used by the target.
  1295. m_ccreg = gen_rtx_REG (VOIDmode, ccr0);
  1296. }
  1297. if (m_ccreg == NULL_RTX)
  1298. log_return (0, "no ccreg.\n\n");
  1299. if (STORE_FLAG_VALUE != 1)
  1300. log_return (0, "unsupported STORE_FLAG_VALUE %d", STORE_FLAG_VALUE);
  1301. log_msg ("ccreg: ");
  1302. log_rtx (m_ccreg);
  1303. log_msg (" STORE_FLAG_VALUE = %d\n", STORE_FLAG_VALUE);
  1304. // Look for basic blocks that end with a conditional branch or for
  1305. // conditional insns and try to optimize them.
  1306. basic_block bb;
  1307. FOR_EACH_BB_FN (bb, fun)
  1308. {
  1309. rtx_insn* i = BB_END (bb);
  1310. if (i == NULL || i == PREV_INSN (BB_HEAD (bb)))
  1311. continue;
  1312. // A conditional branch is always the last insn of a basic block.
  1313. if (any_condjump_p (i) && onlyjump_p (i))
  1314. {
  1315. try_optimize_cbranch (i);
  1316. i = PREV_INSN (i);
  1317. }
  1318. // Check all insns in block for conditional insns.
  1319. for (; i != NULL && i != PREV_INSN (BB_HEAD (bb)); i = PREV_INSN (i))
  1320. if (is_conditional_insn (i))
  1321. try_optimize_cbranch (i);
  1322. }
  1323. log_msg ("\n\n");
  1324. // If new insns are created and this pass is executed after all insns
  1325. // have been split already, we must split the insns we've changed or added
  1326. // ourselves here.
  1327. // FIXME: Multi-word operations (which emit multiple insns) are not handled
  1328. // properly here, since only one insn will end up in 'm_touched_insns'.
  1329. // On SH this is not a problem though.
  1330. if (m_split_insns)
  1331. for (std::vector<rtx>::const_iterator i = m_touched_insns.begin ();
  1332. i != m_touched_insns.end (); ++i)
  1333. {
  1334. log_msg ("trying to split insn:\n");
  1335. log_insn (*i);
  1336. log_msg ("\n");
  1337. try_split (PATTERN (*i), *i, 0);
  1338. }
  1339. m_touched_insns.clear ();
  1340. log_return (0, "\n\n");
  1341. }
  1342. // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  1343. // This allows instantiating the pass somewhere else without having to pull
  1344. // in a header file.
  1345. opt_pass*
  1346. make_pass_sh_treg_combine (gcc::context* ctx, bool split_insns,
  1347. const char* name)
  1348. {
  1349. return new sh_treg_combine (ctx, split_insns, name);
  1350. }