X86PartialReduction.cpp Source File (original) (raw)

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

29using namespace llvm;

31#define DEBUG_TYPE "x86-partial-reduction"

33namespace {

35class X86PartialReduction {

40public:

44private:

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

47};

49class X86PartialReductionLegacy : public FunctionPass {

50public:

51 static char ID;

57 void getAnalysisUsage(AnalysisUsage &AU) const override {

59 }

61 StringRef getPassName() const override { return "X86 Partial Reduction"; }

62};

63}

66 return new X86PartialReductionLegacy();

67}

69char X86PartialReductionLegacy::ID = 0;

72 false, false)

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

78 return false;

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

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

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

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

92 return true;

93 }

96 };

100

104 return true;

105

106 return false;

107}

108

109bool X86PartialReduction::tryMAddReplacement(Instruction *Op,

110 bool ReduceInOneBB) {

111 if (->hasSSE2())

112 return false;

113

114

116 return false;

117

118

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

120 return false;

121

124 return false;

125

128

129

130

131

132

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

134 return false;

135

136

137

138

139

140 if (ST->hasSSE41()) {

143 return false;

144 } else {

146 return false;

148 return false;

149 }

150 }

151

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

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

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

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

159 return true;

160 }

161

163 };

164

165

166

168 return true;

169

170

171

177 return true;

178 }

179

180 return false;

181 };

182

183

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

185 return false;

186

188

190 unsigned NumElts = MulTy->getNumElements();

191

192

193

194

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

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

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

198 EvenMask[i] = i * 2;

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

200 }

201

202

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

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

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

207

208

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

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

213

216

217 return true;

218}

219

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

221 if (->hasSSE2())

222 return false;

223

224

225

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

227 return false;

228

231 LHS = Op->getOperand(0);

232 } else {

233

235 if (!SI)

236 return false;

237

239

241 if (SPR.Flavor != SPF_ABS)

242 return false;

243 }

244

245

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

248 return false;

249

250

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

254 ->getElementType()

255 ->isIntegerTy(8))

256 return ZExt->getOperand(0);

257

258 return nullptr;

259 };

260

261

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

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

264 if (!Op0 || !Op1)

265 return false;

266

268

270 unsigned NumElts = OpTy->getNumElements();

271

272 unsigned IntrinsicNumElts;

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

275 IID = Intrinsic::x86_avx512_psad_bw_512;

276 IntrinsicNumElts = 64;

277 } else if (ST->hasAVX2() && NumElts >= 32) {

278 IID = Intrinsic::x86_avx2_psad_bw;

279 IntrinsicNumElts = 32;

280 } else {

281 IID = Intrinsic::x86_sse2_psad_bw;

282 IntrinsicNumElts = 16;

283 }

284

286

287 if (NumElts < 16) {

288

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

291 ConcatMask[i] = i;

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

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

294

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

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

298 NumElts = 16;

299 }

300

301

302 auto *I32Ty =

304

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

306 unsigned NumSplits = NumElts / IntrinsicNumElts;

307

308

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

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

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

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

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

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

317 }

318

320 unsigned Stages = Log2_32(NumSplits);

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

322 unsigned NumConcatElts =

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

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

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

328 }

329 }

330

331

332

334 if (NumElts == 2) {

335

336 Ops[0] = Builder.CreateShuffleVector(Ops[0], Ops[0], ArrayRef{0, 1});

337 } else if (NumElts >= 8) {

339 unsigned SubElts =

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

342 ConcatMask[i] = i;

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

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

345

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

348 }

349

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

351 Op->eraseFromParent();

352

353 return true;

354}

355

356

357

359 bool &ReduceInOneBB) {

360 ReduceInOneBB = true;

361

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

364 return nullptr;

365

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

368 return nullptr;

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

370 ReduceInOneBB = false;

371

373

375 return nullptr;

376

378 unsigned Stages = Log2_32(NumElems);

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

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

382 return nullptr;

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

384 ReduceInOneBB = false;

385

386

387

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

389 return nullptr;

390

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

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

393

395 if (Shuffle) {

397 } else {

400 }

401

402

403

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

405 return nullptr;

406

407

408 unsigned MaskEnd = 1 << i;

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

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

411 return nullptr;

412 }

413

414 return const_cast<Value *>(Op);

415}

416

417

418

419

421

422 if (!Phi->hasOneUse())

423 return false;

424

426 if (U == BO)

427 return true;

428

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

431

432 return U == BO;

433}

434

435

436

437

438

443

444 while (!Worklist.empty()) {

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

447 continue;

448

450

451

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

453 break;

454

455

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

457

458 continue;

459 }

460

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

463

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

466 continue;

467 }

468

469

470

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

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

475 if (!Visited.count(P))

476 PN = P;

477

478

479

481 continue;

482

483

485 continue;

486

487

489 }

490 }

491 }

492

493

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

496 continue;

497

498

500 }

501 }

502}

503

504bool X86PartialReduction::run(Function &F) {

506 DL = &F.getDataLayout();

507

508 bool MadeChange = false;

509 for (auto &BB : F) {

510 for (auto &I : BB) {

512 if (!EE)

513 continue;

514

515 bool ReduceInOneBB;

516

517

519 if (!Root)

520 continue;

521

522 SmallVector<Instruction *, 8> Leaves;

524

525 for (Instruction *I : Leaves) {

526 if (tryMAddReplacement(I, ReduceInOneBB)) {

527 MadeChange = true;

528 continue;

529 }

530

531

532

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

534 MadeChange = true;

535 }

536 }

537 }

538

539 return MadeChange;

540}

541

542bool X86PartialReductionLegacy::runOnFunction(Function &F) {

543 if (skipFunction(F))

544 return false;

545

546 auto *TPC = getAnalysisIfAvailable();

547 if (!TPC)

548 return false;

549

550 return X86PartialReduction(&TPC->getTM()).run(F);

551}

552

555 bool Changed = X86PartialReduction(TM).run(F);

558

561 return PA;

562}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

static bool runOnFunction(Function &F, bool PostInlining)

This header defines various interfaces for pass management in LLVM.

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

FunctionAnalysisManager FAM

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

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

Target-Independent Code Generator Pass Configuration Options pass.

static constexpr int Concat[]

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

Definition X86PartialReduction.cpp:420

Value * RHS

Definition X86PartialReduction.cpp:81

Value * LHS

Definition X86PartialReduction.cpp:80

BinaryOperator * Mul

Definition X86PartialReduction.cpp:75

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

Definition X86PartialReduction.cpp:86

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

Definition X86PartialReduction.cpp:358

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

Definition X86PartialReduction.cpp:439

Represent the analysis usage information of a pass.

LLVM_ABI void setPreservesCFG()

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

BinaryOps getOpcode() const

Represents analyses that only rely on functions' control flow.

static LLVM_ABI Constant * getNullValue(Type *Ty)

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

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

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

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

LLVM_ABI InstListType::iterator eraseFromParent()

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

unsigned getNumIncomingValues() const

Return the number of incoming edges.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses none()

Convenience factory function for the empty preserved set.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserveSet()

Mark an analysis set as preserved.

size_type count(ConstPtrType Ptr) const

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

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

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

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

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

void push_back(const T &Elt)

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

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

Value * getOperand(unsigned i) const

LLVM Value Representation.

Type * getType() const

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

bool hasOneUse() const

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

LLVM_ABI void replaceAllUsesWith(Value *V)

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

LLVM_ABI bool hasNUses(unsigned N) const

Return true if this Value has exactly N uses.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)

Definition X86PartialReduction.cpp:553

const X86Subtarget * getSubtargetImpl(const Function &F) const override

Virtual method implemented by subclasses that returns a reference to that target's TargetSubtargetInf...

const ParentTy * getParent() const

Pass manager infrastructure for declaring and invalidating analyses.

unsigned ID

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

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

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

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

IntrinsicID_match m_Intrinsic()

Match intrinsic calls like this: m_IntrinsicIntrinsic::fabs(m_Value(X))

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

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

Wrapper function to append range R to container C.

FunctionPass * createX86PartialReductionLegacyPass()

Definition X86PartialReduction.cpp:65

unsigned Log2_32(uint32_t Value)

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

@ SPF_ABS

Floating point maxnum.

constexpr bool isPowerOf2_32(uint32_t Value)

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

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

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

LLVM_ABI 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...

class LLVM_GSL_OWNER SmallVector

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

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

@ Sub

Subtraction of integers.

DWARFExpression::Operation Op

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

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

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

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

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

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

Implement std::swap in terms of BitVector swap.