Transforms/Coroutines/SuspendCrossingInfo.h

0001 //===- SuspendCrossingInfo.cpp - Utility for suspend crossing values ------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 // The SuspendCrossingInfo maintains data that allows to answer a question
0009 // whether given two BasicBlocks A and B there is a path from A to B that
0010 // passes through a suspend point. Note, SuspendCrossingInfo is invalidated
0011 // by changes to the CFG including adding/removing BBs due to its use of BB
0012 // ptrs in the BlockToIndexMapping.
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_TRANSFORMS_COROUTINES_SUSPENDCROSSINGINFO_H
0016 #define LLVM_TRANSFORMS_COROUTINES_SUSPENDCROSSINGINFO_H
0017
0018 #include "llvm/ADT/BitVector.h"
0019 #include "llvm/ADT/PostOrderIterator.h"
0020 #include "llvm/ADT/SmallVector.h"
0021 #include "llvm/IR/BasicBlock.h"
0022 #include "llvm/IR/Function.h"
0023 #include "llvm/IR/Instruction.h"
0024 #include "llvm/Transforms/Coroutines/CoroInstr.h"
0025
0026 namespace llvm {
0027
0028 class ModuleSlotTracker;
0029
0030 // Provides two way mapping between the blocks and numbers.
0031 class BlockToIndexMapping {
0032   SmallVector<BasicBlock *, 32> V;
0033
0034 public:
0035   size_t size() const { return V.size(); }
0036
0037   BlockToIndexMapping(Function &F) {
0038     for (BasicBlock &BB : F)
0039       V.push_back(&BB);
0040     llvm::sort(V);
0041   }
0042
0043   size_t blockToIndex(BasicBlock const *BB) const {
0044     auto *I = llvm::lower_bound(V, BB);
0045     assert(I != V.end() && *I == BB && "BasicBlockNumberng: Unknown block");
0046     return I - V.begin();
0047   }
0048
0049   BasicBlock *indexToBlock(unsigned Index) const { return V[Index]; }
0050 };
0051
0052 // The SuspendCrossingInfo maintains data that allows to answer a question
0053 // whether given two BasicBlocks A and B there is a path from A to B that
0054 // passes through a suspend point.
0055 //
0056 // For every basic block 'i' it maintains a BlockData that consists of:
0057 //   Consumes:  a bit vector which contains a set of indices of blocks that can
0058 //              reach block 'i'. A block can trivially reach itself.
0059 //   Kills: a bit vector which contains a set of indices of blocks that can
0060 //          reach block 'i' but there is a path crossing a suspend point
0061 //          not repeating 'i' (path to 'i' without cycles containing 'i').
0062 //   Suspend: a boolean indicating whether block 'i' contains a suspend point.
0063 //   End: a boolean indicating whether block 'i' contains a coro.end intrinsic.
0064 //   KillLoop: There is a path from 'i' to 'i' not otherwise repeating 'i' that
0065 //             crosses a suspend point.
0066 //
0067 class SuspendCrossingInfo {
0068   BlockToIndexMapping Mapping;
0069
0070   struct BlockData {
0071     BitVector Consumes;
0072     BitVector Kills;
0073     bool Suspend = false;
0074     bool End = false;
0075     bool KillLoop = false;
0076     bool Changed = false;
0077   };
0078   SmallVector<BlockData, 32> Block;
0079
0080   iterator_range<pred_iterator> predecessors(BlockData const &BD) const {
0081     BasicBlock *BB = Mapping.indexToBlock(&BD - &Block[0]);
0082     return llvm::predecessors(BB);
0083   }
0084
0085   BlockData &getBlockData(BasicBlock *BB) {
0086     return Block[Mapping.blockToIndex(BB)];
0087   }
0088
0089   /// Compute the BlockData for the current function in one iteration.
0090   /// Initialize - Whether this is the first iteration, we can optimize
0091   /// the initial case a little bit by manual loop switch.
0092   /// Returns whether the BlockData changes in this iteration.
0093   template <bool Initialize = false>
0094   bool computeBlockData(const ReversePostOrderTraversal<Function *> &RPOT);
0095
0096 public:
0097 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
0098   // Print order is in RPO
0099   void dump() const;
0100   void dump(StringRef Label, BitVector const &BV,
0101             const ReversePostOrderTraversal<Function *> &RPOT,
0102             ModuleSlotTracker &MST) const;
0103 #endif
0104
0105   SuspendCrossingInfo(Function &F,
0106                       const SmallVectorImpl<AnyCoroSuspendInst *> &CoroSuspends,
0107                       const SmallVectorImpl<AnyCoroEndInst *> &CoroEnds);
0108
0109   /// Returns true if there is a path from \p From to \p To crossing a suspend
0110   /// point without crossing \p From a 2nd time.
0111   bool hasPathCrossingSuspendPoint(BasicBlock *From, BasicBlock *To) const;
0112
0113   /// Returns true if there is a path from \p From to \p To crossing a suspend
0114   /// point without crossing \p From a 2nd time. If \p From is the same as \p To
0115   /// this will also check if there is a looping path crossing a suspend point.
0116   bool hasPathOrLoopCrossingSuspendPoint(BasicBlock *From,
0117                                          BasicBlock *To) const;
0118
0119   bool isDefinitionAcrossSuspend(BasicBlock *DefBB, User *U) const {
0120     auto *I = cast<Instruction>(U);
0121
0122     // We rewrote PHINodes, so that only the ones with exactly one incoming
0123     // value need to be analyzed.
0124     if (auto *PN = dyn_cast<PHINode>(I))
0125       if (PN->getNumIncomingValues() > 1)
0126         return false;
0127
0128     BasicBlock *UseBB = I->getParent();
0129
0130     // As a special case, treat uses by an llvm.coro.suspend.retcon or an
0131     // llvm.coro.suspend.async as if they were uses in the suspend's single
0132     // predecessor: the uses conceptually occur before the suspend.
0133     if (isa<CoroSuspendRetconInst>(I) || isa<CoroSuspendAsyncInst>(I)) {
0134       UseBB = UseBB->getSinglePredecessor();
0135       assert(UseBB && "should have split coro.suspend into its own block");
0136     }
0137
0138     return hasPathCrossingSuspendPoint(DefBB, UseBB);
0139   }
0140
0141   bool isDefinitionAcrossSuspend(Argument &A, User *U) const {
0142     return isDefinitionAcrossSuspend(&A.getParent()->getEntryBlock(), U);
0143   }
0144
0145   bool isDefinitionAcrossSuspend(Instruction &I, User *U) const {
0146     auto *DefBB = I.getParent();
0147
0148     // As a special case, treat values produced by an llvm.coro.suspend.*
0149     // as if they were defined in the single successor: the uses
0150     // conceptually occur after the suspend.
0151     if (isa<AnyCoroSuspendInst>(I)) {
0152       DefBB = DefBB->getSingleSuccessor();
0153       assert(DefBB && "should have split coro.suspend into its own block");
0154     }
0155
0156     return isDefinitionAcrossSuspend(DefBB, U);
0157   }
0158
0159   bool isDefinitionAcrossSuspend(Value &V, User *U) const {
0160     if (auto *Arg = dyn_cast<Argument>(&V))
0161       return isDefinitionAcrossSuspend(*Arg, U);
0162     if (auto *Inst = dyn_cast<Instruction>(&V))
0163       return isDefinitionAcrossSuspend(*Inst, U);
0164
0165     llvm_unreachable(
0166         "Coroutine could only collect Argument and Instruction now.");
0167   }
0168
0169   bool isDefinitionAcrossSuspend(Value &V) const {
0170     if (auto *Arg = dyn_cast<Argument>(&V)) {
0171       for (User *U : Arg->users())
0172         if (isDefinitionAcrossSuspend(*Arg, U))
0173           return true;
0174     } else if (auto *Inst = dyn_cast<Instruction>(&V)) {
0175       for (User *U : Inst->users())
0176         if (isDefinitionAcrossSuspend(*Inst, U))
0177           return true;
0178     }
0179
0180     llvm_unreachable(
0181         "Coroutine could only collect Argument and Instruction now.");
0182   }
0183 };
0184
0185 } // namespace llvm
0186
0187 #endif // LLVM_TRANSFORMS_COROUTINES_SUSPENDCROSSINGINFO_H