//
//===----------------------------------------------------------------------===//
//
-// This pass does two things:
-// (1) fuse compares and branches into COMPARE AND BRANCH instructions
-// (2) make sure that all branches are in range.
-//
-// We do (1) here rather than earlier because the fused form prevents
-// predication.
-//
-// Doing it so late makes it more likely that a register will be reused
-// between the compare and the branch, but it isn't clear whether preventing
-// that would be a win or not.
-//
-// There are several ways in which (2) could be done. One aggressive
-// approach is to assume that all branches are in range and successively
-// replace those that turn out not to be in range with a longer form
-// (branch relaxation). A simple implementation is to continually walk
-// through the function relaxing branches until no more changes are
-// needed and a fixed point is reached. However, in the pathological
-// worst case, this implementation is quadratic in the number of blocks;
-// relaxing branch N can make branch N-1 go out of range, which in turn
-// can make branch N-2 go out of range, and so on.
+// This pass makes sure that all branches are in range. There are several ways
+// in which this could be done. One aggressive approach is to assume that all
+// branches are in range and successively replace those that turn out not
+// to be in range with a longer form (branch relaxation). A simple
+// implementation is to continually walk through the function relaxing
+// branches until no more changes are needed and a fixed point is reached.
+// However, in the pathological worst case, this implementation is
+// quadratic in the number of blocks; relaxing branch N can make branch N-1
+// go out of range, which in turn can make branch N-2 go out of range,
+// and so on.
//
// An alternative approach is to assume that all branches must be
// converted to their long forms, then reinstate the short forms of
STATISTIC(LongBranches, "Number of long branches.");
namespace {
- typedef MachineBasicBlock::iterator Iter;
-
// Represents positional information about a basic block.
struct MBBInfo {
// The address that we currently assume the block has.
void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
bool AssumeRelaxed);
TerminatorInfo describeTerminator(MachineInstr *MI);
- bool fuseCompareAndBranch(MachineInstr *Compare);
uint64_t initMBBInfo();
bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
bool mustRelaxABranch();
void setWorstCaseAddresses();
+ void splitBranchOnCount(MachineInstr *MI, unsigned AddOpcode);
void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode);
void relaxBranch(TerminatorInfo &Terminator);
void relaxBranches();
// Relaxes to BRCL, which is 2 bytes longer.
Terminator.ExtraRelaxSize = 2;
break;
+ case SystemZ::BRCT:
+ case SystemZ::BRCTG:
+ // Relaxes to A(G)HI and BRCL, which is 6 bytes longer.
+ Terminator.ExtraRelaxSize = 6;
+ break;
case SystemZ::CRJ:
- // Relaxes to a CR/BRCL sequence, which is 2 bytes longer.
+ case SystemZ::CLRJ:
+ // Relaxes to a C(L)R/BRCL sequence, which is 2 bytes longer.
Terminator.ExtraRelaxSize = 2;
break;
case SystemZ::CGRJ:
- // Relaxes to a CGR/BRCL sequence, which is 4 bytes longer.
+ case SystemZ::CLGRJ:
+ // Relaxes to a C(L)GR/BRCL sequence, which is 4 bytes longer.
Terminator.ExtraRelaxSize = 4;
break;
case SystemZ::CIJ:
// Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer.
Terminator.ExtraRelaxSize = 4;
break;
+ case SystemZ::CLIJ:
+ case SystemZ::CLGIJ:
+ // Relaxes to a CL(G)FI/BRCL sequence, which is 6 bytes longer.
+ Terminator.ExtraRelaxSize = 6;
+ break;
default:
llvm_unreachable("Unrecognized branch instruction");
}
return Terminator;
}
-// Return true if CC is live after MBBI.
-static bool isCCLiveAfter(MachineBasicBlock::iterator MBBI,
- const TargetRegisterInfo *TRI) {
- if (MBBI->killsRegister(SystemZ::CC, TRI))
- return false;
-
- MachineBasicBlock *MBB = MBBI->getParent();
- MachineBasicBlock::iterator MBBE = MBB->end();
- for (++MBBI; MBBI != MBBE; ++MBBI) {
- if (MBBI->readsRegister(SystemZ::CC, TRI))
- return true;
- if (MBBI->definesRegister(SystemZ::CC, TRI))
- return false;
- }
-
- for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
- SE = MBB->succ_end(); SI != SE; ++SI)
- if ((*SI)->isLiveIn(SystemZ::CC))
- return true;
-
- return false;
-}
-
-// Try to fuse compare instruction Compare into a later branch. Return
-// true on success and if Compare is therefore redundant.
-bool SystemZLongBranch::fuseCompareAndBranch(MachineInstr *Compare) {
- if (MF->getTarget().getOptLevel() == CodeGenOpt::None)
- return false;
-
- unsigned FusedOpcode = TII->getCompareAndBranch(Compare->getOpcode(),
- Compare);
- if (!FusedOpcode)
- return false;
-
- unsigned SrcReg = Compare->getOperand(0).getReg();
- unsigned SrcReg2 = (Compare->getOperand(1).isReg() ?
- Compare->getOperand(1).getReg() : 0);
- const TargetRegisterInfo *TRI = &TII->getRegisterInfo();
- MachineBasicBlock *MBB = Compare->getParent();
- MachineBasicBlock::iterator MBBI = Compare, MBBE = MBB->end();
- for (++MBBI; MBBI != MBBE; ++MBBI) {
- if (MBBI->getOpcode() == SystemZ::BRC && !isCCLiveAfter(MBBI, TRI)) {
- // Read the branch mask and target.
- MachineOperand CCMask(MBBI->getOperand(0));
- MachineOperand Target(MBBI->getOperand(1));
-
- // Clear out all current operands.
- int CCUse = MBBI->findRegisterUseOperandIdx(SystemZ::CC, false, TRI);
- assert(CCUse >= 0 && "BRC must use CC");
- MBBI->RemoveOperand(CCUse);
- MBBI->RemoveOperand(1);
- MBBI->RemoveOperand(0);
-
- // Rebuild MBBI as a fused compare and branch.
- MBBI->setDesc(TII->get(FusedOpcode));
- MachineInstrBuilder(*MBB->getParent(), MBBI)
- .addOperand(Compare->getOperand(0))
- .addOperand(Compare->getOperand(1))
- .addOperand(CCMask)
- .addOperand(Target);
-
- // Clear any intervening kills of SrcReg and SrcReg2.
- MBBI = Compare;
- for (++MBBI; MBBI != MBBE; ++MBBI) {
- MBBI->clearRegisterKills(SrcReg, TRI);
- if (SrcReg2)
- MBBI->clearRegisterKills(SrcReg2, TRI);
- }
- return true;
- }
-
- // Stop if we find another reference to CC before a branch.
- if (MBBI->readsRegister(SystemZ::CC, TRI) ||
- MBBI->modifiesRegister(SystemZ::CC, TRI))
- return false;
-
- // Stop if we find another assignment to the registers before the branch.
- if (MBBI->modifiesRegister(SrcReg, TRI) ||
- (SrcReg2 && MBBI->modifiesRegister(SrcReg2, TRI)))
- return false;
- }
- return false;
-}
-
// Fill MBBs and Terminators, setting the addresses on the assumption
// that no branches need relaxation. Return the size of the function under
// this assumption.
MachineBasicBlock::iterator MI = MBB->begin();
MachineBasicBlock::iterator End = MBB->end();
while (MI != End && !MI->isTerminator()) {
- MachineInstr *Current = MI;
+ Block.Size += TII->getInstSizeInBytes(MI);
++MI;
- if (Current->isCompare() && fuseCompareAndBranch(Current))
- Current->removeFromParent();
- else
- Block.Size += TII->getInstSizeInBytes(Current);
}
skipNonTerminators(Position, Block);
}
}
+// Split BRANCH ON COUNT MI into the addition given by AddOpcode followed
+// by a BRCL on the result.
+void SystemZLongBranch::splitBranchOnCount(MachineInstr *MI,
+ unsigned AddOpcode) {
+ MachineBasicBlock *MBB = MI->getParent();
+ DebugLoc DL = MI->getDebugLoc();
+ BuildMI(*MBB, MI, DL, TII->get(AddOpcode))
+ .addOperand(MI->getOperand(0))
+ .addOperand(MI->getOperand(1))
+ .addImm(-1);
+ MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
+ .addImm(SystemZ::CCMASK_ICMP)
+ .addImm(SystemZ::CCMASK_CMP_NE)
+ .addOperand(MI->getOperand(2));
+ // The implicit use of CC is a killing use.
+ BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
+ MI->eraseFromParent();
+}
+
// Split MI into the comparison given by CompareOpcode followed
// a BRCL on the result.
void SystemZLongBranch::splitCompareBranch(MachineInstr *MI,
.addOperand(MI->getOperand(0))
.addOperand(MI->getOperand(1));
MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
+ .addImm(SystemZ::CCMASK_ICMP)
.addOperand(MI->getOperand(2))
.addOperand(MI->getOperand(3));
// The implicit use of CC is a killing use.
- BRCL->getOperand(2).setIsKill();
+ BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
MI->eraseFromParent();
}
case SystemZ::BRC:
Branch->setDesc(TII->get(SystemZ::BRCL));
break;
+ case SystemZ::BRCT:
+ splitBranchOnCount(Branch, SystemZ::AHI);
+ break;
+ case SystemZ::BRCTG:
+ splitBranchOnCount(Branch, SystemZ::AGHI);
+ break;
case SystemZ::CRJ:
splitCompareBranch(Branch, SystemZ::CR);
break;
case SystemZ::CGIJ:
splitCompareBranch(Branch, SystemZ::CGHI);
break;
+ case SystemZ::CLRJ:
+ splitCompareBranch(Branch, SystemZ::CLR);
+ break;
+ case SystemZ::CLGRJ:
+ splitCompareBranch(Branch, SystemZ::CLGR);
+ break;
+ case SystemZ::CLIJ:
+ splitCompareBranch(Branch, SystemZ::CLFI);
+ break;
+ case SystemZ::CLGIJ:
+ splitCompareBranch(Branch, SystemZ::CLGFI);
+ break;
default:
llvm_unreachable("Unrecognized branch");
}