Folding instructions

Project Infrastructure LLVM Dev List Archives
1

Dear LLVMers,

    I am trying to fold memory operands in the way that is done in
RegAllocLocal.cpp, or in LiveIntervalAnalysis.cpp, but I am getting errors
that
I don't know how to fix. Could someone tell me which steps should I take
in order
to correctly fold memory operands? The code that I am using is:

const TargetMachine & target_machine =
this->machine_function->getTarget();
const MRegisterInfo *ri = target_machine.getRegisterInfo();
MachineInstr * fmi = ri->foldMemoryOperand(mi, u, slot);
if(fmi) {
   numFolded++;
   MachineBasicBlock * mbb = mi->getParent();
   this->vrm->virtFolded(v_reg, mi, u, fmi);
   //std::cerr << "Folding " << NeatPrint::mi2string(*mi,
*this->machine_function) << "\n";
   // TODO: see if it is not necessary to iterate
   // again on the instruction.
   return mbb->insert(mbb->erase(mi), fmi);
}

With this code, my register allocator passes many tests, but crashes in
some.
Curiously, if I uncomment the printing line, it passes some more tests.
gdb gives me
the error trace below. Could someone point me directions? I am not
deleting fmi
before the spiller runs, so, maybe I am not calling some methods from LLVM
to
indicate the folding.

Thanks a lot,

Fernando

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0x80000004
0x94abb19c in std::_Rb_tree_rebalance_for_erase ()
(gdb) where
#0 0x94abb19c in std::_Rb_tree_rebalance_for_erase ()
#1 0x0073dd40 in std::_Rb_tree<llvm::MachineInstr*,
std::pair<llvm::MachineInstr* const, std::pair<unsigned int,
llvm::VirtRegMap::ModRef> >, std::_Select1st<std::pair<llvm::MachineInstr*
const, std::pair<unsigned int, llvm::VirtRegMap::ModRef> > >,
std::less<llvm::MachineInstr*>,
std::allocator<std::pair<llvm::MachineInstr* const, std::pair<unsigned
int, llvm::VirtRegMap::ModRef> > > >::erase (this=0x8d1afcc,
__position={_M_node = 0x8d1c520}) at
/usr/include/c++/4.0.0/bits/stl_iterator_base_funcs.h:994
#2 0x0073df9c in std::_Rb_tree<llvm::MachineInstr*,
std::pair<llvm::MachineInstr* const, std::pair<unsigned int,
llvm::VirtRegMap::ModRef> >, std::_Select1st<std::pair<llvm::MachineInstr*
const, std::pair<unsigned int, llvm::VirtRegMap::ModRef> > >,
std::less<llvm::MachineInstr*>,
std::allocator<std::pair<llvm::MachineInstr* const, std::pair<unsigned
int, llvm::VirtRegMap::ModRef> > > >::erase (this=0x8d1afcc,
__first={_M_node = 0x8d1d6e0}, __last={_M_node = 0x8d1d6e0}) at
/usr/include/c++/4.0.0/bits/stl_tree.h:1073
#3 0x0073e04c in std::_Rb_tree<llvm::MachineInstr*,
std::pair<llvm::MachineInstr* const, std::pair<unsigned int,
llvm::VirtRegMap::ModRef> >, std::_Select1st<std::pair<llvm::MachineInstr*
const, std::pair<unsigned int, llvm::VirtRegMap::ModRef> > >,
std::less<llvm::MachineInstr*>,
std::allocator<std::pair<llvm::MachineInstr* const, std::pair<unsigned
int, llvm::VirtRegMap::ModRef> > > >::erase (this=0x8d1afcc,
__x=@0xbfffe57c) at /usr/include/c++/4.0.0/bits/stl_tree.h:1007
#4 0x0073e094 in std::multimap<llvm::MachineInstr*, std::pair<unsigned
int, llvm::VirtRegMap::ModRef>, std::less<llvm::MachineInstr*>,
std::allocator<std::pair<llvm::MachineInstr* const, std::pair<unsigned
int, llvm::VirtRegMap::ModRef> > > >::erase (this=0x8d1afcc,
__x=@0xbfffe57c) at /usr/include/c++/4.0.0/bits/stl_multimap.h:414
#5 0x0073e0e4 in llvm::VirtRegMap::RemoveFromFoldedVirtMap
(this=0x8d1afa0, MI=0x8b417f0) at VirtRegMap.h:145
#6 0x0019f398 in (anonymous namespace)::LocalSpiller::RewriteMBB
(this=0x8b29460, MBB=@0x8b31230, VRM=@0x8d1afa0) at VirtRegMap.cpp:715
#7 0x007435b8 in (anonymous
namespace)::LocalSpiller::runOnMachineFunction (this=0x8b29460,
MF=@0x8b2b9d0, VRM=@0x8d1afa0) at VirtRegMap.cpp:219
#8 0x00155708 in (anonymous
namespace)::RegAllocChordal_Fer::runOnMachineFunction (this=0x8b0d280,
mf=@0x8b2b9d0) at ChordalAlloc_Fernando.cpp:757
#9 0x003e5ce4 in llvm::MachineFunctionPass::runOnFunction
(this=0x8b0d280, F=@0x8b02940) at
/private/var/automount/u/gs3/fernando/Programs/ppc_llvm/include/llvm/CodeGen/MachineFunctionPass.h:38
#10 0x0086ad88 in llvm::FunctionPassManagerT::runPass (this=0x8b02360,
P=0x8b0d280, F=0x8b02940) at PassManagerT.h:795
#11 0x008892ec in llvm::PassManagerT<llvm::FTraits>::runPasses
(this=0x8b02378, M=0x8b02940, LastUserOf=@0xbfffeab8) at
PassManagerT.h:596
#12 0x0088c9b4 in llvm::PassManagerT<llvm::FTraits>::runOnUnit
(this=0x8b02378, M=0x8b02940) at PassManagerT.h:282
#13 0x0086af54 in llvm::FunctionPassManagerT::runOnFunction
(this=0x8b02360, F=@0x8b02940) at PassManagerT.h:884
#14 0x002463d4 in llvm::FunctionPass::runOnModule (this=0x8b02360,
M=@0x8b00850) at Pass.cpp:249
#15 0x0086ae8c in llvm::ModulePassManager::runPass (this=0x8b005c0,
P=0x8b02360, M=0x8b00850) at PassManagerT.h:837
#16 0x00888be4 in llvm::PassManagerT<llvm::MTraits>::runPasses
(this=0x8b005d8, M=0x8b00850, LastUserOf=@0xbfffecd8) at
PassManagerT.h:596
#17 0x0088add8 in llvm::PassManagerT<llvm::MTraits>::runOnUnit
(this=0x8b005d8, M=0x8b00850) at PassManagerT.h:282
#18 0x002450c4 in llvm::ModulePassManager::runOnModule (this=0x8b005c0,
M=@0x8b00850) at PassManagerT.h:905
#19 0x0024539c in llvm::PassManager::run (this=0xbffff388, M=@0x8b00850)
at Pass.cpp:85
#20 0x00004dd0 in main (argc=5, argv=0xbffff4dc) at llc.cpp:234

2

Hi Fernando,

It's hard to say exactly what's happening because I don't know your code (though, from the stack trace, it seems like there's some sort of memory debacle), but looking at the comment in the LiveVariableAnalysis.cpp file where it's folding memory operands, it might explain somethings better:

             // Folding the load/store can completely change the instruction in
             // unpredictable ways, rescan it from the beginning.

It's after this that it re-analyzes the operands of the machine instruction. Are you doing this?

-bw

3

Hi Fernando,

It's hard to say exactly what's happening because I don't know your
code (though, from the stack trace, it seems like there's some sort
of memory debacle), but looking at the comment in the
LiveVariableAnalysis.cpp file where it's folding memory operands, it
might explain somethings better:

             // Folding the load/store can completely change the
instruction in
             // unpredictable ways, rescan it from the beginning.

It's after this that it re-analyzes the operands of the machine
instruction. Are you doing this?

-bw

Thanks, Bill.

    I am iterating on the instruction, as linear scan does, but I am still
getting the memory error. If I print data, the error does not happen. But
I realized something important: I am not mapping virtuals to physicals
strait on VirtRegMap during the scan. I use my own data structures to
record the register assignment, and write on VirtRegMap after I am done,
on a single step. When I remove the command this->vrm->virtFolded(v_reg,
mi, u, fmi) from my code, the error does not happen. So, I think I am not
using VirtRegMap properly. It seems to me that I don't have to call this
method during the scan, because instruction operands still contain
virtuals, not physical registers, as it would be expected. Is this right?
If someone has time to look into it, I am sending the piece of code where
I reload spilled code. If I am doing something evidently wrong, I would
appreciate if someone tells me. With the comment on vrm->virtFolded, I am
passing all the tests that I have.

All the best,

Fernando

MachineInstr * RegAllocChordal_Fer::allocate_spilled_uses
                              (MachineInstr * mi, KillingSites_Fer & ks) {
  if(mi->getOpcode() != TargetInstrInfo::PHI) {
    /// This set helps to avoid allocating the same use twice. Even if a
    /// virtual is used twice or more in an instruction, it only needs one
    /// physical register.
    std::set<unsigned> seen_regs;
    for(unsigned u = 0; u < mi->getNumOperands(); u++) {
      const MachineOperand & mo = mi->getOperand(u);
      if(mo.isUse() && mo.isRegister() && mo.getReg()) {
        if(MRegisterInfo::isVirtualRegister(mo.getReg())) {
          unsigned v_reg = mo.getReg();
          if(this->vrm->hasStackSlot(v_reg)) {
            int slot = this->vrm->getStackSlot(v_reg);
            // First, try to fold the memory reference into the
            // instruction. If we can do this, we don't need to
            // insert spill code.
            const TargetMachine & target_machine =
                               this->machine_function->getTarget();
            const MRegisterInfo *ri =
                                  target_machine.getRegisterInfo();
            MachineInstr * fmi =
                                ri->foldMemoryOperand(mi, u, slot);
            if(fmi) {
              numFolded++;
              MachineBasicBlock * mbb = mi->getParent();
------> //this->vrm->virtFolded(v_reg, mi, u, fmi);
              ks.fold_inst(mi, fmi);
              // TODO: see if it is not necessary to iterate
              // again on the instruction.
              mi = mbb->insert(mbb->erase(mi), fmi);
              u = 0;
              seen_regs.clear();
              continue;
            }
            // It was not possible to fold the spill into the
            // instruction: a register must be fond.
            if(seen_regs.find(v_reg) != seen_regs.end()) {
              continue;
            } else {
              seen_regs.insert(v_reg);
            }
            unsigned p_reg = reg_mapping->get_free_register(v_reg);
            if(p_reg != RegMapping_Fer::NO_REG) {
              this->reg_mapping->allocate_color(v_reg, p_reg);
            } else {
              // unused register may conflict with this virtual, because
              // they may be pre-colored, for instance.
              unsigned p_reg = reg_mapping->get_unused_reg(v_reg);
              if(p_reg != RegMapping_Fer::NO_REG) {
                reg_mapping->allocate_color(v_reg, p_reg);
              } else {
                const MachineOperand * spill_op =
                                    choose_reg_to_spill(v_reg);
                unsigned spill_v = spill_op->getReg();
                unsigned p_reg =
                   reg_mapping->get_physical_location(spill_v);
                spill(* spill_op, ks, * mi->getParent());
                reg_mapping->allocate_color(v_reg, p_reg);
              }
            }
          }
        }
      }
    }
  }
  return mi;
}

4

I reload spilled code. If I am doing something evidently wrong, I would
appreciate if someone tells me. With the comment on vrm->virtFolded, I am
passing all the tests that I have.

I haven't had a chance to look at the code you have below, but I would guess that you are leaving a dangling pointer in some map somewhere. "foldMemoryOperand", if successful, leaves the original instruction in the program. When you delete this instruction (which is require to avoid miscompiling the program) you must inform virtregmap that you've done this, by calling 'virtFolded'. This is important, because it allows the virtregmap to remove the (about to be deleted) instruction from *its* internal maps.

If you are still getting stuck, I'd try running valgrind on llc with the bad code, it is quite good at flushing out these sorts of problems.

-Chris

MachineInstr * RegAllocChordal_Fer::allocate_spilled_uses
                             (MachineInstr * mi, KillingSites_Fer & ks) {
if(mi->getOpcode() != TargetInstrInfo::PHI) {
   /// This set helps to avoid allocating the same use twice. Even if a
   /// virtual is used twice or more in an instruction, it only needs one
   /// physical register.
   std::set<unsigned> seen_regs;
   for(unsigned u = 0; u < mi->getNumOperands(); u++) {
     const MachineOperand & mo = mi->getOperand(u);
     if(mo.isUse() && mo.isRegister() && mo.getReg()) {
       if(MRegisterInfo::isVirtualRegister(mo.getReg())) {
         unsigned v_reg = mo.getReg();
         if(this->vrm->hasStackSlot(v_reg)) {
           int slot = this->vrm->getStackSlot(v_reg);
           // First, try to fold the memory reference into the
           // instruction. If we can do this, we don't need to
           // insert spill code.
           const TargetMachine & target_machine =
                              this->machine_function->getTarget();
           const MRegisterInfo *ri =
                                 target_machine.getRegisterInfo();
           MachineInstr * fmi =
                               ri->foldMemoryOperand(mi, u, slot);
           if(fmi) {
             numFolded++;
             MachineBasicBlock * mbb = mi->getParent();
------> //this->vrm->virtFolded(v_reg, mi, u, fmi);
             ks.fold_inst(mi, fmi);
             // TODO: see if it is not necessary to iterate
             // again on the instruction.
             mi = mbb->insert(mbb->erase(mi), fmi);
             u = 0;
             seen_regs.clear();
             continue;
           }
           // It was not possible to fold the spill into the
           // instruction: a register must be fond.
           if(seen_regs.find(v_reg) != seen_regs.end()) {
             continue;
           } else {
             seen_regs.insert(v_reg);
           }
           unsigned p_reg = reg_mapping->get_free_register(v_reg);
           if(p_reg != RegMapping_Fer::NO_REG) {
             this->reg_mapping->allocate_color(v_reg, p_reg);
           } else {
             // unused register may conflict with this virtual, because
             // they may be pre-colored, for instance.
             unsigned p_reg = reg_mapping->get_unused_reg(v_reg);
             if(p_reg != RegMapping_Fer::NO_REG) {
               reg_mapping->allocate_color(v_reg, p_reg);
             } else {
               const MachineOperand * spill_op =
                                   choose_reg_to_spill(v_reg);
               unsigned spill_v = spill_op->getReg();
               unsigned p_reg =
                  reg_mapping->get_physical_location(spill_v);
               spill(* spill_op, ks, * mi->getParent());
               reg_mapping->allocate_color(v_reg, p_reg);
             }
           }
         }
       }
     }
   }
}
return mi;
}
_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-Chris

5

If you are still getting stuck, I'd try running valgrind on llc with the
bad code, it is quite good at flushing out these sorts of problems.

Thank you, Chris.

    I just tried to install valgrind, but it seems to me it does not work
on Mac OS. Do you know if it is true? Is there any valgrind like
application that I can use on Mac OS?

regards,

Fernando

6

Right, it doesn't. On macos I'd suggest using the variety of environment variables that can debug malloc, see "man malloc".

-Chris