CodeMoverUtils.cpp Source File (original) (raw)

21using namespace llvm;

23#define DEBUG_TYPE "codemover-utils"

26 "Cannot move across instructions that has memory dependences");

27 STATISTIC(MayThrowException, "Cannot move across instructions that may throw");

29 "Instructions are not control flow equivalent");

30 STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");

31 STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");

33namespace {

42#ifndef NDEBUG

44 OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")

45 << "]";

46 return OS;

47}

48#endif

51class ControlConditions {

52 using ConditionVectorTy = SmallVector<ControlCondition, 6>;

55 ConditionVectorTy Conditions;

57public:

62 static const std::optional

63 collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator,

64 const DominatorTree &DT,

65 const PostDominatorTree &PDT,

66 unsigned MaxLookup = 6);

70 bool isUnconditional() const { return Conditions.empty(); }

73 const ConditionVectorTy &getControlConditions() const { return Conditions; }

77 bool addControlCondition(ControlCondition C);

81 bool isEquivalent(const ControlConditions &Other) const;

84 static bool isEquivalent(const ControlCondition &C1,

85 const ControlCondition &C2);

87private:

88 ControlConditions() = default;

90 static bool isEquivalent(const Value &V1, const Value &V2);

91 static bool isInverse(const Value &V1, const Value &V2);

92};

93}

101

104 return DA->getLevel() < DB->getLevel();

105}

106

107const std::optional

108ControlConditions::collectControlConditions(const BasicBlock &BB,

112 unsigned MaxLookup) {

113 assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");

114

115 ControlConditions Conditions;

116 unsigned NumConditions = 0;

117

118

119 if (&Dominator == &BB)

120 return Conditions;

121

123

124

125 do {

126 assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock");

129 "Expecting Dominator to dominate IDom");

130

131

133 if (!BI)

134 return std::nullopt;

135

137 if (PDT.dominates(CurBlock, IDom)) {

139 << " is executed unconditionally from "

140 << IDom->getName() << "\n");

144 << IDom->getName() << "\n");

145 Inserted = Conditions.addControlCondition(

149 << *BI->getCondition() << "\" is false from "

150 << IDom->getName() << "\n");

151 Inserted = Conditions.addControlCondition(

152 ControlCondition(BI->getCondition(), false));

153 } else

154 return std::nullopt;

155

156 if (Inserted)

157 ++NumConditions;

158

159 if (MaxLookup != 0 && NumConditions > MaxLookup)

160 return std::nullopt;

161

162 CurBlock = IDom;

163 } while (CurBlock != &Dominator);

164

165 return Conditions;

166}

167

168bool ControlConditions::addControlCondition(ControlCondition C) {

170 if (none_of(Conditions, [&](ControlCondition &Exists) {

171 return ControlConditions::isEquivalent(C, Exists);

172 })) {

173 Conditions.push_back(C);

175 }

176

177 LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n");

179}

180

181bool ControlConditions::isEquivalent(const ControlConditions &Other) const {

182 if (Conditions.empty() && Other.Conditions.empty())

183 return true;

184

185 if (Conditions.size() != Other.Conditions.size())

186 return false;

187

188 return all_of(Conditions, [&](const ControlCondition &C) {

189 return any_of(Other.Conditions, [&](const ControlCondition &OtherC) {

190 return ControlConditions::isEquivalent(C, OtherC);

191 });

192 });

193}

194

195bool ControlConditions::isEquivalent(const ControlCondition &C1,

196 const ControlCondition &C2) {

197 if (C1.getInt() == C2.getInt()) {

198 if (isEquivalent(*C1.getPointer(), *C2.getPointer()))

199 return true;

200 } else if (isInverse(*C1.getPointer(), *C2.getPointer()))

201 return true;

202

203 return false;

204}

205

206

207

208

209

210bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) {

211 return &V1 == &V2;

212}

213

214bool ControlConditions::isInverse(const Value &V1, const Value &V2) {

217 if (Cmp1->getPredicate() == Cmp2->getInversePredicate() &&

218 Cmp1->getOperand(0) == Cmp2->getOperand(0) &&

219 Cmp1->getOperand(1) == Cmp2->getOperand(1))

220 return true;

221

222 if (Cmp1->getPredicate() ==

224 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&

225 Cmp1->getOperand(1) == Cmp2->getOperand(0))

226 return true;

227 }

228 return false;

229}

230

236

240 if (&BB0 == &BB1)

241 return true;

242

245 return true;

246

247

248

251 << " and " << BB1.getName() << " is "

252 << CommonDominator->getName() << "\n");

253

254 const std::optional BB0Conditions =

255 ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,

256 PDT);

257 if (BB0Conditions == std::nullopt)

258 return false;

259

260 const std::optional BB1Conditions =

261 ControlConditions::collectControlConditions(BB1, *CommonDominator, DT,

262 PDT);

263 if (BB1Conditions == std::nullopt)

264 return false;

265

266 return BB0Conditions->isEquivalent(*BB1Conditions);

267}

268

271 ++Stat;

272 LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "

273 << Stat.getDesc());

274 return false;

275}

276

277

278

279static void

282 assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");

283

284

288 WorkList.insert(NextInst);

289 else {

290 assert(I.isTerminator() && "Expecting a terminator instruction");

292 WorkList.insert(&Succ->front());

293 }

294 };

295

297 getNextInsts(StartInst, WorkList);

298 while (!WorkList.empty()) {

300 WorkList.erase(CurInst);

301

302 if (CurInst == &EndInst)

303 continue;

304

305 if (!InBetweenInsts.insert(CurInst).second)

306 continue;

307

308 getNextInsts(*CurInst, WorkList);

309 }

310}

311

315

316 if (!PDT || !DI)

317 return false;

318

319

320 if (&I == &InsertPoint)

321 return false;

322

323

324 if (I.getNextNode() == &InsertPoint)

325 return true;

326

329

330 if (I.isTerminator())

332

333

336

338 for (const Use &U : I.uses())

340

341

342 if (I.getParent() == InsertPoint.getParent() &&

343 UserInst == I.getParent()->getTerminator())

344 return false;

345 if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U)) {

346

347

348

349 if (CheckForEntireBlock && I.getParent() == UserInst->getParent() &&

351 continue;

352 return false;

353 }

354 }

356 for (const Value *Op : I.operands())

358 if (&InsertPoint == OpInst)

359 return false;

360

361

362 if (CheckForEntireBlock && I.getParent() == OpInst->getParent() &&

364 continue;

365 if (!DT.dominates(OpInst, &InsertPoint))

366 return false;

367 }

368

371 Instruction &StartInst = (MoveForward ? I : InsertPoint);

372 Instruction &EndInst = (MoveForward ? InsertPoint : I);

375 if (!MoveForward)

376 InstsToCheck.insert(&InsertPoint);

377

378

379

382 if (I->mayThrow())

383 return true;

384

386 if (!CB)

387 return false;

388 if (!CB->hasFnAttr(Attribute::WillReturn))

389 return true;

390 if (!CB->hasFnAttr(Attribute::NoSync))

391 return true;

392

393 return false;

394 })) {

396 }

397

398

399

401 auto DepResult = DI->depends(&I, CurInst);

402 if (DepResult && (DepResult->isOutput() || DepResult->isFlow() ||

403 DepResult->isAnti()))

404 return true;

405 return false;

406 }))

408

409 return true;

410}

411

417 return true;

418

420 true);

421 });

422}

423

431

433 I.moveBeforePreserving(MovePos);

434 }

435}

436

442 while (FromBB.size() > 1) {

445 I.moveBeforePreserving(MovePos->getIterator());

446 }

447}

448

454 "ThisBlock and OtherBlock must be CFG equivalent!");

457 if (CommonDominator == nullptr)

458 return false;

459

460

461

462

466 while (!WorkList.empty()) {

468 Visited.insert(CurBlock);

469 if (PDT->dominates(CurBlock, OtherBlock))

470 return true;

471

472 for (const auto *Pred : predecessors(CurBlock)) {

473 if (Pred == CommonDominator || Visited.count(Pred))

474 continue;

476 }

477 }

478 return false;

479}

480

485 const BasicBlock *BB1 = I1->getParent();

486 if (BB0 == BB1)

488

490}

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

static bool reportInvalidCandidate(const Instruction &I, llvm::Statistic &Stat)

Definition CodeMoverUtils.cpp:269

static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA, const Instruction *InstB)

Definition CodeMoverUtils.cpp:95

static void collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst, SmallPtrSetImpl< Instruction * > &InBetweenInsts)

Collect all instructions in between StartInst and EndInst, and store them in InBetweenInsts.

Definition CodeMoverUtils.cpp:280

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

LLVM Basic Block Representation.

LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const

Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...

const Instruction & front() const

InstListType::iterator iterator

Instruction iterators...

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

BasicBlock * getSuccessor(unsigned i) const

Value * getCondition() const

Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...

bool hasFnAttr(Attribute::AttrKind Kind) const

Determine whether this call has the given attribute.

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

DependenceInfo - This class is the main dependence-analysis driver.

LLVM_ABI std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool UnderRuntimeAssumptions=false)

depends - Tests for a dependence between the Src and Dst instructions.

DomTreeNodeBase * getIDom() const

void updateDFSNumbers() const

updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

LLVM_ABI Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const

Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

LLVM_ABI bool comesBefore(const Instruction *Other) const

Given an instruction Other in the same basic block as this instruction, return true if this instructi...

PointerIntPair - This class implements a pair of a pointer and small integer.

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...

LLVM_ABI bool dominates(const Instruction *I1, const Instruction *I2) const

Return true if I1 dominates I2.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

bool erase(PtrType Ptr)

Remove pointer from the set.

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.

void push_back(const T &Elt)

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

A Use represents the edge between a Value definition and its users.

LLVM Value Representation.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

self_iterator getIterator()

This class implements an extremely fast bulk output stream that can only output to a stream.

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

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.

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)

Return true if the instruction does not have any effects besides calculating the result and does not ...

LLVM_ABI void moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB, DominatorTree &DT, const PostDominatorTree &PDT, DependenceInfo &DI)

Move instructions, in an order-preserving manner, from FromBB to the end of ToBB when proven safe.

Definition CodeMoverUtils.cpp:437

LLVM_ABI bool isReachedBefore(const Instruction *I0, const Instruction *I1, const DominatorTree *DT, const PostDominatorTree *PDT)

Definition CodeMoverUtils.cpp:481

DomTreeNodeBase< BasicBlock > DomTreeNode

bool any_of(R &&range, UnaryPredicate P)

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

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

bool none_of(R &&Range, UnaryPredicate P)

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

LLVM_ABI bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT)

Return true if I0 and I1 are control flow equivalent.

Definition CodeMoverUtils.cpp:231

LLVM_ABI bool nonStrictlyPostDominate(const BasicBlock *ThisBlock, const BasicBlock *OtherBlock, const DominatorTree *DT, const PostDominatorTree *PDT)

In case that two BBs ThisBlock and OtherBlock are control flow equivalent but they do not strictly do...

Definition CodeMoverUtils.cpp:449

bool isa(const From &Val)

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

LLVM_ABI void moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB, DominatorTree &DT, const PostDominatorTree &PDT, DependenceInfo &DI)

Move instructions, in an order-preserving manner, from FromBB to the beginning of ToBB when proven sa...

Definition CodeMoverUtils.cpp:424

DWARFExpression::Operation Op

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

auto predecessors(const MachineBasicBlock *BB)

LLVM_ABI bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT=nullptr, DependenceInfo *DI=nullptr, bool CheckForEntireBlock=false)

Return true if I can be safely moved before InsertPoint.

Definition CodeMoverUtils.cpp:312