So what addIntervalsToSpills returns are new intervals to allocate with infinite weights, right? And I need not to allocate the old interval. Should hasStackSlot return true on its register then? On 8/21/06, Fernando Magno Quintao Pereira <fernando at cs.ucla.edu> wrote:> > > Well, someone correct me if am wrong, but, you still have to allocate > physical registers to them, because their values must be reloaded before > been used. But after you spill a register, you break its live ranges, so, > each use of that register can be loaded into a different physical. In my > register allocator, after I spill reg_v: > > For each use of reg_v: > create a new reg_v' > replace reg_v by reg_v' > > If the instruction containing reg_v' hasn't been scanned by the register > allocator, when it happens, reg_v' will receive a physical register. You > must assign to reg_v' a weight such that is is not spilled again, > otherwise you may enter on an infinite loop, always spilling the same > spilled register. > > Fernando > > > > > So, as far as I understood live intervals with weight equal to HUGE_VAL > are > > spilled and I don't need to allocate physical registers for them, right? > > Shoud hasStackSlot method of VirtRegMap return true for these intervals' > reg > > members? > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Nae king! Nae quin! Nae laird! Nae master! We willnae be fooled again! -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20060821/1c8f5715/attachment.html>
Fernando Magno Quintao Pereira
2006-Aug-21 19:03 UTC
[LLVMdev] Recalculating live intervals
> So what addIntervalsToSpills returns are new intervals to allocate with > infinite weights, right? > And I need not to allocate the old interval. Should hasStackSlot return true > on its register then? >I am not very sure about addIntervalsToSpill, but, for all the registers created to replace a spilled registers, they must have a stack slot assigned to them. I am sending you my spilling method, so you can have an example: //===-------------------------------------------------------------------------- // This method performs register spilling. The parameter indicates a class of // registers. The spilling algorithm must evict a register from the same class // as the parameter. I am using the VirtRegMap class to place loads and stores. //===-------------------------------------------------------------------------- void RegAllocChordal_Fer::spill( unsigned v_reg, KillingSites_Fer & ks, const MachineBasicBlock & mbb ) { // First, find a place to store this register. Of course, this will be done // by the implementation of vrm. We just have to ask it. int slot = vrm->assignVirt2StackSlot(v_reg); unsigned p_reg = this->reg_mapping->get_physical_location(v_reg); // Now, it is necessary to break the live range of the spilled register. // This is done by creating new virtual registers, and substituting the // spilled register by the new registers. MachineInstr * last_seen; std::vector< MachineInstr * > & use_sites this->def_use_sites->get_use_sites(v_reg); for(unsigned u = 0; u < use_sites.size(); u++) { MachineInstr * mi = use_sites[u]; if(mi == last_seen) { continue; // this happens when the same virtual is used multiple // times in the same instruction. } unsigned new_reg = create_new_virtual_register(v_reg); if(mi->getParent()->getNumber() =ks.get_basic_block()->getNumber()) { ks.replace_used_reg(mi, new_reg, v_reg); } this->vrm->grow(); this->reg_mapping->grow(); this->vrm->assignVirt2StackSlot(new_reg, slot); for(unsigned t = 0; t < mi->getNumOperands(); t++) { MachineOperand & mo_aux = mi->getOperand(t); if(mo_aux.isRegister() && mo_aux.getReg() && mo_aux.isUse()) { if(mo_aux.getReg() == v_reg) { mo_aux.setReg(new_reg); this->reg_mapping->set_color_spilled_register (new_reg, p_reg); } } } last_seen = mi; } // this method will clean the machine register, e.g. p_reg, that is been // currently used to hold the color of v_reg. this->reg_mapping->liberate_color(p_reg); clean_live_range(ks, v_reg, mbb); }
I'm not sure about one thing: you assign stack slot to each new register you replace the spilled one with. And then you need to allocate physical registers to them. Is it possible to assign physical register to the virtual one which has a stack slot already? On 8/21/06, Fernando Magno Quintao Pereira <fernando at cs.ucla.edu> wrote:> > > > So what addIntervalsToSpills returns are new intervals to allocate with > > infinite weights, right? > > And I need not to allocate the old interval. Should hasStackSlot return > true > > on its register then? > > > > I am not very sure about addIntervalsToSpill, but, for all the registers > created to replace a spilled registers, they must have a stack slot > assigned to them. I am sending you my spilling method, so you can have an > example: > > > //===-------------------------------------------------------------------------- > // This method performs register spilling. The parameter indicates a class > of > // registers. The spilling algorithm must evict a register from the same > class > // as the parameter. I am using the VirtRegMap class to place loads and > stores. > > //===-------------------------------------------------------------------------- > void RegAllocChordal_Fer::spill( > unsigned v_reg, > KillingSites_Fer & ks, > const MachineBasicBlock & mbb > ) { > // First, find a place to store this register. Of course, this will be > done > // by the implementation of vrm. We just have to ask it. > int slot = vrm->assignVirt2StackSlot(v_reg); > unsigned p_reg = this->reg_mapping->get_physical_location(v_reg); > > // Now, it is necessary to break the live range of the spilled > register. > // This is done by creating new virtual registers, and substituting > the > // spilled register by the new registers. > MachineInstr * last_seen; > std::vector< MachineInstr * > & use_sites > > this->def_use_sites->get_use_sites(v_reg); > for(unsigned u = 0; u < use_sites.size(); u++) { > MachineInstr * mi = use_sites[u]; > if(mi == last_seen) { > continue; // this happens when the same virtual is used > multiple > // times in the same instruction. > } > unsigned new_reg = create_new_virtual_register(v_reg); > if(mi->getParent()->getNumber() => ks.get_basic_block()->getNumber()) { > ks.replace_used_reg(mi, new_reg, v_reg); > } > this->vrm->grow(); > this->reg_mapping->grow(); > this->vrm->assignVirt2StackSlot(new_reg, slot); > for(unsigned t = 0; t < mi->getNumOperands(); t++) { > MachineOperand & mo_aux = mi->getOperand(t); > if(mo_aux.isRegister() && mo_aux.getReg() && mo_aux.isUse()) { > if(mo_aux.getReg() == v_reg) { > mo_aux.setReg(new_reg); > this->reg_mapping->set_color_spilled_register > (new_reg, > p_reg); > } > } > } > last_seen = mi; > } > > // this method will clean the machine register, e.g. p_reg, that is > been > // currently used to hold the color of v_reg. > this->reg_mapping->liberate_color(p_reg); > > clean_live_range(ks, v_reg, mbb); > } > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Nae king! Nae quin! Nae laird! Nae master! We willnae be fooled again! -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20060822/d6f2cc53/attachment.html>