sched-deps.c revision 117395
190075Sobrien/* Instruction scheduling pass. This file computes dependencies between 290075Sobrien instructions. 390075Sobrien Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 490075Sobrien 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 590075Sobrien Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by, 690075Sobrien and currently maintained by, Jim Wilson (wilson@cygnus.com) 790075Sobrien 890075SobrienThis file is part of GCC. 990075Sobrien 1090075SobrienGCC is free software; you can redistribute it and/or modify it under 1190075Sobrienthe terms of the GNU General Public License as published by the Free 1290075SobrienSoftware Foundation; either version 2, or (at your option) any later 1390075Sobrienversion. 1490075Sobrien 1590075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1690075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1790075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1890075Sobrienfor more details. 1990075Sobrien 2090075SobrienYou should have received a copy of the GNU General Public License 2190075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 2290075SobrienSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 2390075Sobrien02111-1307, USA. */ 2490075Sobrien 2590075Sobrien#include "config.h" 2690075Sobrien#include "system.h" 2790075Sobrien#include "toplev.h" 2890075Sobrien#include "rtl.h" 2990075Sobrien#include "tm_p.h" 3090075Sobrien#include "hard-reg-set.h" 3190075Sobrien#include "basic-block.h" 3290075Sobrien#include "regs.h" 3390075Sobrien#include "function.h" 3490075Sobrien#include "flags.h" 3590075Sobrien#include "insn-config.h" 3690075Sobrien#include "insn-attr.h" 3790075Sobrien#include "except.h" 3890075Sobrien#include "toplev.h" 3990075Sobrien#include "recog.h" 4090075Sobrien#include "sched-int.h" 4190075Sobrien#include "params.h" 4290075Sobrien#include "cselib.h" 4390075Sobrien 4490075Sobrienextern char *reg_known_equiv_p; 4590075Sobrienextern rtx *reg_known_value; 4690075Sobrien 4790075Sobrienstatic regset_head reg_pending_sets_head; 4890075Sobrienstatic regset_head reg_pending_clobbers_head; 4990075Sobrienstatic regset_head reg_pending_uses_head; 5090075Sobrien 5190075Sobrienstatic regset reg_pending_sets; 5290075Sobrienstatic regset reg_pending_clobbers; 5390075Sobrienstatic regset reg_pending_uses; 5490075Sobrienstatic bool reg_pending_barrier; 5590075Sobrien 5690075Sobrien/* To speed up the test for duplicate dependency links we keep a 5790075Sobrien record of dependencies created by add_dependence when the average 5890075Sobrien number of instructions in a basic block is very large. 5990075Sobrien 6090075Sobrien Studies have shown that there is typically around 5 instructions between 6190075Sobrien branches for typical C code. So we can make a guess that the average 6290075Sobrien basic block is approximately 5 instructions long; we will choose 100X 6390075Sobrien the average size as a very large basic block. 6490075Sobrien 6590075Sobrien Each insn has associated bitmaps for its dependencies. Each bitmap 6690075Sobrien has enough entries to represent a dependency on any other insn in 6790075Sobrien the insn chain. All bitmap for true dependencies cache is 6890075Sobrien allocated then the rest two ones are also allocated. */ 6990075Sobrienstatic sbitmap *true_dependency_cache; 7090075Sobrienstatic sbitmap *anti_dependency_cache; 7190075Sobrienstatic sbitmap *output_dependency_cache; 7290075Sobrien 7390075Sobrien/* To speed up checking consistency of formed forward insn 7490075Sobrien dependencies we use the following cache. Another possible solution 7590075Sobrien could be switching off checking duplication of insns in forward 7690075Sobrien dependencies. */ 7790075Sobrien#ifdef ENABLE_CHECKING 7890075Sobrienstatic sbitmap *forward_dependency_cache; 7990075Sobrien#endif 8090075Sobrien 8190075Sobrienstatic int deps_may_trap_p PARAMS ((rtx)); 8290075Sobrienstatic void add_dependence_list PARAMS ((rtx, rtx, enum reg_note)); 8390075Sobrienstatic void add_dependence_list_and_free PARAMS ((rtx, rtx *, enum reg_note)); 8490075Sobrienstatic void remove_dependence PARAMS ((rtx, rtx)); 8590075Sobrienstatic void set_sched_group_p PARAMS ((rtx)); 8690075Sobrien 8790075Sobrienstatic void flush_pending_lists PARAMS ((struct deps *, rtx, int, int)); 8890075Sobrienstatic void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx)); 8990075Sobrienstatic void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx)); 9090075Sobrienstatic void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx)); 9190075Sobrienstatic rtx group_leader PARAMS ((rtx)); 9290075Sobrien 9390075Sobrienstatic rtx get_condition PARAMS ((rtx)); 9490075Sobrienstatic int conditions_mutex_p PARAMS ((rtx, rtx)); 9590075Sobrien 9690075Sobrien/* Return nonzero if a load of the memory reference MEM can cause a trap. */ 9790075Sobrien 9890075Sobrienstatic int 9990075Sobriendeps_may_trap_p (mem) 10090075Sobrien rtx mem; 10190075Sobrien{ 10290075Sobrien rtx addr = XEXP (mem, 0); 10390075Sobrien 10490075Sobrien if (REG_P (addr) 10590075Sobrien && REGNO (addr) >= FIRST_PSEUDO_REGISTER 10690075Sobrien && reg_known_value[REGNO (addr)]) 10790075Sobrien addr = reg_known_value[REGNO (addr)]; 10890075Sobrien return rtx_addr_can_trap_p (addr); 10990075Sobrien} 11090075Sobrien 11190075Sobrien/* Return the INSN_LIST containing INSN in LIST, or NULL 11290075Sobrien if LIST does not contain INSN. */ 11390075Sobrien 11490075Sobrienrtx 11590075Sobrienfind_insn_list (insn, list) 11690075Sobrien rtx insn; 11790075Sobrien rtx list; 11890075Sobrien{ 11990075Sobrien while (list) 12090075Sobrien { 12190075Sobrien if (XEXP (list, 0) == insn) 12290075Sobrien return list; 12390075Sobrien list = XEXP (list, 1); 12490075Sobrien } 12590075Sobrien return 0; 12690075Sobrien} 12790075Sobrien 12890075Sobrien/* Find the condition under which INSN is executed. */ 12990075Sobrien 13090075Sobrienstatic rtx 13190075Sobrienget_condition (insn) 13290075Sobrien rtx insn; 13390075Sobrien{ 13490075Sobrien rtx pat = PATTERN (insn); 13590075Sobrien rtx cond; 13690075Sobrien 13790075Sobrien if (pat == 0) 13890075Sobrien return 0; 13990075Sobrien if (GET_CODE (pat) == COND_EXEC) 14090075Sobrien return COND_EXEC_TEST (pat); 14190075Sobrien if (GET_CODE (insn) != JUMP_INSN) 14290075Sobrien return 0; 14390075Sobrien if (GET_CODE (pat) != SET || SET_SRC (pat) != pc_rtx) 14490075Sobrien return 0; 14590075Sobrien if (GET_CODE (SET_DEST (pat)) != IF_THEN_ELSE) 14690075Sobrien return 0; 14790075Sobrien pat = SET_DEST (pat); 14890075Sobrien cond = XEXP (pat, 0); 14990075Sobrien if (GET_CODE (XEXP (cond, 1)) == LABEL_REF 15090075Sobrien && XEXP (cond, 2) == pc_rtx) 15190075Sobrien return cond; 15290075Sobrien else if (GET_CODE (XEXP (cond, 2)) == LABEL_REF 15390075Sobrien && XEXP (cond, 1) == pc_rtx) 15490075Sobrien return gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)), GET_MODE (cond), 15590075Sobrien XEXP (cond, 0), XEXP (cond, 1)); 15690075Sobrien else 15790075Sobrien return 0; 15890075Sobrien} 15990075Sobrien 16090075Sobrien/* Return nonzero if conditions COND1 and COND2 can never be both true. */ 16190075Sobrien 16290075Sobrienstatic int 16390075Sobrienconditions_mutex_p (cond1, cond2) 16490075Sobrien rtx cond1, cond2; 16590075Sobrien{ 16690075Sobrien if (GET_RTX_CLASS (GET_CODE (cond1)) == '<' 16790075Sobrien && GET_RTX_CLASS (GET_CODE (cond2)) == '<' 16890075Sobrien && GET_CODE (cond1) == reverse_condition (GET_CODE (cond2)) 16990075Sobrien && XEXP (cond1, 0) == XEXP (cond2, 0) 17090075Sobrien && XEXP (cond1, 1) == XEXP (cond2, 1)) 17190075Sobrien return 1; 17290075Sobrien return 0; 17390075Sobrien} 17490075Sobrien 17590075Sobrien/* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the 17690075Sobrien LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type 17790075Sobrien of dependence that this link represents. */ 17890075Sobrien 17990075Sobrienvoid 18090075Sobrienadd_dependence (insn, elem, dep_type) 18190075Sobrien rtx insn; 18290075Sobrien rtx elem; 18390075Sobrien enum reg_note dep_type; 18490075Sobrien{ 18590075Sobrien rtx link, next; 18690075Sobrien int present_p; 18790075Sobrien rtx cond1, cond2; 18890075Sobrien 18990075Sobrien /* Don't depend an insn on itself. */ 19090075Sobrien if (insn == elem) 19190075Sobrien return; 19290075Sobrien 19390075Sobrien /* We can get a dependency on deleted insns due to optimizations in 19490075Sobrien the register allocation and reloading or due to splitting. Any 19590075Sobrien such dependency is useless and can be ignored. */ 19690075Sobrien if (GET_CODE (elem) == NOTE) 19790075Sobrien return; 19890075Sobrien 19990075Sobrien /* flow.c doesn't handle conditional lifetimes entirely correctly; 20090075Sobrien calls mess up the conditional lifetimes. */ 20190075Sobrien /* ??? add_dependence is the wrong place to be eliding dependencies, 20290075Sobrien as that forgets that the condition expressions themselves may 20390075Sobrien be dependent. */ 20490075Sobrien if (GET_CODE (insn) != CALL_INSN && GET_CODE (elem) != CALL_INSN) 20590075Sobrien { 20690075Sobrien cond1 = get_condition (insn); 20790075Sobrien cond2 = get_condition (elem); 20890075Sobrien if (cond1 && cond2 20990075Sobrien && conditions_mutex_p (cond1, cond2) 21090075Sobrien /* Make sure first instruction doesn't affect condition of second 21190075Sobrien instruction if switched. */ 21290075Sobrien && !modified_in_p (cond1, elem) 21390075Sobrien /* Make sure second instruction doesn't affect condition of first 21490075Sobrien instruction if switched. */ 21590075Sobrien && !modified_in_p (cond2, insn)) 21690075Sobrien return; 21790075Sobrien } 21890075Sobrien 21990075Sobrien /* If elem is part of a sequence that must be scheduled together, then 22090075Sobrien make the dependence point to the last insn of the sequence. 22190075Sobrien When HAVE_cc0, it is possible for NOTEs to exist between users and 22290075Sobrien setters of the condition codes, so we must skip past notes here. 22390075Sobrien Otherwise, NOTEs are impossible here. */ 22490075Sobrien next = next_nonnote_insn (elem); 225117395Skan if (next && INSN_P (next) && SCHED_GROUP_P (next)) 22690075Sobrien { 22790075Sobrien /* Notes will never intervene here though, so don't bother checking 22890075Sobrien for them. */ 22990075Sobrien /* Hah! Wrong. */ 23090075Sobrien /* We must reject CODE_LABELs, so that we don't get confused by one 23190075Sobrien that has LABEL_PRESERVE_P set, which is represented by the same 23290075Sobrien bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be 23390075Sobrien SCHED_GROUP_P. */ 23490075Sobrien 23590075Sobrien rtx nnext; 23690075Sobrien while ((nnext = next_nonnote_insn (next)) != NULL 237117395Skan && INSN_P (nnext) 238117395Skan && SCHED_GROUP_P (nnext)) 23990075Sobrien next = nnext; 24090075Sobrien 24190075Sobrien /* Again, don't depend an insn on itself. */ 24290075Sobrien if (insn == next) 24390075Sobrien return; 24490075Sobrien 24590075Sobrien /* Make the dependence to NEXT, the last insn of the group, instead 24690075Sobrien of the original ELEM. */ 24790075Sobrien elem = next; 24890075Sobrien } 24990075Sobrien 25090075Sobrien present_p = 1; 25190075Sobrien#ifdef INSN_SCHEDULING 25290075Sobrien /* ??? No good way to tell from here whether we're doing interblock 25390075Sobrien scheduling. Possibly add another callback. */ 25490075Sobrien#if 0 25590075Sobrien /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.) 25690075Sobrien No need for interblock dependences with calls, since 25790075Sobrien calls are not moved between blocks. Note: the edge where 25890075Sobrien elem is a CALL is still required. */ 25990075Sobrien if (GET_CODE (insn) == CALL_INSN 26090075Sobrien && (INSN_BB (elem) != INSN_BB (insn))) 26190075Sobrien return; 26290075Sobrien#endif 26390075Sobrien 26490075Sobrien /* If we already have a dependency for ELEM, then we do not need to 26590075Sobrien do anything. Avoiding the list walk below can cut compile times 26690075Sobrien dramatically for some code. */ 26790075Sobrien if (true_dependency_cache != NULL) 26890075Sobrien { 26990075Sobrien enum reg_note present_dep_type = 0; 27090075Sobrien 27190075Sobrien if (anti_dependency_cache == NULL || output_dependency_cache == NULL) 27290075Sobrien abort (); 27390075Sobrien if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem))) 27490075Sobrien /* Do nothing (present_set_type is already 0). */ 27590075Sobrien ; 27690075Sobrien else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)], 27790075Sobrien INSN_LUID (elem))) 27890075Sobrien present_dep_type = REG_DEP_ANTI; 27990075Sobrien else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)], 28090075Sobrien INSN_LUID (elem))) 28190075Sobrien present_dep_type = REG_DEP_OUTPUT; 282117395Skan else 28390075Sobrien present_p = 0; 28490075Sobrien if (present_p && (int) dep_type >= (int) present_dep_type) 28590075Sobrien return; 28690075Sobrien } 28790075Sobrien#endif 28890075Sobrien 28990075Sobrien /* Check that we don't already have this dependence. */ 29090075Sobrien if (present_p) 29190075Sobrien for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) 29290075Sobrien if (XEXP (link, 0) == elem) 29390075Sobrien { 29490075Sobrien#ifdef INSN_SCHEDULING 29590075Sobrien /* Clear corresponding cache entry because type of the link 29690075Sobrien may be changed. */ 29790075Sobrien if (true_dependency_cache != NULL) 29890075Sobrien { 29990075Sobrien if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 30090075Sobrien RESET_BIT (anti_dependency_cache[INSN_LUID (insn)], 30190075Sobrien INSN_LUID (elem)); 30290075Sobrien else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT 30390075Sobrien && output_dependency_cache) 30490075Sobrien RESET_BIT (output_dependency_cache[INSN_LUID (insn)], 30590075Sobrien INSN_LUID (elem)); 30690075Sobrien else 30790075Sobrien abort (); 30890075Sobrien } 30990075Sobrien#endif 31090075Sobrien 31190075Sobrien /* If this is a more restrictive type of dependence than the existing 31290075Sobrien one, then change the existing dependence to this type. */ 31390075Sobrien if ((int) dep_type < (int) REG_NOTE_KIND (link)) 31490075Sobrien PUT_REG_NOTE_KIND (link, dep_type); 315117395Skan 31690075Sobrien#ifdef INSN_SCHEDULING 31790075Sobrien /* If we are adding a dependency to INSN's LOG_LINKs, then 31890075Sobrien note that in the bitmap caches of dependency information. */ 31990075Sobrien if (true_dependency_cache != NULL) 32090075Sobrien { 32190075Sobrien if ((int) REG_NOTE_KIND (link) == 0) 32290075Sobrien SET_BIT (true_dependency_cache[INSN_LUID (insn)], 32390075Sobrien INSN_LUID (elem)); 32490075Sobrien else if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 32590075Sobrien SET_BIT (anti_dependency_cache[INSN_LUID (insn)], 32690075Sobrien INSN_LUID (elem)); 32790075Sobrien else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) 32890075Sobrien SET_BIT (output_dependency_cache[INSN_LUID (insn)], 32990075Sobrien INSN_LUID (elem)); 33090075Sobrien } 33190075Sobrien#endif 33290075Sobrien return; 33390075Sobrien } 33490075Sobrien /* Might want to check one level of transitivity to save conses. */ 33590075Sobrien 33690075Sobrien link = alloc_INSN_LIST (elem, LOG_LINKS (insn)); 33790075Sobrien LOG_LINKS (insn) = link; 33890075Sobrien 33990075Sobrien /* Insn dependency, not data dependency. */ 34090075Sobrien PUT_REG_NOTE_KIND (link, dep_type); 34190075Sobrien 34290075Sobrien#ifdef INSN_SCHEDULING 34390075Sobrien /* If we are adding a dependency to INSN's LOG_LINKs, then note that 34490075Sobrien in the bitmap caches of dependency information. */ 34590075Sobrien if (true_dependency_cache != NULL) 34690075Sobrien { 34790075Sobrien if ((int) dep_type == 0) 34890075Sobrien SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); 34990075Sobrien else if (dep_type == REG_DEP_ANTI) 35090075Sobrien SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); 35190075Sobrien else if (dep_type == REG_DEP_OUTPUT) 35290075Sobrien SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); 35390075Sobrien } 35490075Sobrien#endif 35590075Sobrien} 35690075Sobrien 35790075Sobrien/* A convenience wrapper to operate on an entire list. */ 35890075Sobrien 35990075Sobrienstatic void 36090075Sobrienadd_dependence_list (insn, list, dep_type) 36190075Sobrien rtx insn, list; 36290075Sobrien enum reg_note dep_type; 36390075Sobrien{ 36490075Sobrien for (; list; list = XEXP (list, 1)) 36590075Sobrien add_dependence (insn, XEXP (list, 0), dep_type); 36690075Sobrien} 36790075Sobrien 36890075Sobrien/* Similar, but free *LISTP at the same time. */ 36990075Sobrien 37090075Sobrienstatic void 37190075Sobrienadd_dependence_list_and_free (insn, listp, dep_type) 37290075Sobrien rtx insn; 37390075Sobrien rtx *listp; 37490075Sobrien enum reg_note dep_type; 37590075Sobrien{ 37690075Sobrien rtx list, next; 37790075Sobrien for (list = *listp, *listp = NULL; list ; list = next) 37890075Sobrien { 37990075Sobrien next = XEXP (list, 1); 38090075Sobrien add_dependence (insn, XEXP (list, 0), dep_type); 38190075Sobrien free_INSN_LIST_node (list); 38290075Sobrien } 38390075Sobrien} 38490075Sobrien 38590075Sobrien/* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS 38690075Sobrien of INSN. Abort if not found. */ 38790075Sobrien 38890075Sobrienstatic void 38990075Sobrienremove_dependence (insn, elem) 39090075Sobrien rtx insn; 39190075Sobrien rtx elem; 39290075Sobrien{ 39390075Sobrien rtx prev, link, next; 39490075Sobrien int found = 0; 39590075Sobrien 39690075Sobrien for (prev = 0, link = LOG_LINKS (insn); link; link = next) 39790075Sobrien { 39890075Sobrien next = XEXP (link, 1); 39990075Sobrien if (XEXP (link, 0) == elem) 40090075Sobrien { 40190075Sobrien if (prev) 40290075Sobrien XEXP (prev, 1) = next; 40390075Sobrien else 40490075Sobrien LOG_LINKS (insn) = next; 40590075Sobrien 40690075Sobrien#ifdef INSN_SCHEDULING 40790075Sobrien /* If we are removing a dependency from the LOG_LINKS list, 40890075Sobrien make sure to remove it from the cache too. */ 40990075Sobrien if (true_dependency_cache != NULL) 41090075Sobrien { 41190075Sobrien if (REG_NOTE_KIND (link) == 0) 41290075Sobrien RESET_BIT (true_dependency_cache[INSN_LUID (insn)], 41390075Sobrien INSN_LUID (elem)); 41490075Sobrien else if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 41590075Sobrien RESET_BIT (anti_dependency_cache[INSN_LUID (insn)], 41690075Sobrien INSN_LUID (elem)); 41790075Sobrien else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) 41890075Sobrien RESET_BIT (output_dependency_cache[INSN_LUID (insn)], 41990075Sobrien INSN_LUID (elem)); 42090075Sobrien } 42190075Sobrien#endif 42290075Sobrien 42390075Sobrien free_INSN_LIST_node (link); 42490075Sobrien 42590075Sobrien found = 1; 42690075Sobrien } 42790075Sobrien else 42890075Sobrien prev = link; 42990075Sobrien } 43090075Sobrien 43190075Sobrien if (!found) 43290075Sobrien abort (); 43390075Sobrien return; 43490075Sobrien} 43590075Sobrien 43690075Sobrien/* Return an insn which represents a SCHED_GROUP, which is 43790075Sobrien the last insn in the group. */ 43890075Sobrien 43990075Sobrienstatic rtx 44090075Sobriengroup_leader (insn) 44190075Sobrien rtx insn; 44290075Sobrien{ 44390075Sobrien rtx prev; 44490075Sobrien 44590075Sobrien do 44690075Sobrien { 44790075Sobrien prev = insn; 44890075Sobrien insn = next_nonnote_insn (insn); 44990075Sobrien } 450117395Skan while (insn && INSN_P (insn) && SCHED_GROUP_P (insn)); 45190075Sobrien 45290075Sobrien return prev; 45390075Sobrien} 45490075Sobrien 45590075Sobrien/* Set SCHED_GROUP_P and care for the rest of the bookkeeping that 45690075Sobrien goes along with that. */ 45790075Sobrien 45890075Sobrienstatic void 45990075Sobrienset_sched_group_p (insn) 46090075Sobrien rtx insn; 46190075Sobrien{ 46290075Sobrien rtx link, prev; 46390075Sobrien 46490075Sobrien SCHED_GROUP_P (insn) = 1; 46590075Sobrien 46690075Sobrien /* There may be a note before this insn now, but all notes will 46790075Sobrien be removed before we actually try to schedule the insns, so 46890075Sobrien it won't cause a problem later. We must avoid it here though. */ 46990075Sobrien prev = prev_nonnote_insn (insn); 47090075Sobrien 47190075Sobrien /* Make a copy of all dependencies on the immediately previous insn, 47290075Sobrien and add to this insn. This is so that all the dependencies will 47390075Sobrien apply to the group. Remove an explicit dependence on this insn 47490075Sobrien as SCHED_GROUP_P now represents it. */ 47590075Sobrien 47690075Sobrien if (find_insn_list (prev, LOG_LINKS (insn))) 47790075Sobrien remove_dependence (insn, prev); 47890075Sobrien 47990075Sobrien for (link = LOG_LINKS (prev); link; link = XEXP (link, 1)) 48090075Sobrien add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link)); 48190075Sobrien} 48290075Sobrien 48390075Sobrien/* Process an insn's memory dependencies. There are four kinds of 48490075Sobrien dependencies: 48590075Sobrien 48690075Sobrien (0) read dependence: read follows read 48790075Sobrien (1) true dependence: read follows write 48890075Sobrien (2) anti dependence: write follows read 48990075Sobrien (3) output dependence: write follows write 49090075Sobrien 49190075Sobrien We are careful to build only dependencies which actually exist, and 49290075Sobrien use transitivity to avoid building too many links. */ 49390075Sobrien 49490075Sobrien/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST. 49590075Sobrien The MEM is a memory reference contained within INSN, which we are saving 49690075Sobrien so that we can do memory aliasing on it. */ 49790075Sobrien 49890075Sobrienvoid 49990075Sobrienadd_insn_mem_dependence (deps, insn_list, mem_list, insn, mem) 50090075Sobrien struct deps *deps; 50190075Sobrien rtx *insn_list, *mem_list, insn, mem; 50290075Sobrien{ 50390075Sobrien rtx link; 50490075Sobrien 50590075Sobrien link = alloc_INSN_LIST (insn, *insn_list); 50690075Sobrien *insn_list = link; 50790075Sobrien 50890075Sobrien if (current_sched_info->use_cselib) 50990075Sobrien { 51090075Sobrien mem = shallow_copy_rtx (mem); 51190075Sobrien XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0)); 51290075Sobrien } 51390075Sobrien link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list); 51490075Sobrien *mem_list = link; 51590075Sobrien 51690075Sobrien deps->pending_lists_length++; 51790075Sobrien} 51890075Sobrien 51990075Sobrien/* Make a dependency between every memory reference on the pending lists 52090075Sobrien and INSN, thus flushing the pending lists. FOR_READ is true if emitting 52190075Sobrien dependencies for a read operation, similarly with FOR_WRITE. */ 52290075Sobrien 52390075Sobrienstatic void 52490075Sobrienflush_pending_lists (deps, insn, for_read, for_write) 52590075Sobrien struct deps *deps; 52690075Sobrien rtx insn; 52790075Sobrien int for_read, for_write; 52890075Sobrien{ 52990075Sobrien if (for_write) 53090075Sobrien { 53190075Sobrien add_dependence_list_and_free (insn, &deps->pending_read_insns, 53290075Sobrien REG_DEP_ANTI); 53390075Sobrien free_EXPR_LIST_list (&deps->pending_read_mems); 53490075Sobrien } 53590075Sobrien 53690075Sobrien add_dependence_list_and_free (insn, &deps->pending_write_insns, 53790075Sobrien for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT); 53890075Sobrien free_EXPR_LIST_list (&deps->pending_write_mems); 53990075Sobrien deps->pending_lists_length = 0; 54090075Sobrien 54190075Sobrien add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 54290075Sobrien for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT); 54390075Sobrien deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX); 54490075Sobrien deps->pending_flush_length = 1; 54590075Sobrien} 54690075Sobrien 54790075Sobrien/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC 54890075Sobrien rtx, X, creating all dependencies generated by the write to the 54990075Sobrien destination of X, and reads of everything mentioned. */ 55090075Sobrien 55190075Sobrienstatic void 55290075Sobriensched_analyze_1 (deps, x, insn) 55390075Sobrien struct deps *deps; 55490075Sobrien rtx x; 55590075Sobrien rtx insn; 55690075Sobrien{ 55790075Sobrien int regno; 55890075Sobrien rtx dest = XEXP (x, 0); 55990075Sobrien enum rtx_code code = GET_CODE (x); 56090075Sobrien 56190075Sobrien if (dest == 0) 56290075Sobrien return; 56390075Sobrien 56490075Sobrien if (GET_CODE (dest) == PARALLEL) 56590075Sobrien { 56690075Sobrien int i; 56790075Sobrien 56890075Sobrien for (i = XVECLEN (dest, 0) - 1; i >= 0; i--) 56990075Sobrien if (XEXP (XVECEXP (dest, 0, i), 0) != 0) 57090075Sobrien sched_analyze_1 (deps, 57190075Sobrien gen_rtx_CLOBBER (VOIDmode, 57290075Sobrien XEXP (XVECEXP (dest, 0, i), 0)), 57390075Sobrien insn); 57490075Sobrien 57590075Sobrien if (GET_CODE (x) == SET) 57690075Sobrien sched_analyze_2 (deps, SET_SRC (x), insn); 57790075Sobrien return; 57890075Sobrien } 57990075Sobrien 58090075Sobrien while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG 58190075Sobrien || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) 58290075Sobrien { 58390075Sobrien if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) 58490075Sobrien { 58590075Sobrien /* The second and third arguments are values read by this insn. */ 58690075Sobrien sched_analyze_2 (deps, XEXP (dest, 1), insn); 58790075Sobrien sched_analyze_2 (deps, XEXP (dest, 2), insn); 58890075Sobrien } 58990075Sobrien dest = XEXP (dest, 0); 59090075Sobrien } 59190075Sobrien 59290075Sobrien if (GET_CODE (dest) == REG) 59390075Sobrien { 59490075Sobrien regno = REGNO (dest); 59590075Sobrien 59690075Sobrien /* A hard reg in a wide mode may really be multiple registers. 59790075Sobrien If so, mark all of them just like the first. */ 59890075Sobrien if (regno < FIRST_PSEUDO_REGISTER) 59990075Sobrien { 60090075Sobrien int i = HARD_REGNO_NREGS (regno, GET_MODE (dest)); 60190075Sobrien if (code == SET) 60290075Sobrien { 60390075Sobrien while (--i >= 0) 60490075Sobrien SET_REGNO_REG_SET (reg_pending_sets, regno + i); 60590075Sobrien } 60690075Sobrien else 60790075Sobrien { 60890075Sobrien while (--i >= 0) 60990075Sobrien SET_REGNO_REG_SET (reg_pending_clobbers, regno + i); 61090075Sobrien } 61190075Sobrien } 61290075Sobrien /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that 61390075Sobrien it does not reload. Ignore these as they have served their 61490075Sobrien purpose already. */ 61590075Sobrien else if (regno >= deps->max_reg) 61690075Sobrien { 61790075Sobrien if (GET_CODE (PATTERN (insn)) != USE 61890075Sobrien && GET_CODE (PATTERN (insn)) != CLOBBER) 61990075Sobrien abort (); 62090075Sobrien } 62190075Sobrien else 62290075Sobrien { 62390075Sobrien if (code == SET) 62490075Sobrien SET_REGNO_REG_SET (reg_pending_sets, regno); 62590075Sobrien else 62690075Sobrien SET_REGNO_REG_SET (reg_pending_clobbers, regno); 62790075Sobrien 62890075Sobrien /* Pseudos that are REG_EQUIV to something may be replaced 62990075Sobrien by that during reloading. We need only add dependencies for 63090075Sobrien the address in the REG_EQUIV note. */ 63190075Sobrien if (!reload_completed 63290075Sobrien && reg_known_equiv_p[regno] 63390075Sobrien && GET_CODE (reg_known_value[regno]) == MEM) 63490075Sobrien sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn); 63590075Sobrien 63690075Sobrien /* Don't let it cross a call after scheduling if it doesn't 63790075Sobrien already cross one. */ 63890075Sobrien if (REG_N_CALLS_CROSSED (regno) == 0) 63990075Sobrien add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI); 64090075Sobrien } 64190075Sobrien } 64290075Sobrien else if (GET_CODE (dest) == MEM) 64390075Sobrien { 64490075Sobrien /* Writing memory. */ 64590075Sobrien rtx t = dest; 64690075Sobrien 64790075Sobrien if (current_sched_info->use_cselib) 64890075Sobrien { 64990075Sobrien t = shallow_copy_rtx (dest); 65090075Sobrien cselib_lookup (XEXP (t, 0), Pmode, 1); 65190075Sobrien XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0)); 65290075Sobrien } 65390075Sobrien 65490075Sobrien if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH) 65590075Sobrien { 65690075Sobrien /* Flush all pending reads and writes to prevent the pending lists 65790075Sobrien from getting any larger. Insn scheduling runs too slowly when 65890075Sobrien these lists get long. When compiling GCC with itself, 65990075Sobrien this flush occurs 8 times for sparc, and 10 times for m88k using 66090075Sobrien the default value of 32. */ 66190075Sobrien flush_pending_lists (deps, insn, false, true); 66290075Sobrien } 66390075Sobrien else 66490075Sobrien { 66590075Sobrien rtx pending, pending_mem; 66690075Sobrien 66790075Sobrien pending = deps->pending_read_insns; 66890075Sobrien pending_mem = deps->pending_read_mems; 66990075Sobrien while (pending) 67090075Sobrien { 67190075Sobrien if (anti_dependence (XEXP (pending_mem, 0), t)) 67290075Sobrien add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); 67390075Sobrien 67490075Sobrien pending = XEXP (pending, 1); 67590075Sobrien pending_mem = XEXP (pending_mem, 1); 67690075Sobrien } 67790075Sobrien 67890075Sobrien pending = deps->pending_write_insns; 67990075Sobrien pending_mem = deps->pending_write_mems; 68090075Sobrien while (pending) 68190075Sobrien { 68290075Sobrien if (output_dependence (XEXP (pending_mem, 0), t)) 68390075Sobrien add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 68490075Sobrien 68590075Sobrien pending = XEXP (pending, 1); 68690075Sobrien pending_mem = XEXP (pending_mem, 1); 68790075Sobrien } 68890075Sobrien 68990075Sobrien add_dependence_list (insn, deps->last_pending_memory_flush, 69090075Sobrien REG_DEP_ANTI); 69190075Sobrien 69290075Sobrien add_insn_mem_dependence (deps, &deps->pending_write_insns, 69390075Sobrien &deps->pending_write_mems, insn, dest); 69490075Sobrien } 69590075Sobrien sched_analyze_2 (deps, XEXP (dest, 0), insn); 69690075Sobrien } 69790075Sobrien 69890075Sobrien /* Analyze reads. */ 69990075Sobrien if (GET_CODE (x) == SET) 70090075Sobrien sched_analyze_2 (deps, SET_SRC (x), insn); 70190075Sobrien} 70290075Sobrien 70390075Sobrien/* Analyze the uses of memory and registers in rtx X in INSN. */ 70490075Sobrien 70590075Sobrienstatic void 70690075Sobriensched_analyze_2 (deps, x, insn) 70790075Sobrien struct deps *deps; 70890075Sobrien rtx x; 70990075Sobrien rtx insn; 71090075Sobrien{ 71190075Sobrien int i; 71290075Sobrien int j; 71390075Sobrien enum rtx_code code; 71490075Sobrien const char *fmt; 71590075Sobrien 71690075Sobrien if (x == 0) 71790075Sobrien return; 71890075Sobrien 71990075Sobrien code = GET_CODE (x); 72090075Sobrien 72190075Sobrien switch (code) 72290075Sobrien { 72390075Sobrien case CONST_INT: 72490075Sobrien case CONST_DOUBLE: 72596263Sobrien case CONST_VECTOR: 72690075Sobrien case SYMBOL_REF: 72790075Sobrien case CONST: 72890075Sobrien case LABEL_REF: 72990075Sobrien /* Ignore constants. Note that we must handle CONST_DOUBLE here 73090075Sobrien because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but 73190075Sobrien this does not mean that this insn is using cc0. */ 73290075Sobrien return; 73390075Sobrien 73490075Sobrien#ifdef HAVE_cc0 73590075Sobrien case CC0: 73690075Sobrien /* User of CC0 depends on immediately preceding insn. */ 73790075Sobrien set_sched_group_p (insn); 73890075Sobrien return; 73990075Sobrien#endif 74090075Sobrien 74190075Sobrien case REG: 74290075Sobrien { 74390075Sobrien int regno = REGNO (x); 74490075Sobrien if (regno < FIRST_PSEUDO_REGISTER) 74590075Sobrien { 74690075Sobrien int i = HARD_REGNO_NREGS (regno, GET_MODE (x)); 74790075Sobrien while (--i >= 0) 74890075Sobrien SET_REGNO_REG_SET (reg_pending_uses, regno + i); 74990075Sobrien } 75090075Sobrien /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that 75190075Sobrien it does not reload. Ignore these as they have served their 75290075Sobrien purpose already. */ 75390075Sobrien else if (regno >= deps->max_reg) 75490075Sobrien { 75590075Sobrien if (GET_CODE (PATTERN (insn)) != USE 75690075Sobrien && GET_CODE (PATTERN (insn)) != CLOBBER) 75790075Sobrien abort (); 75890075Sobrien } 75990075Sobrien else 76090075Sobrien { 76190075Sobrien SET_REGNO_REG_SET (reg_pending_uses, regno); 76290075Sobrien 76390075Sobrien /* Pseudos that are REG_EQUIV to something may be replaced 76490075Sobrien by that during reloading. We need only add dependencies for 76590075Sobrien the address in the REG_EQUIV note. */ 76690075Sobrien if (!reload_completed 76790075Sobrien && reg_known_equiv_p[regno] 76890075Sobrien && GET_CODE (reg_known_value[regno]) == MEM) 76990075Sobrien sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn); 77090075Sobrien 77190075Sobrien /* If the register does not already cross any calls, then add this 77290075Sobrien insn to the sched_before_next_call list so that it will still 77390075Sobrien not cross calls after scheduling. */ 77490075Sobrien if (REG_N_CALLS_CROSSED (regno) == 0) 77590075Sobrien deps->sched_before_next_call 77690075Sobrien = alloc_INSN_LIST (insn, deps->sched_before_next_call); 77790075Sobrien } 77890075Sobrien return; 77990075Sobrien } 78090075Sobrien 78190075Sobrien case MEM: 78290075Sobrien { 78390075Sobrien /* Reading memory. */ 78490075Sobrien rtx u; 78590075Sobrien rtx pending, pending_mem; 78690075Sobrien rtx t = x; 78790075Sobrien 78890075Sobrien if (current_sched_info->use_cselib) 78990075Sobrien { 79090075Sobrien t = shallow_copy_rtx (t); 79190075Sobrien cselib_lookup (XEXP (t, 0), Pmode, 1); 79290075Sobrien XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0)); 79390075Sobrien } 79490075Sobrien pending = deps->pending_read_insns; 79590075Sobrien pending_mem = deps->pending_read_mems; 79690075Sobrien while (pending) 79790075Sobrien { 79890075Sobrien if (read_dependence (XEXP (pending_mem, 0), t)) 79990075Sobrien add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); 80090075Sobrien 80190075Sobrien pending = XEXP (pending, 1); 80290075Sobrien pending_mem = XEXP (pending_mem, 1); 80390075Sobrien } 80490075Sobrien 80590075Sobrien pending = deps->pending_write_insns; 80690075Sobrien pending_mem = deps->pending_write_mems; 80790075Sobrien while (pending) 80890075Sobrien { 80990075Sobrien if (true_dependence (XEXP (pending_mem, 0), VOIDmode, 81090075Sobrien t, rtx_varies_p)) 81190075Sobrien add_dependence (insn, XEXP (pending, 0), 0); 81290075Sobrien 81390075Sobrien pending = XEXP (pending, 1); 81490075Sobrien pending_mem = XEXP (pending_mem, 1); 81590075Sobrien } 81690075Sobrien 81790075Sobrien for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1)) 81890075Sobrien if (GET_CODE (XEXP (u, 0)) != JUMP_INSN 81990075Sobrien || deps_may_trap_p (x)) 82090075Sobrien add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); 82190075Sobrien 82290075Sobrien /* Always add these dependencies to pending_reads, since 82390075Sobrien this insn may be followed by a write. */ 82490075Sobrien add_insn_mem_dependence (deps, &deps->pending_read_insns, 82590075Sobrien &deps->pending_read_mems, insn, x); 82690075Sobrien 82790075Sobrien /* Take advantage of tail recursion here. */ 82890075Sobrien sched_analyze_2 (deps, XEXP (x, 0), insn); 82990075Sobrien return; 83090075Sobrien } 83190075Sobrien 83290075Sobrien /* Force pending stores to memory in case a trap handler needs them. */ 83390075Sobrien case TRAP_IF: 83490075Sobrien flush_pending_lists (deps, insn, true, false); 83590075Sobrien break; 83690075Sobrien 83790075Sobrien case ASM_OPERANDS: 83890075Sobrien case ASM_INPUT: 83990075Sobrien case UNSPEC_VOLATILE: 84090075Sobrien { 84190075Sobrien /* Traditional and volatile asm instructions must be considered to use 84290075Sobrien and clobber all hard registers, all pseudo-registers and all of 84390075Sobrien memory. So must TRAP_IF and UNSPEC_VOLATILE operations. 84490075Sobrien 84590075Sobrien Consider for instance a volatile asm that changes the fpu rounding 84690075Sobrien mode. An insn should not be moved across this even if it only uses 84790075Sobrien pseudo-regs because it might give an incorrectly rounded result. */ 84890075Sobrien if (code != ASM_OPERANDS || MEM_VOLATILE_P (x)) 84990075Sobrien reg_pending_barrier = true; 85090075Sobrien 85190075Sobrien /* For all ASM_OPERANDS, we must traverse the vector of input operands. 85290075Sobrien We can not just fall through here since then we would be confused 85390075Sobrien by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate 85490075Sobrien traditional asms unlike their normal usage. */ 85590075Sobrien 85690075Sobrien if (code == ASM_OPERANDS) 85790075Sobrien { 85890075Sobrien for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++) 85990075Sobrien sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn); 86090075Sobrien return; 86190075Sobrien } 86290075Sobrien break; 86390075Sobrien } 86490075Sobrien 86590075Sobrien case PRE_DEC: 86690075Sobrien case POST_DEC: 86790075Sobrien case PRE_INC: 86890075Sobrien case POST_INC: 86990075Sobrien /* These both read and modify the result. We must handle them as writes 87090075Sobrien to get proper dependencies for following instructions. We must handle 87190075Sobrien them as reads to get proper dependencies from this to previous 87290075Sobrien instructions. Thus we need to pass them to both sched_analyze_1 87390075Sobrien and sched_analyze_2. We must call sched_analyze_2 first in order 87490075Sobrien to get the proper antecedent for the read. */ 87590075Sobrien sched_analyze_2 (deps, XEXP (x, 0), insn); 87690075Sobrien sched_analyze_1 (deps, x, insn); 87790075Sobrien return; 87890075Sobrien 87990075Sobrien case POST_MODIFY: 88090075Sobrien case PRE_MODIFY: 88190075Sobrien /* op0 = op0 + op1 */ 88290075Sobrien sched_analyze_2 (deps, XEXP (x, 0), insn); 88390075Sobrien sched_analyze_2 (deps, XEXP (x, 1), insn); 88490075Sobrien sched_analyze_1 (deps, x, insn); 88590075Sobrien return; 88690075Sobrien 88790075Sobrien default: 88890075Sobrien break; 88990075Sobrien } 89090075Sobrien 89190075Sobrien /* Other cases: walk the insn. */ 89290075Sobrien fmt = GET_RTX_FORMAT (code); 89390075Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 89490075Sobrien { 89590075Sobrien if (fmt[i] == 'e') 89690075Sobrien sched_analyze_2 (deps, XEXP (x, i), insn); 89790075Sobrien else if (fmt[i] == 'E') 89890075Sobrien for (j = 0; j < XVECLEN (x, i); j++) 89990075Sobrien sched_analyze_2 (deps, XVECEXP (x, i, j), insn); 90090075Sobrien } 90190075Sobrien} 90290075Sobrien 90390075Sobrien/* Analyze an INSN with pattern X to find all dependencies. */ 90490075Sobrien 90590075Sobrienstatic void 90690075Sobriensched_analyze_insn (deps, x, insn, loop_notes) 90790075Sobrien struct deps *deps; 90890075Sobrien rtx x, insn; 90990075Sobrien rtx loop_notes; 91090075Sobrien{ 91190075Sobrien RTX_CODE code = GET_CODE (x); 91290075Sobrien rtx link; 91390075Sobrien int i; 91490075Sobrien 91590075Sobrien if (code == COND_EXEC) 91690075Sobrien { 91790075Sobrien sched_analyze_2 (deps, COND_EXEC_TEST (x), insn); 91890075Sobrien 91990075Sobrien /* ??? Should be recording conditions so we reduce the number of 92090075Sobrien false dependencies. */ 92190075Sobrien x = COND_EXEC_CODE (x); 92290075Sobrien code = GET_CODE (x); 92390075Sobrien } 92490075Sobrien if (code == SET || code == CLOBBER) 925104752Skan { 926104752Skan sched_analyze_1 (deps, x, insn); 927104752Skan 928104752Skan /* Bare clobber insns are used for letting life analysis, reg-stack 929104752Skan and others know that a value is dead. Depend on the last call 930104752Skan instruction so that reg-stack won't get confused. */ 931104752Skan if (code == CLOBBER) 932104752Skan add_dependence_list (insn, deps->last_function_call, REG_DEP_OUTPUT); 933104752Skan } 93490075Sobrien else if (code == PARALLEL) 93590075Sobrien { 93690075Sobrien int i; 93790075Sobrien for (i = XVECLEN (x, 0) - 1; i >= 0; i--) 93890075Sobrien { 93990075Sobrien rtx sub = XVECEXP (x, 0, i); 94090075Sobrien code = GET_CODE (sub); 94190075Sobrien 94290075Sobrien if (code == COND_EXEC) 94390075Sobrien { 94490075Sobrien sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn); 94590075Sobrien sub = COND_EXEC_CODE (sub); 94690075Sobrien code = GET_CODE (sub); 94790075Sobrien } 94890075Sobrien if (code == SET || code == CLOBBER) 94990075Sobrien sched_analyze_1 (deps, sub, insn); 95090075Sobrien else 95190075Sobrien sched_analyze_2 (deps, sub, insn); 95290075Sobrien } 95390075Sobrien } 95490075Sobrien else 95590075Sobrien sched_analyze_2 (deps, x, insn); 95690075Sobrien 95790075Sobrien /* Mark registers CLOBBERED or used by called function. */ 95890075Sobrien if (GET_CODE (insn) == CALL_INSN) 95990075Sobrien { 96090075Sobrien for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) 96190075Sobrien { 96290075Sobrien if (GET_CODE (XEXP (link, 0)) == CLOBBER) 96390075Sobrien sched_analyze_1 (deps, XEXP (link, 0), insn); 96490075Sobrien else 96590075Sobrien sched_analyze_2 (deps, XEXP (link, 0), insn); 96690075Sobrien } 96790075Sobrien if (find_reg_note (insn, REG_SETJMP, NULL)) 96890075Sobrien reg_pending_barrier = true; 96990075Sobrien } 97090075Sobrien 97190075Sobrien if (GET_CODE (insn) == JUMP_INSN) 97290075Sobrien { 97390075Sobrien rtx next; 97490075Sobrien next = next_nonnote_insn (insn); 97590075Sobrien if (next && GET_CODE (next) == BARRIER) 97690075Sobrien reg_pending_barrier = true; 97790075Sobrien else 97890075Sobrien { 97990075Sobrien rtx pending, pending_mem; 98090075Sobrien regset_head tmp; 98190075Sobrien INIT_REG_SET (&tmp); 98290075Sobrien 98390075Sobrien (*current_sched_info->compute_jump_reg_dependencies) (insn, &tmp); 98490075Sobrien IOR_REG_SET (reg_pending_uses, &tmp); 98590075Sobrien CLEAR_REG_SET (&tmp); 98690075Sobrien 98790075Sobrien /* All memory writes and volatile reads must happen before the 98890075Sobrien jump. Non-volatile reads must happen before the jump iff 98990075Sobrien the result is needed by the above register used mask. */ 99090075Sobrien 99190075Sobrien pending = deps->pending_write_insns; 99290075Sobrien pending_mem = deps->pending_write_mems; 99390075Sobrien while (pending) 99490075Sobrien { 99590075Sobrien add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 99690075Sobrien pending = XEXP (pending, 1); 99790075Sobrien pending_mem = XEXP (pending_mem, 1); 99890075Sobrien } 99990075Sobrien 100090075Sobrien pending = deps->pending_read_insns; 100190075Sobrien pending_mem = deps->pending_read_mems; 100290075Sobrien while (pending) 100390075Sobrien { 100490075Sobrien if (MEM_VOLATILE_P (XEXP (pending_mem, 0))) 100590075Sobrien add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 100690075Sobrien pending = XEXP (pending, 1); 100790075Sobrien pending_mem = XEXP (pending_mem, 1); 100890075Sobrien } 100990075Sobrien 101090075Sobrien add_dependence_list (insn, deps->last_pending_memory_flush, 101190075Sobrien REG_DEP_ANTI); 101290075Sobrien } 101390075Sobrien } 101490075Sobrien 101590075Sobrien /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic 101690075Sobrien block, then we must be sure that no instructions are scheduled across it. 101790075Sobrien Otherwise, the reg_n_refs info (which depends on loop_depth) would 101890075Sobrien become incorrect. */ 101990075Sobrien if (loop_notes) 102090075Sobrien { 102190075Sobrien rtx link; 102290075Sobrien 102390075Sobrien /* Update loop_notes with any notes from this insn. Also determine 102490075Sobrien if any of the notes on the list correspond to instruction scheduling 102590075Sobrien barriers (loop, eh & setjmp notes, but not range notes). */ 102690075Sobrien link = loop_notes; 102790075Sobrien while (XEXP (link, 1)) 102890075Sobrien { 102990075Sobrien if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG 103090075Sobrien || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END 103190075Sobrien || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG 103290075Sobrien || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END) 103390075Sobrien reg_pending_barrier = true; 103490075Sobrien 103590075Sobrien link = XEXP (link, 1); 103690075Sobrien } 103790075Sobrien XEXP (link, 1) = REG_NOTES (insn); 103890075Sobrien REG_NOTES (insn) = loop_notes; 103990075Sobrien } 104090075Sobrien 104190075Sobrien /* If this instruction can throw an exception, then moving it changes 1042117395Skan where block boundaries fall. This is mighty confusing elsewhere. 104390075Sobrien Therefore, prevent such an instruction from being moved. */ 104490075Sobrien if (can_throw_internal (insn)) 104590075Sobrien reg_pending_barrier = true; 104690075Sobrien 104790075Sobrien /* Add dependencies if a scheduling barrier was found. */ 104890075Sobrien if (reg_pending_barrier) 104990075Sobrien { 105090075Sobrien if (GET_CODE (PATTERN (insn)) == COND_EXEC) 105190075Sobrien { 105290075Sobrien EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 105390075Sobrien { 105490075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 105590075Sobrien add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 105690075Sobrien add_dependence_list (insn, reg_last->sets, 0); 105790075Sobrien add_dependence_list (insn, reg_last->clobbers, 0); 105890075Sobrien }); 105990075Sobrien } 106090075Sobrien else 106190075Sobrien { 106290075Sobrien EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 106390075Sobrien { 106490075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 106590075Sobrien add_dependence_list_and_free (insn, ®_last->uses, 106690075Sobrien REG_DEP_ANTI); 106790075Sobrien add_dependence_list_and_free (insn, ®_last->sets, 0); 106890075Sobrien add_dependence_list_and_free (insn, ®_last->clobbers, 0); 106990075Sobrien reg_last->uses_length = 0; 107090075Sobrien reg_last->clobbers_length = 0; 107190075Sobrien }); 107290075Sobrien } 107390075Sobrien 107490075Sobrien for (i = 0; i < deps->max_reg; i++) 107590075Sobrien { 107690075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 107790075Sobrien reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 107890075Sobrien SET_REGNO_REG_SET (&deps->reg_last_in_use, i); 107990075Sobrien } 108090075Sobrien 108190075Sobrien flush_pending_lists (deps, insn, true, true); 108290075Sobrien reg_pending_barrier = false; 108390075Sobrien } 108490075Sobrien else 108590075Sobrien { 108690075Sobrien /* If the current insn is conditional, we can't free any 108790075Sobrien of the lists. */ 108890075Sobrien if (GET_CODE (PATTERN (insn)) == COND_EXEC) 108990075Sobrien { 109090075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, 109190075Sobrien { 109290075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 109390075Sobrien add_dependence_list (insn, reg_last->sets, 0); 109490075Sobrien add_dependence_list (insn, reg_last->clobbers, 0); 109590075Sobrien reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 109690075Sobrien reg_last->uses_length++; 109790075Sobrien }); 109890075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, 109990075Sobrien { 110090075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 110190075Sobrien add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 110290075Sobrien add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 110390075Sobrien reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers); 110490075Sobrien reg_last->clobbers_length++; 110590075Sobrien }); 110690075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, 110790075Sobrien { 110890075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 110990075Sobrien add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 111090075Sobrien add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT); 111190075Sobrien add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 111290075Sobrien reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 111390075Sobrien }); 111490075Sobrien } 111590075Sobrien else 111690075Sobrien { 111790075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, 111890075Sobrien { 111990075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 112090075Sobrien add_dependence_list (insn, reg_last->sets, 0); 112190075Sobrien add_dependence_list (insn, reg_last->clobbers, 0); 112290075Sobrien reg_last->uses_length++; 112390075Sobrien reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 112490075Sobrien }); 112590075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, 112690075Sobrien { 112790075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 112890075Sobrien if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH 112990075Sobrien || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH) 113090075Sobrien { 113190075Sobrien add_dependence_list_and_free (insn, ®_last->sets, 113290075Sobrien REG_DEP_OUTPUT); 113390075Sobrien add_dependence_list_and_free (insn, ®_last->uses, 113490075Sobrien REG_DEP_ANTI); 113590075Sobrien add_dependence_list_and_free (insn, ®_last->clobbers, 113690075Sobrien REG_DEP_OUTPUT); 1137103445Skan reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 113890075Sobrien reg_last->clobbers_length = 0; 113990075Sobrien reg_last->uses_length = 0; 114090075Sobrien } 114190075Sobrien else 114290075Sobrien { 114390075Sobrien add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 114490075Sobrien add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 114590075Sobrien } 114690075Sobrien reg_last->clobbers_length++; 114790075Sobrien reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers); 114890075Sobrien }); 114990075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, 115090075Sobrien { 115190075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 115290075Sobrien add_dependence_list_and_free (insn, ®_last->sets, 115390075Sobrien REG_DEP_OUTPUT); 115490075Sobrien add_dependence_list_and_free (insn, ®_last->clobbers, 115590075Sobrien REG_DEP_OUTPUT); 115690075Sobrien add_dependence_list_and_free (insn, ®_last->uses, 115790075Sobrien REG_DEP_ANTI); 115890075Sobrien reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 115990075Sobrien reg_last->uses_length = 0; 116090075Sobrien reg_last->clobbers_length = 0; 116190075Sobrien }); 116290075Sobrien } 116390075Sobrien 116490075Sobrien IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses); 116590075Sobrien IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers); 116690075Sobrien IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets); 116790075Sobrien } 116890075Sobrien CLEAR_REG_SET (reg_pending_uses); 116990075Sobrien CLEAR_REG_SET (reg_pending_clobbers); 117090075Sobrien CLEAR_REG_SET (reg_pending_sets); 117190075Sobrien 1172102780Skan /* If we are currently in a libcall scheduling group, then mark the 1173102780Skan current insn as being in a scheduling group and that it can not 1174102780Skan be moved into a different basic block. */ 1175102780Skan 1176102780Skan if (deps->libcall_block_tail_insn) 1177102780Skan { 1178102780Skan set_sched_group_p (insn); 1179102780Skan CANT_MOVE (insn) = 1; 1180102780Skan } 1181102780Skan 118290075Sobrien /* If a post-call group is still open, see if it should remain so. 118390075Sobrien This insn must be a simple move of a hard reg to a pseudo or 118490075Sobrien vice-versa. 118590075Sobrien 118690075Sobrien We must avoid moving these insns for correctness on 118790075Sobrien SMALL_REGISTER_CLASS machines, and for special registers like 118890075Sobrien PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all 118990075Sobrien hard regs for all targets. */ 119090075Sobrien 119190075Sobrien if (deps->in_post_call_group_p) 119290075Sobrien { 119390075Sobrien rtx tmp, set = single_set (insn); 119490075Sobrien int src_regno, dest_regno; 119590075Sobrien 119690075Sobrien if (set == NULL) 119790075Sobrien goto end_call_group; 119890075Sobrien 119990075Sobrien tmp = SET_DEST (set); 120090075Sobrien if (GET_CODE (tmp) == SUBREG) 120190075Sobrien tmp = SUBREG_REG (tmp); 120290075Sobrien if (GET_CODE (tmp) == REG) 120390075Sobrien dest_regno = REGNO (tmp); 120490075Sobrien else 120590075Sobrien goto end_call_group; 120690075Sobrien 120790075Sobrien tmp = SET_SRC (set); 120890075Sobrien if (GET_CODE (tmp) == SUBREG) 120990075Sobrien tmp = SUBREG_REG (tmp); 121090075Sobrien if (GET_CODE (tmp) == REG) 121190075Sobrien src_regno = REGNO (tmp); 121290075Sobrien else 121390075Sobrien goto end_call_group; 121490075Sobrien 121590075Sobrien if (src_regno < FIRST_PSEUDO_REGISTER 121690075Sobrien || dest_regno < FIRST_PSEUDO_REGISTER) 121790075Sobrien { 121890075Sobrien set_sched_group_p (insn); 121990075Sobrien CANT_MOVE (insn) = 1; 122090075Sobrien } 122190075Sobrien else 122290075Sobrien { 122390075Sobrien end_call_group: 122490075Sobrien deps->in_post_call_group_p = false; 122590075Sobrien } 122690075Sobrien } 122790075Sobrien} 122890075Sobrien 122990075Sobrien/* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS 123090075Sobrien for every dependency. */ 123190075Sobrien 123290075Sobrienvoid 123390075Sobriensched_analyze (deps, head, tail) 123490075Sobrien struct deps *deps; 123590075Sobrien rtx head, tail; 123690075Sobrien{ 123790075Sobrien rtx insn; 123890075Sobrien rtx loop_notes = 0; 123990075Sobrien 124090075Sobrien if (current_sched_info->use_cselib) 124190075Sobrien cselib_init (); 124290075Sobrien 124390075Sobrien for (insn = head;; insn = NEXT_INSN (insn)) 124490075Sobrien { 1245117395Skan rtx link, end_seq, r0, set; 1246102780Skan 124790075Sobrien if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 124890075Sobrien { 124990075Sobrien /* Clear out the stale LOG_LINKS from flow. */ 125090075Sobrien free_INSN_LIST_list (&LOG_LINKS (insn)); 125190075Sobrien 125290075Sobrien /* Make each JUMP_INSN a scheduling barrier for memory 125390075Sobrien references. */ 125490075Sobrien if (GET_CODE (insn) == JUMP_INSN) 125590075Sobrien { 125690075Sobrien /* Keep the list a reasonable size. */ 125790075Sobrien if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH) 125890075Sobrien flush_pending_lists (deps, insn, true, true); 125990075Sobrien else 126090075Sobrien deps->last_pending_memory_flush 126190075Sobrien = alloc_INSN_LIST (insn, deps->last_pending_memory_flush); 126290075Sobrien } 126390075Sobrien sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); 126490075Sobrien loop_notes = 0; 126590075Sobrien } 126690075Sobrien else if (GET_CODE (insn) == CALL_INSN) 126790075Sobrien { 126890075Sobrien int i; 126990075Sobrien 127090075Sobrien CANT_MOVE (insn) = 1; 127190075Sobrien 127290075Sobrien /* Clear out the stale LOG_LINKS from flow. */ 127390075Sobrien free_INSN_LIST_list (&LOG_LINKS (insn)); 127490075Sobrien 127590075Sobrien if (find_reg_note (insn, REG_SETJMP, NULL)) 127690075Sobrien { 127790075Sobrien /* This is setjmp. Assume that all registers, not just 127890075Sobrien hard registers, may be clobbered by this call. */ 127990075Sobrien reg_pending_barrier = true; 128090075Sobrien } 128190075Sobrien else 128290075Sobrien { 128390075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 128490075Sobrien /* A call may read and modify global register variables. */ 128590075Sobrien if (global_regs[i]) 128690075Sobrien { 128790075Sobrien SET_REGNO_REG_SET (reg_pending_sets, i); 128890075Sobrien SET_REGNO_REG_SET (reg_pending_uses, i); 128990075Sobrien } 1290117395Skan /* Other call-clobbered hard regs may be clobbered. 1291117395Skan Since we only have a choice between 'might be clobbered' 1292117395Skan and 'definitely not clobbered', we must include all 1293117395Skan partly call-clobbered registers here. */ 1294117395Skan else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i]) 1295117395Skan || TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 129690075Sobrien SET_REGNO_REG_SET (reg_pending_clobbers, i); 129790075Sobrien /* We don't know what set of fixed registers might be used 129890075Sobrien by the function, but it is certain that the stack pointer 129990075Sobrien is among them, but be conservative. */ 130090075Sobrien else if (fixed_regs[i]) 130190075Sobrien SET_REGNO_REG_SET (reg_pending_uses, i); 130290075Sobrien /* The frame pointer is normally not used by the function 130390075Sobrien itself, but by the debugger. */ 130490075Sobrien /* ??? MIPS o32 is an exception. It uses the frame pointer 130590075Sobrien in the macro expansion of jal but does not represent this 130690075Sobrien fact in the call_insn rtl. */ 130790075Sobrien else if (i == FRAME_POINTER_REGNUM 130890075Sobrien || (i == HARD_FRAME_POINTER_REGNUM 130990075Sobrien && (! reload_completed || frame_pointer_needed))) 131090075Sobrien SET_REGNO_REG_SET (reg_pending_uses, i); 131190075Sobrien } 131290075Sobrien 131390075Sobrien /* For each insn which shouldn't cross a call, add a dependence 131490075Sobrien between that insn and this call insn. */ 131590075Sobrien add_dependence_list_and_free (insn, &deps->sched_before_next_call, 131690075Sobrien REG_DEP_ANTI); 131790075Sobrien 131890075Sobrien sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); 131990075Sobrien loop_notes = 0; 132090075Sobrien 132190075Sobrien /* In the absence of interprocedural alias analysis, we must flush 132290075Sobrien all pending reads and writes, and start new dependencies starting 132390075Sobrien from here. But only flush writes for constant calls (which may 132490075Sobrien be passed a pointer to something we haven't written yet). */ 132590075Sobrien flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn)); 132690075Sobrien 132790075Sobrien /* Remember the last function call for limiting lifetimes. */ 132890075Sobrien free_INSN_LIST_list (&deps->last_function_call); 132990075Sobrien deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX); 133090075Sobrien 133190075Sobrien /* Before reload, begin a post-call group, so as to keep the 133290075Sobrien lifetimes of hard registers correct. */ 133390075Sobrien if (! reload_completed) 133490075Sobrien deps->in_post_call_group_p = true; 133590075Sobrien } 133690075Sobrien 133790075Sobrien /* See comments on reemit_notes as to why we do this. 133890075Sobrien ??? Actually, the reemit_notes just say what is done, not why. */ 133990075Sobrien 1340117395Skan if (GET_CODE (insn) == NOTE 134190075Sobrien && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG 134290075Sobrien || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END 134390075Sobrien || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG 134490075Sobrien || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)) 134590075Sobrien { 134690075Sobrien rtx rtx_region; 134790075Sobrien 134890075Sobrien if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG 134990075Sobrien || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END) 135090075Sobrien rtx_region = GEN_INT (NOTE_EH_HANDLER (insn)); 135190075Sobrien else 135290075Sobrien rtx_region = GEN_INT (0); 135390075Sobrien 135490075Sobrien loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 135590075Sobrien rtx_region, 135690075Sobrien loop_notes); 135790075Sobrien loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 135890075Sobrien GEN_INT (NOTE_LINE_NUMBER (insn)), 135990075Sobrien loop_notes); 136090075Sobrien CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn); 136190075Sobrien } 136290075Sobrien 136390075Sobrien if (current_sched_info->use_cselib) 136490075Sobrien cselib_process_insn (insn); 1365102780Skan 1366102780Skan /* Now that we have completed handling INSN, check and see if it is 1367102780Skan a CLOBBER beginning a libcall block. If it is, record the 1368102780Skan end of the libcall sequence. 1369102780Skan 1370102780Skan We want to schedule libcall blocks as a unit before reload. While 1371102780Skan this restricts scheduling, it preserves the meaning of a libcall 1372102780Skan block. 1373102780Skan 1374102780Skan As a side effect, we may get better code due to decreased register 1375102780Skan pressure as well as less chance of a foreign insn appearing in 1376102780Skan a libcall block. */ 1377102780Skan if (!reload_completed 1378102780Skan /* Note we may have nested libcall sequences. We only care about 1379102780Skan the outermost libcall sequence. */ 1380102780Skan && deps->libcall_block_tail_insn == 0 1381102780Skan /* The sequence must start with a clobber of a register. */ 1382102780Skan && GET_CODE (insn) == INSN 1383102780Skan && GET_CODE (PATTERN (insn)) == CLOBBER 1384102780Skan && (r0 = XEXP (PATTERN (insn), 0), GET_CODE (r0) == REG) 1385102780Skan && GET_CODE (XEXP (PATTERN (insn), 0)) == REG 1386102780Skan /* The CLOBBER must also have a REG_LIBCALL note attached. */ 1387102780Skan && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0 1388102780Skan && (end_seq = XEXP (link, 0)) != 0 1389102780Skan /* The insn referenced by the REG_LIBCALL note must be a 1390102780Skan simple nop copy with the same destination as the register 1391102780Skan mentioned in the clobber. */ 1392102780Skan && (set = single_set (end_seq)) != 0 1393102780Skan && SET_DEST (set) == r0 && SET_SRC (set) == r0 1394102780Skan /* And finally the insn referenced by the REG_LIBCALL must 1395102780Skan also contain a REG_EQUAL note and a REG_RETVAL note. */ 1396102780Skan && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0 1397102780Skan && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0) 1398102780Skan deps->libcall_block_tail_insn = XEXP (link, 0); 1399102780Skan 1400102780Skan /* If we have reached the end of a libcall block, then close the 1401102780Skan block. */ 1402102780Skan if (deps->libcall_block_tail_insn == insn) 1403102780Skan deps->libcall_block_tail_insn = 0; 1404102780Skan 140590075Sobrien if (insn == tail) 140690075Sobrien { 140790075Sobrien if (current_sched_info->use_cselib) 140890075Sobrien cselib_finish (); 140990075Sobrien return; 141090075Sobrien } 141190075Sobrien } 141290075Sobrien abort (); 141390075Sobrien} 141490075Sobrien 141590075Sobrien/* Examine insns in the range [ HEAD, TAIL ] and Use the backward 141690075Sobrien dependences from LOG_LINKS to build forward dependences in 141790075Sobrien INSN_DEPEND. */ 141890075Sobrien 141990075Sobrienvoid 142090075Sobriencompute_forward_dependences (head, tail) 142190075Sobrien rtx head, tail; 142290075Sobrien{ 142390075Sobrien rtx insn, link; 142490075Sobrien rtx next_tail; 142590075Sobrien enum reg_note dep_type; 142690075Sobrien 142790075Sobrien next_tail = NEXT_INSN (tail); 142890075Sobrien for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 142990075Sobrien { 143090075Sobrien if (! INSN_P (insn)) 143190075Sobrien continue; 143290075Sobrien 143390075Sobrien insn = group_leader (insn); 143490075Sobrien 143590075Sobrien for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) 143690075Sobrien { 143790075Sobrien rtx x = group_leader (XEXP (link, 0)); 143890075Sobrien rtx new_link; 143990075Sobrien 144090075Sobrien if (x != XEXP (link, 0)) 144190075Sobrien continue; 144290075Sobrien 144390075Sobrien#ifdef ENABLE_CHECKING 144490075Sobrien /* If add_dependence is working properly there should never 144590075Sobrien be notes, deleted insns or duplicates in the backward 144690075Sobrien links. Thus we need not check for them here. 144790075Sobrien 144890075Sobrien However, if we have enabled checking we might as well go 144990075Sobrien ahead and verify that add_dependence worked properly. */ 145090075Sobrien if (GET_CODE (x) == NOTE 145190075Sobrien || INSN_DELETED_P (x) 145290075Sobrien || (forward_dependency_cache != NULL 145390075Sobrien && TEST_BIT (forward_dependency_cache[INSN_LUID (x)], 145490075Sobrien INSN_LUID (insn))) 145590075Sobrien || (forward_dependency_cache == NULL 145690075Sobrien && find_insn_list (insn, INSN_DEPEND (x)))) 145790075Sobrien abort (); 145890075Sobrien if (forward_dependency_cache != NULL) 145990075Sobrien SET_BIT (forward_dependency_cache[INSN_LUID (x)], 146090075Sobrien INSN_LUID (insn)); 146190075Sobrien#endif 146290075Sobrien 146390075Sobrien new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x)); 146490075Sobrien 146590075Sobrien dep_type = REG_NOTE_KIND (link); 146690075Sobrien PUT_REG_NOTE_KIND (new_link, dep_type); 146790075Sobrien 146890075Sobrien INSN_DEPEND (x) = new_link; 146990075Sobrien INSN_DEP_COUNT (insn) += 1; 147090075Sobrien } 147190075Sobrien } 147290075Sobrien} 147390075Sobrien 147490075Sobrien/* Initialize variables for region data dependence analysis. 147590075Sobrien n_bbs is the number of region blocks. */ 147690075Sobrien 147790075Sobrienvoid 147890075Sobrieninit_deps (deps) 147990075Sobrien struct deps *deps; 148090075Sobrien{ 148190075Sobrien int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ()); 148290075Sobrien 148390075Sobrien deps->max_reg = max_reg; 148490075Sobrien deps->reg_last = (struct deps_reg *) 148590075Sobrien xcalloc (max_reg, sizeof (struct deps_reg)); 148690075Sobrien INIT_REG_SET (&deps->reg_last_in_use); 148790075Sobrien 148890075Sobrien deps->pending_read_insns = 0; 148990075Sobrien deps->pending_read_mems = 0; 149090075Sobrien deps->pending_write_insns = 0; 149190075Sobrien deps->pending_write_mems = 0; 149290075Sobrien deps->pending_lists_length = 0; 149390075Sobrien deps->pending_flush_length = 0; 149490075Sobrien deps->last_pending_memory_flush = 0; 149590075Sobrien deps->last_function_call = 0; 149690075Sobrien deps->sched_before_next_call = 0; 149790075Sobrien deps->in_post_call_group_p = false; 1498102780Skan deps->libcall_block_tail_insn = 0; 149990075Sobrien} 150090075Sobrien 150190075Sobrien/* Free insn lists found in DEPS. */ 150290075Sobrien 150390075Sobrienvoid 150490075Sobrienfree_deps (deps) 150590075Sobrien struct deps *deps; 150690075Sobrien{ 150790075Sobrien int i; 150890075Sobrien 150990075Sobrien free_INSN_LIST_list (&deps->pending_read_insns); 151090075Sobrien free_EXPR_LIST_list (&deps->pending_read_mems); 151190075Sobrien free_INSN_LIST_list (&deps->pending_write_insns); 151290075Sobrien free_EXPR_LIST_list (&deps->pending_write_mems); 151390075Sobrien free_INSN_LIST_list (&deps->last_pending_memory_flush); 151490075Sobrien 151590075Sobrien /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions 151690075Sobrien times. For a test case with 42000 regs and 8000 small basic blocks, 151790075Sobrien this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */ 151890075Sobrien EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 151990075Sobrien { 152090075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 1521117395Skan if (reg_last->uses) 1522117395Skan free_INSN_LIST_list (®_last->uses); 1523117395Skan if (reg_last->sets) 1524117395Skan free_INSN_LIST_list (®_last->sets); 1525117395Skan if (reg_last->clobbers) 1526117395Skan free_INSN_LIST_list (®_last->clobbers); 152790075Sobrien }); 152890075Sobrien CLEAR_REG_SET (&deps->reg_last_in_use); 152990075Sobrien 153090075Sobrien free (deps->reg_last); 153190075Sobrien} 153290075Sobrien 153390075Sobrien/* If it is profitable to use them, initialize caches for tracking 153490075Sobrien dependency informatino. LUID is the number of insns to be scheduled, 153590075Sobrien it is used in the estimate of profitability. */ 153690075Sobrien 153790075Sobrienvoid 153890075Sobrieninit_dependency_caches (luid) 153990075Sobrien int luid; 154090075Sobrien{ 154190075Sobrien /* ?!? We could save some memory by computing a per-region luid mapping 154290075Sobrien which could reduce both the number of vectors in the cache and the size 154390075Sobrien of each vector. Instead we just avoid the cache entirely unless the 154490075Sobrien average number of instructions in a basic block is very high. See 154590075Sobrien the comment before the declaration of true_dependency_cache for 154690075Sobrien what we consider "very high". */ 154790075Sobrien if (luid / n_basic_blocks > 100 * 5) 154890075Sobrien { 154990075Sobrien true_dependency_cache = sbitmap_vector_alloc (luid, luid); 155090075Sobrien sbitmap_vector_zero (true_dependency_cache, luid); 155190075Sobrien anti_dependency_cache = sbitmap_vector_alloc (luid, luid); 155290075Sobrien sbitmap_vector_zero (anti_dependency_cache, luid); 155390075Sobrien output_dependency_cache = sbitmap_vector_alloc (luid, luid); 155490075Sobrien sbitmap_vector_zero (output_dependency_cache, luid); 155590075Sobrien#ifdef ENABLE_CHECKING 155690075Sobrien forward_dependency_cache = sbitmap_vector_alloc (luid, luid); 155790075Sobrien sbitmap_vector_zero (forward_dependency_cache, luid); 155890075Sobrien#endif 155990075Sobrien } 156090075Sobrien} 156190075Sobrien 156290075Sobrien/* Free the caches allocated in init_dependency_caches. */ 156390075Sobrien 156490075Sobrienvoid 156590075Sobrienfree_dependency_caches () 156690075Sobrien{ 156790075Sobrien if (true_dependency_cache) 156890075Sobrien { 156990075Sobrien sbitmap_vector_free (true_dependency_cache); 157090075Sobrien true_dependency_cache = NULL; 157190075Sobrien sbitmap_vector_free (anti_dependency_cache); 157290075Sobrien anti_dependency_cache = NULL; 157390075Sobrien sbitmap_vector_free (output_dependency_cache); 157490075Sobrien output_dependency_cache = NULL; 157590075Sobrien#ifdef ENABLE_CHECKING 157690075Sobrien sbitmap_vector_free (forward_dependency_cache); 157790075Sobrien forward_dependency_cache = NULL; 157890075Sobrien#endif 157990075Sobrien } 158090075Sobrien} 158190075Sobrien 158290075Sobrien/* Initialize some global variables needed by the dependency analysis 158390075Sobrien code. */ 158490075Sobrien 158590075Sobrienvoid 158690075Sobrieninit_deps_global () 158790075Sobrien{ 158890075Sobrien reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head); 158990075Sobrien reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head); 159090075Sobrien reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head); 159190075Sobrien reg_pending_barrier = false; 159290075Sobrien} 159390075Sobrien 159490075Sobrien/* Free everything used by the dependency analysis code. */ 159590075Sobrien 159690075Sobrienvoid 159790075Sobrienfinish_deps_global () 159890075Sobrien{ 159990075Sobrien FREE_REG_SET (reg_pending_sets); 160090075Sobrien FREE_REG_SET (reg_pending_clobbers); 160190075Sobrien FREE_REG_SET (reg_pending_uses); 160290075Sobrien} 1603