SliceAnalysis.cpp Source File (original) (raw)

19#include "llvm/ADT/STLExtras.h"

20#include "llvm/ADT/SetVector.h"

26using namespace mlir;

28static void

32 if (!op)

33 return;

38 if (filter && !filter(op))

39 return;

42 for (Block &block : region)

44 if (forwardSlice->count(&blockOp) == 0) {

50 visited.insert(&blockOp);

52 visited.erase(&blockOp);

53 }

65 if (forwardSlice->count(userOp) == 0 && visited.insert(userOp).second)

68 visited.erase(userOp);

69 }

71 forwardSlice->insert(op);

72}

77 visited.insert(op);

82 forwardSlice->remove(op);

83 }

89 forwardSlice->insert(v.rbegin(), v.rend());

90}

96 visited.insert(user);

98 visited.erase(user);

99 }

100

101

102

103

105 forwardSlice->insert(v.rbegin(), v.rend());

106}

107

112 if (!op)

114

115

116

117

120

122 if (auto *definingOp = value.getDefiningOp()) {

123 if (backwardSlice->count(definingOp) == 0 &&

124 visited.insert(definingOp).second)

127

128 visited.erase(definingOp);

129 } else if (auto blockArg = dyn_cast(value)) {

130 if (options.omitBlockArguments)

132

133 Block *block = blockArg.getOwner();

135

136

137

138 if (parentOp && backwardSlice->count(parentOp) == 0) {

144 }

145 }

146 } else {

147 return failure();

148 }

150 };

151

152 bool succeeded = true;

153

154 if ( options .omitUsesFromAbove &&

157

158

159 SmallPtrSet<Region *, 4> descendents;

160 region.walk(

161 [&](Region *childRegion) { descendents.insert(childRegion); });

164 if (!descendents.contains(operand.get().getParentRegion()))

165 if ( processValue (operand.get()).succeeded()) {

167 }

168 }

170 });

171 });

172 }

173 llvm::for_each(op->getOperands(), processValue);

174

175 backwardSlice->insert(op);

176 return success(succeeded);

177}

178

183 visited.insert(op);

184 LogicalResult result =

186

187 if ( options .inclusive) {

188

189

190 backwardSlice->remove(op);

191 }

193}

194

204

209 slice.insert(op);

210

211 unsigned currentIndex = 0;

214 while (currentIndex != slice.size()) {

215 auto *currentOp = (slice)[currentIndex];

216

217 backwardSlice.clear();

218 LogicalResult result =

219 getBackwardSlice(currentOp, &backwardSlice, backwardSliceOptions);

220 assert(result.succeeded());

222 slice.insert_range(backwardSlice);

223

224

225 forwardSlice.clear();

226 getForwardSlice(currentOp, &forwardSlice, forwardSliceOptions);

227 slice.insert_range(forwardSlice);

228 ++currentIndex;

229 }

231}

232

233

234

238

243 };

245 assert(result.succeeded());

247

248

249

251 if (iterCarriedValSet.contains(value))

252 return true;

253

255 for (Value operand : op->getOperands())

256 if (iterCarriedValSet.contains(operand))

257 return true;

258

259 return false;

260}

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

291 unsigned redPos,

293 assert(redPos < iterCarriedArgs.size() && "'redPos' is out of bounds");

294

295 BlockArgument redCarriedVal = iterCarriedArgs[redPos];

297 return nullptr;

298

299

302 return nullptr;

303 Value reducedVal = combinerOp->getOperand(0) == redCarriedVal

306

308 iterCarriedArgs.front().getOwner()->getParent()->getParentOp();

310 return nullptr;

311

312

313

314

318 return nullptr;

319

320 combinerOps.push_back(combinerOp);

321 combinerOp = *combinerOp->getUsers().begin();

322 }

323

324

325

326 if (combinerOps.size() != 1)

327 return nullptr;

328

329

330

331 Operation *terminatorOp = combinerOp;

332 if (terminatorOp->getOperand(redPos) != combinerOps.back()->getResults()[0])

333 return nullptr;

334

335 return reducedVal;

336}

static llvm::ManagedStatic< PassManagerOptions > options

static void processValue(Value value, LiveMap &liveMap)

static LogicalResult getBackwardSliceImpl(Operation *op, DenseSet< Operation * > &visited, SetVector< Operation * > *backwardSlice, const BackwardSliceOptions &options)

Definition SliceAnalysis.cpp:108

static bool dependsOnCarriedVals(Value value, ArrayRef< BlockArgument > iterCarriedArgs, Operation *ancestorOp)

Returns true if value (transitively) depends on iteration-carried values of the given ancestorOp.

Definition SliceAnalysis.cpp:235

static void getForwardSliceImpl(Operation *op, DenseSet< Operation * > &visited, SetVector< Operation * > *forwardSlice, const SliceOptions::TransitiveFilter &filter=nullptr)

Definition SliceAnalysis.cpp:29

This class represents an argument of a Block.

Block represents an ordered list of Operations.

Operation * getParentOp()

Returns the closest surrounding operation that contains this block.

This class represents an operand of an operation.

This class provides the API for ops that are known to be isolated from above.

This class provides the API for ops that are known to be terminators.

Operation is the basic unit of execution within MLIR.

Region & getRegion(unsigned index)

Returns the region held by this operation at position 'index'.

Value getOperand(unsigned idx)

bool hasTrait()

Returns true if the operation was registered with a particular trait, e.g.

bool mightHaveTrait()

Returns true if the operation might have the provided trait.

bool hasOneUse()

Returns true if this operation has exactly one use.

unsigned getNumRegions()

Returns the number of regions held by this operation.

Operation * getParentOp()

Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...

MutableArrayRef< OpOperand > getOpOperands()

unsigned getNumOperands()

MutableArrayRef< Region > getRegions()

Returns the regions held by this operation.

bool isAncestor(Operation *other)

Return true if this operation is an ancestor of the other operation.

user_range getUsers()

Returns a range of all users.

result_range getResults()

unsigned getNumResults()

Return the number of results held by this operation.

This class contains a list of basic blocks and a link to the parent operation it is attached to.

bool hasOneBlock()

Return true if this region has exactly one block.

RetT walk(FnT &&callback)

Walk all nested operations, blocks or regions (including this region), depending on the type of callb...

This class represents an instance of an SSA value in the MLIR system, representing a computable value...

user_range getUsers() const

bool hasOneUse() const

Returns true if this value has exactly one use.

Operation * getDefiningOp() const

If this value is the result of an operation, return the operation that defines it.

static WalkResult advance()

static WalkResult interrupt()

Include the generated interface declarations.

LogicalResult getBackwardSlice(Operation *op, SetVector< Operation * > *backwardSlice, const BackwardSliceOptions &options={})

Fills backwardSlice with the computed backward slice (i.e.

Definition SliceAnalysis.cpp:179

llvm::DenseSet< ValueT, ValueInfoT > DenseSet

bool isMemoryEffectFree(Operation *op)

Returns true if the given operation is free of memory effects.

Value matchReduction(ArrayRef< BlockArgument > iterCarriedArgs, unsigned redPos, SmallVectorImpl< Operation * > &combinerOps)

Utility to match a generic reduction given a list of iteration-carried arguments, iterCarriedArgs and...

Definition SliceAnalysis.cpp:290

llvm::SetVector< T, Vector, Set, N > SetVector

SliceOptions ForwardSliceOptions

SetVector< Operation * > getSlice(Operation *op, const BackwardSliceOptions &backwardSliceOptions={}, const ForwardSliceOptions &forwardSliceOptions={})

Iteratively computes backward slices and forward slices until a fixed point is reached.

Definition SliceAnalysis.cpp:206

SetVector< Operation * > topologicalSort(const SetVector< Operation * > &toSort)

Sorts all operations in toSort topologically while also considering region semantics.

void getForwardSlice(Operation *op, SetVector< Operation * > *forwardSlice, const ForwardSliceOptions &options={})

Fills forwardSlice with the computed forward slice (i.e.

Definition SliceAnalysis.cpp:74

std::function< bool(Operation *)> TransitiveFilter

Type of the condition to limit the propagation of transitive use-defs.