Movatterモバイル変換

Go to the documentation of this file.

1//===-- X86PartialReduction.cpp -------------------------------------------===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// This pass looks for add instructions used by a horizontal reduction to see

10// if we might be able to use pmaddwd or psadbw. Some cases of this require

11// cross basic block knowledge and can't be done in SelectionDAG.

12//

13//===----------------------------------------------------------------------===//

15#include "X86.h"

16#include "X86TargetMachine.h"

17#include "llvm/Analysis/ValueTracking.h"

18#include "llvm/CodeGen/TargetPassConfig.h"

19#include "llvm/IR/Constants.h"

20#include "llvm/IR/IRBuilder.h"

21#include "llvm/IR/Instructions.h"

22#include "llvm/IR/IntrinsicsX86.h"

23#include "llvm/IR/PatternMatch.h"

24#include "llvm/Pass.h"

25#include "llvm/Support/KnownBits.h"

27using namespacellvm;

29#define DEBUG_TYPE "x86-partial-reduction"

31namespace{

33classX86PartialReduction :publicFunctionPass {

34constDataLayout *DL =nullptr;

35constX86Subtarget *ST =nullptr;

37public:

38staticcharID;// Pass identification, replacement for typeid.

40 X86PartialReduction() :FunctionPass(ID) { }

42boolrunOnFunction(Function &Fn)override;

44voidgetAnalysisUsage(AnalysisUsage &AU) const override{

45 AU.setPreservesCFG();

46 }

48StringRef getPassName() const override{

49return"X86 Partial Reduction";

50 }

52private:

53bool tryMAddReplacement(Instruction *Op,bool ReduceInOneBB);

54bool trySADReplacement(Instruction *Op);

55};

56}

58FunctionPass *llvm::createX86PartialReductionPass() {

59returnnew X86PartialReduction();

60}

62char X86PartialReduction::ID = 0;

64INITIALIZE_PASS(X86PartialReduction,DEBUG_TYPE,

65"X86 Partial Reduction",false,false)

67// This function should be aligned with detectExtMul() in X86ISelLowering.cpp.

68staticbool matchVPDPBUSDPattern(const X86Subtarget *ST,BinaryOperator *Mul,

69const DataLayout *DL) {

70if (!ST->hasVNNI() && !ST->hasAVXVNNI())

71returnfalse;

73Value *LHS =Mul->getOperand(0);

74Value *RHS =Mul->getOperand(1);

76if (isa<SExtInst>(LHS))

77std::swap(LHS,RHS);

79autoIsFreeTruncation = [&](Value *Op) {

80if (auto *Cast = dyn_cast<CastInst>(Op)) {

81if (Cast->getParent() ==Mul->getParent() &&

82 (Cast->getOpcode() == Instruction::SExt ||

83 Cast->getOpcode() == Instruction::ZExt) &&

84 Cast->getOperand(0)->getType()->getScalarSizeInBits() <= 8)

85returntrue;

86 }

88return isa<Constant>(Op);

89 };

91// (dpbusd (zext a), (sext, b)). Since the first operand should be unsigned

92// value, we need to check LHS is zero extended value. RHS should be signed

93// value, so we just check the signed bits.

94if ((IsFreeTruncation(LHS) &&

95computeKnownBits(LHS, *DL).countMaxActiveBits() <= 8) &&

96 (IsFreeTruncation(RHS) &&ComputeMaxSignificantBits(RHS, *DL) <= 8))

97returntrue;

99returnfalse;

100}

101

102bool X86PartialReduction::tryMAddReplacement(Instruction *Op,

103bool ReduceInOneBB) {

104if (!ST->hasSSE2())

105returnfalse;

106

107// Need at least 8 elements.

108if (cast<FixedVectorType>(Op->getType())->getNumElements() < 8)

109returnfalse;

110

111// Element type should be i32.

112if (!cast<VectorType>(Op->getType())->getElementType()->isIntegerTy(32))

113returnfalse;

114

115auto *Mul = dyn_cast<BinaryOperator>(Op);

116if (!Mul ||Mul->getOpcode() != Instruction::Mul)

117returnfalse;

118

119Value *LHS =Mul->getOperand(0);

120Value *RHS =Mul->getOperand(1);

121

122// If the target support VNNI, leave it to ISel to combine reduce operation

123// to VNNI instruction.

124// TODO: we can support transforming reduce to VNNI intrinsic for across block

125// in this pass.

126if (ReduceInOneBB && matchVPDPBUSDPattern(ST,Mul,DL))

127returnfalse;

128

129// LHS and RHS should be only used once or if they are the same then only

130// used twice. Only check this when SSE4.1 is enabled and we have zext/sext

131// instructions, otherwise we use punpck to emulate zero extend in stages. The

132// trunc/ we need to do likely won't introduce new instructions in that case.

133if (ST->hasSSE41()) {

134if (LHS ==RHS) {

135if (!isa<Constant>(LHS) && !LHS->hasNUses(2))

136returnfalse;

137 }else {

138if (!isa<Constant>(LHS) && !LHS->hasOneUse())

139returnfalse;

140if (!isa<Constant>(RHS) && !RHS->hasOneUse())

141returnfalse;

142 }

143 }

144

145auto CanShrinkOp = [&](Value *Op) {

146autoIsFreeTruncation = [&](Value *Op) {

147if (auto *Cast = dyn_cast<CastInst>(Op)) {

148if (Cast->getParent() ==Mul->getParent() &&

149 (Cast->getOpcode() == Instruction::SExt ||

150 Cast->getOpcode() == Instruction::ZExt) &&

151 Cast->getOperand(0)->getType()->getScalarSizeInBits() <= 16)

152returntrue;

153 }

154

155return isa<Constant>(Op);

156 };

157

158// If the operation can be freely truncated and has enough sign bits we

159// can shrink.

160if (IsFreeTruncation(Op) &&

161ComputeNumSignBits(Op, *DL, 0,nullptr,Mul) > 16)

162returntrue;

163

164// SelectionDAG has limited support for truncating through an add or sub if

165// the inputs are freely truncatable.

166if (auto *BO = dyn_cast<BinaryOperator>(Op)) {

167if (BO->getParent() ==Mul->getParent() &&

168IsFreeTruncation(BO->getOperand(0)) &&

169IsFreeTruncation(BO->getOperand(1)) &&

170ComputeNumSignBits(Op, *DL, 0,nullptr,Mul) > 16)

171returntrue;

172 }

173

174returnfalse;

175 };

176

177// Both Ops need to be shrinkable.

178if (!CanShrinkOp(LHS) && !CanShrinkOp(RHS))

179returnfalse;

180

181IRBuilder<> Builder(Mul);

182

183auto *MulTy = cast<FixedVectorType>(Op->getType());

184unsigned NumElts = MulTy->getNumElements();

185

186// Extract even elements and odd elements and add them together. This will

187// be pattern matched by SelectionDAG to pmaddwd. This instruction will be

188// half the original width.

189SmallVector<int, 16> EvenMask(NumElts / 2);

190SmallVector<int, 16> OddMask(NumElts / 2);

191for (int i = 0, e = NumElts / 2; i !=e; ++i) {

192 EvenMask[i] = i * 2;

193 OddMask[i] = i * 2 + 1;

194 }

195// Creating a new mul so the replaceAllUsesWith below doesn't replace the

196// uses in the shuffles we're creating.

197Value *NewMul = Builder.CreateMul(Mul->getOperand(0),Mul->getOperand(1));

198Value *EvenElts = Builder.CreateShuffleVector(NewMul, NewMul, EvenMask);

199Value *OddElts = Builder.CreateShuffleVector(NewMul, NewMul, OddMask);

200Value *MAdd = Builder.CreateAdd(EvenElts, OddElts);

201

202// Concatenate zeroes to extend back to the original type.

203SmallVector<int, 32> ConcatMask(NumElts);

204 std::iota(ConcatMask.begin(), ConcatMask.end(), 0);

205Value *Zero =Constant::getNullValue(MAdd->getType());

206Value *Concat = Builder.CreateShuffleVector(MAdd, Zero, ConcatMask);

207

208Mul->replaceAllUsesWith(Concat);

209Mul->eraseFromParent();

210

211returntrue;

212}

213

214bool X86PartialReduction::trySADReplacement(Instruction *Op) {

215if (!ST->hasSSE2())

216returnfalse;

217

218// TODO: There's nothing special about i32, any integer type above i16 should

219// work just as well.

220if (!cast<VectorType>(Op->getType())->getElementType()->isIntegerTy(32))

221returnfalse;

222

223Value *LHS;

224if (match(Op, PatternMatch::m_Intrinsic<Intrinsic::abs>())) {

225LHS =Op->getOperand(0);

226 }else {

227// Operand should be a select.

228auto *SI = dyn_cast<SelectInst>(Op);

229if (!SI)

230returnfalse;

231

232Value *RHS;

233// Select needs to implement absolute value.

234auto SPR =matchSelectPattern(SI,LHS,RHS);

235if (SPR.Flavor !=SPF_ABS)

236returnfalse;

237 }

238

239// Need a subtract of two values.

240auto *Sub = dyn_cast<BinaryOperator>(LHS);

241if (!Sub || Sub->getOpcode() != Instruction::Sub)

242returnfalse;

243

244// Look for zero extend from i8.

245auto getZeroExtendedVal = [](Value *Op) ->Value * {

246if (auto *ZExt = dyn_cast<ZExtInst>(Op))

247if (cast<VectorType>(ZExt->getOperand(0)->getType())

248 ->getElementType()

249 ->isIntegerTy(8))

250return ZExt->getOperand(0);

251

252returnnullptr;

253 };

254

255// Both operands of the subtract should be extends from vXi8.

256Value *Op0 = getZeroExtendedVal(Sub->getOperand(0));

257Value *Op1 = getZeroExtendedVal(Sub->getOperand(1));

258if (!Op0 || !Op1)

259returnfalse;

260

261IRBuilder<> Builder(Op);

262

263auto *OpTy = cast<FixedVectorType>(Op->getType());

264unsigned NumElts = OpTy->getNumElements();

265

266unsigned IntrinsicNumElts;

267Intrinsic::ID IID;

268if (ST->hasBWI() && NumElts >= 64) {

269 IID = Intrinsic::x86_avx512_psad_bw_512;

270 IntrinsicNumElts = 64;

271 }elseif (ST->hasAVX2() && NumElts >= 32) {

272 IID = Intrinsic::x86_avx2_psad_bw;

273 IntrinsicNumElts = 32;

274 }else {

275 IID = Intrinsic::x86_sse2_psad_bw;

276 IntrinsicNumElts = 16;

277 }

278

279Function *PSADBWFn =Intrinsic::getOrInsertDeclaration(Op->getModule(), IID);

280

281if (NumElts < 16) {

282// Pad input with zeroes.

283SmallVector<int, 32> ConcatMask(16);

284for (unsigned i = 0; i != NumElts; ++i)

285 ConcatMask[i] = i;

286for (unsigned i = NumElts; i != 16; ++i)

287 ConcatMask[i] = (i % NumElts) + NumElts;

288

289Value *Zero =Constant::getNullValue(Op0->getType());

290 Op0 = Builder.CreateShuffleVector(Op0, Zero, ConcatMask);

291 Op1 = Builder.CreateShuffleVector(Op1, Zero, ConcatMask);

292 NumElts = 16;

293 }

294

295// Intrinsics produce vXi64 and need to be casted to vXi32.

296auto *I32Ty =

297FixedVectorType::get(Builder.getInt32Ty(), IntrinsicNumElts / 4);

298

299assert(NumElts % IntrinsicNumElts == 0 &&"Unexpected number of elements!");

300unsigned NumSplits = NumElts / IntrinsicNumElts;

301

302// First collect the pieces we need.

303SmallVector<Value *, 4> Ops(NumSplits);

304for (unsigned i = 0; i != NumSplits; ++i) {

305SmallVector<int, 64> ExtractMask(IntrinsicNumElts);

306 std::iota(ExtractMask.begin(), ExtractMask.end(), i * IntrinsicNumElts);

307Value *ExtractOp0 = Builder.CreateShuffleVector(Op0, Op0, ExtractMask);

308Value *ExtractOp1 = Builder.CreateShuffleVector(Op1, Op0, ExtractMask);

309 Ops[i] = Builder.CreateCall(PSADBWFn, {ExtractOp0, ExtractOp1});

310 Ops[i] = Builder.CreateBitCast(Ops[i], I32Ty);

311 }

312

313assert(isPowerOf2_32(NumSplits) &&"Expected power of 2 splits");

314unsigned Stages =Log2_32(NumSplits);

315for (unsigned s = Stages; s > 0; --s) {

316unsigned NumConcatElts =

317 cast<FixedVectorType>(Ops[0]->getType())->getNumElements() * 2;

318for (unsigned i = 0; i != 1U << (s - 1); ++i) {

319SmallVector<int, 64> ConcatMask(NumConcatElts);

320 std::iota(ConcatMask.begin(), ConcatMask.end(), 0);

321 Ops[i] = Builder.CreateShuffleVector(Ops[i*2], Ops[i*2+1], ConcatMask);

322 }

323 }

324

325// At this point the final value should be in Ops[0]. Now we need to adjust

326// it to the final original type.

327 NumElts = cast<FixedVectorType>(OpTy)->getNumElements();

328if (NumElts == 2) {

329// Extract down to 2 elements.

330 Ops[0] = Builder.CreateShuffleVector(Ops[0], Ops[0],ArrayRef<int>{0, 1});

331 }elseif (NumElts >= 8) {

332SmallVector<int, 32> ConcatMask(NumElts);

333unsigned SubElts =

334 cast<FixedVectorType>(Ops[0]->getType())->getNumElements();

335for (unsigned i = 0; i != SubElts; ++i)

336 ConcatMask[i] = i;

337for (unsigned i = SubElts; i != NumElts; ++i)

338 ConcatMask[i] = (i % SubElts) + SubElts;

339

340Value *Zero =Constant::getNullValue(Ops[0]->getType());

341 Ops[0] = Builder.CreateShuffleVector(Ops[0], Zero, ConcatMask);

342 }

343

344Op->replaceAllUsesWith(Ops[0]);

345Op->eraseFromParent();

346

347returntrue;

348}

349

350// Walk backwards from the ExtractElementInst and determine if it is the end of

351// a horizontal reduction. Return the input to the reduction if we find one.

352staticValue *matchAddReduction(constExtractElementInst &EE,

353bool &ReduceInOneBB) {

354 ReduceInOneBB =true;

355// Make sure we're extracting index 0.

356auto *Index = dyn_cast<ConstantInt>(EE.getIndexOperand());

357if (!Index || !Index->isNullValue())

358returnnullptr;

359

360constauto *BO = dyn_cast<BinaryOperator>(EE.getVectorOperand());

361if (!BO || BO->getOpcode() != Instruction::Add || !BO->hasOneUse())

362returnnullptr;

363if (EE.getParent() != BO->getParent())

364 ReduceInOneBB =false;

365

366unsigned NumElems = cast<FixedVectorType>(BO->getType())->getNumElements();

367// Ensure the reduction size is a power of 2.

368if (!isPowerOf2_32(NumElems))

369returnnullptr;

370

371constValue *Op = BO;

372unsigned Stages =Log2_32(NumElems);

373for (unsigned i = 0; i != Stages; ++i) {

374constauto *BO = dyn_cast<BinaryOperator>(Op);

375if (!BO || BO->getOpcode() != Instruction::Add)

376returnnullptr;

377if (EE.getParent() != BO->getParent())

378 ReduceInOneBB =false;

379

380// If this isn't the first add, then it should only have 2 users, the

381// shuffle and another add which we checked in the previous iteration.

382if (i != 0 && !BO->hasNUses(2))

383returnnullptr;

384

385Value *LHS = BO->getOperand(0);

386Value *RHS = BO->getOperand(1);

387

388auto *Shuffle = dyn_cast<ShuffleVectorInst>(LHS);

389if (Shuffle) {

390Op =RHS;

391 }else {

392 Shuffle = dyn_cast<ShuffleVectorInst>(RHS);

393Op =LHS;

394 }

395

396// The first operand of the shuffle should be the same as the other operand

397// of the bin op.

398if (!Shuffle || Shuffle->getOperand(0) !=Op)

399returnnullptr;

400

401// Verify the shuffle has the expected (at this stage of the pyramid) mask.

402unsigned MaskEnd = 1 << i;

403for (unsigned Index = 0; Index < MaskEnd; ++Index)

404if (Shuffle->getMaskValue(Index) != (int)(MaskEnd + Index))

405returnnullptr;

406 }

407

408returnconst_cast<Value *>(Op);

409}

410

411// See if this BO is reachable from this Phi by walking forward through single

412// use BinaryOperators with the same opcode. If we get back then we know we've

413// found a loop and it is safe to step through this Add to find more leaves.

414staticboolisReachableFromPHI(PHINode *Phi,BinaryOperator *BO) {

415// The PHI itself should only have one use.

416if (!Phi->hasOneUse())

417returnfalse;

418

419Instruction *U = cast<Instruction>(*Phi->user_begin());

420if (U == BO)

421returntrue;

422

423while (U->hasOneUse() && U->getOpcode() == BO->getOpcode())

424 U = cast<Instruction>(*U->user_begin());

425

426return U == BO;

427}

428

429// Collect all the leaves of the tree of adds that feeds into the horizontal

430// reduction. Root is the Value that is used by the horizontal reduction.

431// We look through single use phis, single use adds, or adds that are used by

432// a phi that forms a loop with the add.

433staticvoidcollectLeaves(Value *Root,SmallVectorImpl<Instruction *> &Leaves) {

434SmallPtrSet<Value *, 8> Visited;

435SmallVector<Value *, 8> Worklist;

436 Worklist.push_back(Root);

437

438while (!Worklist.empty()) {

439Value *V = Worklist.pop_back_val();

440if (!Visited.insert(V).second)

441continue;

442

443if (auto *PN = dyn_cast<PHINode>(V)) {

444// PHI node should have single use unless it is the root node, then it

445// has 2 uses.

446if (!PN->hasNUses(PN == Root ? 2 : 1))

447break;

448

449// Push incoming values to the worklist.

450append_range(Worklist, PN->incoming_values());

451

452continue;

453 }

454

455if (auto *BO = dyn_cast<BinaryOperator>(V)) {

456if (BO->getOpcode() == Instruction::Add) {

457// Simple case. Single use, just push its operands to the worklist.

458if (BO->hasNUses(BO == Root ? 2 : 1)) {

459append_range(Worklist, BO->operands());

460continue;

461 }

462

463// If there is additional use, make sure it is an unvisited phi that

464// gets us back to this node.

465if (BO->hasNUses(BO == Root ? 3 : 2)) {

466PHINode *PN =nullptr;

467for (auto *U : BO->users())

468if (auto *P = dyn_cast<PHINode>(U))

469if (!Visited.count(P))

470 PN =P;

471

472// If we didn't find a 2-input PHI then this isn't a case we can

473// handle.

474if (!PN || PN->getNumIncomingValues() != 2)

475continue;

476

477// Walk forward from this phi to see if it reaches back to this add.

478if (!isReachableFromPHI(PN, BO))

479continue;

480

481// The phi forms a loop with this Add, push its operands.

482append_range(Worklist, BO->operands());

483 }

484 }

485 }

486

487// Not an add or phi, make it a leaf.

488if (auto *I = dyn_cast<Instruction>(V)) {

489if (!V->hasNUses(I == Root ? 2 : 1))

490continue;

491

492// Add this as a leaf.

493 Leaves.push_back(I);

494 }

495 }

496}

497

498bool X86PartialReduction::runOnFunction(Function &F) {

499if (skipFunction(F))

500returnfalse;

501

502auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();

503if (!TPC)

504returnfalse;

505

506auto &TM = TPC->getTM<X86TargetMachine>();

507ST =TM.getSubtargetImpl(F);

508

509DL = &F.getDataLayout();

510

511bool MadeChange =false;

512for (auto &BB :F) {

513for (auto &I : BB) {

514auto *EE = dyn_cast<ExtractElementInst>(&I);

515if (!EE)

516continue;

517

518bool ReduceInOneBB;

519// First find a reduction tree.

520// FIXME: Do we need to handle other opcodes than Add?

521Value *Root =matchAddReduction(*EE, ReduceInOneBB);

522if (!Root)

523continue;

524

525SmallVector<Instruction *, 8> Leaves;

526collectLeaves(Root, Leaves);

527

528for (Instruction *I : Leaves) {

529if (tryMAddReplacement(I, ReduceInOneBB)) {

530 MadeChange =true;

531continue;

532 }

533

534// Don't do SAD matching on the root node. SelectionDAG already

535// has support for that and currently generates better code.

536if (I != Root && trySADReplacement(I))

537 MadeChange =true;

538 }

539 }

540 }

541

542return MadeChange;

543}

const

aarch64 promote const

Definition:AArch64PromoteConstant.cpp:230

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Definition:ARMSLSHardening.cpp:73

Constants.h

This file contains the declarations for the subclasses of Constant, which represent the different fla...

IRBuilder.h

Instructions.h

KnownBits.h

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

#define P(N)

INITIALIZE_PASS

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

Definition:PassSupport.h:38

Pass.h

PatternMatch.h

assert

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

getType

static SymbolRef::Type getType(const Symbol *Sym)

Definition:TapiFile.cpp:39

TargetPassConfig.h

Target-Independent Code Generator Pass Configuration Options pass.

ValueTracking.h

Concat

static constexpr int Concat[]

Definition:X86InterleavedAccess.cpp:232

isReachableFromPHI

static bool isReachableFromPHI(PHINode *Phi, BinaryOperator *BO)

Definition:X86PartialReduction.cpp:414

BinaryOperator const DataLayout * DL

Definition:X86PartialReduction.cpp:69

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

LHS

Value * LHS

Definition:X86PartialReduction.cpp:73

DEBUG_TYPE

#define DEBUG_TYPE

Definition:X86PartialReduction.cpp:29

Mul

BinaryOperator * Mul

Definition:X86PartialReduction.cpp:68

IsFreeTruncation

if(isa< SExtInst >(LHS)) std auto IsFreeTruncation

Definition:X86PartialReduction.cpp:79

matchAddReduction

static Value * matchAddReduction(const ExtractElementInst &EE, bool &ReduceInOneBB)

Definition:X86PartialReduction.cpp:352

collectLeaves

static void collectLeaves(Value *Root, SmallVectorImpl< Instruction * > &Leaves)

Definition:X86PartialReduction.cpp:433

X86TargetMachine.h

X86.h

llvm::AnalysisUsage

Represent the analysis usage information of a pass.

Definition:PassAnalysisSupport.h:47

llvm::AnalysisUsage::setPreservesCFG

void setPreservesCFG()

This function should be called by the pass, iff they do not:

Definition:Pass.cpp:256

llvm::ArrayRef

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Definition:ArrayRef.h:41

llvm::BinaryOperator

Definition:InstrTypes.h:170

llvm::BinaryOperator::getOpcode

BinaryOps getOpcode() const

Definition:InstrTypes.h:370

llvm::Constant::getNullValue

static Constant * getNullValue(Type *Ty)

Constructor to create a '0' constant of arbitrary type.

Definition:Constants.cpp:373

llvm::DWARFExpression::Operation

This class represents an Operation in the Expression.

Definition:DWARFExpression.h:32

llvm::DataLayout

A parsed version of the target data layout string in and methods for querying it.

Definition:DataLayout.h:63

llvm::ExtractElementInst

This instruction extracts a single (scalar) element from a VectorType value.

Definition:Instructions.h:1775

llvm::ExtractElementInst::getVectorOperand

Value * getVectorOperand()

Definition:Instructions.h:1799

llvm::ExtractElementInst::getIndexOperand

Value * getIndexOperand()

Definition:Instructions.h:1800

llvm::FixedVectorType::get

static FixedVectorType * get(Type *ElementType, unsigned NumElts)

Definition:Type.cpp:791

llvm::FunctionPass

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

Definition:Pass.h:310

llvm::FunctionPass::runOnFunction

virtual bool runOnFunction(Function &F)=0

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

llvm::Function

Definition:Function.h:63

llvm::IRBuilder

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

Definition:IRBuilder.h:2705

llvm::Instruction

Definition:Instruction.h:68

llvm::Instruction::eraseFromParent

InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

Definition:Instruction.cpp:94

llvm::PHINode

Definition:Instructions.h:2600

llvm::PHINode::getNumIncomingValues

unsigned getNumIncomingValues() const

Return the number of incoming edges.

Definition:Instructions.h:2671

llvm::Pass::getAnalysisUsage

virtual void getAnalysisUsage(AnalysisUsage &) const

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

Definition:Pass.cpp:98

llvm::Pass::getPassName

virtual StringRef getPassName() const

getPassName - Return a nice clean name for a pass.

Definition:Pass.cpp:81

llvm::SmallPtrSetImpl::count

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

Definition:SmallPtrSet.h:452

llvm::SmallPtrSetImpl::insert

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

Definition:SmallPtrSet.h:384

llvm::SmallPtrSet

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

Definition:SmallPtrSet.h:519

llvm::SmallVectorBase::empty

bool empty() const

Definition:SmallVector.h:81

llvm::SmallVectorImpl

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

Definition:SmallVector.h:573

llvm::SmallVectorImpl::pop_back_val

T pop_back_val()

Definition:SmallVector.h:673

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVector

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Definition:SmallVector.h:1196

llvm::StringRef

StringRef - Represent a constant reference to a string, i.e.

Definition:StringRef.h:51

llvm::User::getOperand

Value * getOperand(unsigned i) const

Definition:User.h:228

llvm::Value

LLVM Value Representation.

Definition:Value.h:74

llvm::Value::getType

Type * getType() const

All values are typed, get the type of this value.

Definition:Value.h:255

llvm::Value::hasOneUse

bool hasOneUse() const

Return true if there is exactly one use of this value.

Definition:Value.h:434

llvm::Value::replaceAllUsesWith

void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

Definition:Value.cpp:534

llvm::Value::hasNUses

bool hasNUses(unsigned N) const

Return true if this Value has exactly N uses.

Definition:Value.cpp:149

llvm::X86Subtarget

Definition:X86Subtarget.h:53

llvm::X86TargetMachine

Definition:X86TargetMachine.h:28

llvm::ilist_detail::node_parent_access::getParent

const ParentTy * getParent() const

Definition:ilist_node.h:32

unsigned

llvm::ARM_MB::ST

@ ST

Definition:ARMBaseInfo.h:73

llvm::CallingConv::ID

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

Definition:CallingConv.h:24

llvm::Intrinsic::getOrInsertDeclaration

Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})

Look up the Function declaration of the intrinsic id in the Module M.

Definition:Intrinsics.cpp:732

llvm::MipsISD::MAdd

@ MAdd

Definition:MipsISelLowering.h:137

llvm::PatternMatch::match

bool match(Val *V, const Pattern &P)

Definition:PatternMatch.h:49

llvm::SIEncodingFamily::SI

@ SI

Definition:SIDefines.h:36

llvm::SystemZISD::TM

@ TM

Definition:SystemZISelLowering.h:66

llvm::logicalview::LVAttributeKind::Zero

@ Zero

llvm::numbers::e

constexpr double e

Definition:MathExtras.h:47

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::append_range

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

Definition:STLExtras.h:2115

llvm::Log2_32

unsigned Log2_32(uint32_t Value)

Return the floor log base 2 of the specified value, -1 if the value is zero.

Definition:MathExtras.h:341

llvm::SPF_ABS

@ SPF_ABS

Floating point maxnum.

Definition:ValueTracking.h:1121

llvm::isPowerOf2_32

constexpr bool isPowerOf2_32(uint32_t Value)

Return true if the argument is a power of two > 0.

Definition:MathExtras.h:292

llvm::matchSelectPattern

SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)

Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...

Definition:ValueTracking.cpp:9047

llvm::createX86PartialReductionPass

FunctionPass * createX86PartialReductionPass()

This pass optimizes arithmetic based on knowledge that is only used by a reduction sequence and is th...

Definition:X86PartialReduction.cpp:58

llvm::computeKnownBits

void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)

Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...

Definition:ValueTracking.cpp:164

llvm::Op

DWARFExpression::Operation Op

Definition:DWARFExpression.cpp:22

llvm::ComputeNumSignBits

unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)

Return the number of times the sign bit of the register is replicated into the other bits.

Definition:ValueTracking.cpp:351

llvm::ComputeMaxSignificantBits

unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)

Get the upper bound on bit size for this Value Op as a signed integer.

Definition:ValueTracking.cpp:359

std::swap

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

Definition:BitVector.h:860