lib/Target/SystemZ/SystemZLongBranch.cpp

   1 //===-- SystemZLongBranch.cpp - Branch lengthening for SystemZ ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass does three things:
  11 // (1) try to remove compares if CC already contains the required information
  12 // (2) fuse compares and branches into COMPARE AND BRANCH instructions
  13 // (3) make sure that all branches are in range.
  14 //
  15 // We do (1) here rather than earlier because some transformations can
  16 // change the set of available CC values and we generally want those
  17 // transformations to have priority over (1).  This is especially true in
  18 // the commonest case where the CC value is used by a single in-range branch
  19 // instruction, since (2) will then be able to fuse the compare and the
  20 // branch instead.
  21 //
  22 // For example, two-address NILF can sometimes be converted into
  23 // three-address RISBLG.  NILF produces a CC value that indicates whether
  24 // the low word is zero, but RISBLG does not modify CC at all.  On the
  25 // other hand, 64-bit ANDs like NILL can sometimes be converted to RISBG.
  26 // The CC value produced by NILL isn't useful for our purposes, but the
  27 // value produced by RISBG can be used for any comparison with zero
  28 // (not just equality).  So there are some transformations that lose
  29 // CC values (while still being worthwhile) and others that happen to make
  30 // the CC result more useful than it was originally.
  31 //
  32 // We do (2) here rather than earlier because the fused form prevents
  33 // predication.  It also has to happen after (1).
  34 //
  35 // Doing (2) so late makes it more likely that a register will be reused
  36 // between the compare and the branch, but it isn't clear whether preventing
  37 // that would be a win or not.
  38 //
  39 // There are several ways in which (3) could be done.  One aggressive
  40 // approach is to assume that all branches are in range and successively
  41 // replace those that turn out not to be in range with a longer form
  42 // (branch relaxation).  A simple implementation is to continually walk
  43 // through the function relaxing branches until no more changes are
  44 // needed and a fixed point is reached.  However, in the pathological
  45 // worst case, this implementation is quadratic in the number of blocks;
  46 // relaxing branch N can make branch N-1 go out of range, which in turn
  47 // can make branch N-2 go out of range, and so on.
  48 //
  49 // An alternative approach is to assume that all branches must be
  50 // converted to their long forms, then reinstate the short forms of
  51 // branches that, even under this pessimistic assumption, turn out to be
  52 // in range (branch shortening).  This too can be implemented as a function
  53 // walk that is repeated until a fixed point is reached.  In general,
  54 // the result of shortening is not as good as that of relaxation, and
  55 // shortening is also quadratic in the worst case; shortening branch N
  56 // can bring branch N-1 in range of the short form, which in turn can do
  57 // the same for branch N-2, and so on.  The main advantage of shortening
  58 // is that each walk through the function produces valid code, so it is
  59 // possible to stop at any point after the first walk.  The quadraticness
  60 // could therefore be handled with a maximum pass count, although the
  61 // question then becomes: what maximum count should be used?
  62 //
  63 // On SystemZ, long branches are only needed for functions bigger than 64k,
  64 // which are relatively rare to begin with, and the long branch sequences
  65 // are actually relatively cheap.  It therefore doesn't seem worth spending
  66 // much compilation time on the problem.  Instead, the approach we take is:
  67 //
  68 // (1) Work out the address that each block would have if no branches
  69 //     need relaxing.  Exit the pass early if all branches are in range
  70 //     according to this assumption.
  71 //
  72 // (2) Work out the address that each block would have if all branches
  73 //     need relaxing.
  74 //
  75 // (3) Walk through the block calculating the final address of each instruction
  76 //     and relaxing those that need to be relaxed.  For backward branches,
  77 //     this check uses the final address of the target block, as calculated
  78 //     earlier in the walk.  For forward branches, this check uses the
  79 //     address of the target block that was calculated in (2).  Both checks
  80 //     give a conservatively-correct range.
  81 //
  82 //===----------------------------------------------------------------------===//
  83
  84 #define DEBUG_TYPE "systemz-long-branch"
  85
  86 #include "SystemZTargetMachine.h"
  87 #include "llvm/ADT/Statistic.h"
  88 #include "llvm/CodeGen/MachineFunctionPass.h"
  89 #include "llvm/CodeGen/MachineInstrBuilder.h"
  90 #include "llvm/IR/Function.h"
  91 #include "llvm/Support/CommandLine.h"
  92 #include "llvm/Support/MathExtras.h"
  93 #include "llvm/Target/TargetInstrInfo.h"
  94 #include "llvm/Target/TargetMachine.h"
  95 #include "llvm/Target/TargetRegisterInfo.h"
  96
  97 using namespace llvm;
  98
  99 STATISTIC(LongBranches, "Number of long branches.");
 100
 101 namespace {
 102   typedef MachineBasicBlock::iterator Iter;
 103
 104   // Represents positional information about a basic block.
 105   struct MBBInfo {
 106     // The address that we currently assume the block has.
 107     uint64_t Address;
 108
 109     // The size of the block in bytes, excluding terminators.
 110     // This value never changes.
 111     uint64_t Size;
 112
 113     // The minimum alignment of the block, as a log2 value.
 114     // This value never changes.
 115     unsigned Alignment;
 116
 117     // The number of terminators in this block.  This value never changes.
 118     unsigned NumTerminators;
 119
 120     MBBInfo()
 121       : Address(0), Size(0), Alignment(0), NumTerminators(0) {}
 122   };
 123
 124   // Represents the state of a block terminator.
 125   struct TerminatorInfo {
 126     // If this terminator is a relaxable branch, this points to the branch
 127     // instruction, otherwise it is null.
 128     MachineInstr *Branch;
 129
 130     // The address that we currently assume the terminator has.
 131     uint64_t Address;
 132
 133     // The current size of the terminator in bytes.
 134     uint64_t Size;
 135
 136     // If Branch is nonnull, this is the number of the target block,
 137     // otherwise it is unused.
 138     unsigned TargetBlock;
 139
 140     // If Branch is nonnull, this is the length of the longest relaxed form,
 141     // otherwise it is zero.
 142     unsigned ExtraRelaxSize;
 143
 144     TerminatorInfo() : Branch(0), Size(0), TargetBlock(0), ExtraRelaxSize(0) {}
 145   };
 146
 147   // Used to keep track of the current position while iterating over the blocks.
 148   struct BlockPosition {
 149     // The address that we assume this position has.
 150     uint64_t Address;
 151
 152     // The number of low bits in Address that are known to be the same
 153     // as the runtime address.
 154     unsigned KnownBits;
 155
 156     BlockPosition(unsigned InitialAlignment)
 157       : Address(0), KnownBits(InitialAlignment) {}
 158   };
 159
 160   class SystemZLongBranch : public MachineFunctionPass {
 161   public:
 162     static char ID;
 163     SystemZLongBranch(const SystemZTargetMachine &tm)
 164       : MachineFunctionPass(ID), TII(0) {}
 165
 166     virtual const char *getPassName() const {
 167       return "SystemZ Long Branch";
 168     }
 169
 170     bool runOnMachineFunction(MachineFunction &F);
 171
 172   private:
 173     void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);
 174     void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,
 175                         bool AssumeRelaxed);
 176     TerminatorInfo describeTerminator(MachineInstr *MI);
 177     bool optimizeCompareZero(MachineInstr *PrevCCSetter, MachineInstr *Compare);
 178     bool fuseCompareAndBranch(MachineInstr *Compare);
 179     uint64_t initMBBInfo();
 180     bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);
 181     bool mustRelaxABranch();
 182     void setWorstCaseAddresses();
 183     void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode);
 184     void relaxBranch(TerminatorInfo &Terminator);
 185     void relaxBranches();
 186
 187     const SystemZInstrInfo *TII;
 188     MachineFunction *MF;
 189     SmallVector<MBBInfo, 16> MBBs;
 190     SmallVector<TerminatorInfo, 16> Terminators;
 191   };
 192
 193   char SystemZLongBranch::ID = 0;
 194
 195   const uint64_t MaxBackwardRange = 0x10000;
 196   const uint64_t MaxForwardRange = 0xfffe;
 197 } // end of anonymous namespace
 198
 199 FunctionPass *llvm::createSystemZLongBranchPass(SystemZTargetMachine &TM) {
 200   return new SystemZLongBranch(TM);
 201 }
 202
 203 // Position describes the state immediately before Block.  Update Block
 204 // accordingly and move Position to the end of the block's non-terminator
 205 // instructions.
 206 void SystemZLongBranch::skipNonTerminators(BlockPosition &Position,
 207                                            MBBInfo &Block) {
 208   if (Block.Alignment > Position.KnownBits) {
 209     // When calculating the address of Block, we need to conservatively
 210     // assume that Block had the worst possible misalignment.
 211     Position.Address += ((uint64_t(1) << Block.Alignment) -
 212                          (uint64_t(1) << Position.KnownBits));
 213     Position.KnownBits = Block.Alignment;
 214   }
 215
 216   // Align the addresses.
 217   uint64_t AlignMask = (uint64_t(1) << Block.Alignment) - 1;
 218   Position.Address = (Position.Address + AlignMask) & ~AlignMask;
 219
 220   // Record the block's position.
 221   Block.Address = Position.Address;
 222
 223   // Move past the non-terminators in the block.
 224   Position.Address += Block.Size;
 225 }
 226
 227 // Position describes the state immediately before Terminator.
 228 // Update Terminator accordingly and move Position past it.
 229 // Assume that Terminator will be relaxed if AssumeRelaxed.
 230 void SystemZLongBranch::skipTerminator(BlockPosition &Position,
 231                                        TerminatorInfo &Terminator,
 232                                        bool AssumeRelaxed) {
 233   Terminator.Address = Position.Address;
 234   Position.Address += Terminator.Size;
 235   if (AssumeRelaxed)
 236     Position.Address += Terminator.ExtraRelaxSize;
 237 }
 238
 239 // Return a description of terminator instruction MI.
 240 TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr *MI) {
 241   TerminatorInfo Terminator;
 242   Terminator.Size = TII->getInstSizeInBytes(MI);
 243   if (MI->isConditionalBranch() || MI->isUnconditionalBranch()) {
 244     switch (MI->getOpcode()) {
 245     case SystemZ::J:
 246       // Relaxes to JG, which is 2 bytes longer.
 247       Terminator.ExtraRelaxSize = 2;
 248       break;
 249     case SystemZ::BRC:
 250       // Relaxes to BRCL, which is 2 bytes longer.
 251       Terminator.ExtraRelaxSize = 2;
 252       break;
 253     case SystemZ::CRJ:
 254       // Relaxes to a CR/BRCL sequence, which is 2 bytes longer.
 255       Terminator.ExtraRelaxSize = 2;
 256       break;
 257     case SystemZ::CGRJ:
 258       // Relaxes to a CGR/BRCL sequence, which is 4 bytes longer.
 259       Terminator.ExtraRelaxSize = 4;
 260       break;
 261     case SystemZ::CIJ:
 262     case SystemZ::CGIJ:
 263       // Relaxes to a C(G)HI/BRCL sequence, which is 4 bytes longer.
 264       Terminator.ExtraRelaxSize = 4;
 265       break;
 266     default:
 267       llvm_unreachable("Unrecognized branch instruction");
 268     }
 269     Terminator.Branch = MI;
 270     Terminator.TargetBlock =
 271       TII->getBranchInfo(MI).Target->getMBB()->getNumber();
 272   }
 273   return Terminator;
 274 }
 275
 276 // Return true if CC is live out of MBB.
 277 static bool isCCLiveOut(MachineBasicBlock *MBB) {
 278   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 279          SE = MBB->succ_end(); SI != SE; ++SI)
 280     if ((*SI)->isLiveIn(SystemZ::CC))
 281       return true;
 282   return false;
 283 }
 284
 285 // Return true if CC is live after MBBI.
 286 static bool isCCLiveAfter(MachineBasicBlock::iterator MBBI,
 287                           const TargetRegisterInfo *TRI) {
 288   if (MBBI->killsRegister(SystemZ::CC, TRI))
 289     return false;
 290
 291   MachineBasicBlock *MBB = MBBI->getParent();
 292   MachineBasicBlock::iterator MBBE = MBB->end();
 293   for (++MBBI; MBBI != MBBE; ++MBBI) {
 294     if (MBBI->readsRegister(SystemZ::CC, TRI))
 295       return true;
 296     if (MBBI->definesRegister(SystemZ::CC, TRI))
 297       return false;
 298   }
 299
 300   return isCCLiveOut(MBB);
 301 }
 302
 303 // Return true if all uses of the CC value produced by MBBI could make do
 304 // with the CC values in ReusableCCMask.  When returning true, point AlterMasks
 305 // to the "CC valid" and "CC mask" operands for each condition.
 306 static bool canRestrictCCMask(MachineBasicBlock::iterator MBBI,
 307                               unsigned ReusableCCMask,
 308                               SmallVectorImpl<MachineOperand *> &AlterMasks,
 309                               const TargetRegisterInfo *TRI) {
 310   MachineBasicBlock *MBB = MBBI->getParent();
 311   MachineBasicBlock::iterator MBBE = MBB->end();
 312   for (++MBBI; MBBI != MBBE; ++MBBI) {
 313     if (MBBI->readsRegister(SystemZ::CC, TRI)) {
 314       // Fail if this isn't a use of CC that we understand.
 315       unsigned MBBIFlags = MBBI->getDesc().TSFlags;
 316       unsigned FirstOpNum;
 317       if (MBBIFlags & SystemZII::CCMaskFirst)
 318         FirstOpNum = 0;
 319       else if (MBBIFlags & SystemZII::CCMaskLast)
 320         FirstOpNum = MBBI->getNumExplicitOperands() - 2;
 321       else
 322         return false;
 323
 324       // Check whether the instruction predicate treats all CC values
 325       // outside of ReusableCCMask in the same way.  In that case it
 326       // doesn't matter what those CC values mean.
 327       unsigned CCValid = MBBI->getOperand(FirstOpNum).getImm();
 328       unsigned CCMask = MBBI->getOperand(FirstOpNum + 1).getImm();
 329       unsigned OutValid = ~ReusableCCMask & CCValid;
 330       unsigned OutMask = ~ReusableCCMask & CCMask;
 331       if (OutMask != 0 && OutMask != OutValid)
 332         return false;
 333
 334       AlterMasks.push_back(&MBBI->getOperand(FirstOpNum));
 335       AlterMasks.push_back(&MBBI->getOperand(FirstOpNum + 1));
 336
 337       // Succeed if this was the final use of the CC value.
 338       if (MBBI->killsRegister(SystemZ::CC, TRI))
 339         return true;
 340     }
 341     // Succeed if the instruction redefines CC.
 342     if (MBBI->definesRegister(SystemZ::CC, TRI))
 343       return true;
 344   }
 345   // Fail if there are other uses of CC that we didn't see.
 346   return !isCCLiveOut(MBB);
 347 }
 348
 349 // Try to make Compare redundant with PrevCCSetter, the previous setter of CC,
 350 // by looking for cases where Compare compares the result of PrevCCSetter
 351 // against zero.  Return true on success and if Compare can therefore
 352 // be deleted.
 353 bool SystemZLongBranch::optimizeCompareZero(MachineInstr *PrevCCSetter,
 354                                             MachineInstr *Compare) {
 355   if (MF->getTarget().getOptLevel() == CodeGenOpt::None)
 356     return false;
 357
 358   // Check whether this is a comparison against zero.
 359   if (Compare->getNumExplicitOperands() != 2 ||
 360       !Compare->getOperand(1).isImm() ||
 361       Compare->getOperand(1).getImm() != 0)
 362     return false;
 363
 364   // See which compare-style condition codes are available after PrevCCSetter.
 365   unsigned PrevFlags = PrevCCSetter->getDesc().TSFlags;
 366   unsigned ReusableCCMask = 0;
 367   if (PrevFlags & SystemZII::CCHasZero)
 368     ReusableCCMask |= SystemZ::CCMASK_CMP_EQ;
 369
 370   // For unsigned comparisons with zero, only equality makes sense.
 371   unsigned CompareFlags = Compare->getDesc().TSFlags;
 372   if (!(CompareFlags & SystemZII::IsLogical) &&
 373       (PrevFlags & SystemZII::CCHasOrder))
 374     ReusableCCMask |= SystemZ::CCMASK_CMP_LT | SystemZ::CCMASK_CMP_GT;
 375
 376   if (ReusableCCMask == 0)
 377     return false;
 378
 379   // Make sure that PrevCCSetter sets the value being compared.
 380   unsigned SrcReg = Compare->getOperand(0).getReg();
 381   unsigned SrcSubReg = Compare->getOperand(0).getSubReg();
 382   if (!PrevCCSetter->getOperand(0).isReg() ||
 383       !PrevCCSetter->getOperand(0).isDef() ||
 384       PrevCCSetter->getOperand(0).getReg() != SrcReg ||
 385       PrevCCSetter->getOperand(0).getSubReg() != SrcSubReg)
 386     return false;
 387
 388   // Make sure that SrcReg survives until Compare.
 389   MachineBasicBlock::iterator MBBI = PrevCCSetter, MBBE = Compare;
 390   const TargetRegisterInfo *TRI = &TII->getRegisterInfo();
 391   for (++MBBI; MBBI != MBBE; ++MBBI)
 392     if (MBBI->modifiesRegister(SrcReg, TRI))
 393       return false;
 394
 395   // See whether all uses of Compare's CC value could make do with
 396   // the values produced by PrevCCSetter.
 397   SmallVector<MachineOperand *, 4> AlterMasks;
 398   if (!canRestrictCCMask(Compare, ReusableCCMask, AlterMasks, TRI))
 399     return false;
 400
 401   // Alter the CC masks that canRestrictCCMask says need to be altered.
 402   unsigned CCValues = SystemZII::getCCValues(PrevFlags);
 403   assert((ReusableCCMask & ~CCValues) == 0 && "Invalid CCValues");
 404   for (unsigned I = 0, E = AlterMasks.size(); I != E; I += 2) {
 405     AlterMasks[I]->setImm(CCValues);
 406     unsigned CCMask = AlterMasks[I + 1]->getImm();
 407     if (CCMask & ~ReusableCCMask)
 408       AlterMasks[I + 1]->setImm((CCMask & ReusableCCMask) |
 409                                 (CCValues & ~ReusableCCMask));
 410   }
 411
 412   // CC is now live after PrevCCSetter.
 413   int CCDef = PrevCCSetter->findRegisterDefOperandIdx(SystemZ::CC, false,
 414                                                       true, TRI);
 415   assert(CCDef >= 0 && "Couldn't find CC set");
 416   PrevCCSetter->getOperand(CCDef).setIsDead(false);
 417
 418   // Clear any intervening kills of CC.
 419   MBBI = PrevCCSetter;
 420   for (++MBBI; MBBI != MBBE; ++MBBI)
 421     MBBI->clearRegisterKills(SystemZ::CC, TRI);
 422
 423   return true;
 424 }
 425
 426 // Try to fuse compare instruction Compare into a later branch.  Return
 427 // true on success and if Compare is therefore redundant.
 428 bool SystemZLongBranch::fuseCompareAndBranch(MachineInstr *Compare) {
 429   if (MF->getTarget().getOptLevel() == CodeGenOpt::None)
 430     return false;
 431
 432   unsigned FusedOpcode = TII->getCompareAndBranch(Compare->getOpcode(),
 433                                                   Compare);
 434   if (!FusedOpcode)
 435     return false;
 436
 437   unsigned SrcReg = Compare->getOperand(0).getReg();
 438   unsigned SrcReg2 = (Compare->getOperand(1).isReg() ?
 439                       Compare->getOperand(1).getReg() : 0);
 440   const TargetRegisterInfo *TRI = &TII->getRegisterInfo();
 441   MachineBasicBlock *MBB = Compare->getParent();
 442   MachineBasicBlock::iterator MBBI = Compare, MBBE = MBB->end();
 443   for (++MBBI; MBBI != MBBE; ++MBBI) {
 444     if (MBBI->getOpcode() == SystemZ::BRC && !isCCLiveAfter(MBBI, TRI)) {
 445       // Read the branch mask and target.
 446       MachineOperand CCMask(MBBI->getOperand(1));
 447       MachineOperand Target(MBBI->getOperand(2));
 448       assert((CCMask.getImm() & ~SystemZ::CCMASK_ICMP) == 0 &&
 449              "Invalid condition-code mask for integer comparison");
 450
 451       // Clear out all current operands.
 452       int CCUse = MBBI->findRegisterUseOperandIdx(SystemZ::CC, false, TRI);
 453       assert(CCUse >= 0 && "BRC must use CC");
 454       MBBI->RemoveOperand(CCUse);
 455       MBBI->RemoveOperand(2);
 456       MBBI->RemoveOperand(1);
 457       MBBI->RemoveOperand(0);
 458
 459       // Rebuild MBBI as a fused compare and branch.
 460       MBBI->setDesc(TII->get(FusedOpcode));
 461       MachineInstrBuilder(*MBB->getParent(), MBBI)
 462         .addOperand(Compare->getOperand(0))
 463         .addOperand(Compare->getOperand(1))
 464         .addOperand(CCMask)
 465         .addOperand(Target);
 466
 467       // Clear any intervening kills of SrcReg and SrcReg2.
 468       MBBI = Compare;
 469       for (++MBBI; MBBI != MBBE; ++MBBI) {
 470         MBBI->clearRegisterKills(SrcReg, TRI);
 471         if (SrcReg2)
 472           MBBI->clearRegisterKills(SrcReg2, TRI);
 473       }
 474       return true;
 475     }
 476
 477     // Stop if we find another reference to CC before a branch.
 478     if (MBBI->readsRegister(SystemZ::CC, TRI) ||
 479         MBBI->modifiesRegister(SystemZ::CC, TRI))
 480       return false;
 481
 482     // Stop if we find another assignment to the registers before the branch.
 483     if (MBBI->modifiesRegister(SrcReg, TRI) ||
 484         (SrcReg2 && MBBI->modifiesRegister(SrcReg2, TRI)))
 485       return false;
 486   }
 487   return false;
 488 }
 489
 490 // Fill MBBs and Terminators, setting the addresses on the assumption
 491 // that no branches need relaxation.  Return the size of the function under
 492 // this assumption.
 493 uint64_t SystemZLongBranch::initMBBInfo() {
 494   const TargetRegisterInfo *TRI = &TII->getRegisterInfo();
 495
 496   MF->RenumberBlocks();
 497   unsigned NumBlocks = MF->size();
 498
 499   MBBs.clear();
 500   MBBs.resize(NumBlocks);
 501
 502   Terminators.clear();
 503   Terminators.reserve(NumBlocks);
 504
 505   BlockPosition Position(MF->getAlignment());
 506   for (unsigned I = 0; I < NumBlocks; ++I) {
 507     MachineBasicBlock *MBB = MF->getBlockNumbered(I);
 508     MBBInfo &Block = MBBs[I];
 509
 510     // Record the alignment, for quick access.
 511     Block.Alignment = MBB->getAlignment();
 512
 513     // Calculate the size of the fixed part of the block.
 514     MachineBasicBlock::iterator MI = MBB->begin();
 515     MachineBasicBlock::iterator End = MBB->end();
 516     MachineInstr *PrevCCSetter = 0;
 517     while (MI != End && !MI->isTerminator()) {
 518       MachineInstr *Current = MI;
 519       ++MI;
 520       if (Current->isCompare()) {
 521         if ((PrevCCSetter && optimizeCompareZero(PrevCCSetter, Current)) ||
 522             fuseCompareAndBranch(Current)) {
 523           Current->removeFromParent();
 524           continue;
 525         }
 526       }
 527       if (Current->modifiesRegister(SystemZ::CC, TRI))
 528         PrevCCSetter = Current;
 529       Block.Size += TII->getInstSizeInBytes(Current);
 530     }
 531     skipNonTerminators(Position, Block);
 532
 533     // Add the terminators.
 534     while (MI != End) {
 535       if (!MI->isDebugValue()) {
 536         assert(MI->isTerminator() && "Terminator followed by non-terminator");
 537         Terminators.push_back(describeTerminator(MI));
 538         skipTerminator(Position, Terminators.back(), false);
 539         ++Block.NumTerminators;
 540       }
 541       ++MI;
 542     }
 543   }
 544
 545   return Position.Address;
 546 }
 547
 548 // Return true if, under current assumptions, Terminator would need to be
 549 // relaxed if it were placed at address Address.
 550 bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator,
 551                                         uint64_t Address) {
 552   if (!Terminator.Branch)
 553     return false;
 554
 555   const MBBInfo &Target = MBBs[Terminator.TargetBlock];
 556   if (Address >= Target.Address) {
 557     if (Address - Target.Address <= MaxBackwardRange)
 558       return false;
 559   } else {
 560     if (Target.Address - Address <= MaxForwardRange)
 561       return false;
 562   }
 563
 564   return true;
 565 }
 566
 567 // Return true if, under current assumptions, any terminator needs
 568 // to be relaxed.
 569 bool SystemZLongBranch::mustRelaxABranch() {
 570   for (SmallVectorImpl<TerminatorInfo>::iterator TI = Terminators.begin(),
 571          TE = Terminators.end(); TI != TE; ++TI)
 572     if (mustRelaxBranch(*TI, TI->Address))
 573       return true;
 574   return false;
 575 }
 576
 577 // Set the address of each block on the assumption that all branches
 578 // must be long.
 579 void SystemZLongBranch::setWorstCaseAddresses() {
 580   SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
 581   BlockPosition Position(MF->getAlignment());
 582   for (SmallVectorImpl<MBBInfo>::iterator BI = MBBs.begin(), BE = MBBs.end();
 583        BI != BE; ++BI) {
 584     skipNonTerminators(Position, *BI);
 585     for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
 586       skipTerminator(Position, *TI, true);
 587       ++TI;
 588     }
 589   }
 590 }
 591
 592 // Split MI into the comparison given by CompareOpcode followed
 593 // a BRCL on the result.
 594 void SystemZLongBranch::splitCompareBranch(MachineInstr *MI,
 595                                            unsigned CompareOpcode) {
 596   MachineBasicBlock *MBB = MI->getParent();
 597   DebugLoc DL = MI->getDebugLoc();
 598   BuildMI(*MBB, MI, DL, TII->get(CompareOpcode))
 599     .addOperand(MI->getOperand(0))
 600     .addOperand(MI->getOperand(1));
 601   MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))
 602     .addImm(SystemZ::CCMASK_ICMP)
 603     .addOperand(MI->getOperand(2))
 604     .addOperand(MI->getOperand(3));
 605   // The implicit use of CC is a killing use.
 606   BRCL->addRegisterKilled(SystemZ::CC, &TII->getRegisterInfo());
 607   MI->eraseFromParent();
 608 }
 609
 610 // Relax the branch described by Terminator.
 611 void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {
 612   MachineInstr *Branch = Terminator.Branch;
 613   switch (Branch->getOpcode()) {
 614   case SystemZ::J:
 615     Branch->setDesc(TII->get(SystemZ::JG));
 616     break;
 617   case SystemZ::BRC:
 618     Branch->setDesc(TII->get(SystemZ::BRCL));
 619     break;
 620   case SystemZ::CRJ:
 621     splitCompareBranch(Branch, SystemZ::CR);
 622     break;
 623   case SystemZ::CGRJ:
 624     splitCompareBranch(Branch, SystemZ::CGR);
 625     break;
 626   case SystemZ::CIJ:
 627     splitCompareBranch(Branch, SystemZ::CHI);
 628     break;
 629   case SystemZ::CGIJ:
 630     splitCompareBranch(Branch, SystemZ::CGHI);
 631     break;
 632   default:
 633     llvm_unreachable("Unrecognized branch");
 634   }
 635
 636   Terminator.Size += Terminator.ExtraRelaxSize;
 637   Terminator.ExtraRelaxSize = 0;
 638   Terminator.Branch = 0;
 639
 640   ++LongBranches;
 641 }
 642
 643 // Run a shortening pass and relax any branches that need to be relaxed.
 644 void SystemZLongBranch::relaxBranches() {
 645   SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();
 646   BlockPosition Position(MF->getAlignment());
 647   for (SmallVectorImpl<MBBInfo>::iterator BI = MBBs.begin(), BE = MBBs.end();
 648        BI != BE; ++BI) {
 649     skipNonTerminators(Position, *BI);
 650     for (unsigned BTI = 0, BTE = BI->NumTerminators; BTI != BTE; ++BTI) {
 651       assert(Position.Address <= TI->Address &&
 652              "Addresses shouldn't go forwards");
 653       if (mustRelaxBranch(*TI, Position.Address))
 654         relaxBranch(*TI);
 655       skipTerminator(Position, *TI, false);
 656       ++TI;
 657     }
 658   }
 659 }
 660
 661 bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {
 662   TII = static_cast<const SystemZInstrInfo *>(F.getTarget().getInstrInfo());
 663   MF = &F;
 664   uint64_t Size = initMBBInfo();
 665   if (Size <= MaxForwardRange || !mustRelaxABranch())
 666     return false;
 667
 668   setWorstCaseAddresses();
 669   relaxBranches();
 670   return true;
 671 }