reg_alloc2.c

unix下调试内存泄露的工具源代码

      rreg_lrs[rreg_lrs_used].rreg        = available_real_regs[j];
      rreg_lrs[rreg_lrs_used].live_after  = toShort(rreg_live_after[j]);
      rreg_lrs[rreg_lrs_used].dead_before = toShort(rreg_dead_before[j]);
      rreg_lrs_used++;
   }

   /* Compute summary hints for choosing real regs.  If a real reg is
      involved in a hard live range, record that fact in the fixed
      part of the running rreg_state.  Later, when offered a choice between
      rregs, it's better to choose one which is not marked as having
      any HLRs, since ones with HLRs may need to be spilled around
      their HLRs.  Correctness of final assignment is unaffected by
      this mechanism -- it is only an optimisation. */

   for (j = 0; j < rreg_lrs_used; j++) {
      rreg = rreg_lrs[j].rreg;
      vassert(!hregIsVirtual(rreg));
      /* rreg is involved in a HLR.  Record this info in the array, if
         there is space. */
      for (k = 0; k < n_rregs; k++)
         if (rreg_state[k].rreg == rreg)
            break;
      vassert(k < n_rregs); /* else rreg was not found in rreg_state?! */
      rreg_state[k].has_hlrs = True;
   }
   if (0) {
      for (j = 0; j < n_rregs; j++) {
         if (!rreg_state[j].has_hlrs)
            continue;
         ppReg(rreg_state[j].rreg);
         vex_printf(" hinted\n");
      }
   }

   /* ------ end of FINALISE RREG LIVE RANGES ------ */

#  if DEBUG_REGALLOC
   for (j = 0; j < n_vregs; j++) {
      vex_printf("vreg %d:  la = %d,  db = %d\n", 
                 j, vreg_lrs[j].live_after, vreg_lrs[j].dead_before );
   }
#  endif

#  if DEBUG_REGALLOC
   for (j = 0; j < rreg_lrs_used; j++) {
      (*ppReg)(rreg_lrs[j].rreg);
      vex_printf("      la = %d,  db = %d\n",
                 rreg_lrs[j].live_after, rreg_lrs[j].dead_before );
   }
#  endif

   /* --------- Stage 3: allocate spill slots. --------- */

   /* Each spill slot is 8 bytes long.  For 128-bit vregs
      we have to allocate two spill slots.

      Do a rank-based allocation of vregs to spill slot numbers.  We
      put as few values as possible in spill slows, but nevertheless
      need to have a spill slot available for all vregs, just in case.
   */
   /* max_ss_no = -1; */

   for (j = 0; j < N_SPILL64S; j++)
      ss_busy_until_before[j] = 0;

   for (j = 0; j < n_vregs; j++) {

      /* True iff this vreg is unused.  In which case we also expect
         that the reg_class field for it has not been set.  */
      if (vreg_lrs[j].live_after == INVALID_INSTRNO) {
         vassert(vreg_lrs[j].reg_class == HRcINVALID);
         continue;
      }

      /* The spill slots are 64 bits in size.  That means, to spill a
         Vec128-class vreg, we'll need to find two adjacent spill
         slots to use.  Note, this special-casing needs to happen for
         all 128-bit sized register classes.  Currently though
         HRcVector is the only such class. */

      if (vreg_lrs[j].reg_class != HRcVec128) {

         /* The ordinary case -- just find a single spill slot. */

         /* Find the lowest-numbered spill slot which is available at
            the start point of this interval, and assign the interval
            to it. */
         for (k = 0; k < N_SPILL64S; k++)
            if (ss_busy_until_before[k] <= vreg_lrs[j].live_after)
               break;
         if (k == N_SPILL64S) {
            vpanic("LibVEX_N_SPILL_BYTES is too low.  " 
                   "Increase and recompile.");
         }
         ss_busy_until_before[k] = vreg_lrs[j].dead_before;

      } else {

	/* Find two adjacent free slots in which to spill a 128-bit
           vreg. */

         for (k = 0; k < N_SPILL64S-1; k++)
            if (ss_busy_until_before[k] <= vreg_lrs[j].live_after
                && ss_busy_until_before[k+1] <= vreg_lrs[j].live_after)
               break;
         if (k == N_SPILL64S-1) {
            vpanic("LibVEX_N_SPILL_BYTES is too low.  " 
                   "Increase and recompile.");
         }
         ss_busy_until_before[k+0] = vreg_lrs[j].dead_before;
         ss_busy_until_before[k+1] = vreg_lrs[j].dead_before;

      }

      /* This reflects LibVEX's hard-wired knowledge of the baseBlock
         layout: the guest state, then an equal sized area following
         it for shadow state, and then the spill area. */
      vreg_lrs[j].spill_offset = toShort(guest_sizeB * 2 + k * 8);

      /* if (j > max_ss_no) */
      /*    max_ss_no = j; */
   }

#  if 0
   vex_printf("\n\n");
   for (j = 0; j < n_vregs; j++)
      vex_printf("vreg %d    --> spill offset %d\n",
                 j, vreg_lrs[j].spill_offset);
#  endif

   /* --------- Stage 4: establish rreg preferences --------- */

   /* It may be advantageous to allocating certain vregs to specific
      rregs, as a way of avoiding reg-reg moves later.  Here we
      establish which, if any, rreg each vreg would prefer to be in.
      Note that this constrains the allocator -- ideally we end up
      with as few as possible vregs expressing a preference.  

      This is an optimisation: if the .preferred_rreg field is never
      set to anything different from INVALID_HREG, the allocator still
      works. */

   /* 30 Dec 04: removed this mechanism as it does not seem to
      help. */

   /* --------- Stage 5: process instructions --------- */

   /* This is the main loop of the allocator.  First, we need to
      correctly set up our running state, which tracks the status of
      each real register. */

   /* ------ BEGIN: Process each insn in turn. ------ */

   for (ii = 0; ii < instrs_in->arr_used; ii++) {

#     if DEBUG_REGALLOC
      vex_printf("\n====----====---- Insn %d ----====----====\n", ii);
      vex_printf("---- ");
      (*ppInstr)(instrs_in->arr[ii]);
      vex_printf("\n\nInitial state:\n");
      PRINT_STATE;
      vex_printf("\n");
#     endif

      /* ------------ Sanity checks ------------ */

      /* Sanity checks are expensive.  So they are done only once
         every 7 instructions, and just before the last
         instruction. */
      do_sanity_check
         = toBool(
              False  /* Set to True for sanity checking of all insns. */
              || ii == instrs_in->arr_used-1
              || (ii > 0 && (ii % 7) == 0)
           );

      if (do_sanity_check) {

         /* Sanity check 1: all rregs with a hard live range crossing
            this insn must be marked as unavailable in the running
            state. */
         for (j = 0; j < rreg_lrs_used; j++) {
            if (rreg_lrs[j].live_after < ii 
                && ii < rreg_lrs[j].dead_before) {
               /* ii is the middle of a hard live range for some real
                  reg.  Check it's marked as such in the running
                  state. */

#              if 0
               vex_printf("considering la %d .. db %d   reg = ", 
                          rreg_lrs[j].live_after, 
                          rreg_lrs[j].dead_before);
               (*ppReg)(rreg_lrs[j].rreg);
               vex_printf("\n");
#              endif

               /* find the state entry for this rreg */
               for (k = 0; k < n_rregs; k++)
                  if (rreg_state[k].rreg == rreg_lrs[j].rreg)
                     break;

               /* and assert that this rreg is marked as unavailable */
               vassert(rreg_state[k].disp == Unavail);
            }
         }

         /* Sanity check 2: conversely, all rregs marked as
            unavailable in the running rreg_state must have a
            corresponding hard live range entry in the rreg_lrs
            array. */
         for (j = 0; j < n_available_real_regs; j++) {
            vassert(rreg_state[j].disp == Bound
                    || rreg_state[j].disp == Free
                    || rreg_state[j].disp == Unavail);
            if (rreg_state[j].disp != Unavail)
               continue;
            for (k = 0; k < rreg_lrs_used; k++) 
               if (rreg_lrs[k].rreg == rreg_state[j].rreg
                   && rreg_lrs[k].live_after < ii 
                   && ii < rreg_lrs[k].dead_before) 
                  break;
            /* If this vassertion fails, we couldn't find a
               corresponding HLR. */
            vassert(k < rreg_lrs_used);
         }

         /* Sanity check 3: all vreg-rreg bindings must bind registers
            of the same class. */
         for (j = 0; j < n_rregs; j++) {
            if (rreg_state[j].disp != Bound)
               continue;
            vassert(hregClass(rreg_state[j].rreg) 
                    == hregClass(rreg_state[j].vreg));
            vassert( hregIsVirtual(rreg_state[j].vreg));
            vassert(!hregIsVirtual(rreg_state[j].rreg));
         }

         /* Sanity check 4: the vreg_state and rreg_state
            mutually-redundant mappings are consistent.  If
            rreg_state[j].vreg points at some vreg_state entry then
            that vreg_state entry should point back at
            rreg_state[j]. */
         for (j = 0; j < n_rregs; j++) {
            if (rreg_state[j].disp != Bound)
               continue;
            k = hregNumber(rreg_state[j].vreg);
            vassert(IS_VALID_VREGNO(k));
            vassert(vreg_state[k] == j);
         }
         for (j = 0; j < n_vregs; j++) {
            k = vreg_state[j];
            if (k == INVALID_RREG_NO)
               continue;
            vassert(IS_VALID_RREGNO(k));
            vassert(rreg_state[k].disp == Bound);
            vassert(hregNumber(rreg_state[k].vreg) == j);
         }

      } /* if (do_sanity_check) */

      /* ------------ end of Sanity checks ------------ */

      /* Do various optimisations pertaining to register coalescing
         and preferencing:
            MOV  v <-> v   coalescing (done here).
            MOV  v <-> r   coalescing (not yet, if ever)
      */
      /* If doing a reg-reg move between two vregs, and the src's live
         range ends here and the dst's live range starts here, bind
         the dst to the src's rreg, and that's all. */
      if ( (*isMove)( instrs_in->arr[ii], &vregS, &vregD ) ) {
         if (!hregIsVirtual(vregS)) goto cannot_coalesce;
         if (!hregIsVirtual(vregD)) goto cannot_coalesce;
         /* Check that *isMove is not telling us a bunch of lies ... */
         vassert(hregClass(vregS) == hregClass(vregD));
         k = hregNumber(vregS);
         m = hregNumber(vregD);
         vassert(IS_VALID_VREGNO(k));
         vassert(IS_VALID_VREGNO(m));
         if (vreg_lrs[k].dead_before != ii + 1) goto cannot_coalesce;
         if (vreg_lrs[m].live_after != ii) goto cannot_coalesce;
#        if DEBUG_REGALLOC
         vex_printf("COALESCE ");
         (*ppReg)(vregS);
         vex_printf(" -> ");
         (*ppReg)(vregD);
         vex_printf("\n\n");
#        endif
         /* Find the state entry for vregS. */
         for (m = 0; m < n_rregs; m++)
            if (rreg_state[m].disp == Bound && rreg_state[m].vreg == vregS)
               break;
         if (m == n_rregs)
            /* We failed to find a binding for vregS, which means it's
               currently not in a register.  So we can't do the
               coalescing.  Give up. */
            goto cannot_coalesce;

         /* Finally, we can do the coalescing.  It's trivial -- merely
            claim vregS's register for vregD. */
         rreg_state[m].vreg = vregD;
         vassert(IS_VALID_VREGNO(hregNumber(vregD)));
         vassert(IS_VALID_VREGNO(hregNumber(vregS)));
         vreg_state[hregNumber(vregD)] = toShort(m);
         vreg_state[hregNumber(vregS)] = INVALID_RREG_NO;

         /* Move on to the next insn.  We skip the post-insn stuff for
            fixed registers, since this move should not interact with
            them in any way. */
         continue;
      }
     cannot_coalesce:

      /* ------ Free up rregs bound to dead vregs ------ */