43 // When such rewriting is possible, we call S1 a "basis" of S2. When S2 has
45 // basis, the basis that is the closest ancestor in the dominator tree.
158     // candidate with respect to its immediate basis. Note that one instruction
173     // Points to the immediate basis of this candidate, or nullptr if we cannot
174     // find any basis for this candidate.
175     Candidate *Basis = nullptr;  member
181   // Returns true if Basis is a basis for C, i.e., Basis dominates C and they
183   bool isBasisFor(const Candidate &Basis, const Candidate &C);
194   // to Candidates, and tries to find the immediate basis for each of them.
222   // basis.
227   // Rewrites candidate C with respect to Basis.
228   void rewriteCandidateWithBasis(const Candidate &C, const Candidate &Basis);
236   // Emit code that computes the "bump" from Basis to C.
237   static Value *emitBump(const Candidate &Basis, const Candidate &C,
268 bool StraightLineStrengthReduce::isBasisFor(const Candidate &Basis,  in isBasisFor()  argument
270   return (Basis.Ins != C.Ins && // skip the same instruction  in isBasisFor()
271           // They must have the same type too. Basis.Base == C.Base doesn't  in isBasisFor()
273           Basis.Ins->getType() == C.Ins->getType() &&  in isBasisFor()
274           // Basis must dominate C in order to rewrite C with respect to Basis.  in isBasisFor()
275           DT->dominates(Basis.Ins->getParent(), C.Ins->getParent()) &&  in isBasisFor()
277           Basis.Base == C.Base && Basis.Stride == C.Stride &&  in isBasisFor()
278           Basis.CandidateKind == C.CandidateKind);  in isBasisFor()
340 // a candidate. Therefore, finding the immediate basis of a candidate boils down
357   // the basis of other candidates, but we leave I's basis blank so that I  in allocateCandidatesAndFindBasis()
360     // Try to compute the immediate basis of C.  in allocateCandidatesAndFindBasis()
364     for (auto Basis = Candidates.rbegin();  in allocateCandidatesAndFindBasis()  local
365          Basis != Candidates.rend() && NumIterations < MaxNumIterations;  in allocateCandidatesAndFindBasis()
366          ++Basis, ++NumIterations) {  in allocateCandidatesAndFindBasis()
367       if (isBasisFor(*Basis, C)) {  in allocateCandidatesAndFindBasis()
368         C.Basis = &(*Basis);  in allocateCandidatesAndFindBasis()
373   // Regardless of whether we find a basis for C, we need to push C to the  in allocateCandidatesAndFindBasis()
374   // candidate list so that it can be the basis of other candidates.  in allocateCandidatesAndFindBasis()
575 Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,  in emitBump()  argument
579   APInt Idx = C.Index->getValue(), BasisIdx = Basis.Index->getValue();  in emitBump()
583   // Compute Bump = C - Basis = (i' - i) * S.  in emitBump()
594       IntegerType::get(Basis.Ins->getContext(), IndexOffset.getBitWidth());  in emitBump()
612     const Candidate &C, const Candidate &Basis) {  in rewriteCandidateWithBasis()  argument
613   assert(C.CandidateKind == Basis.CandidateKind && C.Base == Basis.Base &&  in rewriteCandidateWithBasis()
614          C.Stride == Basis.Stride);  in rewriteCandidateWithBasis()
616   // basis of a candidate cannot be unlinked before the candidate.  in rewriteCandidateWithBasis()
617   assert(Basis.Ins->getParent() != nullptr && "the basis is unlinked");  in rewriteCandidateWithBasis()
627   Value *Bump = emitBump(Basis, C, Builder, DL);  in rewriteCandidateWithBasis()
632     // C = Basis + Bump  in rewriteCandidateWithBasis()
635       // If Bump is a neg instruction, emit C = Basis - (-Bump).  in rewriteCandidateWithBasis()
636       Reduced = Builder.CreateSub(Basis.Ins, NegBump);  in rewriteCandidateWithBasis()
650       Reduced = Builder.CreateAdd(Basis.Ins, Bump);  in rewriteCandidateWithBasis()
656     // C = (char *)Basis + Bump  in rewriteCandidateWithBasis()
657     Reduced = Builder.CreatePtrAdd(Basis.Ins, Bump, "", InBounds);  in rewriteCandidateWithBasis()
689   // a candidate being rewritten is not a basis for any other candidate.  in runOnFunction()
692     if (C.Basis != nullptr) {  in runOnFunction()
693       rewriteCandidateWithBasis(C, *C.Basis);  in runOnFunction()