CodeMoverUtils.cpp revision 360784 
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
33bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
34                                   const DominatorTree &DT,
35                                   const PostDominatorTree &PDT) {
36  return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
37}
38
39bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
40                                   const DominatorTree &DT,
41                                   const PostDominatorTree &PDT) {
42  if (&BB0 == &BB1)
43    return true;
44
45  return ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
46          (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)));
47}
48
49static bool reportInvalidCandidate(const Instruction &I,
50                                   llvm::Statistic &Stat) {
51  ++Stat;
52  LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
53                    << Stat.getDesc());
54  return false;
55}
56
57/// Collect all instructions in between \p StartInst and \p EndInst, and store
58/// them in \p InBetweenInsts.
59static void
60collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
61                             SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
62  assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
63
64  /// Get the next instructions of \p I, and push them to \p WorkList.
65  auto getNextInsts = [](Instruction &I,
66                         SmallPtrSetImpl<Instruction *> &WorkList) {
67    if (Instruction *NextInst = I.getNextNode())
68      WorkList.insert(NextInst);
69    else {
70      assert(I.isTerminator() && "Expecting a terminator instruction");
71      for (BasicBlock *Succ : successors(&I))
72        WorkList.insert(&Succ->front());
73    }
74  };
75
76  SmallPtrSet<Instruction *, 10> WorkList;
77  getNextInsts(StartInst, WorkList);
78  while (!WorkList.empty()) {
79    Instruction *CurInst = *WorkList.begin();
80    WorkList.erase(CurInst);
81
82    if (CurInst == &EndInst)
83      continue;
84
85    if (!InBetweenInsts.insert(CurInst).second)
86      continue;
87
88    getNextInsts(*CurInst, WorkList);
89  }
90}
91
92bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
93                              const DominatorTree &DT,
94                              const PostDominatorTree &PDT,
95                              DependenceInfo &DI) {
96  // Cannot move itself before itself.
97  if (&I == &InsertPoint)
98    return false;
99
100  // Not moved.
101  if (I.getNextNode() == &InsertPoint)
102    return true;
103
104  if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
105    return reportInvalidCandidate(I, NotMovedPHINode);
106
107  if (I.isTerminator())
108    return reportInvalidCandidate(I, NotMovedTerminator);
109
110  // TODO remove this limitation.
111  if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT))
112    return reportInvalidCandidate(I, NotControlFlowEquivalent);
113
114  // As I and InsertPoint are control flow equivalent, if I dominates
115  // InsertPoint, then I comes before InsertPoint.
116  const bool MoveForward = DT.dominates(&I, &InsertPoint);
117  if (MoveForward) {
118    // When I is being moved forward, we need to make sure the InsertPoint
119    // dominates every users. Or else, a user may be using an undefined I.
120    for (const Use &U : I.uses())
121      if (auto *UserInst = dyn_cast<Instruction>(U.getUser()))
122        if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U))
123          return false;
124  } else {
125    // When I is being moved backward, we need to make sure all its opernads
126    // dominates the InsertPoint. Or else, an operand may be undefined for I.
127    for (const Value *Op : I.operands())
128      if (auto *OpInst = dyn_cast<Instruction>(Op))
129        if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint))
130          return false;
131  }
132
133  Instruction &StartInst = (MoveForward ? I : InsertPoint);
134  Instruction &EndInst = (MoveForward ? InsertPoint : I);
135  SmallPtrSet<Instruction *, 10> InstsToCheck;
136  collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
137  if (!MoveForward)
138    InstsToCheck.insert(&InsertPoint);
139
140  // Check if there exists instructions which may throw, may synchonize, or may
141  // never return, from I to InsertPoint.
142  if (!isSafeToSpeculativelyExecute(&I))
143    if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
144                    [](Instruction *I) {
145                      if (I->mayThrow())
146                        return true;
147
148                      const CallBase *CB = dyn_cast<CallBase>(I);
149                      if (!CB)
150                        return false;
151                      if (!CB->hasFnAttr(Attribute::WillReturn))
152                        return true;
153                      if (!CB->hasFnAttr(Attribute::NoSync))
154                        return true;
155
156                      return false;
157                    })) {
158      return reportInvalidCandidate(I, MayThrowException);
159    }
160
161  // Check if I has any output/flow/anti dependences with instructions from \p
162  // StartInst to \p EndInst.
163  if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
164                  [&DI, &I](Instruction *CurInst) {
165                    auto DepResult = DI.depends(&I, CurInst, true);
166                    if (DepResult &&
167                        (DepResult->isOutput() || DepResult->isFlow() ||
168                         DepResult->isAnti()))
169                      return true;
170                    return false;
171                  }))
172    return reportInvalidCandidate(I, HasDependences);
173
174  return true;
175}
176
177void llvm::moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB,
178                             const DominatorTree &DT,
179                             const PostDominatorTree &PDT, DependenceInfo &DI) {
180  for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) {
181    Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
182    Instruction &I = *It;
183    // Increment the iterator before modifying FromBB.
184    ++It;
185
186    if (isSafeToMoveBefore(I, *MovePos, DT, PDT, DI))
187      I.moveBefore(MovePos);
188  }
189}
190