diff options
Diffstat (limited to 'llvm/lib/Transforms/Utils')
| -rw-r--r-- | llvm/lib/Transforms/Utils/PredicateInfo.cpp | 3 | ||||
| -rw-r--r-- | llvm/lib/Transforms/Utils/SimplifyCFG.cpp | 114 |
2 files changed, 80 insertions, 37 deletions
diff --git a/llvm/lib/Transforms/Utils/PredicateInfo.cpp b/llvm/lib/Transforms/Utils/PredicateInfo.cpp index 371d9e6..27fed73 100644 --- a/llvm/lib/Transforms/Utils/PredicateInfo.cpp +++ b/llvm/lib/Transforms/Utils/PredicateInfo.cpp @@ -809,7 +809,6 @@ public: void emitInstructionAnnot(const Instruction *I, formatted_raw_ostream &OS) override { if (const auto *PI = PredInfo->getPredicateInfoFor(I)) { - OS << "; Has predicate info\n"; if (const auto *PB = dyn_cast<PredicateBranch>(PI)) { OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge << " Comparison:" << *PB->Condition << " Edge: ["; @@ -819,7 +818,7 @@ public: OS << "]"; } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) { OS << "; switch predicate info { CaseValue: " << *PS->CaseValue - << " Switch:" << *PS->Switch << " Edge: ["; + << " Edge: ["; PS->From->printAsOperand(OS); OS << ","; PS->To->printAsOperand(OS); diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp index d831c27..b03fb62 100644 --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -1866,10 +1866,19 @@ bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI, // If either of the blocks has it's address taken, then we can't do this fold, // because the code we'd hoist would no longer run when we jump into the block // by it's address. - for (auto *Succ : successors(BB)) - if (Succ->hasAddressTaken() || !Succ->getSinglePredecessor()) + for (auto *Succ : successors(BB)) { + if (Succ->hasAddressTaken()) return false; - + if (Succ->getSinglePredecessor()) + continue; + // If Succ has >1 predecessors, continue to check if the Succ contains only + // one `unreachable` inst. Since executing `unreachable` inst is an UB, we + // can relax the condition based on the assumptiom that the program would + // never enter Succ and trigger such an UB. + if (isa<UnreachableInst>(*Succ->begin())) + continue; + return false; + } // The second of pair is a SkipFlags bitmask. using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>; SmallVector<SuccIterPair, 8> SuccIterPairs; @@ -5228,32 +5237,52 @@ bool SimplifyCFGOpt::simplifyBranchOnICmpChain(BranchInst *BI, CompVal, DL.getIntPtrType(CompVal->getType()), "magicptr"); } - // Create the new switch instruction now. - SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size()); - if (HasProfile) { - // We know the weight of the default case. We don't know the weight of the - // other cases, but rather than completely lose profiling info, we split - // the remaining probability equally over them. - SmallVector<uint32_t> NewWeights(Values.size() + 1); - NewWeights[0] = BranchWeights[1]; // this is the default, and we swapped if - // TrueWhenEqual. - for (auto &V : drop_begin(NewWeights)) - V = BranchWeights[0] / Values.size(); - setBranchWeights(*New, NewWeights, /*IsExpected=*/false); - } - - // Add all of the 'cases' to the switch instruction. - for (ConstantInt *Val : Values) - New->addCase(Val, EdgeBB); + // Check if we can represent the values as a contiguous range. If so, we use a + // range check + conditional branch instead of a switch. + if (Values.front()->getValue() - Values.back()->getValue() == + Values.size() - 1) { + ConstantRange RangeToCheck = ConstantRange::getNonEmpty( + Values.back()->getValue(), Values.front()->getValue() + 1); + APInt Offset, RHS; + ICmpInst::Predicate Pred; + RangeToCheck.getEquivalentICmp(Pred, RHS, Offset); + Value *X = CompVal; + if (!Offset.isZero()) + X = Builder.CreateAdd(X, ConstantInt::get(CompVal->getType(), Offset)); + Value *Cond = + Builder.CreateICmp(Pred, X, ConstantInt::get(CompVal->getType(), RHS)); + BranchInst *NewBI = Builder.CreateCondBr(Cond, EdgeBB, DefaultBB); + if (HasProfile) + setBranchWeights(*NewBI, BranchWeights, /*IsExpected=*/false); + // We don't need to update PHI nodes since we don't add any new edges. + } else { + // Create the new switch instruction now. + SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size()); + if (HasProfile) { + // We know the weight of the default case. We don't know the weight of the + // other cases, but rather than completely lose profiling info, we split + // the remaining probability equally over them. + SmallVector<uint32_t> NewWeights(Values.size() + 1); + NewWeights[0] = BranchWeights[1]; // this is the default, and we swapped + // if TrueWhenEqual. + for (auto &V : drop_begin(NewWeights)) + V = BranchWeights[0] / Values.size(); + setBranchWeights(*New, NewWeights, /*IsExpected=*/false); + } - // We added edges from PI to the EdgeBB. As such, if there were any - // PHI nodes in EdgeBB, they need entries to be added corresponding to - // the number of edges added. - for (BasicBlock::iterator BBI = EdgeBB->begin(); isa<PHINode>(BBI); ++BBI) { - PHINode *PN = cast<PHINode>(BBI); - Value *InVal = PN->getIncomingValueForBlock(BB); - for (unsigned i = 0, e = Values.size() - 1; i != e; ++i) - PN->addIncoming(InVal, BB); + // Add all of the 'cases' to the switch instruction. + for (ConstantInt *Val : Values) + New->addCase(Val, EdgeBB); + + // We added edges from PI to the EdgeBB. As such, if there were any + // PHI nodes in EdgeBB, they need entries to be added corresponding to + // the number of edges added. + for (BasicBlock::iterator BBI = EdgeBB->begin(); isa<PHINode>(BBI); ++BBI) { + PHINode *PN = cast<PHINode>(BBI); + Value *InVal = PN->getIncomingValueForBlock(BB); + for (unsigned i = 0, e = Values.size() - 1; i != e; ++i) + PN->addIncoming(InVal, BB); + } } // Erase the old branch instruction. @@ -7551,6 +7580,7 @@ static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, /// log2(C)-indexed value table (instead of traditionally emitting a load of the /// address of the jump target, and indirectly jump to it). static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, + DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI) { Value *Condition = SI->getCondition(); @@ -7573,12 +7603,6 @@ static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, if (SI->getNumCases() < 4) return false; - // We perform this optimization only for switches with - // unreachable default case. - // This assumtion will save us from checking if `Condition` is a power of two. - if (!SI->defaultDestUnreachable()) - return false; - // Check that switch cases are powers of two. SmallVector<uint64_t, 4> Values; for (const auto &Case : SI->cases()) { @@ -7598,6 +7622,26 @@ static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, Builder.SetInsertPoint(SI); + if (!SI->defaultDestUnreachable()) { + // Let non-power-of-two inputs jump to the default case, when the latter is + // reachable. + auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition); + auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1)); + + auto *OrigBB = SI->getParent(); + auto *DefaultCaseBB = SI->getDefaultDest(); + BasicBlock *SplitBB = SplitBlock(OrigBB, SI, DTU); + auto It = OrigBB->getTerminator()->getIterator(); + auto *BI = BranchInst::Create(SplitBB, DefaultCaseBB, IsPow2, It); + // BI is handling the default case for SI, and so should share its DebugLoc. + BI->setDebugLoc(SI->getDebugLoc()); + It->eraseFromParent(); + + addPredecessorToBlock(DefaultCaseBB, OrigBB, SplitBB); + if (DTU) + DTU->applyUpdates({{DominatorTree::Insert, OrigBB, DefaultCaseBB}}); + } + // Replace each case with its trailing zeros number. for (auto &Case : SI->cases()) { auto *OrigValue = Case.getCaseValue(); @@ -7953,7 +7997,7 @@ bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { Options.ConvertSwitchToLookupTable)) return requestResimplify(); - if (simplifySwitchOfPowersOfTwo(SI, Builder, DL, TTI)) + if (simplifySwitchOfPowersOfTwo(SI, Builder, DTU, DL, TTI)) return requestResimplify(); if (reduceSwitchRange(SI, Builder, DL, TTI)) |