MBB Critical edges

Hi all,

     I have a pass to break critical edges of Machine Basic Blocks, but I just discovered a bug (when compiling code for x86). The problem is 'jumpl *%reg'. I don't know how to update the jump table for this type of instruction. The code that I had (see below) does not update the jump table, and the actual branch keeps jumping to the old basic block, instead of the new. Could someone help me to fix this? If it works fine, I can send a patch for this pass.

     /// modify every branch in src that points to dst to point
     /// to the new machine basic block "crit_mbb" instead:
     MachineBasicBlock::iterator mii = src.end();
     bool found_branch = false;
     while (mii != src.begin()) {
         mii--;
         // if there are no more branches, finish the loop
         if (!tii->isTerminatorInstr(mii->getOpcode())) {
             break;
         }
         // Scan the operands of this branch, replacing any
         // uses of dst with crit_mbb.
         for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
             if (mii->getOperand(i).isMachineBasicBlock() &&
                  mii->getOperand(i).getMachineBasicBlock() == & dst) {
                 found_branch = true;
                 mii->getOperand(i).setMachineBasicBlock(crit_mbb);
             }
         }
     }

Thanks a lot,

Fernando

Sorry about the tardiness of my reply. My mail client has playing tricks with me. :slight_smile:

I am assuming the issue has nothing to do the branch to jumptable instructions but rather the MachineJumpTableInfo associated with every MachineFunction? If so, please take a look at BranchFoldiing.cpp for an example.

Evan

Thanks, Evan.

     Actually I've solved my problem with some hints from Dale and Anton. At least I think I've solved it. I had to add one method to TargetInstrInfo to tell me when an instruction is an indirect jump - TargetInstrInfo::tii.isIndirectJump(opcode). When that is the case, I update the jump table using:

     // Change jumps to go to the new basic block:
     if(isJumpTable) {
         mf.getJumpTableInfo()->ReplaceMBBInJumpTables(& dst, crit_mbb);
     }

where dst was the old basic block, and crit_mbb is the new one, created to remove a critical edge. I think this should solve the problem. If you want, I can give you the pass to break critical edges of machine blocks, so that you guys can see if it is worth adding to LLVM's main branch. Up to now, as far as I know, there is no pass to remove critical edges of machine functions in LLVM.

By the way, with this change, my register allocator is passing all the tests that LLVM with default RA (linearscan) is passing, although I am still using LLVM v1.8.

best,

Fernando

Thanks, Evan.

     Actually I've solved my problem with some hints from Dale and Anton.

Ok, cool. I didn't see their replies. Like I said, my email client is acting funny.

At least I think I've solved it. I had to add one method to
TargetInstrInfo to tell me when an instruction is an indirect jump -
TargetInstrInfo::tii.isIndirectJump(opcode). When that is the case, I
update the jump table using:

     // Change jumps to go to the new basic block:
     if(isJumpTable) {
         mf.getJumpTableInfo()->ReplaceMBBInJumpTables(& dst, crit_mbb);
     }

where dst was the old basic block, and crit_mbb is the new one, created to
remove a critical edge. I think this should solve the problem. If you
want, I can give you the pass to break critical edges of machine blocks,
so that you guys can see if it is worth adding to LLVM's main branch. Up
to now, as far as I know, there is no pass to remove critical edges of
machine functions in LLVM.

Can you explain briefly what it does? What benefits do you expect?

By the way, with this change, my register allocator is passing all the
tests that LLVM with default RA (linearscan) is passing, although I am
still using LLVM v1.8.

Very nice. Does this include all the external tests (specs, etc.)? Is it possible for you to move to tot?

Evan

By the way, with this change, my register allocator is passing all the
tests that LLVM with default RA (linearscan) is passing, although I am
still using LLVM v1.8.

Very nice. Does this include all the external tests (specs, etc.)? Is
it possible for you to move to tot?

It includes SPEC2000 and the benchmarks in the LLVM test suite (over 250 benchmarks). But my LLVM is not compiling gap or gcc from SPEC correctly, even using the default algorithm.

Fernando