CbC/CbC_llvm: lib/IR/SafepointIRVerifier.cpp comparison

comparison lib/IR/SafepointIRVerifier.cpp @ 148:63bd29f05246

merged

author	Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date	Wed, 14 Aug 2019 19:46:37 +0900
parents	c2174574ed3a
children

comparison

equal deleted inserted replaced

-:3fc4d5c3e21e
+:63bd29f05246
 //===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===//
 //
-//                     The LLVM Compiler Infrastructure
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-//
+// See https://llvm.org/LICENSE.txt for license information.
-// This file is distributed under the University of Illinois Open Source
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Run a sanity check on the IR to ensure that Safepoints - if they've been
 // inserted - were inserted correctly.  In particular, look for use of
 /// when verification fails, report a message to the console (for FileCheck
 /// usage) and continue execution as if nothing happened.
 static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only",
 cl::init(false));
-static void Verify(const Function &F, const DominatorTree &DT);
 namespace {
+/// This CFG Deadness finds dead blocks and edges. Algorithm starts with a set
+/// of blocks unreachable from entry then propagates deadness using foldable
+/// conditional branches without modifying CFG. So GVN does but it changes CFG
+/// by splitting critical edges. In most cases passes rely on SimplifyCFG to
+/// clean up dead blocks, but in some cases, like verification or loop passes
+/// it's not possible.
+class CFGDeadness {
+const DominatorTree *DT = nullptr;
+SetVector<const BasicBlock *> DeadBlocks;
+SetVector<const Use *> DeadEdges; // Contains all dead edges from live blocks.
+public:
+/// Return the edge that coresponds to the predecessor.
+static const Use& getEdge(const_pred_iterator &PredIt) {
+auto &PU = PredIt.getUse();
+return PU.getUser()->getOperandUse(PU.getOperandNo());
+}
+/// Return true if there is at least one live edge that corresponds to the
+/// basic block InBB listed in the phi node.
+bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
+assert(!isDeadBlock(InBB) && "block must be live");
+const BasicBlock* BB = PN->getParent();
+bool Listed = false;
+for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
+if (InBB == *PredIt) {
+if (!isDeadEdge(&getEdge(PredIt)))
+return true;
+Listed = true;
+}
+}
+(void)Listed;
+assert(Listed && "basic block is not found among incoming blocks");
+return false;
+}
+bool isDeadBlock(const BasicBlock *BB) const {
+return DeadBlocks.count(BB);
+}
+bool isDeadEdge(const Use *U) const {
+assert(dyn_cast<Instruction>(U->getUser())->isTerminator() &&
+"edge must be operand of terminator");
+assert(cast_or_null<BasicBlock>(U->get()) &&
+"edge must refer to basic block");
+assert(!isDeadBlock(dyn_cast<Instruction>(U->getUser())->getParent()) &&
+"isDeadEdge() must be applied to edge from live block");
+return DeadEdges.count(U);
+}
+bool hasLiveIncomingEdges(const BasicBlock *BB) const {
+// Check if all incoming edges are dead.
+for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
+auto &PU = PredIt.getUse();
+const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo());
+if (!isDeadBlock(*PredIt) && !isDeadEdge(&U))
+return true; // Found a live edge.
+}
+return false;
+}
+void processFunction(const Function &F, const DominatorTree &DT) {
+this->DT = &DT;
+// Start with all blocks unreachable from entry.
+for (const BasicBlock &BB : F)
+if (!DT.isReachableFromEntry(&BB))
+DeadBlocks.insert(&BB);
+// Top-down walk of the dominator tree
+ReversePostOrderTraversal<const Function *> RPOT(&F);
+for (const BasicBlock *BB : RPOT) {
+const Instruction *TI = BB->getTerminator();
+assert(TI && "blocks must be well formed");
+// For conditional branches, we can perform simple conditional propagation on
+// the condition value itself.
+const BranchInst *BI = dyn_cast<BranchInst>(TI);
+if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition()))
+continue;
+// If a branch has two identical successors, we cannot declare either dead.
+if (BI->getSuccessor(0) == BI->getSuccessor(1))
+continue;
+ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
+if (!Cond)
+continue;
+addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2));
+}
+}
+protected:
+void addDeadBlock(const BasicBlock *BB) {
+SmallVector<const BasicBlock *, 4> NewDead;
+SmallSetVector<const BasicBlock *, 4> DF;
+NewDead.push_back(BB);
+while (!NewDead.empty()) {
+const BasicBlock *D = NewDead.pop_back_val();
+if (isDeadBlock(D))
+continue;
+// All blocks dominated by D are dead.
+SmallVector<BasicBlock *, 8> Dom;
+DT->getDescendants(const_cast<BasicBlock*>(D), Dom);
+// Do not need to mark all in and out edges dead
+// because BB is marked dead and this is enough
+// to run further.
+DeadBlocks.insert(Dom.begin(), Dom.end());
+// Figure out the dominance-frontier(D).
+for (BasicBlock *B : Dom)
+for (BasicBlock *S : successors(B))
+if (!isDeadBlock(S) && !hasLiveIncomingEdges(S))
+NewDead.push_back(S);
+}
+}
+void addDeadEdge(const Use &DeadEdge) {
+if (!DeadEdges.insert(&DeadEdge))
+return;
+BasicBlock *BB = cast_or_null<BasicBlock>(DeadEdge.get());
+if (hasLiveIncomingEdges(BB))
+return;
+addDeadBlock(BB);
+}
+};
+} // namespace
+static void Verify(const Function &F, const DominatorTree &DT,
+const CFGDeadness &CD);
+namespace llvm {
+PreservedAnalyses SafepointIRVerifierPass::run(Function &F,
+FunctionAnalysisManager &AM) {
+const auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+CFGDeadness CD;
+CD.processFunction(F, DT);
+Verify(F, DT, CD);
+return PreservedAnalyses::all();
+}
+}
+namespace {
 struct SafepointIRVerifier : public FunctionPass {
 static char ID; // Pass identification, replacement for typeid
-DominatorTree DT;
 SafepointIRVerifier() : FunctionPass(ID) {
 initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
 }
 bool runOnFunction(Function &F) override {
-DT.recalculate(F);
+auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-Verify(F, DT);
+CFGDeadness CD;
+CD.processFunction(F, DT);
+Verify(F, DT, CD);
 return false; // no modifications
 }
 void getAnalysisUsage(AnalysisUsage &AU) const override {
+AU.addRequiredID(DominatorTreeWrapperPass::ID);
 AU.setPreservesAll();
 }
 StringRef getPassName() const override { return "safepoint verifier"; }
 };
 FunctionPass *llvm::createSafepointIRVerifierPass() {
 return new SafepointIRVerifier();
 }
 INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
-"Safepoint IR Verifier", false, true)
+"Safepoint IR Verifier", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",
-"Safepoint IR Verifier", false, true)
+"Safepoint IR Verifier", false, false)
 static bool isGCPointerType(Type *T) {
 if (auto *PT = dyn_cast<PointerType>(T))
 // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
 // GC managed heap.  We know that a pointer into this heap needs to be
 if (VectorType *VT = dyn_cast<VectorType>(Ty))
 return isGCPointerType(VT->getScalarType());
 if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
 return containsGCPtrType(AT->getElementType());
 if (StructType *ST = dyn_cast<StructType>(Ty))
-return std::any_of(ST->subtypes().begin(), ST->subtypes().end(),
+return llvm::any_of(ST->elements(), containsGCPtrType);
-containsGCPtrType);
 return false;
 }
 // Debugging aid -- prints a [Begin, End) range of values.
 template<typename IteratorTy>
 /// To fix this we need to introduce conception of generations and be able to
 /// check if two values belong to one generation or not. This way p2 will be
 /// considered to be unrelocated and no false alarm will happen.
 class GCPtrTracker {
 const Function &F;
+const CFGDeadness &CD;
 SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;
 DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;
 // This set contains defs of unrelocated pointers that are proved to be legal
 // and don't need verification.
 DenseSet<const Instruction *> ValidUnrelocatedDefs;
 // This set contains poisoned defs. They can be safely ignored during
 // verification too.
 DenseSet<const Value *> PoisonedDefs;
 public:
-GCPtrTracker(const Function &F, const DominatorTree &DT);
+GCPtrTracker(const Function &F, const DominatorTree &DT,
+const CFGDeadness &CD);
+bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
+return CD.hasLiveIncomingEdge(PN, InBB);
+}
 BasicBlockState *getBasicBlockState(const BasicBlock *BB);
 const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;
 bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }
 /// It destructively modifies GCPtrTracker so it's passed via rvalue reference
 /// in order to prohibit further usages of GCPtrTracker as it'll be in
 /// inconsistent state.
 static void verifyFunction(GCPtrTracker &&Tracker,
 InstructionVerifier &Verifier);
+/// Returns true for reachable and live blocks.
+bool isMapped(const BasicBlock *BB) const {
+return BlockMap.find(BB) != BlockMap.end();
+}
 private:
 /// Returns true if the instruction may be safely skipped during verification.
 bool instructionMayBeSkipped(const Instruction *I) const;
 private:
 void reportInvalidUse(const Value &V, const Instruction &I);
 };
 } // end anonymous namespace
-GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT) : F(F) {
+GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT,
-// First, calculate Contribution of each BB.
+const CFGDeadness &CD) : F(F), CD(CD) {
-for (const BasicBlock &BB : F) {
+// Calculate Contribution of each live BB.
-BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
+// Allocate BB states for live blocks.
-for (const auto &I : BB)
+for (const BasicBlock &BB : F)
-transferInstruction(I, BBS->Cleared, BBS->Contribution);
+if (!CD.isDeadBlock(&BB)) {
-BlockMap[&BB] = BBS;
+BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
-}
+for (const auto &I : BB)
+transferInstruction(I, BBS->Cleared, BBS->Contribution);
+BlockMap[&BB] = BBS;
+}
 // Initialize AvailableIn/Out sets of each BB using only information about
 // dominating BBs.
 for (auto &BBI : BlockMap) {
 gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
 recalculateBBsStates();
 }
 BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
 auto it = BlockMap.find(BB);
-assert(it != BlockMap.end() &&
+return it != BlockMap.end() ? it->second : nullptr;
-"No such BB in BlockMap! Probably BB from another function");
-return it->second;
 }
 const BasicBlockState *GCPtrTracker::getBasicBlockState(
 const BasicBlock *BB) const {
 return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
 // We need RPO here to a) report always the first error b) report errors in
 // same order from run to run.
 ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F);
 for (const BasicBlock *BB : RPOT) {
 BasicBlockState *BBS = Tracker.getBasicBlockState(BB);
+if (!BBS)
+continue;
 // We destructively modify AvailableIn as we traverse the block instruction
 // by instruction.
 AvailableValueSet &AvailableSet = BBS->AvailableIn;
 for (const Instruction &I : *BB) {
 if (Tracker.instructionMayBeSkipped(&I))
 // This loop iterates the AvailableIn/Out sets until it converges.
 // The AvailableIn and AvailableOut sets decrease as we iterate.
 while (!Worklist.empty()) {
 const BasicBlock *BB = Worklist.pop_back_val();
-BasicBlockState *BBS = BlockMap[BB];
+BasicBlockState *BBS = getBasicBlockState(BB);
+if (!BBS)
+continue; // Ignore dead successors.
 size_t OldInCount = BBS->AvailableIn.size();
-for (const BasicBlock *PBB : predecessors(BB))
+for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
-set_intersect(BBS->AvailableIn, BlockMap[PBB]->AvailableOut);
+const BasicBlock *PBB = *PredIt;
+BasicBlockState *PBBS = getBasicBlockState(PBB);
+if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt)))
+set_intersect(BBS->AvailableIn, PBBS->AvailableOut);
+}
 assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
 bool InputsChanged = OldInCount != BBS->AvailableIn.size();
 bool ContributionChanged =
 // If both is true, output is poisoned.
 bool HasRelocatedInputs = false;
 bool HasUnrelocatedInputs = false;
 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 const BasicBlock *InBB = PN->getIncomingBlock(i);
+if (!isMapped(InBB) ||
+!CD.hasLiveIncomingEdge(PN, InBB))
+continue; // Skip dead block or dead edge.
 const Value *InValue = PN->getIncomingValue(i);
 if (isNotExclusivelyConstantDerived(InValue)) {
 if (isValuePoisoned(InValue)) {
 // If any of inputs is poisoned, output is always poisoned too.
 // Remove def of unrelocated pointer from Contribution of this BB and
 // trigger update of all its successors.
 Contribution.erase(&I);
 PoisonedDefs.erase(&I);
 ValidUnrelocatedDefs.insert(&I);
-DEBUG(dbgs() << "Removing urelocated " << I << " from Contribution of "
+LLVM_DEBUG(dbgs() << "Removing urelocated " << I
-<< BB->getName() << "\n");
+<< " from Contribution of " << BB->getName() << "\n");
 ContributionChanged = true;
 } else if (PoisonedPointerDef) {
 // Mark pointer as poisoned, remove its def from Contribution and trigger
 // update of all successors.
 Contribution.erase(&I);
 PoisonedDefs.insert(&I);
-DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "
+LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "
 << BB->getName() << "\n");
 ContributionChanged = true;
 } else {
 bool Cleared = false;
 transferInstruction(I, Cleared, AvailableSet);
 (void)Cleared;
 void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,
 AvailableValueSet &Result,
 const DominatorTree &DT) {
 DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
+assert(DTN && "Unreachable blocks are ignored");
 while (DTN->getIDom()) {
 DTN = DTN->getIDom();
-const auto &Defs = BlockMap[DTN->getBlock()]->Contribution;
+auto BBS = getBasicBlockState(DTN->getBlock());
+assert(BBS && "immediate dominator cannot be dead for a live block");
+const auto &Defs = BBS->Contribution;
 Result.insert(Defs.begin(), Defs.end());
 // If this block is 'Cleared', then nothing LiveIn to this block can be
 // available after this block completes.  Note: This turns out to be
 // really important for reducing memory consuption of the initial available
 // sets and thus peak memory usage by this verifier.
-if (BlockMap[DTN->getBlock()]->Cleared)
+if (BBS->Cleared)
 return;
 }
 for (const Argument &A : BB->getParent()->args())
 if (containsGCPtrType(A.getType()))
 AvailableValueSet Temp = BBS.Contribution;
 set_union(Temp, AvailableIn);
 AvailableOut = std::move(Temp);
 }
-DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
+LLVM_DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
 PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());
 dbgs() << " to ";
 PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());
 dbgs() << "\n";);
 }
 void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared,
 AvailableValueSet &Available) {
 if (isStatepoint(I)) {
 const AvailableValueSet &AvailableSet) {
 if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
 if (containsGCPtrType(PN->getType()))
 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 const BasicBlock *InBB = PN->getIncomingBlock(i);
+const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB);
+if (!InBBS ||
+!Tracker->hasLiveIncomingEdge(PN, InBB))
+continue; // Skip dead block or dead edge.
 const Value *InValue = PN->getIncomingValue(i);
 if (isNotExclusivelyConstantDerived(InValue) &&
-!Tracker->getBasicBlockState(InBB)->AvailableOut.count(InValue))
+!InBBS->AvailableOut.count(InValue))
 reportInvalidUse(*InValue, *PN);
 }
 } else if (isa<CmpInst>(I) &&
 containsGCPtrType(I.getOperand(0)->getType())) {
 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 if (!PrintOnly)
 abort();
 AnyInvalidUses = true;
 }
-static void Verify(const Function &F, const DominatorTree &DT) {
+static void Verify(const Function &F, const DominatorTree &DT,
-DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n");
+const CFGDeadness &CD) {
+LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName()
+<< "\n");
 if (PrintOnly)
 dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
-GCPtrTracker Tracker(F, DT);
+GCPtrTracker Tracker(F, DT, CD);
 // We now have all the information we need to decide if the use of a heap
 // reference is legal or not, given our safepoint semantics.
 InstructionVerifier Verifier;

Mercurial > hg > CbC > CbC_llvm

comparison lib/IR/SafepointIRVerifier.cpp @ 148:63bd29f05246