sched-deps.c revision 90075
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); 22590075Sobrien if (next && SCHED_GROUP_P (next) 22690075Sobrien && GET_CODE (next) != CODE_LABEL) 22790075Sobrien { 22890075Sobrien /* Notes will never intervene here though, so don't bother checking 22990075Sobrien for them. */ 23090075Sobrien /* Hah! Wrong. */ 23190075Sobrien /* We must reject CODE_LABELs, so that we don't get confused by one 23290075Sobrien that has LABEL_PRESERVE_P set, which is represented by the same 23390075Sobrien bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be 23490075Sobrien SCHED_GROUP_P. */ 23590075Sobrien 23690075Sobrien rtx nnext; 23790075Sobrien while ((nnext = next_nonnote_insn (next)) != NULL 23890075Sobrien && SCHED_GROUP_P (nnext) 23990075Sobrien && GET_CODE (nnext) != CODE_LABEL) 24090075Sobrien next = nnext; 24190075Sobrien 24290075Sobrien /* Again, don't depend an insn on itself. */ 24390075Sobrien if (insn == next) 24490075Sobrien return; 24590075Sobrien 24690075Sobrien /* Make the dependence to NEXT, the last insn of the group, instead 24790075Sobrien of the original ELEM. */ 24890075Sobrien elem = next; 24990075Sobrien } 25090075Sobrien 25190075Sobrien present_p = 1; 25290075Sobrien#ifdef INSN_SCHEDULING 25390075Sobrien /* ??? No good way to tell from here whether we're doing interblock 25490075Sobrien scheduling. Possibly add another callback. */ 25590075Sobrien#if 0 25690075Sobrien /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.) 25790075Sobrien No need for interblock dependences with calls, since 25890075Sobrien calls are not moved between blocks. Note: the edge where 25990075Sobrien elem is a CALL is still required. */ 26090075Sobrien if (GET_CODE (insn) == CALL_INSN 26190075Sobrien && (INSN_BB (elem) != INSN_BB (insn))) 26290075Sobrien return; 26390075Sobrien#endif 26490075Sobrien 26590075Sobrien /* If we already have a dependency for ELEM, then we do not need to 26690075Sobrien do anything. Avoiding the list walk below can cut compile times 26790075Sobrien dramatically for some code. */ 26890075Sobrien if (true_dependency_cache != NULL) 26990075Sobrien { 27090075Sobrien enum reg_note present_dep_type = 0; 27190075Sobrien 27290075Sobrien if (anti_dependency_cache == NULL || output_dependency_cache == NULL) 27390075Sobrien abort (); 27490075Sobrien if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem))) 27590075Sobrien /* Do nothing (present_set_type is already 0). */ 27690075Sobrien ; 27790075Sobrien else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)], 27890075Sobrien INSN_LUID (elem))) 27990075Sobrien present_dep_type = REG_DEP_ANTI; 28090075Sobrien else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)], 28190075Sobrien INSN_LUID (elem))) 28290075Sobrien present_dep_type = REG_DEP_OUTPUT; 28390075Sobrien else 28490075Sobrien present_p = 0; 28590075Sobrien if (present_p && (int) dep_type >= (int) present_dep_type) 28690075Sobrien return; 28790075Sobrien } 28890075Sobrien#endif 28990075Sobrien 29090075Sobrien /* Check that we don't already have this dependence. */ 29190075Sobrien if (present_p) 29290075Sobrien for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) 29390075Sobrien if (XEXP (link, 0) == elem) 29490075Sobrien { 29590075Sobrien#ifdef INSN_SCHEDULING 29690075Sobrien /* Clear corresponding cache entry because type of the link 29790075Sobrien may be changed. */ 29890075Sobrien if (true_dependency_cache != NULL) 29990075Sobrien { 30090075Sobrien if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 30190075Sobrien RESET_BIT (anti_dependency_cache[INSN_LUID (insn)], 30290075Sobrien INSN_LUID (elem)); 30390075Sobrien else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT 30490075Sobrien && output_dependency_cache) 30590075Sobrien RESET_BIT (output_dependency_cache[INSN_LUID (insn)], 30690075Sobrien INSN_LUID (elem)); 30790075Sobrien else 30890075Sobrien abort (); 30990075Sobrien } 31090075Sobrien#endif 31190075Sobrien 31290075Sobrien /* If this is a more restrictive type of dependence than the existing 31390075Sobrien one, then change the existing dependence to this type. */ 31490075Sobrien if ((int) dep_type < (int) REG_NOTE_KIND (link)) 31590075Sobrien PUT_REG_NOTE_KIND (link, dep_type); 31690075Sobrien 31790075Sobrien#ifdef INSN_SCHEDULING 31890075Sobrien /* If we are adding a dependency to INSN's LOG_LINKs, then 31990075Sobrien note that in the bitmap caches of dependency information. */ 32090075Sobrien if (true_dependency_cache != NULL) 32190075Sobrien { 32290075Sobrien if ((int) REG_NOTE_KIND (link) == 0) 32390075Sobrien SET_BIT (true_dependency_cache[INSN_LUID (insn)], 32490075Sobrien INSN_LUID (elem)); 32590075Sobrien else if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 32690075Sobrien SET_BIT (anti_dependency_cache[INSN_LUID (insn)], 32790075Sobrien INSN_LUID (elem)); 32890075Sobrien else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) 32990075Sobrien SET_BIT (output_dependency_cache[INSN_LUID (insn)], 33090075Sobrien INSN_LUID (elem)); 33190075Sobrien } 33290075Sobrien#endif 33390075Sobrien return; 33490075Sobrien } 33590075Sobrien /* Might want to check one level of transitivity to save conses. */ 33690075Sobrien 33790075Sobrien link = alloc_INSN_LIST (elem, LOG_LINKS (insn)); 33890075Sobrien LOG_LINKS (insn) = link; 33990075Sobrien 34090075Sobrien /* Insn dependency, not data dependency. */ 34190075Sobrien PUT_REG_NOTE_KIND (link, dep_type); 34290075Sobrien 34390075Sobrien#ifdef INSN_SCHEDULING 34490075Sobrien /* If we are adding a dependency to INSN's LOG_LINKs, then note that 34590075Sobrien in the bitmap caches of dependency information. */ 34690075Sobrien if (true_dependency_cache != NULL) 34790075Sobrien { 34890075Sobrien if ((int) dep_type == 0) 34990075Sobrien SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); 35090075Sobrien else if (dep_type == REG_DEP_ANTI) 35190075Sobrien SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); 35290075Sobrien else if (dep_type == REG_DEP_OUTPUT) 35390075Sobrien SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); 35490075Sobrien } 35590075Sobrien#endif 35690075Sobrien} 35790075Sobrien 35890075Sobrien/* A convenience wrapper to operate on an entire list. */ 35990075Sobrien 36090075Sobrienstatic void 36190075Sobrienadd_dependence_list (insn, list, dep_type) 36290075Sobrien rtx insn, list; 36390075Sobrien enum reg_note dep_type; 36490075Sobrien{ 36590075Sobrien for (; list; list = XEXP (list, 1)) 36690075Sobrien add_dependence (insn, XEXP (list, 0), dep_type); 36790075Sobrien} 36890075Sobrien 36990075Sobrien/* Similar, but free *LISTP at the same time. */ 37090075Sobrien 37190075Sobrienstatic void 37290075Sobrienadd_dependence_list_and_free (insn, listp, dep_type) 37390075Sobrien rtx insn; 37490075Sobrien rtx *listp; 37590075Sobrien enum reg_note dep_type; 37690075Sobrien{ 37790075Sobrien rtx list, next; 37890075Sobrien for (list = *listp, *listp = NULL; list ; list = next) 37990075Sobrien { 38090075Sobrien next = XEXP (list, 1); 38190075Sobrien add_dependence (insn, XEXP (list, 0), dep_type); 38290075Sobrien free_INSN_LIST_node (list); 38390075Sobrien } 38490075Sobrien} 38590075Sobrien 38690075Sobrien/* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS 38790075Sobrien of INSN. Abort if not found. */ 38890075Sobrien 38990075Sobrienstatic void 39090075Sobrienremove_dependence (insn, elem) 39190075Sobrien rtx insn; 39290075Sobrien rtx elem; 39390075Sobrien{ 39490075Sobrien rtx prev, link, next; 39590075Sobrien int found = 0; 39690075Sobrien 39790075Sobrien for (prev = 0, link = LOG_LINKS (insn); link; link = next) 39890075Sobrien { 39990075Sobrien next = XEXP (link, 1); 40090075Sobrien if (XEXP (link, 0) == elem) 40190075Sobrien { 40290075Sobrien if (prev) 40390075Sobrien XEXP (prev, 1) = next; 40490075Sobrien else 40590075Sobrien LOG_LINKS (insn) = next; 40690075Sobrien 40790075Sobrien#ifdef INSN_SCHEDULING 40890075Sobrien /* If we are removing a dependency from the LOG_LINKS list, 40990075Sobrien make sure to remove it from the cache too. */ 41090075Sobrien if (true_dependency_cache != NULL) 41190075Sobrien { 41290075Sobrien if (REG_NOTE_KIND (link) == 0) 41390075Sobrien RESET_BIT (true_dependency_cache[INSN_LUID (insn)], 41490075Sobrien INSN_LUID (elem)); 41590075Sobrien else if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 41690075Sobrien RESET_BIT (anti_dependency_cache[INSN_LUID (insn)], 41790075Sobrien INSN_LUID (elem)); 41890075Sobrien else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) 41990075Sobrien RESET_BIT (output_dependency_cache[INSN_LUID (insn)], 42090075Sobrien INSN_LUID (elem)); 42190075Sobrien } 42290075Sobrien#endif 42390075Sobrien 42490075Sobrien free_INSN_LIST_node (link); 42590075Sobrien 42690075Sobrien found = 1; 42790075Sobrien } 42890075Sobrien else 42990075Sobrien prev = link; 43090075Sobrien } 43190075Sobrien 43290075Sobrien if (!found) 43390075Sobrien abort (); 43490075Sobrien return; 43590075Sobrien} 43690075Sobrien 43790075Sobrien/* Return an insn which represents a SCHED_GROUP, which is 43890075Sobrien the last insn in the group. */ 43990075Sobrien 44090075Sobrienstatic rtx 44190075Sobriengroup_leader (insn) 44290075Sobrien rtx insn; 44390075Sobrien{ 44490075Sobrien rtx prev; 44590075Sobrien 44690075Sobrien do 44790075Sobrien { 44890075Sobrien prev = insn; 44990075Sobrien insn = next_nonnote_insn (insn); 45090075Sobrien } 45190075Sobrien while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL)); 45290075Sobrien 45390075Sobrien return prev; 45490075Sobrien} 45590075Sobrien 45690075Sobrien/* Set SCHED_GROUP_P and care for the rest of the bookkeeping that 45790075Sobrien goes along with that. */ 45890075Sobrien 45990075Sobrienstatic void 46090075Sobrienset_sched_group_p (insn) 46190075Sobrien rtx insn; 46290075Sobrien{ 46390075Sobrien rtx link, prev; 46490075Sobrien 46590075Sobrien SCHED_GROUP_P (insn) = 1; 46690075Sobrien 46790075Sobrien /* There may be a note before this insn now, but all notes will 46890075Sobrien be removed before we actually try to schedule the insns, so 46990075Sobrien it won't cause a problem later. We must avoid it here though. */ 47090075Sobrien prev = prev_nonnote_insn (insn); 47190075Sobrien 47290075Sobrien /* Make a copy of all dependencies on the immediately previous insn, 47390075Sobrien and add to this insn. This is so that all the dependencies will 47490075Sobrien apply to the group. Remove an explicit dependence on this insn 47590075Sobrien as SCHED_GROUP_P now represents it. */ 47690075Sobrien 47790075Sobrien if (find_insn_list (prev, LOG_LINKS (insn))) 47890075Sobrien remove_dependence (insn, prev); 47990075Sobrien 48090075Sobrien for (link = LOG_LINKS (prev); link; link = XEXP (link, 1)) 48190075Sobrien add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link)); 48290075Sobrien} 48390075Sobrien 48490075Sobrien/* Process an insn's memory dependencies. There are four kinds of 48590075Sobrien dependencies: 48690075Sobrien 48790075Sobrien (0) read dependence: read follows read 48890075Sobrien (1) true dependence: read follows write 48990075Sobrien (2) anti dependence: write follows read 49090075Sobrien (3) output dependence: write follows write 49190075Sobrien 49290075Sobrien We are careful to build only dependencies which actually exist, and 49390075Sobrien use transitivity to avoid building too many links. */ 49490075Sobrien 49590075Sobrien/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST. 49690075Sobrien The MEM is a memory reference contained within INSN, which we are saving 49790075Sobrien so that we can do memory aliasing on it. */ 49890075Sobrien 49990075Sobrienvoid 50090075Sobrienadd_insn_mem_dependence (deps, insn_list, mem_list, insn, mem) 50190075Sobrien struct deps *deps; 50290075Sobrien rtx *insn_list, *mem_list, insn, mem; 50390075Sobrien{ 50490075Sobrien rtx link; 50590075Sobrien 50690075Sobrien link = alloc_INSN_LIST (insn, *insn_list); 50790075Sobrien *insn_list = link; 50890075Sobrien 50990075Sobrien if (current_sched_info->use_cselib) 51090075Sobrien { 51190075Sobrien mem = shallow_copy_rtx (mem); 51290075Sobrien XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0)); 51390075Sobrien } 51490075Sobrien link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list); 51590075Sobrien *mem_list = link; 51690075Sobrien 51790075Sobrien deps->pending_lists_length++; 51890075Sobrien} 51990075Sobrien 52090075Sobrien/* Make a dependency between every memory reference on the pending lists 52190075Sobrien and INSN, thus flushing the pending lists. FOR_READ is true if emitting 52290075Sobrien dependencies for a read operation, similarly with FOR_WRITE. */ 52390075Sobrien 52490075Sobrienstatic void 52590075Sobrienflush_pending_lists (deps, insn, for_read, for_write) 52690075Sobrien struct deps *deps; 52790075Sobrien rtx insn; 52890075Sobrien int for_read, for_write; 52990075Sobrien{ 53090075Sobrien if (for_write) 53190075Sobrien { 53290075Sobrien add_dependence_list_and_free (insn, &deps->pending_read_insns, 53390075Sobrien REG_DEP_ANTI); 53490075Sobrien free_EXPR_LIST_list (&deps->pending_read_mems); 53590075Sobrien } 53690075Sobrien 53790075Sobrien add_dependence_list_and_free (insn, &deps->pending_write_insns, 53890075Sobrien for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT); 53990075Sobrien free_EXPR_LIST_list (&deps->pending_write_mems); 54090075Sobrien deps->pending_lists_length = 0; 54190075Sobrien 54290075Sobrien add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 54390075Sobrien for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT); 54490075Sobrien deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX); 54590075Sobrien deps->pending_flush_length = 1; 54690075Sobrien} 54790075Sobrien 54890075Sobrien/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC 54990075Sobrien rtx, X, creating all dependencies generated by the write to the 55090075Sobrien destination of X, and reads of everything mentioned. */ 55190075Sobrien 55290075Sobrienstatic void 55390075Sobriensched_analyze_1 (deps, x, insn) 55490075Sobrien struct deps *deps; 55590075Sobrien rtx x; 55690075Sobrien rtx insn; 55790075Sobrien{ 55890075Sobrien int regno; 55990075Sobrien rtx dest = XEXP (x, 0); 56090075Sobrien enum rtx_code code = GET_CODE (x); 56190075Sobrien 56290075Sobrien if (dest == 0) 56390075Sobrien return; 56490075Sobrien 56590075Sobrien if (GET_CODE (dest) == PARALLEL) 56690075Sobrien { 56790075Sobrien int i; 56890075Sobrien 56990075Sobrien for (i = XVECLEN (dest, 0) - 1; i >= 0; i--) 57090075Sobrien if (XEXP (XVECEXP (dest, 0, i), 0) != 0) 57190075Sobrien sched_analyze_1 (deps, 57290075Sobrien gen_rtx_CLOBBER (VOIDmode, 57390075Sobrien XEXP (XVECEXP (dest, 0, i), 0)), 57490075Sobrien insn); 57590075Sobrien 57690075Sobrien if (GET_CODE (x) == SET) 57790075Sobrien sched_analyze_2 (deps, SET_SRC (x), insn); 57890075Sobrien return; 57990075Sobrien } 58090075Sobrien 58190075Sobrien while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG 58290075Sobrien || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) 58390075Sobrien { 58490075Sobrien if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) 58590075Sobrien { 58690075Sobrien /* The second and third arguments are values read by this insn. */ 58790075Sobrien sched_analyze_2 (deps, XEXP (dest, 1), insn); 58890075Sobrien sched_analyze_2 (deps, XEXP (dest, 2), insn); 58990075Sobrien } 59090075Sobrien dest = XEXP (dest, 0); 59190075Sobrien } 59290075Sobrien 59390075Sobrien if (GET_CODE (dest) == REG) 59490075Sobrien { 59590075Sobrien regno = REGNO (dest); 59690075Sobrien 59790075Sobrien /* A hard reg in a wide mode may really be multiple registers. 59890075Sobrien If so, mark all of them just like the first. */ 59990075Sobrien if (regno < FIRST_PSEUDO_REGISTER) 60090075Sobrien { 60190075Sobrien int i = HARD_REGNO_NREGS (regno, GET_MODE (dest)); 60290075Sobrien if (code == SET) 60390075Sobrien { 60490075Sobrien while (--i >= 0) 60590075Sobrien SET_REGNO_REG_SET (reg_pending_sets, regno + i); 60690075Sobrien } 60790075Sobrien else 60890075Sobrien { 60990075Sobrien while (--i >= 0) 61090075Sobrien SET_REGNO_REG_SET (reg_pending_clobbers, regno + i); 61190075Sobrien } 61290075Sobrien } 61390075Sobrien /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that 61490075Sobrien it does not reload. Ignore these as they have served their 61590075Sobrien purpose already. */ 61690075Sobrien else if (regno >= deps->max_reg) 61790075Sobrien { 61890075Sobrien if (GET_CODE (PATTERN (insn)) != USE 61990075Sobrien && GET_CODE (PATTERN (insn)) != CLOBBER) 62090075Sobrien abort (); 62190075Sobrien } 62290075Sobrien else 62390075Sobrien { 62490075Sobrien if (code == SET) 62590075Sobrien SET_REGNO_REG_SET (reg_pending_sets, regno); 62690075Sobrien else 62790075Sobrien SET_REGNO_REG_SET (reg_pending_clobbers, regno); 62890075Sobrien 62990075Sobrien /* Pseudos that are REG_EQUIV to something may be replaced 63090075Sobrien by that during reloading. We need only add dependencies for 63190075Sobrien the address in the REG_EQUIV note. */ 63290075Sobrien if (!reload_completed 63390075Sobrien && reg_known_equiv_p[regno] 63490075Sobrien && GET_CODE (reg_known_value[regno]) == MEM) 63590075Sobrien sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn); 63690075Sobrien 63790075Sobrien /* Don't let it cross a call after scheduling if it doesn't 63890075Sobrien already cross one. */ 63990075Sobrien if (REG_N_CALLS_CROSSED (regno) == 0) 64090075Sobrien add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI); 64190075Sobrien } 64290075Sobrien } 64390075Sobrien else if (GET_CODE (dest) == MEM) 64490075Sobrien { 64590075Sobrien /* Writing memory. */ 64690075Sobrien rtx t = dest; 64790075Sobrien 64890075Sobrien if (current_sched_info->use_cselib) 64990075Sobrien { 65090075Sobrien t = shallow_copy_rtx (dest); 65190075Sobrien cselib_lookup (XEXP (t, 0), Pmode, 1); 65290075Sobrien XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0)); 65390075Sobrien } 65490075Sobrien 65590075Sobrien if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH) 65690075Sobrien { 65790075Sobrien /* Flush all pending reads and writes to prevent the pending lists 65890075Sobrien from getting any larger. Insn scheduling runs too slowly when 65990075Sobrien these lists get long. When compiling GCC with itself, 66090075Sobrien this flush occurs 8 times for sparc, and 10 times for m88k using 66190075Sobrien the default value of 32. */ 66290075Sobrien flush_pending_lists (deps, insn, false, true); 66390075Sobrien } 66490075Sobrien else 66590075Sobrien { 66690075Sobrien rtx pending, pending_mem; 66790075Sobrien 66890075Sobrien pending = deps->pending_read_insns; 66990075Sobrien pending_mem = deps->pending_read_mems; 67090075Sobrien while (pending) 67190075Sobrien { 67290075Sobrien if (anti_dependence (XEXP (pending_mem, 0), t)) 67390075Sobrien add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); 67490075Sobrien 67590075Sobrien pending = XEXP (pending, 1); 67690075Sobrien pending_mem = XEXP (pending_mem, 1); 67790075Sobrien } 67890075Sobrien 67990075Sobrien pending = deps->pending_write_insns; 68090075Sobrien pending_mem = deps->pending_write_mems; 68190075Sobrien while (pending) 68290075Sobrien { 68390075Sobrien if (output_dependence (XEXP (pending_mem, 0), t)) 68490075Sobrien add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 68590075Sobrien 68690075Sobrien pending = XEXP (pending, 1); 68790075Sobrien pending_mem = XEXP (pending_mem, 1); 68890075Sobrien } 68990075Sobrien 69090075Sobrien add_dependence_list (insn, deps->last_pending_memory_flush, 69190075Sobrien REG_DEP_ANTI); 69290075Sobrien 69390075Sobrien add_insn_mem_dependence (deps, &deps->pending_write_insns, 69490075Sobrien &deps->pending_write_mems, insn, dest); 69590075Sobrien } 69690075Sobrien sched_analyze_2 (deps, XEXP (dest, 0), insn); 69790075Sobrien } 69890075Sobrien 69990075Sobrien /* Analyze reads. */ 70090075Sobrien if (GET_CODE (x) == SET) 70190075Sobrien sched_analyze_2 (deps, SET_SRC (x), insn); 70290075Sobrien} 70390075Sobrien 70490075Sobrien/* Analyze the uses of memory and registers in rtx X in INSN. */ 70590075Sobrien 70690075Sobrienstatic void 70790075Sobriensched_analyze_2 (deps, x, insn) 70890075Sobrien struct deps *deps; 70990075Sobrien rtx x; 71090075Sobrien rtx insn; 71190075Sobrien{ 71290075Sobrien int i; 71390075Sobrien int j; 71490075Sobrien enum rtx_code code; 71590075Sobrien const char *fmt; 71690075Sobrien 71790075Sobrien if (x == 0) 71890075Sobrien return; 71990075Sobrien 72090075Sobrien code = GET_CODE (x); 72190075Sobrien 72290075Sobrien switch (code) 72390075Sobrien { 72490075Sobrien case CONST_INT: 72590075Sobrien case CONST_DOUBLE: 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) 92590075Sobrien sched_analyze_1 (deps, x, insn); 92690075Sobrien else if (code == PARALLEL) 92790075Sobrien { 92890075Sobrien int i; 92990075Sobrien for (i = XVECLEN (x, 0) - 1; i >= 0; i--) 93090075Sobrien { 93190075Sobrien rtx sub = XVECEXP (x, 0, i); 93290075Sobrien code = GET_CODE (sub); 93390075Sobrien 93490075Sobrien if (code == COND_EXEC) 93590075Sobrien { 93690075Sobrien sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn); 93790075Sobrien sub = COND_EXEC_CODE (sub); 93890075Sobrien code = GET_CODE (sub); 93990075Sobrien } 94090075Sobrien if (code == SET || code == CLOBBER) 94190075Sobrien sched_analyze_1 (deps, sub, insn); 94290075Sobrien else 94390075Sobrien sched_analyze_2 (deps, sub, insn); 94490075Sobrien } 94590075Sobrien } 94690075Sobrien else 94790075Sobrien sched_analyze_2 (deps, x, insn); 94890075Sobrien 94990075Sobrien /* Mark registers CLOBBERED or used by called function. */ 95090075Sobrien if (GET_CODE (insn) == CALL_INSN) 95190075Sobrien { 95290075Sobrien for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) 95390075Sobrien { 95490075Sobrien if (GET_CODE (XEXP (link, 0)) == CLOBBER) 95590075Sobrien sched_analyze_1 (deps, XEXP (link, 0), insn); 95690075Sobrien else 95790075Sobrien sched_analyze_2 (deps, XEXP (link, 0), insn); 95890075Sobrien } 95990075Sobrien if (find_reg_note (insn, REG_SETJMP, NULL)) 96090075Sobrien reg_pending_barrier = true; 96190075Sobrien } 96290075Sobrien 96390075Sobrien if (GET_CODE (insn) == JUMP_INSN) 96490075Sobrien { 96590075Sobrien rtx next; 96690075Sobrien next = next_nonnote_insn (insn); 96790075Sobrien if (next && GET_CODE (next) == BARRIER) 96890075Sobrien reg_pending_barrier = true; 96990075Sobrien else 97090075Sobrien { 97190075Sobrien rtx pending, pending_mem; 97290075Sobrien regset_head tmp; 97390075Sobrien INIT_REG_SET (&tmp); 97490075Sobrien 97590075Sobrien (*current_sched_info->compute_jump_reg_dependencies) (insn, &tmp); 97690075Sobrien IOR_REG_SET (reg_pending_uses, &tmp); 97790075Sobrien CLEAR_REG_SET (&tmp); 97890075Sobrien 97990075Sobrien /* All memory writes and volatile reads must happen before the 98090075Sobrien jump. Non-volatile reads must happen before the jump iff 98190075Sobrien the result is needed by the above register used mask. */ 98290075Sobrien 98390075Sobrien pending = deps->pending_write_insns; 98490075Sobrien pending_mem = deps->pending_write_mems; 98590075Sobrien while (pending) 98690075Sobrien { 98790075Sobrien add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 98890075Sobrien pending = XEXP (pending, 1); 98990075Sobrien pending_mem = XEXP (pending_mem, 1); 99090075Sobrien } 99190075Sobrien 99290075Sobrien pending = deps->pending_read_insns; 99390075Sobrien pending_mem = deps->pending_read_mems; 99490075Sobrien while (pending) 99590075Sobrien { 99690075Sobrien if (MEM_VOLATILE_P (XEXP (pending_mem, 0))) 99790075Sobrien add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 99890075Sobrien pending = XEXP (pending, 1); 99990075Sobrien pending_mem = XEXP (pending_mem, 1); 100090075Sobrien } 100190075Sobrien 100290075Sobrien add_dependence_list (insn, deps->last_pending_memory_flush, 100390075Sobrien REG_DEP_ANTI); 100490075Sobrien } 100590075Sobrien } 100690075Sobrien 100790075Sobrien /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic 100890075Sobrien block, then we must be sure that no instructions are scheduled across it. 100990075Sobrien Otherwise, the reg_n_refs info (which depends on loop_depth) would 101090075Sobrien become incorrect. */ 101190075Sobrien if (loop_notes) 101290075Sobrien { 101390075Sobrien rtx link; 101490075Sobrien 101590075Sobrien /* Update loop_notes with any notes from this insn. Also determine 101690075Sobrien if any of the notes on the list correspond to instruction scheduling 101790075Sobrien barriers (loop, eh & setjmp notes, but not range notes). */ 101890075Sobrien link = loop_notes; 101990075Sobrien while (XEXP (link, 1)) 102090075Sobrien { 102190075Sobrien if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG 102290075Sobrien || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END 102390075Sobrien || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG 102490075Sobrien || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END) 102590075Sobrien reg_pending_barrier = true; 102690075Sobrien 102790075Sobrien link = XEXP (link, 1); 102890075Sobrien } 102990075Sobrien XEXP (link, 1) = REG_NOTES (insn); 103090075Sobrien REG_NOTES (insn) = loop_notes; 103190075Sobrien } 103290075Sobrien 103390075Sobrien /* If this instruction can throw an exception, then moving it changes 103490075Sobrien where block boundaries fall. This is mighty confusing elsewhere. 103590075Sobrien Therefore, prevent such an instruction from being moved. */ 103690075Sobrien if (can_throw_internal (insn)) 103790075Sobrien reg_pending_barrier = true; 103890075Sobrien 103990075Sobrien /* Add dependencies if a scheduling barrier was found. */ 104090075Sobrien if (reg_pending_barrier) 104190075Sobrien { 104290075Sobrien if (GET_CODE (PATTERN (insn)) == COND_EXEC) 104390075Sobrien { 104490075Sobrien EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 104590075Sobrien { 104690075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 104790075Sobrien add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 104890075Sobrien add_dependence_list (insn, reg_last->sets, 0); 104990075Sobrien add_dependence_list (insn, reg_last->clobbers, 0); 105090075Sobrien }); 105190075Sobrien } 105290075Sobrien else 105390075Sobrien { 105490075Sobrien EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 105590075Sobrien { 105690075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 105790075Sobrien add_dependence_list_and_free (insn, ®_last->uses, 105890075Sobrien REG_DEP_ANTI); 105990075Sobrien add_dependence_list_and_free (insn, ®_last->sets, 0); 106090075Sobrien add_dependence_list_and_free (insn, ®_last->clobbers, 0); 106190075Sobrien reg_last->uses_length = 0; 106290075Sobrien reg_last->clobbers_length = 0; 106390075Sobrien }); 106490075Sobrien } 106590075Sobrien 106690075Sobrien for (i = 0; i < deps->max_reg; i++) 106790075Sobrien { 106890075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 106990075Sobrien reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 107090075Sobrien SET_REGNO_REG_SET (&deps->reg_last_in_use, i); 107190075Sobrien } 107290075Sobrien 107390075Sobrien flush_pending_lists (deps, insn, true, true); 107490075Sobrien reg_pending_barrier = false; 107590075Sobrien } 107690075Sobrien else 107790075Sobrien { 107890075Sobrien /* If the current insn is conditional, we can't free any 107990075Sobrien of the lists. */ 108090075Sobrien if (GET_CODE (PATTERN (insn)) == COND_EXEC) 108190075Sobrien { 108290075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, 108390075Sobrien { 108490075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 108590075Sobrien add_dependence_list (insn, reg_last->sets, 0); 108690075Sobrien add_dependence_list (insn, reg_last->clobbers, 0); 108790075Sobrien reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 108890075Sobrien reg_last->uses_length++; 108990075Sobrien }); 109090075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, 109190075Sobrien { 109290075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 109390075Sobrien add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 109490075Sobrien add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 109590075Sobrien reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers); 109690075Sobrien reg_last->clobbers_length++; 109790075Sobrien }); 109890075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 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->clobbers, REG_DEP_OUTPUT); 110390075Sobrien add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 110490075Sobrien reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 110590075Sobrien }); 110690075Sobrien } 110790075Sobrien else 110890075Sobrien { 110990075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, 111090075Sobrien { 111190075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 111290075Sobrien add_dependence_list (insn, reg_last->sets, 0); 111390075Sobrien add_dependence_list (insn, reg_last->clobbers, 0); 111490075Sobrien reg_last->uses_length++; 111590075Sobrien reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 111690075Sobrien }); 111790075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, 111890075Sobrien { 111990075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 112090075Sobrien add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 112190075Sobrien add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 112290075Sobrien if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH 112390075Sobrien || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH) 112490075Sobrien { 112590075Sobrien add_dependence_list_and_free (insn, ®_last->sets, 112690075Sobrien REG_DEP_OUTPUT); 112790075Sobrien add_dependence_list_and_free (insn, ®_last->uses, 112890075Sobrien REG_DEP_ANTI); 112990075Sobrien add_dependence_list_and_free (insn, ®_last->clobbers, 113090075Sobrien REG_DEP_OUTPUT); 113190075Sobrien reg_last->clobbers_length = 0; 113290075Sobrien reg_last->uses_length = 0; 113390075Sobrien } 113490075Sobrien else 113590075Sobrien { 113690075Sobrien add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 113790075Sobrien add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 113890075Sobrien } 113990075Sobrien reg_last->clobbers_length++; 114090075Sobrien reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers); 114190075Sobrien }); 114290075Sobrien EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, 114390075Sobrien { 114490075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 114590075Sobrien add_dependence_list_and_free (insn, ®_last->sets, 114690075Sobrien REG_DEP_OUTPUT); 114790075Sobrien add_dependence_list_and_free (insn, ®_last->clobbers, 114890075Sobrien REG_DEP_OUTPUT); 114990075Sobrien add_dependence_list_and_free (insn, ®_last->uses, 115090075Sobrien REG_DEP_ANTI); 115190075Sobrien reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 115290075Sobrien reg_last->uses_length = 0; 115390075Sobrien reg_last->clobbers_length = 0; 115490075Sobrien }); 115590075Sobrien } 115690075Sobrien 115790075Sobrien IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses); 115890075Sobrien IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers); 115990075Sobrien IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets); 116090075Sobrien } 116190075Sobrien CLEAR_REG_SET (reg_pending_uses); 116290075Sobrien CLEAR_REG_SET (reg_pending_clobbers); 116390075Sobrien CLEAR_REG_SET (reg_pending_sets); 116490075Sobrien 116590075Sobrien /* If a post-call group is still open, see if it should remain so. 116690075Sobrien This insn must be a simple move of a hard reg to a pseudo or 116790075Sobrien vice-versa. 116890075Sobrien 116990075Sobrien We must avoid moving these insns for correctness on 117090075Sobrien SMALL_REGISTER_CLASS machines, and for special registers like 117190075Sobrien PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all 117290075Sobrien hard regs for all targets. */ 117390075Sobrien 117490075Sobrien if (deps->in_post_call_group_p) 117590075Sobrien { 117690075Sobrien rtx tmp, set = single_set (insn); 117790075Sobrien int src_regno, dest_regno; 117890075Sobrien 117990075Sobrien if (set == NULL) 118090075Sobrien goto end_call_group; 118190075Sobrien 118290075Sobrien tmp = SET_DEST (set); 118390075Sobrien if (GET_CODE (tmp) == SUBREG) 118490075Sobrien tmp = SUBREG_REG (tmp); 118590075Sobrien if (GET_CODE (tmp) == REG) 118690075Sobrien dest_regno = REGNO (tmp); 118790075Sobrien else 118890075Sobrien goto end_call_group; 118990075Sobrien 119090075Sobrien tmp = SET_SRC (set); 119190075Sobrien if (GET_CODE (tmp) == SUBREG) 119290075Sobrien tmp = SUBREG_REG (tmp); 119390075Sobrien if (GET_CODE (tmp) == REG) 119490075Sobrien src_regno = REGNO (tmp); 119590075Sobrien else 119690075Sobrien goto end_call_group; 119790075Sobrien 119890075Sobrien if (src_regno < FIRST_PSEUDO_REGISTER 119990075Sobrien || dest_regno < FIRST_PSEUDO_REGISTER) 120090075Sobrien { 120190075Sobrien set_sched_group_p (insn); 120290075Sobrien CANT_MOVE (insn) = 1; 120390075Sobrien } 120490075Sobrien else 120590075Sobrien { 120690075Sobrien end_call_group: 120790075Sobrien deps->in_post_call_group_p = false; 120890075Sobrien } 120990075Sobrien } 121090075Sobrien} 121190075Sobrien 121290075Sobrien/* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS 121390075Sobrien for every dependency. */ 121490075Sobrien 121590075Sobrienvoid 121690075Sobriensched_analyze (deps, head, tail) 121790075Sobrien struct deps *deps; 121890075Sobrien rtx head, tail; 121990075Sobrien{ 122090075Sobrien rtx insn; 122190075Sobrien rtx loop_notes = 0; 122290075Sobrien 122390075Sobrien if (current_sched_info->use_cselib) 122490075Sobrien cselib_init (); 122590075Sobrien 122690075Sobrien for (insn = head;; insn = NEXT_INSN (insn)) 122790075Sobrien { 122890075Sobrien if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 122990075Sobrien { 123090075Sobrien /* Clear out the stale LOG_LINKS from flow. */ 123190075Sobrien free_INSN_LIST_list (&LOG_LINKS (insn)); 123290075Sobrien 123390075Sobrien /* Clear out stale SCHED_GROUP_P. */ 123490075Sobrien SCHED_GROUP_P (insn) = 0; 123590075Sobrien 123690075Sobrien /* Make each JUMP_INSN a scheduling barrier for memory 123790075Sobrien references. */ 123890075Sobrien if (GET_CODE (insn) == JUMP_INSN) 123990075Sobrien { 124090075Sobrien /* Keep the list a reasonable size. */ 124190075Sobrien if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH) 124290075Sobrien flush_pending_lists (deps, insn, true, true); 124390075Sobrien else 124490075Sobrien deps->last_pending_memory_flush 124590075Sobrien = alloc_INSN_LIST (insn, deps->last_pending_memory_flush); 124690075Sobrien } 124790075Sobrien sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); 124890075Sobrien loop_notes = 0; 124990075Sobrien } 125090075Sobrien else if (GET_CODE (insn) == CALL_INSN) 125190075Sobrien { 125290075Sobrien int i; 125390075Sobrien 125490075Sobrien /* Clear out stale SCHED_GROUP_P. */ 125590075Sobrien SCHED_GROUP_P (insn) = 0; 125690075Sobrien 125790075Sobrien CANT_MOVE (insn) = 1; 125890075Sobrien 125990075Sobrien /* Clear out the stale LOG_LINKS from flow. */ 126090075Sobrien free_INSN_LIST_list (&LOG_LINKS (insn)); 126190075Sobrien 126290075Sobrien if (find_reg_note (insn, REG_SETJMP, NULL)) 126390075Sobrien { 126490075Sobrien /* This is setjmp. Assume that all registers, not just 126590075Sobrien hard registers, may be clobbered by this call. */ 126690075Sobrien reg_pending_barrier = true; 126790075Sobrien } 126890075Sobrien else 126990075Sobrien { 127090075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 127190075Sobrien /* A call may read and modify global register variables. */ 127290075Sobrien if (global_regs[i]) 127390075Sobrien { 127490075Sobrien SET_REGNO_REG_SET (reg_pending_sets, i); 127590075Sobrien SET_REGNO_REG_SET (reg_pending_uses, i); 127690075Sobrien } 127790075Sobrien /* Other call-clobbered hard regs may be clobbered. */ 127890075Sobrien else if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 127990075Sobrien SET_REGNO_REG_SET (reg_pending_clobbers, i); 128090075Sobrien /* We don't know what set of fixed registers might be used 128190075Sobrien by the function, but it is certain that the stack pointer 128290075Sobrien is among them, but be conservative. */ 128390075Sobrien else if (fixed_regs[i]) 128490075Sobrien SET_REGNO_REG_SET (reg_pending_uses, i); 128590075Sobrien /* The frame pointer is normally not used by the function 128690075Sobrien itself, but by the debugger. */ 128790075Sobrien /* ??? MIPS o32 is an exception. It uses the frame pointer 128890075Sobrien in the macro expansion of jal but does not represent this 128990075Sobrien fact in the call_insn rtl. */ 129090075Sobrien else if (i == FRAME_POINTER_REGNUM 129190075Sobrien || (i == HARD_FRAME_POINTER_REGNUM 129290075Sobrien && (! reload_completed || frame_pointer_needed))) 129390075Sobrien SET_REGNO_REG_SET (reg_pending_uses, i); 129490075Sobrien } 129590075Sobrien 129690075Sobrien /* For each insn which shouldn't cross a call, add a dependence 129790075Sobrien between that insn and this call insn. */ 129890075Sobrien add_dependence_list_and_free (insn, &deps->sched_before_next_call, 129990075Sobrien REG_DEP_ANTI); 130090075Sobrien 130190075Sobrien sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); 130290075Sobrien loop_notes = 0; 130390075Sobrien 130490075Sobrien /* In the absence of interprocedural alias analysis, we must flush 130590075Sobrien all pending reads and writes, and start new dependencies starting 130690075Sobrien from here. But only flush writes for constant calls (which may 130790075Sobrien be passed a pointer to something we haven't written yet). */ 130890075Sobrien flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn)); 130990075Sobrien 131090075Sobrien /* Remember the last function call for limiting lifetimes. */ 131190075Sobrien free_INSN_LIST_list (&deps->last_function_call); 131290075Sobrien deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX); 131390075Sobrien 131490075Sobrien /* Before reload, begin a post-call group, so as to keep the 131590075Sobrien lifetimes of hard registers correct. */ 131690075Sobrien if (! reload_completed) 131790075Sobrien deps->in_post_call_group_p = true; 131890075Sobrien } 131990075Sobrien 132090075Sobrien /* See comments on reemit_notes as to why we do this. 132190075Sobrien ??? Actually, the reemit_notes just say what is done, not why. */ 132290075Sobrien 132390075Sobrien else if (GET_CODE (insn) == NOTE 132490075Sobrien && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG 132590075Sobrien || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END)) 132690075Sobrien { 132790075Sobrien loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn), 132890075Sobrien loop_notes); 132990075Sobrien loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 133090075Sobrien GEN_INT (NOTE_LINE_NUMBER (insn)), 133190075Sobrien loop_notes); 133290075Sobrien } 133390075Sobrien else if (GET_CODE (insn) == NOTE 133490075Sobrien && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG 133590075Sobrien || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END 133690075Sobrien || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG 133790075Sobrien || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)) 133890075Sobrien { 133990075Sobrien rtx rtx_region; 134090075Sobrien 134190075Sobrien if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG 134290075Sobrien || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END) 134390075Sobrien rtx_region = GEN_INT (NOTE_EH_HANDLER (insn)); 134490075Sobrien else 134590075Sobrien rtx_region = GEN_INT (0); 134690075Sobrien 134790075Sobrien loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 134890075Sobrien rtx_region, 134990075Sobrien loop_notes); 135090075Sobrien loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 135190075Sobrien GEN_INT (NOTE_LINE_NUMBER (insn)), 135290075Sobrien loop_notes); 135390075Sobrien CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn); 135490075Sobrien } 135590075Sobrien 135690075Sobrien if (current_sched_info->use_cselib) 135790075Sobrien cselib_process_insn (insn); 135890075Sobrien if (insn == tail) 135990075Sobrien { 136090075Sobrien if (current_sched_info->use_cselib) 136190075Sobrien cselib_finish (); 136290075Sobrien return; 136390075Sobrien } 136490075Sobrien } 136590075Sobrien abort (); 136690075Sobrien} 136790075Sobrien 136890075Sobrien/* Examine insns in the range [ HEAD, TAIL ] and Use the backward 136990075Sobrien dependences from LOG_LINKS to build forward dependences in 137090075Sobrien INSN_DEPEND. */ 137190075Sobrien 137290075Sobrienvoid 137390075Sobriencompute_forward_dependences (head, tail) 137490075Sobrien rtx head, tail; 137590075Sobrien{ 137690075Sobrien rtx insn, link; 137790075Sobrien rtx next_tail; 137890075Sobrien enum reg_note dep_type; 137990075Sobrien 138090075Sobrien next_tail = NEXT_INSN (tail); 138190075Sobrien for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 138290075Sobrien { 138390075Sobrien if (! INSN_P (insn)) 138490075Sobrien continue; 138590075Sobrien 138690075Sobrien insn = group_leader (insn); 138790075Sobrien 138890075Sobrien for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) 138990075Sobrien { 139090075Sobrien rtx x = group_leader (XEXP (link, 0)); 139190075Sobrien rtx new_link; 139290075Sobrien 139390075Sobrien if (x != XEXP (link, 0)) 139490075Sobrien continue; 139590075Sobrien 139690075Sobrien#ifdef ENABLE_CHECKING 139790075Sobrien /* If add_dependence is working properly there should never 139890075Sobrien be notes, deleted insns or duplicates in the backward 139990075Sobrien links. Thus we need not check for them here. 140090075Sobrien 140190075Sobrien However, if we have enabled checking we might as well go 140290075Sobrien ahead and verify that add_dependence worked properly. */ 140390075Sobrien if (GET_CODE (x) == NOTE 140490075Sobrien || INSN_DELETED_P (x) 140590075Sobrien || (forward_dependency_cache != NULL 140690075Sobrien && TEST_BIT (forward_dependency_cache[INSN_LUID (x)], 140790075Sobrien INSN_LUID (insn))) 140890075Sobrien || (forward_dependency_cache == NULL 140990075Sobrien && find_insn_list (insn, INSN_DEPEND (x)))) 141090075Sobrien abort (); 141190075Sobrien if (forward_dependency_cache != NULL) 141290075Sobrien SET_BIT (forward_dependency_cache[INSN_LUID (x)], 141390075Sobrien INSN_LUID (insn)); 141490075Sobrien#endif 141590075Sobrien 141690075Sobrien new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x)); 141790075Sobrien 141890075Sobrien dep_type = REG_NOTE_KIND (link); 141990075Sobrien PUT_REG_NOTE_KIND (new_link, dep_type); 142090075Sobrien 142190075Sobrien INSN_DEPEND (x) = new_link; 142290075Sobrien INSN_DEP_COUNT (insn) += 1; 142390075Sobrien } 142490075Sobrien } 142590075Sobrien} 142690075Sobrien 142790075Sobrien/* Initialize variables for region data dependence analysis. 142890075Sobrien n_bbs is the number of region blocks. */ 142990075Sobrien 143090075Sobrienvoid 143190075Sobrieninit_deps (deps) 143290075Sobrien struct deps *deps; 143390075Sobrien{ 143490075Sobrien int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ()); 143590075Sobrien 143690075Sobrien deps->max_reg = max_reg; 143790075Sobrien deps->reg_last = (struct deps_reg *) 143890075Sobrien xcalloc (max_reg, sizeof (struct deps_reg)); 143990075Sobrien INIT_REG_SET (&deps->reg_last_in_use); 144090075Sobrien 144190075Sobrien deps->pending_read_insns = 0; 144290075Sobrien deps->pending_read_mems = 0; 144390075Sobrien deps->pending_write_insns = 0; 144490075Sobrien deps->pending_write_mems = 0; 144590075Sobrien deps->pending_lists_length = 0; 144690075Sobrien deps->pending_flush_length = 0; 144790075Sobrien deps->last_pending_memory_flush = 0; 144890075Sobrien deps->last_function_call = 0; 144990075Sobrien deps->sched_before_next_call = 0; 145090075Sobrien deps->in_post_call_group_p = false; 145190075Sobrien} 145290075Sobrien 145390075Sobrien/* Free insn lists found in DEPS. */ 145490075Sobrien 145590075Sobrienvoid 145690075Sobrienfree_deps (deps) 145790075Sobrien struct deps *deps; 145890075Sobrien{ 145990075Sobrien int i; 146090075Sobrien 146190075Sobrien free_INSN_LIST_list (&deps->pending_read_insns); 146290075Sobrien free_EXPR_LIST_list (&deps->pending_read_mems); 146390075Sobrien free_INSN_LIST_list (&deps->pending_write_insns); 146490075Sobrien free_EXPR_LIST_list (&deps->pending_write_mems); 146590075Sobrien free_INSN_LIST_list (&deps->last_pending_memory_flush); 146690075Sobrien 146790075Sobrien /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions 146890075Sobrien times. For a test case with 42000 regs and 8000 small basic blocks, 146990075Sobrien this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */ 147090075Sobrien EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 147190075Sobrien { 147290075Sobrien struct deps_reg *reg_last = &deps->reg_last[i]; 147390075Sobrien free_INSN_LIST_list (®_last->uses); 147490075Sobrien free_INSN_LIST_list (®_last->sets); 147590075Sobrien free_INSN_LIST_list (®_last->clobbers); 147690075Sobrien }); 147790075Sobrien CLEAR_REG_SET (&deps->reg_last_in_use); 147890075Sobrien 147990075Sobrien free (deps->reg_last); 148090075Sobrien} 148190075Sobrien 148290075Sobrien/* If it is profitable to use them, initialize caches for tracking 148390075Sobrien dependency informatino. LUID is the number of insns to be scheduled, 148490075Sobrien it is used in the estimate of profitability. */ 148590075Sobrien 148690075Sobrienvoid 148790075Sobrieninit_dependency_caches (luid) 148890075Sobrien int luid; 148990075Sobrien{ 149090075Sobrien /* ?!? We could save some memory by computing a per-region luid mapping 149190075Sobrien which could reduce both the number of vectors in the cache and the size 149290075Sobrien of each vector. Instead we just avoid the cache entirely unless the 149390075Sobrien average number of instructions in a basic block is very high. See 149490075Sobrien the comment before the declaration of true_dependency_cache for 149590075Sobrien what we consider "very high". */ 149690075Sobrien if (luid / n_basic_blocks > 100 * 5) 149790075Sobrien { 149890075Sobrien true_dependency_cache = sbitmap_vector_alloc (luid, luid); 149990075Sobrien sbitmap_vector_zero (true_dependency_cache, luid); 150090075Sobrien anti_dependency_cache = sbitmap_vector_alloc (luid, luid); 150190075Sobrien sbitmap_vector_zero (anti_dependency_cache, luid); 150290075Sobrien output_dependency_cache = sbitmap_vector_alloc (luid, luid); 150390075Sobrien sbitmap_vector_zero (output_dependency_cache, luid); 150490075Sobrien#ifdef ENABLE_CHECKING 150590075Sobrien forward_dependency_cache = sbitmap_vector_alloc (luid, luid); 150690075Sobrien sbitmap_vector_zero (forward_dependency_cache, luid); 150790075Sobrien#endif 150890075Sobrien } 150990075Sobrien} 151090075Sobrien 151190075Sobrien/* Free the caches allocated in init_dependency_caches. */ 151290075Sobrien 151390075Sobrienvoid 151490075Sobrienfree_dependency_caches () 151590075Sobrien{ 151690075Sobrien if (true_dependency_cache) 151790075Sobrien { 151890075Sobrien sbitmap_vector_free (true_dependency_cache); 151990075Sobrien true_dependency_cache = NULL; 152090075Sobrien sbitmap_vector_free (anti_dependency_cache); 152190075Sobrien anti_dependency_cache = NULL; 152290075Sobrien sbitmap_vector_free (output_dependency_cache); 152390075Sobrien output_dependency_cache = NULL; 152490075Sobrien#ifdef ENABLE_CHECKING 152590075Sobrien sbitmap_vector_free (forward_dependency_cache); 152690075Sobrien forward_dependency_cache = NULL; 152790075Sobrien#endif 152890075Sobrien } 152990075Sobrien} 153090075Sobrien 153190075Sobrien/* Initialize some global variables needed by the dependency analysis 153290075Sobrien code. */ 153390075Sobrien 153490075Sobrienvoid 153590075Sobrieninit_deps_global () 153690075Sobrien{ 153790075Sobrien reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head); 153890075Sobrien reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head); 153990075Sobrien reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head); 154090075Sobrien reg_pending_barrier = false; 154190075Sobrien} 154290075Sobrien 154390075Sobrien/* Free everything used by the dependency analysis code. */ 154490075Sobrien 154590075Sobrienvoid 154690075Sobrienfinish_deps_global () 154790075Sobrien{ 154890075Sobrien FREE_REG_SET (reg_pending_sets); 154990075Sobrien FREE_REG_SET (reg_pending_clobbers); 155090075Sobrien FREE_REG_SET (reg_pending_uses); 155190075Sobrien} 1552