Lines Matching full:basis
44 // When such rewriting is possible, we call S1 a "basis" of S2. When S2 has
46 // basis, the basis that is the closest ancestor in the dominator tree.
93 Stride(nullptr), Ins(nullptr), Basis(nullptr) {}
97 Basis(nullptr) {}
106 // candidate with respect to its immediate basis. Note that one instruction
120 // Points to the immediate basis of this candidate, or nullptr if we cannot
121 // find any basis for this candidate.
122 Candidate *Basis;
148 // Returns true if Basis is a basis for C, i.e., Basis dominates C and they
150 bool isBasisFor(const Candidate &Basis, const Candidate &C);
158 // to Candidates, and tries to find the immediate basis for each of them.
180 // basis.
184 // Rewrites candidate C with respect to Basis.
185 void rewriteCandidateWithBasis(const Candidate &C, const Candidate &Basis);
191 // Emit code that computes the "bump" from Basis to C. If the candidate is a
194 // basis using an ugly GEP.
195 static Value *emitBump(const Candidate &Basis, const Candidate &C,
224 bool StraightLineStrengthReduce::isBasisFor(const Candidate &Basis,
226 return (Basis.Ins != C.Ins && // skip the same instruction
227 // They must have the same type too. Basis.Base == C.Base doesn't
229 Basis.Ins->getType() == C.Ins->getType() &&
230 // Basis must dominate C in order to rewrite C with respect to Basis.
231 DT->dominates(Basis.Ins->getParent(), C.Ins->getParent()) &&
233 Basis.Base == C.Base && Basis.Stride == C.Stride &&
234 Basis.CandidateKind == C.CandidateKind);
298 // a candidate. Therefore, finding the immediate basis of a candidate boils down
315 // the basis of other candidates, but we leave I's basis blank so that I
318 // Try to compute the immediate basis of C.
322 for (auto Basis = Candidates.rbegin();
323 Basis != Candidates.rend() && NumIterations < MaxNumIterations;
324 ++Basis, ++NumIterations) {
325 if (isBasisFor(*Basis, C)) {
326 C.Basis = &(*Basis);
331 // Regardless of whether we find a basis for C, we need to push C to the
332 // candidate list so that it can be the basis of other candidates.
537 Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,
542 APInt Idx = C.Index->getValue(), BasisIdx = Basis.Index->getValue();
547 if (Basis.CandidateKind == Candidate::GEP) {
551 cast<GetElementPtrInst>(Basis.Ins)->getResultElementType()));
560 // Compute Bump = C - Basis = (i' - i) * S.
571 IntegerType::get(Basis.Ins->getContext(), IndexOffset.getBitWidth());
589 const Candidate &C, const Candidate &Basis) {
590 assert(C.CandidateKind == Basis.CandidateKind && C.Base == Basis.Base &&
591 C.Stride == Basis.Stride);
593 // basis of a candidate cannot be unlinked before the candidate.
594 assert(Basis.Ins->getParent() != nullptr && "the basis is unlinked");
605 Value *Bump = emitBump(Basis, C, Builder, DL, BumpWithUglyGEP);
610 // C = Basis + Bump
612 // If Bump is a neg instruction, emit C = Basis - (-Bump).
614 Builder.CreateSub(Basis.Ins, BinaryOperator::getNegArgument(Bump));
628 Reduced = Builder.CreateAdd(Basis.Ins, Bump);
636 // C = (char *)Basis + Bump
637 unsigned AS = Basis.Ins->getType()->getPointerAddressSpace();
638 Type *CharTy = Type::getInt8PtrTy(Basis.Ins->getContext(), AS);
639 Reduced = Builder.CreateBitCast(Basis.Ins, CharTy);
647 // C = gep Basis, Bump
651 Reduced = Builder.CreateInBoundsGEP(nullptr, Basis.Ins, Bump);
653 Reduced = Builder.CreateGEP(nullptr, Basis.Ins, Bump);
684 // a candidate being rewritten is not a basis for any other candidate.
687 if (C.Basis != nullptr) {
688 rewriteCandidateWithBasis(C, *C.Basis);
