X86OptimizeLEAs.cpp Source File (original) (raw)

49#include

50#include

51#include

53using namespace llvm;

55#define DEBUG_TYPE "x86-optimize-LEAs"

59 cl::desc("X86: Disable LEA optimizations."),

62 STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions");

63 STATISTIC(NumRedundantLEAs, "Number of redundant LEA instructions removed");

78namespace {

81class MemOpKey {

82public:

86 : Disp(Disp) {

87 Operands[0] = Base;

88 Operands[1] = Scale;

89 Operands[2] = Index;

90 Operands[3] = Segment;

91 }

95 for (int i = 0; i < 4; ++i)

97 return false;

100

101

102

104 }

105

106

107 const MachineOperand *Operands[4];

108

109

110 const MachineOperand *Disp;

111};

112

113}

114

115namespace llvm {

116

117

120

122 return MemOpKey(PtrInfo::getEmptyKey(), PtrInfo::getEmptyKey(),

123 PtrInfo::getEmptyKey(), PtrInfo::getEmptyKey(),

124 PtrInfo::getEmptyKey());

125 }

126

128 return MemOpKey(PtrInfo::getTombstoneKey(), PtrInfo::getTombstoneKey(),

129 PtrInfo::getTombstoneKey(), PtrInfo::getTombstoneKey(),

130 PtrInfo::getTombstoneKey());

131 }

132

134

135

136 assert(Val.Disp != PtrInfo::getEmptyKey() && "Cannot hash the empty key");

137 assert(Val.Disp != PtrInfo::getTombstoneKey() &&

138 "Cannot hash the tombstone key");

139

141 *Val.Operands[2], *Val.Operands[3]);

142

143

144

145

146

147 switch (Val.Disp->getType()) {

149 break;

153 break;

156 break;

159 break;

162 break;

165 break;

168 break;

169 default:

171 }

172

173 return (unsigned)Hash;

174 }

175

176 static bool isEqual(const MemOpKey &LHS, const MemOpKey &RHS) {

177

178

179 if (RHS.Disp == PtrInfo::getEmptyKey())

180 return LHS.Disp == PtrInfo::getEmptyKey();

181 if (RHS.Disp == PtrInfo::getTombstoneKey())

182 return LHS.Disp == PtrInfo::getTombstoneKey();

183 return LHS == RHS;

184 }

185};

186

187}

188

189

190

193 "The instruction must be a LEA, a load or a store");

199}

200

205

206#ifndef NDEBUG

211#endif

212

216 "Address displacement operand is not valid");

217 return (MO1.isImm() && MO2.isImm()) ||

229}

230

232 unsigned Opcode = MI.getOpcode();

233 return Opcode == X86::LEA16r || Opcode == X86::LEA32r ||

234 Opcode == X86::LEA64r || Opcode == X86::LEA64_32r;

235}

236

237namespace {

238

240public:

241 X86OptimizeLEAPass() : MachineFunctionPass(ID) {}

242

243 StringRef getPassName() const override { return "X86 LEA Optimize"; }

244

245

246

247

248 bool runOnMachineFunction(MachineFunction &MF) override;

249

250 static char ID;

251

252 void getAnalysisUsage(AnalysisUsage &AU) const override {

253 AU.addRequired();

254 AU.addRequired();

256 }

257

258private:

259 using MemOpMap = DenseMap<MemOpKey, SmallVector<MachineInstr *, 16>>;

260

261

262

263 int calcInstrDist(const MachineInstr &First, const MachineInstr &Last);

264

265

266

267

268

269 bool chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,

270 const MachineInstr &MI, MachineInstr *&BestLEA,

271 int64_t &AddrDispShift, int &Dist);

272

273

274

275

276 int64_t getAddrDispShift(const MachineInstr &MI1, unsigned N1,

277 const MachineInstr &MI2, unsigned N2) const;

278

279

280

281

282

283 bool isReplaceable(const MachineInstr &First, const MachineInstr &Last,

284 int64_t &AddrDispShift) const;

285

286

287

288

289 void findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs);

290

291

292 bool removeRedundantAddrCalc(MemOpMap &LEAs);

293

294

295

296

297 MachineInstr *replaceDebugValue(MachineInstr &MI, Register OldReg,

298 Register NewReg, int64_t AddrDispShift);

299

300

301 bool removeRedundantLEAs(MemOpMap &LEAs);

302

303 DenseMap<const MachineInstr *, unsigned> InstrPos;

304

305 MachineRegisterInfo *MRI = nullptr;

306 const X86InstrInfo *TII = nullptr;

307 const X86RegisterInfo *TRI = nullptr;

308};

309

310}

311

312char X86OptimizeLEAPass::ID = 0;

313

316 false)

317

320

321

323 "Instructions are in different basic blocks");

324 assert(InstrPos.contains(&First) && InstrPos.contains(&Last) &&

325 "Instructions' positions are undefined");

326

327 return InstrPos[&Last] - InstrPos[&First];

328}

329

330

331

332

333

334

335

336

337

338

339bool X86OptimizeLEAPass::chooseBestLEA(

341 MachineInstr *&BestLEA, int64_t &AddrDispShift, int &Dist) {

342 const MCInstrDesc &Desc = MI.getDesc();

345

346 BestLEA = nullptr;

347

348

350

351 int64_t AddrDispShiftTemp = getAddrDispShift(MI, MemOpNo, *DefMI, 1);

352

353

354 if ( isInt<32> (AddrDispShiftTemp))

355 continue;

356

357

358

359

360

361

364 continue;

365

366

367

368

369

370 int DistTemp = calcInstrDist(*DefMI, MI);

371 assert(DistTemp != 0 &&

372 "The distance between two different instructions cannot be zero");

373 if (DistTemp > 0 || BestLEA == nullptr) {

374

375

376 if (BestLEA != nullptr && isInt<8> (AddrDispShiftTemp) &&

378 continue;

379

381 AddrDispShift = AddrDispShiftTemp;

382 Dist = DistTemp;

383 }

384

385

386 if (DistTemp < 0)

387 break;

388 }

389

390 return BestLEA != nullptr;

391}

392

393

394

395

396int64_t X86OptimizeLEAPass::getAddrDispShift(const MachineInstr &MI1,

397 unsigned N1,

398 const MachineInstr &MI2,

399 unsigned N2) const {

402

404 "Address displacement operands are not compatible");

405

406

407

408

410 return 0;

413}

414

415

416

417

418

419

420

421bool X86OptimizeLEAPass::isReplaceable(const MachineInstr &First,

422 const MachineInstr &Last,

423 int64_t &AddrDispShift) const {

425 "The function works only with LEA instructions");

426

427

428

429

430

431 if (MRI->getRegClass(First.getOperand(0).getReg()) !=

432 MRI->getRegClass(Last.getOperand(0).getReg()))

433 return false;

434

435

436 AddrDispShift = getAddrDispShift(Last, 1, First, 1);

437

438

439

440

441 for (auto &MO : MRI->use_nodbg_operands(Last.getOperand(0).getReg())) {

442 MachineInstr &MI = *MO.getParent();

443

444

445 const MCInstrDesc &Desc = MI.getDesc();

447

448

449

450 if (MemOpNo < 0)

451 return false;

452

454

455

456

458 return false;

459

460

461

462 for (unsigned i = 0; i < MI.getNumOperands(); i++)

465 return false;

466

467

470 AddrDispShift))

471 return false;

472 }

473

474 return true;

475}

476

477void X86OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB,

478 MemOpMap &LEAs) {

479 unsigned Pos = 0;

480 for (auto &MI : MBB) {

481

482

483

484

485

486 InstrPos[&MI] = Pos += 2;

487

489 LEAs[getMemOpKey(MI, 1)].push_back(const_cast<MachineInstr *>(&MI));

490 }

491}

492

493

494

495

496bool X86OptimizeLEAPass::removeRedundantAddrCalc(MemOpMap &LEAs) {

498

499 assert(!LEAs.empty());

500 MachineBasicBlock *MBB = (*LEAs.begin()->second.begin())->getParent();

501

502

504

505 if (.mayLoadOrStore())

506 continue;

507

508

509 const MCInstrDesc &Desc = MI.getDesc();

511

512

513 if (MemOpNo < 0)

514 continue;

515

517

518

519 auto Insns = LEAs.find(getMemOpKey(MI, MemOpNo));

520 if (Insns == LEAs.end())

521 continue;

522

523

524 MachineInstr *DefMI;

525 int64_t AddrDispShift;

526 int Dist;

527 if (!chooseBestLEA(Insns->second, MI, DefMI, AddrDispShift, Dist))

528 continue;

529

530

531

532

533

534

535

536 if (Dist < 0) {

539 InstrPos[DefMI] = InstrPos[&MI] - 1;

540

541

544 InstrPos[DefMI] >

546 "Instruction positioning is broken");

547 }

548

549

551

552 ++NumSubstLEAs;

554

555

560 .ChangeToRegister(X86::NoRegister, false);

561 MI.getOperand(MemOpNo + X86::AddrDisp).ChangeToImmediate(AddrDispShift);

563 .ChangeToRegister(X86::NoRegister, false);

564

566

568 }

569

571}

572

573MachineInstr *X86OptimizeLEAPass::replaceDebugValue(MachineInstr &MI,

576 int64_t AddrDispShift) {

577 const DIExpression *Expr = MI.getDebugExpression();

578 if (AddrDispShift != 0) {

579 if (MI.isNonListDebugValue()) {

580 Expr =

582 } else {

583

584

587 for (MachineOperand &Op : MI.getDebugOperandsForReg(OldReg)) {

588 unsigned OpIdx = MI.getDebugOperandIndex(&Op);

590 }

591 }

592 }

593

594

595 MachineBasicBlock *MBB = MI.getParent();

597 bool IsIndirect = MI.isIndirectDebugValue();

598 const MDNode *Var = MI.getDebugVariable();

599 unsigned Opcode = MI.isNonListDebugValue() ? TargetOpcode::DBG_VALUE

600 : TargetOpcode::DBG_VALUE_LIST;

601 if (IsIndirect)

602 assert(MI.getDebugOffset().getImm() == 0 &&

603 "DBG_VALUE with nonzero offset");

605

606

607 auto replaceOldReg = [OldReg, NewReg](const MachineOperand &Op) {

608 if (Op.isReg() && Op.getReg() == OldReg)

610 false, false, false, false, false,

611 true);

612 return Op;

613 };

614 for (const MachineOperand &Op : MI.debug_operands())

617 NewOps, Var, Expr);

618}

619

620

621bool X86OptimizeLEAPass::removeRedundantLEAs(MemOpMap &LEAs) {

623

624

625 for (auto &E : LEAs) {

626 auto &List = E.second;

627

628

629 auto I1 = List.begin();

630 while (I1 != List.end()) {

631 MachineInstr &First = **I1;

632 auto I2 = std::next(I1);

633 while (I2 != List.end()) {

634 MachineInstr &Last = **I2;

635 int64_t AddrDispShift;

636

637

638

640 "LEAs must be in occurrence order in the list");

641

642

643 if (!isReplaceable(First, Last, AddrDispShift)) {

644 ++I2;

645 continue;

646 }

647

648

649

650

651 Register FirstVReg = First.getOperand(0).getReg();

652 Register LastVReg = Last.getOperand(0).getReg();

653

654

655

656

657 while ( MRI ->use_empty(LastVReg)) {

658 MachineOperand &MO = *MRI->use_begin(LastVReg);

660

661 if (MI.isDebugValue()) {

662

663

664

665 replaceDebugValue(MI, LastVReg, FirstVReg, AddrDispShift);

666 continue;

667 }

668

669

670 const MCInstrDesc &Desc = MI.getDesc();

671 int MemOpNo =

674

675

676 MO.setReg(FirstVReg);

677

678

680 if (Op.isImm())

681 Op.setImm(Op.getImm() + AddrDispShift);

682 else if (.isJTI())

683 Op.setOffset(Op.getOffset() + AddrDispShift);

684 }

685

686

687 MRI->clearKillFlags(FirstVReg);

688

689 ++NumRedundantLEAs;

690 LLVM_DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: ";

691 Last.dump(););

692

693

694

695 assert(MRI->use_empty(LastVReg) &&

696 "The LEA's def register must have no uses");

697 Last.eraseFromParent();

698

699

700 I2 = List.erase(I2);

701

703 }

704 ++I1;

705 }

706 }

707

709}

710

711bool X86OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) {

713

715 return false;

716

720 auto *PSI =

721 &getAnalysis().getPSI();

722 auto *MBFI = (PSI && PSI->hasProfileSummary()) ?

723 &getAnalysis().getBFI() :

724 nullptr;

725

726

727 for (auto &MBB : MF) {

728 MemOpMap LEAs;

729 InstrPos.clear();

730

731

732 findLEAs(MBB, LEAs);

733

734

735 if (LEAs.empty())

736 continue;

737

738

739 Changed |= removeRedundantLEAs(LEAs);

740

741

742

744 Changed |= removeRedundantAddrCalc(LEAs);

745 }

746

748}

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder MachineInstrBuilder & DefMI

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

const TargetInstrInfo & TII

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

This file defines DenseMapInfo traits for DenseMap.

This file defines the DenseMap class.

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

===- LazyMachineBlockFrequencyInfo.h - Lazy Block Frequency -*- C++ -*–===//

Promote Memory to Register

MachineInstr unsigned OpIdx

#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 bool isLEA(unsigned Opcode)

static cl::opt< bool > DisableX86LEAOpt("disable-x86-lea-opt", cl::Hidden, cl::desc("X86: Disable LEA optimizations."), cl::init(false))

static bool isLEA(const MachineInstr &MI)

Returns true if the instruction is LEA.

Definition X86OptimizeLEAs.cpp:231

static bool isValidDispOp(const MachineOperand &MO)

Definition X86OptimizeLEAs.cpp:207

static MemOpKey getMemOpKey(const MachineInstr &MI, unsigned N)

Returns a hash table key based on memory operands of MI.

Definition X86OptimizeLEAs.cpp:191

static bool isSimilarDispOp(const MachineOperand &MO1, const MachineOperand &MO2)

Returns true if two address displacement operands are of the same type and use the same symbol/index/...

Definition X86OptimizeLEAs.cpp:213

static bool isIdenticalOp(const MachineOperand &MO1, const MachineOperand &MO2)

Returns true if two machine operands are identical and they are not physical registers.

Definition X86OptimizeLEAs.cpp:201

AnalysisUsage & addRequired()

static LLVM_ABI void appendOffset(SmallVectorImpl< uint64_t > &Ops, int64_t Offset)

Append Ops with operations to apply the Offset.

static LLVM_ABI DIExpression * appendOpsToArg(const DIExpression *Expr, ArrayRef< uint64_t > Ops, unsigned ArgNo, bool StackValue=false)

Create a copy of Expr by appending the given list of Ops to each instance of the operand DW_OP_LLVM_a...

static LLVM_ABI DIExpression * prepend(const DIExpression *Expr, uint8_t Flags, int64_t Offset=0)

Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value or/and an ...

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

const MCInstrDesc & get(unsigned Opcode) const

Return the machine instruction descriptor that corresponds to the specified instruction opcode.

LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)

Insert MI into the instruction list before I, possibly inside a bundle.

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

LLVM_ABI instr_iterator erase(instr_iterator I)

Remove an instruction from the instruction list and delete it.

MachineInstrBundleIterator< MachineInstr > iterator

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

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Function & getFunction()

Return the LLVM function that this machine code represents.

Representation of each machine instruction.

LLVM_ABI MachineInstr * removeFromParent()

Unlink 'this' from the containing basic block, and return it without deleting it.

const MachineOperand & getOperand(unsigned i) const

MachineOperand class - Representation of each machine instruction operand.

const GlobalValue * getGlobal() const

bool isReg() const

isReg - Tests if this is a MO_Register operand.

MachineBasicBlock * getMBB() const

bool isCPI() const

isCPI - Tests if this is a MO_ConstantPoolIndex operand.

LLVM_ABI void setReg(Register Reg)

Change the register this operand corresponds to.

bool isImm() const

isImm - Tests if this is a MO_Immediate operand.

bool isSymbol() const

isSymbol - Tests if this is a MO_ExternalSymbol operand.

bool isJTI() const

isJTI - Tests if this is a MO_JumpTableIndex operand.

const BlockAddress * getBlockAddress() const

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

bool isGlobal() const

isGlobal - Tests if this is a MO_GlobalAddress operand.

MachineOperandType getType() const

getType - Returns the MachineOperandType for this operand.

const char * getSymbolName() const

bool isBlockAddress() const

isBlockAddress - Tests if this is a MO_BlockAddress operand.

getReg - Returns the register number.

LLVM_ABI bool isIdenticalTo(const MachineOperand &Other) const

Returns true if this operand is identical to the specified operand except for liveness related flags ...

MCSymbol * getMCSymbol() const

@ MO_Immediate

Immediate operand.

@ MO_ConstantPoolIndex

Address of indexed Constant in Constant Pool.

@ MO_MCSymbol

MCSymbol reference (for debug/eh info)

@ MO_GlobalAddress

Address of a global value.

@ MO_BlockAddress

Address of a basic block.

@ MO_MachineBasicBlock

MachineBasicBlock reference.

@ MO_ExternalSymbol

Name of external global symbol.

@ MO_JumpTableIndex

Address of indexed Jump Table for switch.

static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)

int64_t getOffset() const

Return the offset from the symbol in this operand.

bool isMBB() const

isMBB - Tests if this is a MO_MachineBasicBlock operand.

constexpr bool isPhysical() const

Return true if the specified register number is in the physical register namespace.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

virtual const TargetRegisterClass * getRegClass(const MCInstrDesc &MCID, unsigned OpNum) const

Given a machine instruction descriptor, returns the register class constraint for OpNum,...

An opaque object representing a hash code.

#define llvm_unreachable(msg)

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

int getMemoryOperandNo(uint64_t TSFlags)

unsigned getOperandBias(const MCInstrDesc &Desc)

Compute whether all of the def operands are repeated in the uses and therefore should be skipped.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

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

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

constexpr bool isInt(int64_t x)

Checks if an integer fits into the given bit width.

LLVM_ABI bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)

Returns true if machine function MF is suggested to be size-optimized based on the profile.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

class LLVM_GSL_OWNER SmallVector

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

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

DWARFExpression::Operation Op

FunctionPass * createX86OptimizeLEAs()

Return a pass that removes redundant LEA instructions and redundant address recalculations.

Definition X86OptimizeLEAs.cpp:314

hash_code hash_combine(const Ts &...args)

Combine values into a single hash_code.

static unsigned getHashValue(const MemOpKey &Val)

Definition X86OptimizeLEAs.cpp:133

static MemOpKey getEmptyKey()

Definition X86OptimizeLEAs.cpp:121

DenseMapInfo< const MachineOperand * > PtrInfo

Definition X86OptimizeLEAs.cpp:119

static bool isEqual(const MemOpKey &LHS, const MemOpKey &RHS)

Definition X86OptimizeLEAs.cpp:176

static MemOpKey getTombstoneKey()

Definition X86OptimizeLEAs.cpp:127

An information struct used to provide DenseMap with the various necessary components for a given valu...