Lines Matching +full:se +full:- +full:pos
1 //===- NaryReassociate.cpp - Reassociate n-ary expressions ----------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This pass reassociates n-ary add expressions and eliminates the redundancy
40 // into an SCEV-to-instruction map.
42 // Although the algorithm pattern-matches only ternary additions, it
43 // automatically handles many >3-ary expressions by walking through the function
44 // in the depth-first order. For example, given
52 // Finally, the above dominator-based algorithm may need to be run multiple
57 // single-use instruction and thus eligible for split consideration. For
73 // 1) We only considers n-ary adds and muls for now. This should be extended
76 //===----------------------------------------------------------------------===//
117 #define DEBUG_TYPE "nary-reassociate"
155 INITIALIZE_PASS_BEGIN(NaryReassociateLegacyPass, "nary-reassociate",
162 INITIALIZE_PASS_END(NaryReassociateLegacyPass, "nary-reassociate",
175 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
179 return Impl.runImpl(F, AC, DT, SE, TLI, TTI);
186 auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
190 if (!runImpl(F, AC, DT, SE, TLI, TTI))
205 SE = SE_;
226 BasicBlock *BB = Node->getBlock();
237 const SCEV *NewSCEV = SE->getSCEV(NewI);
258 // nary-gep.ll.
268 DeadInsts, TLI, nullptr, [this](Value *V) { SE->forgetValue(V); });
284 OrigSCEV = SE->getSCEV(I);
298 if (!SE->isSCEVable(I->getType()))
301 switch (I->getOpcode()) {
304 OrigSCEV = SE->getSCEV(I);
307 OrigSCEV = SE->getSCEV(I);
318 if (I->getType()->isIntegerTy())
330 SmallVector<const Value *, 4> Indices(GEP->indices());
331 return TTI->getGEPCost(GEP->getSourceElementType(), GEP->getPointerOperand(),
341 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
343 if (auto *NewGEP = tryReassociateGEPAtIndex(GEP, I - 1,
355 DL->getIndexSizeInBits(GEP->getType()->getPointerAddressSpace());
356 return cast<IntegerType>(Index->getType())->getBitWidth() < IndexSizeInBits;
363 Value *IndexToSplit = GEP->getOperand(I + 1);
365 IndexToSplit = SExt->getOperand(0);
367 // zext can be treated as sext if the source is non-negative.
368 if (isKnownNonNegative(ZExt->getOperand(0), SQ))
369 IndexToSplit = ZExt->getOperand(0);
373 // If the I-th index needs sext and the underlying add is not equipped with
380 Value *LHS = AO->getOperand(0), *RHS = AO->getOperand(1);
399 // the I-th index is replaced with LHS.
401 for (Use &Index : GEP->indices())
402 IndexExprs.push_back(SE->getSCEV(Index));
403 // Replace the I-th index with LHS.
404 IndexExprs[I] = SE->getSCEV(LHS);
406 DL->getTypeSizeInBits(LHS->getType()).getFixedValue() <
407 DL->getTypeSizeInBits(GEP->getOperand(I)->getType())
409 // Zero-extend LHS if it is non-negative. InstCombine canonicalizes sext to
410 // zext if the source operand is proved non-negative. We should do that
414 SE->getZeroExtendExpr(IndexExprs[I], GEP->getOperand(I)->getType());
416 const SCEV *CandidateExpr = SE->getGEPExpr(cast<GEPOperator>(GEP),
427 Candidate = Builder.CreateBitOrPointerCast(Candidate, GEP->getType());
428 assert(Candidate->getType() == GEP->getType());
431 uint64_t IndexedSize = DL->getTypeAllocSize(IndexedType);
432 Type *ElementType = GEP->getResultElementType();
433 uint64_t ElementSize = DL->getTypeAllocSize(ElementType);
435 // GEP, the size of the type at the I-th index (IndexedSize) is not
452 Type *PtrIdxTy = DL->getIndexType(GEP->getType());
453 if (RHS->getType() != PtrIdxTy)
460 Builder.CreateGEP(GEP->getResultElementType(), Candidate, RHS));
461 NewGEP->setIsInBounds(GEP->isInBounds());
462 NewGEP->takeName(GEP);
467 Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
469 if (SE->getSCEV(I)->isZero())
483 if (LHS->hasOneUse() && matchTernaryOp(I, LHS, A, B)) {
486 const SCEV *AExpr = SE->getSCEV(A), *BExpr = SE->getSCEV(B);
487 const SCEV *RHSExpr = SE->getSCEV(RHS);
512 switch (I->getOpcode()) {
514 NewI = BinaryOperator::CreateAdd(LHS, RHS, "", I->getIterator());
517 NewI = BinaryOperator::CreateMul(LHS, RHS, "", I->getIterator());
522 NewI->setDebugLoc(I->getDebugLoc());
523 NewI->takeName(I);
529 switch (I->getOpcode()) {
543 switch (I->getOpcode()) {
545 return SE->getAddExpr(LHS, RHS);
547 return SE->getMulExpr(LHS, RHS);
557 auto Pos = SeenExprs.find(CandidateExpr);
558 if (Pos == SeenExprs.end())
561 auto &Candidates = Pos->second;
562 // Because we process the basic blocks in pre-order of the dominator tree, a
571 if (!DT->dominates(CandidateInstruction, Dominatee))
577 if (!SE->canReuseInstruction(CandidateExpr, CandidateInstruction,
582 I->dropPoisonGeneratingAnnotations();
605 // I - instruction matched by MaxMinMatch matcher
606 // MaxMinMatch - min/max idiom matcher
607 // LHS - first operand of I
608 // RHS - second operand of I
616 if (LHS->hasNUsesOrMore(3) ||
619 llvm::any_of(LHS->users(),
622 !(U->hasOneUser() && *U->users().begin() == I);
629 const SCEV *CExpr) -> Value * {
632 const SCEV *R1Expr = SE->getMinMaxExpr(SCEVType, Ops1);
639 LLVM_DEBUG(dbgs() << "NARY: Found common sub-expr: " << *R1MinMax << "\n");
641 SmallVector<const SCEV *, 2> Ops2{SE->getUnknown(C),
642 SE->getUnknown(R1MinMax)};
643 const SCEV *R2Expr = SE->getMinMaxExpr(SCEVType, Ops2);
645 SCEVExpander Expander(*SE, *DL, "nary-reassociate");
646 Value *NewMinMax = Expander.expandCodeFor(R2Expr, I->getType(), I);
647 NewMinMax->setName(Twine(I->getName()).concat(".nary"));
654 const SCEV *AExpr = SE->getSCEV(A);
655 const SCEV *BExpr = SE->getSCEV(B);
656 const SCEV *RHSExpr = SE->getSCEV(RHS);