cse.c 66 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403
  1. /* Common subexpression elimination for GNU compiler.
  2. Copyright (C) 1987 Free Software Foundation, Inc.
  3. This file is part of GNU CC.
  4. GNU CC is distributed in the hope that it will be useful,
  5. but WITHOUT ANY WARRANTY. No author or distributor
  6. accepts responsibility to anyone for the consequences of using it
  7. or for whether it serves any particular purpose or works at all,
  8. unless he says so in writing. Refer to the GNU CC General Public
  9. License for full details.
  10. Everyone is granted permission to copy, modify and redistribute
  11. GNU CC, but only under the conditions described in the
  12. GNU CC General Public License. A copy of this license is
  13. supposed to have been given to you along with GNU CC so you
  14. can know your rights and responsibilities. It should be in a
  15. file named COPYING. Among other things, the copyright notice
  16. and this notice must be preserved on all copies. */
  17. #include "config.h"
  18. #include "rtl.h"
  19. #include "insn-config.h"
  20. #include "regs.h"
  21. /* The basic idea of common subexpression elimination is to go
  22. through the code, keeping a record of expressions that would
  23. have the same value at the current scan point, and replacing
  24. expressions encountered with the cheapest equivalent expression.
  25. It is too complicated to keep track of the different possibilities
  26. when control paths merge; so, at each label, we forget all that is
  27. known and start fresh. This can be described as processing each
  28. basic block separately. Note, however, that these are not quite
  29. the same as the basic blocks found by a later pass and used for
  30. data flow analysis and register packing. We do not need to start fresh
  31. after a conditional jump instruction if there is no label there.
  32. We use two data structures to record the equivalent expressions:
  33. a hash table for most expressions, and several vectors together
  34. with "quantity numbers" to record equivalent (pseudo) registers.
  35. The use of the special data structure for registers is desirable
  36. because it is faster. It is possible because registers references
  37. contain a fairly small number, the register number, taken from
  38. a contiguously allocated series, and two register references are
  39. identical if they have the same number. General expressions
  40. do not have any such thing, so the only way to retrieve the
  41. information recorded on an expression other than a register
  42. is to keep it in a hash table.
  43. Registers and "quantity numbers":
  44. At the start of each basic block, all of the (hardware and pseudo)
  45. registers used in the function are given distinct quantity
  46. numbers to indicate their contents. During scan, when the code
  47. copies one register into another, we copy the quantity number.
  48. When a register is loaded in any other way, we allocate a new
  49. quantity number to describe the value generated by this operation.
  50. `reg_qty' records what quantity a register is currently thought
  51. of as containing.
  52. We also maintain a bidirectional chain of registers for each
  53. quantity number. `qty_first_reg', `qty_last_reg',
  54. `reg_next_eqv' and `reg_prev_eqv' hold these chains.
  55. The first register in a chain is the one whose lifespan is least local.
  56. Among equals, it is the one that was seen first.
  57. We replace any equivalent register with that one.
  58. Constants and quantity numbers
  59. When a quantity has a known constant value, that value is stored
  60. in the appropriate element of qty_const. This is in addition to
  61. putting the constant in the hash table as is usual for non-regs.
  62. Regs are preferred to constants as they are to everything else,
  63. but expressions containing constants can be simplified, by fold_rtx.
  64. Other expressions:
  65. To record known equivalences among expressions in general
  66. we use a hash table called `table'. It has a fixed number of buckets
  67. that contain chains of `struct table_elt' elements for expressions.
  68. These chains connect the elements whose expressions have the same
  69. hash codes.
  70. Other chains through the same elements connect the elements which
  71. currently have equivalent values.
  72. Register references in an expression are canonicalized before hashing
  73. the expression. This is done using `reg_qty' and `qty_first_reg'.
  74. The hash code of a register reference is computed using the quantity
  75. number, not the register number.
  76. When the value of an expression changes, it is necessary to remove from the
  77. hash table not just that expression but all expressions whose values
  78. could be different as a result.
  79. 1. If the value changing is in memory, except in special cases
  80. ANYTHING referring to memory could be changed. That is because
  81. nobody knows where a pointer does not point.
  82. The function `invalidate_memory' removes what is necessary.
  83. The special cases are when the address is constant or is
  84. a constant plus a fixed register such as the frame pointer
  85. or a static chain pointer. When such addresses are stored in,
  86. we can tell exactly which other such addresses must be invalidated
  87. due to overlap. `invalidate' does this.
  88. All expressions that refer to non-constant
  89. memory addresses are also invalidated. `invalidate_memory' does this.
  90. 2. If the value changing is a register, all expressions
  91. containing references to that register, and only those,
  92. must be removed.
  93. Because searching the entire hash table for expressions that contain
  94. a register is very slow, we try to figure out when it isn't necessary.
  95. Precisely, this is necessary only when there expressions have been
  96. entered in the hash table using this register, and then the value has
  97. changed, and then another expression wants to be added to refer to
  98. teh register's new value. This sequence of circumstances is rare
  99. within any one basic block.
  100. The vectors `reg_tick' and `reg_in_table' are used to detect this case.
  101. reg_tick[i] is incremented whenever a value is stored in register i.
  102. reg_in_table[i] holds -1 if no references to register i have been
  103. entered in the table; otherwise, it contains the value reg_tick[i] had
  104. when the references were entered. If we want to enter a reference
  105. and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
  106. Until we want to enter a new entry, the mere fact that the twovectors
  107. don't match makes the entries be ignored if anyone tries to match them.
  108. Registers themselves are entered in the hash table as well as in
  109. the equivalent-register chains. However, the vectors `reg_tick'
  110. and `reg_in_table' do not apply to expressions which are simple
  111. register references. These expressions are removed from the table
  112. immediately when they become invalid, and this can be done even if
  113. we do not immediately search for all the expressions that refer to
  114. the register.
  115. A CLOBBER rtx in an instruction invalidates its operand for further
  116. reuse. A CLOBBER rtx whose operand is 0 (a null pointer)
  117. invalidates everything that resides in memory.
  118. Related expressions:
  119. Constant expressions that differ only by an additive integer
  120. are called related. When a constant expression is put in
  121. the table, the related expression with no constant term
  122. is also entered. These are made to point at each other
  123. so that it is possible to find out if there exists any
  124. register equivalent to an expression related to a given expression. */
  125. /* One plus largest register number used in this function. */
  126. static int max_reg;
  127. /* Length of vectors indexed by quantity number.
  128. We know in advance we will not need a quantity number this big. */
  129. static int max_qty;
  130. /* Next quantity number to be allocated.
  131. This is 1 + the largest number needed so far. */
  132. static int next_qty;
  133. /* Indexed by quantity number, gives the first (or last) (pseudo) register
  134. in the chain of registers that currently contain this quantity. */
  135. static int *qty_first_reg;
  136. static int *qty_last_reg;
  137. /* Indexed by quantity number, gives the rtx of the constant value of the
  138. quantity, or zero if it does not have a known value. */
  139. static rtx *qty_const;
  140. /* Value stored in CC0 by previous insn:
  141. 0 if previous insn didn't store in CC0.
  142. else 100 + (M&7)<<3 + (N&7)
  143. where M is 1, 0 or -1 if result was pos, zero or neg as signed number
  144. and N is 1, 0 or -1 if result was pos, zero or neg as unsigned number. */
  145. static int prev_insn_cc0;
  146. /* Previous actual insn. 0 if at first insn of basic block. */
  147. static rtx prev_insn;
  148. /* Index by (pseudo) register number, gives the quantity number
  149. of the register's current contents. */
  150. static int *reg_qty;
  151. /* Index by (pseudo) register number, gives the number of the next
  152. (pseudo) register in the chain of registers sharing the same value.
  153. Or -1 if this register is at the end of the chain. */
  154. static int *reg_next_eqv;
  155. /* Index by (pseudo) register number, gives the number of the previous
  156. (pseudo) register in the chain of registers sharing the same value.
  157. Or -1 if this register is at the beginning of the chain. */
  158. static int *reg_prev_eqv;
  159. /* Index by (pseudo) register number, gives the latest rtx
  160. to use to insert a ref to that register. */
  161. static rtx *reg_rtx;
  162. /* Index by (pseudo) register number, gives the number of times
  163. that register has been altered in the current basic block. */
  164. static int *reg_tick;
  165. /* Index by (pseudo) register number, gives the reg_tick value at which
  166. rtx's containing this register are valid in the hash table.
  167. If this does not equal the current reg_tick value, such expressions
  168. existing in the hash table are invalid.
  169. If this is -1, no expressions containing this register have been
  170. entered in the table. */
  171. static int *reg_in_table;
  172. /* Two vectors of max_reg ints:
  173. one containing all -1's; in the other, element i contains i.
  174. These are used to initialize various other vectors fast. */
  175. static int *all_minus_one;
  176. static int *consec_ints;
  177. /* Indexed by hardware register number, contains nonzero
  178. for registers that may be clobbered by subroutine calls
  179. (and also for the fixed-use registers,
  180. which we must check for and refrain from invalidating). */
  181. static char call_clobbers_reg[] = CALL_USED_REGISTERS;
  182. /* UID of insn that ends the basic block currently being cse-processed. */
  183. static int cse_basic_block_end;
  184. /* Nonzero if cse has altered conditional jump insns
  185. in such a way that jump optimization should be redone. */
  186. static int cse_jumps_altered;
  187. /* canon_hash stores 1 in do_not_record
  188. if it notices a reference to CC0, CC1 or PC. */
  189. static int do_not_record;
  190. /* canon_hash stores 1 in hash_arg_in_memory
  191. if it notices a reference to memory within the expression being hashed. */
  192. static int hash_arg_in_memory;
  193. /* The hash table contains buckets which are chains of `struct table_elt's,
  194. each recording one expression's information.
  195. That expression is in the `exp' field.
  196. Those elements with the same hash code are chained in both directions
  197. through the `next_same_hash' and `prev_same_hash' fields.
  198. Each set of expressions with equivalent values
  199. are on a two-way chain through the `next_same_value'
  200. and `prev_same_value' fields, and all point with
  201. the `first_same_value' field at the first element in
  202. that chain. The chain is in order of increasing cost.
  203. Each element's cost value is in its `cost' field.
  204. The `in_memory' field is nonzero for elements that
  205. involve any reference to memory. These elements are removed
  206. whenever a write is done to an unidentified location in memory.
  207. To be safe, we assume that a memory address is unidentified unless
  208. the address is either a symbol constant or a constant plus
  209. the frame pointer or argument pointer.
  210. The `related_value' field is used to connect related expressions
  211. (that differ by adding an integer).
  212. The related expressions are chained in a circular fashion.
  213. `related_value' is zero for expressions for which this
  214. chain is not useful. */
  215. struct table_elt
  216. {
  217. rtx exp;
  218. struct table_elt *next_same_hash;
  219. struct table_elt *prev_same_hash;
  220. struct table_elt *next_same_value;
  221. struct table_elt *prev_same_value;
  222. struct table_elt *first_same_value;
  223. struct table_elt *related_value;
  224. int cost;
  225. char in_memory;
  226. };
  227. #define HASH(x) (canon_hash (x) % NBUCKETS)
  228. /* We don't want a lot of buckets, because we rarely have very many
  229. things stored in the hash table, and a lot of buckets slows
  230. down a lot of loops that happen frequently. */
  231. #define NBUCKETS 31
  232. static struct table_elt *table[NBUCKETS];
  233. /* Chain of `struct table_elt's made so far for this function
  234. but currently removed from the table. */
  235. static struct table_elt *free_element_chain;
  236. /* Number of `struct table_elt' structures made so far for this function. */
  237. static int n_elements_made;
  238. /* Maximum value `n_elements_made' has had so far in this compilation
  239. for functions previously processed. */
  240. static int max_elements_made;
  241. /* Bits describing what kind of values in memory must be invalidated
  242. for a particular instruction. If all three bits are zero,
  243. no memory refs need to be invalidated. Each bit is more powerful
  244. than the preceding ones, and if a bit is set then the preceding
  245. bits are also set.
  246. Here is how the bits are set.
  247. Writing at a fixed address invalidates only variable addresses,
  248. writing in a structure element at variable address
  249. invalidates all but scalar variables,
  250. and writing in anything else at variable address invalidates everything. */
  251. struct write_data
  252. {
  253. int var : 1; /* Invalidate variable addresses. */
  254. int nonscalar : 1; /* Invalidate all but scalar variables. */
  255. int all : 1; /* Invalidate all memory refs. */
  256. };
  257. static struct table_elt *lookup ();
  258. static void free_element ();
  259. static void remove_invalid_refs ();
  260. static int exp_equiv_p ();
  261. int refers_to_p ();
  262. int refers_to_mem_p ();
  263. static void invalidate_from_clobbers ();
  264. static int safe_hash ();
  265. static int get_integer_term ();
  266. static rtx get_related_value ();
  267. static void note_mem_written ();
  268. /* Return an estimate of the cost of computing rtx X.
  269. The only use of this is to compare the costs of two expressions
  270. to decide whether to replace one with the other. */
  271. static int
  272. rtx_cost (x)
  273. rtx x;
  274. {
  275. register int i;
  276. register RTX_CODE code = GET_CODE (x);
  277. register char *fmt;
  278. register int total;
  279. switch (code)
  280. {
  281. case REG:
  282. return 1;
  283. case SUBREG:
  284. return 2;
  285. CONST_COSTS (x, code);
  286. }
  287. total = 2;
  288. /* Compare the elements. If any pair of corresponding elements
  289. fail to match, return 0 for the whole things. */
  290. fmt = GET_RTX_FORMAT (code);
  291. for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  292. if (fmt[i] == 'e')
  293. total += rtx_cost (XEXP (x, i));
  294. return total;
  295. }
  296. /* Clear the hash table and initialize each register with its own quantity,
  297. for a new basic block. */
  298. static void
  299. new_basic_block ()
  300. {
  301. register int i;
  302. register int vecsize = max_reg * sizeof (rtx);
  303. next_qty = max_reg;
  304. bzero (reg_rtx, vecsize);
  305. bzero (reg_tick, vecsize);
  306. bcopy (all_minus_one, reg_in_table, vecsize);
  307. bcopy (all_minus_one, reg_next_eqv, vecsize);
  308. bcopy (all_minus_one, reg_prev_eqv, vecsize);
  309. bcopy (consec_ints, reg_qty, vecsize);
  310. for (i = 0; i < max_qty; i++)
  311. {
  312. qty_first_reg[i] = i;
  313. qty_last_reg[i] = i;
  314. qty_const[i] = 0;
  315. }
  316. for (i = 0; i < NBUCKETS; i++)
  317. {
  318. register struct table_elt *this, *next;
  319. for (this = table[i]; this; this = next)
  320. {
  321. next = this->next_same_hash;
  322. free_element (this);
  323. }
  324. }
  325. bzero (table, sizeof table);
  326. prev_insn_cc0 = 0;
  327. prev_insn = 0;
  328. }
  329. /* Say that register REG contains a quantity not in any register before. */
  330. static void
  331. make_new_qty (reg)
  332. register int reg;
  333. {
  334. register int q;
  335. q = reg_qty[reg] = next_qty++;
  336. qty_first_reg[q] = reg;
  337. qty_last_reg[q] = reg;
  338. }
  339. /* Make reg NEW equivalent to reg OLD.
  340. OLD is not changing; NEW is. */
  341. static void
  342. make_regs_eqv (new, old)
  343. register int new, old;
  344. {
  345. register int lastr, firstr;
  346. register int q;
  347. q = reg_qty[new] = reg_qty[old];
  348. firstr = qty_first_reg[q];
  349. /* Prefer pseudo regs to hard regs with the same value.
  350. Among pseudos, if NEW will live longer than any other reg of the same qty,
  351. and that is beyond the current basic block,
  352. make it the new canonical replacement for this qty. */
  353. if (new >= FIRST_PSEUDO_REGISTER
  354. && (firstr < FIRST_PSEUDO_REGISTER
  355. || ((regno_last_uid[new] > cse_basic_block_end)
  356. &&
  357. (regno_last_uid[new] > regno_last_uid[firstr]))))
  358. {
  359. lastr = qty_first_reg[q];
  360. reg_prev_eqv[lastr] = new;
  361. reg_next_eqv[new] = lastr;
  362. reg_prev_eqv[new] = -1;
  363. qty_first_reg[q] = new;
  364. }
  365. else
  366. {
  367. lastr = qty_last_reg[q];
  368. reg_next_eqv[lastr] = new;
  369. reg_prev_eqv[new] = lastr;
  370. reg_next_eqv[new] = -1;
  371. qty_last_reg[q] = new;
  372. }
  373. }
  374. /* Discard the records of what is in register REG. */
  375. static void
  376. reg_invalidate (reg)
  377. register int reg;
  378. {
  379. register int n = reg_next_eqv[reg];
  380. register int p = reg_prev_eqv[reg];
  381. register int q = reg_qty[reg];
  382. reg_tick[reg]++;
  383. if (q == reg)
  384. return; /* Save time if already invalid */
  385. if (n != -1)
  386. reg_prev_eqv[n] = p;
  387. else
  388. qty_last_reg[q] = p;
  389. if (p != -1)
  390. reg_next_eqv[p] = n;
  391. else
  392. qty_first_reg[q] = n;
  393. reg_qty[reg] = reg;
  394. qty_first_reg[reg] = reg;
  395. qty_last_reg[reg] = reg;
  396. reg_next_eqv[reg] = -1;
  397. reg_prev_eqv[reg] = -1;
  398. }
  399. /* Remove any invalid expressions from the hash table
  400. that refer to any of the registers contained in expression X.
  401. Make sure that newly inserted references to those registers
  402. as subexpressions will be considered valid.
  403. mention_regs is not called when a register itself
  404. is being stored in the table. */
  405. static void
  406. mention_regs (x)
  407. rtx x;
  408. {
  409. register RTX_CODE code = GET_CODE (x);
  410. register int i;
  411. register char *fmt;
  412. if (code == REG)
  413. {
  414. register int regno = REGNO (x);
  415. reg_rtx[regno] = x;
  416. if (reg_in_table[regno] >= 0 && reg_in_table[regno] != reg_tick[regno])
  417. remove_invalid_refs (regno);
  418. reg_in_table[regno] = reg_tick[regno];
  419. return;
  420. }
  421. fmt = GET_RTX_FORMAT (code);
  422. for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  423. if (fmt[i] == 'e')
  424. mention_regs (XEXP (x, i));
  425. }
  426. /* Update the register quantities for inserting X into the hash table
  427. with a value equivalent to CLASSP.
  428. If MODIFIED is nonzero, X is a destination; it is being modified.
  429. Note that reg_invalidate should be called on a register
  430. before insert_regs is done on that register with MODIFIED != 0. */
  431. static int
  432. insert_regs (x, classp, modified)
  433. rtx x;
  434. struct table_elt *classp;
  435. int modified;
  436. {
  437. if (GET_CODE (x) == REG)
  438. {
  439. register int regno = REGNO (x);
  440. reg_rtx[regno] = x;
  441. if (modified || reg_qty[regno] == regno)
  442. {
  443. if (classp && GET_CODE (classp->exp) == REG)
  444. {
  445. make_regs_eqv (regno, REGNO (classp->exp));
  446. /* Make sure reg_rtx is set up even for regs
  447. not explicitly set (such as function value). */
  448. reg_rtx[REGNO (classp->exp)] = classp->exp;
  449. }
  450. else
  451. make_new_qty (regno);
  452. return 1;
  453. }
  454. }
  455. else
  456. mention_regs (x);
  457. return 0;
  458. }
  459. /* Look in or update the hash table. */
  460. /* Put the element ELT on the list of free elements. */
  461. static void
  462. free_element (elt)
  463. struct table_elt *elt;
  464. {
  465. elt->next_same_hash = free_element_chain;
  466. free_element_chain = elt;
  467. }
  468. /* Return an element that is free for use. */
  469. static struct table_elt *
  470. get_element ()
  471. {
  472. struct table_elt *elt = free_element_chain;
  473. if (elt)
  474. {
  475. free_element_chain = elt->next_same_hash;
  476. return elt;
  477. }
  478. n_elements_made++;
  479. return (struct table_elt *) oballoc (sizeof (struct table_elt));
  480. }
  481. /* Remove table element ELT from use in the table.
  482. HASH is its hash code, made using the HASH macro.
  483. It's an argument because often that is known in advance
  484. and we save much time not recomputing it. */
  485. static void
  486. remove (elt, hash)
  487. register struct table_elt *elt;
  488. int hash;
  489. {
  490. if (elt == 0)
  491. return;
  492. /* Mark this element as removed. See cse_insn. */
  493. elt->first_same_value = 0;
  494. /* Remove the table element from its equivalence class. */
  495. {
  496. register struct table_elt *prev = elt->prev_same_value;
  497. register struct table_elt *next = elt->next_same_value;
  498. if (next) next->prev_same_value = prev;
  499. if (prev)
  500. prev->next_same_value = next;
  501. else
  502. {
  503. register struct table_elt *newfirst = next;
  504. while (next)
  505. {
  506. next->first_same_value = newfirst;
  507. next = next->next_same_value;
  508. }
  509. }
  510. }
  511. /* Remove the table element from its hash bucket. */
  512. {
  513. register struct table_elt *prev = elt->prev_same_hash;
  514. register struct table_elt *next = elt->next_same_hash;
  515. if (next) next->prev_same_hash = prev;
  516. if (prev)
  517. prev->next_same_hash = next;
  518. else
  519. table[hash] = next;
  520. }
  521. /* Remove the table element from its related-value circular chain. */
  522. if (elt->related_value != 0 && elt->related_value != elt)
  523. {
  524. register struct table_elt *p = elt->related_value;
  525. while (p->related_value != elt)
  526. p = p->related_value;
  527. p->related_value = elt->related_value;
  528. if (p->related_value == p)
  529. p->related_value = 0;
  530. }
  531. free_element (elt);
  532. }
  533. /* Look up X in the hash table and return its table element,
  534. or 0 if X is not in the table.
  535. Here we are satisfied to find an expression equivalent to X. */
  536. static struct table_elt *
  537. lookup (x, hash)
  538. rtx x;
  539. int hash;
  540. {
  541. register struct table_elt *p;
  542. for (p = table[hash]; p; p = p->next_same_hash)
  543. if (x == p->exp || exp_equiv_p (x, p->exp, 1))
  544. return p;
  545. return 0;
  546. }
  547. /* Look for an expression equivalent to X and of the form (CODE Y).
  548. If one is found, return Y. */
  549. static rtx
  550. lookup_as_function (x, code)
  551. rtx x;
  552. enum rtx_code code;
  553. {
  554. register struct table_elt *p = lookup (x, safe_hash (x) % NBUCKETS);
  555. if (p == 0)
  556. return 0;
  557. for (p = p->first_same_value; p; p = p->next_same_value)
  558. {
  559. if (GET_CODE (p->exp) == code
  560. /* Make sure this is a valid entry in the table. */
  561. && (exp_equiv_p (XEXP (p->exp, 0), XEXP (p->exp, 0))))
  562. return XEXP (p->exp, 0);
  563. }
  564. return 0;
  565. }
  566. /* Insert X in the hash table, assuming HASH is its hash code
  567. and CLASSP is the current first element of the class it should go in
  568. (or 0 if a new class should be made).
  569. It is inserted at the proper position to keep the class in
  570. the order cheapest first.
  571. For elements of equal cheapness, the most recent one
  572. goes in front, except that the first element in the list
  573. remains first unless a cheaper element is added.
  574. The in_memory field in the hash table element is set to 0.
  575. The caller must set it nonzero if appropriate.
  576. You should call insert_regs (X, CLASSP, MODIFY) before calling here,
  577. and if insert_regs returns a nonzero value
  578. you must then recompute its hash code before calling here.
  579. If necessary, update table showing constant values of quantities. */
  580. #define CHEAPER(X,Y) \
  581. (((X)->cost < (Y)->cost) || \
  582. (GET_CODE ((X)->exp) == REG && GET_CODE ((Y)->exp) == REG \
  583. && (regno_last_uid[REGNO ((X)->exp)] \
  584. > cse_basic_block_end) \
  585. && (regno_last_uid[REGNO ((X)->exp)] \
  586. > regno_last_uid[REGNO ((Y)->exp)])))
  587. static struct table_elt *
  588. insert (x, classp, hash)
  589. register rtx x;
  590. register struct table_elt *classp;
  591. int hash;
  592. {
  593. register struct table_elt *elt;
  594. /* Put an element for X into the right hash bucket. */
  595. elt = get_element ();
  596. elt->exp = x;
  597. elt->cost = rtx_cost (x);
  598. elt->next_same_value = 0;
  599. elt->prev_same_value = 0;
  600. elt->next_same_hash = table[hash];
  601. elt->prev_same_hash = 0;
  602. elt->related_value = 0;
  603. elt->in_memory = 0;
  604. if (table[hash])
  605. table[hash]->prev_same_hash = elt;
  606. table[hash] = elt;
  607. /* Put it into the proper value-class. */
  608. if (classp)
  609. {
  610. if (CHEAPER (elt, classp))
  611. /** Insert at the head of the class */
  612. {
  613. register struct table_elt *p;
  614. elt->next_same_value = classp;
  615. classp->prev_same_value = elt;
  616. elt->first_same_value = elt;
  617. for (p = classp; p; p = p->next_same_value)
  618. p->first_same_value = elt;
  619. }
  620. else
  621. {
  622. /* Insert not at head of the class. */
  623. /* Put it after the last element cheaper than X. */
  624. register struct table_elt *p, *next;
  625. for (p = classp; (next = p->next_same_value) && CHEAPER (p, elt);
  626. p = next);
  627. elt->next_same_value = next;
  628. if (next)
  629. next->prev_same_value = elt;
  630. elt->prev_same_value = p;
  631. p->next_same_value = elt;
  632. elt->first_same_value = classp;
  633. }
  634. }
  635. else
  636. elt->first_same_value = elt;
  637. if (GET_CODE (x) == CONST_INT)
  638. {
  639. if (GET_CODE (elt->first_same_value->exp) == REG)
  640. qty_const[reg_qty[REGNO (elt->first_same_value->exp)]] = x;
  641. }
  642. if (GET_CODE (x) == REG)
  643. {
  644. if (elt->next_same_value != 0
  645. && GET_CODE (elt->next_same_value->exp) == CONST_INT)
  646. qty_const[reg_qty[REGNO (x)]] = elt->next_same_value->exp;
  647. if (GET_CODE (elt->first_same_value->exp) == CONST_INT)
  648. qty_const[reg_qty[REGNO (x)]] = elt->first_same_value->exp;
  649. }
  650. /* If this is a constant with symbolic value,
  651. and it has a term with an explicit integer value,
  652. link it up with related expressions. */
  653. if (GET_CODE (x) == CONST)
  654. {
  655. rtx subexp = get_related_value (x);
  656. int subhash;
  657. struct table_elt *subelt;
  658. if (subexp != 0)
  659. {
  660. /* Get the integer-free subexpression in the hash table. */
  661. subhash = safe_hash (subexp) % NBUCKETS;
  662. subelt = lookup (subexp, subhash);
  663. if (subelt == 0)
  664. subelt = insert (subexp, 0, subhash);
  665. /* Initialize SUBELT's circular chain if it has none. */
  666. if (subelt->related_value == 0)
  667. subelt->related_value = subelt;
  668. /* Put new ELT into SUBELT's circular chain. */
  669. elt->related_value = subelt->related_value;
  670. subelt->related_value = elt;
  671. }
  672. }
  673. return elt;
  674. }
  675. /* Remove from the hash table all expressions that
  676. refer to expression X. X is either a register
  677. or a memory reference with nonvarying address
  678. (because, when a memory reference with a varying address is stored in,
  679. all memory references are removed by invalidate_memory
  680. so specific invalidation is superfluous).
  681. A nonvarying address may be just a register or just
  682. a symbol reference, or it may be either of those plus
  683. a numeric offset. */
  684. static void
  685. invalidate (x)
  686. rtx x;
  687. {
  688. register int i;
  689. register struct table_elt *p;
  690. register rtx base;
  691. register int start, end;
  692. /* If X is a register, dependencies on its contents
  693. are recorded through the qty number mechanism.
  694. Just change the qty number of the register,
  695. mark it as invalid for expressions that refer to it,
  696. and remove it itself. */
  697. if (GET_CODE (x) == REG)
  698. {
  699. register int hash = HASH (x);
  700. reg_invalidate (REGNO (x));
  701. remove (lookup (x, hash), hash);
  702. return;
  703. }
  704. /* X is not a register; it must be a memory reference with
  705. a nonvarying address. Remove all hash table elements
  706. that refer to overlapping pieces of memory. */
  707. if (GET_CODE (x) != MEM)
  708. abort ();
  709. base = XEXP (x, 0);
  710. start = 0;
  711. if (GET_CODE (base) == CONST)
  712. base = XEXP (base, 0);
  713. if (GET_CODE (base) == PLUS
  714. && GET_CODE (XEXP (base, 1)) == CONST_INT)
  715. {
  716. start = INTVAL (XEXP (base, 1));
  717. base = XEXP (base, 0);
  718. }
  719. end = start + GET_MODE_SIZE (GET_MODE (x));
  720. for (i = 0; i < NBUCKETS; i++)
  721. {
  722. register struct table_elt *next;
  723. for (p = table[i]; p; p = next)
  724. {
  725. next = p->next_same_hash;
  726. if (refers_to_mem_p (p->exp, base, start, end))
  727. remove (p, i);
  728. }
  729. }
  730. }
  731. /* Remove all expressions that refer to register REGNO,
  732. since they are already invalid, and we are about to
  733. mark that register valid again and don't want the old
  734. expressions to reappear as valid. */
  735. static void
  736. remove_invalid_refs (regno)
  737. int regno;
  738. {
  739. register int i;
  740. register struct table_elt *p, *next;
  741. register rtx x = reg_rtx[regno];
  742. for (i = 0; i < NBUCKETS; i++)
  743. for (p = table[i]; p; p = next)
  744. {
  745. next = p->next_same_hash;
  746. if (GET_CODE (p->exp) != REG && refers_to_p (p->exp, x))
  747. remove (p, i);
  748. }
  749. }
  750. /* Remove from the hash table all expressions that reference memory,
  751. or some of them as specified by *WRITES. */
  752. static void
  753. invalidate_memory (writes)
  754. struct write_data *writes;
  755. {
  756. register int i;
  757. register struct table_elt *p, *next;
  758. int all = writes->all;
  759. int nonscalar = writes->nonscalar;
  760. for (i = 0; i < NBUCKETS; i++)
  761. for (p = table[i]; p; p = next)
  762. {
  763. next = p->next_same_hash;
  764. if (p->in_memory
  765. && (all
  766. || (nonscalar && p->exp->in_struct)
  767. || rtx_addr_varies_p (p->exp)))
  768. remove (p, i);
  769. }
  770. }
  771. /* Return the value of the integer term in X, if one is apparent;
  772. otherwise return 0.
  773. We do not check extremely carefully for the presence of integer terms
  774. but rather consider only the cases that `insert' notices
  775. for the `related_value' field. */
  776. static int
  777. get_integer_term (x)
  778. rtx x;
  779. {
  780. if (GET_CODE (x) == CONST)
  781. x = XEXP (x, 0);
  782. if (GET_CODE (x) == MINUS
  783. && GET_CODE (XEXP (x, 1)) == CONST_INT)
  784. return - INTVAL (XEXP (x, 1));
  785. if (GET_CODE (x) != PLUS)
  786. return 0;
  787. if (GET_CODE (XEXP (x, 0)) == CONST_INT)
  788. return INTVAL (XEXP (x, 0));
  789. if (GET_CODE (XEXP (x, 1)) == CONST_INT)
  790. return INTVAL (XEXP (x, 1));
  791. return 0;
  792. }
  793. static rtx
  794. get_related_value (x)
  795. rtx x;
  796. {
  797. if (GET_CODE (x) != CONST)
  798. return 0;
  799. x = XEXP (x, 0);
  800. if (GET_CODE (x) == PLUS)
  801. {
  802. if (GET_CODE (XEXP (x, 0)) == CONST_INT)
  803. return XEXP (x, 1);
  804. if (GET_CODE (XEXP (x, 1)) == CONST_INT)
  805. return XEXP (x, 0);
  806. }
  807. else if (GET_CODE (x) == MINUS
  808. && GET_CODE (XEXP (x, 1)) == CONST_INT)
  809. return XEXP (x, 0);
  810. return 0;
  811. }
  812. /* Given an expression X of type CONST,
  813. and ELT which is its table entry (or 0 if it
  814. is not in the hash table),
  815. return an alternate expression for X as a register plus integer.
  816. If none can be found or it would not be a valid address, return 0. */
  817. static rtx
  818. use_related_value (x, elt)
  819. rtx x;
  820. struct table_elt *elt;
  821. {
  822. register struct table_elt *relt = 0;
  823. register struct table_elt *p;
  824. int offset;
  825. rtx addr;
  826. /* First, is there anything related known?
  827. If we have a table element, we can tell from that.
  828. Otherwise, must look it up. */
  829. if (elt != 0 && elt->related_value != 0)
  830. relt = elt;
  831. else if (elt == 0 && GET_CODE (x) == CONST)
  832. {
  833. rtx subexp = get_related_value (x);
  834. if (subexp != 0)
  835. relt = lookup (subexp, safe_hash (subexp) % NBUCKETS);
  836. }
  837. if (relt == 0)
  838. return 0;
  839. /* Search all related table entries for one that has an
  840. equivalent register. */
  841. p = relt;
  842. while (1)
  843. {
  844. if (p->first_same_value != 0
  845. && GET_CODE (p->first_same_value->exp) == REG)
  846. break;
  847. p = p->related_value;
  848. /* We went all the way around, so there is nothing to be found.
  849. Return failure. */
  850. if (p == relt)
  851. return 0;
  852. }
  853. offset = (get_integer_term (x) - get_integer_term (p->exp));
  854. if (offset == 0)
  855. abort ();
  856. addr = plus_constant (p->first_same_value->exp, offset);
  857. GO_IF_LEGITIMATE_ADDRESS (QImode, addr, win1);
  858. return 0;
  859. win1:
  860. return addr;
  861. }
  862. /* Hash an rtx. We are careful to make sure the value is never negative.
  863. Equivalent registers hash identically.
  864. Store 1 in do_not_record if any subexpression is volatile.
  865. Store 1 in hash_arg_in_memory if there is a use of MEM
  866. anywhere within X.
  867. Note that cse_insn knows that the hash code of a MEM expression
  868. is just (int) MEM plus the hash code of the address.
  869. It also knows it can use HASHREG to get the hash code of (REG n). */
  870. #define HASHBITS 16
  871. #define HASHREG(RTX) \
  872. ((((int) REG << 7) + reg_qty[REGNO (RTX)]) % NBUCKETS)
  873. static int
  874. canon_hash (x)
  875. rtx x;
  876. {
  877. register int i;
  878. register int hash = 0;
  879. register RTX_CODE code;
  880. register char *fmt;
  881. /* repeat is used to turn tail-recursion into iteration. */
  882. repeat:
  883. code = GET_CODE (x);
  884. switch (code)
  885. {
  886. case REG:
  887. {
  888. /* We do not invalidate anything on pushing or popping
  889. because they cannot change anything but the stack pointer;
  890. but that means we must consider the stack pointer volatile
  891. since it can be changed "mysteriously".
  892. We consider the function value register volatile
  893. because it can be referred to in multi-word modes.
  894. If it were live across basic block boundaries, that
  895. could cause trouble in register allocation.
  896. The only way this can happen is if it were substituted
  897. as a cse. This way we prevent that. */
  898. register int regno = REGNO (x);
  899. if (regno == STACK_POINTER_REGNUM
  900. || regno == FUNCTION_VALUE_REGNUM)
  901. {
  902. do_not_record = 1;
  903. return 0;
  904. }
  905. return hash + ((int) REG << 7) + reg_qty[regno];
  906. }
  907. /* Assume there is only one rtx object for any given label. */
  908. case LABEL_REF:
  909. return hash + ((int) LABEL_REF << 7) + (int) XEXP (x, 0);
  910. case SYMBOL_REF:
  911. return hash + ((int) SYMBOL_REF << 7) + (int) XEXP (x, 0);
  912. case MEM:
  913. hash_arg_in_memory = 1;
  914. /* Now that we have already found this special case,
  915. might as well speed it up as much as possible. */
  916. hash += (int) MEM;
  917. x = XEXP (x, 0);
  918. goto repeat;
  919. case VOLATILE:
  920. do_not_record = 1;
  921. return 0;
  922. case PRE_DEC:
  923. case PRE_INC:
  924. case POST_DEC:
  925. case POST_INC:
  926. case PC:
  927. case CC0:
  928. do_not_record = 1;
  929. return 0;
  930. }
  931. i = GET_RTX_LENGTH (code) - 1;
  932. hash += (int) code + (int) GET_MODE (x);
  933. fmt = GET_RTX_FORMAT (code);
  934. for (; i >= 0; i--)
  935. {
  936. if (fmt[i] == 'e')
  937. {
  938. /* If we are about to do the last recursive call
  939. needed at this level, change it into iteration.
  940. This function is called enough to be worth it. */
  941. if (i == 0)
  942. {
  943. x = XEXP (x, 0);
  944. goto repeat;
  945. }
  946. hash += canon_hash (XEXP (x, i));
  947. }
  948. else
  949. {
  950. register int tem = XINT (x, i);
  951. hash += ((1 << HASHBITS) - 1) & (tem + tem >> HASHBITS);
  952. }
  953. }
  954. return hash;
  955. }
  956. /* Like canon_hash but with no side effects. */
  957. static int
  958. safe_hash (x)
  959. rtx x;
  960. {
  961. int save_do_not_record = do_not_record;
  962. int save_hash_arg_in_memory = hash_arg_in_memory;
  963. int hash = canon_hash (x);
  964. hash_arg_in_memory = save_hash_arg_in_memory;
  965. do_not_record = save_do_not_record;
  966. return hash;
  967. }
  968. /* Return 1 iff X and Y would canonicalize into the same thing,
  969. without actually constructing the canonicalization of either one.
  970. If VALIDATE is nonzero,
  971. we assume X is an expression being processed from the rtl
  972. and Y was found in the hash table. We check register refs
  973. in Y for being marked as valid. */
  974. static int
  975. exp_equiv_p (x, y, validate)
  976. rtx x, y;
  977. int validate;
  978. {
  979. register int i;
  980. register int hash = 0;
  981. register RTX_CODE code = GET_CODE (x);
  982. register char *fmt;
  983. /* An expression is usually equivalent to itself,
  984. but not if it's a register that's invalid. */
  985. if (x == y)
  986. return (code != REG
  987. || !validate
  988. || reg_in_table[REGNO (y)] == reg_tick[REGNO (y)]);
  989. if (code != GET_CODE (y))
  990. return 0;
  991. if (code == REG)
  992. return (reg_qty[REGNO (x)] == reg_qty[REGNO (y)]
  993. && (!validate
  994. || reg_in_table[REGNO (y)] == reg_tick[REGNO (y)]));
  995. /* Assume there is only one rtx object to refer
  996. to any given label.
  997. We already know that X and Y are not the same object
  998. so they must differ. */
  999. if (code == LABEL_REF || code == SYMBOL_REF)
  1000. return XEXP (x, 0) == XEXP (y, 0);
  1001. /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
  1002. if (GET_MODE (x) != GET_MODE (y))
  1003. return 0;
  1004. /* Compare the elements. If any pair of corresponding elements
  1005. fail to match, return 0 for the whole things. */
  1006. fmt = GET_RTX_FORMAT (code);
  1007. for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1008. {
  1009. if (fmt[i] == 'e')
  1010. {
  1011. if (exp_equiv_p (XEXP (x, i), XEXP (y, i), validate) == 0)
  1012. return 0;
  1013. }
  1014. else
  1015. {
  1016. if (XINT (x, i) != XINT (y, i))
  1017. return 0;
  1018. }
  1019. }
  1020. return 1;
  1021. }
  1022. /* Return 1 iff any subexpression of X matches Y.
  1023. Here we do not require that X or Y be valid (for registers referred to)
  1024. for being in the hash table. */
  1025. int
  1026. refers_to_p (x, y)
  1027. rtx x, y;
  1028. {
  1029. register int i;
  1030. register RTX_CODE code;
  1031. register char *fmt;
  1032. repeat:
  1033. if (x == y)
  1034. return 1;
  1035. code = GET_CODE (x);
  1036. /* If X as a whole has the same code as Y, they may match.
  1037. If so, return 1. */
  1038. if (code == GET_CODE (y))
  1039. {
  1040. if (exp_equiv_p (x, y, 0))
  1041. return 1;
  1042. }
  1043. /* X does not match, so try its subexpressions. */
  1044. fmt = GET_RTX_FORMAT (code);
  1045. for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1046. if (fmt[i] == 'e')
  1047. if (i == 0)
  1048. {
  1049. x = XEXP (x, 0);
  1050. goto repeat;
  1051. }
  1052. else
  1053. if (refers_to_p (XEXP (x, i), y))
  1054. return 1;
  1055. return 0;
  1056. }
  1057. /* Return 1 iff any subexpression of X refers to memory
  1058. at an address of REG plus some offset
  1059. such that any of the bytes' offsets fall between START (inclusive)
  1060. and END (exclusive).
  1061. The value is undefined if X is a varying address.
  1062. This function is not used in such cases. */
  1063. int
  1064. refers_to_mem_p (x, reg, start, end)
  1065. rtx x, reg;
  1066. int start, end;
  1067. {
  1068. register int i;
  1069. register RTX_CODE code;
  1070. register char *fmt;
  1071. repeat:
  1072. code = GET_CODE (x);
  1073. if (code == MEM)
  1074. {
  1075. register rtx addr = XEXP (x, 0); /* Get the address. */
  1076. int myend;
  1077. if (GET_CODE (addr) == CONST)
  1078. addr = XEXP (addr, 0);
  1079. if (addr == reg)
  1080. i = 0;
  1081. else if (GET_CODE (addr) == PLUS
  1082. && XEXP (addr, 0) == reg
  1083. && GET_CODE (XEXP (addr, 1)) == CONST_INT)
  1084. i = INTVAL (XEXP (addr, 1));
  1085. else
  1086. return 0;
  1087. myend = i + GET_MODE_SIZE (GET_MODE (x));
  1088. return myend > start && i < end;
  1089. }
  1090. /* X does not match, so try its subexpressions. */
  1091. fmt = GET_RTX_FORMAT (code);
  1092. for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1093. if (fmt[i] == 'e')
  1094. if (i == 0)
  1095. {
  1096. x = XEXP (x, 0);
  1097. goto repeat;
  1098. }
  1099. else
  1100. if (refers_to_mem_p (XEXP (x, i), reg, start, end))
  1101. return 1;
  1102. return 0;
  1103. }
  1104. /* Canonicalize an expression:
  1105. replace each register reference inside it
  1106. with the "oldest" equivalent register. */
  1107. static rtx
  1108. canon_reg (x)
  1109. rtx x;
  1110. {
  1111. register int i;
  1112. register RTX_CODE code = GET_CODE (x);
  1113. register char *fmt;
  1114. if (code == REG)
  1115. {
  1116. register int qty = reg_qty[REGNO (x)];
  1117. register rtx new = reg_rtx[qty_first_reg[qty]];
  1118. return new ? new : x;
  1119. }
  1120. fmt = GET_RTX_FORMAT (code);
  1121. for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1122. {
  1123. if (fmt[i] == 'E')
  1124. abort ();
  1125. if (fmt[i] == 'e')
  1126. XEXP (x, i) = canon_reg (XEXP (x, i));
  1127. }
  1128. return x;
  1129. }
  1130. /* If X is a nontrivial arithmetic operation on an argument
  1131. for which a constant value can be determined, return
  1132. the result of operating on that value, as a constant.
  1133. Otherwise, return X, possibly with one or more operands
  1134. modified by recursive calls to this function. */
  1135. static rtx
  1136. fold_rtx (x)
  1137. rtx x;
  1138. {
  1139. register RTX_CODE code = GET_CODE (x);
  1140. register char *fmt;
  1141. register int i, val;
  1142. rtx const_arg[2];
  1143. const_arg[0] = 0;
  1144. const_arg[1] = 0;
  1145. /* Try folding our operands.
  1146. Then see which ones have constant values known. */
  1147. fmt = GET_RTX_FORMAT (code);
  1148. for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1149. if (fmt[i] == 'e')
  1150. {
  1151. register rtx tem = fold_rtx (XEXP (x, i));
  1152. XEXP (x, i) = tem;
  1153. if (i < 2)
  1154. {
  1155. if (GET_CODE (tem) == CONST_INT)
  1156. const_arg[i] = tem;
  1157. else if (GET_CODE (tem) == REG
  1158. && qty_const[reg_qty[REGNO (tem)]] != 0)
  1159. const_arg[i] = qty_const[reg_qty[REGNO (tem)]];
  1160. }
  1161. }
  1162. /* Now decode the kind of rtx X is
  1163. and either return X (if nothing can be done)
  1164. or store a value in VAL and drop through
  1165. (to return a CONST_INT for the integer VAL). */
  1166. if (GET_RTX_LENGTH (code) == 1)
  1167. {
  1168. register int arg0;
  1169. if (const_arg[0] == 0)
  1170. {
  1171. return x;
  1172. }
  1173. arg0 = INTVAL (const_arg[0]);
  1174. switch (GET_CODE (x))
  1175. {
  1176. case NOT:
  1177. val = ~ arg0;
  1178. break;
  1179. case NEG:
  1180. val = - arg0;
  1181. break;
  1182. case SIGN_EXTEND:
  1183. val = arg0;
  1184. break;
  1185. default:
  1186. return x;
  1187. }
  1188. }
  1189. else if (GET_RTX_LENGTH (code) == 2)
  1190. {
  1191. register int arg0, arg1;
  1192. /* If 1st arg is the condition codes, 2nd must be zero
  1193. and this must be a comparison.
  1194. Decode the info on how the previous insn set the cc0
  1195. and use that to deduce result of comparison. */
  1196. if (XEXP (x, 0) == cc0_rtx)
  1197. {
  1198. if (prev_insn_cc0 == 0
  1199. || const_arg[1] != const0_rtx)
  1200. return x;
  1201. if (code == LEU || code == LTU || code == GEU || code == GTU)
  1202. arg0 = prev_insn_cc0 & 7;
  1203. else
  1204. arg0 = (prev_insn_cc0 >> 3) & 7;
  1205. if (arg0 == 7) arg0 = -1;
  1206. switch (code)
  1207. {
  1208. case LE:
  1209. case LEU:
  1210. return (arg0 <= 0) ? const1_rtx : const0_rtx;
  1211. case LT:
  1212. case LTU:
  1213. return (arg0 < 0) ? const1_rtx : const0_rtx;
  1214. case GE:
  1215. case GEU:
  1216. return (arg0 >= 0) ? const1_rtx : const0_rtx;
  1217. case GT:
  1218. case GTU:
  1219. return (arg0 > 0) ? const1_rtx : const0_rtx;
  1220. case NE:
  1221. return (arg0 != 0) ? const1_rtx : const0_rtx;
  1222. case EQ:
  1223. return (arg0 == 0) ? const1_rtx : const0_rtx;
  1224. default:
  1225. abort ();
  1226. }
  1227. }
  1228. if (const_arg[0] == 0 || const_arg[1] == 0)
  1229. {
  1230. /* Even if we can't compute a constant result,
  1231. there are some cases worth simplifying. */
  1232. if (code == PLUS)
  1233. {
  1234. if (const_arg[0] != 0 && INTVAL (const_arg[0]) == 0)
  1235. return XEXP (x, 1);
  1236. if (const_arg[1] != 0 && INTVAL (const_arg[1]) == 0)
  1237. return XEXP (x, 0);
  1238. if (const_arg[0] != 0 && GET_CODE (XEXP (x, 1)) == PLUS
  1239. && (CONSTANT_ADDRESS_P (XEXP (XEXP (x, 1), 0))
  1240. || CONSTANT_ADDRESS_P (XEXP (XEXP (x, 1), 1))))
  1241. /* constant + (variable + constant)
  1242. can result if an index register is made constant.
  1243. We simplify this by adding the constants.
  1244. If we did not, it would become an invalid address. */
  1245. return plus_constant (XEXP (x, 1),
  1246. INTVAL (const_arg[0]));
  1247. if (const_arg[1] != 0 && GET_CODE (XEXP (x, 0)) == PLUS
  1248. && (CONSTANT_ADDRESS_P (XEXP (XEXP (x, 0), 0))
  1249. || CONSTANT_ADDRESS_P (XEXP (XEXP (x, 0), 1))))
  1250. return plus_constant (XEXP (x, 0),
  1251. INTVAL (const_arg[1]));
  1252. }
  1253. if (code == MINUS)
  1254. {
  1255. if (const_arg[1] != 0 && INTVAL (const_arg[1]) == 0)
  1256. return XEXP (x, 0);
  1257. }
  1258. /* PLUS and MULT can appear inside of a MEM.
  1259. In such situations, a constant term must come second. */
  1260. if (code == MULT || code == PLUS)
  1261. if (const_arg[0] != 0)
  1262. {
  1263. XEXP (x, 0) = XEXP (x, 1);
  1264. XEXP (x, 1) = const_arg[0];
  1265. }
  1266. return x;
  1267. }
  1268. arg0 = INTVAL (const_arg[0]);
  1269. arg1 = INTVAL (const_arg[1]);
  1270. switch (code)
  1271. {
  1272. case PLUS:
  1273. val = arg0 + arg1;
  1274. break;
  1275. case MINUS:
  1276. if (GET_MODE (x) == VOIDmode)
  1277. /* Overflowless comparison:
  1278. cannot represent an exact answer, so don't fold.
  1279. This is used only to set the CC0,
  1280. and fold_cc0 will take care of it. */
  1281. return x;
  1282. val = arg0 - arg1;
  1283. break;
  1284. case MULT:
  1285. val = arg0 * arg1;
  1286. break;
  1287. case DIV:
  1288. val = arg0 / arg1;
  1289. break;
  1290. case MOD:
  1291. val = arg0 % arg1;
  1292. break;
  1293. case UMULT:
  1294. val = (unsigned) arg0 * arg1;
  1295. break;
  1296. case UDIV:
  1297. val = (unsigned) arg0 / arg1;
  1298. break;
  1299. case UMOD:
  1300. val = (unsigned) arg0 % arg1;
  1301. break;
  1302. case AND:
  1303. val = arg0 & arg1;
  1304. break;
  1305. case IOR:
  1306. val = arg0 | arg1;
  1307. break;
  1308. case XOR:
  1309. val = arg0 ^ arg1;
  1310. break;
  1311. case NE:
  1312. val = arg0 != arg1;
  1313. break;
  1314. case EQ:
  1315. val = arg0 == arg1;
  1316. break;
  1317. case LE:
  1318. val = arg0 <= arg1;
  1319. break;
  1320. case LT:
  1321. val = arg0 < arg1;
  1322. break;
  1323. case GE:
  1324. val = arg0 >= arg1;
  1325. break;
  1326. case GT:
  1327. val = arg0 > arg1;
  1328. break;
  1329. case LEU:
  1330. val = ((unsigned) arg0) <= ((unsigned) arg1);
  1331. break;
  1332. case LTU:
  1333. val = ((unsigned) arg0) < ((unsigned) arg1);
  1334. break;
  1335. case GEU:
  1336. val = ((unsigned) arg0) >= ((unsigned) arg1);
  1337. break;
  1338. case GTU:
  1339. val = ((unsigned) arg0) > ((unsigned) arg1);
  1340. break;
  1341. case LSHIFT:
  1342. val = ((unsigned) arg0) << arg1;
  1343. break;
  1344. case ASHIFT:
  1345. val = arg0 << arg1;
  1346. break;
  1347. case ROTATERT:
  1348. arg1 = - arg1;
  1349. case ROTATE:
  1350. {
  1351. int size = GET_MODE_SIZE (GET_MODE (x)) * BITS_PER_UNIT;
  1352. if (arg1 > 0)
  1353. {
  1354. arg1 %= size;
  1355. val = ((((unsigned) arg0) << arg1)
  1356. | (((unsigned) arg0) >> (size - arg1)));
  1357. }
  1358. else if (arg1 < 0)
  1359. {
  1360. arg1 = (- arg1) % size;
  1361. val = ((((unsigned) arg0) >> arg1)
  1362. | (((unsigned) arg0) << (size - arg1)));
  1363. }
  1364. else
  1365. val = arg0;
  1366. }
  1367. break;
  1368. case LSHIFTRT:
  1369. val = ((unsigned) arg0) >> arg1;
  1370. break;
  1371. case ASHIFTRT:
  1372. val = arg0 >> arg1;
  1373. break;
  1374. default:
  1375. return x;
  1376. }
  1377. }
  1378. else if (code == IF_THEN_ELSE && const_arg[0] != 0)
  1379. return XEXP (x, ((INTVAL (const_arg[0]) != 0) ? 1 : 2));
  1380. else
  1381. return x;
  1382. /* ??? Here must clear or set the bits that don't belong in our mode. */
  1383. return gen_rtx (CONST_INT, VOIDmode, val);
  1384. }
  1385. /* Given an expression X which is used to set CC0,
  1386. return an integer recording (in the encoding used for prev_insn_cc0)
  1387. how the condition codes would be set by that expression.
  1388. Return 0 if the value is not constant. */
  1389. static int
  1390. fold_cc0 (x)
  1391. rtx x;
  1392. {
  1393. if (GET_CODE (x) == MINUS && GET_MODE (x) == VOIDmode)
  1394. {
  1395. rtx y0 = fold_rtx (XEXP (x, 0));
  1396. rtx y1 = fold_rtx (XEXP (x, 1));
  1397. int i0, i1;
  1398. if (GET_CODE (y0) != CONST_INT || GET_CODE (y1) != CONST_INT)
  1399. return 0;
  1400. i0 = INTVAL (y0);
  1401. i1 = INTVAL (y1);
  1402. return 100 + ((i0 < i1 ? 7 : i0 > i1) << 3)
  1403. + (((unsigned) i0 < (unsigned) i1) ? 7
  1404. : ((unsigned) i0 > (unsigned) i1));
  1405. }
  1406. x = fold_rtx (x);
  1407. if (GET_CODE (x) != CONST_INT)
  1408. return 0;
  1409. return 100 + ((INTVAL (x) < 0 ? 7 : INTVAL (x) > 0) << 3) + INTVAL (x) != 0;
  1410. }
  1411. /* Attempt to prove that a loop will be executed >= 1 times,
  1412. or prove it will be executed 0 times.
  1413. If either can be proved, delete some of the code. */
  1414. predecide_loop_entry (insn)
  1415. register rtx insn;
  1416. {
  1417. register rtx jump = NEXT_INSN (insn);
  1418. register rtx p = JUMP_LABEL (jump);
  1419. register rtx loop_top_label = NEXT_INSN (NEXT_INSN (jump));
  1420. enum { UNK, DELETE_LOOP, DELETE_JUMP } disposition = UNK;
  1421. /* Trace the flow of control through the end test,
  1422. propagating constants, to see if result is determined. */
  1423. prev_insn_cc0 = 0;
  1424. while (1)
  1425. {
  1426. /* Arriving at end of loop means endtest will drop out. */
  1427. if (GET_CODE (p) == NOTE
  1428. && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
  1429. {
  1430. disposition = DELETE_LOOP;
  1431. break;
  1432. }
  1433. else if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == NOTE)
  1434. ;
  1435. /* We only know how to handle two kinds of insns:
  1436. conditional jumps, and those that set the condition codes. */
  1437. else if (GET_CODE (p) == INSN && GET_CODE (PATTERN (p)) == SET
  1438. && SET_DEST (PATTERN (p)) == cc0_rtx)
  1439. {
  1440. prev_insn_cc0 = fold_cc0 (copy_rtx (SET_SRC (PATTERN (p))));
  1441. }
  1442. else if (GET_CODE (p) == JUMP_INSN
  1443. && GET_CODE (PATTERN (p)) == SET
  1444. && SET_DEST (PATTERN (p)) == pc_rtx)
  1445. {
  1446. register rtx target
  1447. = fold_rtx (copy_rtx (SET_SRC (PATTERN (p))));
  1448. if (GET_CODE (target) == LABEL_REF)
  1449. p = XEXP (target, 0);
  1450. else if (target != pc_rtx)
  1451. /* If destination of jump is not fixed, give up. */
  1452. break;
  1453. }
  1454. /* Any other kind of insn means we don't know
  1455. what result the test will have. */
  1456. else
  1457. break;
  1458. /* Arriving at top of loop means we can drop straight in.
  1459. Check here because we can arrive only via a jump insn
  1460. which would have changed P above. */
  1461. if (p == loop_top_label)
  1462. {
  1463. disposition = DELETE_JUMP;
  1464. break;
  1465. }
  1466. /* We went past one insn; consider the next. */
  1467. p = NEXT_INSN (p);
  1468. }
  1469. if (disposition == DELETE_JUMP)
  1470. {
  1471. /* We know the loop test will succeed the first time,
  1472. so delete the jump to the test; drop right into loop.
  1473. Note that one call to delete_insn gets the BARRIER as well. */
  1474. delete_insn (jump);
  1475. }
  1476. if (disposition == DELETE_LOOP)
  1477. {
  1478. /* We know the endtest will fail and drop right out of the loop,
  1479. but it isn't safe to delete the loop here.
  1480. There could be jumps into it from outside.
  1481. So make the entry-jump jump around the loop.
  1482. This will cause find_basic_blocks to delete it if appropriate. */
  1483. register rtx label = gen_label_rtx ();
  1484. emit_label_after (label, p);
  1485. redirect_jump (jump, label);
  1486. }
  1487. }
  1488. /* CSE processing for one instruction.
  1489. First simplify sources and addresses of all assignments
  1490. in the instruction, using previously-computed equivalents values.
  1491. Then install the new sources and destinations in the table
  1492. of available values. */
  1493. static rtx set[MAX_SETS_PER_INSN];
  1494. static struct table_elt *src_elt[MAX_SETS_PER_INSN];
  1495. static int src_hash_code[MAX_SETS_PER_INSN];
  1496. static int dest_hash_code[MAX_SETS_PER_INSN];
  1497. static char src_in_memory[MAX_SETS_PER_INSN];
  1498. static char src_volatile[MAX_SETS_PER_INSN];
  1499. static void
  1500. cse_insn (insn)
  1501. rtx insn;
  1502. {
  1503. register rtx x = PATTERN (insn);
  1504. register int i;
  1505. register int n_sets = 0;
  1506. /* Records what this insn does to set CC0,
  1507. using same encoding used for prev_insn_cc0. */
  1508. int this_insn_cc0 = 0;
  1509. struct write_data writes_memory;
  1510. static struct write_data init = {0, 0, 0};
  1511. writes_memory = init;
  1512. /* Find all the SETs and CLOBBERs in this instruction.
  1513. Record all the SETs in the array `set' and count them.
  1514. Also determine whether there is a CLOBBER that invalidates
  1515. all memory references, or all references at varying addresses. */
  1516. if (GET_CODE (x) == SET)
  1517. {
  1518. n_sets = 1;
  1519. set[0] = x;
  1520. /* Return now for unconditional jumps.
  1521. The never need cse processing, so this does not hurt.
  1522. The reason is not efficiency but rather
  1523. so that we can test at the end for instructions
  1524. that have been simplified to unconditional jumps
  1525. and not be misled by unchanged instructions
  1526. that were unconditional jumps to begin with. */
  1527. if (SET_DEST (x) == pc_rtx
  1528. && GET_CODE (SET_SRC (x)) == LABEL_REF)
  1529. return;
  1530. }
  1531. else if (GET_CODE (x) == PARALLEL)
  1532. {
  1533. register int lim;
  1534. lim = XVECLEN (x, 0);
  1535. for (i = 0; i < lim; i++)
  1536. {
  1537. register rtx y = XVECEXP (x, 0, i);
  1538. if (GET_CODE (y) == SET)
  1539. set[n_sets++] = y;
  1540. else if (GET_CODE (y) == CLOBBER)
  1541. note_mem_written (XEXP (y, 0), &writes_memory);
  1542. else if (GET_CODE (y) == CALL)
  1543. canon_reg (y);
  1544. }
  1545. }
  1546. else if (GET_CODE (x) == CLOBBER)
  1547. note_mem_written (XEXP (x, 0), &writes_memory);
  1548. else if (GET_CODE (x) == CALL)
  1549. canon_reg (x);
  1550. if (n_sets == 0)
  1551. {
  1552. invalidate_from_clobbers (&writes_memory, x);
  1553. return;
  1554. }
  1555. /* Canonicalize sources and addresses of destinations.
  1556. set src_elt[i] to the class each source belongs to.
  1557. Detect assignments from or to volatile things
  1558. and set set[i] to zero so they will be ignored
  1559. in the rest of this function.
  1560. Nothing in this loop changes the hash table or the register chains. */
  1561. for (i = 0; i < n_sets; i++)
  1562. {
  1563. register rtx src, dest, addr;
  1564. register struct table_elt *elt;
  1565. dest = SET_DEST (set[i]);
  1566. src = SET_SRC (set[i]);
  1567. /* Replace each registers in SRC with oldest equivalent register,
  1568. but if DEST is a register do not replace it if it appears in SRC. */
  1569. if (GET_CODE (dest) == REG)
  1570. {
  1571. int tem = reg_qty[REGNO (dest)];
  1572. reg_qty[REGNO (dest)] = REGNO (dest);
  1573. src = canon_reg (src);
  1574. reg_qty[REGNO (dest)] = tem;
  1575. }
  1576. else
  1577. src = canon_reg (src);
  1578. /* Compute SRC's hash code, and also notice if it
  1579. should not be recorded at all. In that case,
  1580. prevent any further processing of this assignment. */
  1581. do_not_record = 0;
  1582. hash_arg_in_memory = 0;
  1583. src = fold_rtx (src);
  1584. /* If we have (NOT Y), see if Y is known to be (NOT Z).
  1585. If so, (NOT Y) simplifies to Z. */
  1586. if (GET_CODE (src) == NOT || GET_CODE (src) == NEG)
  1587. {
  1588. rtx y = lookup_as_function (XEXP (src, 0), GET_CODE (src));
  1589. if (y != 0)
  1590. src = y;
  1591. }
  1592. /* If storing a constant value in a register that
  1593. previously held the constant value 0,
  1594. record this fact with a REG_WAS_0 note on this insn. */
  1595. if (GET_CODE (src) == CONST_INT
  1596. && GET_CODE (dest) == REG
  1597. && qty_const[reg_qty[REGNO (dest)]] == const0_rtx)
  1598. REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_WAS_0,
  1599. dest, REG_NOTES (insn));
  1600. src_hash_code[i] = HASH (src);
  1601. src_volatile[i] = do_not_record;
  1602. if (GET_CODE (src) == REG)
  1603. {
  1604. src_in_memory[i] = 0;
  1605. src_elt[i] = 0;
  1606. }
  1607. else if (!src_volatile[i])
  1608. {
  1609. /* Replace the source with its cheapest equivalent. */
  1610. elt = lookup (src, src_hash_code[i]);
  1611. if (elt && elt != elt->first_same_value)
  1612. {
  1613. elt = elt->first_same_value;
  1614. /* Find the cheapest one that is still valid. */
  1615. while (GET_CODE (elt->exp) != REG
  1616. && !exp_equiv_p (elt->exp, elt->exp, 1))
  1617. elt = elt->next_same_value;
  1618. src = copy_rtx (elt->exp);
  1619. hash_arg_in_memory = 0;
  1620. src_hash_code[i] = HASH (src);
  1621. }
  1622. /* If ELT is a constant, is there a register
  1623. linearly related to it? If so, replace it
  1624. with the sum of that register plus an offset. */
  1625. if (GET_CODE (src) == CONST && n_sets == 1)
  1626. {
  1627. rtx newsrc = use_related_value (src, elt);
  1628. if (newsrc)
  1629. {
  1630. src = newsrc;
  1631. hash_arg_in_memory = 0;
  1632. src_hash_code[i] = HASH (src);
  1633. /* The new expression for the SRC has the same value
  1634. as the previous one; so if the previous one is in
  1635. the hash table, put the new one in as equivalent. */
  1636. if (elt != 0)
  1637. elt = insert (src, elt->first_same_value, src_hash_code[i]);
  1638. /* The reg this insn sets is no longer a "constant" reg
  1639. because SRC now depends on a register that may not
  1640. be invariant. */
  1641. REG_NOTES (insn) = 0;
  1642. }
  1643. }
  1644. src_elt[i] = elt;
  1645. src_in_memory[i] = hash_arg_in_memory;
  1646. }
  1647. /* Either canon_reg or the copy_rtx may have changed this. */
  1648. /* Note it is not safe to replace the sources if there
  1649. is more than one set. We could get an insn
  1650. [(set (reg) (reg)) (set (reg) (reg))], which is probably
  1651. not in the machine description.
  1652. This case we could handle by breaking into several insns.
  1653. Cases of partial substituttion cannot win at all. */
  1654. /* Also, if this insn is setting a "constant" register,
  1655. we may not replace the value that is given to it. */
  1656. if (n_sets == 1)
  1657. if (REG_NOTES (insn) == 0
  1658. || (enum reg_note) GET_MODE (REG_NOTES (insn)) != REG_CONST)
  1659. SET_SRC (set[i]) = src;
  1660. do_not_record = 0;
  1661. /* If storing into memory, do cse on the memory address.
  1662. Also compute the hash code of the destination now,
  1663. before the effects of this instruction are recorded,
  1664. since the register values used in the address computation
  1665. are those before this instruction. */
  1666. /* We can discard a VOLATILE around the destination of the set
  1667. because we never coalesce, reorder or delete stores into memory. */
  1668. if (GET_CODE (dest) == VOLATILE)
  1669. SET_SRC (set[i]) = dest = XEXP (dest, 0);
  1670. if (GET_CODE (dest) == MEM)
  1671. {
  1672. register rtx addr;
  1673. register int hash;
  1674. canon_reg (dest);
  1675. addr = fold_rtx (XEXP (dest, 0));
  1676. XEXP (dest, 0) = addr;
  1677. /* Pushing or popping does not invalidate anything. */
  1678. if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
  1679. || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
  1680. && GET_CODE (XEXP (addr, 0)) == REG
  1681. && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
  1682. ;
  1683. else
  1684. /* Otherwise, decide whether we invalidate
  1685. everything in memory, or just things at non-fixed places.
  1686. Writing a large aggregate must invalidate everything
  1687. because we don't know how long it is. */
  1688. note_mem_written (dest, &writes_memory);
  1689. /* Do not consider addresses of local and argument slots.
  1690. The MEM expressions for args and non-register local variables
  1691. are made only once and inserted in many instructions,
  1692. as well as being used to control symbol table output.
  1693. It is not safe to clobber them. */
  1694. if ((GET_CODE (addr) == PLUS
  1695. && GET_CODE (XEXP (addr, 0)) == REG
  1696. && GET_CODE (XEXP (addr, 1)) == CONST_INT
  1697. && (hash = REGNO (XEXP (addr, 0)),
  1698. hash == FRAME_POINTER_REGNUM || hash == ARG_POINTER_REGNUM))
  1699. || (GET_CODE (addr) == REG
  1700. && (hash = REGNO (addr),
  1701. hash == FRAME_POINTER_REGNUM || hash == ARG_POINTER_REGNUM)))
  1702. ;
  1703. else
  1704. {
  1705. hash = HASH (addr);
  1706. if (! do_not_record)
  1707. {
  1708. elt = lookup (addr, hash);
  1709. dest_hash_code[i] = ((int) MEM + hash) % NBUCKETS;
  1710. if (elt && elt != elt->first_same_value)
  1711. {
  1712. elt = elt->first_same_value;
  1713. /* Find the cheapest one that is still valid. */
  1714. while (GET_CODE (elt->exp) != REG
  1715. && !exp_equiv_p (elt->exp, elt->exp, 1))
  1716. elt = elt->next_same_value;
  1717. XEXP (dest, 0) = addr
  1718. = copy_rtx (elt->exp);
  1719. }
  1720. }
  1721. }
  1722. }
  1723. /* For compound destinations that modify only a part of
  1724. register or memory location, we cannot enter them
  1725. in the hash table since we know only part of the value.
  1726. Set src_volatile to prevent this.
  1727. But we must invalidate the entire value.
  1728. So prevent set[i] from becoming zero. */
  1729. if (GET_CODE (dest) == SUBREG
  1730. || GET_CODE (dest) == STRICT_LOW_PART
  1731. || GET_CODE (dest) == ZERO_EXTRACT
  1732. || GET_CODE (dest) == SIGN_EXTRACT)
  1733. src_volatile[i] = 1;
  1734. /* No further processing for this assignment
  1735. if destination is volatile. */
  1736. else if (do_not_record
  1737. || (GET_CODE (dest) == REG
  1738. ? REGNO (dest) == STACK_POINTER_REGNUM
  1739. : GET_CODE (dest) != MEM))
  1740. set[i] = 0;
  1741. if (dest == cc0_rtx && GET_CODE (src) == MINUS)
  1742. this_insn_cc0 = fold_cc0 (src);
  1743. }
  1744. /* Now enter all non-volatile source expressions in the hash table
  1745. if they are not already present.
  1746. Record in src_elt the heads of their equivalence classes.
  1747. This way we can insert the corresponding destinations into
  1748. the same classes even if the actual sources are no longer in them
  1749. (having been invalidated). */
  1750. for (i = 0; i < n_sets; i++)
  1751. if (set[i] && src_elt[i] == 0 && ! src_volatile[i])
  1752. {
  1753. register rtx src = SET_SRC (set[i]);
  1754. register struct table_elt *elt;
  1755. /* Note that these insert_regs calls cannot remove
  1756. any of the src_elt's, because they would have failed to match
  1757. if not still valid. */
  1758. if (insert_regs (src, 0, 0))
  1759. src_hash_code[i] = HASH (src);
  1760. elt = insert (src, 0, src_hash_code[i]);
  1761. elt->in_memory = src_in_memory[i];
  1762. src_elt[i] = elt->first_same_value;
  1763. }
  1764. invalidate_from_clobbers (&writes_memory, x);
  1765. /* Now invalidate everything set by this instruction.
  1766. If a SUBREG or other funny destination is being set,
  1767. set[i] is still nonzero, so here we invalidate the reg
  1768. a part of which is being set. */
  1769. for (i = 0; i < n_sets; i++)
  1770. if (set[i])
  1771. {
  1772. register rtx dest = SET_DEST (set[i]);
  1773. while (GET_CODE (dest) == SUBREG
  1774. || GET_CODE (dest) == STRICT_LOW_PART
  1775. || GET_CODE (dest) == ZERO_EXTRACT
  1776. || GET_CODE (dest) == SIGN_EXTRACT)
  1777. dest = XEXP (dest, 0);
  1778. /* Needed for registers to remove the register from its
  1779. previous quantity's chain.
  1780. Needed for memory if this is a nonvarying address, unless
  1781. we have just done an invalidate_memory that covers even those. */
  1782. if (GET_CODE (dest) == REG
  1783. || (! writes_memory.all && ! rtx_addr_varies_p (dest)))
  1784. invalidate (dest);
  1785. }
  1786. /* We may have just removed some of the src_elt's.
  1787. So replace each one with the current head of the same class. */
  1788. for (i = 0; i < n_sets; i++)
  1789. if (set[i] && ! src_volatile[i] && src_elt[i]->first_same_value == 0)
  1790. {
  1791. register struct table_elt *elt = src_elt[i];
  1792. /* If elt was removed, find current head of same class,
  1793. or 0 if nothing remains of that class. */
  1794. while (elt && elt->first_same_value == 0)
  1795. elt = elt->next_same_value;
  1796. src_elt[i] = elt ? elt->first_same_value : 0;
  1797. }
  1798. /* Now insert the destinations into their equivalence classes.
  1799. If the source is volatile, record the destination in
  1800. a class of its own. */
  1801. for (i = 0; i < n_sets; i++)
  1802. if (set[i])
  1803. {
  1804. register rtx dest = SET_DEST (set[i]);
  1805. register struct table_elt *elt = src_elt[i];
  1806. if (src_volatile[i])
  1807. elt = 0;
  1808. if (insert_regs (dest, elt, 1))
  1809. dest_hash_code[i] = HASHREG (dest);
  1810. elt = insert (dest, elt, dest_hash_code[i]);
  1811. elt->in_memory = GET_CODE (dest) == MEM;
  1812. }
  1813. /* Did this insn become an unconditional branch or become a no-op? */
  1814. if (GET_CODE (insn) == JUMP_INSN
  1815. && GET_CODE (x) == SET
  1816. && SET_DEST (x) == pc_rtx)
  1817. {
  1818. if (SET_SRC (x) == pc_rtx)
  1819. {
  1820. PUT_CODE (insn, NOTE);
  1821. NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
  1822. NOTE_SOURCE_FILE (insn) = 0;
  1823. cse_jumps_altered = 1;
  1824. /* If previous insn just set CC0 for us, delete it too. */
  1825. if (prev_insn_cc0 != 0)
  1826. {
  1827. PUT_CODE (prev_insn, NOTE);
  1828. NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
  1829. NOTE_SOURCE_FILE (prev_insn) = 0;
  1830. }
  1831. }
  1832. else if (GET_CODE (SET_SRC (x)) == LABEL_REF)
  1833. {
  1834. emit_barrier_after (insn);
  1835. cse_jumps_altered = 1;
  1836. /* If previous insn just set CC0 for us, delete it too. */
  1837. if (prev_insn_cc0 != 0)
  1838. {
  1839. PUT_CODE (prev_insn, NOTE);
  1840. NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
  1841. NOTE_SOURCE_FILE (prev_insn) = 0;
  1842. }
  1843. }
  1844. }
  1845. prev_insn_cc0 = this_insn_cc0;
  1846. prev_insn = insn;
  1847. }
  1848. /* Store 1 in *WRITES_PTR for those categories of memory ref
  1849. that must be invalidated when the expression WRITTEN is stored in.
  1850. If WRITTEN is null, say everything must be invalidated. */
  1851. static void
  1852. note_mem_written (written, writes_ptr)
  1853. rtx written;
  1854. struct write_data *writes_ptr;
  1855. {
  1856. static struct write_data everything = {1, 1, 1};
  1857. if (written == 0)
  1858. *writes_ptr = everything;
  1859. else if (GET_CODE (written) == MEM)
  1860. {
  1861. if (rtx_addr_varies_p (written))
  1862. {
  1863. /* A varying address that is a sum indicates an array element,
  1864. and that's just as good as a structure element
  1865. in implying that we need not invalidate scalar variables. */
  1866. if (!(written->in_struct
  1867. || GET_CODE (XEXP (written, 0)) == PLUS))
  1868. writes_ptr->all = 1;
  1869. writes_ptr->nonscalar = 1;
  1870. }
  1871. writes_ptr->var = 1;
  1872. }
  1873. }
  1874. /* Perform invalidation on the basis of everything about an insn
  1875. except for invalidating the actual places that are SET in it.
  1876. This includes the places CLOBBERed, and anything that might
  1877. alias with something that is SET or CLOBBERed.
  1878. W points to the writes_memory for this insn, a struct write_data
  1879. saying which kinds of memory references must be invalidated.
  1880. X is the pattern of the insn. */
  1881. static void
  1882. invalidate_from_clobbers (w, x)
  1883. struct write_data *w;
  1884. rtx x;
  1885. {
  1886. /* If W->var is not set, W specifies no action.
  1887. If W->all is set, this step gets all memory refs
  1888. so they can be ignored in the rest of this function. */
  1889. if (w->var)
  1890. invalidate_memory (w);
  1891. if (GET_CODE (x) == CLOBBER)
  1892. {
  1893. rtx ref = XEXP (x, 0);
  1894. if (ref
  1895. && (GET_CODE (ref) == REG
  1896. || (GET_CODE (ref) == MEM && ! w->all)))
  1897. invalidate (ref);
  1898. }
  1899. else if (GET_CODE (x) == PARALLEL)
  1900. {
  1901. register int i;
  1902. for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
  1903. {
  1904. register rtx y = XVECEXP (x, 0, i);
  1905. if (GET_CODE (y) == CLOBBER)
  1906. {
  1907. rtx ref = XEXP (y, 0);
  1908. if (ref
  1909. &&(GET_CODE (ref) == REG
  1910. || (GET_CODE (ref) == MEM && !w->all)))
  1911. invalidate (ref);
  1912. }
  1913. }
  1914. }
  1915. }
  1916. static void cse_basic_block ();
  1917. /* Perform cse on the instructions of a function.
  1918. F is the first instruction.
  1919. NREGS is one plus the highest pseudo-reg number used in the instruction.
  1920. Returns 1 if jump_optimize should be redone due to simplifications
  1921. in conditional jump instructions. */
  1922. int
  1923. cse_main (f, nregs)
  1924. /* f is the first instruction of a chain of insns for one function */
  1925. rtx f;
  1926. /* nregs is the total number of registers used in it */
  1927. int nregs;
  1928. {
  1929. register rtx insn = f;
  1930. register int i;
  1931. cse_jumps_altered = 0;
  1932. init_recog ();
  1933. max_reg = nregs;
  1934. all_minus_one = (int *) alloca (nregs * sizeof (int));
  1935. consec_ints = (int *) alloca (nregs * sizeof (int));
  1936. for (i = 0; i < nregs; i++)
  1937. {
  1938. all_minus_one[i] = -1;
  1939. consec_ints[i] = i;
  1940. }
  1941. reg_next_eqv = (int *) alloca (nregs * sizeof (int));
  1942. reg_prev_eqv = (int *) alloca (nregs * sizeof (int));
  1943. reg_qty = (int *) alloca (nregs * sizeof (int));
  1944. reg_rtx = (rtx *) alloca (nregs * sizeof (rtx));
  1945. reg_in_table = (int *) alloca (nregs * sizeof (int));
  1946. reg_tick = (int *) alloca (nregs * sizeof (int));
  1947. /* Discard all the free elements of the previous function
  1948. since they are allocated in the temporarily obstack. */
  1949. bzero (table, sizeof table);
  1950. free_element_chain = 0;
  1951. n_elements_made = 0;
  1952. /* Loop over basic blocks */
  1953. while (insn)
  1954. {
  1955. register rtx p = insn;
  1956. register int i = 0;
  1957. register int last_uid;
  1958. /* Find end of next basic block */
  1959. while (p && GET_CODE (p) != CODE_LABEL)
  1960. {
  1961. last_uid = INSN_UID (p);
  1962. p = NEXT_INSN (p);
  1963. i++;
  1964. }
  1965. cse_basic_block_end = last_uid;
  1966. max_qty = max_reg + i * MAX_SETS_PER_INSN;
  1967. cse_basic_block (insn, p);
  1968. insn = p ? NEXT_INSN (p) : 0;
  1969. }
  1970. if (max_elements_made < n_elements_made)
  1971. max_elements_made = n_elements_made;
  1972. return cse_jumps_altered;
  1973. }
  1974. static void
  1975. cse_basic_block (from, to)
  1976. register rtx from, to;
  1977. {
  1978. register rtx insn;
  1979. int *qv1 = (int *) alloca (max_qty * sizeof (int));
  1980. int *qv2 = (int *) alloca (max_qty * sizeof (int));
  1981. rtx *qv3 = (rtx *) alloca (max_qty * sizeof (rtx));
  1982. qty_first_reg = qv1;
  1983. qty_last_reg = qv2;
  1984. qty_const = qv3;
  1985. new_basic_block ();
  1986. for (insn = from; insn != to; insn = NEXT_INSN (insn))
  1987. {
  1988. register RTX_CODE code = GET_CODE (insn);
  1989. if (code == INSN || code == JUMP_INSN || code == CALL_INSN)
  1990. cse_insn (insn);
  1991. /* Memory, and some registers, are invalidate by subroutine calls. */
  1992. if (code == CALL_INSN)
  1993. {
  1994. register int i;
  1995. static struct write_data everything = {1, 1, 1};
  1996. invalidate_memory (&everything);
  1997. for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
  1998. if (call_clobbers_reg[i] && reg_rtx[i]
  1999. && i != FRAME_POINTER_REGNUM
  2000. && i != ARG_POINTER_REGNUM)
  2001. invalidate (reg_rtx[i]);
  2002. }
  2003. /* Loop beginnings are often followed by jumps
  2004. (that enter the loop above the endtest).
  2005. See if we can prove the loop will be executed at least once;
  2006. if so, delete the jump. Also perhaps we can prove loop
  2007. will never be executed and delete the entire thing. */
  2008. if (code == NOTE
  2009. && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
  2010. && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN)
  2011. {
  2012. predecide_loop_entry (insn);
  2013. /* Whether that jump was deleted or not,
  2014. it certainly is the end of the basic block.
  2015. Since the jump is unconditional,
  2016. it requires no further processing here. */
  2017. break;
  2018. }
  2019. }
  2020. }