Lines Matching +full:push +full:- +full:ci +full:- +full:container
1 //===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
63 #define DEBUG_TYPE "early-cse"
73 DEBUG_COUNTER(CSECounter, "early-cse",
77 "earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden,
82 "earlycse-debug-hash", cl::init(false), cl::Hidden,
84 "function is well-behaved w.r.t. its isEqual predicate"));
86 //===----------------------------------------------------------------------===//
88 //===----------------------------------------------------------------------===//
106 // This can only handle non-void readnone functions.
109 if (CallInst *CI = dyn_cast<CallInst>(Inst)) {
110 if (Function *F = CI->getCalledFunction()) {
111 switch ((Intrinsic::ID)F->getIntrinsicID()) {
123 auto *CFP = cast<ConstrainedFPIntrinsic>(CI);
124 if (CFP->getExceptionBehavior() &&
125 CFP->getExceptionBehavior() == fp::ebStrict)
129 if (CFP->getRoundingMode() &&
130 CFP->getRoundingMode() == RoundingMode::Dynamic)
136 return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy() &&
144 !CI->getFunction()->isPresplitCoroutine();
211 // Non-strict inequalities.
222 static unsigned hashCallInst(CallInst *CI) {
225 if (CI->isConvergent()) {
227 CI->getOpcode(), CI->getParent(),
228 hash_combine_range(CI->value_op_begin(), CI->value_op_end()));
231 CI->getOpcode(),
232 hash_combine_range(CI->value_op_begin(), CI->value_op_end()));
239 Value *LHS = BinOp->getOperand(0);
240 Value *RHS = BinOp->getOperand(1);
241 if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
244 return hash_combine(BinOp->getOpcode(), LHS, RHS);
247 if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
252 Value *LHS = CI->getOperand(0);
253 Value *RHS = CI->getOperand(1);
254 CmpInst::Predicate Pred = CI->getPredicate();
255 CmpInst::Predicate SwappedPred = CI->getSwappedPredicate();
260 return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
268 // Min/max may also have non-canonical compare predicate (eg, the compare for
269 // smin may use 'sgt' rather than 'slt'), and non-canonical operands in the
276 return hash_combine(Inst->getOpcode(), SPF, A, B);
285 return hash_combine(Inst->getOpcode(), Cond, A, B);
287 // Similar to cmp normalization (above) - canonicalize the predicate value:
288 // select (icmp Pred, X, Y), A, B --> select (icmp InvPred, X, Y), B, A
293 return hash_combine(Inst->getOpcode(),
297 if (CastInst *CI = dyn_cast<CastInst>(Inst))
298 return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
301 return hash_combine(FI->getOpcode(), FI->getOperand(0));
304 return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
305 hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
308 return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
309 IVI->getOperand(1),
310 hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
319 if (II && II->isCommutative() && II->arg_size() >= 2) {
320 Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1);
324 II->getOpcode(), LHS, RHS,
325 hash_combine_range(II->value_op_begin() + 2, II->value_op_end()));
332 return hash_combine(GCR->getOpcode(), GCR->getOperand(0),
333 GCR->getBasePtr(), GCR->getDerivedPtr());
337 if (CallInst *CI = dyn_cast<CallInst>(Inst))
338 return hashCallInst(CI);
342 Inst->getOpcode(),
343 hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
348 // If -earlycse-debug-hash was specified, return a constant -- this
364 if (LHSI->getOpcode() != RHSI->getOpcode())
366 if (LHSI->isIdenticalToWhenDefined(RHSI, /*IntersectAttrs=*/true)) {
370 if (CallInst *CI = dyn_cast<CallInst>(LHSI);
371 CI && CI->isConvergent() && LHSI->getParent() != RHSI->getParent())
379 if (!LHSBinOp->isCommutative())
387 return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
388 LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
395 return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
396 LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
397 LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
402 if (LII && RII && LII->getIntrinsicID() == RII->getIntrinsicID() &&
403 LII->isCommutative() && LII->arg_size() >= 2) {
404 return LII->getArgOperand(0) == RII->getArgOperand(1) &&
405 LII->getArgOperand(1) == RII->getArgOperand(0) &&
406 std::equal(LII->arg_begin() + 2, LII->arg_end(),
407 RII->arg_begin() + 2, RII->arg_end());
413 return GCR1->getOperand(0) == GCR2->getOperand(0) &&
414 GCR1->getBasePtr() == GCR2->getBasePtr() &&
415 GCR1->getDerivedPtr() == GCR2->getDerivedPtr();
417 // Min/max can occur with commuted operands, non-canonical predicates,
418 // and/or non-canonical operands.
419 // Selects can be non-trivially equivalent via inverted conditions and swaps.
431 // select Cond, A, B <--> select not(Cond), B, A
438 // select (icmp Pred, X, Y), A, B <--> select (icmp InvPred, X, Y), B, A
440 // This also handles patterns with a double-negation in the sense of not +
443 // select (cmp Pred, X, Y), A, B <--> select (not (cmp InvPred, X, Y)), B, A
445 // This intentionally does NOT handle patterns with a double-negation in
449 // select (cmp slt, X, Y), X, Y <--> select (not (not (cmp slt, X, Y))), X, Y
452 // this code, as we simplify the double-negation before hashing the second
476 //===----------------------------------------------------------------------===//
478 //===----------------------------------------------------------------------===//
498 if (Inst->getType()->isVoidTy())
501 CallInst *CI = dyn_cast<CallInst>(Inst);
502 if (!CI || !CI->onlyReadsMemory() ||
510 CI->getFunction()->isPresplitCoroutine())
552 if (LHSI->isConvergent() && LHSI->getParent() != RHSI->getParent())
555 return LHSI->isIdenticalToWhenDefined(RHSI, /*IntersectAttrs=*/true);
558 //===----------------------------------------------------------------------===//
560 //===----------------------------------------------------------------------===//
609 return hash_combine(GEP->getOpcode(), GEP->getPointerOperand(),
612 GEP->getOpcode(),
613 hash_combine_range(GEP->value_op_begin(), GEP->value_op_end()));
621 if (LGEP->getPointerOperand() != RGEP->getPointerOperand())
625 return LGEP->isIdenticalToWhenDefined(RGEP);
628 //===----------------------------------------------------------------------===//
630 //===----------------------------------------------------------------------===//
634 /// A simple and fast domtree-based CSE pass.
636 /// This pass does a simple depth-first walk over the dominator tree,
683 int MatchingId = -1;
714 /// A scoped hash table of the current values of read-only call
817 IntrID = II->getIntrinsicID();
823 Info.PtrVal = Inst->getOperand(0);
830 Info.PtrVal = Inst->getOperand(1);
832 // prevent matching non-masked loads/stores with masked ones
834 // does not support matching intrinsics with non-intrinsics,
865 return Inst->isAtomic();
873 return LI->isUnordered();
875 return SI->isUnordered();
878 return !Inst->isAtomic();
886 return LI->isVolatile();
888 return SI->isVolatile();
896 return LI->hasMetadata(LLVMContext::MD_invariant_load);
902 // For regular (non-intrinsic) loads/stores, this is set to -1. For
905 // non-negative values only.
909 return -1;
919 // TODO: handle target-specific intrinsics.
920 return Inst->getAccessType();
926 return Inst->mayReadFromMemory();
932 return Inst->mayWriteToMemory();
941 // This function is to prevent accidentally passing a non-target
953 return isHandledNonTargetIntrinsic(II->getIntrinsicID());
973 switch (II->getIntrinsicID()) {
978 V = II->getOperand(0);
984 V = isa<LoadInst>(Inst) ? Inst : cast<StoreInst>(Inst)->getValueOperand();
987 return V->getType() == ExpectedType ? V : nullptr;
1009 if (Vec0->getType() != Vec1->getType())
1011 for (int i = 0, e = Vec0->getNumOperands(); i != e; ++i) {
1012 Constant *Elem0 = Vec0->getOperand(i);
1013 Constant *Elem1 = Vec1->getOperand(i);
1015 if (Int0 && Int0->isZero())
1018 if (Int1 && !Int1->isZero())
1029 if (II->getIntrinsicID() == Intrinsic::masked_load)
1030 return II->getOperand(0);
1031 if (II->getIntrinsicID() == Intrinsic::masked_store)
1032 return II->getOperand(1);
1036 if (II->getIntrinsicID() == Intrinsic::masked_load)
1037 return II->getOperand(2);
1038 if (II->getIntrinsicID() == Intrinsic::masked_store)
1039 return II->getOperand(3);
1043 if (II->getIntrinsicID() == Intrinsic::masked_load)
1044 return II->getOperand(3);
1051 Intrinsic::ID IDE = Earlier->getIntrinsicID();
1052 Intrinsic::ID IDL = Later->getIntrinsicID();
1058 // - masks and pass-throughs are the same, or
1059 // - replacee's pass-through is "undef" and replacer's mask is a
1060 // super-set of the replacee's mask.
1070 // - load's mask is a subset of store's mask, and
1071 // - load's pass-through is "undef".
1079 // - store's mask is a subset of the load's mask.
1085 // - the to-be-removed store's mask is a subset of the other store's
1096 MSSA->verifyMemorySSA();
1101 // removeMemoryAccess. The non-optimized MemoryUse case is lazily updated
1103 MSSAUpdater->removeMemoryAccess(&Inst, true);
1143 auto *EarlierMA = MSSA->getMemoryAccess(EarlierInst);
1146 auto *LaterMA = MSSA->getMemoryAccess(LaterInst);
1156 LaterDef = MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
1159 LaterDef = LaterMA->getDefiningAccess();
1161 return MSSA->dominates(LaterDef, EarlierMA);
1168 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1188 assert(BI->isConditional() && "Should be a conditional branch!");
1189 assert(BI->getCondition() == CondInst && "Wrong condition?");
1190 assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
1191 auto *TorF = (BI->getSuccessor(0) == BB)
1192 ? ConstantInt::getTrue(BB->getContext())
1193 : ConstantInt::getFalse(BB->getContext());
1208 (BI->getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;
1219 << Curr->getName() << "' as " << *TorF << " in "
1220 << BB->getName() << "\n");
1266 ? getOrCreateResult(Matching, Other->getType())
1271 // Deal with non-target memory intrinsics.
1288 Result = getOrCreateResult(Matching, Other->getType());
1296 // TODO: Currently some fast-math flags are not treated as
1297 // poison-generating even though they should. Until this is fixed,
1301 (I->hasPoisonGeneratingFlags() && !programUndefinedIfPoison(I)))
1302 I->andIRFlags(&From);
1315 cast<CallBase>(To)->tryIntersectAttributes(cast<CallBase>(&From));
1339 // other atomic stores since we were going to execute the non-atomic
1344 // Deal with non-target memory intrinsics.
1352 // For now disallow matching intrinsics with non-intrinsics,
1359 BasicBlock *BB = Node->getBlock();
1364 // have invalidated the live-out memory values of our parent value. For now,
1367 if (!BB->getSinglePredecessor())
1376 if (BasicBlock *Pred = BB->getSinglePredecessor()) {
1377 auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
1378 if (BI && BI->isConditional()) {
1379 auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
1385 /// LastStore - Keep track of the last non-volatile store that we saw... for
1416 auto *CondI = dyn_cast<Instruction>(Assume->getArgOperand(0));
1420 AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
1479 cast<ConstantInt>(KnownCond)->isOne()) {
1493 AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
1533 if ([[maybe_unused]] auto *CI = dyn_cast<ConstrainedFPIntrinsic>(&Inst)) {
1534 assert(CI->getExceptionBehavior() != fp::ebStrict &&
1536 assert((!CI->getRoundingMode() ||
1537 CI->getRoundingMode() != RoundingMode::Dynamic) &&
1564 // If this is a non-volatile load, process it.
1632 // If this is a read-only call, process it.
1665 APInt Offset = APInt(SQ.DL.getIndexTypeSizeInBits(GEP->getType()), 0);
1666 GEPValue GEPVal(GEP, GEP->accumulateConstantOffset(SQ.DL, Offset)
1693 if (FI->getOrdering() == AtomicOrdering::Release) {
1698 // write back DSE - If we write back the same value we just loaded from
1750 LastStore->eraseFromParent();
1756 // fallthrough - we can exploit information about this store
1762 // to non-volatile loads, so we don't have to check for volatility of
1790 // gains over vector when the container becomes very large due to the
1793 // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
1802 DT.getRootNode()->begin(), DT.getRootNode()->end()));
1813 CurrentGeneration = NodeToProcess->currentGeneration();
1816 if (!NodeToProcess->isProcessed()) {
1818 Changed |= processNode(NodeToProcess->node());
1819 NodeToProcess->childGeneration(CurrentGeneration);
1820 NodeToProcess->process();
1821 } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
1822 // Push the next child onto the stack.
1823 DomTreeNode *child = NodeToProcess->nextChild();
1826 AvailableGEPs, NodeToProcess->childGeneration(), child,
1827 child->begin(), child->end()));
1862 static_cast<PassInfoMixin<EarlyCSEPass> *>(this)->printPipeline(
1872 /// A simple and fast domtree-based CSE pass.
1874 /// This pass does a simple depth-first walk over the dominator tree,
1930 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
1936 INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)
1951 INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1959 INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",