SystemZLongBranch.cpp Source File (original) (raw)

68#include

69#include

71using namespace llvm;

73#define DEBUG_TYPE "systemz-long-branch"

75 STATISTIC(LongBranches, "Number of long branches.");

77namespace {

80struct MBBInfo {

93 unsigned NumTerminators = 0;

95 MBBInfo() = default;

96};

99struct TerminatorInfo {

100

101

102 MachineInstr *Branch = nullptr;

103

104

105 uint64_t Address = 0;

106

107

108 uint64_t Size = 0;

109

110

111

112 unsigned TargetBlock = 0;

113

114

115

116 unsigned ExtraRelaxSize = 0;

117

118 TerminatorInfo() = default;

119};

120

121

122struct BlockPosition {

123

124 uint64_t Address = 0;

125

126

127

128 unsigned KnownBits;

129

130 BlockPosition(unsigned InitialLogAlignment)

131 : KnownBits(InitialLogAlignment) {}

132};

133

135public:

136 static char ID;

137

138 SystemZLongBranch() : MachineFunctionPass(ID) {}

139

140 bool runOnMachineFunction(MachineFunction &F) override;

141

142 MachineFunctionProperties getRequiredProperties() const override {

143 return MachineFunctionProperties().setNoVRegs();

144 }

145

146private:

147 void skipNonTerminators(BlockPosition &Position, MBBInfo &Block);

148 void skipTerminator(BlockPosition &Position, TerminatorInfo &Terminator,

149 bool AssumeRelaxed);

150 TerminatorInfo describeTerminator(MachineInstr &MI);

151 uint64_t initMBBInfo();

152 bool mustRelaxBranch(const TerminatorInfo &Terminator, uint64_t Address);

153 bool mustRelaxABranch();

154 void setWorstCaseAddresses();

155 void splitBranchOnCount(MachineInstr *MI, unsigned AddOpcode);

156 void splitCompareBranch(MachineInstr *MI, unsigned CompareOpcode);

157 void relaxBranch(TerminatorInfo &Terminator);

158 void relaxBranches();

159

160 const SystemZInstrInfo *TII = nullptr;

161 MachineFunction *MF = nullptr;

164};

165

166char SystemZLongBranch::ID = 0;

167

168const uint64_t MaxBackwardRange = 0x10000;

169const uint64_t MaxForwardRange = 0xfffe;

170

171}

172

174 false)

175

176

177

178

179void SystemZLongBranch::skipNonTerminators(BlockPosition &Position,

180 MBBInfo &Block) {

181 if (Log2(Block.Alignment) > Position.KnownBits) {

182

183

184 Position.Address +=

185 (Block.Alignment.value() - (uint64_t(1) << Position.KnownBits));

186 Position.KnownBits = Log2(Block.Alignment);

187 }

188

189

190 Position.Address = alignTo(Position.Address, Block.Alignment);

191

192

193 Block.Address = Position.Address;

194

195

196 Position.Address += Block.Size;

197}

198

199

200

201

202void SystemZLongBranch::skipTerminator(BlockPosition &Position,

203 TerminatorInfo &Terminator,

204 bool AssumeRelaxed) {

205 Terminator.Address = Position.Address;

207 if (AssumeRelaxed)

208 Position.Address += Terminator.ExtraRelaxSize;

209}

210

213 unsigned Size = TII->getInstSizeInBytes(MI);

215

216 MI.isDebugOrPseudoInstr() || MI.isPosition() || MI.isKill() ||

217 MI.isImplicitDef() || MI.getOpcode() == TargetOpcode::MEMBARRIER ||

218 MI.getOpcode() == TargetOpcode::INIT_UNDEF || MI.isFakeUse() ||

219 MI.getOpcode() == TargetOpcode::RELOC_NONE ||

220

221 MI.isInlineAsm() || MI.getOpcode() == SystemZ::STACKMAP ||

222 MI.getOpcode() == SystemZ::PATCHPOINT ||

223

224

225 MI.getOpcode() == SystemZ::EH_SjLj_Setup) &&

226 "Missing size value for instruction.");

228}

229

230

231TerminatorInfo SystemZLongBranch::describeTerminator(MachineInstr &MI) {

234 if (MI.isConditionalBranch() || MI.isUnconditionalBranch()) {

235 switch (MI.getOpcode()) {

236 case SystemZ::J:

237

239 break;

240 case SystemZ::BRC:

241

243 break;

244 case SystemZ::BRCT:

245 case SystemZ::BRCTG:

246

248 break;

249 case SystemZ::BRCTH:

250

252 break;

253 case SystemZ::CRJ:

254 case SystemZ::CLRJ:

255

257 break;

258 case SystemZ::CGRJ:

259 case SystemZ::CLGRJ:

260

262 break;

263 case SystemZ::CIJ:

264 case SystemZ::CGIJ:

265

267 break;

268 case SystemZ::CLIJ:

269 case SystemZ::CLGIJ:

270

272 break;

273 default:

275 }

278 TII->getBranchInfo(MI).getMBBTarget()->getNumber();

279 }

281}

282

283

284

285

286uint64_t SystemZLongBranch::initMBBInfo() {

288 unsigned NumBlocks = MF->size();

289

290 MBBs.clear();

291 MBBs.resize(NumBlocks);

292

293 Terminators.clear();

294 Terminators.reserve(NumBlocks);

295

297 for (unsigned I = 0; I < NumBlocks; ++I) {

299 MBBInfo &Block = MBBs[I];

300

301

303

304

307 while (MI != End && ->isTerminator()) {

309 ++MI;

310 }

311 skipNonTerminators(Position, Block);

312

313

314 while (MI != End) {

315 if (->isDebugInstr()) {

316 assert(MI->isTerminator() && "Terminator followed by non-terminator");

317 Terminators.push_back(describeTerminator(*MI));

318 skipTerminator(Position, Terminators.back(), false);

319 ++Block.NumTerminators;

320 }

321 ++MI;

322 }

323 }

324

325 return Position.Address;

326}

327

328

329

330bool SystemZLongBranch::mustRelaxBranch(const TerminatorInfo &Terminator,

333 return false;

334

337 if (Address - Target.Address <= MaxBackwardRange)

338 return false;

339 } else {

341 return false;

342 }

343

344 return true;

345}

346

347

348

349bool SystemZLongBranch::mustRelaxABranch() {

350 for (auto &Terminator : Terminators)

351 if (mustRelaxBranch(Terminator, Terminator.Address))

352 return true;

353 return false;

354}

355

356

357

358void SystemZLongBranch::setWorstCaseAddresses() {

359 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();

361 for (auto &Block : MBBs) {

362 skipNonTerminators(Position, Block);

363 for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {

364 skipTerminator(Position, *TI, true);

365 ++TI;

366 }

367 }

368}

369

370

371

372void SystemZLongBranch::splitBranchOnCount(MachineInstr *MI,

373 unsigned AddOpcode) {

374 MachineBasicBlock *MBB = MI->getParent();

376 MachineInstr *AddImm = BuildMI(*MBB, MI, DL, TII->get(AddOpcode))

377 .add(MI->getOperand(0))

378 .add(MI->getOperand(1))

380 MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))

383 .add(MI->getOperand(2));

384

386

387

389 MI->eraseFromParent();

390}

391

392

393

394void SystemZLongBranch::splitCompareBranch(MachineInstr *MI,

395 unsigned CompareOpcode) {

396 MachineBasicBlock *MBB = MI->getParent();

399 .add(MI->getOperand(0))

400 .add(MI->getOperand(1));

401 MachineInstr *BRCL = BuildMI(*MBB, MI, DL, TII->get(SystemZ::BRCL))

403 .add(MI->getOperand(2))

404 .add(MI->getOperand(3));

405

407

408

409 MI->eraseFromParent();

410}

411

412

413void SystemZLongBranch::relaxBranch(TerminatorInfo &Terminator) {

415 switch (Branch->getOpcode()) {

416 case SystemZ::J:

417 Branch->setDesc(TII->get(SystemZ::JG));

418 break;

419 case SystemZ::BRC:

420 Branch->setDesc(TII->get(SystemZ::BRCL));

421 break;

422 case SystemZ::BRCT:

423 splitBranchOnCount(Branch, SystemZ::AHI);

424 break;

425 case SystemZ::BRCTG:

426 splitBranchOnCount(Branch, SystemZ::AGHI);

427 break;

428 case SystemZ::CRJ:

429 splitCompareBranch(Branch, SystemZ::CR);

430 break;

431 case SystemZ::CGRJ:

432 splitCompareBranch(Branch, SystemZ::CGR);

433 break;

434 case SystemZ::CIJ:

435 splitCompareBranch(Branch, SystemZ::CHI);

436 break;

437 case SystemZ::CGIJ:

438 splitCompareBranch(Branch, SystemZ::CGHI);

439 break;

440 case SystemZ::CLRJ:

441 splitCompareBranch(Branch, SystemZ::CLR);

442 break;

443 case SystemZ::CLGRJ:

444 splitCompareBranch(Branch, SystemZ::CLGR);

445 break;

446 case SystemZ::CLIJ:

447 splitCompareBranch(Branch, SystemZ::CLFI);

448 break;

449 case SystemZ::CLGIJ:

450 splitCompareBranch(Branch, SystemZ::CLGFI);

451 break;

452 default:

454 }

455

459

460 ++LongBranches;

461}

462

463

464void SystemZLongBranch::relaxBranches() {

465 SmallVector<TerminatorInfo, 16>::iterator TI = Terminators.begin();

467 for (auto &Block : MBBs) {

468 skipNonTerminators(Position, Block);

469 for (unsigned BTI = 0, BTE = Block.NumTerminators; BTI != BTE; ++BTI) {

470 assert(Position.Address <= TI->Address &&

471 "Addresses shouldn't go forwards");

472 if (mustRelaxBranch(*TI, Position.Address))

473 relaxBranch(*TI);

474 skipTerminator(Position, *TI, false);

475 ++TI;

476 }

477 }

478}

479

480bool SystemZLongBranch::runOnMachineFunction(MachineFunction &F) {

481 TII = static_cast<const SystemZInstrInfo *>(F.getSubtarget().getInstrInfo());

482 MF = &F;

483 uint64_t Size = initMBBInfo();

484 if (Size <= MaxForwardRange || !mustRelaxABranch())

485 return false;

486

487 setWorstCaseAddresses();

488 relaxBranches();

489 return true;

490}

491

493 return new SystemZLongBranch();

494}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

const HexagonInstrInfo * TII

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

static unsigned getInstSizeInBytes(const MachineInstr &MI, const SystemZInstrInfo *TII)

Definition SystemZLongBranch.cpp:211

FunctionPass class - This class is used to implement most global optimizations.

const HexagonRegisterInfo & getRegisterInfo() const

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

Align getAlignment() const

Return alignment of the basic block.

MachineInstrBundleIterator< MachineInstr > iterator

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

void substituteDebugValuesForInst(const MachineInstr &Old, MachineInstr &New, unsigned MaxOperand=UINT_MAX)

Create substitutions for any tracked values in Old, to point at New.

MachineBasicBlock * getBlockNumbered(unsigned N) const

getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...

Align getAlignment() const

getAlignment - Return the alignment of the function.

void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)

RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.

const MachineInstrBuilder & addImm(int64_t Val) const

Add a new immediate operand.

const MachineInstrBuilder & add(const MachineOperand &MO) const

Representation of each machine instruction.

LLVM_ABI bool addRegisterKilled(Register IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)

We have determined MI kills a register.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

const unsigned CCMASK_ICMP

const unsigned CCMASK_CMP_NE

This is an optimization pass for GlobalISel generic memory operations.

FunctionPass * createSystemZLongBranchPass(SystemZTargetMachine &TM)

Definition SystemZLongBranch.cpp:492

MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)

Builder interface. Specify how to create the initial instruction itself.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

uint64_t alignTo(uint64_t Size, Align A)

Returns a multiple of A needed to store Size bytes.

unsigned Log2(Align A)

Returns the log2 of the alignment.

This struct is a compact representation of a valid (non-zero power of two) alignment.