1 //===--- BitTracker.cpp ---------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // SSA-based bit propagation.
12 // The purpose of this code is, for a given virtual register, to provide
13 // information about the value of each bit in the register. The values
14 // of bits are represented by the class BitValue, and take one of four
15 // cases: 0, 1, "ref" and "bottom". The 0 and 1 are rather clear, the
16 // "ref" value means that the bit is a copy of another bit (which itself
17 // cannot be a copy of yet another bit---such chains are not allowed).
18 // A "ref" value is associated with a BitRef structure, which indicates
19 // which virtual register, and which bit in that register is the origin
20 // of the value. For example, given an instruction
21 // vreg2 = ASL vreg1, 1
22 // assuming that nothing is known about bits of vreg1, bit 1 of vreg2
23 // will be a "ref" to (vreg1, 0). If there is a subsequent instruction
24 // vreg3 = ASL vreg2, 2
25 // then bit 3 of vreg3 will be a "ref" to (vreg1, 0) as well.
26 // The "bottom" case means that the bit's value cannot be determined,
27 // and that this virtual register actually defines it. The "bottom" case
28 // is discussed in detail in BitTracker.h. In fact, "bottom" is a "ref
29 // to self", so for the vreg1 above, the bit 0 of it will be a "ref" to
30 // (vreg1, 0), bit 1 will be a "ref" to (vreg1, 1), etc.
32 // The tracker implements the Wegman-Zadeck algorithm, originally developed
33 // for SSA-based constant propagation. Each register is represented as
34 // a sequence of bits, with the convention that bit 0 is the least signi-
35 // ficant bit. Each bit is propagated individually. The class RegisterCell
36 // implements the register's representation, and is also the subject of
37 // the lattice operations in the tracker.
39 // The intended usage of the bit tracker is to create a target-specific
40 // machine instruction evaluator, pass the evaluator to the BitTracker
41 // object, and run the tracker. The tracker will then collect the bit
42 // value information for a given machine function. After that, it can be
43 // queried for the cells for each virtual register.
45 // const TargetSpecificEvaluator TSE(TRI, MRI);
46 // BitTracker BT(TSE, MF);
49 // unsigned Reg = interestingRegister();
50 // RegisterCell RC = BT.get(Reg);
54 // The code below is intended to be fully target-independent.
56 #include "BitTracker.h"
57 #include "llvm/ADT/APInt.h"
58 #include "llvm/ADT/BitVector.h"
59 #include "llvm/CodeGen/MachineBasicBlock.h"
60 #include "llvm/CodeGen/MachineFunction.h"
61 #include "llvm/CodeGen/MachineInstr.h"
62 #include "llvm/CodeGen/MachineOperand.h"
63 #include "llvm/CodeGen/MachineRegisterInfo.h"
64 #include "llvm/IR/Constants.h"
65 #include "llvm/Support/Debug.h"
66 #include "llvm/Support/raw_ostream.h"
67 #include "llvm/Target/TargetRegisterInfo.h"
74 typedef BitTracker BT;
78 // Local trickery to pretty print a register (without the whole "%vreg"
81 printv(unsigned r) : R(r) {}
86 raw_ostream &operator<< (raw_ostream &OS, const printv &PV) {
88 OS << 'v' << TargetRegisterInfo::virtReg2Index(PV.R);
94 } // end anonymous namespace
98 raw_ostream &operator<<(raw_ostream &OS, const BT::BitValue &BV) {
100 case BT::BitValue::Top:
103 case BT::BitValue::Zero:
106 case BT::BitValue::One:
109 case BT::BitValue::Ref:
110 OS << printv(BV.RefI.Reg) << '[' << BV.RefI.Pos << ']';
116 raw_ostream &operator<<(raw_ostream &OS, const BT::RegisterCell &RC) {
117 unsigned n = RC.Bits.size();
119 // Instead of printing each bit value individually, try to group them
120 // into logical segments, such as sequences of 0 or 1 bits or references
121 // to consecutive bits (e.g. "bits 3-5 are same as bits 7-9 of reg xyz").
122 // "Start" will be the index of the beginning of the most recent segment.
124 bool SeqRef = false; // A sequence of refs to consecutive bits.
125 bool ConstRef = false; // A sequence of refs to the same bit.
127 for (unsigned i = 1, n = RC.Bits.size(); i < n; ++i) {
128 const BT::BitValue &V = RC[i];
129 const BT::BitValue &SV = RC[Start];
130 bool IsRef = (V.Type == BT::BitValue::Ref);
131 // If the current value is the same as Start, skip to the next one.
132 if (!IsRef && V == SV)
134 if (IsRef && SV.Type == BT::BitValue::Ref && V.RefI.Reg == SV.RefI.Reg) {
136 SeqRef = (V.RefI.Pos == SV.RefI.Pos+1);
137 ConstRef = (V.RefI.Pos == SV.RefI.Pos);
139 if (SeqRef && V.RefI.Pos == SV.RefI.Pos+(i-Start))
141 if (ConstRef && V.RefI.Pos == SV.RefI.Pos)
145 // The current value is different. Print the previous one and reset
148 unsigned Count = i - Start;
152 OS << '-' << i-1 << "]:";
153 if (SV.Type == BT::BitValue::Ref && SeqRef)
154 OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
155 << SV.RefI.Pos+(Count-1) << ']';
160 SeqRef = ConstRef = false;
164 unsigned Count = n - Start;
166 OS << "]:" << RC[Start];
168 OS << '-' << n-1 << "]:";
169 const BT::BitValue &SV = RC[Start];
170 if (SV.Type == BT::BitValue::Ref && SeqRef)
171 OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
172 << SV.RefI.Pos+(Count-1) << ']';
181 } // end namespace llvm
183 void BitTracker::print_cells(raw_ostream &OS) const {
184 for (CellMapType::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
185 dbgs() << PrintReg(I->first, &ME.TRI) << " -> " << I->second << "\n";
188 BitTracker::BitTracker(const MachineEvaluator &E, MachineFunction &F)
189 : Trace(false), ME(E), MF(F), MRI(F.getRegInfo()), Map(*new CellMapType) {}
191 BitTracker::~BitTracker() {
195 // If we were allowed to update a cell for a part of a register, the meet
196 // operation would need to be parametrized by the register number and the
197 // exact part of the register, so that the computer BitRefs correspond to
198 // the actual bits of the "self" register.
199 // While this cannot happen in the current implementation, I'm not sure
200 // if this should be ruled out in the future.
201 bool BT::RegisterCell::meet(const RegisterCell &RC, unsigned SelfR) {
202 // An example when "meet" can be invoked with SelfR == 0 is a phi node
203 // with a physical register as an operand.
204 assert(SelfR == 0 || TargetRegisterInfo::isVirtualRegister(SelfR));
205 bool Changed = false;
206 for (uint16_t i = 0, n = Bits.size(); i < n; ++i) {
207 const BitValue &RCV = RC[i];
208 Changed |= Bits[i].meet(RCV, BitRef(SelfR, i));
213 // Insert the entire cell RC into the current cell at position given by M.
214 BT::RegisterCell &BT::RegisterCell::insert(const BT::RegisterCell &RC,
216 uint16_t B = M.first(), E = M.last(), W = width();
217 // Sanity: M must be a valid mask for *this.
218 assert(B < W && E < W);
219 // Sanity: the masked part of *this must have the same number of bits
221 assert(B > E || E-B+1 == RC.width()); // B <= E => E-B+1 = |RC|.
222 assert(B <= E || E+(W-B)+1 == RC.width()); // E < B => E+(W-B)+1 = |RC|.
224 for (uint16_t i = 0; i <= E-B; ++i)
227 for (uint16_t i = 0; i < W-B; ++i)
229 for (uint16_t i = 0; i <= E; ++i)
230 Bits[i] = RC[i+(W-B)];
235 BT::RegisterCell BT::RegisterCell::extract(const BitMask &M) const {
236 uint16_t B = M.first(), E = M.last(), W = width();
237 assert(B < W && E < W);
239 RegisterCell RC(E-B+1);
240 for (uint16_t i = B; i <= E; ++i)
241 RC.Bits[i-B] = Bits[i];
245 RegisterCell RC(E+(W-B)+1);
246 for (uint16_t i = 0; i < W-B; ++i)
247 RC.Bits[i] = Bits[i+B];
248 for (uint16_t i = 0; i <= E; ++i)
249 RC.Bits[i+(W-B)] = Bits[i];
253 BT::RegisterCell &BT::RegisterCell::rol(uint16_t Sh) {
254 // Rotate left (i.e. towards increasing bit indices).
255 // Swap the two parts: [0..W-Sh-1] [W-Sh..W-1]
256 uint16_t W = width();
261 RegisterCell Tmp(W-Sh);
262 // Tmp = [0..W-Sh-1].
263 for (uint16_t i = 0; i < W-Sh; ++i)
265 // Shift [W-Sh..W-1] to [0..Sh-1].
266 for (uint16_t i = 0; i < Sh; ++i)
267 Bits[i] = Bits[W-Sh+i];
268 // Copy Tmp to [Sh..W-1].
269 for (uint16_t i = 0; i < W-Sh; ++i)
270 Bits[i+Sh] = Tmp.Bits[i];
274 BT::RegisterCell &BT::RegisterCell::fill(uint16_t B, uint16_t E,
282 BT::RegisterCell &BT::RegisterCell::cat(const RegisterCell &RC) {
283 // Append the cell given as the argument to the "this" cell.
284 // Bit 0 of RC becomes bit W of the result, where W is this->width().
285 uint16_t W = width(), WRC = RC.width();
287 for (uint16_t i = 0; i < WRC; ++i)
288 Bits[i+W] = RC.Bits[i];
292 uint16_t BT::RegisterCell::ct(bool B) const {
293 uint16_t W = width();
296 while (C < W && Bits[C] == V)
301 uint16_t BT::RegisterCell::cl(bool B) const {
302 uint16_t W = width();
305 while (C < W && Bits[W-(C+1)] == V)
310 bool BT::RegisterCell::operator== (const RegisterCell &RC) const {
311 uint16_t W = Bits.size();
312 if (RC.Bits.size() != W)
314 for (uint16_t i = 0; i < W; ++i)
315 if (Bits[i] != RC[i])
320 BT::RegisterCell &BT::RegisterCell::regify(unsigned R) {
321 for (unsigned i = 0, n = width(); i < n; ++i) {
322 const BitValue &V = Bits[i];
323 if (V.Type == BitValue::Ref && V.RefI.Reg == 0)
324 Bits[i].RefI = BitRef(R, i);
329 uint16_t BT::MachineEvaluator::getRegBitWidth(const RegisterRef &RR) const {
330 // The general problem is with finding a register class that corresponds
331 // to a given reference reg:sub. There can be several such classes, and
332 // since we only care about the register size, it does not matter which
333 // such class we would find.
334 // The easiest way to accomplish what we want is to
335 // 1. find a physical register PhysR from the same class as RR.Reg,
336 // 2. find a physical register PhysS that corresponds to PhysR:RR.Sub,
337 // 3. find a register class that contains PhysS.
339 if (TargetRegisterInfo::isVirtualRegister(RR.Reg)) {
340 const TargetRegisterClass *VC = MRI.getRegClass(RR.Reg);
341 assert(VC->begin() != VC->end() && "Empty register class");
342 PhysR = *VC->begin();
344 assert(TargetRegisterInfo::isPhysicalRegister(RR.Reg));
348 unsigned PhysS = (RR.Sub == 0) ? PhysR : TRI.getSubReg(PhysR, RR.Sub);
349 const TargetRegisterClass *RC = TRI.getMinimalPhysRegClass(PhysS);
350 uint16_t BW = TRI.getRegSizeInBits(*RC);
354 BT::RegisterCell BT::MachineEvaluator::getCell(const RegisterRef &RR,
355 const CellMapType &M) const {
356 uint16_t BW = getRegBitWidth(RR);
358 // Physical registers are assumed to be present in the map with an unknown
359 // value. Don't actually insert anything in the map, just return the cell.
360 if (TargetRegisterInfo::isPhysicalRegister(RR.Reg))
361 return RegisterCell::self(0, BW);
363 assert(TargetRegisterInfo::isVirtualRegister(RR.Reg));
364 // For virtual registers that belong to a class that is not tracked,
365 // generate an "unknown" value as well.
366 const TargetRegisterClass *C = MRI.getRegClass(RR.Reg);
368 return RegisterCell::self(0, BW);
370 CellMapType::const_iterator F = M.find(RR.Reg);
374 BitMask M = mask(RR.Reg, RR.Sub);
375 return F->second.extract(M);
377 // If not found, create a "top" entry, but do not insert it in the map.
378 return RegisterCell::top(BW);
381 void BT::MachineEvaluator::putCell(const RegisterRef &RR, RegisterCell RC,
382 CellMapType &M) const {
383 // While updating the cell map can be done in a meaningful way for
384 // a part of a register, it makes little sense to implement it as the
385 // SSA representation would never contain such "partial definitions".
386 if (!TargetRegisterInfo::isVirtualRegister(RR.Reg))
388 assert(RR.Sub == 0 && "Unexpected sub-register in definition");
389 // Eliminate all ref-to-reg-0 bit values: replace them with "self".
390 M[RR.Reg] = RC.regify(RR.Reg);
393 // Check if the cell represents a compile-time integer value.
394 bool BT::MachineEvaluator::isInt(const RegisterCell &A) const {
395 uint16_t W = A.width();
396 for (uint16_t i = 0; i < W; ++i)
397 if (!A[i].is(0) && !A[i].is(1))
402 // Convert a cell to the integer value. The result must fit in uint64_t.
403 uint64_t BT::MachineEvaluator::toInt(const RegisterCell &A) const {
406 uint16_t W = A.width();
407 for (uint16_t i = 0; i < W; ++i) {
414 // Evaluator helper functions. These implement some common operation on
415 // register cells that can be used to implement target-specific instructions
416 // in a target-specific evaluator.
418 BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const {
420 // For bits beyond the 63rd, this will generate the sign bit of V.
421 for (uint16_t i = 0; i < W; ++i) {
422 Res[i] = BitValue(V & 1);
428 BT::RegisterCell BT::MachineEvaluator::eIMM(const ConstantInt *CI) const {
429 const APInt &A = CI->getValue();
430 uint16_t BW = A.getBitWidth();
431 assert((unsigned)BW == A.getBitWidth() && "BitWidth overflow");
432 RegisterCell Res(BW);
433 for (uint16_t i = 0; i < BW; ++i)
438 BT::RegisterCell BT::MachineEvaluator::eADD(const RegisterCell &A1,
439 const RegisterCell &A2) const {
440 uint16_t W = A1.width();
441 assert(W == A2.width());
445 for (I = 0; I < W; ++I) {
446 const BitValue &V1 = A1[I];
447 const BitValue &V2 = A2[I];
448 if (!V1.num() || !V2.num())
450 unsigned S = bool(V1) + bool(V2) + Carry;
451 Res[I] = BitValue(S & 1);
455 const BitValue &V1 = A1[I];
456 const BitValue &V2 = A2[I];
457 // If the next bit is same as Carry, the result will be 0 plus the
458 // other bit. The Carry bit will remain unchanged.
460 Res[I] = BitValue::ref(V2);
461 else if (V2.is(Carry))
462 Res[I] = BitValue::ref(V1);
467 Res[I] = BitValue::self();
471 BT::RegisterCell BT::MachineEvaluator::eSUB(const RegisterCell &A1,
472 const RegisterCell &A2) const {
473 uint16_t W = A1.width();
474 assert(W == A2.width());
478 for (I = 0; I < W; ++I) {
479 const BitValue &V1 = A1[I];
480 const BitValue &V2 = A2[I];
481 if (!V1.num() || !V2.num())
483 unsigned S = bool(V1) - bool(V2) - Borrow;
484 Res[I] = BitValue(S & 1);
488 const BitValue &V1 = A1[I];
489 const BitValue &V2 = A2[I];
491 Res[I] = BitValue::ref(V2);
495 Res[I] = BitValue::ref(V1);
500 Res[I] = BitValue::self();
504 BT::RegisterCell BT::MachineEvaluator::eMLS(const RegisterCell &A1,
505 const RegisterCell &A2) const {
506 uint16_t W = A1.width() + A2.width();
507 uint16_t Z = A1.ct(false) + A2.ct(false);
509 Res.fill(0, Z, BitValue::Zero);
510 Res.fill(Z, W, BitValue::self());
514 BT::RegisterCell BT::MachineEvaluator::eMLU(const RegisterCell &A1,
515 const RegisterCell &A2) const {
516 uint16_t W = A1.width() + A2.width();
517 uint16_t Z = A1.ct(false) + A2.ct(false);
519 Res.fill(0, Z, BitValue::Zero);
520 Res.fill(Z, W, BitValue::self());
524 BT::RegisterCell BT::MachineEvaluator::eASL(const RegisterCell &A1,
526 assert(Sh <= A1.width());
527 RegisterCell Res = RegisterCell::ref(A1);
529 Res.fill(0, Sh, BitValue::Zero);
533 BT::RegisterCell BT::MachineEvaluator::eLSR(const RegisterCell &A1,
535 uint16_t W = A1.width();
537 RegisterCell Res = RegisterCell::ref(A1);
539 Res.fill(W-Sh, W, BitValue::Zero);
543 BT::RegisterCell BT::MachineEvaluator::eASR(const RegisterCell &A1,
545 uint16_t W = A1.width();
547 RegisterCell Res = RegisterCell::ref(A1);
548 BitValue Sign = Res[W-1];
550 Res.fill(W-Sh, W, Sign);
554 BT::RegisterCell BT::MachineEvaluator::eAND(const RegisterCell &A1,
555 const RegisterCell &A2) const {
556 uint16_t W = A1.width();
557 assert(W == A2.width());
559 for (uint16_t i = 0; i < W; ++i) {
560 const BitValue &V1 = A1[i];
561 const BitValue &V2 = A2[i];
563 Res[i] = BitValue::ref(V2);
565 Res[i] = BitValue::ref(V1);
566 else if (V1.is(0) || V2.is(0))
567 Res[i] = BitValue::Zero;
571 Res[i] = BitValue::self();
576 BT::RegisterCell BT::MachineEvaluator::eORL(const RegisterCell &A1,
577 const RegisterCell &A2) const {
578 uint16_t W = A1.width();
579 assert(W == A2.width());
581 for (uint16_t i = 0; i < W; ++i) {
582 const BitValue &V1 = A1[i];
583 const BitValue &V2 = A2[i];
584 if (V1.is(1) || V2.is(1))
585 Res[i] = BitValue::One;
587 Res[i] = BitValue::ref(V2);
589 Res[i] = BitValue::ref(V1);
593 Res[i] = BitValue::self();
598 BT::RegisterCell BT::MachineEvaluator::eXOR(const RegisterCell &A1,
599 const RegisterCell &A2) const {
600 uint16_t W = A1.width();
601 assert(W == A2.width());
603 for (uint16_t i = 0; i < W; ++i) {
604 const BitValue &V1 = A1[i];
605 const BitValue &V2 = A2[i];
607 Res[i] = BitValue::ref(V2);
609 Res[i] = BitValue::ref(V1);
611 Res[i] = BitValue::Zero;
613 Res[i] = BitValue::self();
618 BT::RegisterCell BT::MachineEvaluator::eNOT(const RegisterCell &A1) const {
619 uint16_t W = A1.width();
621 for (uint16_t i = 0; i < W; ++i) {
622 const BitValue &V = A1[i];
624 Res[i] = BitValue::One;
626 Res[i] = BitValue::Zero;
628 Res[i] = BitValue::self();
633 BT::RegisterCell BT::MachineEvaluator::eSET(const RegisterCell &A1,
634 uint16_t BitN) const {
635 assert(BitN < A1.width());
636 RegisterCell Res = RegisterCell::ref(A1);
637 Res[BitN] = BitValue::One;
641 BT::RegisterCell BT::MachineEvaluator::eCLR(const RegisterCell &A1,
642 uint16_t BitN) const {
643 assert(BitN < A1.width());
644 RegisterCell Res = RegisterCell::ref(A1);
645 Res[BitN] = BitValue::Zero;
649 BT::RegisterCell BT::MachineEvaluator::eCLB(const RegisterCell &A1, bool B,
651 uint16_t C = A1.cl(B), AW = A1.width();
652 // If the last leading non-B bit is not a constant, then we don't know
654 if ((C < AW && A1[AW-1-C].num()) || C == AW)
656 return RegisterCell::self(0, W);
659 BT::RegisterCell BT::MachineEvaluator::eCTB(const RegisterCell &A1, bool B,
661 uint16_t C = A1.ct(B), AW = A1.width();
662 // If the last trailing non-B bit is not a constant, then we don't know
664 if ((C < AW && A1[C].num()) || C == AW)
666 return RegisterCell::self(0, W);
669 BT::RegisterCell BT::MachineEvaluator::eSXT(const RegisterCell &A1,
670 uint16_t FromN) const {
671 uint16_t W = A1.width();
673 RegisterCell Res = RegisterCell::ref(A1);
674 BitValue Sign = Res[FromN-1];
675 // Sign-extend "inreg".
676 Res.fill(FromN, W, Sign);
680 BT::RegisterCell BT::MachineEvaluator::eZXT(const RegisterCell &A1,
681 uint16_t FromN) const {
682 uint16_t W = A1.width();
684 RegisterCell Res = RegisterCell::ref(A1);
685 Res.fill(FromN, W, BitValue::Zero);
689 BT::RegisterCell BT::MachineEvaluator::eXTR(const RegisterCell &A1,
690 uint16_t B, uint16_t E) const {
691 uint16_t W = A1.width();
692 assert(B < W && E <= W);
694 return RegisterCell(0);
695 uint16_t Last = (E > 0) ? E-1 : W-1;
696 RegisterCell Res = RegisterCell::ref(A1).extract(BT::BitMask(B, Last));
697 // Return shorter cell.
701 BT::RegisterCell BT::MachineEvaluator::eINS(const RegisterCell &A1,
702 const RegisterCell &A2, uint16_t AtN) const {
703 uint16_t W1 = A1.width(), W2 = A2.width();
705 assert(AtN < W1 && AtN+W2 <= W1);
706 // Copy bits from A1, insert A2 at position AtN.
707 RegisterCell Res = RegisterCell::ref(A1);
709 Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1));
713 BT::BitMask BT::MachineEvaluator::mask(unsigned Reg, unsigned Sub) const {
714 assert(Sub == 0 && "Generic BitTracker::mask called for Sub != 0");
715 uint16_t W = getRegBitWidth(Reg);
716 assert(W > 0 && "Cannot generate mask for empty register");
717 return BitMask(0, W-1);
720 bool BT::MachineEvaluator::evaluate(const MachineInstr &MI,
721 const CellMapType &Inputs,
722 CellMapType &Outputs) const {
723 unsigned Opc = MI.getOpcode();
725 case TargetOpcode::REG_SEQUENCE: {
726 RegisterRef RD = MI.getOperand(0);
728 RegisterRef RS = MI.getOperand(1);
729 unsigned SS = MI.getOperand(2).getImm();
730 RegisterRef RT = MI.getOperand(3);
731 unsigned ST = MI.getOperand(4).getImm();
734 uint16_t W = getRegBitWidth(RD);
736 Res.insert(RegisterCell::ref(getCell(RS, Inputs)), mask(RD.Reg, SS));
737 Res.insert(RegisterCell::ref(getCell(RT, Inputs)), mask(RD.Reg, ST));
738 putCell(RD, Res, Outputs);
742 case TargetOpcode::COPY: {
743 // COPY can transfer a smaller register into a wider one.
744 // If that is the case, fill the remaining high bits with 0.
745 RegisterRef RD = MI.getOperand(0);
746 RegisterRef RS = MI.getOperand(1);
748 uint16_t WD = getRegBitWidth(RD);
749 uint16_t WS = getRegBitWidth(RS);
751 RegisterCell Src = getCell(RS, Inputs);
752 RegisterCell Res(WD);
753 Res.insert(Src, BitMask(0, WS-1));
754 Res.fill(WS, WD, BitValue::Zero);
755 putCell(RD, Res, Outputs);
766 // Main W-Z implementation.
768 void BT::visitPHI(const MachineInstr &PI) {
769 int ThisN = PI.getParent()->getNumber();
771 dbgs() << "Visit FI(BB#" << ThisN << "): " << PI;
773 const MachineOperand &MD = PI.getOperand(0);
774 assert(MD.getSubReg() == 0 && "Unexpected sub-register in definition");
775 RegisterRef DefRR(MD);
776 uint16_t DefBW = ME.getRegBitWidth(DefRR);
778 RegisterCell DefC = ME.getCell(DefRR, Map);
779 if (DefC == RegisterCell::self(DefRR.Reg, DefBW)) // XXX slow
782 bool Changed = false;
784 for (unsigned i = 1, n = PI.getNumOperands(); i < n; i += 2) {
785 const MachineBasicBlock *PB = PI.getOperand(i + 1).getMBB();
786 int PredN = PB->getNumber();
788 dbgs() << " edge BB#" << PredN << "->BB#" << ThisN;
789 if (!EdgeExec.count(CFGEdge(PredN, ThisN))) {
791 dbgs() << " not executable\n";
795 RegisterRef RU = PI.getOperand(i);
796 RegisterCell ResC = ME.getCell(RU, Map);
798 dbgs() << " input reg: " << PrintReg(RU.Reg, &ME.TRI, RU.Sub)
799 << " cell: " << ResC << "\n";
800 Changed |= DefC.meet(ResC, DefRR.Reg);
805 dbgs() << "Output: " << PrintReg(DefRR.Reg, &ME.TRI, DefRR.Sub)
806 << " cell: " << DefC << "\n";
807 ME.putCell(DefRR, DefC, Map);
808 visitUsesOf(DefRR.Reg);
812 void BT::visitNonBranch(const MachineInstr &MI) {
814 int ThisN = MI.getParent()->getNumber();
815 dbgs() << "Visit MI(BB#" << ThisN << "): " << MI;
817 if (MI.isDebugValue())
819 assert(!MI.isBranch() && "Unexpected branch instruction");
822 bool Eval = ME.evaluate(MI, Map, ResMap);
825 for (unsigned i = 0, n = MI.getNumOperands(); i < n; ++i) {
826 const MachineOperand &MO = MI.getOperand(i);
827 if (!MO.isReg() || !MO.isUse())
830 dbgs() << " input reg: " << PrintReg(RU.Reg, &ME.TRI, RU.Sub)
831 << " cell: " << ME.getCell(RU, Map) << "\n";
833 dbgs() << "Outputs:\n";
834 for (CellMapType::iterator I = ResMap.begin(), E = ResMap.end();
836 RegisterRef RD(I->first);
837 dbgs() << " " << PrintReg(I->first, &ME.TRI) << " cell: "
838 << ME.getCell(RD, ResMap) << "\n";
842 // Iterate over all definitions of the instruction, and update the
843 // cells accordingly.
844 for (unsigned i = 0, n = MI.getNumOperands(); i < n; ++i) {
845 const MachineOperand &MO = MI.getOperand(i);
846 // Visit register defs only.
847 if (!MO.isReg() || !MO.isDef())
850 assert(RD.Sub == 0 && "Unexpected sub-register in definition");
851 if (!TargetRegisterInfo::isVirtualRegister(RD.Reg))
854 bool Changed = false;
855 if (!Eval || ResMap.count(RD.Reg) == 0) {
856 // Set to "ref" (aka "bottom").
857 uint16_t DefBW = ME.getRegBitWidth(RD);
858 RegisterCell RefC = RegisterCell::self(RD.Reg, DefBW);
859 if (RefC != ME.getCell(RD, Map)) {
860 ME.putCell(RD, RefC, Map);
864 RegisterCell DefC = ME.getCell(RD, Map);
865 RegisterCell ResC = ME.getCell(RD, ResMap);
866 // This is a non-phi instruction, so the values of the inputs come
867 // from the same registers each time this instruction is evaluated.
868 // During the propagation, the values of the inputs can become lowered
869 // in the sense of the lattice operation, which may cause different
870 // results to be calculated in subsequent evaluations. This should
871 // not cause the bottoming of the result in the map, since the new
872 // result is already reflecting the lowered inputs.
873 for (uint16_t i = 0, w = DefC.width(); i < w; ++i) {
874 BitValue &V = DefC[i];
875 // Bits that are already "bottom" should not be updated.
876 if (V.Type == BitValue::Ref && V.RefI.Reg == RD.Reg)
878 // Same for those that are identical in DefC and ResC.
885 ME.putCell(RD, DefC, Map);
892 void BT::visitBranchesFrom(const MachineInstr &BI) {
893 const MachineBasicBlock &B = *BI.getParent();
894 MachineBasicBlock::const_iterator It = BI, End = B.end();
895 BranchTargetList Targets, BTs;
896 bool FallsThrough = true, DefaultToAll = false;
897 int ThisN = B.getNumber();
901 const MachineInstr &MI = *It;
903 dbgs() << "Visit BR(BB#" << ThisN << "): " << MI;
904 assert(MI.isBranch() && "Expecting branch instruction");
905 InstrExec.insert(&MI);
906 bool Eval = ME.evaluate(MI, Map, BTs, FallsThrough);
908 // If the evaluation failed, we will add all targets. Keep going in
909 // the loop to mark all executable branches as such.
913 dbgs() << " failed to evaluate: will add all CFG successors\n";
914 } else if (!DefaultToAll) {
915 // If evaluated successfully add the targets to the cumulative list.
917 dbgs() << " adding targets:";
918 for (unsigned i = 0, n = BTs.size(); i < n; ++i)
919 dbgs() << " BB#" << BTs[i]->getNumber();
921 dbgs() << "\n falls through\n";
923 dbgs() << "\n does not fall through\n";
925 Targets.insert(BTs.begin(), BTs.end());
928 } while (FallsThrough && It != End);
930 typedef MachineBasicBlock::const_succ_iterator succ_iterator;
932 // Need to add all CFG successors that lead to EH landing pads.
933 // There won't be explicit branches to these blocks, but they must
935 for (succ_iterator I = B.succ_begin(), E = B.succ_end(); I != E; ++I) {
936 const MachineBasicBlock *SB = *I;
941 MachineFunction::const_iterator BIt = B.getIterator();
942 MachineFunction::const_iterator Next = std::next(BIt);
943 if (Next != MF.end())
944 Targets.insert(&*Next);
947 for (succ_iterator I = B.succ_begin(), E = B.succ_end(); I != E; ++I)
951 for (unsigned i = 0, n = Targets.size(); i < n; ++i) {
952 int TargetN = Targets[i]->getNumber();
953 FlowQ.push(CFGEdge(ThisN, TargetN));
957 void BT::visitUsesOf(unsigned Reg) {
959 dbgs() << "visiting uses of " << PrintReg(Reg, &ME.TRI) << "\n";
961 typedef MachineRegisterInfo::use_nodbg_iterator use_iterator;
962 use_iterator End = MRI.use_nodbg_end();
963 for (use_iterator I = MRI.use_nodbg_begin(Reg); I != End; ++I) {
964 MachineInstr *UseI = I->getParent();
965 if (!InstrExec.count(UseI))
969 else if (!UseI->isBranch())
970 visitNonBranch(*UseI);
972 visitBranchesFrom(*UseI);
976 BT::RegisterCell BT::get(RegisterRef RR) const {
977 return ME.getCell(RR, Map);
980 void BT::put(RegisterRef RR, const RegisterCell &RC) {
981 ME.putCell(RR, RC, Map);
984 // Replace all references to bits from OldRR with the corresponding bits
986 void BT::subst(RegisterRef OldRR, RegisterRef NewRR) {
987 assert(Map.count(OldRR.Reg) > 0 && "OldRR not present in map");
988 BitMask OM = ME.mask(OldRR.Reg, OldRR.Sub);
989 BitMask NM = ME.mask(NewRR.Reg, NewRR.Sub);
990 uint16_t OMB = OM.first(), OME = OM.last();
991 uint16_t NMB = NM.first(), NME = NM.last();
993 assert((OME-OMB == NME-NMB) &&
994 "Substituting registers of different lengths");
995 for (CellMapType::iterator I = Map.begin(), E = Map.end(); I != E; ++I) {
996 RegisterCell &RC = I->second;
997 for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
999 if (V.Type != BitValue::Ref || V.RefI.Reg != OldRR.Reg)
1001 if (V.RefI.Pos < OMB || V.RefI.Pos > OME)
1003 V.RefI.Reg = NewRR.Reg;
1004 V.RefI.Pos += NMB-OMB;
1009 // Check if the block has been "executed" during propagation. (If not, the
1010 // block is dead, but it may still appear to be reachable.)
1011 bool BT::reached(const MachineBasicBlock *B) const {
1012 int BN = B->getNumber();
1014 return ReachedBB.count(BN);
1017 // Visit an individual instruction. This could be a newly added instruction,
1018 // or one that has been modified by an optimization.
1019 void BT::visit(const MachineInstr &MI) {
1020 assert(!MI.isBranch() && "Only non-branches are allowed");
1021 InstrExec.insert(&MI);
1023 // The call to visitNonBranch could propagate the changes until a branch
1024 // is actually visited. This could result in adding CFG edges to the flow
1025 // queue. Since the queue won't be processed, clear it.
1026 while (!FlowQ.empty())
1035 ReachedBB.reserve(MF.size());
1040 assert(FlowQ.empty());
1042 typedef GraphTraits<const MachineFunction*> MachineFlowGraphTraits;
1043 const MachineBasicBlock *Entry = MachineFlowGraphTraits::getEntryNode(&MF);
1046 for (MachineFunction::const_iterator I = MF.begin(), E = MF.end();
1048 assert(I->getNumber() >= 0 && "Disconnected block");
1049 unsigned BN = I->getNumber();
1054 // Keep track of visited blocks.
1055 BitVector BlockScanned(MaxBN+1);
1057 int EntryN = Entry->getNumber();
1058 // Generate a fake edge to get something to start with.
1059 FlowQ.push(CFGEdge(-1, EntryN));
1061 while (!FlowQ.empty()) {
1062 CFGEdge Edge = FlowQ.front();
1065 if (EdgeExec.count(Edge))
1067 EdgeExec.insert(Edge);
1068 ReachedBB.insert(Edge.second);
1070 const MachineBasicBlock &B = *MF.getBlockNumbered(Edge.second);
1071 MachineBasicBlock::const_iterator It = B.begin(), End = B.end();
1072 // Visit PHI nodes first.
1073 while (It != End && It->isPHI()) {
1074 const MachineInstr &PI = *It++;
1075 InstrExec.insert(&PI);
1079 // If this block has already been visited through a flow graph edge,
1080 // then the instructions have already been processed. Any updates to
1081 // the cells would now only happen through visitUsesOf...
1082 if (BlockScanned[Edge.second])
1084 BlockScanned[Edge.second] = true;
1086 // Visit non-branch instructions.
1087 while (It != End && !It->isBranch()) {
1088 const MachineInstr &MI = *It++;
1089 InstrExec.insert(&MI);
1092 // If block end has been reached, add the fall-through edge to the queue.
1094 MachineFunction::const_iterator BIt = B.getIterator();
1095 MachineFunction::const_iterator Next = std::next(BIt);
1096 if (Next != MF.end() && B.isSuccessor(&*Next)) {
1097 int ThisN = B.getNumber();
1098 int NextN = Next->getNumber();
1099 FlowQ.push(CFGEdge(ThisN, NextN));
1102 // Handle the remaining sequence of branches. This function will update
1104 visitBranchesFrom(*It);
1106 } // while (!FlowQ->empty())
1109 print_cells(dbgs() << "Cells after propagation:\n");