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/Optional.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/Analysis/DependenceAnalysis.h"
18#include "llvm/Analysis/PostDominators.h"
19#include "llvm/Analysis/ValueTracking.h"
20#include "llvm/IR/Dominators.h"
21
22using namespace llvm;
23
24#define DEBUG_TYPE "codemover-utils"
25
26STATISTIC(HasDependences,
27          "Cannot move across instructions that has memory dependences");
28STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
29STATISTIC(NotControlFlowEquivalent,
30          "Instructions are not control flow equivalent");
31STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
32STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
33
34namespace {
35/// Represent a control condition. A control condition is a condition of a
36/// terminator to decide which successors to execute. The pointer field
37/// represents the address of the condition of the terminator. The integer field
38/// is a bool, it is true when the basic block is executed when V is true. For
39/// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the
40/// integer field equals to true, while %cond is a control condition of bb1 with
41/// the integer field equals to false.
42using ControlCondition = PointerIntPair<Value *, 1, bool>;
43#ifndef NDEBUG
44raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) {
45  OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")
46     << "]";
47  return OS;
48}
49#endif
50
51/// Represent a set of control conditions required to execute ToBB from FromBB.
52class ControlConditions {
53  using ConditionVectorTy = SmallVector<ControlCondition, 6>;
54
55  /// A SmallVector of control conditions.
56  ConditionVectorTy Conditions;
57
58public:
59  /// Return a ControlConditions which stores all conditions required to execute
60  /// \p BB from \p Dominator. If \p MaxLookup is non-zero, it limits the
61  /// number of conditions to collect. Return None if not all conditions are
62  /// collected successfully, or we hit the limit.
63  static const Optional<ControlConditions>
64  collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator,
65                           const DominatorTree &DT,
66                           const PostDominatorTree &PDT,
67                           unsigned MaxLookup = 6);
68
69  /// Return true if there exists no control conditions required to execute ToBB
70  /// from FromBB.
71  bool isUnconditional() const { return Conditions.empty(); }
72
73  /// Return a constant reference of Conditions.
74  const ConditionVectorTy &getControlConditions() const { return Conditions; }
75
76  /// Add \p V as one of the ControlCondition in Condition with IsTrueCondition
77  /// equals to \p True. Return true if inserted successfully.
78  bool addControlCondition(ControlCondition C);
79
80  /// Return true if for all control conditions in Conditions, there exists an
81  /// equivalent control condition in \p Other.Conditions.
82  bool isEquivalent(const ControlConditions &Other) const;
83
84  /// Return true if \p C1 and \p C2 are equivalent.
85  static bool isEquivalent(const ControlCondition &C1,
86                           const ControlCondition &C2);
87
88private:
89  ControlConditions() = default;
90
91  static bool isEquivalent(const Value &V1, const Value &V2);
92  static bool isInverse(const Value &V1, const Value &V2);
93};
94} // namespace
95
96static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA,
97                               const Instruction *InstB) {
98  // Use ordered basic block in case the 2 instructions are in the same
99  // block.
100  if (InstA->getParent() == InstB->getParent())
101    return InstA->comesBefore(InstB);
102
103  DomTreeNode *DA = DT->getNode(InstA->getParent());
104  DomTreeNode *DB = DT->getNode(InstB->getParent());
105  return DA->getLevel() < DB->getLevel();
106}
107
108const Optional<ControlConditions> ControlConditions::collectControlConditions(
109    const BasicBlock &BB, const BasicBlock &Dominator, const DominatorTree &DT,
110    const PostDominatorTree &PDT, unsigned MaxLookup) {
111  assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");
112
113  ControlConditions Conditions;
114  unsigned NumConditions = 0;
115
116  // BB is executed unconditional from itself.
117  if (&Dominator == &BB)
118    return Conditions;
119
120  const BasicBlock *CurBlock = &BB;
121  // Walk up the dominator tree from the associated DT node for BB to the
122  // associated DT node for Dominator.
123  do {
124    assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock");
125    BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock();
126    assert(DT.dominates(&Dominator, IDom) &&
127           "Expecting Dominator to dominate IDom");
128
129    // Limitation: can only handle branch instruction currently.
130    const BranchInst *BI = dyn_cast<BranchInst>(IDom->getTerminator());
131    if (!BI)
132      return None;
133
134    bool Inserted = false;
135    if (PDT.dominates(CurBlock, IDom)) {
136      LLVM_DEBUG(dbgs() << CurBlock->getName()
137                        << " is executed unconditionally from "
138                        << IDom->getName() << "\n");
139    } else if (PDT.dominates(CurBlock, BI->getSuccessor(0))) {
140      LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
141                        << *BI->getCondition() << "\" is true from "
142                        << IDom->getName() << "\n");
143      Inserted = Conditions.addControlCondition(
144          ControlCondition(BI->getCondition(), true));
145    } else if (PDT.dominates(CurBlock, BI->getSuccessor(1))) {
146      LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
147                        << *BI->getCondition() << "\" is false from "
148                        << IDom->getName() << "\n");
149      Inserted = Conditions.addControlCondition(
150          ControlCondition(BI->getCondition(), false));
151    } else
152      return None;
153
154    if (Inserted)
155      ++NumConditions;
156
157    if (MaxLookup != 0 && NumConditions > MaxLookup)
158      return None;
159
160    CurBlock = IDom;
161  } while (CurBlock != &Dominator);
162
163  return Conditions;
164}
165
166bool ControlConditions::addControlCondition(ControlCondition C) {
167  bool Inserted = false;
168  if (none_of(Conditions, [&](ControlCondition &Exists) {
169        return ControlConditions::isEquivalent(C, Exists);
170      })) {
171    Conditions.push_back(C);
172    Inserted = true;
173  }
174
175  LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n");
176  return Inserted;
177}
178
179bool ControlConditions::isEquivalent(const ControlConditions &Other) const {
180  if (Conditions.empty() && Other.Conditions.empty())
181    return true;
182
183  if (Conditions.size() != Other.Conditions.size())
184    return false;
185
186  return all_of(Conditions, [&](const ControlCondition &C) {
187    return any_of(Other.Conditions, [&](const ControlCondition &OtherC) {
188      return ControlConditions::isEquivalent(C, OtherC);
189    });
190  });
191}
192
193bool ControlConditions::isEquivalent(const ControlCondition &C1,
194                                     const ControlCondition &C2) {
195  if (C1.getInt() == C2.getInt()) {
196    if (isEquivalent(*C1.getPointer(), *C2.getPointer()))
197      return true;
198  } else if (isInverse(*C1.getPointer(), *C2.getPointer()))
199    return true;
200
201  return false;
202}
203
204// FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between
205// Values.
206// Currently, isEquivalent rely on other passes to ensure equivalent conditions
207// have the same value, e.g. GVN.
208bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) {
209  return &V1 == &V2;
210}
211
212bool ControlConditions::isInverse(const Value &V1, const Value &V2) {
213  if (const CmpInst *Cmp1 = dyn_cast<CmpInst>(&V1))
214    if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&V2)) {
215      if (Cmp1->getPredicate() == Cmp2->getInversePredicate() &&
216          Cmp1->getOperand(0) == Cmp2->getOperand(0) &&
217          Cmp1->getOperand(1) == Cmp2->getOperand(1))
218        return true;
219
220      if (Cmp1->getPredicate() ==
221              CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) &&
222          Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
223          Cmp1->getOperand(1) == Cmp2->getOperand(0))
224        return true;
225    }
226  return false;
227}
228
229bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
230                                   const DominatorTree &DT,
231                                   const PostDominatorTree &PDT) {
232  return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
233}
234
235bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
236                                   const DominatorTree &DT,
237                                   const PostDominatorTree &PDT) {
238  if (&BB0 == &BB1)
239    return true;
240
241  if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
242      (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)))
243    return true;
244
245  // If the set of conditions required to execute BB0 and BB1 from their common
246  // dominator are the same, then BB0 and BB1 are control flow equivalent.
247  const BasicBlock *CommonDominator = DT.findNearestCommonDominator(&BB0, &BB1);
248  LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName()
249                    << " and " << BB1.getName() << " is "
250                    << CommonDominator->getName() << "\n");
251
252  const Optional<ControlConditions> BB0Conditions =
253      ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,
254                                                  PDT);
255  if (BB0Conditions == None)
256    return false;
257
258  const Optional<ControlConditions> BB1Conditions =
259      ControlConditions::collectControlConditions(BB1, *CommonDominator, DT,
260                                                  PDT);
261  if (BB1Conditions == None)
262    return false;
263
264  return BB0Conditions->isEquivalent(*BB1Conditions);
265}
266
267static bool reportInvalidCandidate(const Instruction &I,
268                                   llvm::Statistic &Stat) {
269  ++Stat;
270  LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
271                    << Stat.getDesc());
272  return false;
273}
274
275/// Collect all instructions in between \p StartInst and \p EndInst, and store
276/// them in \p InBetweenInsts.
277static void
278collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
279                             SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
280  assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
281
282  /// Get the next instructions of \p I, and push them to \p WorkList.
283  auto getNextInsts = [](Instruction &I,
284                         SmallPtrSetImpl<Instruction *> &WorkList) {
285    if (Instruction *NextInst = I.getNextNode())
286      WorkList.insert(NextInst);
287    else {
288      assert(I.isTerminator() && "Expecting a terminator instruction");
289      for (BasicBlock *Succ : successors(&I))
290        WorkList.insert(&Succ->front());
291    }
292  };
293
294  SmallPtrSet<Instruction *, 10> WorkList;
295  getNextInsts(StartInst, WorkList);
296  while (!WorkList.empty()) {
297    Instruction *CurInst = *WorkList.begin();
298    WorkList.erase(CurInst);
299
300    if (CurInst == &EndInst)
301      continue;
302
303    if (!InBetweenInsts.insert(CurInst).second)
304      continue;
305
306    getNextInsts(*CurInst, WorkList);
307  }
308}
309
310bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
311                              DominatorTree &DT, const PostDominatorTree *PDT,
312                              DependenceInfo *DI) {
313  // Skip tests when we don't have PDT or DI
314  if (!PDT || !DI)
315    return false;
316
317  // Cannot move itself before itself.
318  if (&I == &InsertPoint)
319    return false;
320
321  // Not moved.
322  if (I.getNextNode() == &InsertPoint)
323    return true;
324
325  if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
326    return reportInvalidCandidate(I, NotMovedPHINode);
327
328  if (I.isTerminator())
329    return reportInvalidCandidate(I, NotMovedTerminator);
330
331  // TODO remove this limitation.
332  if (!isControlFlowEquivalent(I, InsertPoint, DT, *PDT))
333    return reportInvalidCandidate(I, NotControlFlowEquivalent);
334
335  if (!DT.dominates(&InsertPoint, &I))
336    for (const Use &U : I.uses())
337      if (auto *UserInst = dyn_cast<Instruction>(U.getUser()))
338        if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U))
339          return false;
340  if (!DT.dominates(&I, &InsertPoint))
341    for (const Value *Op : I.operands())
342      if (auto *OpInst = dyn_cast<Instruction>(Op))
343        if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint))
344          return false;
345
346  DT.updateDFSNumbers();
347  const bool MoveForward = domTreeLevelBefore(&DT, &I, &InsertPoint);
348  Instruction &StartInst = (MoveForward ? I : InsertPoint);
349  Instruction &EndInst = (MoveForward ? InsertPoint : I);
350  SmallPtrSet<Instruction *, 10> InstsToCheck;
351  collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
352  if (!MoveForward)
353    InstsToCheck.insert(&InsertPoint);
354
355  // Check if there exists instructions which may throw, may synchonize, or may
356  // never return, from I to InsertPoint.
357  if (!isSafeToSpeculativelyExecute(&I))
358    if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
359                    [](Instruction *I) {
360                      if (I->mayThrow())
361                        return true;
362
363                      const CallBase *CB = dyn_cast<CallBase>(I);
364                      if (!CB)
365                        return false;
366                      if (!CB->hasFnAttr(Attribute::WillReturn))
367                        return true;
368                      if (!CB->hasFnAttr(Attribute::NoSync))
369                        return true;
370
371                      return false;
372                    })) {
373      return reportInvalidCandidate(I, MayThrowException);
374    }
375
376  // Check if I has any output/flow/anti dependences with instructions from \p
377  // StartInst to \p EndInst.
378  if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
379                  [&DI, &I](Instruction *CurInst) {
380                    auto DepResult = DI->depends(&I, CurInst, true);
381                    if (DepResult &&
382                        (DepResult->isOutput() || DepResult->isFlow() ||
383                         DepResult->isAnti()))
384                      return true;
385                    return false;
386                  }))
387    return reportInvalidCandidate(I, HasDependences);
388
389  return true;
390}
391
392bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
393                              DominatorTree &DT, const PostDominatorTree *PDT,
394                              DependenceInfo *DI) {
395  return llvm::all_of(BB, [&](Instruction &I) {
396    if (BB.getTerminator() == &I)
397      return true;
398
399    return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI);
400  });
401}
402
403void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
404                                          DominatorTree &DT,
405                                          const PostDominatorTree &PDT,
406                                          DependenceInfo &DI) {
407  for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) {
408    Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
409    Instruction &I = *It;
410    // Increment the iterator before modifying FromBB.
411    ++It;
412
413    if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
414      I.moveBefore(MovePos);
415  }
416}
417
418void llvm::moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB,
419                                    DominatorTree &DT,
420                                    const PostDominatorTree &PDT,
421                                    DependenceInfo &DI) {
422  Instruction *MovePos = ToBB.getTerminator();
423  while (FromBB.size() > 1) {
424    Instruction &I = FromBB.front();
425    if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
426      I.moveBefore(MovePos);
427  }
428}
429