Lines Matching +full:mi +full:- +full:v
1 //===- BitTracker.cpp -----------------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // SSA-based bit propagation.
16 // cannot be a copy of yet another bit---such chains are not allowed).
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.
87 OS << 'v' << Register::virtReg2Index(PV.R); in operator <<()
120 // to consecutive bits (e.g. "bits 3-5 are same as bits 7-9 of reg xyz"). in operator <<()
127 const BT::BitValue &V = RC[i]; in operator <<() local
129 bool IsRef = (V.Type == BT::BitValue::Ref); in operator <<()
131 if (!IsRef && V == SV) in operator <<()
133 if (IsRef && SV.Type == BT::BitValue::Ref && V.RefI.Reg == SV.RefI.Reg) { in operator <<()
135 SeqRef = (V.RefI.Pos == SV.RefI.Pos+1); in operator <<()
136 ConstRef = (V.RefI.Pos == SV.RefI.Pos); in operator <<()
138 if (SeqRef && V.RefI.Pos == SV.RefI.Pos+(i-Start)) in operator <<()
140 if (ConstRef && V.RefI.Pos == SV.RefI.Pos) 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()
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()
227 for (uint16_t i = 0; i < W-B; ++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()
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()
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()
275 const BitValue &V) { in fill() argument
278 Bits[B++] = V; in fill()
284 // Bit 0 of RC becomes bit W of the result, where W is this->width(). in cat()
295 BitValue V = B; in ct() local
296 while (C < W && Bits[C] == V) in ct()
304 BitValue V = B; in cl() local
305 while (C < W && Bits[W-(C+1)] == V) in cl()
322 const BitValue &V = Bits[i]; in regify() local
323 if (V.Type == BitValue::Ref && V.RefI.Reg == 0) 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.
412 BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const { in eIMM() argument
414 // For bits beyond the 63rd, this will generate the sign bit of V. in eIMM()
416 Res[i] = BitValue(V & 1); in eIMM()
417 V >>= 1; in eIMM()
423 const APInt &A = CI->getValue(); in eIMM()
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()
616 const BitValue &V = A1[i]; in eNOT() local
617 if (V.is(0)) in eNOT()
619 else if (V.is(1)) in eNOT()
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()
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()
703 Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1)); in eINS()
711 return BitMask(0, W-1); in mask()
719 bool BT::MachineEvaluator::evaluate(const MachineInstr &MI, in evaluate() argument
722 unsigned Opc = MI.getOpcode(); in evaluate()
725 RegisterRef RD = MI.getOperand(0); in evaluate()
727 RegisterRef RS = MI.getOperand(1); in evaluate()
728 unsigned SS = MI.getOperand(2).getImm(); in evaluate()
729 RegisterRef RT = MI.getOperand(3); in evaluate()
730 unsigned ST = MI.getOperand(4).getImm(); in evaluate()
744 RegisterRef RD = MI.getOperand(0); in evaluate()
745 RegisterRef RS = MI.getOperand(1); 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 ()()
781 auto getDist = [this] (const MachineInstr *MI) { in operator ()() argument
782 auto F = Dist.find(MI); 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 ()()
788 Dist.insert(std::make_pair(MI, D)); 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()
842 void BT::visitNonBranch(const MachineInstr &MI) { in visitNonBranch() argument
844 dbgs() << "Visit MI(" << printMBBReference(*MI.getParent()) << "): " << MI; in visitNonBranch()
845 if (MI.isDebugInstr()) in visitNonBranch()
847 assert(!MI.isBranch() && "Unexpected branch instruction"); in visitNonBranch()
850 bool Eval = ME.evaluate(MI, Map, ResMap); in visitNonBranch()
853 for (const MachineOperand &MO : MI.operands()) { in visitNonBranch()
870 for (const MachineOperand &MO : MI.operands()) { in visitNonBranch()
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()
899 BitValue &V = DefC[i]; in visitNonBranch() local
901 if (V.Type == BitValue::Ref && V.RefI.Reg == RD.Reg) in visitNonBranch()
904 if (V == ResC[i]) in visitNonBranch()
906 V = ResC[i]; in visitNonBranch()
926 const MachineInstr &MI = *It; in visitBranchesFrom() local
928 dbgs() << "Visit BR(" << printMBBReference(B) << "): " << MI; in visitBranchesFrom()
929 assert(MI.isBranch() && "Expecting branch instruction"); in visitBranchesFrom()
930 InstrExec.insert(&MI); in visitBranchesFrom()
931 bool Eval = ME.evaluate(MI, Map, BTs, FallsThrough); in visitBranchesFrom()
963 if (SB->isEHPad()) in visitBranchesFrom()
978 FlowQ.push(CFGEdge(ThisN, TB->getNumber())); in visitBranchesFrom()
1007 assert((OME-OMB == NME-NMB) && in subst()
1012 BitValue &V = RC[i]; in subst() local
1013 if (V.Type != BitValue::Ref || V.RefI.Reg != OldRR.Reg) in subst()
1015 if (V.RefI.Pos < OMB || V.RefI.Pos > OME) in subst()
1017 V.RefI.Reg = NewRR.Reg; in subst()
1018 V.RefI.Pos += NMB-OMB; in subst()
1026 int BN = B->getNumber(); in reached()
1033 void BT::visit(const MachineInstr &MI) { in visit() argument
1034 assert(!MI.isBranch() && "Only non-branches are allowed"); in visit()
1035 InstrExec.insert(&MI); in visit()
1036 visitNonBranch(MI); 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()
1081 const MachineInstr &MI = *It++; in runEdgeQueue() local
1082 InstrExec.insert(&MI); in runEdgeQueue()
1083 visitNonBranch(MI); 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()