BottomUpVec.cpp Source File (original) (raw)

19namespace llvm {

21#ifndef NDEBUG

24 cl::desc("Helps find bugs by verifying the IR whenever we "

25 "emit new instructions (*very* expensive)."));

26#endif

29 std::numeric_limits::max();

32 cl::desc("Vectorize if the invocation count is < than this. 0 "

33 "disables vectorization."));

36 std::numeric_limits::max();

39 cl::desc("Vectorize up to this many bundles."));

46 for (Value *BndlV : Bndl) {

49 }

50 return Operands;

51}

58 if (BotI == nullptr)

60 return BB->empty()

62 : std::next(

64 return std::next(BotI->getIterator());

65}

72 "Expect Instructions!");

73 auto &Ctx = Bndl[0]->getContext();

82 switch (Opcode) {

83 case Instruction::Opcode::ZExt:

84 case Instruction::Opcode::SExt:

85 case Instruction::Opcode::FPToUI:

86 case Instruction::Opcode::FPToSI:

87 case Instruction::Opcode::FPExt:

88 case Instruction::Opcode::PtrToInt:

89 case Instruction::Opcode::IntToPtr:

90 case Instruction::Opcode::SIToFP:

91 case Instruction::Opcode::UIToFP:

92 case Instruction::Opcode::Trunc:

93 case Instruction::Opcode::FPTrunc:

94 case Instruction::Opcode::BitCast: {

95 assert(Operands.size() == 1u && "Casts are unary!");

96 return CastInst::create(VecTy, Opcode, Operands[0], WhereIt, Ctx,

97 "VCast");

98 }

99 case Instruction::Opcode::FCmp:

100 case Instruction::Opcode::ICmp: {

101 auto Pred = cast(Bndl[0])->getPredicate();

103 [Pred](auto *SBV) {

104 return cast(SBV)->getPredicate() == Pred;

105 }) &&

106 "Expected same predicate across bundle.");

107 return CmpInst::create(Pred, Operands[0], Operands[1], WhereIt, Ctx,

108 "VCmp");

109 }

110 case Instruction::Opcode::Select: {

111 return SelectInst::create(Operands[0], Operands[1], Operands[2], WhereIt,

112 Ctx, "Vec");

113 }

114 case Instruction::Opcode::FNeg: {

116 auto OpC = UOp0->getOpcode();

118 WhereIt, Ctx, "Vec");

119 }

120 case Instruction::Opcode::Add:

121 case Instruction::Opcode::FAdd:

122 case Instruction::Opcode::Sub:

123 case Instruction::Opcode::FSub:

124 case Instruction::Opcode::Mul:

125 case Instruction::Opcode::FMul:

126 case Instruction::Opcode::UDiv:

127 case Instruction::Opcode::SDiv:

128 case Instruction::Opcode::FDiv:

129 case Instruction::Opcode::URem:

130 case Instruction::Opcode::SRem:

131 case Instruction::Opcode::FRem:

132 case Instruction::Opcode::Shl:

133 case Instruction::Opcode::LShr:

134 case Instruction::Opcode::AShr:

135 case Instruction::Opcode::And:

136 case Instruction::Opcode::Or:

137 case Instruction::Opcode::Xor: {

139 auto *LHS = Operands[0];

140 auto *RHS = Operands[1];

142 BinOp0->getOpcode(), LHS, RHS, BinOp0, WhereIt, Ctx, "Vec");

143 }

144 case Instruction::Opcode::Load: {

146 Value *Ptr = Ld0->getPointerOperand();

147 return LoadInst::create(VecTy, Ptr, Ld0->getAlign(), WhereIt, Ctx,

148 "VecL");

149 }

150 case Instruction::Opcode::Store: {

152 Value *Val = Operands[0];

153 Value *Ptr = Operands[1];

155 }

156 case Instruction::Opcode::Br:

157 case Instruction::Opcode::Ret:

158 case Instruction::Opcode::PHI:

159 case Instruction::Opcode::AddrSpaceCast:

160 case Instruction::Opcode::Call:

161 case Instruction::Opcode::GetElementPtr:

163 break;

164 default:

166 break;

167 }

169

170 };

171

172 auto *NewI = CreateVectorInstr(Bndl, Operands);

174 return NewI;

175}

176

177void BottomUpVec::tryEraseDeadInstrs() {

178 DenseMap<BasicBlock *, SmallVector<Instruction *>> SortedDeadInstrCandidates;

179

180 for (auto *DeadI : DeadInstrCandidates)

181 SortedDeadInstrCandidates[DeadI->getParent()].push_back(DeadI);

182 for (auto &Pair : SortedDeadInstrCandidates)

183 sort(Pair.second,

185 for (const auto &Pair : SortedDeadInstrCandidates) {

187 if (I->hasNUses(0)) {

188

190 I->eraseFromParent();

191 }

192 }

193 }

194 DeadInstrCandidates.clear();

195}

196

201 VecOp->getContext(), "VShuf");

202}

203

206

210

211

213

214 Context &Ctx = ToPack[0]->getContext();

215

216 unsigned InsertIdx = 0;

217 for (Value *Elm : ToPack) {

218

219

220 if (Elm->getType()->isVectorTy()) {

221 unsigned NumElms =

223 for (auto ExtrLane : seq(0, NumElms)) {

224

227

228 auto *ExtrI =

234

236 LastInsert, ExtrI, InsertLaneC, WhereIt, Ctx, "VPack");

237 LastInsert = InsertI;

239 WhereIt = std::next(cast(LastInsert)->getIterator());

240 }

241 } else {

244

245

247 WhereIt, Ctx, "Pack");

249 WhereIt = std::next(NewI->getIterator());

250 }

251 }

252 return LastInsert;

253}

254

255void BottomUpVec::collectPotentiallyDeadInstrs(ArrayRef<Value *> Bndl) {

256 for (Value *V : Bndl)

258

260 switch (Opcode) {

261 case Instruction::Opcode::Load: {

263 if (auto *Ptr =

265 DeadInstrCandidates.insert(Ptr);

266 break;

267 }

268 case Instruction::Opcode::Store: {

270 if (auto *Ptr =

272 DeadInstrCandidates.insert(Ptr);

273 break;

274 }

275 default:

276 break;

277 }

278}

279

283 bool StopForDebug =

287 const auto &LegalityRes = StopForDebug ? Legality.getForcedPackForDebugging()

288 : Legality.canVectorize(Bndl);

290 auto ActionPtr =

291 std::make_unique(&LegalityRes, Bndl, UserBndl, Depth);

293 switch (LegalityRes.getSubclassID()) {

296 switch (I->getOpcode()) {

297 case Instruction::Opcode::Load:

298 break;

299 case Instruction::Opcode::Store: {

300

301 Action *OpA =

302 vectorizeRec(getOperand(Bndl, 0), Bndl, Depth + 1, Legality);

303 Operands.push_back(OpA);

304 break;

305 }

306 default:

307

309 Action *OpA =

311 Operands.push_back(OpA);

312 }

313 break;

314 }

315

316 IMaps->registerVector(Bndl, ActionPtr.get());

317 break;

318 }

323 break;

324 }

325

326 ActionPtr->Operands = std::move(Operands);

327 auto *Action = ActionPtr.get();

328 Actions.push_back(std::move(ActionPtr));

329 return Action;

330}

331

332#ifndef NDEBUG

333void BottomUpVec::ActionsVector::print(raw_ostream &OS) const {

334 for (auto [Idx, Action] : enumerate(Actions)) {

335 Action->print(OS);

336 OS << "\n";

337 }

338}

339void BottomUpVec::ActionsVector::dump() const { print(dbgs()); }

340#endif

341

342Value *BottomUpVec::emitVectors() {

343 Value *NewVec = nullptr;

344 for (const auto &ActionPtr : Actions) {

347 const LegalityResult &LegalityRes = *ActionPtr->LegalityRes;

348 unsigned Depth = ActionPtr->Depth;

349 auto *UserBB = !UserBndl.empty()

352

353 switch (LegalityRes.getSubclassID()) {

356 SmallVector<Value *, 2> VecOperands;

357 switch (I->getOpcode()) {

358 case Instruction::Opcode::Load:

360 break;

361 case Instruction::Opcode::Store: {

362 VecOperands.push_back(ActionPtr->Operands[0]->Vec);

364 break;

365 }

366 default:

367

368 for (Action *OpA : ActionPtr->Operands) {

369 auto *VecOp = OpA->Vec;

370 VecOperands.push_back(VecOp);

371 }

372 break;

373 }

374 NewVec = createVectorInstr(ActionPtr->Bndl, VecOperands);

375

376

377 if (NewVec != nullptr)

378 collectPotentiallyDeadInstrs(Bndl);

379 break;

380 }

383 break;

384 }

387 const ShuffleMask &Mask =

389 NewVec = createShuffle(VecOp, Mask, UserBB);

390 assert(NewVec->getType() == VecOp->getType() &&

391 "Expected same type! Bad mask ?");

392 break;

393 }

395 const auto &Descr =

398

399

401 for (const auto &ElmDescr : Descr.getDescrs()) {

402 auto *V = ElmDescr.needsExtract() ? ElmDescr.getValue()->Vec

403 : ElmDescr.getScalar();

405 DescrInstrs.push_back(I);

406 }

409

411 Context &Ctx = LastV->getContext();

412 unsigned Lane = 0;

413 for (const auto &ElmDescr : Descr.getDescrs()) {

414 Value *VecOp = nullptr;

415 Value *ValueToInsert;

416 if (ElmDescr.needsExtract()) {

417 VecOp = ElmDescr.getValue()->Vec;

418 ConstantInt *IdxC =

421 VecOp, IdxC, WhereIt, VecOp->getContext(), "VExt");

422 } else {

423 ValueToInsert = ElmDescr.getScalar();

424 }

426 if (NumLanesToInsert == 1) {

427

428

431 WhereIt, Ctx, "VIns");

432 } else {

433

434

435

436

437

438

439

440 for (unsigned LnCnt = 0; LnCnt != NumLanesToInsert; ++LnCnt) {

443 WhereIt, Ctx, "VExt");

444 unsigned InsLane = Lane + LnCnt;

447 Ctx, "VIns");

448 }

449 }

450 Lane += NumLanesToInsert;

451 }

452 NewVec = LastV;

453 break;

454 }

456

458 return nullptr;

459 NewVec = createPack(Bndl, UserBB);

460 break;

461 }

462 }

463 if (NewVec != nullptr) {

464 Change = true;

465 ActionPtr->Vec = NewVec;

466 }

467#ifndef NDEBUG

469

470

475 "Broken function!");

476 }

477#endif

478 }

479 return NewVec;

480}

481

483 LegalityAnalysis &Legality) {

484 Change = false;

487 return false;

488 DeadInstrCandidates.clear();

489 Legality.clear();

490 Actions.clear();

491 DebugBndlCnt = 0;

492 vectorizeRec(Bndl, {}, 0, Legality);

494 Actions.dump());

495 emitVectors();

496 tryEraseDeadInstrs();

497 return Change;

498}

499

501 const auto &SeedSlice = Rgn.getAux();

502 assert(SeedSlice.size() >= 2 && "Bad slice!");

503 Function &F = *SeedSlice[0]->getParent()->getParent();

504 IMaps = std::make_unique();

506 F.getParent()->getDataLayout(), F.getContext(),

507 *IMaps);

508

509

511

512

513

514 return tryVectorize(SeedSliceVals, Legality);

515}

516

517}

518}

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

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

#define LLVM_UNLIKELY(EXPR)

MachineInstr unsigned OpIdx

This file defines the SmallVector class.

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

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

size_t size() const

size - Get the array size.

iterator begin()

Instruction iterator methods.

InstListType::iterator iterator

Instruction iterators...

void push_back(const T &Elt)

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

LLVM Value Representation.

static LLVM_ABI Value * createWithCopiedFlags(Instruction::Opcode Op, Value *LHS, Value *RHS, Value *CopyFrom, InsertPosition Pos, Context &Ctx, const Twine &Name="")

bool runOnRegion(Region &Rgn, const Analyses &A) final

\Returns true if it modifies R.

Definition BottomUpVec.cpp:500

static LLVM_ABI Value * create(Type *DestTy, Opcode Op, Value *Operand, InsertPosition Pos, Context &Ctx, const Twine &Name="")

static LLVM_ABI Value * create(Predicate Pred, Value *S1, Value *S2, InsertPosition Pos, Context &Ctx, const Twine &Name="")

static LLVM_ABI ConstantInt * get(Type *Ty, uint64_t V, bool IsSigned=false)

If Ty is a vector type, return a Constant with a splat of the given value.

static LLVM_ABI ConstantInt * getSigned(IntegerType *Ty, int64_t V)

Return a ConstantInt with the specified value for the specified type.

static LLVM_ABI Value * create(Value *Vec, Value *Idx, InsertPosition Pos, Context &Ctx, const Twine &Name="")

static LLVM_ABI Value * create(Value *Vec, Value *NewElt, Value *Idx, InsertPosition Pos, Context &Ctx, const Twine &Name="")

Performs the legality analysis and returns a LegalityResult object.

static LLVM_ABI LoadInst * create(Type *Ty, Value *Ptr, MaybeAlign Align, InsertPosition Pos, bool IsVolatile, Context &Ctx, const Twine &Name="")

virtual void print(raw_ostream &OS) const

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

The main job of the Region is to point to new instructions generated by vectorization passes.

const SmallVector< Instruction * > & getAux() const

\Returns the auxiliary vector.

static LLVM_ABI Value * create(Value *Cond, Value *True, Value *False, InsertPosition Pos, Context &Ctx, const Twine &Name="")

static LLVM_ABI Value * create(Value *V1, Value *V2, Value *Mask, InsertPosition Pos, Context &Ctx, const Twine &Name="")

static LLVM_ABI StoreInst * create(Value *V, Value *Ptr, MaybeAlign Align, InsertPosition Pos, bool IsVolatile, Context &Ctx)

static LLVM_ABI Type * getInt32Ty(Context &Ctx)

static LLVM_ABI Value * createWithCopiedFlags(Instruction::Opcode Op, Value *OpV, Value *CopyFrom, InsertPosition Pos, Context &Ctx, const Twine &Name="")

static Type * getExpectedType(const Value *V)

\Returns the expected type of Value V.

static bool verifyFunction(const Function *F, raw_ostream &OS)

Equivalent to llvm::verifyFunction().

A SandboxIR Value has users. This is the base class.

static Instruction * getLowest(ArrayRef< Instruction * > Instrs)

\Returns the instruction in Instrs that is lowest in the BB.

static Type * getCommonScalarType(ArrayRef< Value * > Bndl)

Similar to tryGetCommonScalarType() but will assert that there is a common type.

static Instruction * getLastPHIOrSelf(Instruction *I)

If I is not a PHI it returns it.

static unsigned getNumLanes(Type *Ty)

\Returns the number of vector lanes of Ty or 1 if not a vector.

static LLVM_DUMP_METHOD void dump(ArrayRef< Value * > Bndl)

Helper dump function for debugging.

static Type * getWideType(Type *ElemTy, unsigned NumElts)

\Returns .

static Type * getElementType(Type *Ty)

Returns Ty if scalar or its element type if vector.

#define llvm_unreachable(msg)

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

constexpr char Align[]

Key for Kernel::Arg::Metadata::mAlign.

constexpr std::underlying_type_t< E > Mask()

Get a bitmask with 1s in all places up to the high-order bit of E's largest value.

initializer< Ty > init(const Ty &Val)

LLVM_ABI Function * getParent() const

@ DiamondReuseWithShuffle

BasicBlock(llvm::BasicBlock *BB, Context &SBCtx)

friend class Instruction

Iterator for Instructions in a `BasicBlock.

static BasicBlock::iterator getInsertPointAfterInstrs(ArrayRef< Value * > Vals, BasicBlock *BB)

\Returns the BB iterator after the lowest instruction in Vals, or the top of BB if no instruction fou...

Definition BottomUpVec.cpp:55

static SmallVector< Value *, 4 > getOperand(ArrayRef< Value * > Bndl, unsigned OpIdx)

Definition BottomUpVec.cpp:43

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

FunctionAddr VTableAddr Value

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

static cl::opt< unsigned long > StopAt("sbvec-stop-at", cl::init(StopAtDisabled), cl::Hidden, cl::desc("Vectorize if the invocation count is < than this. 0 " "disables vectorization."))

auto enumerate(FirstRange &&First, RestRanges &&...Rest)

Given two or more input ranges, returns a new range whose values are tuples (A, B,...

decltype(auto) dyn_cast(const From &Val)

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

static constexpr unsigned long StopBundleDisabled

Definition BottomUpVec.cpp:35

static cl::opt< unsigned long > StopBundle("sbvec-stop-bndl", cl::init(StopBundleDisabled), cl::Hidden, cl::desc("Vectorize up to this many bundles."))

const Value * getPointerOperand(const Value *V)

A helper function that returns the pointer operand of a load, store or GEP instruction.

auto reverse(ContainerTy &&C)

void sort(IteratorTy Start, IteratorTy End)

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

bool isa(const From &Val)

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

ArrayRef(const T &OneElt) -> ArrayRef< T >

static constexpr unsigned long StopAtDisabled

Definition BottomUpVec.cpp:28

decltype(auto) cast(const From &Val)

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

static cl::opt< bool > AlwaysVerify("sbvec-always-verify", cl::init(false), cl::Hidden, cl::desc("Helps find bugs by verifying the IR whenever we " "emit new instructions (*very* expensive)."))

auto seq(T Begin, T End)

Iterate over an integral type from Begin up to - but not including - End.