1//===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This family of functions perform movements on basic blocks, and instructions
10// contained within a function.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/Utils/CodeMoverUtils.h"
15#include "llvm/ADT/Statistic.h"
16#include "llvm/Analysis/DependenceAnalysis.h"
17#include "llvm/Analysis/PostDominators.h"
18#include "llvm/Analysis/ValueTracking.h"
19#include "llvm/IR/Dominators.h"
20
21using namespace llvm;
22
23#define DEBUG_TYPE "codemover-utils"
24
25STATISTIC(HasDependences,
26          "Cannot move across instructions that has memory dependences");
27STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
28STATISTIC(NotControlFlowEquivalent,
29          "Instructions are not control flow equivalent");
30STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
31STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
32
33namespace {
34/// Represent a control condition. A control condition is a condition of a
35/// terminator to decide which successors to execute. The pointer field
36/// represents the address of the condition of the terminator. The integer field
37/// is a bool, it is true when the basic block is executed when V is true. For
38/// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the
39/// integer field equals to true, while %cond is a control condition of bb1 with
40/// the integer field equals to false.
41using ControlCondition = PointerIntPair<Value *, 1, bool>;
42#ifndef NDEBUG
43raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) {
44  OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")
45     << "]";
46  return OS;
47}
48#endif
49
50/// Represent a set of control conditions required to execute ToBB from FromBB.
51class ControlConditions {
52  using ConditionVectorTy = SmallVector<ControlCondition, 6>;
53
54  /// A SmallVector of control conditions.
55  ConditionVectorTy Conditions;
56
57public:
58  /// Return a ControlConditions which stores all conditions required to execute
59  /// \p BB from \p Dominator. If \p MaxLookup is non-zero, it limits the
60  /// number of conditions to collect. Return std::nullopt if not all conditions
61  /// are collected successfully, or we hit the limit.
62  static const std::optional<ControlConditions>
63  collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator,
64                           const DominatorTree &DT,
65                           const PostDominatorTree &PDT,
66                           unsigned MaxLookup = 6);
67
68  /// Return true if there exists no control conditions required to execute ToBB
69  /// from FromBB.
70  bool isUnconditional() const { return Conditions.empty(); }
71
72  /// Return a constant reference of Conditions.
73  const ConditionVectorTy &getControlConditions() const { return Conditions; }
74
75  /// Add \p V as one of the ControlCondition in Condition with IsTrueCondition
76  /// equals to \p True. Return true if inserted successfully.
77  bool addControlCondition(ControlCondition C);
78
79  /// Return true if for all control conditions in Conditions, there exists an
80  /// equivalent control condition in \p Other.Conditions.
81  bool isEquivalent(const ControlConditions &Other) const;
82
83  /// Return true if \p C1 and \p C2 are equivalent.
84  static bool isEquivalent(const ControlCondition &C1,
85                           const ControlCondition &C2);
86
87private:
88  ControlConditions() = default;
89
90  static bool isEquivalent(const Value &V1, const Value &V2);
91  static bool isInverse(const Value &V1, const Value &V2);
92};
93} // namespace
94
95static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA,
96                               const Instruction *InstB) {
97  // Use ordered basic block in case the 2 instructions are in the same
98  // block.
99  if (InstA->getParent() == InstB->getParent())
100    return InstA->comesBefore(InstB);
101
102  DomTreeNode *DA = DT->getNode(InstA->getParent());
103  DomTreeNode *DB = DT->getNode(InstB->getParent());
104  return DA->getLevel() < DB->getLevel();
105}
106
107const std::optional<ControlConditions>
108ControlConditions::collectControlConditions(const BasicBlock &BB,
109                                            const BasicBlock &Dominator,
110                                            const DominatorTree &DT,
111                                            const PostDominatorTree &PDT,
112                                            unsigned MaxLookup) {
113  assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");
114
115  ControlConditions Conditions;
116  unsigned NumConditions = 0;
117
118  // BB is executed unconditional from itself.
119  if (&Dominator == &BB)
120    return Conditions;
121
122  const BasicBlock *CurBlock = &BB;
123  // Walk up the dominator tree from the associated DT node for BB to the
124  // associated DT node for Dominator.
125  do {
126    assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock");
127    BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock();
128    assert(DT.dominates(&Dominator, IDom) &&
129           "Expecting Dominator to dominate IDom");
130
131    // Limitation: can only handle branch instruction currently.
132    const BranchInst *BI = dyn_cast<BranchInst>(IDom->getTerminator());
133    if (!BI)
134      return std::nullopt;
135
136    bool Inserted = false;
137    if (PDT.dominates(CurBlock, IDom)) {
138      LLVM_DEBUG(dbgs() << CurBlock->getName()
139                        << " is executed unconditionally from "
140                        << IDom->getName() << "\n");
141    } else if (PDT.dominates(CurBlock, BI->getSuccessor(0))) {
142      LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
143                        << *BI->getCondition() << "\" is true from "
144                        << IDom->getName() << "\n");
145      Inserted = Conditions.addControlCondition(
146          ControlCondition(BI->getCondition(), true));
147    } else if (PDT.dominates(CurBlock, BI->getSuccessor(1))) {
148      LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
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) {
169  bool Inserted = false;
170  if (none_of(Conditions, [&](ControlCondition &Exists) {
171        return ControlConditions::isEquivalent(C, Exists);
172      })) {
173    Conditions.push_back(C);
174    Inserted = true;
175  }
176
177  LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n");
178  return Inserted;
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// FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between
207// Values.
208// Currently, isEquivalent rely on other passes to ensure equivalent conditions
209// have the same value, e.g. GVN.
210bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) {
211  return &V1 == &V2;
212}
213
214bool ControlConditions::isInverse(const Value &V1, const Value &V2) {
215  if (const CmpInst *Cmp1 = dyn_cast<CmpInst>(&V1))
216    if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&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() ==
223              CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) &&
224          Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
225          Cmp1->getOperand(1) == Cmp2->getOperand(0))
226        return true;
227    }
228  return false;
229}
230
231bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
232                                   const DominatorTree &DT,
233                                   const PostDominatorTree &PDT) {
234  return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
235}
236
237bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
238                                   const DominatorTree &DT,
239                                   const PostDominatorTree &PDT) {
240  if (&BB0 == &BB1)
241    return true;
242
243  if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
244      (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)))
245    return true;
246
247  // If the set of conditions required to execute BB0 and BB1 from their common
248  // dominator are the same, then BB0 and BB1 are control flow equivalent.
249  const BasicBlock *CommonDominator = DT.findNearestCommonDominator(&BB0, &BB1);
250  LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName()
251                    << " and " << BB1.getName() << " is "
252                    << CommonDominator->getName() << "\n");
253
254  const std::optional<ControlConditions> BB0Conditions =
255      ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,
256                                                  PDT);
257  if (BB0Conditions == std::nullopt)
258    return false;
259
260  const std::optional<ControlConditions> 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
269static bool reportInvalidCandidate(const Instruction &I,
270                                   llvm::Statistic &Stat) {
271  ++Stat;
272  LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
273                    << Stat.getDesc());
274  return false;
275}
276
277/// Collect all instructions in between \p StartInst and \p EndInst, and store
278/// them in \p InBetweenInsts.
279static void
280collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
281                             SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
282  assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
283
284  /// Get the next instructions of \p I, and push them to \p WorkList.
285  auto getNextInsts = [](Instruction &I,
286                         SmallPtrSetImpl<Instruction *> &WorkList) {
287    if (Instruction *NextInst = I.getNextNode())
288      WorkList.insert(NextInst);
289    else {
290      assert(I.isTerminator() && "Expecting a terminator instruction");
291      for (BasicBlock *Succ : successors(&I))
292        WorkList.insert(&Succ->front());
293    }
294  };
295
296  SmallPtrSet<Instruction *, 10> WorkList;
297  getNextInsts(StartInst, WorkList);
298  while (!WorkList.empty()) {
299    Instruction *CurInst = *WorkList.begin();
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
312bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
313                              DominatorTree &DT, const PostDominatorTree *PDT,
314                              DependenceInfo *DI, bool CheckForEntireBlock) {
315  // Skip tests when we don't have PDT or DI
316  if (!PDT || !DI)
317    return false;
318
319  // Cannot move itself before itself.
320  if (&I == &InsertPoint)
321    return false;
322
323  // Not moved.
324  if (I.getNextNode() == &InsertPoint)
325    return true;
326
327  if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
328    return reportInvalidCandidate(I, NotMovedPHINode);
329
330  if (I.isTerminator())
331    return reportInvalidCandidate(I, NotMovedTerminator);
332
333  // TODO remove this limitation.
334  if (!isControlFlowEquivalent(I, InsertPoint, DT, *PDT))
335    return reportInvalidCandidate(I, NotControlFlowEquivalent);
336
337  if (isReachedBefore(&I, &InsertPoint, &DT, PDT))
338    for (const Use &U : I.uses())
339      if (auto *UserInst = dyn_cast<Instruction>(U.getUser()))
340        if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U))
341          return false;
342  if (isReachedBefore(&InsertPoint, &I, &DT, PDT))
343    for (const Value *Op : I.operands())
344      if (auto *OpInst = dyn_cast<Instruction>(Op)) {
345        if (&InsertPoint == OpInst)
346          return false;
347        // If OpInst is an instruction that appears earlier in the same BB as
348        // I, then it is okay to move since OpInst will still be available.
349        if (CheckForEntireBlock && I.getParent() == OpInst->getParent() &&
350            DT.dominates(OpInst, &I))
351          continue;
352        if (!DT.dominates(OpInst, &InsertPoint))
353          return false;
354      }
355
356  DT.updateDFSNumbers();
357  const bool MoveForward = domTreeLevelBefore(&DT, &I, &InsertPoint);
358  Instruction &StartInst = (MoveForward ? I : InsertPoint);
359  Instruction &EndInst = (MoveForward ? InsertPoint : I);
360  SmallPtrSet<Instruction *, 10> InstsToCheck;
361  collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
362  if (!MoveForward)
363    InstsToCheck.insert(&InsertPoint);
364
365  // Check if there exists instructions which may throw, may synchonize, or may
366  // never return, from I to InsertPoint.
367  if (!isSafeToSpeculativelyExecute(&I))
368    if (llvm::any_of(InstsToCheck, [](Instruction *I) {
369          if (I->mayThrow())
370            return true;
371
372          const CallBase *CB = dyn_cast<CallBase>(I);
373          if (!CB)
374            return false;
375          if (!CB->hasFnAttr(Attribute::WillReturn))
376            return true;
377          if (!CB->hasFnAttr(Attribute::NoSync))
378            return true;
379
380          return false;
381        })) {
382      return reportInvalidCandidate(I, MayThrowException);
383    }
384
385  // Check if I has any output/flow/anti dependences with instructions from \p
386  // StartInst to \p EndInst.
387  if (llvm::any_of(InstsToCheck, [&DI, &I](Instruction *CurInst) {
388        auto DepResult = DI->depends(&I, CurInst, true);
389        if (DepResult && (DepResult->isOutput() || DepResult->isFlow() ||
390                          DepResult->isAnti()))
391          return true;
392        return false;
393      }))
394    return reportInvalidCandidate(I, HasDependences);
395
396  return true;
397}
398
399bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
400                              DominatorTree &DT, const PostDominatorTree *PDT,
401                              DependenceInfo *DI) {
402  return llvm::all_of(BB, [&](Instruction &I) {
403    if (BB.getTerminator() == &I)
404      return true;
405
406    return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI,
407                              /*CheckForEntireBlock=*/true);
408  });
409}
410
411void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
412                                          DominatorTree &DT,
413                                          const PostDominatorTree &PDT,
414                                          DependenceInfo &DI) {
415  for (Instruction &I :
416       llvm::make_early_inc_range(llvm::drop_begin(llvm::reverse(FromBB)))) {
417    Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
418
419    if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
420      I.moveBeforePreserving(MovePos);
421  }
422}
423
424void llvm::moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB,
425                                    DominatorTree &DT,
426                                    const PostDominatorTree &PDT,
427                                    DependenceInfo &DI) {
428  Instruction *MovePos = ToBB.getTerminator();
429  while (FromBB.size() > 1) {
430    Instruction &I = FromBB.front();
431    if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
432      I.moveBeforePreserving(MovePos);
433  }
434}
435
436bool llvm::nonStrictlyPostDominate(const BasicBlock *ThisBlock,
437                                   const BasicBlock *OtherBlock,
438                                   const DominatorTree *DT,
439                                   const PostDominatorTree *PDT) {
440  assert(isControlFlowEquivalent(*ThisBlock, *OtherBlock, *DT, *PDT) &&
441         "ThisBlock and OtherBlock must be CFG equivalent!");
442  const BasicBlock *CommonDominator =
443      DT->findNearestCommonDominator(ThisBlock, OtherBlock);
444  if (CommonDominator == nullptr)
445    return false;
446
447  /// Recursively check the predecessors of \p ThisBlock up to
448  /// their common dominator, and see if any of them post-dominates
449  /// \p OtherBlock.
450  SmallVector<const BasicBlock *, 8> WorkList;
451  SmallPtrSet<const BasicBlock *, 8> Visited;
452  WorkList.push_back(ThisBlock);
453  while (!WorkList.empty()) {
454    const BasicBlock *CurBlock = WorkList.back();
455    WorkList.pop_back();
456    Visited.insert(CurBlock);
457    if (PDT->dominates(CurBlock, OtherBlock))
458      return true;
459
460    for (const auto *Pred : predecessors(CurBlock)) {
461      if (Pred == CommonDominator || Visited.count(Pred))
462        continue;
463      WorkList.push_back(Pred);
464    }
465  }
466  return false;
467}
468
469bool llvm::isReachedBefore(const Instruction *I0, const Instruction *I1,
470                           const DominatorTree *DT,
471                           const PostDominatorTree *PDT) {
472  const BasicBlock *BB0 = I0->getParent();
473  const BasicBlock *BB1 = I1->getParent();
474  if (BB0 == BB1)
475    return DT->dominates(I0, I1);
476
477  return nonStrictlyPostDominate(BB1, BB0, DT, PDT);
478}
479