VPlanPredicator.cpp Source File (original) (raw)

22using namespace llvm;

25namespace {

26class VPPredicator {

28 VPBuilder Builder;

32 using EdgeMaskCacheTy =

33 DenseMap<std::pair<const VPBasicBlock *, const VPBasicBlock *>,

34 VPValue *>;

35 using BlockMaskCacheTy = DenseMap<VPBasicBlock *, VPValue *>;

36 EdgeMaskCacheTy EdgeMaskCache;

38 BlockMaskCacheTy BlockMaskCache;

41 void createSwitchEdgeMasks(VPInstruction *SI);

45 VPValue *createEdgeMask(VPBasicBlock *Src, VPBasicBlock *Dst);

49 void setBlockInMask(VPBasicBlock *VPBB, VPValue *Mask) {

52 assert(!getBlockInMask(VPBB) && "Mask already set");

53 BlockMaskCache[VPBB] = Mask;

54 }

58 VPValue *setEdgeMask(const VPBasicBlock *Src, const VPBasicBlock *Dst,

59 VPValue *Mask) {

60 assert(Src != Dst && "Src and Dst must be different");

61 assert(!getEdgeMask(Src, Dst) && "Mask already set");

62 return EdgeMaskCache[{Src, Dst}] = Mask;

63 }

65public:

67 VPValue *getBlockInMask(VPBasicBlock *VPBB) const {

68 return BlockMaskCache.lookup(VPBB);

69 }

72 VPValue *getEdgeMask(const VPBasicBlock *Src, const VPBasicBlock *Dst) const {

73 return EdgeMaskCache.lookup({Src, Dst});

74 }

77 void createHeaderMask(VPBasicBlock *HeaderVPBB, bool FoldTail);

81 VPValue *createBlockInMask(VPBasicBlock *VPBB);

84 void convertPhisToBlends(VPBasicBlock *VPBB);

86 const BlockMaskCacheTy getBlockMaskCache() const { return BlockMaskCache; }

87};

88}

94 VPValue *EdgeMask = getEdgeMask(Src, Dst);

95 if (EdgeMask)

96 return EdgeMask;

98 VPValue *SrcMask = getBlockInMask(Src);

100

101 if (Src->getNumSuccessors() == 1)

102 return setEdgeMask(Src, Dst, SrcMask);

103

105 if (Term->getOpcode() == Instruction::Switch) {

106 createSwitchEdgeMasks(Term);

107 return getEdgeMask(Src, Dst);

108 }

109

111 "Unsupported terminator");

112 if (Src->getSuccessors()[0] == Src->getSuccessors()[1])

113 return setEdgeMask(Src, Dst, SrcMask);

114

115 EdgeMask = Term->getOperand(0);

116 assert(EdgeMask && "No Edge Mask found for condition");

117

118 if (Src->getSuccessors()[0] != Dst)

119 EdgeMask = Builder.createNot(EdgeMask, Term->getDebugLoc());

120

121 if (SrcMask) {

122

123

124

126 }

127

128 return setEdgeMask(Src, Dst, EdgeMask);

129}

130

131VPValue *VPPredicator::createBlockInMask(VPBasicBlock *VPBB) {

132

134

135

136 VPValue *BlockMask = nullptr;

137

138 for (auto *Predecessor : SetVector<VPBlockBase *>(

140 VPValue *EdgeMask = createEdgeMask(cast(Predecessor), VPBB);

141 if (!EdgeMask) {

142

143 setBlockInMask(VPBB, EdgeMask);

144 return EdgeMask;

145 }

146

147 if (!BlockMask) {

148 BlockMask = EdgeMask;

149 continue;

150 }

151

152 BlockMask = Builder.createOr(BlockMask, EdgeMask, {});

153 }

154

155 setBlockInMask(VPBB, BlockMask);

156 return BlockMask;

157}

158

159void VPPredicator::createHeaderMask(VPBasicBlock *HeaderVPBB, bool FoldTail) {

160 if (!FoldTail) {

161 setBlockInMask(HeaderVPBB, nullptr);

162 return;

163 }

164

165

166

167

168

169

170 auto &Plan = *HeaderVPBB->getPlan();

171 auto *IV =

175

176 VPValue *BTC = Plan.getOrCreateBackedgeTakenCount();

178 setBlockInMask(HeaderVPBB, BlockMask);

179}

180

181void VPPredicator::createSwitchEdgeMasks(VPInstruction *SI) {

182 VPBasicBlock *Src = SI->getParent();

183

184

185

186

187 VPValue *Cond = SI->getOperand(0);

188 VPBasicBlock *DefaultDst = cast(Src->getSuccessors()[0]);

189 MapVector<VPBasicBlock *, SmallVector<VPValue *>> Dst2Compares;

190 for (const auto &[Idx, Succ] : enumerate(drop_begin(Src->getSuccessors()))) {

192 assert(!getEdgeMask(Src, Dst) && "Edge masks already created");

193

194

195 if (Dst == DefaultDst)

196 continue;

197 auto &Compares = Dst2Compares[Dst];

198 VPValue *V = SI->getOperand(Idx + 1);

200 }

201

202

203

204 VPValue *SrcMask = getBlockInMask(Src);

205 VPValue *DefaultMask = nullptr;

206 for (const auto &[Dst, Conds] : Dst2Compares) {

207

208

209

210 VPValue *Mask = Conds[0];

213 if (SrcMask)

215 setEdgeMask(Src, Dst, Mask);

216

217

218

219

220

221 DefaultMask = DefaultMask ? Builder.createOr(DefaultMask, Mask) : Mask;

222 }

223

224 if (DefaultMask) {

225 DefaultMask = Builder.createNot(DefaultMask);

226 if (SrcMask)

227 DefaultMask = Builder.createLogicalAnd(SrcMask, DefaultMask);

228 }

229 setEdgeMask(Src, DefaultDst, DefaultMask);

230}

231

232void VPPredicator::convertPhisToBlends(VPBasicBlock *VPBB) {

234 for (VPRecipeBase &R : VPBB->phis())

236 for (VPPhi *PhiR : Phis) {

237

238

239

240

241

242

244 for (const auto &[InVPV, InVPBB] : PhiR->incoming_values_and_blocks()) {

245 OperandsWithMask.push_back(InVPV);

246 VPValue *EdgeMask = getEdgeMask(InVPBB, VPBB);

247 if (!EdgeMask) {

249 "Distinct incoming values with one having a full mask");

250 break;

251 }

252

253 OperandsWithMask.push_back(EdgeMask);

254 }

256 auto *Blend =

257 new VPBlendRecipe(IRPhi, OperandsWithMask, PhiR->getDebugLoc());

258 Builder.insert(Blend);

259 PhiR->replaceAllUsesWith(Blend);

260 PhiR->eraseFromParent();

261 }

262}

263

264DenseMap<VPBasicBlock *, VPValue *>

267

268

271 Header);

274

276

277

278

279 if (VPBB == Header) {

280 Predicator.createHeaderMask(Header, FoldTail);

281 continue;

282 }

283

285 Predicator.convertPhisToBlends(VPBB);

286 }

287

288

292 if (Successors.size() > 1)

294

295

296

297 for (auto *Succ : Successors)

299 if (PrevVPBB)

301

302 PrevVPBB = VPBB;

303 }

304

305

306

307

308

309 if (FoldTail) {

311 "only a single-exit block is supported currently");

314 "the exit block must have middle block as single predecessor");

315

320 continue;

321

322

324 VPValue *LastActiveLane =

326 auto *Ext =

328 R.getVPSingleValue()->replaceAllUsesWith(Ext);

329 }

330 }

331 return Predicator.getBlockMaskCache();

332}

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

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

const SmallVectorImpl< MachineOperand > & Cond

This file provides utility VPlan to VPlan transformations.

This file contains the declarations of the Vectorization Plan base classes:

static const uint32_t IV[8]

@ ICMP_ULE

unsigned less or equal

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

void push_back(const T &Elt)

VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.

iterator_range< iterator > phis()

Returns an iterator range over the PHI-like recipes in the block.

iterator getFirstNonPhi()

Return the position of the first non-phi node recipe in the block.

VPRecipeBase * getTerminator()

If the block has multiple successors, return the branch recipe terminating the block.

VPBlockBase is the building block of the Hierarchical Control-Flow Graph.

VPRegionBlock * getParent()

const VPBlocksTy & getPredecessors() const

const VPBasicBlock * getEntryBasicBlock() const

const VPBlocksTy & getSuccessors() const

static auto blocksOnly(const T &Range)

Return an iterator range over Range which only includes BlockTy blocks.

static void connectBlocks(VPBlockBase *From, VPBlockBase *To, unsigned PredIdx=-1u, unsigned SuccIdx=-1u)

Connect VPBlockBases From and To bi-directionally.

static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)

Disconnect VPBlockBases From and To bi-directionally.

VPlan-based builder utility analogous to IRBuilder.

VPInstruction * createOr(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")

VPInstruction * createNot(VPValue *Operand, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")

VPInstruction * createLogicalAnd(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")

void insert(VPRecipeBase *R)

Insert R at the current insertion point.

VPInstruction * createICmp(CmpInst::Predicate Pred, VPValue *A, VPValue *B, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")

Create a new ICmp VPInstruction with predicate Pred and operands A and B.

void setInsertPoint(VPBasicBlock *TheBB)

This specifies that created VPInstructions should be appended to the end of the specified block.

@ ExtractLane

Extracts a single lane (first operand) from a set of vector operands.

VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.

iplist< VPRecipeBase >::iterator eraseFromParent()

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

VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...

VPCanonicalIVPHIRecipe * getCanonicalIV()

Returns the canonical induction recipe of the region.

This is the base class of the VPlan Def/Use graph, used for modeling the data flow into,...

VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...

ArrayRef< VPIRBasicBlock * > getExitBlocks() const

Return an ArrayRef containing VPIRBasicBlocks wrapping the exit blocks of the original scalar loop.

LLVM_ABI_FOR_TEST VPRegionBlock * getVectorLoopRegion()

Returns the VPRegionBlock of the vector loop.

VPBasicBlock * getMiddleBlock()

Returns the 'middle' block of the plan, that is the block that selects whether to execute the scalar ...

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.

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

VPInstruction_match< VPInstruction::ExtractLastLane, Op0_t > m_ExtractLastLane(const Op0_t &Op0)

VPInstruction_match< VPInstruction::ExtractLastPart, Op0_t > m_ExtractLastPart(const Op0_t &Op0)

class_match< VPValue > m_VPValue()

Match an arbitrary VPValue and ignore it.

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.

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

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

auto cast_or_null(const Y &Val)

SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)

Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...

class LLVM_GSL_OWNER SmallVector

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

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

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

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

bool all_equal(std::initializer_list< T > Values)

Returns true if all Values in the initializer lists are equal or the list.

static DenseMap< VPBasicBlock *, VPValue * > introduceMasksAndLinearize(VPlan &Plan, bool FoldTail)

Predicate and linearize the control-flow in the only loop region of Plan.

Definition VPlanPredicator.cpp:265