1169689Skan/* Sign extension elimination optimization for GNU compiler.
2169689Skan   Copyright (C) 2005 Free Software Foundation, Inc.
3169689Skan   Contributed by Leehod Baruch <leehod@il.ibm.com>
4169689Skan
5169689SkanThis file is part of GCC.
6169689Skan
7169689SkanGCC is free software; you can redistribute it and/or modify it under
8169689Skanthe terms of the GNU General Public License as published by the Free
9169689Skan-Software Foundation; either version 2, or (at your option) any later
10169689Skanversion.
11169689Skan
12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY
13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or
14169689SkanFITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15169689Skanfor more details.
16169689Skan
17169689SkanYou should have received a copy of the GNU General Public License
18169689Skanalong with GCC; see the file COPYING.  If not, write to the Free
19169689SkanSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA
20169689Skan02111-1307, USA.
21169689Skan
22169689SkanProblem description:
23169689Skan--------------------
24169689SkanIn order to support 32bit computations on a 64bit machine, sign
25169689Skanextension instructions are generated to ensure the correctness of
26169689Skanthe computation.
27169689SkanA possible policy (as currently implemented) is to generate a sign
28169689Skanextension right after each 32bit computation.
29169689SkanDepending on the instruction set of the architecture, some of these
30169689Skansign extension instructions may be redundant.
31169689SkanThere are two cases in which the extension may be redundant:
32169689Skan
33169689SkanCase1:
34169689SkanThe instruction that uses the 64bit operands that are sign
35169689Skanextended has a dual mode that works with 32bit operands.
36169689SkanFor example:
37169689Skan
38169689Skan  int32 a, b;
39169689Skan
40169689Skan  a = ....	       -->	a = ....
41169689Skan  a = sign extend a    -->
42169689Skan  b = ....	       -->	b = ....
43169689Skan  b = sign extend a    -->
44169689Skan		       -->
45169689Skan  cmpd a, b	       -->	cmpw a, b  //half word compare
46169689Skan
47169689SkanCase2:
48169689SkanThe instruction that defines the 64bit operand (which is later sign
49169689Skanextended) has a dual mode that defines and sign-extends simultaneously
50169689Skana 32bit operand.  For example:
51169689Skan
52169689Skan  int32 a;
53169689Skan
54169689Skan  ld a		     -->   lwa a   // load half word and sign extend
55169689Skan  a = sign extend a  -->
56169689Skan		     -->
57169689Skan  return a	     -->   return a
58169689Skan
59169689Skan
60169689SkanGeneral idea for solution:
61169689Skan--------------------------
62169689SkanFirst, try to merge the sign extension with the instruction that
63169689Skandefines the source of the extension and (separately) with the
64169689Skaninstructions that uses the extended result.  By doing this, both cases
65169689Skanof redundancies (as described above) will be eliminated.
66169689Skan
67169689SkanThen, use partial redundancy elimination to place the non redundant
68169689Skanones at optimal placements.
69169689Skan
70169689Skan
71169689SkanImplementation by example:
72169689Skan--------------------------
73169689SkanNote: The instruction stream is not changed till the last phase.
74169689Skan
75169689SkanPhase 0: Initial code, as currently generated by gcc.
76169689Skan
77169689Skan			 def1		def3
78169689Skan			 se1	 def2	 se3
79169689Skan			  | \	  |	/ |
80169689Skan			  |  \	  |    /  |
81169689Skan			  |   \	  |   /	  |
82169689Skan			  |    \  |  /	  |
83169689Skan			  |	\ | /	  |
84169689Skan			  |	 \|/	  |
85169689Skan			use1	use2	 use3
86169689Skan					 use4
87169689Skandef1 + se1:
88169689Skanset ((reg:SI 10) (..def1rhs..))
89169689Skanset ((reg:DI 100) (sign_extend:DI (reg:SI 10)))
90169689Skan
91169689Skandef2:
92169689Skanset ((reg:DI 100) (const_int 7))
93169689Skan
94169689Skandef3 + se3:
95169689Skanset ((reg:SI 20) (..def3rhs..))
96169689Skanset ((reg:DI 100) (sign_extend:DI (reg:SI 20)))
97169689Skan
98169689Skanuse1:
99169689Skanset ((reg:CC...) (compare:CC (reg:DI 100) (...)))
100169689Skan
101169689Skanuse2, use3, use4:
102169689Skanset ((...) (reg:DI 100))
103169689Skan
104169689SkanPhase 1: Propagate extensions to uses.
105169689Skan
106169689Skan			 def1		def3
107169689Skan			 se1	 def2	 se3
108169689Skan			  | \	  |	/ |
109169689Skan			  |  \	  |    /  |
110169689Skan			  |   \	  |   /	  |
111169689Skan			  |    \  |  /	  |
112169689Skan			  |	\ | /	  |
113169689Skan			  |	 \|/	  |
114169689Skan			 se	 se	 se
115169689Skan			use1	use2	 use3
116169689Skan					 se
117169689Skan					 use4
118169689Skan
119169689SkanFrom here, all of the subregs are lowpart !
120169689Skan
121169689Skandef1, def2, def3: No change.
122169689Skan
123169689Skanuse1:
124169689Skanset ((reg:DI 100) (sign_extend:DI ((subreg:SI (reg:DI 100)))))
125169689Skanset ((reg:CC...) (compare:CC (reg:DI 100) (...)))
126169689Skan
127169689Skanuse2, use3, use4:
128169689Skanset ((reg:DI 100) (sign_extend:DI ((subreg:SI (reg:DI 100)))))
129169689Skanset ((...) (reg:DI 100))
130169689Skan
131169689Skan
132169689SkanPhase 2: Merge and eliminate locally redundant extensions.
133169689Skan
134169689Skan
135169689Skan			*def1	 def2	*def3
136169689Skan		  [se removed]	  se	 se3
137169689Skan			  | \	  |	/ |
138169689Skan			  |  \	  |    /  |
139169689Skan			  |   \	  |   /	  |
140169689Skan			  |    \  |  /	  |
141169689Skan			  |	\ | /	  |
142169689Skan			  |	 \|/	  |
143169689Skan		  [se removed]	 se	  se
144169689Skan			*use1	use2	 use3
145169689Skan				      [se removed]
146169689Skan					 use4
147169689Skan
148169689SkanThe instructions that were changed at this phase are marked with
149169689Skanasterisk.
150169689Skan
151169689Skan*def1: Merge failed.
152169689Skan       Remove the sign extension instruction, modify def1 and
153169689Skan       insert a move instruction to assure to correctness of the code.
154169689Skanset ((subreg:SI (reg:DI 100)) (..def1rhs..))
155169689Skanset ((reg:SI 10) (subreg:SI (reg:DI 100)))
156169689Skan
157169689Skandef2 + se: There is no need for merge.
158169689Skan	   Def2 is not changed but a sign extension instruction is
159169689Skan	   created.
160169689Skanset ((reg:DI 100) (const_int 7))
161169689Skanset ((reg:DI 100) (sign_extend:DI ((subreg:SI (reg:DI 100)))))
162169689Skan
163169689Skan*def3 + se3: Merge succeeded.
164169689Skanset ((reg:DI 100) (sign_extend:DI (..def3rhs..)))
165169689Skanset ((reg:SI 20) (reg:DI 100))
166169689Skanset ((reg:DI 100) (sign_extend:DI (reg:SI 20)))
167169689Skan(The extension instruction is the original one).
168169689Skan
169169689Skan*use1: Merge succeeded.  Remove the sign extension instruction.
170169689Skanset ((reg:CC...)
171169689Skan     (compare:CC (subreg:SI (reg:DI 100)) (...)))
172169689Skan
173169689Skanuse2, use3: Merge failed.  No change.
174169689Skan
175169689Skanuse4: The extension is locally redundant, therefore it is eliminated
176169689Skan      at this point.
177169689Skan
178169689Skan
179169689SkanPhase 3: Eliminate globally redundant extensions.
180169689Skan
181169689SkanFollowing the LCM output:
182169689Skan
183169689Skan			 def1	 def2	 def3
184169689Skan				  se	 se3
185169689Skan			  | \	  |	/ |
186169689Skan			  |  \	  |    /  |
187169689Skan			  |   se  |   /	  |
188169689Skan			  |    \  |  /	  |
189169689Skan			  |	\ | /	  |
190169689Skan			  |	 \|/	  |
191169689Skan				[ses removed]
192169689Skan			 use1	use2	 use3
193169689Skan					 use4
194169689Skan
195169689Skanse:
196169689Skanset ((reg:DI 100) (sign_extend:DI ((subreg:SI (reg:DI 100)))))
197169689Skan
198169689Skanse3:
199169689Skanset ((reg:DI 100) (sign_extend:DI (reg:SI 20)))
200169689Skan
201169689Skan
202169689SkanPhase 4: Commit changes to the insn stream.
203169689Skan
204169689Skan
205169689Skan   def1		   def3			*def1	 def2	*def3
206169689Skan    se1	   def2	   se3		    [se removed]       [se removed]
207169689Skan    | \	    |	  / |			  | \	  |	/ |
208169689Skan    |  \    |	 /  |	   ------>	  |  \	  |    /  |
209169689Skan    |	\   |	/   |	   ------>	  |   se  |   /	  |
210169689Skan    |	 \  |  /    |			  |    \  |  /	  |
211169689Skan    |	  \ | /	    |			  |	\ | /	  |
212169689Skan    |	   \|/	    |			  |	 \|/	  |
213169689Skan   use1	   use2	   use3			 *use1	 use2	 use3
214169689Skan		   use4					 use4
215169689Skan
216169689SkanThe instructions that were changed during the whole optimization are
217169689Skanmarked with asterisk.
218169689Skan
219169689SkanThe result:
220169689Skan
221169689Skandef1 + se1:
222169689Skan[  set ((reg:SI 10) (..def1rhs..))		     ]	 - Deleted
223169689Skan[  set ((reg:DI 100) (sign_extend:DI (reg:SI 10)))   ]	 - Deleted
224169689Skanset ((subreg:SI (reg:DI 100)) (..def3rhs..))		 - Inserted
225169689Skanset ((reg:SI 10) (subreg:SI (reg:DI 100)))		 - Inserted
226169689Skan
227169689Skandef2:
228169689Skanset ((reg:DI 100) (const_int 7))			 - No change
229169689Skan
230169689Skandef3 + se3:
231169689Skan[  set ((reg:SI 20) (..def3rhs..))		     ]	 - Deleted
232169689Skan[  set ((reg:DI 100) (sign_extend:DI (reg:SI 20)))   ]	 - Deleted
233169689Skanset ((reg:DI 100) (sign_extend:DI (..def3rhs..)))	 - Inserted
234169689Skanset ((reg:SI 20) (reg:DI 100))				 - Inserted
235169689Skan
236169689Skanuse1:
237169689Skan[  set ((reg:CC...) (compare:CC (reg:DI 100) (...))) ]	 - Deleted
238169689Skanset ((reg:CC...)					 - Inserted
239169689Skan     (compare:CC (subreg:SI (reg:DI 100)) (...)))
240169689Skan
241169689Skanuse2, use3, use4:
242169689Skanset ((...) (reg:DI 100))				 - No change
243169689Skan
244169689Skanse:							 - Inserted
245169689Skanset ((reg:DI 100) (sign_extend:DI ((subreg:SI (reg:DI 100)))))
246169689Skan
247169689SkanNote: Most of the simple move instructions that were inserted will be
248169689Skan      trivially dead and therefore eliminated.
249169689Skan
250169689SkanThe implementation outline:
251169689Skan---------------------------
252169689SkanSome definitions:
253169689Skan   A web is RELEVANT if at the end of phase 1, his leader's
254169689Skan     relevancy is {ZERO, SIGN}_EXTENDED_DEF.  The source_mode of
255169689Skan     the web is the source_mode of his leader.
256169689Skan   A definition is a candidate for the optimization if it is part
257169689Skan     of a RELEVANT web and his local source_mode is not narrower
258169689Skan     then the source_mode of its web.
259169689Skan   A use is a candidate for the optimization if it is part of a
260169689Skan     RELEVANT web.
261169689Skan   A simple explicit extension is a single set instruction that
262169689Skan     extends a register (or a subregister) to a register (or
263169689Skan     subregister).
264169689Skan   A complex explicit extension is an explicit extension instruction
265169689Skan     that is not simple.
266169689Skan   A def extension is a simple explicit extension that is
267169689Skan     also a candidate for the optimization.  This extension is part
268169689Skan     of the instruction stream, it is not generated by this
269169689Skan     optimization.
270169689Skan   A use extension is a simple explicit extension that is generated
271169689Skan     and stored for candidate use during this optimization.  It is
272169689Skan     not emitted to the instruction stream till the last phase of
273169689Skan     the optimization.
274169689Skan   A reference is an instruction that satisfy at least on of these
275169689Skan     criteria:
276169689Skan     - It contains a definition with EXTENDED_DEF relevancy in a RELEVANT web.
277169689Skan     - It is followed by a def extension.
278169689Skan     - It contains a candidate use.
279169689Skan
280169689SkanPhase 1: Propagate extensions to uses.
281169689Skan  In this phase, we find candidate extensions for the optimization
282169689Skan  and we generate (but not emit) proper extensions "right before the
283169689Skan  uses".
284169689Skan
285169689Skan  a. Build a DF object.
286169689Skan  b. Traverse over all the instructions that contains a definition
287169689Skan     and set their local relevancy and local source_mode like this:
288169689Skan     - If the instruction is a simple explicit extension instruction,
289169689Skan       mark it as {ZERO, SIGN}_EXTENDED_DEF according to the extension
290169689Skan       type and mark its source_mode to be the mode of the quantity
291169689Skan       that is been extended.
292169689Skan     - Otherwise, If the instruction has an implicit extension,
293169689Skan       which means that its high part is an extension of its low part,
294169689Skan       or if it is a complicated explicit extension, mark it as
295169689Skan       EXTENDED_DEF and set its source_mode to be the narrowest
296169689Skan       mode that is been extended in the instruction.
297169689Skan  c. Traverse over all the instructions that contains a use and set
298169689Skan     their local relevancy to RELEVANT_USE (except for few corner
299169689Skan     cases).
300169689Skan  d. Produce the web.  During union of two entries, update the
301169689Skan     relevancy and source_mode of the leader.  There are two major
302169689Skan     guide lines for this update:
303169689Skan     - If one of the entries is NOT_RELEVANT, mark the leader
304169689Skan       NOT_RELEVANT.
305169689Skan     - If one is ZERO_EXTENDED_DEF and the other is SIGN_EXTENDED_DEF
306169689Skan       (or vice versa) mark the leader as NOT_RELEVANT.  We don't
307169689Skan       handle this kind of mixed webs.
308169689Skan     (For more details about this update process,
309169689Skan      see see_update_leader_extra_info ()).
310169689Skan  e. Generate uses extensions according to the relevancy and
311169689Skan     source_mode of the webs.
312169689Skan
313169689SkanPhase 2: Merge and eliminate locally redundant extensions.
314169689Skan  In this phase, we try to merge def extensions and use
315169689Skan  extensions with their references, and eliminate redundant extensions
316169689Skan  in the same basic block.
317169689Skan
318169689Skan  Traverse over all the references.  Do this in basic block number and
319169689Skan  luid number forward order.
320169689Skan  For each reference do:
321169689Skan    a. Peephole optimization - try to merge it with all its
322169689Skan       def extensions and use extensions in the following
323169689Skan       order:
324169689Skan       - Try to merge only the def extensions, one by one.
325169689Skan       - Try to merge only the use extensions, one by one.
326169689Skan       - Try to merge any couple of use extensions simultaneously.
327169689Skan       - Try to merge any def extension with one or two uses
328169689Skan	 extensions simultaneously.
329169689Skan    b. Handle each EXTENDED_DEF in it as if it was already merged with
330169689Skan       an extension.
331169689Skan
332169689Skan  During the merge process we save the following data for each
333169689Skan  register in each basic block:
334169689Skan    a. The first instruction that defines the register in the basic
335169689Skan       block.
336169689Skan    b. The last instruction that defines the register in the basic
337169689Skan       block.
338169689Skan    c. The first extension of this register before the first
339169689Skan       instruction that defines it in the basic block.
340169689Skan    c. The first extension of this register after the last
341169689Skan       instruction that defines it in the basic block.
342169689Skan  This data will help us eliminate (or more precisely, not generate)
343169689Skan  locally redundant extensions, and will be useful in the next stage.
344169689Skan
345169689Skan  While merging extensions with their reference there are 4 possible
346169689Skan  situations:
347169689Skan    a. A use extension was merged with the reference:
348169689Skan       Delete the extension instruction and save the merged reference
349169689Skan       for phase 4.  (For details, see see_use_extension_merged ())
350169689Skan    b. A use extension failed to be merged with the reference:
351169689Skan       If there is already such an extension in the same basic block
352169689Skan       and it is not dead at this point, delete the unmerged extension
353169689Skan       (it is locally redundant), otherwise properly update the above
354169689Skan       basic block data.
355169689Skan       (For details, see see_merge_one_use_extension ())
356169689Skan    c. A def extension was merged with the reference:
357169689Skan       Mark this extension as a merged_def extension and properly
358169689Skan       update the above basic block data.
359169689Skan       (For details, see see_merge_one_def_extension ())
360169689Skan    d. A def extension failed to be merged with the reference:
361169689Skan       Replace the definition of the NARROWmode register in the
362169689Skan       reference with the proper subreg of WIDEmode register and save
363169689Skan       the result as a merged reference.  Also, properly update the
364169689Skan       the above basic block data.
365169689Skan       (For details, see see_def_extension_not_merged ())
366169689Skan
367169689SkanPhase 3: Eliminate globally redundant extensions.
368169689SkanIn this phase, we set the bit vectors input of the edge based LCM
369169689Skanusing the recorded data on the registers in each basic block.
370169689SkanWe also save pointers for all the anticipatable and available
371169689Skanoccurrences of the relevant extensions.  Then we run the LCM.
372169689Skan
373169689Skan  a. Initialize the comp, antloc, kill bit vectors to zero and the
374169689Skan     transp bit vector to ones.
375169689Skan
376169689Skan  b. Traverse over all the references.  Do this in basic block number
377169689Skan     and luid number forward order.  For each reference:
378169689Skan     - Go over all its use extensions.  For each such extension -
379169689Skan	 If it is not dead from the beginning of the basic block SET
380169689Skan	   the antloc bit of the current extension in the current
381169689Skan	   basic block bits.
382169689Skan	 If it is not dead till the end of the basic block SET the
383169689Skan	   comp bit of the current extension in the current basic
384169689Skan	   block bits.
385169689Skan     - Go over all its def extensions that were merged with
386169689Skan       it.  For each such extension -
387169689Skan	 If it is not dead till the end of the basic block SET the
388169689Skan  	   comp bit of the current extension in the current basic
389169689Skan	   block bits.
390169689Skan	 RESET the proper transp and kill bits.
391169689Skan     - Go over all its def extensions that were not merged
392169689Skan       with it.  For each such extension -
393169689Skan	 RESET the transp bit and SET the kill bit of the current
394169689Skan	 extension in the current basic block bits.
395169689Skan
396169689Skan  c. Run the edge based LCM.
397169689Skan
398169689SkanPhase 4: Commit changes to the insn stream.
399169689SkanThis is the only phase that actually changes the instruction stream.
400169689SkanUp to this point the optimization could be aborted at any time.
401169689SkanHere we insert extensions at their best placements and delete the
402169689Skanredundant ones according to the output of the LCM.  We also replace
403169689Skansome of the instructions according to the second phase merges results.
404169689Skan
405169689Skan  a. Use the pre_delete_map (from the output of the LCM) in order to
406169689Skan     delete redundant extensions.  This will prevent them from been
407169689Skan     emitted in the first place.
408169689Skan
409169689Skan  b. Insert extensions on edges where needed according to
410169689Skan     pre_insert_map and edge_list (from the output of the LCM).
411169689Skan
412169689Skan  c. For each reference do-
413169689Skan     - Emit all the uses extensions that were not deleted until now,
414169689Skan       right before the reference.
415169689Skan     - Delete all the merged and unmerged def extensions from
416169689Skan       the instruction stream.
417169689Skan     - Replace the reference with the merged one, if exist.
418169689Skan
419169689SkanThe implementation consists of four data structures:
420169689Skan- Data structure I
421169689Skan  Purpose: To handle the relevancy of the uses, definitions and webs.
422169689Skan  Relevant structures: web_entry (from df.h), see_entry_extra_info.
423169689Skan  Details: This is a disjoint-set data structure.  Most of its functions are
424169689Skan	   implemented in web.c.  Each definition and use in the code are
425169689Skan	   elements.  A web_entry structure is allocated for each element to
426169689Skan	   hold the element's relevancy and source_mode.  The union rules are
427169689Skan	   defined in see_update_leader_extra_info ().
428169689Skan- Data structure II
429169689Skan  Purpose: To store references and their extensions (uses and defs)
430169689Skan	   and to enable traverse over these references according to basic
431169689Skan	   block order.
432169689Skan  Relevant structure: see_ref_s.
433169689Skan  Details: This data structure consists of an array of splay trees.  One splay
434169689Skan	   tree for each basic block.  The splay tree nodes are references and
435169689Skan	   the keys are the luids of the references.
436169689Skan	   A see_ref_s structure is allocated for each reference.  It holds the
437169689Skan	   reference itself, its def and uses extensions and later the merged
438169689Skan	   version of the reference.
439169689Skan	   Using this data structure we can traverse over all the references of
440169689Skan	   a basic block and their extensions in forward order.
441169689Skan- Data structure III.
442169689Skan  Purpose: To store local properties of registers for each basic block.
443169689Skan	   This data will later help us build the LCM sbitmap_vectors
444169689Skan	   input.
445169689Skan  Relevant structure: see_register_properties.
446169689Skan  Details: This data structure consists of an array of hash tables.  One hash
447169689Skan	   for each basic block.  The hash node are a register properties
448169689Skan	   and the keys are the numbers of the registers.
449169689Skan	   A see_register_properties structure is allocated for each register
450169689Skan	   that we might be interested in its properties.
451169689Skan	   Using this data structure we can easily find the properties of a
452169689Skan	   register in a specific basic block.  This is necessary for locally
453169689Skan	   redundancy elimination and for setting up the LCM input.
454169689Skan- Data structure IV.
455169689Skan  Purpose: To store the extensions that are candidate for PRE and their
456169689Skan	   anticipatable and available occurrences.
457169689Skan  Relevant structure: see_occr, see_pre_extension_expr.
458169689Skan  Details: This data structure is a hash tables.  Its nodes are the extensions
459169689Skan	   that are candidate for PRE.
460169689Skan	   A see_pre_extension_expr structure is allocated for each candidate
461169689Skan	   extension.  It holds a copy of the extension and a linked list of all
462169689Skan	   the anticipatable and available occurrences of it.
463169689Skan	   We use this data structure when we read the output of the LCM.  */
464169689Skan
465169689Skan#include "config.h"
466169689Skan#include "system.h"
467169689Skan#include "coretypes.h"
468169689Skan#include "tm.h"
469169689Skan
470169689Skan#include "obstack.h"
471169689Skan#include "rtl.h"
472169689Skan#include "output.h"
473169689Skan#include "df.h"
474169689Skan#include "insn-config.h"
475169689Skan#include "recog.h"
476169689Skan#include "expr.h"
477169689Skan#include "splay-tree.h"
478169689Skan#include "hashtab.h"
479169689Skan#include "regs.h"
480169689Skan#include "timevar.h"
481169689Skan#include "tree-pass.h"
482169689Skan
483169689Skan/* Used to classify defs and uses according to relevancy.  */
484169689Skanenum entry_type {
485169689Skan  NOT_RELEVANT,
486169689Skan  SIGN_EXTENDED_DEF,
487169689Skan  ZERO_EXTENDED_DEF,
488169689Skan  EXTENDED_DEF,
489169689Skan  RELEVANT_USE
490169689Skan};
491169689Skan
492169689Skan/* Used to classify extensions in relevant webs.  */
493169689Skanenum extension_type {
494169689Skan  DEF_EXTENSION,
495169689Skan  EXPLICIT_DEF_EXTENSION,
496169689Skan  IMPLICIT_DEF_EXTENSION,
497169689Skan  USE_EXTENSION
498169689Skan};
499169689Skan
500169689Skan/* Global data structures and flags.  */
501169689Skan
502169689Skan/* This structure will be assigned for each web_entry structure (defined
503169689Skan   in df.h).  It is placed in the extra_info field of a web_entry and holds the
504169689Skan   relevancy and source mode of the web_entry.  */
505169689Skan
506169689Skanstruct see_entry_extra_info
507169689Skan{
508169689Skan  /* The relevancy of the ref.  */
509169689Skan  enum entry_type relevancy;
510169689Skan  /* The relevancy of the ref.
511169689Skan     This field is updated only once - when this structure is created.  */
512169689Skan  enum entry_type local_relevancy;
513169689Skan  /* The source register mode.  */
514169689Skan  enum machine_mode source_mode;
515169689Skan  /* This field is used only if the relevancy is ZERO/SIGN_EXTENDED_DEF.
516169689Skan     It is updated only once when this structure is created.  */
517169689Skan  enum machine_mode local_source_mode;
518169689Skan  /* This field is used only if the relevancy is EXTENDED_DEF.
519169689Skan     It holds the narrowest mode that is sign extended.  */
520169689Skan  enum machine_mode source_mode_signed;
521169689Skan  /* This field is used only if the relevancy is EXTENDED_DEF.
522169689Skan     It holds the narrowest mode that is zero extended.  */
523169689Skan  enum machine_mode source_mode_unsigned;
524169689Skan};
525169689Skan
526169689Skan/* There is one such structure for every reference.  It stores the reference
527169689Skan   itself as well as its extensions (uses and definitions).
528169689Skan   Used as the value in splay_tree see_bb_splay_ar[].  */
529169689Skanstruct see_ref_s
530169689Skan{
531169689Skan  /* The luid of the insn.  */
532169689Skan  unsigned int luid;
533169689Skan  /* The insn of the ref.  */
534169689Skan  rtx insn;
535169689Skan  /* The merged insn that was formed from the reference's insn and extensions.
536169689Skan     If all merges failed, it remains NULL.  */
537169689Skan  rtx merged_insn;
538169689Skan  /* The def extensions of the reference that were not merged with
539169689Skan     it.  */
540169689Skan  htab_t unmerged_def_se_hash;
541169689Skan  /* The def extensions of the reference that were merged with
542169689Skan     it.  Implicit extensions of the reference will be stored here too.  */
543169689Skan  htab_t merged_def_se_hash;
544169689Skan  /* The uses extensions of reference.  */
545169689Skan  htab_t use_se_hash;
546169689Skan};
547169689Skan
548169689Skan/* There is one such structure for every relevant extended register in a
549169689Skan   specific basic block.  This data will help us build the LCM sbitmap_vectors
550169689Skan   input.  */
551169689Skanstruct see_register_properties
552169689Skan{
553169689Skan  /* The register number.  */
554169689Skan  unsigned int regno;
555169689Skan  /* The last luid of the reference that defines this register in this basic
556169689Skan     block.  */
557169689Skan  int last_def;
558169689Skan  /* The luid of the reference that has the first extension of this register
559169689Skan     that appears before any definition in this basic block.  */
560169689Skan  int first_se_before_any_def;
561169689Skan  /* The luid of the reference that has the first extension of this register
562169689Skan     that appears after the last definition in this basic block.  */
563169689Skan  int first_se_after_last_def;
564169689Skan};
565169689Skan
566169689Skan/* Occurrence of an expression.
567169689Skan   There must be at most one available occurrence and at most one anticipatable
568169689Skan   occurrence per basic block.  */
569169689Skanstruct see_occr
570169689Skan{
571169689Skan  /* Next occurrence of this expression.  */
572169689Skan  struct see_occr *next;
573169689Skan  /* The insn that computes the expression.  */
574169689Skan  rtx insn;
575169689Skan  int block_num;
576169689Skan};
577169689Skan
578169689Skan/* There is one such structure for every relevant extension expression.
579169689Skan   It holds a copy of this extension instruction as well as a linked lists of
580169689Skan   pointers to all the antic and avail occurrences of it.  */
581169689Skanstruct see_pre_extension_expr
582169689Skan{
583169689Skan  /* A copy of the extension instruction.  */
584169689Skan  rtx se_insn;
585169689Skan  /* Index in the available expression bitmaps.  */
586169689Skan  int bitmap_index;
587169689Skan  /* List of anticipatable occurrences in basic blocks in the function.
588169689Skan     An "anticipatable occurrence" is the first occurrence in the basic block,
589169689Skan     the operands are not modified in the basic block prior to the occurrence
590169689Skan     and the output is not used between the start of the block and the
591169689Skan     occurrence.  */
592169689Skan  struct see_occr *antic_occr;
593169689Skan  /* List of available occurrence in basic blocks in the function.
594169689Skan     An "available occurrence" is the last occurrence in the basic block and
595169689Skan     the operands are not modified by following statements in the basic block
596169689Skan     [including this insn].  */
597169689Skan  struct see_occr *avail_occr;
598169689Skan};
599169689Skan
600169689Skan/* Helper structure for the note_uses and see_replace_src functions.  */
601169689Skanstruct see_replace_data
602169689Skan{
603169689Skan  rtx from;
604169689Skan  rtx to;
605169689Skan};
606169689Skan
607169689Skan/* Helper structure for the note_uses and see_mentioned_reg functions.  */
608169689Skanstruct see_mentioned_reg_data
609169689Skan{
610169689Skan  rtx reg;
611169689Skan  bool mentioned;
612169689Skan};
613169689Skan
614169689Skan/* A data flow object that will be created once and used throughout the
615169689Skan   optimization.  */
616169689Skanstatic struct df *df = NULL;
617169689Skan/* An array of web_entries.  The i'th definition in the df object is associated
618169689Skan   with def_entry[i]  */
619169689Skanstatic struct web_entry *def_entry = NULL;
620169689Skan/* An array of web_entries.  The i'th use in the df object is associated with
621169689Skan   use_entry[i]  */
622169689Skanstatic struct web_entry *use_entry = NULL;
623169689Skan/* Array of splay_trees.
624169689Skan   see_bb_splay_ar[i] refers to the splay tree of the i'th basic block.
625169689Skan   The splay tree will hold see_ref_s structures.  The key is the luid
626169689Skan   of the insn.  This way we can traverse over the references of each basic
627169689Skan   block in forward or backward order.  */
628169689Skanstatic splay_tree *see_bb_splay_ar = NULL;
629169689Skan/* Array of hashes.
630169689Skan   see_bb_hash_ar[i] refers to the hash of the i'th basic block.
631169689Skan   The hash will hold see_register_properties structure.  The key is regno.  */
632169689Skanstatic htab_t *see_bb_hash_ar = NULL;
633169689Skan/* Hash table that holds a copy of all the extensions.  The key is the right
634169689Skan   hand side of the se_insn field.  */
635169689Skanstatic htab_t see_pre_extension_hash = NULL;
636169689Skan
637169689Skan/* Local LCM properties of expressions.  */
638169689Skan/* Nonzero for expressions that are transparent in the block.  */
639169689Skanstatic sbitmap *transp = NULL;
640169689Skan/* Nonzero for expressions that are computed (available) in the block.  */
641169689Skanstatic sbitmap *comp = NULL;
642169689Skan/* Nonzero for expressions that are locally anticipatable in the block.  */
643169689Skanstatic sbitmap *antloc = NULL;
644169689Skan/* Nonzero for expressions that are locally killed in the block.  */
645169689Skanstatic sbitmap *ae_kill = NULL;
646169689Skan/* Nonzero for expressions which should be inserted on a specific edge.  */
647169689Skanstatic sbitmap *pre_insert_map = NULL;
648169689Skan/* Nonzero for expressions which should be deleted in a specific block.  */
649169689Skanstatic sbitmap *pre_delete_map = NULL;
650169689Skan/* Contains the edge_list returned by pre_edge_lcm.  */
651169689Skanstatic struct edge_list *edge_list = NULL;
652169689Skan/* Records the last basic block at the beginning of the optimization.  */
653169689Skanstatic int last_bb;
654169689Skan/* Records the number of uses at the beginning of the optimization.  */
655169689Skanstatic unsigned int uses_num;
656169689Skan/* Records the number of definitions at the beginning of the optimization.  */
657169689Skanstatic unsigned int defs_num;
658169689Skan
659169689Skan#define ENTRY_EI(ENTRY) ((struct see_entry_extra_info *) (ENTRY)->extra_info)
660169689Skan
661169689Skan/* Functions implementation.  */
662169689Skan
663169689Skan/*  Verifies that EXTENSION's pattern is this:
664169689Skan
665169689Skan    set (reg/subreg reg1) (sign/zero_extend:WIDEmode (reg/subreg reg2))
666169689Skan
667169689Skan    If it doesn't have the expected pattern return NULL.
668169689Skan    Otherwise, if RETURN_DEST_REG is set, return reg1 else return reg2.  */
669169689Skan
670169689Skanstatic rtx
671169689Skansee_get_extension_reg (rtx extension, bool return_dest_reg)
672169689Skan{
673169689Skan  rtx set, rhs, lhs;
674169689Skan  rtx reg1 = NULL;
675169689Skan  rtx reg2 = NULL;
676169689Skan
677169689Skan  /* Parallel pattern for extension not supported for the moment.  */
678169689Skan  if (GET_CODE (PATTERN (extension)) == PARALLEL)
679169689Skan    return NULL;
680169689Skan
681169689Skan  set = single_set (extension);
682169689Skan  if (!set)
683169689Skan    return NULL;
684169689Skan  lhs = SET_DEST (set);
685169689Skan  rhs = SET_SRC (set);
686169689Skan
687169689Skan  if (REG_P (lhs))
688169689Skan    reg1 = lhs;
689169689Skan  else if (REG_P (SUBREG_REG (lhs)))
690169689Skan    reg1 = SUBREG_REG (lhs);
691169689Skan  else
692169689Skan    return NULL;
693169689Skan
694169689Skan  if (GET_CODE (rhs) != SIGN_EXTEND && GET_CODE (rhs) != ZERO_EXTEND)
695169689Skan    return NULL;
696169689Skan
697169689Skan  rhs = XEXP (rhs, 0);
698169689Skan  if (REG_P (rhs))
699169689Skan    reg2 = rhs;
700169689Skan  else if (REG_P (SUBREG_REG (rhs)))
701169689Skan    reg2 = SUBREG_REG (rhs);
702169689Skan  else
703169689Skan    return NULL;
704169689Skan
705169689Skan  if (return_dest_reg)
706169689Skan    return reg1;
707169689Skan  return reg2;
708169689Skan}
709169689Skan
710169689Skan/*  Verifies that EXTENSION's pattern is this:
711169689Skan
712169689Skan    set (reg/subreg reg1) (sign/zero_extend: (...expr...)
713169689Skan
714169689Skan    If it doesn't have the expected pattern return UNKNOWN.
715169689Skan    Otherwise, set SOURCE_MODE to be the mode of the extended expr and return
716169689Skan    the rtx code of the extension.  */
717169689Skan
718169689Skanstatic enum rtx_code
719169689Skansee_get_extension_data (rtx extension, enum machine_mode *source_mode)
720169689Skan{
721169689Skan  rtx rhs, lhs, set;
722169689Skan
723169689Skan  if (!extension || !INSN_P (extension))
724169689Skan    return UNKNOWN;
725169689Skan
726169689Skan  /* Parallel pattern for extension not supported for the moment.  */
727169689Skan  if (GET_CODE (PATTERN (extension)) == PARALLEL)
728169689Skan    return NOT_RELEVANT;
729169689Skan
730169689Skan  set = single_set (extension);
731169689Skan  if (!set)
732169689Skan    return NOT_RELEVANT;
733169689Skan  rhs = SET_SRC (set);
734169689Skan  lhs = SET_DEST (set);
735169689Skan
736169689Skan  /* Don't handle extensions to something other then register or
737169689Skan     subregister.  */
738169689Skan  if (!REG_P (lhs) && !SUBREG_REG (lhs))
739169689Skan    return UNKNOWN;
740169689Skan
741169689Skan  if (GET_CODE (rhs) != SIGN_EXTEND && GET_CODE (rhs) != ZERO_EXTEND)
742169689Skan    return UNKNOWN;
743169689Skan
744169689Skan  if (!REG_P (XEXP (rhs, 0))
745169689Skan      && !(GET_CODE (XEXP (rhs, 0)) == SUBREG
746169689Skan	   && REG_P (SUBREG_REG (XEXP (rhs, 0)))))
747169689Skan    return UNKNOWN;
748169689Skan
749169689Skan  *source_mode = GET_MODE (XEXP (rhs, 0));
750169689Skan
751169689Skan  if (GET_CODE (rhs) == SIGN_EXTEND)
752169689Skan    return SIGN_EXTEND;
753169689Skan  return ZERO_EXTEND;
754169689Skan}
755169689Skan
756169689Skan
757169689Skan/* Generate instruction with the pattern:
758169689Skan   set ((reg r) (sign/zero_extend (subreg:mode (reg r))))
759169689Skan   (the register r on both sides of the set is the same register).
760169689Skan   And recognize it.
761169689Skan   If the recognition failed, this is very bad, return NULL (This will abort
762169689Skan   the entire optimization).
763169689Skan   Otherwise, return the generated instruction.  */
764169689Skan
765169689Skanstatic rtx
766169689Skansee_gen_normalized_extension (rtx reg, enum rtx_code extension_code,
767169689Skan   			      enum machine_mode mode)
768169689Skan{
769169689Skan  rtx subreg, insn;
770169689Skan  rtx extension = NULL;
771169689Skan
772169689Skan  if (!reg
773169689Skan      || !REG_P (reg)
774169689Skan      || (extension_code != SIGN_EXTEND && extension_code != ZERO_EXTEND))
775169689Skan    return NULL;
776169689Skan
777169689Skan  subreg = gen_lowpart_SUBREG (mode, reg);
778169689Skan  if (extension_code == SIGN_EXTEND)
779169689Skan    extension = gen_rtx_SIGN_EXTEND (GET_MODE (reg), subreg);
780169689Skan  else
781169689Skan    extension = gen_rtx_ZERO_EXTEND (GET_MODE (reg), subreg);
782169689Skan
783169689Skan  start_sequence ();
784169689Skan  emit_insn (gen_rtx_SET (VOIDmode, reg, extension));
785169689Skan  insn = get_insns ();
786169689Skan  end_sequence ();
787169689Skan
788169689Skan  if (insn_invalid_p (insn))
789169689Skan    /* Recognition failed, this is very bad for this optimization.
790169689Skan       Abort the optimization.  */
791169689Skan    return NULL;
792169689Skan  return insn;
793169689Skan}
794169689Skan
795169689Skan/* Hashes and splay_trees related functions implementation.  */
796169689Skan
797169689Skan/* Helper functions for the pre_extension hash.
798169689Skan   This kind of hash will hold see_pre_extension_expr structures.
799169689Skan
800169689Skan   The key is the right hand side of the se_insn field.
801169689Skan   Note that the se_insn is an expression that looks like:
802169689Skan
803169689Skan   set ((reg:WIDEmode r1) (sign_extend:WIDEmode
804169689Skan			   (subreg:NARROWmode (reg:WIDEmode r2))))  */
805169689Skan
806169689Skan/* Return TRUE if P1 has the same value in its rhs as P2.
807169689Skan   Otherwise, return FALSE.
808169689Skan   P1 and P2 are see_pre_extension_expr structures.  */
809169689Skan
810169689Skanstatic int
811169689Skaneq_descriptor_pre_extension (const void *p1, const void *p2)
812169689Skan{
813169689Skan  const struct see_pre_extension_expr *extension1 = p1;
814169689Skan  const struct see_pre_extension_expr *extension2 = p2;
815169689Skan  rtx set1 = single_set (extension1->se_insn);
816169689Skan  rtx set2 = single_set (extension2->se_insn);
817169689Skan  rtx rhs1, rhs2;
818169689Skan
819169689Skan  gcc_assert (set1 && set2);
820169689Skan  rhs1 = SET_SRC (set1);
821169689Skan  rhs2 = SET_SRC (set2);
822169689Skan
823169689Skan  return rtx_equal_p (rhs1, rhs2);
824169689Skan}
825169689Skan
826169689Skan
827169689Skan/* P is a see_pre_extension_expr struct, use the RHS of the se_insn field.
828169689Skan   Note that the RHS is an expression that looks like this:
829169689Skan   (sign_extend:WIDEmode (subreg:NARROWmode (reg:WIDEmode r)))  */
830169689Skan
831169689Skanstatic hashval_t
832169689Skanhash_descriptor_pre_extension (const void *p)
833169689Skan{
834169689Skan  const struct see_pre_extension_expr *extension = p;
835169689Skan  rtx set = single_set (extension->se_insn);
836169689Skan  rtx rhs;
837169689Skan
838169689Skan  gcc_assert (set);
839169689Skan  rhs = SET_SRC (set);
840169689Skan
841169689Skan  return hash_rtx (rhs, GET_MODE (rhs), 0, NULL, 0);
842169689Skan}
843169689Skan
844169689Skan
845169689Skan/* Free the allocated memory of the current see_pre_extension_expr struct.
846169689Skan
847169689Skan   It frees the two linked list of the occurrences structures.  */
848169689Skan
849169689Skanstatic void
850169689Skanhash_del_pre_extension (void *p)
851169689Skan{
852169689Skan  struct see_pre_extension_expr *extension = p;
853169689Skan  struct see_occr *curr_occr = extension->antic_occr;
854169689Skan  struct see_occr *next_occr = NULL;
855169689Skan
856169689Skan  /*  Free the linked list of the anticipatable occurrences.  */
857169689Skan  while (curr_occr)
858169689Skan    {
859169689Skan      next_occr = curr_occr->next;
860169689Skan      free (curr_occr);
861169689Skan      curr_occr = next_occr;
862169689Skan    }
863169689Skan
864169689Skan  /*  Free the linked list of the available occurrences.  */
865169689Skan  curr_occr = extension->avail_occr;
866169689Skan  while (curr_occr)
867169689Skan    {
868169689Skan      next_occr = curr_occr->next;
869169689Skan      free (curr_occr);
870169689Skan      curr_occr = next_occr;
871169689Skan    }
872169689Skan
873169689Skan  /* Free the see_pre_extension_expr structure itself.  */
874169689Skan  free (extension);
875169689Skan}
876169689Skan
877169689Skan
878169689Skan/* Helper functions for the register_properties hash.
879169689Skan   This kind of hash will hold see_register_properties structures.
880169689Skan
881169689Skan   The value of the key is the regno field of the structure.  */
882169689Skan
883169689Skan/* Return TRUE if P1 has the same value in the regno field as P2.
884169689Skan   Otherwise, return FALSE.
885169689Skan   Where P1 and P2 are see_register_properties structures.  */
886169689Skan
887169689Skanstatic int
888169689Skaneq_descriptor_properties (const void *p1, const void *p2)
889169689Skan{
890169689Skan  const struct see_register_properties *curr_prop1 = p1;
891169689Skan  const struct see_register_properties *curr_prop2 = p2;
892169689Skan
893169689Skan  return curr_prop1->regno == curr_prop2->regno;
894169689Skan}
895169689Skan
896169689Skan
897169689Skan/* P is a see_register_properties struct, use the register number in the
898169689Skan   regno field.  */
899169689Skan
900169689Skanstatic hashval_t
901169689Skanhash_descriptor_properties (const void *p)
902169689Skan{
903169689Skan  const struct see_register_properties *curr_prop = p;
904169689Skan  return curr_prop->regno;
905169689Skan}
906169689Skan
907169689Skan
908169689Skan/* Free the allocated memory of the current see_register_properties struct.  */
909169689Skanstatic void
910169689Skanhash_del_properties (void *p)
911169689Skan{
912169689Skan  struct see_register_properties *curr_prop = p;
913169689Skan  free (curr_prop);
914169689Skan}
915169689Skan
916169689Skan
917169689Skan/* Helper functions for an extension hash.
918169689Skan   This kind of hash will hold insns that look like:
919169689Skan
920169689Skan   set ((reg:WIDEmode r1) (sign_extend:WIDEmode
921169689Skan			   (subreg:NARROWmode (reg:WIDEmode r2))))
922169689Skan   or
923169689Skan   set ((reg:WIDEmode r1) (sign_extend:WIDEmode (reg:NARROWmode r2)))
924169689Skan
925169689Skan   The value of the key is (REGNO (reg:WIDEmode r1))
926169689Skan   It is possible to search this hash in two ways:
927169689Skan   1.  By a register rtx. The Value that is been compared to the keys is the
928169689Skan       REGNO of it.
929169689Skan   2.  By an insn with the above pattern. The Value that is been compared to
930169689Skan       the keys is the REGNO of the reg on the lhs.  */
931169689Skan
932169689Skan/* Return TRUE if P1 has the same value as P2.  Otherwise, return FALSE.
933169689Skan   Where P1 is an insn and P2 is an insn or a register.  */
934169689Skan
935169689Skanstatic int
936169689Skaneq_descriptor_extension (const void *p1, const void *p2)
937169689Skan{
938169689Skan  const rtx insn = (rtx) p1;
939169689Skan  const rtx element = (rtx) p2;
940169689Skan  rtx set1 = single_set (insn);
941169689Skan  rtx dest_reg1;
942169689Skan  rtx set2 = NULL;
943169689Skan  rtx dest_reg2 = NULL;
944169689Skan
945169689Skan  gcc_assert (set1 && element && (REG_P (element) || INSN_P (element)));
946169689Skan
947169689Skan  dest_reg1 = SET_DEST (set1);
948169689Skan
949169689Skan  if (INSN_P (element))
950169689Skan    {
951169689Skan      set2 = single_set (element);
952169689Skan      dest_reg2 = SET_DEST (set2);
953169689Skan    }
954169689Skan  else
955169689Skan    dest_reg2 = element;
956169689Skan
957169689Skan  return REGNO (dest_reg1) == REGNO (dest_reg2);
958169689Skan}
959169689Skan
960169689Skan
961169689Skan/* If P is an insn, use the register number of its lhs
962169689Skan   otherwise, P is a register, use its number.  */
963169689Skan
964169689Skanstatic hashval_t
965169689Skanhash_descriptor_extension (const void *p)
966169689Skan{
967169689Skan  const rtx r = (rtx) p;
968169689Skan  rtx set, lhs;
969169689Skan
970169689Skan  if (r && REG_P (r))
971169689Skan    return REGNO (r);
972169689Skan
973169689Skan  gcc_assert (r && INSN_P (r));
974169689Skan  set = single_set (r);
975169689Skan  gcc_assert (set);
976169689Skan  lhs = SET_DEST (set);
977169689Skan  return REGNO (lhs);
978169689Skan}
979169689Skan
980169689Skan
981169689Skan/* Helper function for a see_bb_splay_ar[i] splay tree.
982169689Skan   It frees all the allocated memory of a struct see_ref_s pointer.
983169689Skan
984169689Skan   VALUE is the value of a splay tree node.  */
985169689Skan
986169689Skanstatic void
987169689Skansee_free_ref_s (splay_tree_value value)
988169689Skan{
989169689Skan  struct see_ref_s *ref_s = (struct see_ref_s *)value;
990169689Skan
991169689Skan  if (ref_s->unmerged_def_se_hash)
992169689Skan    htab_delete (ref_s->unmerged_def_se_hash);
993169689Skan  if (ref_s->merged_def_se_hash)
994169689Skan    htab_delete (ref_s->merged_def_se_hash);
995169689Skan  if (ref_s->use_se_hash)
996169689Skan    htab_delete (ref_s->use_se_hash);
997169689Skan  free (ref_s);
998169689Skan}
999169689Skan
1000169689Skan
1001169689Skan/* Rest of the implementation.  */
1002169689Skan
1003169689Skan/* Search the extension hash for a suitable entry for EXTENSION.
1004169689Skan   TYPE is the type of EXTENSION (USE_EXTENSION or DEF_EXTENSION).
1005169689Skan
1006169689Skan   If TYPE is DEF_EXTENSION we need to normalize EXTENSION before searching the
1007169689Skan   extension hash.
1008169689Skan
1009169689Skan   If a suitable entry was found, return the slot.  Otherwise, store EXTENSION
1010169689Skan   in the hash and return NULL.  */
1011169689Skan
1012169689Skanstatic struct see_pre_extension_expr *
1013169689Skansee_seek_pre_extension_expr (rtx extension, enum extension_type type)
1014169689Skan{
1015169689Skan  struct see_pre_extension_expr **slot_pre_exp, temp_pre_exp;
1016169689Skan  rtx dest_extension_reg = see_get_extension_reg (extension, 1);
1017169689Skan  enum rtx_code extension_code;
1018169689Skan  enum machine_mode source_extension_mode;
1019169689Skan
1020169689Skan  if (type == DEF_EXTENSION)
1021169689Skan    {
1022169689Skan      extension_code = see_get_extension_data (extension,
1023169689Skan					       &source_extension_mode);
1024169689Skan      gcc_assert (extension_code != UNKNOWN);
1025169689Skan      extension =
1026169689Skan	see_gen_normalized_extension (dest_extension_reg, extension_code,
1027169689Skan				      source_extension_mode);
1028169689Skan    }
1029169689Skan  temp_pre_exp.se_insn = extension;
1030169689Skan  slot_pre_exp =
1031169689Skan    (struct see_pre_extension_expr **) htab_find_slot (see_pre_extension_hash,
1032169689Skan							&temp_pre_exp, INSERT);
1033169689Skan  if (*slot_pre_exp == NULL)
1034169689Skan    /* This is the first time this extension instruction is encountered.  Store
1035169689Skan       it in the hash.  */
1036169689Skan    {
1037169689Skan      (*slot_pre_exp) = xmalloc (sizeof (struct see_pre_extension_expr));
1038169689Skan      (*slot_pre_exp)->se_insn = extension;
1039169689Skan      (*slot_pre_exp)->bitmap_index =
1040169689Skan	(htab_elements (see_pre_extension_hash) - 1);
1041169689Skan      (*slot_pre_exp)->antic_occr = NULL;
1042169689Skan      (*slot_pre_exp)->avail_occr = NULL;
1043169689Skan      return NULL;
1044169689Skan    }
1045169689Skan  return *slot_pre_exp;
1046169689Skan}
1047169689Skan
1048169689Skan
1049169689Skan/* This function defines how to update the extra_info of the web_entry.
1050169689Skan
1051169689Skan   FIRST is the pointer of the extra_info of the first web_entry.
1052169689Skan   SECOND is the pointer of the extra_info of the second web_entry.
1053169689Skan   The first web_entry will be the predecessor (leader) of the second web_entry
1054169689Skan   after the union.
1055169689Skan
1056169689Skan   Return true if FIRST and SECOND points to the same web entry structure and
1057169689Skan   nothing is done.  Otherwise, return false.  */
1058169689Skan
1059169689Skanstatic bool
1060169689Skansee_update_leader_extra_info (struct web_entry *first, struct web_entry *second)
1061169689Skan{
1062169689Skan  struct see_entry_extra_info *first_ei, *second_ei;
1063169689Skan
1064169689Skan  first = unionfind_root (first);
1065169689Skan  second = unionfind_root (second);
1066169689Skan
1067169689Skan  if (unionfind_union (first, second))
1068169689Skan    return true;
1069169689Skan
1070169689Skan  first_ei = (struct see_entry_extra_info *) first->extra_info;
1071169689Skan  second_ei = (struct see_entry_extra_info *) second->extra_info;
1072169689Skan
1073169689Skan  gcc_assert (first_ei && second_ei);
1074169689Skan
1075169689Skan  if (second_ei->relevancy == NOT_RELEVANT)
1076169689Skan    {
1077169689Skan      first_ei->relevancy = NOT_RELEVANT;
1078169689Skan      return false;
1079169689Skan    }
1080169689Skan  switch (first_ei->relevancy)
1081169689Skan    {
1082169689Skan    case NOT_RELEVANT:
1083169689Skan      break;
1084169689Skan    case RELEVANT_USE:
1085169689Skan      switch (second_ei->relevancy)
1086169689Skan	{
1087169689Skan	case RELEVANT_USE:
1088169689Skan	  break;
1089169689Skan	case EXTENDED_DEF:
1090169689Skan	  first_ei->relevancy = second_ei->relevancy;
1091169689Skan	  first_ei->source_mode_signed = second_ei->source_mode_signed;
1092169689Skan	  first_ei->source_mode_unsigned = second_ei->source_mode_unsigned;
1093169689Skan	  break;
1094169689Skan	case SIGN_EXTENDED_DEF:
1095169689Skan	case ZERO_EXTENDED_DEF:
1096169689Skan	  first_ei->relevancy = second_ei->relevancy;
1097169689Skan	  first_ei->source_mode = second_ei->source_mode;
1098169689Skan	  break;
1099169689Skan	default:
1100169689Skan	  gcc_unreachable ();
1101169689Skan	}
1102169689Skan      break;
1103169689Skan    case SIGN_EXTENDED_DEF:
1104169689Skan      switch (second_ei->relevancy)
1105169689Skan	{
1106169689Skan	case SIGN_EXTENDED_DEF:
1107169689Skan	  /* The mode of the root should be the wider one in this case.  */
1108169689Skan	  first_ei->source_mode =
1109169689Skan	    (first_ei->source_mode > second_ei->source_mode) ?
1110169689Skan	    first_ei->source_mode : second_ei->source_mode;
1111169689Skan	  break;
1112169689Skan	case RELEVANT_USE:
1113169689Skan	  break;
1114169689Skan	case ZERO_EXTENDED_DEF:
1115169689Skan	  /* Don't mix webs with zero extend and sign extend.  */
1116169689Skan	  first_ei->relevancy = NOT_RELEVANT;
1117169689Skan	  break;
1118169689Skan	case EXTENDED_DEF:
1119169689Skan	  if (second_ei->source_mode_signed == MAX_MACHINE_MODE)
1120169689Skan	    first_ei->relevancy = NOT_RELEVANT;
1121169689Skan	  else
1122169689Skan	    /* The mode of the root should be the wider one in this case.  */
1123169689Skan	    first_ei->source_mode =
1124169689Skan	      (first_ei->source_mode > second_ei->source_mode_signed) ?
1125169689Skan	      first_ei->source_mode : second_ei->source_mode_signed;
1126169689Skan	  break;
1127169689Skan	default:
1128169689Skan	  gcc_unreachable ();
1129169689Skan	}
1130169689Skan      break;
1131169689Skan    /* This case is similar to the previous one, with little changes.  */
1132169689Skan    case ZERO_EXTENDED_DEF:
1133169689Skan      switch (second_ei->relevancy)
1134169689Skan	{
1135169689Skan	case SIGN_EXTENDED_DEF:
1136169689Skan	  /* Don't mix webs with zero extend and sign extend.  */
1137169689Skan	  first_ei->relevancy = NOT_RELEVANT;
1138169689Skan	  break;
1139169689Skan	case RELEVANT_USE:
1140169689Skan	  break;
1141169689Skan	case ZERO_EXTENDED_DEF:
1142169689Skan	  /* The mode of the root should be the wider one in this case.  */
1143169689Skan	  first_ei->source_mode =
1144169689Skan	    (first_ei->source_mode > second_ei->source_mode) ?
1145169689Skan	    first_ei->source_mode : second_ei->source_mode;
1146169689Skan	  break;
1147169689Skan	case EXTENDED_DEF:
1148169689Skan	  if (second_ei->source_mode_unsigned == MAX_MACHINE_MODE)
1149169689Skan	    first_ei->relevancy = NOT_RELEVANT;
1150169689Skan	  else
1151169689Skan	    /* The mode of the root should be the wider one in this case.  */
1152169689Skan	    first_ei->source_mode =
1153169689Skan	      (first_ei->source_mode > second_ei->source_mode_unsigned) ?
1154169689Skan	      first_ei->source_mode : second_ei->source_mode_unsigned;
1155169689Skan	  break;
1156169689Skan	default:
1157169689Skan	  gcc_unreachable ();
1158169689Skan	}
1159169689Skan      break;
1160169689Skan    case EXTENDED_DEF:
1161169689Skan      if (first_ei->source_mode_signed != MAX_MACHINE_MODE
1162169689Skan	  && first_ei->source_mode_unsigned != MAX_MACHINE_MODE)
1163169689Skan	{
1164169689Skan	  switch (second_ei->relevancy)
1165169689Skan	    {
1166169689Skan	    case SIGN_EXTENDED_DEF:
1167169689Skan	      first_ei->relevancy = SIGN_EXTENDED_DEF;
1168169689Skan	      first_ei->source_mode =
1169169689Skan		(first_ei->source_mode_signed > second_ei->source_mode) ?
1170169689Skan		first_ei->source_mode_signed : second_ei->source_mode;
1171169689Skan	      break;
1172169689Skan	    case RELEVANT_USE:
1173169689Skan	      break;
1174169689Skan	    case ZERO_EXTENDED_DEF:
1175169689Skan	      first_ei->relevancy = ZERO_EXTENDED_DEF;
1176169689Skan	      first_ei->source_mode =
1177169689Skan		(first_ei->source_mode_unsigned > second_ei->source_mode) ?
1178169689Skan		first_ei->source_mode_unsigned : second_ei->source_mode;
1179169689Skan	      break;
1180169689Skan	    case EXTENDED_DEF:
1181169689Skan	      if (second_ei->source_mode_unsigned != MAX_MACHINE_MODE)
1182169689Skan		first_ei->source_mode_unsigned =
1183169689Skan		  (first_ei->source_mode_unsigned >
1184169689Skan		  second_ei->source_mode_unsigned) ?
1185169689Skan		  first_ei->source_mode_unsigned :
1186169689Skan		  second_ei->source_mode_unsigned;
1187169689Skan	      if (second_ei->source_mode_signed != MAX_MACHINE_MODE)
1188169689Skan		first_ei->source_mode_signed =
1189169689Skan		  (first_ei->source_mode_signed >
1190169689Skan		  second_ei->source_mode_signed) ?
1191169689Skan		  first_ei->source_mode_signed : second_ei->source_mode_signed;
1192169689Skan	      break;
1193169689Skan	    default:
1194169689Skan	      gcc_unreachable ();
1195169689Skan	    }
1196169689Skan	}
1197169689Skan      else if (first_ei->source_mode_signed == MAX_MACHINE_MODE)
1198169689Skan	{
1199169689Skan	  gcc_assert (first_ei->source_mode_unsigned != MAX_MACHINE_MODE);
1200169689Skan	  switch (second_ei->relevancy)
1201169689Skan	    {
1202169689Skan	    case SIGN_EXTENDED_DEF:
1203169689Skan	      first_ei->relevancy = NOT_RELEVANT;
1204169689Skan	      break;
1205169689Skan	    case RELEVANT_USE:
1206169689Skan	      break;
1207169689Skan	    case ZERO_EXTENDED_DEF:
1208169689Skan	      first_ei->relevancy = ZERO_EXTENDED_DEF;
1209169689Skan	      first_ei->source_mode =
1210169689Skan		(first_ei->source_mode_unsigned > second_ei->source_mode) ?
1211169689Skan		first_ei->source_mode_unsigned : second_ei->source_mode;
1212169689Skan	      break;
1213169689Skan	    case EXTENDED_DEF:
1214169689Skan	      if (second_ei->source_mode_unsigned == MAX_MACHINE_MODE)
1215169689Skan		first_ei->relevancy = NOT_RELEVANT;
1216169689Skan	      else
1217169689Skan		first_ei->source_mode_unsigned =
1218169689Skan		  (first_ei->source_mode_unsigned >
1219169689Skan		  second_ei->source_mode_unsigned) ?
1220169689Skan		  first_ei->source_mode_unsigned :
1221169689Skan		  second_ei->source_mode_unsigned;
1222169689Skan	      break;
1223169689Skan	    default:
1224169689Skan	      gcc_unreachable ();
1225169689Skan	    }
1226169689Skan	}
1227169689Skan      else
1228169689Skan	{
1229169689Skan	  gcc_assert (first_ei->source_mode_unsigned == MAX_MACHINE_MODE);
1230169689Skan	  gcc_assert (first_ei->source_mode_signed != MAX_MACHINE_MODE);
1231169689Skan	  switch (second_ei->relevancy)
1232169689Skan	    {
1233169689Skan	    case SIGN_EXTENDED_DEF:
1234169689Skan	      first_ei->relevancy = SIGN_EXTENDED_DEF;
1235169689Skan	      first_ei->source_mode =
1236169689Skan		(first_ei->source_mode_signed > second_ei->source_mode) ?
1237169689Skan		first_ei->source_mode_signed : second_ei->source_mode;
1238169689Skan	      break;
1239169689Skan	    case RELEVANT_USE:
1240169689Skan	      break;
1241169689Skan	    case ZERO_EXTENDED_DEF:
1242169689Skan	      first_ei->relevancy = NOT_RELEVANT;
1243169689Skan	      break;
1244169689Skan	    case EXTENDED_DEF:
1245169689Skan	      if (second_ei->source_mode_signed == MAX_MACHINE_MODE)
1246169689Skan		first_ei->relevancy = NOT_RELEVANT;
1247169689Skan	      else
1248169689Skan		first_ei->source_mode_signed =
1249169689Skan		  (first_ei->source_mode_signed >
1250169689Skan		  second_ei->source_mode_signed) ?
1251169689Skan		  first_ei->source_mode_signed : second_ei->source_mode_signed;
1252169689Skan	      break;
1253169689Skan	    default:
1254169689Skan	      gcc_unreachable ();
1255169689Skan	    }
1256169689Skan	}
1257169689Skan      break;
1258169689Skan    default:
1259169689Skan      /* Unknown patern type.  */
1260169689Skan      gcc_unreachable ();
1261169689Skan    }
1262169689Skan
1263169689Skan  return false;
1264169689Skan}
1265169689Skan
1266169689Skan
1267169689Skan/* Free global data structures.  */
1268169689Skan
1269169689Skanstatic void
1270169689Skansee_free_data_structures (void)
1271169689Skan{
1272169689Skan  int i;
1273169689Skan  unsigned int j;
1274169689Skan
1275169689Skan  /* Free the bitmap vectors.  */
1276169689Skan  if (transp)
1277169689Skan    {
1278169689Skan      sbitmap_vector_free (transp);
1279169689Skan      transp = NULL;
1280169689Skan      sbitmap_vector_free (comp);
1281169689Skan      comp = NULL;
1282169689Skan      sbitmap_vector_free (antloc);
1283169689Skan      antloc = NULL;
1284169689Skan      sbitmap_vector_free (ae_kill);
1285169689Skan      ae_kill = NULL;
1286169689Skan    }
1287169689Skan  if (pre_insert_map)
1288169689Skan    {
1289169689Skan      sbitmap_vector_free (pre_insert_map);
1290169689Skan      pre_insert_map = NULL;
1291169689Skan    }
1292169689Skan  if (pre_delete_map)
1293169689Skan    {
1294169689Skan      sbitmap_vector_free (pre_delete_map);
1295169689Skan      pre_delete_map = NULL;
1296169689Skan    }
1297169689Skan  if (edge_list)
1298169689Skan    {
1299169689Skan      free_edge_list (edge_list);
1300169689Skan      edge_list = NULL;
1301169689Skan    }
1302169689Skan
1303169689Skan  /*  Free the extension hash.  */
1304169689Skan  htab_delete (see_pre_extension_hash);
1305169689Skan
1306169689Skan  /*  Free the array of hashes.  */
1307169689Skan  for (i = 0; i < last_bb; i++)
1308169689Skan    if (see_bb_hash_ar[i])
1309169689Skan      htab_delete (see_bb_hash_ar[i]);
1310169689Skan  free (see_bb_hash_ar);
1311169689Skan
1312169689Skan  /*  Free the array of splay trees.  */
1313169689Skan  for (i = 0; i < last_bb; i++)
1314169689Skan    if (see_bb_splay_ar[i])
1315169689Skan      splay_tree_delete (see_bb_splay_ar[i]);
1316169689Skan  free (see_bb_splay_ar);
1317169689Skan
1318169689Skan  /*  Free the array of web entries and their extra info field.  */
1319169689Skan  for (j = 0; j < defs_num; j++)
1320169689Skan    free (def_entry[j].extra_info);
1321169689Skan  free (def_entry);
1322169689Skan  for (j = 0; j < uses_num; j++)
1323169689Skan    free (use_entry[j].extra_info);
1324169689Skan  free (use_entry);
1325169689Skan}
1326169689Skan
1327169689Skan
1328169689Skan/* Initialize global data structures and variables.  */
1329169689Skan
1330169689Skanstatic void
1331169689Skansee_initialize_data_structures (void)
1332169689Skan{
1333169689Skan  /* Build the df object. */
1334169689Skan  df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES | DF_SUBREGS);
1335169689Skan  df_rd_add_problem (df, 0);
1336169689Skan  df_chain_add_problem (df, DF_DU_CHAIN | DF_UD_CHAIN);
1337169689Skan  df_analyze (df);
1338169689Skan
1339169689Skan  if (dump_file)
1340169689Skan    df_dump (df, dump_file);
1341169689Skan
1342169689Skan  /* Record the last basic block at the beginning of the optimization.  */
1343169689Skan  last_bb = last_basic_block;
1344169689Skan  /* Record the number of uses at the beginning of the optimization.  */
1345169689Skan  uses_num = DF_USES_SIZE (df);
1346169689Skan  /* Record the number of definitions at the beginning of the optimization.  */
1347169689Skan  defs_num = DF_DEFS_SIZE (df);
1348169689Skan
1349169689Skan  /*  Allocate web entries array for the union-find data structure.  */
1350169689Skan  def_entry = xcalloc (defs_num, sizeof (struct web_entry));
1351169689Skan  use_entry = xcalloc (uses_num, sizeof (struct web_entry));
1352169689Skan
1353169689Skan  /*  Allocate an array of splay trees.
1354169689Skan      One splay tree for each basic block.  */
1355169689Skan  see_bb_splay_ar = xcalloc (last_bb, sizeof (splay_tree));
1356169689Skan
1357169689Skan  /*  Allocate an array of hashes.
1358169689Skan      One hash for each basic block.  */
1359169689Skan  see_bb_hash_ar = xcalloc (last_bb, sizeof (htab_t));
1360169689Skan
1361169689Skan  /*  Allocate the extension hash.  It will hold the extensions that we want
1362169689Skan      to PRE.  */
1363169689Skan  see_pre_extension_hash = htab_create (10,
1364169689Skan					hash_descriptor_pre_extension,
1365169689Skan					eq_descriptor_pre_extension,
1366169689Skan					hash_del_pre_extension);
1367169689Skan}
1368169689Skan
1369169689Skan
1370169689Skan/* Function called by note_uses to check if a register is used in a
1371169689Skan   subexpressions.
1372169689Skan
1373169689Skan   X is a pointer to the subexpression and DATA is a pointer to a
1374169689Skan   see_mentioned_reg_data structure that contains the register to look for and
1375169689Skan   a place for the result.  */
1376169689Skan
1377169689Skanstatic void
1378169689Skansee_mentioned_reg (rtx *x, void *data)
1379169689Skan{
1380169689Skan  struct see_mentioned_reg_data *d
1381169689Skan    = (struct see_mentioned_reg_data *) data;
1382169689Skan
1383169689Skan  if (reg_mentioned_p (d->reg, *x))
1384169689Skan    d->mentioned = true;
1385169689Skan}
1386169689Skan
1387169689Skan
1388169689Skan/* We don't want to merge a use extension with a reference if the extended
1389169689Skan   register is used only in a simple move instruction.  We also don't want to
1390169689Skan   merge a def extension with a reference if the source register of the
1391169689Skan   extension is defined only in a simple move in the reference.
1392169689Skan
1393169689Skan   REF is the reference instruction.
1394169689Skan   EXTENSION is the use extension or def extension instruction.
1395169689Skan   TYPE is the type of the extension (use or def).
1396169689Skan
1397169689Skan   Return true if the reference is complicated enough, so we would like to merge
1398169689Skan   it with the extension.  Otherwise, return false.  */
1399169689Skan
1400169689Skanstatic bool
1401169689Skansee_want_to_be_merged_with_extension (rtx ref, rtx extension,
1402169689Skan   				      enum extension_type type)
1403169689Skan{
1404169689Skan  rtx pat;
1405169689Skan  rtx dest_extension_reg = see_get_extension_reg (extension, 1);
1406169689Skan  rtx source_extension_reg = see_get_extension_reg (extension, 0);
1407169689Skan  enum rtx_code code;
1408169689Skan  struct see_mentioned_reg_data d;
1409169689Skan  int i;
1410169689Skan
1411169689Skan  pat = PATTERN (ref);
1412169689Skan  code = GET_CODE (pat);
1413169689Skan
1414169689Skan  if (code == PARALLEL)
1415169689Skan    {
1416169689Skan      for (i = 0; i < XVECLEN (pat, 0); i++)
1417169689Skan	{
1418169689Skan	  rtx sub = XVECEXP (pat, 0, i);
1419169689Skan
1420169689Skan	  if (GET_CODE (sub) == SET
1421169689Skan	      && (REG_P (SET_DEST (sub))
1422169689Skan		  || (GET_CODE (SET_DEST (sub)) == SUBREG
1423169689Skan		      && REG_P (SUBREG_REG (SET_DEST (sub)))))
1424169689Skan	      && (REG_P (SET_SRC (sub))
1425169689Skan		  || (GET_CODE (SET_SRC (sub)) == SUBREG
1426169689Skan		      && REG_P (SUBREG_REG (SET_SRC (sub))))))
1427169689Skan	    {
1428169689Skan	      /* This is a simple move SET.  */
1429169689Skan	      if (type == DEF_EXTENSION
1430169689Skan		  && reg_mentioned_p (source_extension_reg, SET_DEST (sub)))
1431169689Skan		return false;
1432169689Skan	    }
1433169689Skan	  else
1434169689Skan	    {
1435169689Skan	      /* This is not a simple move SET.
1436169689Skan		 Check if it uses the source of the extension.  */
1437169689Skan	      if (type == USE_EXTENSION)
1438169689Skan		{
1439169689Skan  		  d.reg = dest_extension_reg;
1440169689Skan		  d.mentioned = false;
1441169689Skan		  note_uses (&sub, see_mentioned_reg, &d);
1442169689Skan		  if (d.mentioned)
1443169689Skan		    return true;
1444169689Skan		}
1445169689Skan	    }
1446169689Skan	}
1447169689Skan      if (type == USE_EXTENSION)
1448169689Skan	return false;
1449169689Skan    }
1450169689Skan  else
1451169689Skan    {
1452169689Skan      if (code == SET
1453169689Skan	  && (REG_P (SET_DEST (pat))
1454169689Skan	      || (GET_CODE (SET_DEST (pat)) == SUBREG
1455169689Skan		  && REG_P (SUBREG_REG (SET_DEST (pat)))))
1456169689Skan	  && (REG_P (SET_SRC (pat))
1457169689Skan	      || (GET_CODE (SET_SRC (pat)) == SUBREG
1458169689Skan		  && REG_P (SUBREG_REG (SET_SRC (pat))))))
1459169689Skan	/* This is a simple move SET.  */
1460169689Skan	return false;
1461169689Skan     }
1462169689Skan
1463169689Skan  return true;
1464169689Skan}
1465169689Skan
1466169689Skan
1467169689Skan/* Print the register number of the current see_register_properties
1468169689Skan   structure.
1469169689Skan
1470169689Skan   This is a subroutine of see_main called via htab_traverse.
1471169689Skan   SLOT contains the current see_register_properties structure pointer.  */
1472169689Skan
1473169689Skanstatic int
1474169689Skansee_print_register_properties (void **slot, void *b ATTRIBUTE_UNUSED)
1475169689Skan{
1476169689Skan  struct see_register_properties *prop = *slot;
1477169689Skan
1478169689Skan  gcc_assert (prop);
1479169689Skan  fprintf (dump_file, "Property found for register %d\n", prop->regno);
1480169689Skan  return 1;
1481169689Skan}
1482169689Skan
1483169689Skan
1484169689Skan/* Print the extension instruction of the current see_register_properties
1485169689Skan   structure.
1486169689Skan
1487169689Skan   This is a subroutine of see_main called via htab_traverse.
1488169689Skan   SLOT contains the current see_pre_extension_expr structure pointer.  */
1489169689Skan
1490169689Skanstatic int
1491169689Skansee_print_pre_extension_expr (void **slot, void *b ATTRIBUTE_UNUSED)
1492169689Skan{
1493169689Skan  struct see_pre_extension_expr *pre_extension = *slot;
1494169689Skan
1495169689Skan  gcc_assert (pre_extension
1496169689Skan  	      && pre_extension->se_insn
1497169689Skan	      && INSN_P (pre_extension->se_insn));
1498169689Skan
1499169689Skan  fprintf (dump_file, "Index %d for:\n", pre_extension->bitmap_index);
1500169689Skan  print_rtl_single (dump_file, pre_extension->se_insn);
1501169689Skan
1502169689Skan  return 1;
1503169689Skan}
1504169689Skan
1505169689Skan
1506169689Skan/* Phase 4 implementation: Commit changes to the insn stream.  */
1507169689Skan
1508169689Skan/* Delete the merged def extension.
1509169689Skan
1510169689Skan   This is a subroutine of see_commit_ref_changes called via htab_traverse.
1511169689Skan
1512169689Skan   SLOT contains the current def extension instruction.
1513169689Skan   B is the see_ref_s structure pointer.  */
1514169689Skan
1515169689Skanstatic int
1516169689Skansee_delete_merged_def_extension (void **slot, void *b ATTRIBUTE_UNUSED)
1517169689Skan{
1518169689Skan  rtx def_se = *slot;
1519169689Skan
1520169689Skan  if (dump_file)
1521169689Skan    {
1522169689Skan      fprintf (dump_file, "Deleting merged def extension:\n");
1523169689Skan      print_rtl_single (dump_file, def_se);
1524169689Skan    }
1525169689Skan
1526169689Skan  if (INSN_DELETED_P (def_se))
1527169689Skan    /* This def extension is an implicit one.  No need to delete it since
1528169689Skan       it is not in the insn stream.  */
1529169689Skan    return 1;
1530169689Skan
1531169689Skan  delete_insn (def_se);
1532169689Skan  return 1;
1533169689Skan}
1534169689Skan
1535169689Skan
1536169689Skan/* Delete the unmerged def extension.
1537169689Skan
1538169689Skan   This is a subroutine of see_commit_ref_changes called via htab_traverse.
1539169689Skan
1540169689Skan   SLOT contains the current def extension instruction.
1541169689Skan   B is the see_ref_s structure pointer.  */
1542169689Skan
1543169689Skanstatic int
1544169689Skansee_delete_unmerged_def_extension (void **slot, void *b ATTRIBUTE_UNUSED)
1545169689Skan{
1546169689Skan  rtx def_se = *slot;
1547169689Skan
1548169689Skan  if (dump_file)
1549169689Skan    {
1550169689Skan      fprintf (dump_file, "Deleting unmerged def extension:\n");
1551169689Skan      print_rtl_single (dump_file, def_se);
1552169689Skan    }
1553169689Skan
1554169689Skan  delete_insn (def_se);
1555169689Skan  return 1;
1556169689Skan}
1557169689Skan
1558169689Skan
1559169689Skan/* Emit the non-redundant use extension to the instruction stream.
1560169689Skan
1561169689Skan   This is a subroutine of see_commit_ref_changes called via htab_traverse.
1562169689Skan
1563169689Skan   SLOT contains the current use extension instruction.
1564169689Skan   B is the see_ref_s structure pointer.  */
1565169689Skan
1566169689Skanstatic int
1567169689Skansee_emit_use_extension (void **slot, void *b)
1568169689Skan{
1569169689Skan  rtx use_se = *slot;
1570169689Skan  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
1571169689Skan
1572169689Skan  if (INSN_DELETED_P (use_se))
1573169689Skan    /* This use extension was previously removed according to the lcm
1574169689Skan       output.  */
1575169689Skan    return 1;
1576169689Skan
1577169689Skan  if (dump_file)
1578169689Skan    {
1579169689Skan      fprintf (dump_file, "Inserting use extension:\n");
1580169689Skan      print_rtl_single (dump_file, use_se);
1581169689Skan    }
1582169689Skan
1583169689Skan  add_insn_before (use_se, curr_ref_s->insn);
1584169689Skan
1585169689Skan  return 1;
1586169689Skan}
1587169689Skan
1588169689Skan
1589169689Skan/* For each relevant reference:
1590169689Skan   a. Emit the non-redundant use extensions.
1591169689Skan   b. Delete the def extensions.
1592169689Skan   c. Replace the original reference with the merged one (if exists) and add the
1593169689Skan      move instructions that were generated.
1594169689Skan
1595169689Skan   This is a subroutine of see_commit_changes called via splay_tree_foreach.
1596169689Skan
1597169689Skan   STN is the current node in the see_bb_splay_ar[i] splay tree.  It holds a
1598169689Skan   see_ref_s structure.  */
1599169689Skan
1600169689Skanstatic int
1601169689Skansee_commit_ref_changes (splay_tree_node stn,
1602169689Skan		   	void *data ATTRIBUTE_UNUSED)
1603169689Skan{
1604169689Skan  htab_t use_se_hash = ((struct see_ref_s *) (stn->value))->use_se_hash;
1605169689Skan  htab_t unmerged_def_se_hash =
1606169689Skan    ((struct see_ref_s *) (stn->value))->unmerged_def_se_hash;
1607169689Skan  htab_t merged_def_se_hash =
1608169689Skan    ((struct see_ref_s *) (stn->value))->merged_def_se_hash;
1609169689Skan  rtx ref = ((struct see_ref_s *) (stn->value))->insn;
1610169689Skan  rtx merged_ref = ((struct see_ref_s *) (stn->value))->merged_insn;
1611169689Skan
1612169689Skan  /* Emit the non-redundant use extensions.  */
1613169689Skan  if (use_se_hash)
1614169689Skan    htab_traverse_noresize (use_se_hash, see_emit_use_extension,
1615169689Skan			    (PTR) (stn->value));
1616169689Skan
1617169689Skan  /* Delete the def extensions.  */
1618169689Skan  if (unmerged_def_se_hash)
1619169689Skan    htab_traverse (unmerged_def_se_hash, see_delete_unmerged_def_extension,
1620169689Skan		   (PTR) (stn->value));
1621169689Skan
1622169689Skan  if (merged_def_se_hash)
1623169689Skan    htab_traverse (merged_def_se_hash, see_delete_merged_def_extension,
1624169689Skan		   (PTR) (stn->value));
1625169689Skan
1626169689Skan  /* Replace the original reference with the merged one (if exists) and add the
1627169689Skan     move instructions that were generated.  */
1628169689Skan  if (merged_ref && !INSN_DELETED_P (ref))
1629169689Skan    {
1630169689Skan      if (dump_file)
1631169689Skan	{
1632169689Skan	  fprintf (dump_file, "Replacing orig reference:\n");
1633169689Skan	  print_rtl_single (dump_file, ref);
1634169689Skan	  fprintf (dump_file, "With merged reference:\n");
1635169689Skan	  print_rtl_single (dump_file, merged_ref);
1636169689Skan	}
1637169689Skan      emit_insn_after (merged_ref, ref);
1638169689Skan      delete_insn (ref);
1639169689Skan    }
1640169689Skan
1641169689Skan  /* Continue to the next reference.  */
1642169689Skan  return 0;
1643169689Skan}
1644169689Skan
1645169689Skan
1646169689Skan/* Insert partially redundant expressions on edges to make the expressions fully
1647169689Skan   redundant.
1648169689Skan
1649169689Skan   INDEX_MAP is a mapping of an index to an expression.
1650169689Skan   Return true if an instruction was inserted on an edge.
1651169689Skan   Otherwise, return false.  */
1652169689Skan
1653169689Skanstatic bool
1654169689Skansee_pre_insert_extensions (struct see_pre_extension_expr **index_map)
1655169689Skan{
1656169689Skan  int num_edges = NUM_EDGES (edge_list);
1657169689Skan  int set_size = pre_insert_map[0]->size;
1658169689Skan  size_t pre_extension_num = htab_elements (see_pre_extension_hash);
1659169689Skan
1660169689Skan  int did_insert = 0;
1661169689Skan  int e;
1662169689Skan  int i;
1663169689Skan  int j;
1664169689Skan
1665169689Skan  for (e = 0; e < num_edges; e++)
1666169689Skan    {
1667169689Skan      int indx;
1668169689Skan      basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e);
1669169689Skan
1670169689Skan      for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
1671169689Skan	{
1672169689Skan	  SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];
1673169689Skan
1674169689Skan	  for (j = indx; insert && j < (int) pre_extension_num;
1675169689Skan	       j++, insert >>= 1)
1676169689Skan	    if (insert & 1)
1677169689Skan	      {
1678169689Skan		struct see_pre_extension_expr *expr = index_map[j];
1679169689Skan		int idx = expr->bitmap_index;
1680169689Skan		rtx se_insn = NULL;
1681169689Skan		edge eg = INDEX_EDGE (edge_list, e);
1682169689Skan
1683169689Skan		start_sequence ();
1684169689Skan		emit_insn (PATTERN (expr->se_insn));
1685169689Skan		se_insn = get_insns ();
1686169689Skan		end_sequence ();
1687169689Skan
1688169689Skan		if (eg->flags & EDGE_ABNORMAL)
1689169689Skan		  {
1690169689Skan		    rtx new_insn = NULL;
1691169689Skan
1692169689Skan		    new_insn = insert_insn_end_bb_new (se_insn, bb);
1693169689Skan		    gcc_assert (new_insn && INSN_P (new_insn));
1694169689Skan
1695169689Skan		    if (dump_file)
1696169689Skan		      {
1697169689Skan			fprintf (dump_file,
1698169689Skan				 "PRE: end of bb %d, insn %d, ",
1699169689Skan				 bb->index, INSN_UID (new_insn));
1700169689Skan			fprintf (dump_file,
1701169689Skan				 "inserting expression %d\n", idx);
1702169689Skan		      }
1703169689Skan		  }
1704169689Skan		else
1705169689Skan		  {
1706169689Skan		    insert_insn_on_edge (se_insn, eg);
1707169689Skan
1708169689Skan		    if (dump_file)
1709169689Skan		      {
1710169689Skan			fprintf (dump_file, "PRE: edge (%d,%d), ",
1711169689Skan				 bb->index,
1712169689Skan				 INDEX_EDGE_SUCC_BB (edge_list, e)->index);
1713169689Skan			fprintf (dump_file, "inserting expression %d\n", idx);
1714169689Skan		      }
1715169689Skan		  }
1716169689Skan		did_insert = true;
1717169689Skan	      }
1718169689Skan	}
1719169689Skan    }
1720169689Skan  return did_insert;
1721169689Skan}
1722169689Skan
1723169689Skan
1724169689Skan/* Since all the redundant extensions must be anticipatable, they must be a use
1725169689Skan   extensions.  Mark them as deleted.  This will prevent them from been emitted
1726169689Skan   in the first place.
1727169689Skan
1728169689Skan   This is a subroutine of see_commit_changes called via htab_traverse.
1729169689Skan
1730169689Skan   SLOT contains the current see_pre_extension_expr structure pointer.  */
1731169689Skan
1732169689Skanstatic int
1733169689Skansee_pre_delete_extension (void **slot, void *b ATTRIBUTE_UNUSED)
1734169689Skan{
1735169689Skan  struct see_pre_extension_expr *expr = *slot;
1736169689Skan  struct see_occr *occr;
1737169689Skan  int indx = expr->bitmap_index;
1738169689Skan
1739169689Skan  for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
1740169689Skan    {
1741169689Skan      if (TEST_BIT (pre_delete_map[occr->block_num], indx))
1742169689Skan	{
1743169689Skan	  /* Mark as deleted.  */
1744169689Skan	  INSN_DELETED_P (occr->insn) = 1;
1745169689Skan	  if (dump_file)
1746169689Skan	    {
1747169689Skan	      fprintf (dump_file,"Redundant extension deleted:\n");
1748169689Skan	      print_rtl_single (dump_file, occr->insn);
1749169689Skan	    }
1750169689Skan	}
1751169689Skan    }
1752169689Skan  return 1;
1753169689Skan}
1754169689Skan
1755169689Skan
1756169689Skan/* Create the index_map mapping of an index to an expression.
1757169689Skan
1758169689Skan   This is a subroutine of see_commit_changes called via htab_traverse.
1759169689Skan
1760169689Skan   SLOT contains the current see_pre_extension_expr structure pointer.
1761169689Skan   B a pointer to see_pre_extension_expr structure pointer.  */
1762169689Skan
1763169689Skanstatic int
1764169689Skansee_map_extension (void **slot, void *b)
1765169689Skan{
1766169689Skan  struct see_pre_extension_expr *expr = *slot;
1767169689Skan  struct see_pre_extension_expr **index_map =
1768169689Skan    (struct see_pre_extension_expr **) b;
1769169689Skan
1770169689Skan  index_map[expr->bitmap_index] = expr;
1771169689Skan
1772169689Skan  return 1;
1773169689Skan}
1774169689Skan
1775169689Skan
1776169689Skan/* Phase 4 top level function.
1777169689Skan   In this phase we finally change the instruction stream.
1778169689Skan   Here we insert extensions at their best placements and delete the
1779169689Skan   redundant ones according to the output of the LCM.  We also replace
1780169689Skan   some of the instructions according to phase 2 merges results.  */
1781169689Skan
1782169689Skanstatic void
1783169689Skansee_commit_changes (void)
1784169689Skan{
1785169689Skan  struct see_pre_extension_expr **index_map;
1786169689Skan  size_t pre_extension_num = htab_elements (see_pre_extension_hash);
1787169689Skan  bool did_insert = false;
1788169689Skan  int i;
1789169689Skan
1790169689Skan  index_map = xcalloc (pre_extension_num,
1791169689Skan  		       sizeof (struct see_pre_extension_expr *));
1792169689Skan
1793169689Skan  if (dump_file)
1794169689Skan    fprintf (dump_file,
1795169689Skan      "* Phase 4: Commit changes to the insn stream.  *\n");
1796169689Skan
1797169689Skan  /* Produce a mapping of all the pre_extensions.  */
1798169689Skan  htab_traverse (see_pre_extension_hash, see_map_extension, (PTR) index_map);
1799169689Skan
1800169689Skan  /* Delete redundant extension.  This will prevent them from been emitted in
1801169689Skan     the first place.  */
1802169689Skan  htab_traverse (see_pre_extension_hash, see_pre_delete_extension, NULL);
1803169689Skan
1804169689Skan  /* At this point, we must free the DF object, since the number of basic blocks
1805169689Skan     may change.  */
1806169689Skan  df_finish (df);
1807169689Skan  df = NULL;
1808169689Skan
1809169689Skan  /* Insert extensions on edges, according to the LCM result.  */
1810169689Skan  did_insert = see_pre_insert_extensions (index_map);
1811169689Skan
1812169689Skan  if (did_insert)
1813169689Skan    commit_edge_insertions ();
1814169689Skan
1815169689Skan  /* Commit the rest of the changes.  */
1816169689Skan  for (i = 0; i < last_bb; i++)
1817169689Skan    {
1818169689Skan      if (see_bb_splay_ar[i])
1819169689Skan	{
1820169689Skan	  /* Traverse over all the references in the basic block in forward
1821169689Skan	     order.  */
1822169689Skan	  splay_tree_foreach (see_bb_splay_ar[i],
1823169689Skan			      see_commit_ref_changes, NULL);
1824169689Skan	}
1825169689Skan    }
1826169689Skan
1827169689Skan  free (index_map);
1828169689Skan}
1829169689Skan
1830169689Skan
1831169689Skan/* Phase 3 implementation: Eliminate globally redundant extensions.  */
1832169689Skan
1833169689Skan/* Analyze the properties of a merged def extension for the LCM and record avail
1834169689Skan   occurrences.
1835169689Skan
1836169689Skan   This is a subroutine of see_analyze_ref_local_prop called
1837169689Skan   via htab_traverse.
1838169689Skan
1839169689Skan   SLOT contains the current def extension instruction.
1840169689Skan   B is the see_ref_s structure pointer.  */
1841169689Skan
1842169689Skanstatic int
1843169689Skansee_analyze_merged_def_local_prop (void **slot, void *b)
1844169689Skan{
1845169689Skan  rtx def_se = *slot;
1846169689Skan  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
1847169689Skan  rtx ref = curr_ref_s->insn;
1848169689Skan  struct see_pre_extension_expr *extension_expr;
1849169689Skan  int indx;
1850169689Skan  int bb_num = BLOCK_NUM (ref);
1851169689Skan  htab_t curr_bb_hash;
1852169689Skan  struct see_register_properties *curr_prop, **slot_prop;
1853169689Skan  struct see_register_properties temp_prop;
1854169689Skan  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
1855169689Skan  struct see_occr *curr_occr = NULL;
1856169689Skan  struct see_occr *tmp_occr = NULL;
1857169689Skan
1858169689Skan  extension_expr = see_seek_pre_extension_expr (def_se, DEF_EXTENSION);
1859169689Skan  /* The extension_expr must be found.  */
1860169689Skan  gcc_assert (extension_expr);
1861169689Skan
1862169689Skan  curr_bb_hash = see_bb_hash_ar[bb_num];
1863169689Skan  gcc_assert (curr_bb_hash);
1864169689Skan  temp_prop.regno = REGNO (dest_extension_reg);
1865169689Skan  slot_prop =
1866169689Skan    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
1867169689Skan							&temp_prop, INSERT);
1868169689Skan  curr_prop = *slot_prop;
1869169689Skan  gcc_assert (curr_prop);
1870169689Skan
1871169689Skan  indx = extension_expr->bitmap_index;
1872169689Skan
1873169689Skan  /* Reset the transparency bit.  */
1874169689Skan  RESET_BIT (transp[bb_num], indx);
1875169689Skan  /* Reset the killed bit.  */
1876169689Skan  RESET_BIT (ae_kill[bb_num], indx);
1877169689Skan
1878169689Skan  if (curr_prop->first_se_after_last_def == DF_INSN_LUID (df, ref))
1879169689Skan    {
1880169689Skan      /* Set the available bit.  */
1881169689Skan      SET_BIT (comp[bb_num], indx);
1882169689Skan      /* Record the available occurrence.  */
1883169689Skan      curr_occr = xmalloc (sizeof (struct see_occr));
1884169689Skan      curr_occr->next = NULL;
1885169689Skan      curr_occr->insn = def_se;
1886169689Skan      curr_occr->block_num = bb_num;
1887169689Skan      tmp_occr = extension_expr->avail_occr;
1888169689Skan      if (!tmp_occr)
1889169689Skan	extension_expr->avail_occr = curr_occr;
1890169689Skan      else
1891169689Skan	{
1892169689Skan	  while (tmp_occr->next)
1893169689Skan	    tmp_occr = tmp_occr->next;
1894169689Skan	  tmp_occr->next = curr_occr;
1895169689Skan	}
1896169689Skan    }
1897169689Skan
1898169689Skan  return 1;
1899169689Skan}
1900169689Skan
1901169689Skan
1902169689Skan/* Analyze the properties of a unmerged def extension for the LCM.
1903169689Skan
1904169689Skan   This is a subroutine of see_analyze_ref_local_prop called
1905169689Skan   via htab_traverse.
1906169689Skan
1907169689Skan   SLOT contains the current def extension instruction.
1908169689Skan   B is the see_ref_s structure pointer.  */
1909169689Skan
1910169689Skanstatic int
1911169689Skansee_analyze_unmerged_def_local_prop (void **slot, void *b)
1912169689Skan{
1913169689Skan  rtx def_se = *slot;
1914169689Skan  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
1915169689Skan  rtx ref = curr_ref_s->insn;
1916169689Skan  struct see_pre_extension_expr *extension_expr;
1917169689Skan  int indx;
1918169689Skan  int bb_num = BLOCK_NUM (ref);
1919169689Skan  htab_t curr_bb_hash;
1920169689Skan  struct see_register_properties *curr_prop, **slot_prop;
1921169689Skan  struct see_register_properties temp_prop;
1922169689Skan  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
1923169689Skan
1924169689Skan  extension_expr = see_seek_pre_extension_expr (def_se, DEF_EXTENSION);
1925169689Skan  /* The extension_expr must be found.  */
1926169689Skan  gcc_assert (extension_expr);
1927169689Skan
1928169689Skan  curr_bb_hash = see_bb_hash_ar[bb_num];
1929169689Skan  gcc_assert (curr_bb_hash);
1930169689Skan  temp_prop.regno = REGNO (dest_extension_reg);
1931169689Skan  slot_prop =
1932169689Skan    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
1933169689Skan							&temp_prop, INSERT);
1934169689Skan  curr_prop = *slot_prop;
1935169689Skan  gcc_assert (curr_prop);
1936169689Skan
1937169689Skan  indx = extension_expr->bitmap_index;
1938169689Skan
1939169689Skan  /* Reset the transparency bit.  */
1940169689Skan  RESET_BIT (transp[bb_num], indx);
1941169689Skan  /* Set the killed bit.  */
1942169689Skan  SET_BIT (ae_kill[bb_num], indx);
1943169689Skan
1944169689Skan  return 1;
1945169689Skan}
1946169689Skan
1947169689Skan
1948169689Skan/* Analyze the properties of a use extension for the LCM and record anic and
1949169689Skan   avail occurrences.
1950169689Skan
1951169689Skan   This is a subroutine of see_analyze_ref_local_prop called
1952169689Skan   via htab_traverse.
1953169689Skan
1954169689Skan   SLOT contains the current use extension instruction.
1955169689Skan   B is the see_ref_s structure pointer.  */
1956169689Skan
1957169689Skanstatic int
1958169689Skansee_analyze_use_local_prop (void **slot, void *b)
1959169689Skan{
1960169689Skan  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
1961169689Skan  rtx use_se = *slot;
1962169689Skan  rtx ref = curr_ref_s->insn;
1963169689Skan  rtx dest_extension_reg = see_get_extension_reg (use_se, 1);
1964169689Skan  struct see_pre_extension_expr *extension_expr;
1965169689Skan  struct see_register_properties *curr_prop, **slot_prop;
1966169689Skan  struct see_register_properties temp_prop;
1967169689Skan  struct see_occr *curr_occr = NULL;
1968169689Skan  struct see_occr *tmp_occr = NULL;
1969169689Skan  htab_t curr_bb_hash;
1970169689Skan  int indx;
1971169689Skan  int bb_num = BLOCK_NUM (ref);
1972169689Skan
1973169689Skan  extension_expr = see_seek_pre_extension_expr (use_se, USE_EXTENSION);
1974169689Skan  /* The extension_expr must be found.  */
1975169689Skan  gcc_assert (extension_expr);
1976169689Skan
1977169689Skan  curr_bb_hash = see_bb_hash_ar[bb_num];
1978169689Skan  gcc_assert (curr_bb_hash);
1979169689Skan  temp_prop.regno = REGNO (dest_extension_reg);
1980169689Skan  slot_prop =
1981169689Skan    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
1982169689Skan							&temp_prop, INSERT);
1983169689Skan  curr_prop = *slot_prop;
1984169689Skan  gcc_assert (curr_prop);
1985169689Skan
1986169689Skan  indx = extension_expr->bitmap_index;
1987169689Skan
1988169689Skan  if (curr_prop->first_se_before_any_def == DF_INSN_LUID (df, ref))
1989169689Skan    {
1990169689Skan      /* Set the anticipatable bit.  */
1991169689Skan      SET_BIT (antloc[bb_num], indx);
1992169689Skan      /* Record the anticipatable occurrence.  */
1993169689Skan      curr_occr = xmalloc (sizeof (struct see_occr));
1994169689Skan      curr_occr->next = NULL;
1995169689Skan      curr_occr->insn = use_se;
1996169689Skan      curr_occr->block_num = bb_num;
1997169689Skan      tmp_occr = extension_expr->antic_occr;
1998169689Skan      if (!tmp_occr)
1999169689Skan	extension_expr->antic_occr = curr_occr;
2000169689Skan      else
2001169689Skan	{
2002169689Skan	  while (tmp_occr->next)
2003169689Skan	    tmp_occr = tmp_occr->next;
2004169689Skan	  tmp_occr->next = curr_occr;
2005169689Skan	}
2006169689Skan      if (curr_prop->last_def < 0)
2007169689Skan	{
2008169689Skan	  /* Set the available bit.  */
2009169689Skan	  SET_BIT (comp[bb_num], indx);
2010169689Skan	  /* Record the available occurrence.  */
2011169689Skan	  curr_occr = xmalloc (sizeof (struct see_occr));
2012169689Skan	  curr_occr->next = NULL;
2013169689Skan	  curr_occr->insn = use_se;
2014169689Skan	  curr_occr->block_num = bb_num;
2015169689Skan	  tmp_occr = extension_expr->avail_occr;
2016169689Skan	  if (!tmp_occr)
2017169689Skan	    extension_expr->avail_occr = curr_occr;
2018169689Skan	  else
2019169689Skan	    {
2020169689Skan  	      while (tmp_occr->next)
2021169689Skan  		tmp_occr = tmp_occr->next;
2022169689Skan	      tmp_occr->next = curr_occr;
2023169689Skan	    }
2024169689Skan	}
2025169689Skan      /* Note: there is no need to reset the killed bit since it must be zero at
2026169689Skan	 this point.  */
2027169689Skan    }
2028169689Skan  else if (curr_prop->first_se_after_last_def == DF_INSN_LUID (df, ref))
2029169689Skan    {
2030169689Skan      /* Set the available bit.  */
2031169689Skan      SET_BIT (comp[bb_num], indx);
2032169689Skan      /* Reset the killed bit.  */
2033169689Skan      RESET_BIT (ae_kill[bb_num], indx);
2034169689Skan      /* Record the available occurrence.  */
2035169689Skan      curr_occr = xmalloc (sizeof (struct see_occr));
2036169689Skan      curr_occr->next = NULL;
2037169689Skan      curr_occr->insn = use_se;
2038169689Skan      curr_occr->block_num = bb_num;
2039169689Skan      tmp_occr = extension_expr->avail_occr;
2040169689Skan      if (!tmp_occr)
2041169689Skan	extension_expr->avail_occr = curr_occr;
2042169689Skan      else
2043169689Skan	{
2044169689Skan	  while (tmp_occr->next)
2045169689Skan	    tmp_occr = tmp_occr->next;
2046169689Skan	  tmp_occr->next = curr_occr;
2047169689Skan	}
2048169689Skan    }
2049169689Skan  return 1;
2050169689Skan}
2051169689Skan
2052169689Skan
2053169689Skan/* Here we traverse over all the merged and unmerged extensions of the reference
2054169689Skan   and analyze their properties for the LCM.
2055169689Skan
2056169689Skan   This is a subroutine of see_execute_LCM called via splay_tree_foreach.
2057169689Skan
2058169689Skan   STN is the current node in the see_bb_splay_ar[i] splay tree.  It holds a
2059169689Skan   see_ref_s structure.  */
2060169689Skan
2061169689Skanstatic int
2062169689Skansee_analyze_ref_local_prop (splay_tree_node stn,
2063169689Skan			    void *data ATTRIBUTE_UNUSED)
2064169689Skan{
2065169689Skan  htab_t use_se_hash = ((struct see_ref_s *) (stn->value))->use_se_hash;
2066169689Skan  htab_t unmerged_def_se_hash =
2067169689Skan    ((struct see_ref_s *) (stn->value))->unmerged_def_se_hash;
2068169689Skan  htab_t merged_def_se_hash =
2069169689Skan    ((struct see_ref_s *) (stn->value))->merged_def_se_hash;
2070169689Skan
2071169689Skan  /* Analyze use extensions that were not merged with the reference.  */
2072169689Skan  if (use_se_hash)
2073169689Skan    htab_traverse_noresize (use_se_hash, see_analyze_use_local_prop,
2074169689Skan			    (PTR) (stn->value));
2075169689Skan
2076169689Skan  /* Analyze def extensions that were not merged with the reference.  */
2077169689Skan  if (unmerged_def_se_hash)
2078169689Skan    htab_traverse (unmerged_def_se_hash, see_analyze_unmerged_def_local_prop,
2079169689Skan		   (PTR) (stn->value));
2080169689Skan
2081169689Skan  /* Analyze def extensions that were merged with the reference.  */
2082169689Skan  if (merged_def_se_hash)
2083169689Skan    htab_traverse (merged_def_se_hash, see_analyze_merged_def_local_prop,
2084169689Skan		   (PTR) (stn->value));
2085169689Skan
2086169689Skan  /* Continue to the next definition.  */
2087169689Skan  return 0;
2088169689Skan}
2089169689Skan
2090169689Skan
2091169689Skan/* Phase 3 top level function.
2092169689Skan   In this phase, we set the input bit vectors of the LCM according to data
2093169689Skan   gathered in phase 2.
2094169689Skan   Then we run the edge based LCM.  */
2095169689Skan
2096169689Skanstatic void
2097169689Skansee_execute_LCM (void)
2098169689Skan{
2099169689Skan  size_t pre_extension_num = htab_elements (see_pre_extension_hash);
2100169689Skan  int i = 0;
2101169689Skan
2102169689Skan  if (dump_file)
2103169689Skan    fprintf (dump_file,
2104169689Skan      "* Phase 3: Eliminate globally redundant extensions.  *\n");
2105169689Skan
2106169689Skan  /* Initialize the global sbitmap vectors.  */
2107169689Skan  transp = sbitmap_vector_alloc (last_bb, pre_extension_num);
2108169689Skan  comp = sbitmap_vector_alloc (last_bb, pre_extension_num);
2109169689Skan  antloc = sbitmap_vector_alloc (last_bb, pre_extension_num);
2110169689Skan  ae_kill = sbitmap_vector_alloc (last_bb, pre_extension_num);
2111169689Skan  sbitmap_vector_ones (transp, last_bb);
2112169689Skan  sbitmap_vector_zero (comp, last_bb);
2113169689Skan  sbitmap_vector_zero (antloc, last_bb);
2114169689Skan  sbitmap_vector_zero (ae_kill, last_bb);
2115169689Skan
2116169689Skan  /* Traverse over all the splay trees of the basic blocks.  */
2117169689Skan  for (i = 0; i < last_bb; i++)
2118169689Skan    {
2119169689Skan      if (see_bb_splay_ar[i])
2120169689Skan	{
2121169689Skan	  /* Traverse over all the references in the basic block in forward
2122169689Skan	     order.  */
2123169689Skan	  splay_tree_foreach (see_bb_splay_ar[i],
2124169689Skan			      see_analyze_ref_local_prop, NULL);
2125169689Skan	}
2126169689Skan    }
2127169689Skan
2128169689Skan  /* Add fake exit edges before running the lcm.  */
2129169689Skan  add_noreturn_fake_exit_edges ();
2130169689Skan
2131169689Skan  /* Run the LCM.  */
2132169689Skan  edge_list = pre_edge_lcm (pre_extension_num, transp, comp, antloc,
2133169689Skan  			    ae_kill, &pre_insert_map, &pre_delete_map);
2134169689Skan
2135169689Skan  /* Remove the fake edges.  */
2136169689Skan  remove_fake_exit_edges ();
2137169689Skan}
2138169689Skan
2139169689Skan
2140169689Skan/* Phase 2 implementation: Merge and eliminate locally redundant extensions.  */
2141169689Skan
2142169689Skan/* In this function we set the register properties for the register that is
2143169689Skan   defined and extended in the reference.
2144169689Skan   The properties are defined in see_register_properties structure which is
2145169689Skan   allocated per basic block and per register.
2146169689Skan   Later the extension is inserted into the see_pre_extension_hash for the next
2147169689Skan   phase of the optimization.
2148169689Skan
2149169689Skan   This is a subroutine of see_handle_extensions_for_one_ref called
2150169689Skan   via htab_traverse.
2151169689Skan
2152169689Skan   SLOT contains the current def extension instruction.
2153169689Skan   B is the see_ref_s structure pointer.  */
2154169689Skan
2155169689Skanstatic int
2156169689Skansee_set_prop_merged_def (void **slot, void *b)
2157169689Skan{
2158169689Skan  rtx def_se = *slot;
2159169689Skan  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
2160169689Skan  rtx insn = curr_ref_s->insn;
2161169689Skan  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
2162169689Skan  htab_t curr_bb_hash;
2163169689Skan  struct see_register_properties *curr_prop = NULL;
2164169689Skan  struct see_register_properties **slot_prop;
2165169689Skan  struct see_register_properties temp_prop;
2166169689Skan  int ref_luid = DF_INSN_LUID (df, insn);
2167169689Skan
2168169689Skan  curr_bb_hash = see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)];
2169169689Skan  if (!curr_bb_hash)
2170169689Skan    {
2171169689Skan      /* The hash doesn't exist yet.  Create it.  */
2172169689Skan      curr_bb_hash = htab_create (10,
2173169689Skan				  hash_descriptor_properties,
2174169689Skan				  eq_descriptor_properties,
2175169689Skan				  hash_del_properties);
2176169689Skan      see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)] = curr_bb_hash;
2177169689Skan    }
2178169689Skan
2179169689Skan  /* Find the right register properties in the right basic block.  */
2180169689Skan  temp_prop.regno = REGNO (dest_extension_reg);
2181169689Skan  slot_prop =
2182169689Skan    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
2183169689Skan							&temp_prop, INSERT);
2184169689Skan
2185169689Skan  if (slot_prop && *slot_prop != NULL)
2186169689Skan    {
2187169689Skan      /* Property already exists.  */
2188169689Skan      curr_prop = *slot_prop;
2189169689Skan      gcc_assert (curr_prop->regno == REGNO (dest_extension_reg));
2190169689Skan
2191169689Skan      curr_prop->last_def = ref_luid;
2192169689Skan      curr_prop->first_se_after_last_def = ref_luid;
2193169689Skan    }
2194169689Skan  else
2195169689Skan    {
2196169689Skan      /* Property doesn't exist yet.  */
2197169689Skan      curr_prop = xmalloc (sizeof (struct see_register_properties));
2198169689Skan      curr_prop->regno = REGNO (dest_extension_reg);
2199169689Skan      curr_prop->last_def = ref_luid;
2200169689Skan      curr_prop->first_se_before_any_def = -1;
2201169689Skan      curr_prop->first_se_after_last_def = ref_luid;
2202169689Skan      *slot_prop = curr_prop;
2203169689Skan    }
2204169689Skan
2205169689Skan  /* Insert the def_se into see_pre_extension_hash if it isn't already
2206169689Skan     there.  */
2207169689Skan  see_seek_pre_extension_expr (def_se, DEF_EXTENSION);
2208169689Skan
2209169689Skan  return 1;
2210169689Skan}
2211169689Skan
2212169689Skan
2213169689Skan/* In this function we set the register properties for the register that is
2214169689Skan   defined but not extended in the reference.
2215169689Skan   The properties are defined in see_register_properties structure which is
2216169689Skan   allocated per basic block and per register.
2217169689Skan   Later the extension is inserted into the see_pre_extension_hash for the next
2218169689Skan   phase of the optimization.
2219169689Skan
2220169689Skan   This is a subroutine of see_handle_extensions_for_one_ref called
2221169689Skan   via htab_traverse.
2222169689Skan
2223169689Skan   SLOT contains the current def extension instruction.
2224169689Skan   B is the see_ref_s structure pointer.  */
2225169689Skan
2226169689Skanstatic int
2227169689Skansee_set_prop_unmerged_def (void **slot, void *b)
2228169689Skan{
2229169689Skan  rtx def_se = *slot;
2230169689Skan  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
2231169689Skan  rtx insn = curr_ref_s->insn;
2232169689Skan  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
2233169689Skan  htab_t curr_bb_hash;
2234169689Skan  struct see_register_properties *curr_prop = NULL;
2235169689Skan  struct see_register_properties **slot_prop;
2236169689Skan  struct see_register_properties temp_prop;
2237169689Skan  int ref_luid = DF_INSN_LUID (df, insn);
2238169689Skan
2239169689Skan  curr_bb_hash = see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)];
2240169689Skan  if (!curr_bb_hash)
2241169689Skan    {
2242169689Skan      /* The hash doesn't exist yet.  Create it.  */
2243169689Skan      curr_bb_hash = htab_create (10,
2244169689Skan				  hash_descriptor_properties,
2245169689Skan				  eq_descriptor_properties,
2246169689Skan				  hash_del_properties);
2247169689Skan      see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)] = curr_bb_hash;
2248169689Skan    }
2249169689Skan
2250169689Skan  /* Find the right register properties in the right basic block.  */
2251169689Skan  temp_prop.regno = REGNO (dest_extension_reg);
2252169689Skan  slot_prop =
2253169689Skan    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
2254169689Skan							&temp_prop, INSERT);
2255169689Skan
2256169689Skan  if (slot_prop && *slot_prop != NULL)
2257169689Skan    {
2258169689Skan      /* Property already exists.  */
2259169689Skan      curr_prop = *slot_prop;
2260169689Skan      gcc_assert (curr_prop->regno == REGNO (dest_extension_reg));
2261169689Skan
2262169689Skan      curr_prop->last_def = ref_luid;
2263169689Skan      curr_prop->first_se_after_last_def = -1;
2264169689Skan    }
2265169689Skan  else
2266169689Skan    {
2267169689Skan      /* Property doesn't exist yet.  */
2268169689Skan      curr_prop = xmalloc (sizeof (struct see_register_properties));
2269169689Skan      curr_prop->regno = REGNO (dest_extension_reg);
2270169689Skan      curr_prop->last_def = ref_luid;
2271169689Skan      curr_prop->first_se_before_any_def = -1;
2272169689Skan      curr_prop->first_se_after_last_def = -1;
2273169689Skan      *slot_prop = curr_prop;
2274169689Skan    }
2275169689Skan
2276169689Skan  /* Insert the def_se into see_pre_extension_hash if it isn't already
2277169689Skan     there.  */
2278169689Skan  see_seek_pre_extension_expr (def_se, DEF_EXTENSION);
2279169689Skan
2280169689Skan  return 1;
2281169689Skan}
2282169689Skan
2283169689Skan
2284169689Skan/* In this function we set the register properties for the register that is used
2285169689Skan   in the reference.
2286169689Skan   The properties are defined in see_register_properties structure which is
2287169689Skan   allocated per basic block and per register.
2288169689Skan   When a redundant use extension is found it is removed from the hash of the
2289169689Skan   reference.
2290169689Skan   If the extension is non redundant it is inserted into the
2291169689Skan   see_pre_extension_hash for the next phase of the optimization.
2292169689Skan
2293169689Skan   This is a subroutine of see_handle_extensions_for_one_ref called
2294169689Skan   via htab_traverse.
2295169689Skan
2296169689Skan   SLOT contains the current use extension instruction.
2297169689Skan   B is the see_ref_s structure pointer.  */
2298169689Skan
2299169689Skanstatic int
2300169689Skansee_set_prop_unmerged_use (void **slot, void *b)
2301169689Skan{
2302169689Skan  rtx use_se = *slot;
2303169689Skan  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
2304169689Skan  rtx insn = curr_ref_s->insn;
2305169689Skan  rtx dest_extension_reg = see_get_extension_reg (use_se, 1);
2306169689Skan  htab_t curr_bb_hash;
2307169689Skan  struct see_register_properties *curr_prop = NULL;
2308169689Skan  struct see_register_properties **slot_prop;
2309169689Skan  struct see_register_properties temp_prop;
2310169689Skan  bool locally_redundant = false;
2311169689Skan  int ref_luid = DF_INSN_LUID (df, insn);
2312169689Skan
2313169689Skan  curr_bb_hash = see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)];
2314169689Skan  if (!curr_bb_hash)
2315169689Skan    {
2316169689Skan      /* The hash doesn't exist yet.  Create it.  */
2317169689Skan      curr_bb_hash = htab_create (10,
2318169689Skan				  hash_descriptor_properties,
2319169689Skan				  eq_descriptor_properties,
2320169689Skan				  hash_del_properties);
2321169689Skan      see_bb_hash_ar[BLOCK_NUM (curr_ref_s->insn)] = curr_bb_hash;
2322169689Skan    }
2323169689Skan
2324169689Skan  /* Find the right register properties in the right basic block.  */
2325169689Skan  temp_prop.regno = REGNO (dest_extension_reg);
2326169689Skan  slot_prop =
2327169689Skan    (struct see_register_properties **) htab_find_slot (curr_bb_hash,
2328169689Skan							&temp_prop, INSERT);
2329169689Skan
2330169689Skan  if (slot_prop && *slot_prop != NULL)
2331169689Skan    {
2332169689Skan      /* Property already exists.  */
2333169689Skan      curr_prop = *slot_prop;
2334169689Skan      gcc_assert (curr_prop->regno == REGNO (dest_extension_reg));
2335169689Skan
2336169689Skan
2337169689Skan      if (curr_prop->last_def < 0 && curr_prop->first_se_before_any_def < 0)
2338169689Skan	curr_prop->first_se_before_any_def = ref_luid;
2339169689Skan      else if (curr_prop->last_def < 0
2340169689Skan	       && curr_prop->first_se_before_any_def >= 0)
2341169689Skan	{
2342169689Skan	  /* In this case the extension is locally redundant.  */
2343169689Skan	  htab_clear_slot (curr_ref_s->use_se_hash, (PTR *)slot);
2344169689Skan	  locally_redundant = true;
2345169689Skan	}
2346169689Skan      else if (curr_prop->last_def >= 0
2347169689Skan	       && curr_prop->first_se_after_last_def < 0)
2348169689Skan	curr_prop->first_se_after_last_def = ref_luid;
2349169689Skan      else if (curr_prop->last_def >= 0
2350169689Skan	       && curr_prop->first_se_after_last_def >= 0)
2351169689Skan	{
2352169689Skan	  /* In this case the extension is locally redundant.  */
2353169689Skan	  htab_clear_slot (curr_ref_s->use_se_hash, (PTR *)slot);
2354169689Skan	  locally_redundant = true;
2355169689Skan	}
2356169689Skan      else
2357169689Skan	gcc_unreachable ();
2358169689Skan    }
2359169689Skan  else
2360169689Skan    {
2361169689Skan      /* Property doesn't exist yet.  Create a new one.  */
2362169689Skan      curr_prop = xmalloc (sizeof (struct see_register_properties));
2363169689Skan      curr_prop->regno = REGNO (dest_extension_reg);
2364169689Skan      curr_prop->last_def = -1;
2365169689Skan      curr_prop->first_se_before_any_def = ref_luid;
2366169689Skan      curr_prop->first_se_after_last_def = -1;
2367169689Skan      *slot_prop = curr_prop;
2368169689Skan    }
2369169689Skan
2370169689Skan  /* Insert the use_se into see_pre_extension_hash if it isn't already
2371169689Skan     there.  */
2372169689Skan  if (!locally_redundant)
2373169689Skan    see_seek_pre_extension_expr (use_se, USE_EXTENSION);
2374169689Skan  if (locally_redundant && dump_file)
2375169689Skan    {
2376169689Skan      fprintf (dump_file, "Locally redundant extension:\n");
2377169689Skan      print_rtl_single (dump_file, use_se);
2378169689Skan    }
2379169689Skan  return 1;
2380169689Skan}
2381169689Skan
2382169689Skan
2383169689Skan/* Print an extension instruction.
2384169689Skan
2385169689Skan   This is a subroutine of see_handle_extensions_for_one_ref called
2386169689Skan   via htab_traverse.
2387169689Skan   SLOT contains the extension instruction.  */
2388169689Skan
2389169689Skanstatic int
2390169689Skansee_print_one_extension (void **slot, void *b ATTRIBUTE_UNUSED)
2391169689Skan{
2392169689Skan  rtx def_se = *slot;
2393169689Skan
2394169689Skan  gcc_assert (def_se && INSN_P (def_se));
2395169689Skan  print_rtl_single (dump_file, def_se);
2396169689Skan
2397169689Skan  return 1;
2398169689Skan}
2399169689Skan
2400169689Skan/* Function called by note_uses to replace used subexpressions.
2401169689Skan
2402169689Skan   X is a pointer to the subexpression and DATA is a pointer to a
2403169689Skan   see_replace_data structure that contains the data for the replacement.  */
2404169689Skan
2405169689Skanstatic void
2406169689Skansee_replace_src (rtx *x, void *data)
2407169689Skan{
2408169689Skan  struct see_replace_data *d
2409169689Skan    = (struct see_replace_data *) data;
2410169689Skan
2411169689Skan  *x = replace_rtx (*x, d->from, d->to);
2412169689Skan}
2413169689Skan
2414169689Skan
2415169689Skan/* At this point the pattern is expected to be:
2416169689Skan
2417169689Skan   ref:	    set (dest_reg) (rhs)
2418169689Skan   def_se:  set (dest_extension_reg) (sign/zero_extend (source_extension_reg))
2419169689Skan
2420169689Skan   The merge of these two instructions didn't succeed.
2421169689Skan
2422169689Skan   We try to generate the pattern:
2423169689Skan   set (subreg (dest_extension_reg)) (rhs)
2424169689Skan
2425169689Skan   We do this in 4 steps:
2426169689Skan   a. Replace every use of dest_reg with a new pseudo register.
2427169689Skan   b. Replace every instance of dest_reg with the subreg.
2428169689Skan   c. Replace every use of the new pseudo register back to dest_reg.
2429169689Skan   d. Try to recognize and simplify.
2430169689Skan
2431169689Skan   If the manipulation failed, leave the original ref but try to generate and
2432169689Skan   recognize a simple move instruction:
2433169689Skan   set (subreg (dest_extension_reg)) (dest_reg)
2434169689Skan   This move instruction will be emitted right after the ref to the instruction
2435169689Skan   stream and assure the correctness of the code after def_se will be removed.
2436169689Skan
2437169689Skan   CURR_REF_S is the current reference.
2438169689Skan   DEF_SE is the extension that couldn't be merged.  */
2439169689Skan
2440169689Skanstatic void
2441169689Skansee_def_extension_not_merged (struct see_ref_s *curr_ref_s, rtx def_se)
2442169689Skan{
2443169689Skan  struct see_replace_data d;
2444169689Skan  /* If the original insn was already merged with an extension before,
2445169689Skan     take the merged one.  */
2446169689Skan  rtx ref = (curr_ref_s->merged_insn) ? curr_ref_s->merged_insn :
2447169689Skan					curr_ref_s->insn;
2448169689Skan  rtx merged_ref_next = (curr_ref_s->merged_insn) ?
2449169689Skan  			NEXT_INSN (curr_ref_s->merged_insn): NULL_RTX;
2450169689Skan  rtx ref_copy = copy_rtx (ref);
2451169689Skan  rtx source_extension_reg = see_get_extension_reg (def_se, 0);
2452169689Skan  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
2453169689Skan  rtx move_insn = NULL;
2454169689Skan  rtx set, rhs;
2455169689Skan  rtx dest_reg, dest_real_reg;
2456169689Skan  rtx new_pseudo_reg, subreg;
2457169689Skan  enum machine_mode source_extension_mode = GET_MODE (source_extension_reg);
2458169689Skan  enum machine_mode dest_mode;
2459169689Skan
2460169689Skan  set = single_set (def_se);
2461169689Skan  gcc_assert (set);
2462169689Skan  rhs = SET_SRC (set);
2463169689Skan  gcc_assert (GET_CODE (rhs) == SIGN_EXTEND
2464169689Skan	      || GET_CODE (rhs) == ZERO_EXTEND);
2465169689Skan  dest_reg = XEXP (rhs, 0);
2466169689Skan  gcc_assert (REG_P (dest_reg)
2467169689Skan	      || (GET_CODE (dest_reg) == SUBREG
2468169689Skan		  && REG_P (SUBREG_REG (dest_reg))));
2469169689Skan  dest_real_reg = REG_P (dest_reg) ? dest_reg : SUBREG_REG (dest_reg);
2470169689Skan  dest_mode = GET_MODE (dest_reg);
2471169689Skan
2472169689Skan  subreg = gen_lowpart_SUBREG (dest_mode, dest_extension_reg);
2473169689Skan  new_pseudo_reg = gen_reg_rtx (source_extension_mode);
2474169689Skan
2475169689Skan  /* Step a: Replace every use of dest_real_reg with a new pseudo register.  */
2476169689Skan  d.from = dest_real_reg;
2477169689Skan  d.to = new_pseudo_reg;
2478169689Skan  note_uses (&PATTERN (ref_copy), see_replace_src, &d);
2479169689Skan  /* Step b: Replace every instance of dest_reg with the subreg.  */
2480169689Skan  ref_copy = replace_rtx (ref_copy, dest_reg, subreg);
2481169689Skan
2482169689Skan  /* Step c: Replace every use of the new pseudo register back to
2483169689Skan     dest_real_reg.  */
2484169689Skan  d.from = new_pseudo_reg;
2485169689Skan  d.to = dest_real_reg;
2486169689Skan  note_uses (&PATTERN (ref_copy), see_replace_src, &d);
2487169689Skan
2488169689Skan  if (rtx_equal_p (PATTERN (ref), PATTERN (ref_copy))
2489169689Skan      || insn_invalid_p (ref_copy))
2490169689Skan    {
2491169689Skan      /* The manipulation failed.  */
2492169689Skan
2493169689Skan      /* Create a new copy.  */
2494169689Skan      ref_copy = copy_rtx (ref);
2495169689Skan
2496169689Skan      /* Create a simple move instruction that will replace the def_se.  */
2497169689Skan      start_sequence ();
2498169689Skan      emit_move_insn (subreg, dest_reg);
2499169689Skan      move_insn = get_insns ();
2500169689Skan      end_sequence ();
2501169689Skan
2502169689Skan      /* Link the manipulated instruction to the newly created move instruction
2503169689Skan	 and to the former created move instructions.  */
2504169689Skan      PREV_INSN (ref_copy) = NULL_RTX;
2505169689Skan      NEXT_INSN (ref_copy) = move_insn;
2506169689Skan      PREV_INSN (move_insn) = ref_copy;
2507169689Skan      NEXT_INSN (move_insn) = merged_ref_next;
2508169689Skan      if (merged_ref_next != NULL_RTX)
2509169689Skan	PREV_INSN (merged_ref_next) = move_insn;
2510169689Skan      curr_ref_s->merged_insn = ref_copy;
2511169689Skan
2512169689Skan      if (dump_file)
2513169689Skan	{
2514169689Skan	  fprintf (dump_file, "Following def merge failure a move ");
2515169689Skan	  fprintf (dump_file, "insn was added after the ref.\n");
2516169689Skan	  fprintf (dump_file, "Original ref:\n");
2517169689Skan	  print_rtl_single (dump_file, ref);
2518169689Skan	  fprintf (dump_file, "Move insn that was added:\n");
2519169689Skan	  print_rtl_single (dump_file, move_insn);
2520169689Skan	}
2521169689Skan      return;
2522169689Skan    }
2523169689Skan
2524169689Skan  /* The manipulation succeeded.  Store the new manipulated reference.  */
2525169689Skan
2526169689Skan  /* Try to simplify the new manipulated insn.  */
2527169689Skan  validate_simplify_insn (ref_copy);
2528169689Skan
2529169689Skan  /* Create a simple move instruction to assure the correctness of the code.  */
2530169689Skan  start_sequence ();
2531169689Skan  emit_move_insn (dest_reg, subreg);
2532169689Skan  move_insn = get_insns ();
2533169689Skan  end_sequence ();
2534169689Skan
2535169689Skan  /* Link the manipulated instruction to the newly created move instruction and
2536169689Skan     to the former created move instructions.  */
2537169689Skan  PREV_INSN (ref_copy) = NULL_RTX;
2538169689Skan  NEXT_INSN (ref_copy) = move_insn;
2539169689Skan  PREV_INSN (move_insn) = ref_copy;
2540169689Skan  NEXT_INSN (move_insn) = merged_ref_next;
2541169689Skan  if (merged_ref_next != NULL_RTX)
2542169689Skan    PREV_INSN (merged_ref_next) = move_insn;
2543169689Skan  curr_ref_s->merged_insn = ref_copy;
2544169689Skan
2545169689Skan  if (dump_file)
2546169689Skan    {
2547169689Skan      fprintf (dump_file, "Following merge failure the ref was transformed!\n");
2548169689Skan      fprintf (dump_file, "Original ref:\n");
2549169689Skan      print_rtl_single (dump_file, ref);
2550169689Skan      fprintf (dump_file, "Transformed ref:\n");
2551169689Skan      print_rtl_single (dump_file, ref_copy);
2552169689Skan      fprintf (dump_file, "Move insn that was added:\n");
2553169689Skan      print_rtl_single (dump_file, move_insn);
2554169689Skan    }
2555169689Skan}
2556169689Skan
2557169689Skan
2558169689Skan/* Merge the reference instruction (ref) with the current use extension.
2559169689Skan
2560169689Skan   use_se extends a NARROWmode register to a WIDEmode register.
2561169689Skan   ref uses the WIDEmode register.
2562169689Skan
2563169689Skan   The pattern we try to merge is this:
2564169689Skan   use_se: set (dest_extension_reg) (sign/zero_extend (source_extension_reg))
2565169689Skan   ref:	   use (dest_extension_reg)
2566169689Skan
2567169689Skan   where dest_extension_reg and source_extension_reg can be subregs.
2568169689Skan
2569169689Skan   The merge is done by generating, simplifying and recognizing the pattern:
2570169689Skan   use (sign/zero_extend (source_extension_reg))
2571169689Skan
2572169689Skan   If ref is too simple (according to see_want_to_be_merged_with_extension ())
2573169689Skan   we don't try to merge it with use_se and we continue as if the merge failed.
2574169689Skan
2575169689Skan   This is a subroutine of see_handle_extensions_for_one_ref called
2576169689Skan   via htab_traverse.
2577169689Skan   SLOT contains the current use extension instruction.
2578169689Skan   B is the see_ref_s structure pointer.  */
2579169689Skan
2580169689Skanstatic int
2581169689Skansee_merge_one_use_extension (void **slot, void *b)
2582169689Skan{
2583169689Skan  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
2584169689Skan  rtx use_se = *slot;
2585169689Skan  rtx ref = (curr_ref_s->merged_insn) ? curr_ref_s->merged_insn :
2586169689Skan					curr_ref_s->insn;
2587169689Skan  rtx merged_ref_next = (curr_ref_s->merged_insn) ?
2588169689Skan  			NEXT_INSN (curr_ref_s->merged_insn): NULL_RTX;
2589169689Skan  rtx ref_copy = copy_rtx (ref);
2590169689Skan  rtx extension_set = single_set (use_se);
2591169689Skan  rtx extension_rhs = NULL;
2592169689Skan  rtx dest_extension_reg = see_get_extension_reg (use_se, 1);
2593169689Skan  rtx note = NULL;
2594169689Skan  rtx simplified_note = NULL;
2595169689Skan
2596169689Skan  gcc_assert (use_se && curr_ref_s && extension_set);
2597169689Skan
2598169689Skan  extension_rhs = SET_SRC (extension_set);
2599169689Skan
2600169689Skan  /* In REG_EQUIV and REG_EQUAL notes that mention the register we need to
2601169689Skan     replace the uses of the dest_extension_reg with the rhs of the extension
2602169689Skan     instruction.  This is necessary since there might not be an extension in
2603169689Skan     the path between the definition and the note when this optimization is
2604169689Skan     over.  */
2605169689Skan  note = find_reg_equal_equiv_note (ref_copy);
2606169689Skan  if (note)
2607169689Skan    {
2608169689Skan      simplified_note = simplify_replace_rtx (XEXP (note, 0),
2609169689Skan      					      dest_extension_reg,
2610169689Skan					      extension_rhs);
2611169689Skan      if (rtx_equal_p (XEXP (note, 0), simplified_note))
2612169689Skan	/* Replacement failed.  Remove the note.  */
2613169689Skan	remove_note (ref_copy, note);
2614169689Skan      else
2615169689Skan	XEXP (note, 0) = simplified_note;
2616169689Skan    }
2617169689Skan
2618169689Skan  if (!see_want_to_be_merged_with_extension (ref, use_se, USE_EXTENSION))
2619169689Skan    {
2620169689Skan      /* The use in the reference is too simple.  Don't try to merge.  */
2621169689Skan      if (dump_file)
2622169689Skan	{
2623169689Skan	  fprintf (dump_file, "Use merge skipped!\n");
2624169689Skan	  fprintf (dump_file, "Original instructions:\n");
2625169689Skan	  print_rtl_single (dump_file, use_se);
2626169689Skan	  print_rtl_single (dump_file, ref);
2627169689Skan	}
2628169689Skan      /* Don't remove the current use_se from the use_se_hash and continue to
2629169689Skan	 the next extension.  */
2630169689Skan      return 1;
2631169689Skan    }
2632169689Skan
2633169689Skan  validate_replace_src_group (dest_extension_reg, extension_rhs, ref_copy);
2634169689Skan
2635169689Skan  if (!num_changes_pending ())
2636169689Skan    /* In this case this is not a real use (the only use is/was in the notes
2637169689Skan       list).  Remove the use extension from the hash.  This will prevent it
2638169689Skan       from been emitted in the first place.  */
2639169689Skan    {
2640169689Skan      if (dump_file)
2641169689Skan	{
2642169689Skan	  fprintf (dump_file, "Use extension not necessary before:\n");
2643169689Skan	  print_rtl_single (dump_file, ref);
2644169689Skan	}
2645169689Skan      htab_clear_slot (curr_ref_s->use_se_hash, (PTR *)slot);
2646169689Skan      PREV_INSN (ref_copy) = NULL_RTX;
2647169689Skan      NEXT_INSN (ref_copy) = merged_ref_next;
2648169689Skan      if (merged_ref_next != NULL_RTX)
2649169689Skan	PREV_INSN (merged_ref_next) = ref_copy;
2650169689Skan      curr_ref_s->merged_insn = ref_copy;
2651169689Skan      return 1;
2652169689Skan    }
2653169689Skan
2654169689Skan  if (!apply_change_group ())
2655169689Skan    {
2656169689Skan      /* The merge failed.  */
2657169689Skan      if (dump_file)
2658169689Skan	{
2659169689Skan	  fprintf (dump_file, "Use merge failed!\n");
2660169689Skan	  fprintf (dump_file, "Original instructions:\n");
2661169689Skan	  print_rtl_single (dump_file, use_se);
2662169689Skan	  print_rtl_single (dump_file, ref);
2663169689Skan	}
2664169689Skan      /* Don't remove the current use_se from the use_se_hash and continue to
2665169689Skan	 the next extension.  */
2666169689Skan      return 1;
2667169689Skan    }
2668169689Skan
2669169689Skan  /* The merge succeeded!  */
2670169689Skan
2671169689Skan  /* Try to simplify the new merged insn.  */
2672169689Skan  validate_simplify_insn (ref_copy);
2673169689Skan
2674169689Skan  PREV_INSN (ref_copy) = NULL_RTX;
2675169689Skan  NEXT_INSN (ref_copy) = merged_ref_next;
2676169689Skan  if (merged_ref_next != NULL_RTX)
2677169689Skan    PREV_INSN (merged_ref_next) = ref_copy;
2678169689Skan  curr_ref_s->merged_insn = ref_copy;
2679169689Skan
2680169689Skan  if (dump_file)
2681169689Skan    {
2682169689Skan      fprintf (dump_file, "Use merge succeeded!\n");
2683169689Skan      fprintf (dump_file, "Original instructions:\n");
2684169689Skan      print_rtl_single (dump_file, use_se);
2685169689Skan      print_rtl_single (dump_file, ref);
2686169689Skan      fprintf (dump_file, "Merged instruction:\n");
2687169689Skan      print_rtl_single (dump_file, ref_copy);
2688169689Skan    }
2689169689Skan
2690169689Skan  /* Remove the current use_se from the use_se_hash.  This will prevent it from
2691169689Skan     been emitted in the first place.  */
2692169689Skan  htab_clear_slot (curr_ref_s->use_se_hash, (PTR *)slot);
2693169689Skan  return 1;
2694169689Skan}
2695169689Skan
2696169689Skan
2697169689Skan/* Merge the reference instruction (ref) with the extension that follows it
2698169689Skan   in the same basic block (def_se).
2699169689Skan   ref sets a NARROWmode register and def_se extends it to WIDEmode register.
2700169689Skan
2701169689Skan   The pattern we try to merge is this:
2702169689Skan   ref:	   set (dest_reg) (rhs)
2703169689Skan   def_se: set (dest_extension_reg) (sign/zero_extend (source_extension_reg))
2704169689Skan
2705169689Skan   where dest_reg and source_extension_reg can both be subregs (together)
2706169689Skan   and (REGNO (dest_reg) == REGNO (source_extension_reg))
2707169689Skan
2708169689Skan   The merge is done by generating, simplifying and recognizing the pattern:
2709169689Skan   set (dest_extension_reg) (sign/zero_extend (rhs))
2710169689Skan   If ref is a parallel instruction we just replace the relevant set in it.
2711169689Skan
2712169689Skan   If ref is too simple (according to see_want_to_be_merged_with_extension ())
2713169689Skan   we don't try to merge it with def_se and we continue as if the merge failed.
2714169689Skan
2715169689Skan   This is a subroutine of see_handle_extensions_for_one_ref called
2716169689Skan   via htab_traverse.
2717169689Skan
2718169689Skan   SLOT contains the current def extension instruction.
2719169689Skan   B is the see_ref_s structure pointer.  */
2720169689Skan
2721169689Skanstatic int
2722169689Skansee_merge_one_def_extension (void **slot, void *b)
2723169689Skan{
2724169689Skan  struct see_ref_s *curr_ref_s = (struct see_ref_s *) b;
2725169689Skan  rtx def_se = *slot;
2726169689Skan  /* If the original insn was already merged with an extension before,
2727169689Skan     take the merged one.  */
2728169689Skan  rtx ref = (curr_ref_s->merged_insn) ? curr_ref_s->merged_insn :
2729169689Skan					curr_ref_s->insn;
2730169689Skan  rtx merged_ref_next = (curr_ref_s->merged_insn) ?
2731169689Skan  			NEXT_INSN (curr_ref_s->merged_insn): NULL_RTX;
2732169689Skan  rtx ref_copy = copy_rtx (ref);
2733169689Skan  rtx new_set = NULL;
2734169689Skan  rtx source_extension_reg = see_get_extension_reg (def_se, 0);
2735169689Skan  rtx dest_extension_reg = see_get_extension_reg (def_se, 1);
2736169689Skan  rtx move_insn, *rtx_slot, subreg;
2737169689Skan  rtx temp_extension = NULL;
2738169689Skan  rtx simplified_temp_extension = NULL;
2739169689Skan  rtx *pat;
2740169689Skan  enum rtx_code code;
2741169689Skan  enum rtx_code extension_code;
2742169689Skan  enum machine_mode source_extension_mode;
2743169689Skan  enum machine_mode source_mode;
2744169689Skan  enum machine_mode dest_extension_mode;
2745169689Skan  bool merge_success = false;
2746169689Skan  int i;
2747169689Skan
2748169689Skan  gcc_assert (def_se
2749169689Skan  	      && INSN_P (def_se)
2750169689Skan	      && curr_ref_s
2751169689Skan	      && ref
2752169689Skan	      && INSN_P (ref));
2753169689Skan
2754169689Skan  if (!see_want_to_be_merged_with_extension (ref, def_se, DEF_EXTENSION))
2755169689Skan    {
2756169689Skan      /* The definition in the reference is too simple.  Don't try to merge.  */
2757169689Skan      if (dump_file)
2758169689Skan	{
2759169689Skan	  fprintf (dump_file, "Def merge skipped!\n");
2760169689Skan	  fprintf (dump_file, "Original instructions:\n");
2761169689Skan	  print_rtl_single (dump_file, ref);
2762169689Skan	  print_rtl_single (dump_file, def_se);
2763169689Skan	}
2764169689Skan
2765169689Skan      see_def_extension_not_merged (curr_ref_s, def_se);
2766169689Skan      /* Continue to the next extension.  */
2767169689Skan      return 1;
2768169689Skan    }
2769169689Skan
2770169689Skan  extension_code = see_get_extension_data (def_se, &source_mode);
2771169689Skan
2772169689Skan  /* Try to merge and simplify the extension.  */
2773169689Skan  source_extension_mode = GET_MODE (source_extension_reg);
2774169689Skan  dest_extension_mode = GET_MODE (dest_extension_reg);
2775169689Skan
2776169689Skan  pat = &PATTERN (ref_copy);
2777169689Skan  code = GET_CODE (*pat);
2778169689Skan
2779169689Skan  if (code == PARALLEL)
2780169689Skan    {
2781169689Skan      bool need_to_apply_change = false;
2782169689Skan
2783169689Skan      for (i = 0; i < XVECLEN (*pat, 0); i++)
2784169689Skan	{
2785169689Skan	  rtx *sub = &XVECEXP (*pat, 0, i);
2786169689Skan
2787169689Skan	  if (GET_CODE (*sub) == SET
2788169689Skan	      && GET_MODE (SET_SRC (*sub)) != VOIDmode
2789169689Skan	      && GET_MODE (SET_DEST (*sub)) == source_mode
2790169689Skan	      && ((REG_P (SET_DEST (*sub))
2791169689Skan		   && REGNO (SET_DEST (*sub)) == REGNO (source_extension_reg))
2792169689Skan		  || (GET_CODE (SET_DEST (*sub)) == SUBREG
2793169689Skan		      && REG_P (SUBREG_REG (SET_DEST (*sub)))
2794169689Skan		      && (REGNO (SUBREG_REG (SET_DEST (*sub))) ==
2795169689Skan			  REGNO (source_extension_reg)))))
2796169689Skan	    {
2797169689Skan	      rtx orig_src = SET_SRC (*sub);
2798169689Skan
2799169689Skan	      if (extension_code == SIGN_EXTEND)
2800169689Skan		temp_extension = gen_rtx_SIGN_EXTEND (dest_extension_mode,
2801169689Skan						      orig_src);
2802169689Skan	      else
2803169689Skan		temp_extension = gen_rtx_ZERO_EXTEND (dest_extension_mode,
2804169689Skan						      orig_src);
2805169689Skan	      simplified_temp_extension = simplify_rtx (temp_extension);
2806169689Skan	      temp_extension =
2807169689Skan		(simplified_temp_extension) ? simplified_temp_extension :
2808169689Skan					      temp_extension;
2809169689Skan	      new_set = gen_rtx_SET (VOIDmode, dest_extension_reg,
2810169689Skan				     temp_extension);
2811169689Skan	      validate_change (ref_copy, sub, new_set, 1);
2812169689Skan	      need_to_apply_change = true;
2813169689Skan	    }
2814169689Skan	}
2815169689Skan      if (need_to_apply_change)
2816169689Skan	if (apply_change_group ())
2817169689Skan	  merge_success = true;
2818169689Skan    }
2819169689Skan  else if (code == SET
2820169689Skan	   && GET_MODE (SET_SRC (*pat)) != VOIDmode
2821169689Skan	   && GET_MODE (SET_DEST (*pat)) == source_mode
2822169689Skan	   && ((REG_P (SET_DEST (*pat))
2823169689Skan		&& REGNO (SET_DEST (*pat)) == REGNO (source_extension_reg))
2824169689Skan	       || (GET_CODE (SET_DEST (*pat)) == SUBREG
2825169689Skan		   && REG_P (SUBREG_REG (SET_DEST (*pat)))
2826169689Skan		   && (REGNO (SUBREG_REG (SET_DEST (*pat))) ==
2827169689Skan		       REGNO (source_extension_reg)))))
2828169689Skan    {
2829169689Skan      rtx orig_src = SET_SRC (*pat);
2830169689Skan
2831169689Skan      if (extension_code == SIGN_EXTEND)
2832169689Skan	temp_extension = gen_rtx_SIGN_EXTEND (dest_extension_mode, orig_src);
2833169689Skan      else
2834169689Skan	temp_extension = gen_rtx_ZERO_EXTEND (dest_extension_mode, orig_src);
2835169689Skan      simplified_temp_extension = simplify_rtx (temp_extension);
2836169689Skan      temp_extension = (simplified_temp_extension) ? simplified_temp_extension :
2837169689Skan						     temp_extension;
2838169689Skan      new_set = gen_rtx_SET (VOIDmode, dest_extension_reg, temp_extension);
2839169689Skan      if (validate_change (ref_copy, pat, new_set, 0))
2840169689Skan	merge_success = true;
2841169689Skan    }
2842169689Skan  if (!merge_success)
2843169689Skan    {
2844169689Skan      /* The merge failed.  */
2845169689Skan      if (dump_file)
2846169689Skan	{
2847169689Skan	  fprintf (dump_file, "Def merge failed!\n");
2848169689Skan	  fprintf (dump_file, "Original instructions:\n");
2849169689Skan	  print_rtl_single (dump_file, ref);
2850169689Skan	  print_rtl_single (dump_file, def_se);
2851169689Skan	}
2852169689Skan
2853169689Skan      see_def_extension_not_merged (curr_ref_s, def_se);
2854169689Skan      /* Continue to the next extension.  */
2855169689Skan      return 1;
2856169689Skan    }
2857169689Skan
2858169689Skan  /* The merge succeeded!  */
2859169689Skan
2860169689Skan  /* Create a simple move instruction to assure the correctness of the code.  */
2861169689Skan  subreg = gen_lowpart_SUBREG (source_extension_mode, dest_extension_reg);
2862169689Skan  start_sequence ();
2863169689Skan  emit_move_insn (source_extension_reg, subreg);
2864169689Skan  move_insn = get_insns ();
2865169689Skan  end_sequence ();
2866169689Skan
2867169689Skan  /* Link the merged instruction to the newly created move instruction and
2868169689Skan     to the former created move instructions.  */
2869169689Skan  PREV_INSN (ref_copy) = NULL_RTX;
2870169689Skan  NEXT_INSN (ref_copy) = move_insn;
2871169689Skan  PREV_INSN (move_insn) = ref_copy;
2872169689Skan  NEXT_INSN (move_insn) = merged_ref_next;
2873169689Skan  if (merged_ref_next != NULL_RTX)
2874169689Skan    PREV_INSN (merged_ref_next) = move_insn;
2875169689Skan  curr_ref_s->merged_insn = ref_copy;
2876169689Skan
2877169689Skan  if (dump_file)
2878169689Skan    {
2879169689Skan      fprintf (dump_file, "Def merge succeeded!\n");
2880169689Skan      fprintf (dump_file, "Original instructions:\n");
2881169689Skan      print_rtl_single (dump_file, ref);
2882169689Skan      print_rtl_single (dump_file, def_se);
2883169689Skan      fprintf (dump_file, "Merged instruction:\n");
2884169689Skan      print_rtl_single (dump_file, ref_copy);
2885169689Skan      fprintf (dump_file, "Move instruction that was added:\n");
2886169689Skan      print_rtl_single (dump_file, move_insn);
2887169689Skan    }
2888169689Skan
2889169689Skan  /* Remove the current def_se from the unmerged_def_se_hash and insert it to
2890169689Skan     the merged_def_se_hash.  */
2891169689Skan  htab_clear_slot (curr_ref_s->unmerged_def_se_hash, (PTR *)slot);
2892169689Skan  if (!curr_ref_s->merged_def_se_hash)
2893169689Skan    curr_ref_s->merged_def_se_hash = htab_create (10,
2894169689Skan						  hash_descriptor_extension,
2895169689Skan						  eq_descriptor_extension,
2896169689Skan						  NULL);
2897169689Skan  rtx_slot = (rtx *) htab_find_slot (curr_ref_s->merged_def_se_hash,
2898169689Skan  				     dest_extension_reg, INSERT);
2899169689Skan  gcc_assert (*rtx_slot == NULL);
2900169689Skan  *rtx_slot = def_se;
2901169689Skan
2902169689Skan  return 1;
2903169689Skan}
2904169689Skan
2905169689Skan
2906169689Skan/* Try to eliminate extensions in this order:
2907169689Skan   a. Try to merge only the def extensions, one by one.
2908169689Skan   b. Try to merge only the use extensions, one by one.
2909169689Skan
2910169689Skan   TODO:
2911169689Skan   Try to merge any couple of use extensions simultaneously.
2912169689Skan   Try to merge any def extension with one or two uses extensions
2913169689Skan   simultaneously.
2914169689Skan
2915169689Skan   After all the merges are done, update the register properties for the basic
2916169689Skan   block and eliminate locally redundant use extensions.
2917169689Skan
2918169689Skan   This is a subroutine of see_merge_and_eliminate_extensions called
2919169689Skan   via splay_tree_foreach.
2920169689Skan   STN is the current node in the see_bb_splay_ar[i] splay tree.  It holds a
2921169689Skan   see_ref_s structure.  */
2922169689Skan
2923169689Skanstatic int
2924169689Skansee_handle_extensions_for_one_ref (splay_tree_node stn,
2925169689Skan				   void *data ATTRIBUTE_UNUSED)
2926169689Skan{
2927169689Skan  htab_t use_se_hash = ((struct see_ref_s *) (stn->value))->use_se_hash;
2928169689Skan  htab_t unmerged_def_se_hash =
2929169689Skan    ((struct see_ref_s *) (stn->value))->unmerged_def_se_hash;
2930169689Skan  htab_t merged_def_se_hash;
2931169689Skan  rtx ref = ((struct see_ref_s *) (stn->value))->insn;
2932169689Skan
2933169689Skan  if (dump_file)
2934169689Skan    {
2935169689Skan      fprintf (dump_file, "Handling ref:\n");
2936169689Skan      print_rtl_single (dump_file, ref);
2937169689Skan    }
2938169689Skan
2939169689Skan  /* a. Try to eliminate only def extensions, one by one.  */
2940169689Skan  if (unmerged_def_se_hash)
2941169689Skan    htab_traverse_noresize (unmerged_def_se_hash, see_merge_one_def_extension,
2942169689Skan    			    (PTR) (stn->value));
2943169689Skan
2944169689Skan  if (use_se_hash)
2945169689Skan    /* b. Try to eliminate only use extensions, one by one.  */
2946169689Skan    htab_traverse_noresize (use_se_hash, see_merge_one_use_extension,
2947169689Skan			    (PTR) (stn->value));
2948169689Skan
2949169689Skan  merged_def_se_hash = ((struct see_ref_s *) (stn->value))->merged_def_se_hash;
2950169689Skan
2951169689Skan  if (dump_file)
2952169689Skan    {
2953169689Skan      fprintf (dump_file, "The hashes of the current reference:\n");
2954169689Skan      if (unmerged_def_se_hash)
2955169689Skan	{
2956169689Skan	  fprintf (dump_file, "unmerged_def_se_hash:\n");
2957169689Skan	  htab_traverse (unmerged_def_se_hash, see_print_one_extension, NULL);
2958169689Skan	}
2959169689Skan      if (merged_def_se_hash)
2960169689Skan	{
2961169689Skan	  fprintf (dump_file, "merged_def_se_hash:\n");
2962169689Skan	  htab_traverse (merged_def_se_hash, see_print_one_extension, NULL);
2963169689Skan	}
2964169689Skan      if (use_se_hash)
2965169689Skan	{
2966169689Skan	  fprintf (dump_file, "use_se_hash:\n");
2967169689Skan	  htab_traverse (use_se_hash, see_print_one_extension, NULL);
2968169689Skan	}
2969169689Skan    }
2970169689Skan
2971169689Skan  /* Now that all the merges are done, update the register properties of the
2972169689Skan     basic block and eliminate locally redundant extensions.
2973169689Skan     It is important that we first traverse the use extensions hash and
2974169689Skan     afterwards the def extensions hashes.  */
2975169689Skan
2976169689Skan  if (use_se_hash)
2977169689Skan    htab_traverse_noresize (use_se_hash, see_set_prop_unmerged_use,
2978169689Skan			    (PTR) (stn->value));
2979169689Skan
2980169689Skan  if (unmerged_def_se_hash)
2981169689Skan    htab_traverse (unmerged_def_se_hash, see_set_prop_unmerged_def,
2982169689Skan		   (PTR) (stn->value));
2983169689Skan
2984169689Skan  if (merged_def_se_hash)
2985169689Skan    htab_traverse (merged_def_se_hash, see_set_prop_merged_def,
2986169689Skan		   (PTR) (stn->value));
2987169689Skan
2988169689Skan  /* Continue to the next definition.  */
2989169689Skan  return 0;
2990169689Skan}
2991169689Skan
2992169689Skan
2993169689Skan/* Phase 2 top level function.
2994169689Skan   In this phase, we try to merge def extensions and use extensions with their
2995169689Skan   references, and eliminate redundant extensions in the same basic block.
2996169689Skan   We also gather information for the next phases.  */
2997169689Skan
2998169689Skanstatic void
2999169689Skansee_merge_and_eliminate_extensions (void)
3000169689Skan{
3001169689Skan  int i = 0;
3002169689Skan
3003169689Skan  if (dump_file)
3004169689Skan    fprintf (dump_file,
3005169689Skan      "* Phase 2: Merge and eliminate locally redundant extensions.  *\n");
3006169689Skan
3007169689Skan  /* Traverse over all the splay trees of the basic blocks.  */
3008169689Skan  for (i = 0; i < last_bb; i++)
3009169689Skan    {
3010169689Skan      if (see_bb_splay_ar[i])
3011169689Skan	{
3012169689Skan	  if (dump_file)
3013169689Skan	    fprintf (dump_file, "Handling references for bb %d\n", i);
3014169689Skan	  /* Traverse over all the references in the basic block in forward
3015169689Skan	     order.  */
3016169689Skan	  splay_tree_foreach (see_bb_splay_ar[i],
3017169689Skan			      see_handle_extensions_for_one_ref, NULL);
3018169689Skan	}
3019169689Skan    }
3020169689Skan}
3021169689Skan
3022169689Skan
3023169689Skan/* Phase 1 implementation: Propagate extensions to uses.  */
3024169689Skan
3025169689Skan/* Insert REF_INSN into the splay tree of its basic block.
3026169689Skan   SE_INSN is the extension to store in the proper hash according to TYPE.
3027169689Skan
3028169689Skan   Return true if everything went well.
3029169689Skan   Otherwise, return false (this will cause the optimization to be aborted).  */
3030169689Skan
3031169689Skanstatic bool
3032169689Skansee_store_reference_and_extension (rtx ref_insn, rtx se_insn,
3033169689Skan				   enum extension_type type)
3034169689Skan{
3035169689Skan  rtx *rtx_slot;
3036169689Skan  int curr_bb_num;
3037169689Skan  splay_tree_node stn = NULL;
3038169689Skan  htab_t se_hash = NULL;
3039169689Skan  struct see_ref_s *ref_s = NULL;
3040169689Skan
3041169689Skan  /* Check the arguments.  */
3042169689Skan  gcc_assert (ref_insn && se_insn);
3043169689Skan  if (!see_bb_splay_ar)
3044169689Skan    return false;
3045169689Skan
3046169689Skan  curr_bb_num = BLOCK_NUM (ref_insn);
3047169689Skan  gcc_assert (curr_bb_num < last_bb && curr_bb_num >= 0);
3048169689Skan
3049169689Skan  /* Insert the reference to the splay tree of its basic block.  */
3050169689Skan  if (!see_bb_splay_ar[curr_bb_num])
3051169689Skan    /* The splay tree for this block doesn't exist yet, create it.  */
3052169689Skan    see_bb_splay_ar[curr_bb_num] = splay_tree_new (splay_tree_compare_ints,
3053169689Skan						    NULL, see_free_ref_s);
3054169689Skan  else
3055169689Skan    /* Splay tree already exists, check if the current reference is already
3056169689Skan       in it.  */
3057169689Skan    {
3058169689Skan      stn = splay_tree_lookup (see_bb_splay_ar[curr_bb_num],
3059169689Skan			       DF_INSN_LUID (df, ref_insn));
3060169689Skan      if (stn)
3061169689Skan	switch (type)
3062169689Skan	  {
3063169689Skan	  case EXPLICIT_DEF_EXTENSION:
3064169689Skan	    se_hash =
3065169689Skan	      ((struct see_ref_s *) (stn->value))->unmerged_def_se_hash;
3066169689Skan	    if (!se_hash)
3067169689Skan	      {
3068169689Skan		se_hash = htab_create (10,
3069169689Skan				       hash_descriptor_extension,
3070169689Skan				       eq_descriptor_extension,
3071169689Skan				       NULL);
3072169689Skan		((struct see_ref_s *) (stn->value))->unmerged_def_se_hash =
3073169689Skan		  se_hash;
3074169689Skan	      }
3075169689Skan	    break;
3076169689Skan	  case IMPLICIT_DEF_EXTENSION:
3077169689Skan	    se_hash = ((struct see_ref_s *) (stn->value))->merged_def_se_hash;
3078169689Skan	    if (!se_hash)
3079169689Skan	      {
3080169689Skan		se_hash = htab_create (10,
3081169689Skan				       hash_descriptor_extension,
3082169689Skan				       eq_descriptor_extension,
3083169689Skan				       NULL);
3084169689Skan		((struct see_ref_s *) (stn->value))->merged_def_se_hash =
3085169689Skan		  se_hash;
3086169689Skan	      }
3087169689Skan	    break;
3088169689Skan	  case USE_EXTENSION:
3089169689Skan	    se_hash = ((struct see_ref_s *) (stn->value))->use_se_hash;
3090169689Skan	    if (!se_hash)
3091169689Skan	      {
3092169689Skan		se_hash = htab_create (10,
3093169689Skan				       hash_descriptor_extension,
3094169689Skan				       eq_descriptor_extension,
3095169689Skan				       NULL);
3096169689Skan		((struct see_ref_s *) (stn->value))->use_se_hash = se_hash;
3097169689Skan	      }
3098169689Skan	    break;
3099169689Skan	  default:
3100169689Skan	    gcc_unreachable ();
3101169689Skan	  }
3102169689Skan    }
3103169689Skan
3104169689Skan  /* Initialize a new see_ref_s structure and insert it to the splay
3105169689Skan     tree.  */
3106169689Skan  if (!stn)
3107169689Skan    {
3108169689Skan      ref_s = xmalloc (sizeof (struct see_ref_s));
3109169689Skan      ref_s->luid = DF_INSN_LUID (df, ref_insn);
3110169689Skan      ref_s->insn = ref_insn;
3111169689Skan      ref_s->merged_insn = NULL;
3112169689Skan
3113169689Skan      /* Initialize the hashes.  */
3114169689Skan      switch (type)
3115169689Skan	{
3116169689Skan	case EXPLICIT_DEF_EXTENSION:
3117169689Skan	  ref_s->unmerged_def_se_hash = htab_create (10,
3118169689Skan						     hash_descriptor_extension,
3119169689Skan						     eq_descriptor_extension,
3120169689Skan						     NULL);
3121169689Skan	  se_hash = ref_s->unmerged_def_se_hash;
3122169689Skan	  ref_s->merged_def_se_hash = NULL;
3123169689Skan	  ref_s->use_se_hash = NULL;
3124169689Skan	  break;
3125169689Skan	case IMPLICIT_DEF_EXTENSION:
3126169689Skan	  ref_s->merged_def_se_hash = htab_create (10,
3127169689Skan						   hash_descriptor_extension,
3128169689Skan						   eq_descriptor_extension,
3129169689Skan						   NULL);
3130169689Skan	  se_hash = ref_s->merged_def_se_hash;
3131169689Skan	  ref_s->unmerged_def_se_hash = NULL;
3132169689Skan	  ref_s->use_se_hash = NULL;
3133169689Skan	  break;
3134169689Skan	case USE_EXTENSION:
3135169689Skan	  ref_s->use_se_hash = htab_create (10,
3136169689Skan					    hash_descriptor_extension,
3137169689Skan					    eq_descriptor_extension,
3138169689Skan					    NULL);
3139169689Skan	  se_hash = ref_s->use_se_hash;
3140169689Skan	  ref_s->unmerged_def_se_hash = NULL;
3141169689Skan	  ref_s->merged_def_se_hash = NULL;
3142169689Skan	  break;
3143169689Skan	default:
3144169689Skan	  gcc_unreachable ();
3145169689Skan	}
3146169689Skan    }
3147169689Skan
3148169689Skan  /* Insert the new extension instruction into the correct se_hash of the
3149169689Skan     current reference.  */
3150169689Skan  rtx_slot = (rtx *) htab_find_slot (se_hash, se_insn, INSERT);
3151169689Skan  if (*rtx_slot != NULL)
3152169689Skan    {
3153169689Skan      gcc_assert (type == USE_EXTENSION);
3154169689Skan      gcc_assert (rtx_equal_p (PATTERN (*rtx_slot), PATTERN (se_insn)));
3155169689Skan    }
3156169689Skan  else
3157169689Skan    *rtx_slot = se_insn;
3158169689Skan
3159169689Skan  /* If this is a new reference, insert it into the splay_tree.  */
3160169689Skan  if (!stn)
3161169689Skan    splay_tree_insert (see_bb_splay_ar[curr_bb_num],
3162169689Skan		       DF_INSN_LUID (df, ref_insn), (splay_tree_value) ref_s);
3163169689Skan  return true;
3164169689Skan}
3165169689Skan
3166169689Skan
3167169689Skan/* Go over all the defs, for each relevant definition (defined below) store its
3168169689Skan   instruction as a reference.
3169169689Skan
3170169689Skan   A definition is relevant if its root has
3171169689Skan   ((entry_type == SIGN_EXTENDED_DEF) || (entry_type == ZERO_EXTENDED_DEF)) and
3172169689Skan   his source_mode is not narrower then the the roots source_mode.
3173169689Skan
3174169689Skan   Return the number of relevant defs or negative number if something bad had
3175169689Skan   happened and the optimization should be aborted.  */
3176169689Skan
3177169689Skanstatic int
3178169689Skansee_handle_relevant_defs (void)
3179169689Skan{
3180169689Skan  rtx insn = NULL;
3181169689Skan  rtx se_insn = NULL;
3182169689Skan  rtx reg = NULL;
3183169689Skan  rtx ref_insn = NULL;
3184169689Skan  struct web_entry *root_entry = NULL;
3185169689Skan  unsigned int i;
3186169689Skan  int num_relevant_defs = 0;
3187169689Skan  enum rtx_code extension_code;
3188169689Skan
3189169689Skan  for (i = 0; i < defs_num; i++)
3190169689Skan    {
3191169689Skan      insn = DF_REF_INSN (DF_DEFS_GET (df, i));
3192169689Skan      reg = DF_REF_REAL_REG (DF_DEFS_GET (df, i));
3193169689Skan
3194169689Skan      if (!insn)
3195169689Skan	continue;
3196169689Skan
3197169689Skan      if (!INSN_P (insn))
3198169689Skan	continue;
3199169689Skan
3200169689Skan      root_entry = unionfind_root (&def_entry[i]);
3201169689Skan
3202169689Skan      if (ENTRY_EI (root_entry)->relevancy != SIGN_EXTENDED_DEF
3203169689Skan	  && ENTRY_EI (root_entry)->relevancy != ZERO_EXTENDED_DEF)
3204169689Skan	/* The current web is not relevant.  Continue to the next def.  */
3205169689Skan	continue;
3206169689Skan
3207169689Skan      if (root_entry->reg)
3208169689Skan	/* It isn't possible to have two different register for the same
3209169689Skan	   web.  */
3210169689Skan	gcc_assert (rtx_equal_p (root_entry->reg, reg));
3211169689Skan      else
3212169689Skan	root_entry->reg = reg;
3213169689Skan
3214169689Skan      /* The current definition is an EXTENDED_DEF or a definition that its
3215169689Skan	 source_mode is narrower then its web's source_mode.
3216169689Skan	 This means that we need to generate the implicit extension explicitly
3217169689Skan	 and store it in the current reference's merged_def_se_hash.  */
3218169689Skan      if (ENTRY_EI (&def_entry[i])->local_relevancy == EXTENDED_DEF
3219169689Skan	  || (ENTRY_EI (&def_entry[i])->local_source_mode <
3220169689Skan	      ENTRY_EI (root_entry)->source_mode))
3221169689Skan	{
3222169689Skan	  num_relevant_defs++;
3223169689Skan
3224169689Skan	  if (ENTRY_EI (root_entry)->relevancy == SIGN_EXTENDED_DEF)
3225169689Skan	    extension_code = SIGN_EXTEND;
3226169689Skan	  else
3227169689Skan	    extension_code = ZERO_EXTEND;
3228169689Skan
3229169689Skan	  se_insn =
3230169689Skan	    see_gen_normalized_extension (reg, extension_code,
3231169689Skan	    				  ENTRY_EI (root_entry)->source_mode);
3232169689Skan
3233169689Skan	  /* This is a dummy extension, mark it as deleted.  */
3234169689Skan	  INSN_DELETED_P (se_insn) = 1;
3235169689Skan
3236169689Skan	  if (!see_store_reference_and_extension (insn, se_insn,
3237169689Skan	  					  IMPLICIT_DEF_EXTENSION))
3238169689Skan	    /* Something bad happened.  Abort the optimization.  */
3239169689Skan	    return -1;
3240169689Skan	  continue;
3241169689Skan	}
3242169689Skan
3243169689Skan      ref_insn = PREV_INSN (insn);
3244169689Skan      gcc_assert (BLOCK_NUM (ref_insn) == BLOCK_NUM (insn));
3245169689Skan
3246169689Skan      num_relevant_defs++;
3247169689Skan
3248169689Skan      if (!see_store_reference_and_extension (ref_insn, insn,
3249169689Skan      					      EXPLICIT_DEF_EXTENSION))
3250169689Skan	/* Something bad happened.  Abort the optimization.  */
3251169689Skan	return -1;
3252169689Skan    }
3253169689Skan   return num_relevant_defs;
3254169689Skan}
3255169689Skan
3256169689Skan
3257169689Skan/* Go over all the uses, for each use in relevant web store its instruction as
3258169689Skan   a reference and generate an extension before it.
3259169689Skan
3260169689Skan   Return the number of relevant uses or negative number if something bad had
3261169689Skan   happened and the optimization should be aborted.  */
3262169689Skan
3263169689Skanstatic int
3264169689Skansee_handle_relevant_uses (void)
3265169689Skan{
3266169689Skan  rtx insn = NULL;
3267169689Skan  rtx reg = NULL;
3268169689Skan  struct web_entry *root_entry = NULL;
3269169689Skan  rtx se_insn = NULL;
3270169689Skan  unsigned int i;
3271169689Skan  int num_relevant_uses = 0;
3272169689Skan  enum rtx_code extension_code;
3273169689Skan
3274169689Skan  for (i = 0; i < uses_num; i++)
3275169689Skan    {
3276169689Skan      insn = DF_REF_INSN (DF_USES_GET (df, i));
3277169689Skan      reg = DF_REF_REAL_REG (DF_USES_GET (df, i));
3278169689Skan
3279169689Skan      if (!insn)
3280169689Skan	continue;
3281169689Skan
3282169689Skan      if (!INSN_P (insn))
3283169689Skan	continue;
3284169689Skan
3285169689Skan      root_entry = unionfind_root (&use_entry[i]);
3286169689Skan
3287169689Skan      if (ENTRY_EI (root_entry)->relevancy != SIGN_EXTENDED_DEF
3288169689Skan	  && ENTRY_EI (root_entry)->relevancy != ZERO_EXTENDED_DEF)
3289169689Skan	/* The current web is not relevant.  Continue to the next use.  */
3290169689Skan	continue;
3291169689Skan
3292169689Skan      if (root_entry->reg)
3293169689Skan	/* It isn't possible to have two different register for the same
3294169689Skan	   web.  */
3295169689Skan	gcc_assert (rtx_equal_p (root_entry->reg, reg));
3296169689Skan      else
3297169689Skan	root_entry->reg = reg;
3298169689Skan
3299169689Skan      /* Generate the use extension.  */
3300169689Skan      if (ENTRY_EI (root_entry)->relevancy == SIGN_EXTENDED_DEF)
3301169689Skan	extension_code = SIGN_EXTEND;
3302169689Skan      else
3303169689Skan	extension_code = ZERO_EXTEND;
3304169689Skan
3305169689Skan      se_insn =
3306169689Skan	see_gen_normalized_extension (reg, extension_code,
3307169689Skan				      ENTRY_EI (root_entry)->source_mode);
3308169689Skan      if (!se_insn)
3309169689Skan	/* This is very bad, abort the transformation.  */
3310169689Skan	return -1;
3311169689Skan
3312169689Skan      num_relevant_uses++;
3313169689Skan
3314169689Skan      if (!see_store_reference_and_extension (insn, se_insn,
3315169689Skan      					      USE_EXTENSION))
3316169689Skan	/* Something bad happened.  Abort the optimization.  */
3317169689Skan	return -1;
3318169689Skan    }
3319169689Skan
3320169689Skan  return num_relevant_uses;
3321169689Skan}
3322169689Skan
3323169689Skan
3324169689Skan/* Updates the relevancy of all the uses.
3325169689Skan   The information of the i'th use is stored in use_entry[i].
3326169689Skan   Currently all the uses are relevant for the optimization except for uses that
3327169689Skan   are in LIBCALL or RETVAL instructions.  */
3328169689Skan
3329169689Skanstatic void
3330169689Skansee_update_uses_relevancy (void)
3331169689Skan{
3332169689Skan  rtx insn = NULL;
3333169689Skan  rtx reg = NULL;
3334169689Skan  struct see_entry_extra_info *curr_entry_extra_info;
3335169689Skan  enum entry_type et;
3336169689Skan  unsigned int i;
3337169689Skan
3338169689Skan  if (!df || !use_entry)
3339169689Skan    return;
3340169689Skan
3341169689Skan  for (i = 0; i < uses_num; i++)
3342169689Skan    {
3343169689Skan
3344169689Skan      insn = DF_REF_INSN (DF_USES_GET (df, i));
3345169689Skan      reg = DF_REF_REAL_REG (DF_USES_GET (df, i));
3346169689Skan
3347169689Skan      et = RELEVANT_USE;
3348169689Skan
3349169689Skan      if (insn)
3350169689Skan	{
3351169689Skan	  if (!INSN_P (insn))
3352169689Skan	    et = NOT_RELEVANT;
3353169689Skan	  if (insn && find_reg_note (insn, REG_LIBCALL, NULL_RTX))
3354169689Skan	    et = NOT_RELEVANT;
3355169689Skan	  if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
3356169689Skan	    et = NOT_RELEVANT;
3357169689Skan	}
3358169689Skan      else
3359169689Skan	et = NOT_RELEVANT;
3360169689Skan
3361169689Skan      if (dump_file)
3362169689Skan	{
3363169689Skan	  fprintf (dump_file, "u%i insn %i reg %i ",
3364169689Skan          i, (insn ? INSN_UID (insn) : -1), REGNO (reg));
3365169689Skan	  if (et == NOT_RELEVANT)
3366169689Skan	    fprintf (dump_file, "NOT RELEVANT \n");
3367169689Skan	  else
3368169689Skan	    fprintf (dump_file, "RELEVANT USE \n");
3369169689Skan	}
3370169689Skan
3371169689Skan      curr_entry_extra_info = xmalloc (sizeof (struct see_entry_extra_info));
3372169689Skan      curr_entry_extra_info->relevancy = et;
3373169689Skan      curr_entry_extra_info->local_relevancy = et;
3374169689Skan      use_entry[i].extra_info = curr_entry_extra_info;
3375169689Skan      use_entry[i].reg = NULL;
3376169689Skan      use_entry[i].pred = NULL;
3377169689Skan    }
3378169689Skan}
3379169689Skan
3380169689Skan
3381169689Skan/* A definition in a candidate for this optimization only if its pattern is
3382169689Skan   recognized as relevant in this function.
3383169689Skan   INSN is the instruction to be recognized.
3384169689Skan
3385169689Skan-  If this is the pattern of a common sign extension after definition:
3386169689Skan   PREV_INSN (INSN):	def (reg:NARROWmode r)
3387169689Skan   INSN:		set ((reg:WIDEmode r')
3388169689Skan   			     (sign_extend:WIDEmode (reg:NARROWmode r)))
3389169689Skan   return SIGN_EXTENDED_DEF and set SOURCE_MODE to NARROWmode.
3390169689Skan
3391169689Skan-  If this is the pattern of a common zero extension after definition:
3392169689Skan   PREV_INSN (INSN):	def (reg:NARROWmode r)
3393169689Skan   INSN:		set ((reg:WIDEmode r')
3394169689Skan   			     (zero_extend:WIDEmode (reg:NARROWmode r)))
3395169689Skan   return ZERO_EXTENDED_DEF and set SOURCE_MODE to NARROWmode.
3396169689Skan
3397169689Skan-  Otherwise,
3398169689Skan
3399169689Skan   For the pattern:
3400169689Skan   INSN:  set ((reg:WIDEmode r) (sign_extend:WIDEmode (...expr...)))
3401169689Skan   return EXTENDED_DEF and set SOURCE_MODE to the mode of expr.
3402169689Skan
3403169689Skan   For the pattern:
3404169689Skan   INSN:  set ((reg:WIDEmode r) (zero_extend:WIDEmode (...expr...)))
3405169689Skan   return EXTENDED_DEF and set SOURCE_MODE_UNSIGNED to the mode of expr.
3406169689Skan
3407169689Skan   For the pattern:
3408169689Skan   INSN:  set ((reg:WIDEmode r) (CONST_INT (...)))
3409169689Skan   return EXTENDED_DEF and set SOURCE_MODE(_UNSIGNED) to the narrowest mode that
3410169689Skan   is implicitly sign(zero) extended to WIDEmode in the INSN.
3411169689Skan
3412169689Skan-  FIXME: Extensions that are not adjacent to their definition and EXTENDED_DEF
3413169689Skan   that is part of a PARALLEL instruction are not handled.
3414169689Skan   These restriction can be relaxed.  */
3415169689Skan
3416169689Skanstatic enum entry_type
3417169689Skansee_analyze_one_def (rtx insn, enum machine_mode *source_mode,
3418169689Skan		     enum machine_mode *source_mode_unsigned)
3419169689Skan{
3420169689Skan  enum rtx_code extension_code;
3421169689Skan  rtx rhs = NULL;
3422169689Skan  rtx lhs = NULL;
3423169689Skan  rtx set = NULL;
3424169689Skan  rtx source_register = NULL;
3425169689Skan  rtx prev_insn = NULL;
3426169689Skan  rtx next_insn = NULL;
3427169689Skan  enum machine_mode mode;
3428169689Skan  enum machine_mode next_source_mode;
3429169689Skan  HOST_WIDE_INT val = 0;
3430169689Skan  HOST_WIDE_INT val2 = 0;
3431169689Skan  int i = 0;
3432169689Skan
3433169689Skan  *source_mode = MAX_MACHINE_MODE;
3434169689Skan  *source_mode_unsigned = MAX_MACHINE_MODE;
3435169689Skan
3436169689Skan  if (!insn)
3437169689Skan    return NOT_RELEVANT;
3438169689Skan
3439169689Skan  if (!INSN_P (insn))
3440169689Skan    return NOT_RELEVANT;
3441169689Skan
3442169689Skan  extension_code = see_get_extension_data (insn, source_mode);
3443169689Skan  switch (extension_code)
3444169689Skan    {
3445169689Skan    case SIGN_EXTEND:
3446169689Skan    case ZERO_EXTEND:
3447169689Skan      source_register = see_get_extension_reg (insn, 0);
3448169689Skan      /* FIXME: This restriction can be relaxed.  The only thing that is
3449169689Skan	 important is that the reference would be inside the same basic block
3450169689Skan	 as the extension.  */
3451169689Skan      prev_insn = PREV_INSN (insn);
3452169689Skan      if (!prev_insn || !INSN_P (prev_insn))
3453169689Skan	return NOT_RELEVANT;
3454169689Skan
3455169689Skan      if (!reg_set_between_p (source_register, PREV_INSN (prev_insn), insn))
3456169689Skan	return NOT_RELEVANT;
3457169689Skan
3458169689Skan      if (find_reg_note (prev_insn, REG_LIBCALL, NULL_RTX))
3459169689Skan	return NOT_RELEVANT;
3460169689Skan
3461169689Skan      if (find_reg_note (prev_insn, REG_RETVAL, NULL_RTX))
3462169689Skan	return NOT_RELEVANT;
3463169689Skan
3464169689Skan      /* If we can't use copy_rtx on the reference it can't be a reference.  */
3465169689Skan      if (GET_CODE (PATTERN (prev_insn)) == PARALLEL
3466169689Skan	   && asm_noperands (PATTERN (prev_insn)) >= 0)
3467169689Skan	return NOT_RELEVANT;
3468169689Skan
3469169689Skan      /* Now, check if this extension is a reference itself.  If so, it is not
3470169689Skan	 relevant.  Handling this extension as relevant would make things much
3471169689Skan	 more complicated.  */
3472169689Skan      next_insn = NEXT_INSN (insn);
3473169689Skan      if (next_insn
3474169689Skan	  && INSN_P (next_insn)
3475169689Skan	  && (see_get_extension_data (next_insn, &next_source_mode) !=
3476169689Skan	      NOT_RELEVANT))
3477169689Skan	{
3478169689Skan	  rtx curr_dest_register = see_get_extension_reg (insn, 1);
3479169689Skan	  rtx next_source_register = see_get_extension_reg (next_insn, 0);
3480169689Skan
3481169689Skan	  if (REGNO (curr_dest_register) == REGNO (next_source_register))
3482169689Skan	    return NOT_RELEVANT;
3483169689Skan	}
3484169689Skan
3485169689Skan      if (extension_code == SIGN_EXTEND)
3486169689Skan	return SIGN_EXTENDED_DEF;
3487169689Skan      else
3488169689Skan	return ZERO_EXTENDED_DEF;
3489169689Skan
3490169689Skan    case UNKNOWN:
3491169689Skan      /* This may still be an EXTENDED_DEF.  */
3492169689Skan
3493169689Skan      /* FIXME: This restriction can be relaxed.  It is possible to handle
3494169689Skan	 PARALLEL insns too.  */
3495169689Skan      set = single_set (insn);
3496169689Skan      if (!set)
3497169689Skan	return NOT_RELEVANT;
3498169689Skan      rhs = SET_SRC (set);
3499169689Skan      lhs = SET_DEST (set);
3500169689Skan
3501169689Skan      /* Don't handle extensions to something other then register or
3502169689Skan	 subregister.  */
3503169689Skan      if (!REG_P (lhs) && !SUBREG_REG (lhs))
3504169689Skan	return NOT_RELEVANT;
3505169689Skan
3506169689Skan      switch (GET_CODE (rhs))
3507169689Skan	{
3508169689Skan	case SIGN_EXTEND:
3509169689Skan	  *source_mode = GET_MODE (XEXP (rhs, 0));
3510169689Skan	  *source_mode_unsigned = MAX_MACHINE_MODE;
3511169689Skan	  return EXTENDED_DEF;
3512169689Skan	case ZERO_EXTEND:
3513169689Skan	  *source_mode = MAX_MACHINE_MODE;
3514169689Skan	  *source_mode_unsigned = GET_MODE (XEXP (rhs, 0));
3515169689Skan	  return EXTENDED_DEF;
3516169689Skan	case CONST_INT:
3517169689Skan
3518169689Skan	  val = INTVAL (rhs);
3519169689Skan
3520169689Skan	  /* Find the narrowest mode, val could fit into.  */
3521169689Skan	  for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT), i = 0;
3522169689Skan	       GET_MODE_BITSIZE (mode) < BITS_PER_WORD;
3523169689Skan	       mode = GET_MODE_WIDER_MODE (mode), i++)
3524169689Skan	    {
3525169689Skan	      val2 = trunc_int_for_mode (val, mode);
3526169689Skan  	      if (val2 == val && *source_mode == MAX_MACHINE_MODE)
3527169689Skan		*source_mode = mode;
3528169689Skan	      if (val == (val & (HOST_WIDE_INT)GET_MODE_MASK (mode))
3529169689Skan		  && *source_mode_unsigned == MAX_MACHINE_MODE)
3530169689Skan		*source_mode_unsigned = mode;
3531169689Skan	      if (*source_mode != MAX_MACHINE_MODE
3532169689Skan		  && *source_mode_unsigned !=MAX_MACHINE_MODE)
3533169689Skan		return EXTENDED_DEF;
3534169689Skan	    }
3535169689Skan	  if (*source_mode != MAX_MACHINE_MODE
3536169689Skan	      || *source_mode_unsigned !=MAX_MACHINE_MODE)
3537169689Skan	    return EXTENDED_DEF;
3538169689Skan	  return NOT_RELEVANT;
3539169689Skan	default:
3540169689Skan	  return NOT_RELEVANT;
3541169689Skan	}
3542169689Skan    default:
3543169689Skan      gcc_unreachable ();
3544169689Skan    }
3545169689Skan}
3546169689Skan
3547169689Skan
3548169689Skan/* Updates the relevancy and source_mode of all the definitions.
3549169689Skan   The information of the i'th definition is stored in def_entry[i].  */
3550169689Skan
3551169689Skanstatic void
3552169689Skansee_update_defs_relevancy (void)
3553169689Skan{
3554169689Skan  struct see_entry_extra_info *curr_entry_extra_info;
3555169689Skan  unsigned int i;
3556169689Skan  rtx insn = NULL;
3557169689Skan  rtx reg = NULL;
3558169689Skan  enum entry_type et;
3559169689Skan  enum machine_mode source_mode;
3560169689Skan  enum machine_mode source_mode_unsigned;
3561169689Skan
3562169689Skan  if (!df || !def_entry)
3563169689Skan    return;
3564169689Skan
3565169689Skan  for (i = 0; i < defs_num; i++)
3566169689Skan    {
3567169689Skan      insn = DF_REF_INSN (DF_DEFS_GET (df, i));
3568169689Skan      reg = DF_REF_REAL_REG (DF_DEFS_GET (df, i));
3569169689Skan
3570169689Skan      et = see_analyze_one_def (insn, &source_mode, &source_mode_unsigned);
3571169689Skan
3572169689Skan      curr_entry_extra_info = xmalloc (sizeof (struct see_entry_extra_info));
3573169689Skan      curr_entry_extra_info->relevancy = et;
3574169689Skan      curr_entry_extra_info->local_relevancy = et;
3575169689Skan      if (et != EXTENDED_DEF)
3576169689Skan	{
3577169689Skan	  curr_entry_extra_info->source_mode = source_mode;
3578169689Skan	  curr_entry_extra_info->local_source_mode = source_mode;
3579169689Skan	}
3580169689Skan      else
3581169689Skan	{
3582169689Skan	  curr_entry_extra_info->source_mode_signed = source_mode;
3583169689Skan	  curr_entry_extra_info->source_mode_unsigned = source_mode_unsigned;
3584169689Skan	}
3585169689Skan      def_entry[i].extra_info = curr_entry_extra_info;
3586169689Skan      def_entry[i].reg = NULL;
3587169689Skan      def_entry[i].pred = NULL;
3588169689Skan
3589169689Skan      if (dump_file)
3590169689Skan	{
3591169689Skan	  if (et == NOT_RELEVANT)
3592169689Skan	    {
3593169689Skan	      fprintf (dump_file, "d%i insn %i reg %i ",
3594169689Skan              i, (insn ? INSN_UID (insn) : -1), REGNO (reg));
3595169689Skan	      fprintf (dump_file, "NOT RELEVANT \n");
3596169689Skan	    }
3597169689Skan	  else
3598169689Skan	    {
3599169689Skan	      fprintf (dump_file, "d%i insn %i reg %i ",
3600169689Skan		       i ,INSN_UID (insn), REGNO (reg));
3601169689Skan	      fprintf (dump_file, "RELEVANT - ");
3602169689Skan	      switch (et)
3603169689Skan		{
3604169689Skan		case SIGN_EXTENDED_DEF :
3605169689Skan		  fprintf (dump_file, "SIGN_EXTENDED_DEF, source_mode = %s\n",
3606169689Skan			   GET_MODE_NAME (source_mode));
3607169689Skan		  break;
3608169689Skan		case ZERO_EXTENDED_DEF :
3609169689Skan		  fprintf (dump_file, "ZERO_EXTENDED_DEF, source_mode = %s\n",
3610169689Skan			   GET_MODE_NAME (source_mode));
3611169689Skan		  break;
3612169689Skan		case EXTENDED_DEF :
3613169689Skan		  fprintf (dump_file, "EXTENDED_DEF, ");
3614169689Skan		  if (source_mode != MAX_MACHINE_MODE
3615169689Skan		      && source_mode_unsigned != MAX_MACHINE_MODE)
3616169689Skan		    {
3617169689Skan		      fprintf (dump_file, "positive const, ");
3618169689Skan		      fprintf (dump_file, "source_mode_signed = %s, ",
3619169689Skan			       GET_MODE_NAME (source_mode));
3620169689Skan		      fprintf (dump_file, "source_mode_unsigned = %s\n",
3621169689Skan			       GET_MODE_NAME (source_mode_unsigned));
3622169689Skan		    }
3623169689Skan		  else if (source_mode != MAX_MACHINE_MODE)
3624169689Skan		    fprintf (dump_file, "source_mode_signed = %s\n",
3625169689Skan			     GET_MODE_NAME (source_mode));
3626169689Skan		  else
3627169689Skan		    fprintf (dump_file, "source_mode_unsigned = %s\n",
3628169689Skan			     GET_MODE_NAME (source_mode_unsigned));
3629169689Skan		  break;
3630169689Skan		default :
3631169689Skan		  gcc_unreachable ();
3632169689Skan		}
3633169689Skan	    }
3634169689Skan	}
3635169689Skan    }
3636169689Skan}
3637169689Skan
3638169689Skan
3639169689Skan/* Phase 1 top level function.
3640169689Skan   In this phase the relevancy of all the definitions and uses are checked,
3641169689Skan   later the webs are produces and the extensions are generated.
3642169689Skan   These extensions are not emitted yet into the insns stream.
3643169689Skan
3644169689Skan   returns true if at list one relevant web was found and there were no
3645169689Skan   problems, otherwise return false.  */
3646169689Skan
3647169689Skanstatic bool
3648169689Skansee_propagate_extensions_to_uses (void)
3649169689Skan{
3650169689Skan  unsigned int i = 0;
3651169689Skan  int num_relevant_uses;
3652169689Skan  int num_relevant_defs;
3653169689Skan
3654169689Skan  if (dump_file)
3655169689Skan    fprintf (dump_file,
3656169689Skan      "* Phase 1: Propagate extensions to uses.  *\n");
3657169689Skan
3658169689Skan  /* Update the relevancy of references using the DF object.  */
3659169689Skan  see_update_defs_relevancy ();
3660169689Skan  see_update_uses_relevancy ();
3661169689Skan
3662169689Skan  /* Produce the webs and update the extra_info of the root.
3663169689Skan     In general, a web is relevant if all its definitions and uses are relevant
3664169689Skan     and there is at least one definition that was marked as SIGN_EXTENDED_DEF
3665169689Skan     or ZERO_EXTENDED_DEF.  */
3666169689Skan  for (i = 0; i < uses_num; i++)
3667169689Skan    union_defs (df, DF_USES_GET (df, i), def_entry, use_entry,
3668169689Skan		see_update_leader_extra_info);
3669169689Skan
3670169689Skan  /* Generate use extensions for references and insert these
3671169689Skan     references to see_bb_splay_ar data structure.    */
3672169689Skan  num_relevant_uses = see_handle_relevant_uses ();
3673169689Skan
3674169689Skan  if (num_relevant_uses < 0)
3675169689Skan    return false;
3676169689Skan
3677169689Skan  /* Store the def extensions in their references structures and insert these
3678169689Skan     references to see_bb_splay_ar data structure.    */
3679169689Skan  num_relevant_defs = see_handle_relevant_defs ();
3680169689Skan
3681169689Skan  if (num_relevant_defs < 0)
3682169689Skan    return false;
3683169689Skan
3684169689Skan return num_relevant_uses > 0 || num_relevant_defs > 0;
3685169689Skan}
3686169689Skan
3687169689Skan
3688169689Skan/* Main entry point for the sign extension elimination optimization.  */
3689169689Skan
3690169689Skanstatic void
3691169689Skansee_main (void)
3692169689Skan{
3693169689Skan  bool cont = false;
3694169689Skan  int i = 0;
3695169689Skan
3696169689Skan  /* Initialize global data structures.  */
3697169689Skan  see_initialize_data_structures ();
3698169689Skan
3699169689Skan  /* Phase 1: Propagate extensions to uses.  */
3700169689Skan  cont = see_propagate_extensions_to_uses ();
3701169689Skan
3702169689Skan  if (cont)
3703169689Skan    {
3704169689Skan      init_recog ();
3705169689Skan
3706169689Skan      /* Phase 2: Merge and eliminate locally redundant extensions.  */
3707169689Skan      see_merge_and_eliminate_extensions ();
3708169689Skan
3709169689Skan      /* Phase 3: Eliminate globally redundant extensions.  */
3710169689Skan      see_execute_LCM ();
3711169689Skan
3712169689Skan      /* Phase 4: Commit changes to the insn stream.  */
3713169689Skan      see_commit_changes ();
3714169689Skan
3715169689Skan      if (dump_file)
3716169689Skan	{
3717169689Skan	  /* For debug purpose only.  */
3718169689Skan	  fprintf (dump_file, "see_pre_extension_hash:\n");
3719169689Skan	  htab_traverse (see_pre_extension_hash, see_print_pre_extension_expr,
3720169689Skan      			 NULL);
3721169689Skan
3722169689Skan	  for (i = 0; i < last_bb; i++)
3723169689Skan	    {
3724169689Skan 	      if (see_bb_hash_ar[i])
3725169689Skan		/* Traverse over all the references in the basic block in
3726169689Skan		   forward order.  */
3727169689Skan		{
3728169689Skan		  fprintf (dump_file,
3729169689Skan			   "Searching register properties in bb %d\n", i);
3730169689Skan		  htab_traverse (see_bb_hash_ar[i],
3731169689Skan		  		 see_print_register_properties, NULL);
3732169689Skan		}
3733169689Skan	    }
3734169689Skan	}
3735169689Skan    }
3736169689Skan
3737169689Skan  /* Free global data structures.  */
3738169689Skan  see_free_data_structures ();
3739169689Skan}
3740169689Skan
3741169689Skan
3742169689Skanstatic bool
3743169689Skangate_handle_see (void)
3744169689Skan{
3745169689Skan  return optimize > 1 && flag_see;
3746169689Skan}
3747169689Skan
3748169689Skanstatic unsigned int
3749169689Skanrest_of_handle_see (void)
3750169689Skan{
3751169689Skan  int no_new_pseudos_bcp = no_new_pseudos;
3752169689Skan
3753169689Skan  no_new_pseudos = 0;
3754169689Skan  see_main ();
3755169689Skan  no_new_pseudos = no_new_pseudos_bcp;
3756169689Skan
3757169689Skan  delete_trivially_dead_insns (get_insns (), max_reg_num ());
3758169689Skan  update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
3759169689Skan  				    (PROP_DEATH_NOTES));
3760169689Skan  cleanup_cfg (CLEANUP_EXPENSIVE);
3761169689Skan  reg_scan (get_insns (), max_reg_num ());
3762169689Skan
3763169689Skan  return 0;
3764169689Skan}
3765169689Skan
3766169689Skanstruct tree_opt_pass pass_see =
3767169689Skan{
3768169689Skan  "see",				/* name */
3769169689Skan  gate_handle_see,			/* gate */
3770169689Skan  rest_of_handle_see,			/* execute */
3771169689Skan  NULL,					/* sub */
3772169689Skan  NULL,					/* next */
3773169689Skan  0,					/* static_pass_number */
3774169689Skan  TV_SEE,				/* tv_id */
3775169689Skan  0,					/* properties_required */
3776169689Skan  0,					/* properties_provided */
3777169689Skan  0,					/* properties_destroyed */
3778169689Skan  0,					/* todo_flags_start */
3779169689Skan  TODO_dump_func,			/* todo_flags_finish */
3780169689Skan  'u'					/* letter */
3781169689Skan};
3782169689Skan
3783