reg_alloc2.c

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

      /* Look for vregs whose live range has just ended, and 
	 mark the associated rreg as free. */

      for (j = 0; j < n_rregs; j++) {
         if (rreg_state[j].disp != Bound)
            continue;
         vreg = hregNumber(rreg_state[j].vreg);
         vassert(IS_VALID_VREGNO(vreg));
         if (vreg_lrs[vreg].dead_before <= ii) {
            rreg_state[j].disp = Free;
            m = hregNumber(rreg_state[j].vreg);
            vassert(IS_VALID_VREGNO(m));
            vreg_state[m] = INVALID_RREG_NO;
            if (DEBUG_REGALLOC) {
               vex_printf("free up "); 
               (*ppReg)(rreg_state[j].rreg); 
               vex_printf("\n");
            }
         }
      }

      /* ------ Pre-instruction actions for fixed rreg uses ------ */

      /* Now we have to deal with rregs which are about to be made
         live by this instruction -- in other words, are entering into
         one of their live ranges.  If any such rreg holds a vreg, we
         will have to free up the rreg.  The simplest solution which
         is correct is to spill the rreg.

         Note we could do better:
         * Could move it into some other free rreg, if one is available 

         Simplest way to do this is to iterate over the collection
         of rreg live ranges.
      */
      for (j = 0; j < rreg_lrs_used; j++) {
         if (rreg_lrs[j].live_after == ii) {
            /* rreg_lrs[j].rreg needs to be freed up.  Find 
               the associated rreg_state entry. */
            /* Note, re rreg_lrs[j].live_after == ii.  Real register
               live ranges are guaranteed to be well-formed in that
               they start with a write to the register -- Stage 2
               rejects any code not satisfying this.  So the correct
               question to ask is whether rreg_lrs[j].live_after ==
               ii, that is, whether the reg becomes live after this
               insn -- rather than before it. */
#           if DEBUG_REGALLOC
            vex_printf("need to free up rreg: ");
            (*ppReg)(rreg_lrs[j].rreg);
            vex_printf("\n\n");
#           endif
            for (k = 0; k < n_rregs; k++)
               if (rreg_state[k].rreg == rreg_lrs[j].rreg)
                  break;
            /* If this fails, we don't have an entry for this rreg.
               Which we should. */
            vassert(IS_VALID_RREGNO(k));
            m = hregNumber(rreg_state[k].vreg);
            if (rreg_state[k].disp == Bound) {
               /* Yes, there is an associated vreg.  Spill it if it's
                  still live. */
               vassert(IS_VALID_VREGNO(m));
               vreg_state[m] = INVALID_RREG_NO;
               if (vreg_lrs[m].dead_before > ii) {
                  vassert(vreg_lrs[m].reg_class != HRcINVALID);
                  EMIT_INSTR( (*genSpill)( rreg_state[k].rreg,
                                           vreg_lrs[m].spill_offset ) );
               }
            }
            rreg_state[k].disp = Unavail;
            rreg_state[k].vreg = INVALID_HREG;
         }
      }

#     if DEBUG_REGALLOC
      vex_printf("After pre-insn actions for fixed regs:\n");
      PRINT_STATE;
      vex_printf("\n");
#     endif


      /* ------ Deal with the current instruction. ------ */

      /* Finally we can begin the processing of this instruction
         itself.  The aim is to free up enough rregs for this insn.
         This may generate spill stores since we may have to evict
         some vregs currently in rregs.  Also generates spill loads.
         We also build up the final vreg->rreg mapping to be applied
         to the insn. */
      
      (*getRegUsage)( &reg_usage, instrs_in->arr[ii] );

      initHRegRemap(&remap);

      /* for each reg mentioned in the insn ... */
      for (j = 0; j < reg_usage.n_used; j++) {

         vreg = reg_usage.hreg[j];

         /* only interested in virtual registers right now. */
         if (!hregIsVirtual(vreg)) 
            continue;

#        if 0
         vex_printf("considering "); (*ppReg)(vreg); vex_printf("\n");
#        endif

         /* Now we're trying to find a rreg for "vreg".  First of all,
            if it already has an rreg assigned, we don't need to do
            anything more.  Search the current state to find out. */
         m = hregNumber(vreg);
         vassert(IS_VALID_VREGNO(m));
         k = vreg_state[m];
         if (IS_VALID_RREGNO(k)) {
            vassert(rreg_state[k].disp == Bound);
            addToHRegRemap(&remap, vreg, rreg_state[k].rreg);
            continue;
         } else {
            vassert(k == INVALID_RREG_NO);
         }

         /* No luck.  The next thing to do is see if there is a
            currently free rreg available, of the correct class.  If
            so, bag it.  NOTE, we could improve this by selecting an
            rreg for which the next live-range event is as far ahead
            as possible. */
         k_suboptimal = -1;
         for (k = 0; k < n_rregs; k++) {
            if (rreg_state[k].disp != Free
                || hregClass(rreg_state[k].rreg) != hregClass(vreg))
               continue;
            if (rreg_state[k].has_hlrs) {
               /* Well, at least we can use k_suboptimal if we really
                  have to.  Keep on looking for a better candidate. */
               k_suboptimal = k;
            } else {
               /* Found a preferable reg.  Use it. */
               k_suboptimal = -1;
               break;
            }
         }
         if (k_suboptimal >= 0)
            k = k_suboptimal;

         if (k < n_rregs) {
            rreg_state[k].disp = Bound;
            rreg_state[k].vreg = vreg;
            m = hregNumber(vreg);
            vassert(IS_VALID_VREGNO(m));
            vreg_state[m] = toShort(k);
            addToHRegRemap(&remap, vreg, rreg_state[k].rreg);
            /* Generate a reload if needed. */
            if (reg_usage.mode[j] != HRmWrite) {
               vassert(vreg_lrs[m].reg_class != HRcINVALID);
               EMIT_INSTR( (*genReload)( rreg_state[k].rreg,
                                         vreg_lrs[m].spill_offset ) );
            }
            continue;
         }

         /* Well, now we have no option but to spill a vreg.  It's
            important to make a good choice of vreg to spill, and of
            course we need to be careful not to spill a vreg which is
            needed by this insn. */

         /* First, mark in the rreg_state, those rregs which are not spill
            candidates, due to holding a vreg mentioned by this
            instruction.  Or being of the wrong class. */
         for (k = 0; k < n_rregs; k++) {
            rreg_state[k].is_spill_cand = False;
            if (rreg_state[k].disp != Bound)
               continue;
            if (hregClass(rreg_state[k].rreg) != hregClass(vreg))
               continue;
            rreg_state[k].is_spill_cand = True;
            for (m = 0; m < reg_usage.n_used; m++) {
               if (rreg_state[k].vreg == reg_usage.hreg[m]) {
                  rreg_state[k].is_spill_cand = False;
                  break;
               }
            }
         }

         /* We can choose to spill any rreg satisfying
            rreg_state[r].is_spill_cand (so to speak).  Choose r so that
            the next use of its associated vreg is as far ahead as
            possible, in the hope that this will minimise the number
            of consequent reloads required. */
         spillee
            = findMostDistantlyMentionedVReg ( 
                 getRegUsage, instrs_in, ii+1, rreg_state, n_rregs );

         if (spillee == -1) {
            /* Hmmmmm.  There don't appear to be any spill candidates.
               We're hosed. */
            vex_printf("reg_alloc: can't find a register in class: ");
            ppHRegClass(hregClass(vreg));
            vex_printf("\n");
            vpanic("reg_alloc: can't create a free register.");
         }

         /* Right.  So we're going to spill rreg_state[spillee]. */
         vassert(IS_VALID_RREGNO(spillee));
         vassert(rreg_state[spillee].disp == Bound);
         /* check it's the right class */
         vassert(hregClass(rreg_state[spillee].rreg) == hregClass(vreg));
         /* check we're not ejecting the vreg for which we are trying
            to free up a register. */
         vassert(rreg_state[spillee].vreg != vreg);

         m = hregNumber(rreg_state[spillee].vreg);
         vassert(IS_VALID_VREGNO(m));

         /* So here's the spill store.  Assert that we're spilling a
            live vreg. */
         vassert(vreg_lrs[m].dead_before > ii);
         vassert(vreg_lrs[m].reg_class != HRcINVALID);
         EMIT_INSTR( (*genSpill)( rreg_state[spillee].rreg,
                                  vreg_lrs[m].spill_offset ) );

         /* Update the rreg_state to reflect the new assignment for this
            rreg. */
         rreg_state[spillee].vreg = vreg;
         vreg_state[m] = INVALID_RREG_NO;

         m = hregNumber(vreg);
         vassert(IS_VALID_VREGNO(m));
         vreg_state[m] = toShort(spillee);

         /* Now, if this vreg is being read or modified (as opposed to
            written), we have to generate a reload for it. */
         if (reg_usage.mode[j] != HRmWrite) {
            vassert(vreg_lrs[m].reg_class != HRcINVALID);
            EMIT_INSTR( (*genReload)( rreg_state[spillee].rreg,
                                      vreg_lrs[m].spill_offset ) );
         }

         /* So after much twisting and turning, we have vreg mapped to
            rreg_state[furthest_k].rreg.  Note that in the map. */
         addToHRegRemap(&remap, vreg, rreg_state[spillee].rreg);

      } /* iterate over registers in this instruction. */

      /* We've finished clowning around with registers in this instruction.
         Three results:
         - the running rreg_state[] has been updated
         - a suitable vreg->rreg mapping for this instruction has been 
           constructed
         - spill and reload instructions may have been emitted.

        The final step is to apply the mapping to the instruction, 
        and emit that.
      */

      /* NOTE, DESTRUCTIVELY MODIFIES instrs_in->arr[ii]. */
      (*mapRegs)( &remap, instrs_in->arr[ii] );
      EMIT_INSTR( instrs_in->arr[ii] );

#     if DEBUG_REGALLOC
      vex_printf("After dealing with current insn:\n");
      PRINT_STATE;
      vex_printf("\n");
#     endif

      /* ------ Post-instruction actions for fixed rreg uses ------ */

      /* Now we need to check for rregs exiting fixed live ranges
         after this instruction, and if so mark them as free. */
      for (j = 0; j < rreg_lrs_used; j++) {
         if (rreg_lrs[j].dead_before == ii+1) {
            /* rreg_lrs[j].rreg is exiting a hard live range.  Mark
               it as such in the main rreg_state array. */
            for (k = 0; k < n_rregs; k++)
               if (rreg_state[k].rreg == rreg_lrs[j].rreg)
                  break;
            /* If this vassertion fails, we don't have an entry for
               this rreg.  Which we should. */
            vassert(k < n_rregs);
            vassert(rreg_state[k].disp == Unavail);
            rreg_state[k].disp = Free;
            rreg_state[k].vreg = INVALID_HREG;
         }
      }

#     if DEBUG_REGALLOC
      vex_printf("After post-insn actions for fixed regs:\n");
      PRINT_STATE;
      vex_printf("\n");
#     endif

   } /* iterate over insns */

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

   /* free(rreg_state); */
   /* free(rreg_lrs); */
   /* if (vreg_lrs) free(vreg_lrs); */

   /* Paranoia */
   for (j = 0; j < n_rregs; j++)
      vassert(rreg_state[j].rreg == available_real_regs[j]);

   return instrs_out;

#  undef INVALID_INSTRNO
#  undef EMIT_INSTR
#  undef PRINT_STATE
}



/*---------------------------------------------------------------*/
/*---                               host-generic/reg_alloc2.c ---*/
/*---------------------------------------------------------------*/