|
|
1.1 ! root 1: /* Dummy data flow analysis for GNU compiler in nonoptimizing mode. ! 2: Copyright (C) 1987, 1991 Free Software Foundation, Inc. ! 3: ! 4: This file is part of GNU CC. ! 5: ! 6: GNU CC is free software; you can redistribute it and/or modify ! 7: it under the terms of the GNU General Public License as published by ! 8: the Free Software Foundation; either version 2, or (at your option) ! 9: any later version. ! 10: ! 11: GNU CC is distributed in the hope that it will be useful, ! 12: but WITHOUT ANY WARRANTY; without even the implied warranty of ! 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ! 14: GNU General Public License for more details. ! 15: ! 16: You should have received a copy of the GNU General Public License ! 17: along with GNU CC; see the file COPYING. If not, write to ! 18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ ! 19: ! 20: ! 21: /* This file performs stupid register allocation, which is used ! 22: when cc1 gets the -noreg switch (which is when cc does not get -O). ! 23: ! 24: Stupid register allocation goes in place of the the flow_analysis, ! 25: local_alloc and global_alloc passes. combine_instructions cannot ! 26: be done with stupid allocation because the data flow info that it needs ! 27: is not computed here. ! 28: ! 29: In stupid allocation, the only user-defined variables that can ! 30: go in registers are those declared "register". They are assumed ! 31: to have a life span equal to their scope. Other user variables ! 32: are given stack slots in the rtl-generation pass and are not ! 33: represented as pseudo regs. A compiler-generated temporary ! 34: is assumed to live from its first mention to its last mention. ! 35: ! 36: Since each pseudo-reg's life span is just an interval, it can be ! 37: represented as a pair of numbers, each of which identifies an insn by ! 38: its position in the function (number of insns before it). The first ! 39: thing done for stupid allocation is to compute such a number for each ! 40: insn. It is called the suid. Then the life-interval of each ! 41: pseudo reg is computed. Then the pseudo regs are ordered by priority ! 42: and assigned hard regs in priority order. */ ! 43: ! 44: #include <stdio.h> ! 45: #include "config.h" ! 46: #include "rtl.h" ! 47: #include "hard-reg-set.h" ! 48: #include "regs.h" ! 49: #include "flags.h" ! 50: ! 51: /* Vector mapping INSN_UIDs to suids. ! 52: The suids are like uids but increase monononically always. ! 53: We use them to see whether a subroutine call came ! 54: between a variable's birth and its death. */ ! 55: ! 56: static int *uid_suid; ! 57: ! 58: /* Get the suid of an insn. */ ! 59: ! 60: #define INSN_SUID(INSN) (uid_suid[INSN_UID (INSN)]) ! 61: ! 62: /* Record the suid of the last CALL_INSN ! 63: so we can tell whether a pseudo reg crosses any calls. */ ! 64: ! 65: static int last_call_suid; ! 66: ! 67: /* Record the suid of the last JUMP_INSN ! 68: so we can tell whether a pseudo reg crosses any jumps. */ ! 69: ! 70: static int last_jump_suid; ! 71: ! 72: /* Record the suid of the last CODE_LABEL ! 73: so we can tell whether a pseudo reg crosses any labels. */ ! 74: ! 75: static int last_label_suid; ! 76: ! 77: /* Element N is suid of insn where life span of pseudo reg N ends. ! 78: Element is 0 if register N has not been seen yet on backward scan. */ ! 79: ! 80: static int *reg_where_dead; ! 81: ! 82: /* Element N is suid of insn where life span of pseudo reg N begins. */ ! 83: ! 84: static int *reg_where_born; ! 85: ! 86: /* Element N is 1 if pseudo reg N lives across labels or jumps. */ ! 87: ! 88: static char *reg_crosses_blocks; ! 89: ! 90: /* Numbers of pseudo-regs to be allocated, highest priority first. */ ! 91: ! 92: static int *reg_order; ! 93: ! 94: /* Indexed by reg number (hard or pseudo), nonzero if register is live ! 95: at the current point in the instruction stream. */ ! 96: ! 97: static char *regs_live; ! 98: ! 99: /* Indexed by insn's suid, the set of hard regs live after that insn. */ ! 100: ! 101: static HARD_REG_SET *after_insn_hard_regs; ! 102: ! 103: /* Record that hard reg REGNO is live after insn INSN. */ ! 104: ! 105: #define MARK_LIVE_AFTER(INSN,REGNO) \ ! 106: SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (INSN)], (REGNO)) ! 107: ! 108: static void stupid_mark_refs (); ! 109: static int stupid_reg_compare (); ! 110: static int stupid_find_reg (); ! 111: ! 112: /* Stupid life analysis is for the case where only variables declared ! 113: `register' go in registers. For this case, we mark all ! 114: pseudo-registers that belong to register variables as ! 115: dying in the last instruction of the function, and all other ! 116: pseudo registers as dying in the last place they are referenced. ! 117: Hard registers are marked as dying in the last reference before ! 118: the end or before each store into them. */ ! 119: ! 120: void ! 121: stupid_life_analysis (f, nregs, file) ! 122: rtx f; ! 123: int nregs; ! 124: FILE *file; ! 125: { ! 126: register int i; ! 127: register rtx last, insn; ! 128: int max_uid; ! 129: ! 130: bzero (regs_ever_live, sizeof regs_ever_live); ! 131: ! 132: regs_live = (char *) alloca (nregs); ! 133: ! 134: /* First find the last real insn, and count the number of insns, ! 135: and assign insns their suids. */ ! 136: ! 137: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) ! 138: if (INSN_UID (insn) > i) ! 139: i = INSN_UID (insn); ! 140: ! 141: max_uid = i + 1; ! 142: uid_suid = (int *) alloca ((i + 1) * sizeof (int)); ! 143: ! 144: /* Compute the mapping from uids to suids. ! 145: Suids are numbers assigned to insns, like uids, ! 146: except that suids increase monotonically through the code. */ ! 147: ! 148: last = 0; /* In case of empty function body */ ! 149: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) ! 150: { ! 151: if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN ! 152: || GET_CODE (insn) == JUMP_INSN) ! 153: last = insn; ! 154: INSN_SUID (insn) = ++i; ! 155: } ! 156: ! 157: last_call_suid = i + 1; ! 158: last_jump_suid = i + 1; ! 159: last_label_suid = i + 1; ! 160: ! 161: max_regno = nregs; ! 162: ! 163: /* Allocate tables to record info about regs. */ ! 164: ! 165: reg_where_dead = (int *) alloca (nregs * sizeof (int)); ! 166: bzero (reg_where_dead, nregs * sizeof (int)); ! 167: ! 168: reg_where_born = (int *) alloca (nregs * sizeof (int)); ! 169: bzero (reg_where_born, nregs * sizeof (int)); ! 170: ! 171: reg_crosses_blocks = (char *) alloca (nregs); ! 172: bzero (reg_crosses_blocks, nregs); ! 173: ! 174: reg_order = (int *) alloca (nregs * sizeof (int)); ! 175: bzero (reg_order, nregs * sizeof (int)); ! 176: ! 177: reg_renumber = (short *) oballoc (nregs * sizeof (short)); ! 178: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) ! 179: reg_renumber[i] = i; ! 180: ! 181: for (i = FIRST_VIRTUAL_REGISTER; i <= LAST_VIRTUAL_REGISTER; i++) ! 182: reg_renumber[i] = -1; ! 183: ! 184: after_insn_hard_regs = (HARD_REG_SET *) alloca (max_uid * sizeof (HARD_REG_SET)); ! 185: bzero (after_insn_hard_regs, max_uid * sizeof (HARD_REG_SET)); ! 186: ! 187: /* Allocate and zero out many data structures ! 188: that will record the data from lifetime analysis. */ ! 189: ! 190: allocate_for_life_analysis (); ! 191: ! 192: for (i = 0; i < max_regno; i++) ! 193: { ! 194: reg_n_deaths[i] = 1; ! 195: } ! 196: ! 197: bzero (regs_live, nregs); ! 198: ! 199: /* Find where each pseudo register is born and dies, ! 200: by scanning all insns from the end to the start ! 201: and noting all mentions of the registers. ! 202: ! 203: Also find where each hard register is live ! 204: and record that info in after_insn_hard_regs. ! 205: regs_live[I] is 1 if hard reg I is live ! 206: at the current point in the scan. */ ! 207: ! 208: for (insn = last; insn; insn = PREV_INSN (insn)) ! 209: { ! 210: register HARD_REG_SET *p = after_insn_hard_regs + INSN_SUID (insn); ! 211: ! 212: /* Copy the info in regs_live ! 213: into the element of after_insn_hard_regs ! 214: for the current position in the rtl code. */ ! 215: ! 216: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) ! 217: if (regs_live[i]) ! 218: SET_HARD_REG_BIT (*p, i); ! 219: ! 220: /* Mark all call-clobbered regs as live after each call insn ! 221: so that a pseudo whose life span includes this insn ! 222: will not go in one of them. ! 223: Then mark those regs as all dead for the continuing scan ! 224: of the insns before the call. */ ! 225: ! 226: if (GET_CODE (insn) == CALL_INSN) ! 227: { ! 228: last_call_suid = INSN_SUID (insn); ! 229: IOR_HARD_REG_SET (after_insn_hard_regs[last_call_suid], ! 230: call_used_reg_set); ! 231: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) ! 232: if (call_used_regs[i]) ! 233: regs_live[i] = 0; ! 234: } ! 235: ! 236: if (GET_CODE (insn) == JUMP_INSN) ! 237: last_jump_suid = INSN_SUID (insn); ! 238: ! 239: if (GET_CODE (insn) == CODE_LABEL) ! 240: last_label_suid = INSN_SUID (insn); ! 241: ! 242: /* Update which hard regs are currently live ! 243: and also the birth and death suids of pseudo regs ! 244: based on the pattern of this insn. */ ! 245: ! 246: if (GET_CODE (insn) == INSN ! 247: || GET_CODE (insn) == CALL_INSN ! 248: || GET_CODE (insn) == JUMP_INSN) ! 249: { ! 250: stupid_mark_refs (PATTERN (insn), insn); ! 251: } ! 252: } ! 253: ! 254: /* Now decide the order in which to allocate the pseudo registers. */ ! 255: ! 256: for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++) ! 257: reg_order[i] = i; ! 258: ! 259: qsort (®_order[LAST_VIRTUAL_REGISTER + 1], ! 260: max_regno - LAST_VIRTUAL_REGISTER - 1, sizeof (int), ! 261: stupid_reg_compare); ! 262: ! 263: /* Now, in that order, try to find hard registers for those pseudo regs. */ ! 264: ! 265: for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++) ! 266: { ! 267: register int r = reg_order[i]; ! 268: enum reg_class class; ! 269: ! 270: /* Some regnos disappear from the rtl. Ignore them to avoid crash. */ ! 271: if (regno_reg_rtx[r] == 0) ! 272: continue; ! 273: ! 274: /* Now find the best hard-register class for this pseudo register */ ! 275: if (N_REG_CLASSES > 1) ! 276: { ! 277: class = reg_preferred_class (r); ! 278: ! 279: reg_renumber[r] = stupid_find_reg (reg_n_calls_crossed[r], class, ! 280: PSEUDO_REGNO_MODE (r), ! 281: reg_where_born[r], ! 282: reg_where_dead[r], ! 283: reg_crosses_blocks[r]); ! 284: } ! 285: else ! 286: reg_renumber[r] = -1; ! 287: ! 288: /* If no reg available in that class, ! 289: try any reg. */ ! 290: if (reg_renumber[r] == -1) ! 291: reg_renumber[r] = stupid_find_reg (reg_n_calls_crossed[r], ! 292: GENERAL_REGS, ! 293: PSEUDO_REGNO_MODE (r), ! 294: reg_where_born[r], ! 295: reg_where_dead[r], ! 296: reg_crosses_blocks[r]); ! 297: } ! 298: ! 299: if (file) ! 300: dump_flow_info (file); ! 301: } ! 302: ! 303: /* Comparison function for qsort. ! 304: Returns -1 (1) if register *R1P is higher priority than *R2P. */ ! 305: ! 306: static int ! 307: stupid_reg_compare (r1p, r2p) ! 308: int *r1p, *r2p; ! 309: { ! 310: register int r1 = *r1p, r2 = *r2p; ! 311: register int len1 = reg_where_dead[r1] - reg_where_born[r1]; ! 312: register int len2 = reg_where_dead[r2] - reg_where_born[r2]; ! 313: int tem; ! 314: ! 315: tem = len2 - len1; ! 316: if (tem != 0) return tem; ! 317: ! 318: tem = reg_n_refs[r1] - reg_n_refs[r2]; ! 319: if (tem != 0) return tem; ! 320: ! 321: /* If regs are equally good, sort by regno, ! 322: so that the results of qsort leave nothing to chance. */ ! 323: return r1 - r2; ! 324: } ! 325: ! 326: /* Find a block of SIZE words of hard registers in reg_class CLASS ! 327: that can hold a value of machine-mode MODE ! 328: (but actually we test only the first of the block for holding MODE) ! 329: currently free from after insn whose suid is BIRTH ! 330: through the insn whose suid is DEATH, ! 331: and return the number of the first of them. ! 332: Return -1 if such a block cannot be found. ! 333: ! 334: If CALL_PRESERVED is nonzero, insist on registers preserved ! 335: over subroutine calls, and return -1 if cannot find such. ! 336: If CROSSES_BLOCKS is nonzero, reject registers for which ! 337: PRESERVE_DEATH_INFO_REGNO_P is true. */ ! 338: ! 339: static int ! 340: stupid_find_reg (call_preserved, class, mode, ! 341: born_insn, dead_insn, crosses_blocks) ! 342: int call_preserved; ! 343: enum reg_class class; ! 344: enum machine_mode mode; ! 345: int born_insn, dead_insn; ! 346: int crosses_blocks; ! 347: { ! 348: register int i, ins; ! 349: #ifdef HARD_REG_SET ! 350: register /* Declare them register if they are scalars. */ ! 351: #endif ! 352: HARD_REG_SET used, this_reg; ! 353: #ifdef ELIMINABLE_REGS ! 354: static struct {int from, to; } eliminables[] = ELIMINABLE_REGS; ! 355: #endif ! 356: ! 357: COPY_HARD_REG_SET (used, ! 358: call_preserved ? call_used_reg_set : fixed_reg_set); ! 359: ! 360: #ifdef ELIMINABLE_REGS ! 361: for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++) ! 362: SET_HARD_REG_BIT (used, eliminables[i].from); ! 363: #else ! 364: SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM); ! 365: #endif ! 366: ! 367: for (ins = born_insn; ins < dead_insn; ins++) ! 368: IOR_HARD_REG_SET (used, after_insn_hard_regs[ins]); ! 369: ! 370: IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]); ! 371: ! 372: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) ! 373: { ! 374: #ifdef REG_ALLOC_ORDER ! 375: int regno = reg_alloc_order[i]; ! 376: #else ! 377: int regno = i; ! 378: #endif ! 379: ! 380: /* If we need reasonable death info on this hard reg, ! 381: don't use it for anything whose life spans a label or a jump. */ ! 382: #ifdef PRESERVE_DEATH_INFO_REGNO_P ! 383: if (PRESERVE_DEATH_INFO_REGNO_P (regno) ! 384: && crosses_blocks) ! 385: continue; ! 386: #endif ! 387: /* If a register has screwy overlap problems, ! 388: don't use it at all if not optimizing. ! 389: Actually this is only for the 387 stack register, ! 390: and it's because subsequent code won't work. */ ! 391: #ifdef OVERLAPPING_REGNO_P ! 392: if (OVERLAPPING_REGNO_P (regno)) ! 393: continue; ! 394: #endif ! 395: ! 396: if (! TEST_HARD_REG_BIT (used, regno) ! 397: && HARD_REGNO_MODE_OK (regno, mode)) ! 398: { ! 399: register int j; ! 400: register int size1 = HARD_REGNO_NREGS (regno, mode); ! 401: for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++); ! 402: if (j == size1) ! 403: { ! 404: CLEAR_HARD_REG_SET (this_reg); ! 405: while (--j >= 0) ! 406: SET_HARD_REG_BIT (this_reg, regno + j); ! 407: for (ins = born_insn; ins < dead_insn; ins++) ! 408: { ! 409: IOR_HARD_REG_SET (after_insn_hard_regs[ins], this_reg); ! 410: } ! 411: return regno; ! 412: } ! 413: #ifndef REG_ALLOC_ORDER ! 414: i += j; /* Skip starting points we know will lose */ ! 415: #endif ! 416: } ! 417: } ! 418: return -1; ! 419: } ! 420: ! 421: /* Walk X, noting all assignments and references to registers ! 422: and recording what they imply about life spans. ! 423: INSN is the current insn, supplied so we can find its suid. */ ! 424: ! 425: static void ! 426: stupid_mark_refs (x, insn) ! 427: rtx x, insn; ! 428: { ! 429: register RTX_CODE code = GET_CODE (x); ! 430: register char *fmt; ! 431: register int regno, i; ! 432: ! 433: if (code == SET || code == CLOBBER) ! 434: { ! 435: if (SET_DEST (x) != 0 && GET_CODE (SET_DEST (x)) == REG) ! 436: { ! 437: /* Register is being assigned. */ ! 438: regno = REGNO (SET_DEST (x)); ! 439: ! 440: /* For hard regs, update the where-live info. */ ! 441: if (regno < FIRST_PSEUDO_REGISTER) ! 442: { ! 443: register int j ! 444: = HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x))); ! 445: while (--j >= 0) ! 446: { ! 447: regs_ever_live[regno+j] = 1; ! 448: regs_live[regno+j] = 0; ! 449: /* The following line is for unused outputs; ! 450: they do get stored even though never used again. */ ! 451: MARK_LIVE_AFTER (insn, regno); ! 452: /* When a hard reg is clobbered, mark it in use ! 453: just before this insn, so it is live all through. */ ! 454: if (code == CLOBBER && INSN_SUID (insn) > 0) ! 455: SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (insn) - 1], ! 456: regno); ! 457: } ! 458: } ! 459: /* For pseudo regs, record where born, where dead, number of ! 460: times used, and whether live across a call. */ ! 461: else ! 462: { ! 463: /* Update the life-interval bounds of this pseudo reg. */ ! 464: ! 465: /* When a pseudo-reg is CLOBBERed, it is born just before ! 466: the clobbering insn. When setting, just after. */ ! 467: int where_born = INSN_SUID (insn) - (code == CLOBBER); ! 468: ! 469: reg_where_born[regno] = where_born; ! 470: /* The reg must live at least one insn even ! 471: in it is never again used--because it has to go ! 472: in SOME hard reg. Mark it as dying after the current ! 473: insn so that it will conflict with any other outputs of ! 474: this insn. */ ! 475: if (reg_where_dead[regno] < where_born + 2) ! 476: reg_where_dead[regno] = where_born + 2; ! 477: ! 478: /* Count the refs of this reg. */ ! 479: reg_n_refs[regno]++; ! 480: ! 481: if (last_call_suid < reg_where_dead[regno]) ! 482: reg_n_calls_crossed[regno] += 1; ! 483: if (last_jump_suid < reg_where_dead[regno] ! 484: || last_label_suid < reg_where_dead[regno]) ! 485: reg_crosses_blocks[regno] = 1; ! 486: } ! 487: } ! 488: /* Record references from the value being set, ! 489: or from addresses in the place being set if that's not a reg. ! 490: If setting a SUBREG, we treat the entire reg as *used*. */ ! 491: if (code == SET) ! 492: { ! 493: stupid_mark_refs (SET_SRC (x), insn); ! 494: if (GET_CODE (SET_DEST (x)) != REG) ! 495: stupid_mark_refs (SET_DEST (x), insn); ! 496: } ! 497: return; ! 498: } ! 499: ! 500: /* Register value being used, not set. */ ! 501: ! 502: if (code == REG) ! 503: { ! 504: regno = REGNO (x); ! 505: if (regno < FIRST_PSEUDO_REGISTER) ! 506: { ! 507: /* Hard reg: mark it live for continuing scan of previous insns. */ ! 508: register int j = HARD_REGNO_NREGS (regno, GET_MODE (x)); ! 509: while (--j >= 0) ! 510: { ! 511: regs_ever_live[regno+j] = 1; ! 512: regs_live[regno+j] = 1; ! 513: } ! 514: } ! 515: else ! 516: { ! 517: /* Pseudo reg: record first use, last use and number of uses. */ ! 518: ! 519: reg_where_born[regno] = INSN_SUID (insn); ! 520: reg_n_refs[regno]++; ! 521: if (regs_live[regno] == 0) ! 522: { ! 523: regs_live[regno] = 1; ! 524: reg_where_dead[regno] = INSN_SUID (insn); ! 525: } ! 526: } ! 527: return; ! 528: } ! 529: ! 530: /* Recursive scan of all other rtx's. */ ! 531: ! 532: fmt = GET_RTX_FORMAT (code); ! 533: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) ! 534: { ! 535: if (fmt[i] == 'e') ! 536: stupid_mark_refs (XEXP (x, i), insn); ! 537: if (fmt[i] == 'E') ! 538: { ! 539: register int j; ! 540: for (j = XVECLEN (x, i) - 1; j >= 0; j--) ! 541: stupid_mark_refs (XVECEXP (x, i, j), insn); ! 542: } ! 543: } ! 544: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.