contrib/gcc/see.c

1 /* Sign extension elimination optimization for GNU compiler.
25 extension instructions are generated to ensure the correctness of
28 extension right after each 32bit computation.
30 sign extension instructions may be redundant.
31 There are two cases in which the extension may be redundant:
62 First, try to merge the sign extension with the instruction that
63 defines the source of the extension and (separately) with the
152        Remove the sign extension instruction, modify def1 and
158 	   Def2 is not changed but a sign extension instruction is
167 (The extension instruction is the original one).
169 *use1: Merge succeeded.  Remove the sign extension instruction.
175 use4: The extension is locally redundant, therefore it is eliminated
261    A simple explicit extension is a single set instruction that
264    A complex explicit extension is an explicit extension instruction
266    A def extension is a simple explicit extension that is
267      also a candidate for the optimization.  This extension is part
270    A use extension is a simple explicit extension that is generated
277      - It is followed by a def extension.
288      - If the instruction is a simple explicit extension instruction,
289        mark it as {ZERO, SIGN}_EXTENDED_DEF according to the extension
292      - Otherwise, If the instruction has an implicit extension,
293        which means that its high part is an extension of its low part,
294        or if it is a complicated explicit extension, mark it as
327        - Try to merge any def extension with one or two uses
330        an extension.
338     c. The first extension of this register before the first
340     c. The first extension of this register after the last
347     a. A use extension was merged with the reference:
348        Delete the extension instruction and save the merged reference
350     b. A use extension failed to be merged with the reference:
351        If there is already such an extension in the same basic block
352        and it is not dead at this point, delete the unmerged extension
356     c. A def extension was merged with the reference:
357        Mark this extension as a merged_def extension and properly
360     d. A def extension failed to be merged with the reference:
378      - Go over all its use extensions.  For each such extension -
380 	   the antloc bit of the current extension in the current
383 	   comp bit of the current extension in the current basic
386        it.  For each such extension -
388   	   comp bit of the current extension in the current basic
392        with it.  For each such extension -
394 	 extension in the current basic block bits.
461 	   extension.  It holds a copy of the extension and a linked list of all
558   /* The luid of the reference that has the first extension of this register
561   /* The luid of the reference that has the first extension of this register
578 /* There is one such structure for every relevant extension expression.
579    It holds a copy of this extension instruction as well as a linked lists of
583   /* A copy of the extension instruction.  */
672 see_get_extension_reg (rtx extension, bool return_dest_reg)
678   /* Parallel pattern for extension not supported for the moment.  */
679   if (GET_CODE (PATTERN (extension)) == PARALLEL)
682   set = single_set (extension);
717     the rtx code of the extension.  */
720 see_get_extension_data (rtx extension, enum machine_mode *source_mode)
724   if (!extension || !INSN_P (extension))
727   /* Parallel pattern for extension not supported for the moment.  */
728   if (GET_CODE (PATTERN (extension)) == PARALLEL)
731   set = single_set (extension);
771   rtx extension = NULL;
780     extension = gen_rtx_SIGN_EXTEND (GET_MODE (reg), subreg);
782     extension = gen_rtx_ZERO_EXTEND (GET_MODE (reg), subreg);
785   emit_insn (gen_rtx_SET (VOIDmode, reg, extension));
835   const struct see_pre_extension_expr *extension = p;
836   rtx set = single_set (extension->se_insn);
853   struct see_pre_extension_expr *extension = p;
854   struct see_occr *curr_occr = extension->antic_occr;
866   curr_occr = extension->avail_occr;
875   free (extension);
918 /* Helper functions for an extension hash.
1004 /* Search the extension hash for a suitable entry for EXTENSION.
1008    extension hash.
1014 see_seek_pre_extension_expr (rtx extension, enum extension_type type)
1017   rtx dest_extension_reg = see_get_extension_reg (extension, 1);
1023       extension_code = see_get_extension_data (extension,
1026       extension =
1030   temp_pre_exp.se_insn = extension;
1035     /* This is the first time this extension instruction is encountered.  Store
1039       (*slot_pre_exp)->se_insn = extension;
1304   /*  Free the extension hash.  */
1362   /*  Allocate the extension hash.  It will hold the extensions that we want
1389 /* We don't want to merge a use extension with a reference if the extended
1391    merge a def extension with a reference if the source register of the
1392    extension is defined only in a simple move in the reference.
1395    EXTENSION is the use extension or def extension instruction.
1396    TYPE is the type of the extension (use or def).
1399    it with the extension.  Otherwise, return false.  */
1402 see_want_to_be_merged_with_extension (rtx ref, rtx extension,
1406   rtx dest_extension_reg = see_get_extension_reg (extension, 1);
1407   rtx source_extension_reg = see_get_extension_reg (extension, 0);
1437 		 Check if it uses the source of the extension.  */
1485 /* Print the extension instruction of the current see_register_properties
1509 /* Delete the merged def extension.
1513    SLOT contains the current def extension instruction.
1523       fprintf (dump_file, "Deleting merged def extension:\n");
1528     /* This def extension is an implicit one.  No need to delete it since
1537 /* Delete the unmerged def extension.
1541    SLOT contains the current def extension instruction.
1551       fprintf (dump_file, "Deleting unmerged def extension:\n");
1560 /* Emit the non-redundant use extension to the instruction stream.
1564    SLOT contains the current use extension instruction.
1574     /* This use extension was previously removed according to the lcm
1580       fprintf (dump_file, "Inserting use extension:\n");
1748 	      fprintf (dump_file,"Redundant extension deleted:\n");
1801   /* Delete redundant extension.  This will prevent them from been emitted in
1834 /* Analyze the properties of a merged def extension for the LCM and record avail
1840    SLOT contains the current def extension instruction.
1903 /* Analyze the properties of a unmerged def extension for the LCM.
1908    SLOT contains the current def extension instruction.
1949 /* Analyze the properties of a use extension for the LCM and record anic and
1955    SLOT contains the current use extension instruction.
2147    Later the extension is inserted into the see_pre_extension_hash for the next
2153    SLOT contains the current def extension instruction.
2218    Later the extension is inserted into the see_pre_extension_hash for the next
2224    SLOT contains the current def extension instruction.
2289    When a redundant use extension is found it is removed from the hash of the
2291    If the extension is non redundant it is inserted into the
2297    SLOT contains the current use extension instruction.
2343 	  /* In this case the extension is locally redundant.  */
2353 	  /* In this case the extension is locally redundant.  */
2377       fprintf (dump_file, "Locally redundant extension:\n");
2384 /* Print an extension instruction.
2388    SLOT contains the extension instruction.  */
2439    DEF_SE is the extension that couldn't be merged.  */
2445   /* If the original insn was already merged with an extension before,
2559 /* Merge the reference instruction (ref) with the current use extension.
2578    SLOT contains the current use extension instruction.
2602      replace the uses of the dest_extension_reg with the rhs of the extension
2603      instruction.  This is necessary since there might not be an extension in
2630 	 the next extension.  */
2638        list).  Remove the use extension from the hash.  This will prevent it
2643 	  fprintf (dump_file, "Use extension not necessary before:\n");
2666 	 the next extension.  */
2698 /* Merge the reference instruction (ref) with the extension that follows it
2719    SLOT contains the current def extension instruction.
2727   /* If the original insn was already merged with an extension before,
2767       /* Continue to the next extension.  */
2773   /* Try to merge and simplify the extension.  */
2855       /* Continue to the next extension.  */
2913    Try to merge any def extension with one or two uses extensions
3027    SE_INSN is the extension to store in the proper hash according to TYPE.
3149   /* Insert the new extension instruction into the correct se_hash of the
3217 	 This means that we need to generate the implicit extension explicitly
3234 	  /* This is a dummy extension, mark it as deleted.  */
3259    a reference and generate an extension before it.
3300       /* Generate the use extension.  */
3386 -  If this is the pattern of a common sign extension after definition:
3392 -  If this is the pattern of a common zero extension after definition:
3451 	 as the extension.  */
3470       /* Now, check if this extension is a reference itself.  If so, it is not
3471 	 relevant.  Handling this extension as relevant would make things much
3689 /* Main entry point for the sign extension elimination optimization.  */