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