Lines Matching full:formula
481 /// This class holds information that describes a formula for computing
483 struct Formula { struct
497 /// canonical representation of a formula is
501 /// formula should be put in the ScaledReg.
503 /// registers are needed by the formula: e.g., reg1 + reg2 is reg1 + 1 * reg2.
507 /// This invariant can be temporarily broken while building a formula.
508 /// However, every formula inserted into the LSRInstance must be in canonical
521 Formula() = default;
601 /// Incorporate loop-variant parts of S into this Formula, attempting to keep
603 void Formula::initialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) { in initialMatch()
628 /// Check whether or not this formula satisfies the canonical
630 /// \see Formula::BaseRegs.
631 bool Formula::isCanonical(const Loop &L) const { in isCanonical()
652 /// Helper method to morph a formula into its canonical representation.
653 /// \see Formula::BaseRegs.
654 /// Every formula having more than one base register, must use the ScaledReg
658 void Formula::canonicalize(const Loop &L) { in canonicalize()
691 /// Get rid of the scale in the formula.
694 /// \note After this operation the formula may not be in the canonical form.
695 bool Formula::unscale() { in unscale()
704 bool Formula::hasZeroEnd() const { in hasZeroEnd()
712 /// Return the total number of register operands used by this formula. This does
714 size_t Formula::getNumRegs() const { in getNumRegs()
718 /// Return the type of this formula, if it has one, or null otherwise. This type
720 Type *Formula::getType() const { in getType()
728 void Formula::deleteBaseReg(const SCEV *&S) { in deleteBaseReg()
734 /// Test if this formula references the given register.
735 bool Formula::referencesReg(const SCEV *S) const { in referencesReg()
739 /// Test whether this formula uses registers which are used by uses other than
741 bool Formula::hasRegsUsedByUsesOtherThan(size_t LUIdx, in hasRegsUsedByUsesOtherThan()
753 void Formula::print(raw_ostream &OS) const { in print()
789 LLVM_DUMP_METHOD void Formula::dump() const { in dump()
1187 const LSRUse &LU, const Formula &F);
1191 const LSRUse &LU, const Formula &F,
1238 void RateFormula(const Formula &F,
1248 void RateRegister(const Formula &F, const SCEV *Reg,
1250 void RatePrimaryRegister(const Formula &F, const SCEV *Reg,
1344 /// with a single formula--the one that initially matched. Some SCEV
1347 /// changing the formula.
1359 SmallVector<Formula, 12> Formulae;
1379 bool HasFormulaWithSameRegs(const Formula &F) const;
1381 bool InsertFormula(const Formula &F, const Loop &L);
1382 void DeleteFormula(Formula &F);
1418 void Cost::RateRegister(const Formula &F, const SCEV *Reg, in RateRegister()
1486 /// it. Optional LoserRegs provides a way to declare any formula that refers to
1488 void Cost::RatePrimaryRegister(const Formula &F, const SCEV *Reg, in RatePrimaryRegister()
1502 void Cost::RateFormula(const Formula &F, in RateFormula()
1509 assert(F.isCanonical(*L) && "Cost is accurate only for canonical formula"); in RateFormula()
1588 // If ICmpZero formula ends with not 0, it could not be replaced by in RateFormula()
1699 /// Test whether this use as a formula which has the same registers as the given
1700 /// formula.
1701 bool LSRUse::HasFormulaWithSameRegs(const Formula &F) const { in HasFormulaWithSameRegs()
1709 /// The function returns a probability of selecting formula without Reg.
1712 for (const Formula &F : Formulae) in getNotSelectedProbability()
1718 /// If the given formula has not yet been inserted, add it to the list, and
1719 /// return true. Return false otherwise. The formula must be in canonical form.
1720 bool LSRUse::InsertFormula(const Formula &F, const Loop &L) { in InsertFormula()
1742 // Add the formula to the list. in InsertFormula()
1753 /// Remove the given formula from this use's list.
1754 void LSRUse::DeleteFormula(Formula &F) { in DeleteFormula()
1765 for (const Formula &F : Formulae) { in RecomputeRegs()
1908 const Formula &F, const Loop &L) { in isAMCompletelyFolded()
1909 // For the purpose of isAMCompletelyFolded either having a canonical formula in isAMCompletelyFolded()
1921 /// Test whether we know how to expand the current formula.
1938 MemAccessTy AccessTy, const Formula &F) { in isLegalUse()
1952 const LSRUse &LU, const Formula &F) { in isAMCompletelyFolded()
1969 const LSRUse &LU, const Formula &F, in getScalingFactorCost()
2025 // Canonicalize a scale of 1 to a base register if the formula doesn't in isAlwaysFoldable()
2223 LSRUse *FindUseWithSimilarFormula(const Formula &F, const LSRUse &OrigLU);
2227 void CountRegisters(const Formula &F, size_t LUIdx);
2228 bool InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F);
2232 void GenerateReassociations(LSRUse &LU, unsigned LUIdx, Formula Base,
2236 const Formula &Base, unsigned Depth,
2238 void GenerateCombinations(LSRUse &LU, unsigned LUIdx, Formula Base);
2240 const Formula &Base, size_t Idx,
2242 void GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx, Formula Base);
2244 const Formula &Base,
2247 void GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx, Formula Base);
2248 void GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, Formula Base);
2249 void GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base);
2250 void GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base);
2266 void SolveRecurse(SmallVectorImpl<const Formula *> &Solution,
2268 SmallVectorImpl<const Formula *> &Workspace,
2272 void Solve(SmallVectorImpl<const Formula *> &Solution) const;
2281 Value *Expand(const LSRUse &LU, const LSRFixup &LF, const Formula &F,
2285 const Formula &F,
2287 void Rewrite(const LSRUse &LU, const LSRFixup &LF, const Formula &F,
2289 void ImplementSolution(const SmallVectorImpl<const Formula *> &Solution);
2853 /// Look for a use distinct from OrigLU which is has a formula that has the same
2854 /// registers as the given formula.
2856 LSRInstance::FindUseWithSimilarFormula(const Formula &OrigF, in FindUseWithSimilarFormula()
2858 // Search all uses for the formula. This could be more clever. in FindUseWithSimilarFormula()
2871 for (const Formula &F : LU.Formulae) { in FindUseWithSimilarFormula()
2872 // Check to see if this formula has the same registers and symbols in FindUseWithSimilarFormula()
2881 // This is the formula where all the registers and symbols matched; in FindUseWithSimilarFormula()
3628 // Create SCEV as Formula for calculating baseline cost in CollectFixupsAndInitialFormulae()
3630 Formula F; in CollectFixupsAndInitialFormulae()
3641 // If this is the first use of this LSRUse, give it a formula. in CollectFixupsAndInitialFormulae()
3651 /// Insert a formula for the given expression into the given use, separating out
3659 Formula F; in InsertInitialFormula()
3662 assert(Inserted && "Initial formula already exists!"); (void)Inserted; in InsertInitialFormula()
3665 /// Insert a simple single-register formula for the given expression into the
3670 Formula F; in InsertSupplementalFormula()
3674 assert(Inserted && "Supplemental formula already exists!"); (void)Inserted; in InsertSupplementalFormula()
3677 /// Note which registers are used by the given formula, updating RegUses.
3678 void LSRInstance::CountRegisters(const Formula &F, size_t LUIdx) { in CountRegisters()
3685 /// If the given formula has not yet been inserted, add it to the list, and
3687 bool LSRInstance::InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F) { in InsertFormula()
3688 // Do not insert formula that we will not be able to expand. in InsertFormula()
3690 "Formula is illegal"); in InsertFormula()
3916 const Formula &Base, in GenerateReassociationsImpl()
3922 // reassociations cause extra base+register formula to be created, in GenerateReassociationsImpl()
3964 Formula F = Base; in GenerateReassociationsImpl()
3969 // Add the remaining pieces of the add back into the new formula. in GenerateReassociationsImpl()
3997 // formula accordingly. in GenerateReassociationsImpl()
4001 // If that formula hadn't been seen before, recurse to find more like in GenerateReassociationsImpl()
4014 Formula Base, unsigned Depth) { in GenerateReassociations()
4028 /// Generate a formula consisting of all of the loop-dominating registers added
4031 Formula Base) { in GenerateCombinations()
4039 // processing the formula. in GenerateCombinations()
4042 Formula NewBase = Base; in GenerateCombinations()
4063 Formula F = NewBase; in GenerateCombinations()
4076 // If we collected at least two registers, generate a formula combining them. in GenerateCombinations()
4082 // If we have an unfolded offset, generate a formula combining it with the in GenerateCombinations()
4095 const Formula &Base, size_t Idx, in GenerateSymbolicOffsetsImpl()
4101 Formula F = Base; in GenerateSymbolicOffsetsImpl()
4114 Formula Base) { in GenerateSymbolicOffsets()
4127 LSRUse &LU, unsigned LUIdx, const Formula &Base, in GenerateConstantOffsetsImpl()
4131 Formula F = Base; in GenerateConstantOffsetsImpl()
4191 Formula F = Base; in GenerateConstantOffsetsImpl()
4199 // We may generate non canonical Formula if G is a recurrent expr reg in GenerateConstantOffsetsImpl()
4208 Formula Base) { in GenerateConstantOffsets()
4226 Formula Base) { in GenerateICmpZeroScales()
4229 // Determine the integer type for the base formula. in GenerateICmpZeroScales()
4278 Formula F = Base; in GenerateICmpZeroScales()
4326 void LSRInstance::GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base) { in GenerateScales()
4327 // Determine the integer type for the base formula. in GenerateScales()
4331 // If this Formula already has a scaled register, we can't add another one. in GenerateScales()
4332 // Try to unscale the formula to generate a better scale. in GenerateScales()
4372 Formula F = Base; in GenerateScales()
4376 // Base. In that case, do not try to insert the formula, it will be in GenerateScales()
4382 // non canonical Formula with ScaledReg's loop not being L. in GenerateScales()
4416 void LSRInstance::GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base) { in GenerateTruncates()
4420 // Determine the integer type for the base formula. in GenerateTruncates()
4440 Formula F = Base; in GenerateTruncates()
4616 Formula F = LU.Formulae[L]; in GenerateCrossUseConstantOffsets()
4620 // Formula. in GenerateCrossUseConstantOffsets()
4631 Formula NewF = F; in GenerateCrossUseConstantOffsets()
4640 // immediate itself, then the formula isn't worthwhile. in GenerateCrossUseConstantOffsets()
4663 Formula NewF = F; in GenerateCrossUseConstantOffsets()
4682 // If the new formula has a constant in a register, and adding the in GenerateCrossUseConstantOffsets()
4684 // zero than the immediate itself, then the formula isn't worthwhile. in GenerateCrossUseConstantOffsets()
4756 // Collect the best formula for each unique set of shared registers. This in FilterOutUndesirableDedicatedRegisters()
4771 Formula &F = LU.Formulae[FIdx]; in FilterOutUndesirableDedicatedRegisters()
4784 // During initial formula generation, undesirable formulae are generated in FilterOutUndesirableDedicatedRegisters()
4787 // as the basis of rediscovering the desired formula that uses an AddRec in FilterOutUndesirableDedicatedRegisters()
4811 Formula &Best = LU.Formulae[P.first->second]; in FilterOutUndesirableDedicatedRegisters()
4818 LLVM_DEBUG(dbgs() << " Filtering out formula "; F.print(dbgs()); in FilterOutUndesirableDedicatedRegisters()
4820 " in favor of formula "; in FilterOutUndesirableDedicatedRegisters()
4865 /// When one formula uses a superset of the registers of another formula, it
4880 Formula &F = LU.Formulae[i]; in NarrowSearchSpaceByDetectingSupersets()
4883 // Look for a formula with a constant or GV in a register. If the use in NarrowSearchSpaceByDetectingSupersets()
4884 // also has a formula with that same value in an immediate field, in NarrowSearchSpaceByDetectingSupersets()
4889 Formula NewF = F; in NarrowSearchSpaceByDetectingSupersets()
4909 Formula NewF = F; in NarrowSearchSpaceByDetectingSupersets()
4949 for (const Formula &F : LU.Formulae) { in NarrowSearchSpaceByCollapsingUnrolledCode()
4975 Formula &F = LUThatHas->Formulae[i]; in NarrowSearchSpaceByCollapsingUnrolledCode()
5031 "Narrowing the search space by choosing the best Formula " in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5034 // Map the "Scale * ScaledReg" pair to the best formula of current LSRUse. in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5049 // Return true if Formula FA is better than Formula FB. in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5050 auto IsBetterThan = [&](Formula &FA, Formula &FB) { in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5051 // First we will try to choose the Formula with fewer new registers. in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5052 // For a register used by current Formula, the more the register is in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5054 // counter of the formula. in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5068 // If the new register numbers are the same, choose the Formula with in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5082 Formula &F = LU.Formulae[FIdx]; in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5089 Formula &Best = LU.Formulae[P.first->second]; in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5092 LLVM_DEBUG(dbgs() << " Filtering out formula "; F.print(dbgs()); in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5094 " in favor of formula "; in NarrowSearchSpaceByFilterFormulaWithSameScaledReg()
5128 "register Formula for PostInc Uses.\n"); in NarrowSearchSpaceByFilterPostInc()
5140 for (const Formula &F : LU.Formulae) in NarrowSearchSpaceByFilterPostInc()
5146 Formula &F = LU.Formulae[FIdx]; in NarrowSearchSpaceByFilterPostInc()
5148 LLVM_DEBUG(dbgs() << " Filtering out formula "; F.print(dbgs()); in NarrowSearchSpaceByFilterPostInc()
5167 /// Assuming we don't know the value of each formula (already delete
5193 /// Now count registers number mathematical expectation for each formula:
5215 // Used in each formula of a solution (in example above this is reg(c)). in NarrowSearchSpaceByDeletingCostlyFormulas()
5254 Formula &F = LU.Formulae[i]; in NarrowSearchSpaceByDeletingCostlyFormulas()
5281 LLVM_DEBUG(dbgs() << " The formula "; LU.Formulae[MinIdx].print(dbgs()); in NarrowSearchSpaceByDeletingCostlyFormulas()
5291 assert(LU.Formulae.size() == 1 && "Should be exactly 1 min regs formula"); in NarrowSearchSpaceByDeletingCostlyFormulas()
5292 Formula &F = LU.Formulae[0]; in NarrowSearchSpaceByDeletingCostlyFormulas()
5294 // When we choose the formula, the regs become unique. in NarrowSearchSpaceByDeletingCostlyFormulas()
5359 // handle +C but not -C), opt for the simpler formula. in NarrowSearchSpaceByPickingWinnerRegs()
5385 Formula &F = LU.Formulae[i]; in NarrowSearchSpaceByPickingWinnerRegs()
5423 void LSRInstance::SolveRecurse(SmallVectorImpl<const Formula *> &Solution, in SolveRecurse()
5425 SmallVectorImpl<const Formula *> &Workspace, in SolveRecurse()
5432 // - sort the formula so that the most profitable solutions are found first in SolveRecurse()
5442 // in-progress solution, consider it a requirement that a formula must in SolveRecurse()
5452 for (const Formula &F : LU.Formulae) { in SolveRecurse()
5454 // ReqRegs. The formula should use all required registers before in SolveRecurse()
5476 // Evaluate the cost of the current formula. If it's already worse than in SolveRecurse()
5503 /// Choose one formula from each use. Return the results in the given Solution
5505 void LSRInstance::Solve(SmallVectorImpl<const Formula *> &Solution) const { in Solve()
5506 SmallVector<const Formula *, 8> Workspace; in Solve()
5685 const Formula &F, BasicBlock::iterator IP, in Expand()
5826 // An ICmpZero Formula represents an ICmp which we're handling as a in Expand()
5869 PHINode *PN, const LSRUse &LU, const LSRFixup &LF, const Formula &F, in RewriteForPHI()
6001 const Formula &F, in Rewrite()
6067 const SmallVectorImpl<const Formula *> &Solution) { in ImplementSolution()
6243 SmallVector<const Formula *, 8> Solution; in LSRInstance()
6257 for (const Formula &F : LU.Formulae) in LSRInstance()
6259 F) && "Illegal formula generated!"); in LSRInstance()
6304 for (const Formula &F : LU.Formulae) { in print_uses()