|
|
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 monotonically 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: #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM ! 364: SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM); ! 365: #endif ! 366: #else ! 367: SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM); ! 368: #endif ! 369: ! 370: for (ins = born_insn; ins < dead_insn; ins++) ! 371: IOR_HARD_REG_SET (used, after_insn_hard_regs[ins]); ! 372: ! 373: IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]); ! 374: ! 375: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) ! 376: { ! 377: #ifdef REG_ALLOC_ORDER ! 378: int regno = reg_alloc_order[i]; ! 379: #else ! 380: int regno = i; ! 381: #endif ! 382: ! 383: /* If we need reasonable death info on this hard reg, ! 384: don't use it for anything whose life spans a label or a jump. */ ! 385: #ifdef PRESERVE_DEATH_INFO_REGNO_P ! 386: if (PRESERVE_DEATH_INFO_REGNO_P (regno) ! 387: && crosses_blocks) ! 388: continue; ! 389: #endif ! 390: /* If a register has screwy overlap problems, ! 391: don't use it at all if not optimizing. ! 392: Actually this is only for the 387 stack register, ! 393: and it's because subsequent code won't work. */ ! 394: #ifdef OVERLAPPING_REGNO_P ! 395: if (OVERLAPPING_REGNO_P (regno)) ! 396: continue; ! 397: #endif ! 398: ! 399: if (! TEST_HARD_REG_BIT (used, regno) ! 400: && HARD_REGNO_MODE_OK (regno, mode)) ! 401: { ! 402: register int j; ! 403: register int size1 = HARD_REGNO_NREGS (regno, mode); ! 404: for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++); ! 405: if (j == size1) ! 406: { ! 407: CLEAR_HARD_REG_SET (this_reg); ! 408: while (--j >= 0) ! 409: SET_HARD_REG_BIT (this_reg, regno + j); ! 410: for (ins = born_insn; ins < dead_insn; ins++) ! 411: { ! 412: IOR_HARD_REG_SET (after_insn_hard_regs[ins], this_reg); ! 413: } ! 414: return regno; ! 415: } ! 416: #ifndef REG_ALLOC_ORDER ! 417: i += j; /* Skip starting points we know will lose */ ! 418: #endif ! 419: } ! 420: } ! 421: return -1; ! 422: } ! 423: ! 424: /* Walk X, noting all assignments and references to registers ! 425: and recording what they imply about life spans. ! 426: INSN is the current insn, supplied so we can find its suid. */ ! 427: ! 428: static void ! 429: stupid_mark_refs (x, insn) ! 430: rtx x, insn; ! 431: { ! 432: register RTX_CODE code = GET_CODE (x); ! 433: register char *fmt; ! 434: register int regno, i; ! 435: ! 436: if (code == SET || code == CLOBBER) ! 437: { ! 438: if (SET_DEST (x) != 0 && GET_CODE (SET_DEST (x)) == REG) ! 439: { ! 440: /* Register is being assigned. */ ! 441: regno = REGNO (SET_DEST (x)); ! 442: ! 443: /* For hard regs, update the where-live info. */ ! 444: if (regno < FIRST_PSEUDO_REGISTER) ! 445: { ! 446: register int j ! 447: = HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x))); ! 448: while (--j >= 0) ! 449: { ! 450: regs_ever_live[regno+j] = 1; ! 451: regs_live[regno+j] = 0; ! 452: /* The following line is for unused outputs; ! 453: they do get stored even though never used again. */ ! 454: MARK_LIVE_AFTER (insn, regno); ! 455: /* When a hard reg is clobbered, mark it in use ! 456: just before this insn, so it is live all through. */ ! 457: if (code == CLOBBER && INSN_SUID (insn) > 0) ! 458: SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (insn) - 1], ! 459: regno); ! 460: } ! 461: } ! 462: /* For pseudo regs, record where born, where dead, number of ! 463: times used, and whether live across a call. */ ! 464: else ! 465: { ! 466: /* Update the life-interval bounds of this pseudo reg. */ ! 467: ! 468: /* When a pseudo-reg is CLOBBERed, it is born just before ! 469: the clobbering insn. When setting, just after. */ ! 470: int where_born = INSN_SUID (insn) - (code == CLOBBER); ! 471: ! 472: reg_where_born[regno] = where_born; ! 473: /* The reg must live at least one insn even ! 474: in it is never again used--because it has to go ! 475: in SOME hard reg. Mark it as dying after the current ! 476: insn so that it will conflict with any other outputs of ! 477: this insn. */ ! 478: if (reg_where_dead[regno] < where_born + 2) ! 479: reg_where_dead[regno] = where_born + 2; ! 480: ! 481: /* Count the refs of this reg. */ ! 482: reg_n_refs[regno]++; ! 483: ! 484: if (last_call_suid < reg_where_dead[regno]) ! 485: reg_n_calls_crossed[regno] += 1; ! 486: if (last_jump_suid < reg_where_dead[regno] ! 487: || last_label_suid < reg_where_dead[regno]) ! 488: reg_crosses_blocks[regno] = 1; ! 489: } ! 490: } ! 491: /* Record references from the value being set, ! 492: or from addresses in the place being set if that's not a reg. ! 493: If setting a SUBREG, we treat the entire reg as *used*. */ ! 494: if (code == SET) ! 495: { ! 496: stupid_mark_refs (SET_SRC (x), insn); ! 497: if (GET_CODE (SET_DEST (x)) != REG) ! 498: stupid_mark_refs (SET_DEST (x), insn); ! 499: } ! 500: return; ! 501: } ! 502: ! 503: /* Register value being used, not set. */ ! 504: ! 505: if (code == REG) ! 506: { ! 507: regno = REGNO (x); ! 508: if (regno < FIRST_PSEUDO_REGISTER) ! 509: { ! 510: /* Hard reg: mark it live for continuing scan of previous insns. */ ! 511: register int j = HARD_REGNO_NREGS (regno, GET_MODE (x)); ! 512: while (--j >= 0) ! 513: { ! 514: regs_ever_live[regno+j] = 1; ! 515: regs_live[regno+j] = 1; ! 516: } ! 517: } ! 518: else ! 519: { ! 520: /* Pseudo reg: record first use, last use and number of uses. */ ! 521: ! 522: reg_where_born[regno] = INSN_SUID (insn); ! 523: reg_n_refs[regno]++; ! 524: if (regs_live[regno] == 0) ! 525: { ! 526: regs_live[regno] = 1; ! 527: reg_where_dead[regno] = INSN_SUID (insn); ! 528: } ! 529: } ! 530: return; ! 531: } ! 532: ! 533: /* Recursive scan of all other rtx's. */ ! 534: ! 535: fmt = GET_RTX_FORMAT (code); ! 536: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) ! 537: { ! 538: if (fmt[i] == 'e') ! 539: stupid_mark_refs (XEXP (x, i), insn); ! 540: if (fmt[i] == 'E') ! 541: { ! 542: register int j; ! 543: for (j = XVECLEN (x, i) - 1; j >= 0; j--) ! 544: stupid_mark_refs (XVECEXP (x, i, j), insn); ! 545: } ! 546: } ! 547: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.