Transforms/Scalar/LoopStrengthReduce.cpp

142   void CountRegister(const SCEV *Reg, size_t LUIdx);
143   void DropRegister(const SCEV *Reg, size_t LUIdx);
144   void SwapAndDropUse(size_t LUIdx, size_t LastLUIdx);
146   bool isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const;
163 RegUseTracker::CountRegister(const SCEV *Reg, size_t LUIdx) {
169   RSD.UsedByIndices.resize(std::max(RSD.UsedByIndices.size(), LUIdx + 1));
170   RSD.UsedByIndices.set(LUIdx);
174 RegUseTracker::DropRegister(const SCEV *Reg, size_t LUIdx) {
178   assert(RSD.UsedByIndices.size() > LUIdx);
179   RSD.UsedByIndices.reset(LUIdx);
183 RegUseTracker::SwapAndDropUse(size_t LUIdx, size_t LastLUIdx) {
184   assert(LUIdx <= LastLUIdx);
191     if (LUIdx < UsedByIndices.size())
192       UsedByIndices[LUIdx] =
199 RegUseTracker::isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const {
206   if ((size_t)i != LUIdx) return true;
264   bool hasRegsUsedByUsesOtherThan(size_t LUIdx,
381 bool Formula::hasRegsUsedByUsesOtherThan(size_t LUIdx,
384     if (RegUses.isRegUsedByUsesOtherThan(ScaledReg, LUIdx))
388     if (RegUses.isRegUsedByUsesOtherThan(*I, LUIdx))
1041   /// LUIdx - The index of the LSRUse describing the expression which
1043   size_t LUIdx;
1061   : UserInst(0), OperandValToReplace(0), LUIdx(~size_t(0)), Offset(0) {}
1098   if (LUIdx != ~size_t(0))
1099     OS << ", LUIdx=" << LUIdx;
1204   void RecomputeRegs(size_t LUIdx, RegUseTracker &Reguses);
1262 void LSRUse::RecomputeRegs(size_t LUIdx, RegUseTracker &RegUses) {
1277       RegUses.DropRegister(*I, LUIdx);
1671   void DeleteUse(LSRUse &LU, size_t LUIdx);
1675   void InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
1676   void InsertSupplementalFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
1677   void CountRegisters(const Formula &F, size_t LUIdx);
1678   bool InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F);
1682   void GenerateReassociations(LSRUse &LU, unsigned LUIdx, Formula Base,
1684   void GenerateCombinations(LSRUse &LU, unsigned LUIdx, Formula Base);
1685   void GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx, Formula Base);
1686   void GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx, Formula Base);
1687   void GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, Formula Base);
1688   void GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base);
1689   void GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base);
2235     size_t LUIdx = P.first->second;
2236     LSRUse &LU = Uses[LUIdx];
2239       return std::make_pair(LUIdx, Offset);
2243   size_t LUIdx = Uses.size();
2244   P.first->second = LUIdx;
2246   LSRUse &LU = Uses[LUIdx];
2255   return std::make_pair(LUIdx, Offset);
2259 void LSRInstance::DeleteUse(LSRUse &LU, size_t LUIdx) {
2265   RegUses.SwapAndDropUse(LUIdx, Uses.size());
2274   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
2275     LSRUse &LU = Uses[LUIdx];
2976     LF.LUIdx = P.first;
2978     LSRUse &LU = Uses[LF.LUIdx];
2987       InsertInitialFormula(S, LU, LF.LUIdx);
2988       CountRegisters(LU.Formulae.back(), LF.LUIdx);
2999 LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) {
3006   bool Inserted = InsertFormula(LU, LUIdx, F);
3014                                        LSRUse &LU, size_t LUIdx) {
3018   bool Inserted = InsertFormula(LU, LUIdx, F);
3024 void LSRInstance::CountRegisters(const Formula &F, size_t LUIdx) {
3026     RegUses.CountRegister(F.ScaledReg, LUIdx);
3029     RegUses.CountRegister(*I, LUIdx);
3034 bool LSRInstance::InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F) {
3038   CountRegisters(F, LUIdx);
3113         LF.LUIdx = P.first;
3115         LSRUse &LU = Uses[LF.LUIdx];
3121         InsertSupplementalFormula(U, LU, LF.LUIdx);
3193 void LSRInstance::GenerateReassociations(LSRUse &LU, unsigned LUIdx,
3263       if (InsertFormula(LU, LUIdx, F))
3266         GenerateReassociations(LU, LUIdx, LU.Formulae.back(), Depth+1);
3273 void LSRInstance::GenerateCombinations(LSRUse &LU, unsigned LUIdx,
3297       (void)InsertFormula(LU, LUIdx, F);
3303 void LSRInstance::GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx,
3318     (void)InsertFormula(LU, LUIdx, F);
3323 void LSRInstance::GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx,
3350         (void)InsertFormula(LU, LUIdx, F);
3362     (void)InsertFormula(LU, LUIdx, F);
3368 void LSRInstance::GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx,
3450     (void)InsertFormula(LU, LUIdx, F);
3457 void LSRInstance::GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base) {
3504           (void)InsertFormula(LU, LUIdx, F);
3511 void LSRInstance::GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base) {
3533       if (!F.hasRegsUsedByUsesOtherThan(LUIdx, RegUses))
3536       (void)InsertFormula(LU, LUIdx, F);
3547   size_t LUIdx;
3552     : LUIdx(LI), Imm(I), OrigReg(R) {}
3561   OS << "in formulae referencing " << *OrigReg << " in use " << LUIdx
3638         for (int LUIdx = UsedByIndices.find_first(); LUIdx != -1;
3639              LUIdx = UsedByIndices.find_next(LUIdx))
3641           if (UniqueItems.insert(std::make_pair(LUIdx, Imm)))
3642             WorkItems.push_back(WorkItem(LUIdx, Imm, OrigReg));
3656     size_t LUIdx = WI.LUIdx;
3657     LSRUse &LU = Uses[LUIdx];
3693         (void)InsertFormula(LU, LUIdx, NewF);
3726           (void)InsertFormula(LU, LUIdx, NewF);
3740   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3741     LSRUse &LU = Uses[LUIdx];
3743       GenerateReassociations(LU, LUIdx, LU.Formulae[i]);
3745       GenerateCombinations(LU, LUIdx, LU.Formulae[i]);
3747   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3748     LSRUse &LU = Uses[LUIdx];
3750       GenerateSymbolicOffsets(LU, LUIdx, LU.Formulae[i]);
3752       GenerateConstantOffsets(LU, LUIdx, LU.Formulae[i]);
3754       GenerateICmpZeroScales(LU, LUIdx, LU.Formulae[i]);
3756       GenerateScales(LU, LUIdx, LU.Formulae[i]);
3758   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3759     LSRUse &LU = Uses[LUIdx];
3761       GenerateTruncates(LU, LUIdx, LU.Formulae[i]);
3787   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3788     LSRUse &LU = Uses[LUIdx];
3822           if (RegUses.isRegUsedByUsesOtherThan(Reg, LUIdx))
3826             RegUses.isRegUsedByUsesOtherThan(F.ScaledReg, LUIdx))
3861       LU.RecomputeRegs(LUIdx, RegUses);
3909     for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3910       LSRUse &LU = Uses[LUIdx];
3953         LU.RecomputeRegs(LUIdx, RegUses);
3974   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3975     LSRUse &LU = Uses[LUIdx];
3998         if (Fixup.LUIdx == LUIdx) {
3999           Fixup.LUIdx = LUThatHas - &Uses.front();
4011         if (Fixup.LUIdx == NumUses-1)
4012           Fixup.LUIdx = LUIdx;
4034       DeleteUse(LU, LUIdx);
4035       --LUIdx;
4100     for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
4101       LSRUse &LU = Uses[LUIdx];
4119         LU.RecomputeRegs(LUIdx, RegUses);
4382   const LSRUse &LU = Uses[LF.LUIdx];
4653     if (Uses[LF.LUIdx].Kind == LSRUse::ICmpZero)
4691     Rewrite(Fixup, *Solution[Fixup.LUIdx], Rewriter, DeadInsts, P);