1 //===- BitTracker.cpp -----------------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // SSA-based bit propagation.
13 // of bits are represented by the class BitValue, and take one of four
16 // cannot be a copy of yet another bit---such chains are not allowed).
21 // assuming that nothing is known about bits of %1, bit 1 of %2
31 // The tracker implements the Wegman-Zadeck algorithm, originally developed
32 // for SSA-based constant propagation. Each register is represented as
33 // a sequence of bits, with the convention that bit 0 is the least signi-
38 // The intended usage of the bit tracker is to create a target-specific
53 // The code below is intended to be fully target-independent.
116     unsigned n = RC.Bits.size();  in operator <<()
119     // into logical segments, such as sequences of 0 or 1 bits or references  in operator <<()
120     // to consecutive bits (e.g. "bits 3-5 are same as bits 7-9 of reg xyz").  in operator <<()
123     bool SeqRef = false;    // A sequence of refs to consecutive bits.  in operator <<()
126     for (unsigned i = 1, n = RC.Bits.size(); i < n; ++i) {  in operator <<()
138         if (SeqRef && V.RefI.Pos == SV.RefI.Pos+(i-Start))  in operator <<()
147       unsigned Count = i - Start;  in operator <<()
151         OS << '-' << i-1 << "]:";  in operator <<()
153           OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'  in operator <<()
154              << SV.RefI.Pos+(Count-1) << ']';  in operator <<()
163     unsigned Count = n - Start;  in operator <<()
164     if (n-Start == 1) {  in operator <<()
167       OS << '-' << n-1 << "]:";  in operator <<()
170         OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'  in operator <<()
171            << SV.RefI.Pos+(Count-1) << ']';  in operator <<()
184     dbgs() << printReg(P.first, &ME.TRI) << " -> " << P.second << "\n";  in print_cells()
198 // the actual bits of the "self" register.
206   for (uint16_t i = 0, n = Bits.size(); i < n; ++i) {  in meet()
208     Changed |= Bits[i].meet(RCV, BitRef(SelfR, i));  in meet()
219   // The masked part of *this must have the same number of bits  in insert()
221   assert(B > E || E-B+1 == RC.width());      // B <= E  =>  E-B+1 = |RC|.  in insert()
222   assert(B <= E || E+(W-B)+1 == RC.width()); // E < B   =>  E+(W-B)+1 = |RC|.  in insert()
224     for (uint16_t i = 0; i <= E-B; ++i)  in insert()
225       Bits[i+B] = RC[i];  in insert()
227     for (uint16_t i = 0; i < W-B; ++i)  in insert()
228       Bits[i+B] = RC[i];  in insert()
230       Bits[i] = RC[i+(W-B)];  in insert()
239     RegisterCell RC(E-B+1);  in extract()
241       RC.Bits[i-B] = Bits[i];  in extract()
245   RegisterCell RC(E+(W-B)+1);  in extract()
246   for (uint16_t i = 0; i < W-B; ++i)  in extract()
247     RC.Bits[i] = Bits[i+B];  in extract()
249     RC.Bits[i+(W-B)] = Bits[i];  in extract()
255   // Swap the two parts:  [0..W-Sh-1] [W-Sh..W-1]  in rol()
261   RegisterCell Tmp(W-Sh);  in rol()
262   // Tmp = [0..W-Sh-1].  in rol()
263   for (uint16_t i = 0; i < W-Sh; ++i)  in rol()
264     Tmp[i] = Bits[i];  in rol()
265   // Shift [W-Sh..W-1] to [0..Sh-1].  in rol()
267     Bits[i] = Bits[W-Sh+i];  in rol()
268   // Copy Tmp to [Sh..W-1].  in rol()
269   for (uint16_t i = 0; i < W-Sh; ++i)  in rol()
270     Bits[i+Sh] = Tmp.Bits[i];  in rol()
278     Bits[B++] = V;  in fill()
284   // Bit 0 of RC becomes bit W of the result, where W is this->width().  in cat()
286   Bits.resize(W+WRC);  in cat()
288     Bits[i+W] = RC.Bits[i];  in cat()
296   while (C < W && Bits[C] == V)  in ct()
305   while (C < W && Bits[W-(C+1)] == V)  in cl()
311   uint16_t W = Bits.size();  in operator ==()
312   if (RC.Bits.size() != W)  in operator ==()
315     if (Bits[i] != RC[i])  in operator ==()
322     const BitValue &V = Bits[i];  in regify()
324       Bits[i].RefI = BitRef(R, i);  in regify()
367       return F->second;  in getCell()
369     return F->second.extract(M);  in getCell()
382   assert(RR.Sub == 0 && "Unexpected sub-register in definition");  in putCell()
383   // Eliminate all ref-to-reg-0 bit values: replace them with "self".  in putCell()
387 // Check if the cell represents a compile-time integer value.
409 // register cells that can be used to implement target-specific instructions
410 // in a target-specific evaluator.
414   // For bits beyond the 63rd, this will generate the sign bit of V.  in eIMM()
423   const APInt &A = CI->getValue();  in eIMM()
442     if (!V1.num() || !V2.num())  in eADD()
475     if (!V1.num() || !V2.num())  in eSUB()
477     unsigned S = bool(V1) - bool(V2) - Borrow;  in eSUB()
532   Res.rol(W-Sh);  in eLSR()
533   Res.fill(W-Sh, W, BitValue::Zero);  in eLSR()
542   BitValue Sign = Res[W-1];  in eASR()
543   Res.rol(W-Sh);  in eASR()
544   Res.fill(W-Sh, W, Sign);  in eASR()
646   // If the last leading non-B bit is not a constant, then we don't know  in eCLB()
648   if ((C < AW && A1[AW-1-C].num()) || C == AW)  in eCLB()
656   // If the last trailing non-B bit is not a constant, then we don't know  in eCTB()
658   if ((C < AW && A1[C].num()) || C == AW)  in eCTB()
668   BitValue Sign = Res[FromN-1];  in eSXT()
669   // Sign-extend "inreg".  in eSXT()
689   uint16_t Last = (E > 0) ? E-1 : W-1;  in eXTR()
700   // Copy bits from A1, insert A2 at position AtN.  in eINS()
703     Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1));  in eINS()
711   return BitMask(0, W-1);  in mask()
728       unsigned SS = MI.getOperand(2).getImm();  in evaluate()  local
731       assert(SS != ST);  in evaluate()
735       Res.insert(RegisterCell::ref(getCell(RS, Inputs)), mask(RD.Reg, SS));  in evaluate()
743       // If that is the case, fill the remaining high bits with 0.  in evaluate()
752       Res.insert(Src, BitMask(0, WS-1));  in evaluate()
773   const MachineBasicBlock *BA = InstA->getParent();  in operator ()()
774   const MachineBasicBlock *BB = InstB->getParent();  in operator ()()
778     return BA->getNumber() > BB->getNumber();  in operator ()()
784       return F->second;  in operator ()()
785     MachineBasicBlock::const_iterator I = MI->getParent()->begin();  in operator ()()
786     MachineBasicBlock::const_iterator E = MI->getIterator();  in operator ()()
795 // Main W-Z implementation.
798   int ThisN = PI.getParent()->getNumber();  in visitPHI()
803   assert(MD.getSubReg() == 0 && "Unexpected sub-register in definition");  in visitPHI()
815     int PredN = PB->getNumber();  in visitPHI()
817       dbgs() << "  edge " << printMBBReference(*PB) << "->"  in visitPHI()
875     assert(RD.Sub == 0 && "Unexpected sub-register in definition");  in visitNonBranch()
891       // This is a non-phi instruction, so the values of the inputs come  in visitNonBranch()
900         // Bits that are already "bottom" should not be updated.  in visitNonBranch()
963       if (SB->isEHPad())  in visitBranchesFrom()
978     FlowQ.push(CFGEdge(ThisN, TB->getNumber()));  in visitBranchesFrom()
998 // Replace all references to bits from OldRR with the corresponding bits
1007   assert((OME-OMB == NME-NMB) &&  in subst()
1018       V.RefI.Pos += NMB-OMB;  in subst()
1026   int BN = B->getNumber();  in reached()
1034   assert(!MI.isBranch() && "Only non-branches are allowed");  in visit()
1066     while (It != End && It->isPHI()) {  in runEdgeQueue()
1079     // Visit non-branch instructions.  in runEdgeQueue()
1080     while (It != End && !It->isBranch()) {  in runEdgeQueue()
1085     // If block end has been reached, add the fall-through edge to the queue.  in runEdgeQueue()
1091         int NextN = Next->getNumber();  in runEdgeQueue()
1099   } // while (!FlowQ->empty())  in runEdgeQueue()
1136   int EntryN = Entry->getNumber();  in run()
1138   FlowQ.push(CFGEdge(-1, EntryN));  in run()