| //===--- CheckedCastBrJumpThreading.cpp -----------------------------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "sil-simplify-cfg" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/Support/Allocator.h" |
| #include "swift/SIL/SILInstruction.h" |
| #include "swift/SIL/InstructionUtils.h" |
| #include "swift/SILOptimizer/Analysis/DominanceAnalysis.h" |
| #include "swift/SILOptimizer/Utils/CFG.h" |
| #include "swift/SILOptimizer/Utils/Local.h" |
| #include "swift/SILOptimizer/Utils/SILInliner.h" |
| |
| using namespace swift; |
| |
| namespace { |
| /// This is a class implementing a dominator-based jump-threading |
| /// for checked_cast_br [exact]. |
| class CheckedCastBrJumpThreading { |
| // Basic block of the current checked_cast_br instruction. |
| SILBasicBlock *BB; |
| // Condition used by the current checked_cast_br instruction. |
| SILValue Condition; |
| |
| SILBasicBlock *ArgBB; |
| |
| // The current function to be optimized. |
| SILFunction *Fn; |
| |
| // Dominator information to be used. |
| DominanceInfo *DT; |
| |
| // List of predecessors. |
| typedef SmallVector<SILBasicBlock *, 8> PredList; |
| |
| // Predecessors reached only via a path along the |
| // success branch of the dominating checked_cast_br. |
| PredList SuccessPreds; |
| |
| // Predecessors reached only via a path along the |
| // failure branch of the dominating checked_cast_br. |
| PredList FailurePreds; |
| |
| // All other predecessors, where the outcome of the |
| // checked_cast_br along the path is not known. |
| unsigned numUnknownPreds = 0; |
| |
| // Basic blocks to be added to for reprocessing |
| // after jump-threading is done. |
| SmallVectorImpl<SILBasicBlock *> &BlocksForWorklist; |
| |
| // Information for transforming a single checked_cast_br. |
| // This is the output of the optimization's analysis phase. |
| struct Edit { |
| |
| // The block containing the checked_cast_br. |
| SILBasicBlock *CCBBlock; |
| // Copy of CheckedCastBrJumpThreading::SuccessPreds. |
| PredList SuccessPreds; |
| // Copy of CheckedCastBrJumpThreading::FailurePreds. |
| PredList FailurePreds; |
| // The argument of the dominating checked_cast_br's successor block. |
| SILValue SuccessArg; |
| |
| bool InvertSuccess; |
| |
| // True if CheckedCastBrJumpThreading::numUnknownPreds is not 0. |
| bool hasUnknownPreds; |
| |
| Edit(SILBasicBlock *CCBBlock, bool InvertSuccess, |
| const PredList &SuccessPreds, |
| const PredList &FailurePreds, |
| bool hasUnknownPreds, SILValue SuccessArg) : |
| CCBBlock(CCBBlock), SuccessPreds(SuccessPreds), FailurePreds(FailurePreds), |
| SuccessArg(SuccessArg), InvertSuccess(InvertSuccess), |
| hasUnknownPreds(hasUnknownPreds) { } |
| |
| void modifyCFGForUnknownPreds(); |
| void modifyCFGForFailurePreds(Optional<BasicBlockCloner> &Cloner); |
| void modifyCFGForSuccessPreds(Optional<BasicBlockCloner> &Cloner); |
| }; |
| |
| // Contains an entry for each checked_cast_br to be optimized. |
| llvm::SmallVector<Edit *, 8> Edits; |
| |
| llvm::SpecificBumpPtrAllocator<Edit> EditAllocator; |
| |
| // Keeps track of what blocks we change the terminator instruction. |
| llvm::SmallPtrSet<SILBasicBlock *, 16> BlocksToEdit; |
| // Keeps track of what blocks we clone. |
| llvm::SmallPtrSet<SILBasicBlock *, 16> BlocksToClone; |
| |
| bool areEquivalentConditionsAlongPaths(CheckedCastBranchInst *DomCCBI); |
| bool areEquivalentConditionsAlongSomePaths(CheckedCastBranchInst *DomCCBI, |
| SILValue DomCondition); |
| bool handleArgBBIsEntryBlock(SILBasicBlock *ArgBB, |
| CheckedCastBranchInst *DomCCBI); |
| bool checkCloningConstraints(); |
| |
| void classifyPredecessor(SILBasicBlock *Pred, bool SuccessDominates, |
| bool FailureDominates); |
| |
| SILValue isArgValueEquivalentToCondition(SILValue Value, |
| SILBasicBlock *DomBB, |
| SILValue DomValue, |
| DominanceInfo *DT); |
| |
| bool trySimplify(CheckedCastBranchInst *CCBI); |
| |
| public: |
| CheckedCastBrJumpThreading(SILFunction *Fn, DominanceInfo *DT, |
| SmallVectorImpl<SILBasicBlock *> &BlocksForWorklist) |
| : Fn(Fn), DT(DT), BlocksForWorklist(BlocksForWorklist) { } |
| |
| void optimizeFunction(); |
| }; |
| } // end anonymous namespace |
| |
| /// Estimate the cost of inlining a given basic block. |
| static unsigned basicBlockInlineCost(SILBasicBlock *BB, unsigned Cutoff) { |
| unsigned Cost = 0; |
| for (auto &I : *BB) { |
| auto ICost = instructionInlineCost(I); |
| Cost += unsigned(ICost); |
| if (Cost > Cutoff) |
| return Cost; |
| } |
| return Cost; |
| } |
| |
| /// We cannot duplicate blocks with AllocStack instructions (they need to be |
| /// FIFO). Other instructions can be duplicated. |
| static bool canDuplicateBlock(SILBasicBlock *BB) { |
| for (auto &I : *BB) { |
| if (!I.isTriviallyDuplicatable()) |
| return false; |
| } |
| return true; |
| } |
| |
| /// Classify a predecessor of a BB containing checked_cast_br as being |
| /// reachable via success or failure branches of a dominating checked_cast_br |
| /// or as unknown if it can be reached via success or failure branches |
| /// at the same time. |
| void CheckedCastBrJumpThreading::classifyPredecessor( |
| SILBasicBlock *Pred, bool SuccessDominates, bool FailureDominates) { |
| if (SuccessDominates == FailureDominates) { |
| numUnknownPreds++; |
| return; |
| } |
| if (SuccessDominates) { |
| SuccessPreds.push_back(Pred); |
| return; |
| } |
| assert(FailureDominates && "success and failure should be mutual exclusive"); |
| FailurePreds.push_back(Pred); |
| } |
| |
| /// Check if the root value for Value that comes |
| /// along the path from DomBB is equivalent to the |
| /// DomCondition. |
| SILValue CheckedCastBrJumpThreading::isArgValueEquivalentToCondition( |
| SILValue Value, SILBasicBlock *DomBB, SILValue DomValue, |
| DominanceInfo *DT) { |
| SmallPtrSet<ValueBase *, 16> SeenValues; |
| DomValue = stripClassCasts(DomValue); |
| |
| while (true) { |
| Value = stripClassCasts(Value); |
| if (Value == DomValue) |
| return Value; |
| |
| // We know how to propagate through phi arguments only. |
| auto *V = dyn_cast<SILPHIArgument>(Value); |
| if (!V) |
| return SILValue(); |
| |
| // Have we visited this BB already? |
| if (!SeenValues.insert(Value).second) |
| return SILValue(); |
| |
| if (SeenValues.size() > 10) |
| return SILValue(); |
| |
| SmallVector<SILValue, 4> IncomingValues; |
| if (!V->getIncomingValues(IncomingValues) || IncomingValues.empty()) |
| return SILValue(); |
| |
| ValueBase *Def = nullptr; |
| for (auto IncomingValue : IncomingValues) { |
| // Each incoming value should be either from a block |
| // dominated by DomBB or it should be the value used in |
| // condition in DomBB |
| Value = stripClassCasts(IncomingValue); |
| if (Value == DomValue) |
| continue; |
| |
| // Values should be the same |
| if (!Def) |
| Def = Value; |
| |
| if (Def != Value) |
| return SILValue(); |
| |
| if (!DT->dominates(DomBB, Value->getParentBlock())) |
| return SILValue(); |
| // OK, this value is a potential candidate |
| } |
| |
| Value = IncomingValues[0]; |
| } |
| } |
| |
| void CheckedCastBrJumpThreading::Edit::modifyCFGForUnknownPreds() { |
| if (!hasUnknownPreds) |
| return; |
| // Check the FailureBB if it is a BB that contains a class_method |
| // referring to the same value as a condition. This pattern is typical |
| // for method chaining code like obj.method1().method2().etc() |
| auto *CCBI = cast<CheckedCastBranchInst>(CCBBlock->getTerminator()); |
| SILInstruction *Inst = &*CCBI->getFailureBB()->begin(); |
| if (auto *CMI = dyn_cast<ClassMethodInst>(Inst)) { |
| if (CMI->getOperand() == stripClassCasts(CCBI->getOperand())) { |
| // Replace checked_cast_br by branch to FailureBB. |
| SILBuilder(CCBI->getParent()).createBranch(CCBI->getLoc(), |
| CCBI->getFailureBB()); |
| CCBI->eraseFromParent(); |
| } |
| } |
| } |
| |
| /// Create a copy of the BB as a landing BB |
| /// for all FailurePreds. |
| void CheckedCastBrJumpThreading::Edit:: |
| modifyCFGForFailurePreds(Optional<BasicBlockCloner> &Cloner) { |
| if (FailurePreds.empty()) |
| return; |
| |
| assert(!Cloner.hasValue()); |
| Cloner.emplace(CCBBlock); |
| Cloner->clone(); |
| SILBasicBlock *TargetFailureBB = Cloner->getDestBB(); |
| auto *TI = TargetFailureBB->getTerminator(); |
| SILBuilderWithScope Builder(TI); |
| // This BB copy branches to a FailureBB. |
| auto *CCBI = cast<CheckedCastBranchInst>(CCBBlock->getTerminator()); |
| Builder.createBranch(TI->getLoc(), CCBI->getFailureBB()); |
| TI->eraseFromParent(); |
| splitIfCriticalEdge(CCBBlock, CCBI->getFailureBB()); |
| |
| // Redirect all FailurePreds to the copy of BB. |
| for (auto *Pred : FailurePreds) { |
| TermInst *TI = Pred->getTerminator(); |
| // Replace branch to BB by branch to TargetFailureBB. |
| replaceBranchTarget(TI, CCBBlock, TargetFailureBB, |
| /*PreserveArgs=*/true); |
| } |
| } |
| |
| /// Create a copy of the BB or reuse BB as |
| /// a landing basic block for all FailurePreds. |
| void CheckedCastBrJumpThreading::Edit:: |
| modifyCFGForSuccessPreds(Optional<BasicBlockCloner> &Cloner) { |
| auto *CCBI = cast<CheckedCastBranchInst>(CCBBlock->getTerminator()); |
| |
| if (InvertSuccess) { |
| SILBuilder B(CCBBlock); |
| B.createBranch(CCBI->getLoc(), CCBI->getFailureBB()); |
| CCBI->eraseFromParent(); |
| return; |
| } |
| if (hasUnknownPreds) { |
| if (!SuccessPreds.empty()) { |
| // Create a copy of the BB as a landing BB. |
| // for all SuccessPreds. |
| assert(!Cloner.hasValue()); |
| Cloner.emplace(CCBBlock); |
| Cloner->clone(); |
| SILBasicBlock *TargetSuccessBB = Cloner->getDestBB(); |
| auto *TI = TargetSuccessBB->getTerminator(); |
| SILBuilderWithScope Builder(TI); |
| // This BB copy branches to SuccessBB. |
| // Take argument value from the dominating BB. |
| Builder.createBranch(TI->getLoc(), CCBI->getSuccessBB(), {SuccessArg}); |
| TI->eraseFromParent(); |
| splitIfCriticalEdge(CCBBlock, CCBI->getSuccessBB()); |
| |
| // Redirect all SuccessPreds to the copy of BB. |
| for (auto *Pred : SuccessPreds) { |
| TermInst *TI = Pred->getTerminator(); |
| // Replace branch to BB by branch to TargetSuccessBB. |
| replaceBranchTarget(TI, CCBBlock, TargetSuccessBB, /*PreserveArgs=*/true); |
| } |
| } |
| return; |
| } |
| // There are no predecessors where it is not clear |
| // if they are dominated by a success or failure branch |
| // of DomBB. Therefore, there is no need to clone |
| // the BB for SuccessPreds. Current BB can be re-used |
| // instead as their target. |
| |
| // Add an unconditional jump at the end of the block. |
| // Take argument value from the dominating BB |
| SILBuilder(CCBBlock).createBranch(CCBI->getLoc(), CCBI->getSuccessBB(), |
| {SuccessArg}); |
| CCBI->eraseFromParent(); |
| } |
| |
| /// Handle a special case, where ArgBB is the entry block. |
| bool CheckedCastBrJumpThreading::handleArgBBIsEntryBlock(SILBasicBlock *ArgBB, |
| CheckedCastBranchInst *DomCCBI) { |
| if (!ArgBB->pred_empty()) |
| return false; |
| |
| // It must be the entry block |
| // |
| // TODO: Is this a correct assumption? Do we know that at this point that |
| // ArgBB can not be unreachable? |
| // |
| // See if it is reached over Success or Failure path. |
| bool SuccessDominates = DomCCBI->getSuccessBB() == BB; |
| bool FailureDominates = DomCCBI->getFailureBB() == BB; |
| |
| if (BlocksToEdit.count(ArgBB) != 0) |
| return false; |
| |
| classifyPredecessor(ArgBB, SuccessDominates, FailureDominates); |
| return true; |
| } |
| |
| // Returns false if cloning required by jump threading cannot |
| // be performed, because some of the constraints are violated. |
| bool CheckedCastBrJumpThreading::checkCloningConstraints() { |
| // Check some cloning related constraints. |
| |
| // If this argument from a different BB, then jump-threading |
| // may require too much code duplication. |
| if (ArgBB && ArgBB != BB) |
| return false; |
| |
| // Bail out if current BB cannot be duplicated. |
| if (!canDuplicateBlock(BB)) |
| return false; |
| |
| // Check if code-bloat would be too big when this BB |
| // is jump-threaded. |
| // TODO: Make InlineCostCutoff parameter configurable? |
| // Dec 1, 2014: |
| // We looked at the inline costs of BBs from our benchmark suite |
| // and found that currently the highest inline cost for the |
| // whole benchmark suite is 12. In 95% of all cases it is <=3. |
| const unsigned InlineCostCutoff = 20; |
| if (basicBlockInlineCost(BB, InlineCostCutoff) >= InlineCostCutoff) |
| return false; |
| |
| return true; |
| } |
| |
| /// If conditions are not equivalent along all paths, try harder |
| /// to check if they are actually equivalent along a subset of paths. |
| /// To do it, try to back-propagate the Condition |
| /// backwards and see if it is actually equivalent to DomCondition. |
| /// along some of the paths. |
| bool CheckedCastBrJumpThreading:: |
| areEquivalentConditionsAlongSomePaths(CheckedCastBranchInst *DomCCBI, |
| SILValue DomCondition) { |
| auto *Arg = dyn_cast<SILPHIArgument>(Condition); |
| if (!Arg) |
| return false; |
| |
| ArgBB = Arg->getParent(); |
| SILBasicBlock *DomBB = DomCCBI->getParent(); |
| if (!DT->dominates(DomBB, ArgBB)) |
| return false; |
| |
| // Incoming values for the BBArg. |
| SmallVector<SILValue, 4> IncomingValues; |
| |
| if (ArgBB->getIterator() != ArgBB->getParent()->begin() && |
| (!Arg->getIncomingValues(IncomingValues) || IncomingValues.empty())) |
| return false; |
| |
| // Check for each predecessor, if the incoming value coming from it |
| // is equivalent to the DomCondition. If this is the case, it is |
| // possible to try jump-threading along this path. |
| if (!handleArgBBIsEntryBlock(ArgBB, DomCCBI)) { |
| // ArgBB is not the entry block and has predecessors. |
| unsigned idx = 0; |
| for (auto *PredBB : ArgBB->getPredecessorBlocks()) { |
| |
| // We must avoid that we are going to change a block twice. |
| if (BlocksToEdit.count(PredBB) != 0) |
| return false; |
| |
| auto IncomingValue = IncomingValues[idx]; |
| SILValue ReachingValue = isArgValueEquivalentToCondition( |
| IncomingValue, DomBB, DomCondition, DT); |
| |
| if (ReachingValue == SILValue()) { |
| numUnknownPreds++; |
| idx++; |
| continue; |
| } |
| |
| // Condition is the same if BB is reached over a pass through Pred. |
| DEBUG(llvm::dbgs() << "Condition is the same if reached over "); |
| DEBUG(PredBB->print(llvm::dbgs())); |
| |
| // See if it is reached over Success or Failure path. |
| SILBasicBlock *DomSuccessBB = DomCCBI->getSuccessBB(); |
| bool SuccessDominates = DT->dominates(DomSuccessBB, PredBB) || |
| DT->dominates(DomSuccessBB, BB) || |
| DomSuccessBB == BB; |
| SILBasicBlock *DomFailureBB = DomCCBI->getFailureBB(); |
| bool FailureDominates = DT->dominates(DomFailureBB, PredBB) || |
| DT->dominates(DomFailureBB, BB) || |
| DomFailureBB == BB; |
| |
| classifyPredecessor( |
| PredBB, SuccessDominates, FailureDominates); |
| idx++; |
| } |
| } else { |
| // ArgBB is the entry block. Check that conditions are the equivalent in this |
| // case as well. |
| if (!isArgValueEquivalentToCondition(Condition, DomBB, DomCondition, DT)) |
| return false; |
| } |
| |
| |
| // At this point we know for each predecessor of ArgBB if its reached |
| // over the success, failure or unknown path from DomBB. |
| |
| // Now we can generate a new BB for preds reaching BB over the success |
| // path and a new BB for preds reaching BB over the failure path. |
| // Then we redirect those preds to those new basic blocks. |
| return true; |
| } |
| |
| /// Check if conditions of CCBI and DomCCBI are equivalent along |
| /// all or at least some paths. |
| bool CheckedCastBrJumpThreading:: |
| areEquivalentConditionsAlongPaths(CheckedCastBranchInst *DomCCBI) { |
| // Are conditions equivalent along all paths? |
| SILValue DomCondition = stripClassCasts(DomCCBI->getOperand()); |
| if (DomCondition == Condition) { |
| // Conditions are exactly the same, without any restrictions. |
| // They are equivalent along all paths. |
| |
| // Figure out for each predecessor which branch of |
| // the dominating checked_cast_br is used to reach it. |
| for (auto *PredBB : BB->getPredecessorBlocks()) { |
| // All predecessors should either unconditionally branch |
| // to the current BB or be another checked_cast_br instruction. |
| if (!isa<CheckedCastBranchInst>(PredBB->getTerminator()) && |
| !isa<BranchInst>(PredBB->getTerminator())) |
| return false; |
| |
| // We must avoid that we are going to change a block twice. |
| if (BlocksToEdit.count(PredBB) != 0) |
| return false; |
| |
| // Don't allow critical edges from PredBB to BB. This ensures that |
| // splitAllCriticalEdges() will not invalidate our predecessor lists. |
| if (!BB->getSinglePredecessorBlock() && |
| !PredBB->getSingleSuccessorBlock()) |
| return false; |
| |
| SILBasicBlock *DomSuccessBB = DomCCBI->getSuccessBB(); |
| bool SuccessDominates = |
| DT->dominates(DomSuccessBB, PredBB) || DomSuccessBB == BB; |
| SILBasicBlock *DomFailureBB = DomCCBI->getFailureBB(); |
| bool FailureDominates = |
| DT->dominates(DomFailureBB, PredBB) || DomFailureBB == BB; |
| |
| classifyPredecessor(PredBB, SuccessDominates, FailureDominates); |
| } |
| return true; |
| } |
| |
| // Check if conditions are equivalent along a subset of reaching paths. |
| return areEquivalentConditionsAlongSomePaths(DomCCBI, DomCondition); |
| } |
| |
| /// Try performing a dominator-based jump-threading for |
| /// checked_cast_br instructions. |
| bool CheckedCastBrJumpThreading::trySimplify(CheckedCastBranchInst *CCBI) { |
| // Init information about the checked_cast_br we try to |
| // jump-thread. |
| BB = CCBI->getParent(); |
| if (BlocksToEdit.count(BB) != 0) |
| return false; |
| |
| Condition = stripClassCasts(CCBI->getOperand()); |
| |
| // Find a dominating checked_cast_br, which performs the same check. |
| for (auto *Node = DT->getNode(BB)->getIDom(); Node; Node = Node->getIDom()) { |
| // Get current dominating block. |
| SILBasicBlock *DomBB = Node->getBlock(); |
| auto *DomTerm = DomBB->getTerminator(); |
| |
| if (!DomTerm->getNumOperands()) |
| continue; |
| |
| // Check that it is a dominating checked_cast_br. |
| auto *DomCCBI = dyn_cast<CheckedCastBranchInst>(DomTerm); |
| if (!DomCCBI) |
| continue; |
| |
| // We need to verify that the result type is the same in the |
| // dominating checked_cast_br, but only for non-exact casts. |
| // For exact casts, we are interested only in the |
| // fact that the source operand is the same for |
| // both instructions. |
| if (!CCBI->isExact() && !DomCCBI->isExact()) { |
| if (DomCCBI->getCastType() != CCBI->getCastType()) |
| continue; |
| } |
| |
| // Conservatively check that both checked_cast_br instructions |
| // are either exact or non-exact. This is very conservative, |
| // but safe. |
| // |
| // TODO: |
| // If the dominating checked_cast_br is non-exact, then |
| // it is in general not safe to assume that current exact cast |
| // would have the same outcome. But if the dominating non-exact |
| // checked_cast_br fails, then the current exact cast would |
| // always fail as well. |
| // |
| // If the dominating checked_cast_br is exact then then |
| // it is in general not safe to assume that the current non-exact |
| // cast would have the same outcome. But if the dominating exact |
| // checked_cast_br succeeds, then the current non-exact cast |
| // would always succeed as well. |
| // |
| // TODO: In some specific cases, it is possible to prove that |
| // success or failure of the dominating cast is equivalent to |
| // the success or failure of the current cast, even if one |
| // of them is exact and the other not. This is the case |
| // e.g. if the class has no subclasses. |
| if (DomCCBI->isExact() != CCBI->isExact()) |
| continue; |
| |
| // We need the block argument of the DomSuccessBB. If we are going to |
| // clone it for a previous checked_cast_br the argument will not dominate |
| // the blocks which it's used to dominate anymore. |
| if (BlocksToClone.count(DomCCBI->getSuccessBB()) != 0) |
| continue; |
| |
| // Init state variables for paths analysis |
| SuccessPreds.clear(); |
| FailurePreds.clear(); |
| numUnknownPreds = 0; |
| ArgBB = nullptr; |
| |
| // Are conditions of CCBI and DomCCBI equivalent along (some) paths? |
| // If this is the case, classify all incoming paths into SuccessPreds, |
| // FailurePreds or UnknownPreds depending on how they reach CCBI. |
| if (!areEquivalentConditionsAlongPaths(DomCCBI)) |
| continue; |
| |
| // Check if any jump-threading is required and possible. |
| if (SuccessPreds.empty() && FailurePreds.empty()) |
| return false; |
| |
| // If this check is reachable via success, failure and unknown |
| // at the same time, then we don't know the outcome of the |
| // dominating check. No jump-threading is possible in this case. |
| if (!SuccessPreds.empty() && !FailurePreds.empty() && numUnknownPreds > 0) { |
| return false; |
| } |
| |
| unsigned TotalPreds = |
| SuccessPreds.size() + FailurePreds.size() + numUnknownPreds; |
| |
| // We only need to clone the BB if not all of its |
| // predecessors are in the same group. |
| if (TotalPreds != SuccessPreds.size() && |
| TotalPreds != numUnknownPreds) { |
| // Check some cloning related constraints. |
| if (!checkCloningConstraints()) |
| return false; |
| } |
| |
| bool InvertSuccess = false; |
| if (DomCCBI->isExact() && CCBI->isExact() && |
| DomCCBI->getCastType() != CCBI->getCastType()) { |
| if (TotalPreds == SuccessPreds.size()) { |
| // The dominating exact cast was successful, but it casted to a |
| // different type. Therefore, the current cast fails for sure. |
| // Since we are going to change the BB, |
| // add its successors and predecessors |
| // for re-processing. |
| InvertSuccess = true; |
| } else { |
| // Otherwise, we don't know if the current cast will succeed or |
| // fail. |
| return false; |
| } |
| } |
| // If we have predecessors, where it is not known if they are reached over |
| // success or failure path, we cannot eliminate a checked_cast_br. |
| // We have to generate new dedicated BBs as landing BBs for all |
| // FailurePreds and all SuccessPreds. |
| |
| // Since we are going to change the BB, add its successors and predecessors |
| // for re-processing. |
| for (auto *B : BB->getPredecessorBlocks()) { |
| BlocksForWorklist.push_back(B); |
| } |
| for (auto *B : BB->getSuccessorBlocks()) { |
| BlocksForWorklist.push_back(B); |
| } |
| // Remember the blocks we are going to change. So that we ignore them |
| // for upcoming checked_cast_br instructions. |
| BlocksToEdit.insert(BB); |
| BlocksToClone.insert(BB); |
| for (auto *B : SuccessPreds) |
| BlocksToEdit.insert(B); |
| for (auto *B : FailurePreds) |
| BlocksToEdit.insert(B); |
| |
| // Record what we want to change. |
| Edit *edit = new (EditAllocator.Allocate()) |
| Edit(BB, InvertSuccess, SuccessPreds, FailurePreds, |
| numUnknownPreds != 0, DomCCBI->getSuccessBB()->getArgument(0)); |
| Edits.push_back(edit); |
| |
| return true; |
| } |
| |
| // Jump-threading was not possible. |
| return false; |
| } |
| |
| /// Optimize the checked_cast_br instructions in a function. |
| void CheckedCastBrJumpThreading::optimizeFunction() { |
| |
| // We separate the work in two phases: analyze and transform. This avoids |
| // re-calculating the dominator tree for each optimized checked_cast_br. |
| |
| // First phase: analysis. |
| for (auto &BB : *Fn) { |
| // Ignore unreachable blocks. |
| if (!DT->getNode(&BB)) |
| continue; |
| |
| if (auto *CCBI = dyn_cast<CheckedCastBranchInst>(BB.getTerminator())) |
| trySimplify(CCBI); |
| } |
| |
| assert(BlocksForWorklist.empty() == Edits.empty()); |
| |
| if (Edits.empty()) |
| return; |
| |
| // Second phase: transformation. |
| // Remove critical edges for the SSA-updater. We do this once and keep the |
| // CFG critical-edge free during our transformations. |
| splitAllCriticalEdges(*Fn, true, nullptr, nullptr); |
| |
| for (Edit *edit : Edits) { |
| Optional<BasicBlockCloner> Cloner; |
| |
| // Create a copy of the BB as a landing BB |
| // for all FailurePreds. |
| edit->modifyCFGForFailurePreds(Cloner); |
| // Create a copy of the BB or reuse BB as |
| // a landing basic block for all SuccessPreds. |
| edit->modifyCFGForSuccessPreds(Cloner); |
| // Handle unknown preds. |
| edit->modifyCFGForUnknownPreds(); |
| |
| if (Cloner.hasValue()) { |
| updateSSAAfterCloning(*Cloner.getPointer(), Cloner->getDestBB(), |
| edit->CCBBlock, false); |
| |
| if (!Cloner->getDestBB()->pred_empty()) |
| BlocksForWorklist.push_back(Cloner->getDestBB()); |
| } |
| if (!edit->CCBBlock->pred_empty()) |
| BlocksForWorklist.push_back(edit->CCBBlock); |
| } |
| } |
| |
| namespace swift { |
| |
| bool tryCheckedCastBrJumpThreading(SILFunction *Fn, DominanceInfo *DT, |
| SmallVectorImpl<SILBasicBlock *> &BlocksForWorklist) { |
| CheckedCastBrJumpThreading CCBJumpThreading(Fn, DT, BlocksForWorklist); |
| CCBJumpThreading.optimizeFunction(); |
| return !BlocksForWorklist.empty(); |
| } |
| |
| } // end namespace swift |