11590Srgrimes/* Shared code for before and after reload gcse implementations. 21590Srgrimes Copyright (C) 1997-2015 Free Software Foundation, Inc. 31590Srgrimes 41590Srgrimes This file is part of GCC. 51590Srgrimes 61590Srgrimes GCC is free software; you can redistribute it and/or modify it under 71590Srgrimes the terms of the GNU General Public License as published by the Free 81590Srgrimes Software Foundation; either version 3, or (at your option) any later 91590Srgrimes version. 101590Srgrimes 111590Srgrimes GCC is distributed in the hope that it will be useful, but WITHOUT ANY 121590Srgrimes WARRANTY; without even the implied warranty of MERCHANTABILITY or 131590Srgrimes FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 141590Srgrimes for more details. 151590Srgrimes 161590Srgrimes You should have received a copy of the GNU General Public License 171590Srgrimes along with GCC; see the file COPYING3. If not see 181590Srgrimes <http://www.gnu.org/licenses/>. 191590Srgrimes 201590Srgrimes It is expected that more hunks of gcse.c and postreload-gcse.c should 211590Srgrimes migrate into this file. */ 221590Srgrimes 231590Srgrimes#include "config.h" 241590Srgrimes#include "system.h" 251590Srgrimes#include "coretypes.h" 261590Srgrimes#include "tm.h" 271590Srgrimes#include "rtl.h" 281590Srgrimes#include "vec.h" 291590Srgrimes#include "predict.h" 301590Srgrimes#include "bitmap.h" 311590Srgrimes#include "basic-block.h" 321590Srgrimes#include "df.h" 331590Srgrimes#include "gcse-common.h" 341590Srgrimes 3527423Scharnier 361590Srgrimes/* Record all of the canonicalized MEMs of record_last_mem_set_info's insn. 371590Srgrimes Note we store a pair of elements in the list, so they have to be 381590Srgrimes taken off pairwise. */ 391590Srgrimes 401590Srgrimesvoid 4127423Scharniercanon_list_insert (rtx dest, const_rtx x ATTRIBUTE_UNUSED, void *data) 421590Srgrimes{ 4327423Scharnier rtx dest_addr, insn; 4427423Scharnier int bb; 4548995Ssheldonh modify_pair pair; 461590Srgrimes 471590Srgrimes while (GET_CODE (dest) == SUBREG 481590Srgrimes || GET_CODE (dest) == ZERO_EXTRACT 491590Srgrimes || GET_CODE (dest) == STRICT_LOW_PART) 501590Srgrimes dest = XEXP (dest, 0); 511590Srgrimes 521590Srgrimes /* If DEST is not a MEM, then it will not conflict with a load. Note 531590Srgrimes that function calls are assumed to clobber memory, but are handled 541590Srgrimes elsewhere. */ 5527423Scharnier 561590Srgrimes if (! MEM_P (dest)) 571590Srgrimes return; 581590Srgrimes 591590Srgrimes dest_addr = get_addr (XEXP (dest, 0)); 601590Srgrimes dest_addr = canon_rtx (dest_addr); 6123511Sache insn = ((struct gcse_note_stores_info *)data)->insn; 621590Srgrimes bb = BLOCK_FOR_INSN (insn)->index; 631590Srgrimes 641590Srgrimes pair.dest = dest; 651590Srgrimes pair.dest_addr = dest_addr; 661590Srgrimes vec<modify_pair> *canon_mem_list 671590Srgrimes = ((struct gcse_note_stores_info *)data)->canon_mem_list; 681590Srgrimes canon_mem_list[bb].safe_push (pair); 691590Srgrimes} 701590Srgrimes 711590Srgrimes/* Record memory modification information for INSN. We do not actually care 721590Srgrimes about the memory location(s) that are set, or even how they are set (consider 731590Srgrimes a CALL_INSN). We merely need to record which insns modify memory. */ 741590Srgrimes 751590Srgrimesvoid 761590Srgrimesrecord_last_mem_set_info_common (rtx_insn *insn, 771590Srgrimes vec<rtx_insn *> *modify_mem_list, 7848995Ssheldonh vec<modify_pair> *canon_modify_mem_list, 791590Srgrimes bitmap modify_mem_list_set, 8048995Ssheldonh bitmap blocks_with_calls) 811590Srgrimes 821590Srgrimes{ 831590Srgrimes int bb; 841590Srgrimes 851590Srgrimes bb = BLOCK_FOR_INSN (insn)->index; 861590Srgrimes modify_mem_list[bb].safe_push (insn); 8727423Scharnier bitmap_set_bit (modify_mem_list_set, bb); 881590Srgrimes 8927423Scharnier if (CALL_P (insn)) 901590Srgrimes bitmap_set_bit (blocks_with_calls, bb); 911590Srgrimes else 921590Srgrimes { 931590Srgrimes struct gcse_note_stores_info data; 941590Srgrimes data.insn = insn; 951590Srgrimes data.canon_mem_list = canon_modify_mem_list; 961590Srgrimes note_stores (PATTERN (insn), canon_list_insert, (void*) &data); 971590Srgrimes } 981590Srgrimes} 991590Srgrimes 1001590Srgrimes 1011590Srgrimes/* For each block, compute whether X is transparent. X is either an 1021590Srgrimes expression or an assignment [though we don't care which, for this context 1031590Srgrimes an assignment is treated as an expression]. For each block where an 1041590Srgrimes element of X is modified, reset the INDX bit in BMAP. 1051590Srgrimes 10647107Skris BLOCKS_WITH_CALLS indicates which blocks contain CALL_INSNs which kill 1071590Srgrimes memory. 1081590Srgrimes 10948995Ssheldonh MODIFY_MEM_LIST_SET indicates which blocks have memory stores which might 1101590Srgrimes kill a particular memory location. 1111590Srgrimes 1121590Srgrimes CANON_MODIFY_MEM_LIST is the canonicalized list of memory locations modified 1131590Srgrimes for each block. */ 1141590Srgrimes 1151590Srgrimesvoid 1161590Srgrimescompute_transp (const_rtx x, int indx, sbitmap *bmap, 1171590Srgrimes bitmap blocks_with_calls, 1181590Srgrimes bitmap modify_mem_list_set, 1191590Srgrimes vec<modify_pair> *canon_modify_mem_list) 1201590Srgrimes{ 1211590Srgrimes int i, j; 1221590Srgrimes enum rtx_code code; 1231590Srgrimes const char *fmt; 1241590Srgrimes 1251590Srgrimes /* repeat is used to turn tail-recursion into iteration since GCC 1261590Srgrimes can't do it when there's no return value. */ 1271590Srgrimes repeat: 1281590Srgrimes 1291590Srgrimes if (x == 0) 1301590Srgrimes return; 1311590Srgrimes 1321590Srgrimes code = GET_CODE (x); 1331590Srgrimes switch (code) 1341590Srgrimes { 1351590Srgrimes case REG: 1361590Srgrimes { 1371590Srgrimes df_ref def; 1381590Srgrimes for (def = DF_REG_DEF_CHAIN (REGNO (x)); 1391590Srgrimes def; 1401590Srgrimes def = DF_REF_NEXT_REG (def)) 1411590Srgrimes bitmap_clear_bit (bmap[DF_REF_BB (def)->index], indx); 14227423Scharnier } 1431590Srgrimes 1441590Srgrimes return; 1451590Srgrimes 1461590Srgrimes case MEM: 1471590Srgrimes if (! MEM_READONLY_P (x)) 14813101Sjoerg { 1491590Srgrimes bitmap_iterator bi; 15027423Scharnier unsigned bb_index; 1511590Srgrimes rtx x_addr; 15213101Sjoerg 1531590Srgrimes x_addr = get_addr (XEXP (x, 0)); 1541590Srgrimes x_addr = canon_rtx (x_addr); 1551590Srgrimes 1561590Srgrimes /* First handle all the blocks with calls. We don't need to 1571590Srgrimes do any list walking for them. */ 15827423Scharnier EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls, 0, bb_index, bi) 1591590Srgrimes { 1601590Srgrimes bitmap_clear_bit (bmap[bb_index], indx); 1611590Srgrimes } 16227423Scharnier 1631590Srgrimes /* Now iterate over the blocks which have memory modifications 1641590Srgrimes but which do not have any calls. */ 16527423Scharnier EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set, 1661590Srgrimes blocks_with_calls, 1671590Srgrimes 0, bb_index, bi) 1681590Srgrimes { 1691590Srgrimes vec<modify_pair> list 1701590Srgrimes = canon_modify_mem_list[bb_index]; 1711590Srgrimes modify_pair *pair; 17227423Scharnier unsigned ix; 1731590Srgrimes 1741590Srgrimes FOR_EACH_VEC_ELT_REVERSE (list, ix, pair) 1751590Srgrimes { 1761590Srgrimes rtx dest = pair->dest; 1771590Srgrimes rtx dest_addr = pair->dest_addr; 1781590Srgrimes 1791590Srgrimes if (canon_true_dependence (dest, GET_MODE (dest), 1801590Srgrimes dest_addr, x, x_addr)) 1811590Srgrimes { 1821590Srgrimes bitmap_clear_bit (bmap[bb_index], indx); 1831590Srgrimes break; 1841590Srgrimes } 1851590Srgrimes } 1861590Srgrimes } 1871590Srgrimes } 1881590Srgrimes 1891590Srgrimes x = XEXP (x, 0); 1901590Srgrimes goto repeat; 1911590Srgrimes 1921590Srgrimes case PC: 1931590Srgrimes case CC0: /*FIXME*/ 1941590Srgrimes case CONST: 1951590Srgrimes CASE_CONST_ANY: 19627423Scharnier case SYMBOL_REF: 1971590Srgrimes case LABEL_REF: 1981590Srgrimes case ADDR_VEC: 1991590Srgrimes case ADDR_DIFF_VEC: 2001590Srgrimes return; 20127423Scharnier 2021590Srgrimes default: 20327423Scharnier break; 2041590Srgrimes } 2051590Srgrimes 2061590Srgrimes for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 2071590Srgrimes { 2081590Srgrimes if (fmt[i] == 'e') 2091590Srgrimes { 2101590Srgrimes /* If we are about to do the last recursive call 2111590Srgrimes needed at this level, change it into iteration. 2121590Srgrimes This function is called enough to be worth it. */ 2131590Srgrimes if (i == 0) 2141590Srgrimes { 2151590Srgrimes x = XEXP (x, i); 2161590Srgrimes goto repeat; 2171590Srgrimes } 2181590Srgrimes 2191590Srgrimes compute_transp (XEXP (x, i), indx, bmap, blocks_with_calls, 2201590Srgrimes modify_mem_list_set, canon_modify_mem_list); 2211590Srgrimes } 2221590Srgrimes else if (fmt[i] == 'E') 2231590Srgrimes for (j = 0; j < XVECLEN (x, i); j++) 2241590Srgrimes compute_transp (XVECEXP (x, i, j), indx, bmap, blocks_with_calls, 2251590Srgrimes modify_mem_list_set, canon_modify_mem_list); 2261590Srgrimes } 2271590Srgrimes} 2281590Srgrimes