//===--- BitTracker.cpp ---------------------------------------------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // SSA-based bit propagation. // // The purpose of this code is, for a given virtual register, to provide // information about the value of each bit in the register. The values // of bits are represented by the class BitValue, and take one of four // cases: 0, 1, "ref" and "bottom". The 0 and 1 are rather clear, the // "ref" value means that the bit is a copy of another bit (which itself // cannot be a copy of yet another bit---such chains are not allowed). // A "ref" value is associated with a BitRef structure, which indicates // which virtual register, and which bit in that register is the origin // of the value. For example, given an instruction // vreg2 = ASL vreg1, 1 // assuming that nothing is known about bits of vreg1, bit 1 of vreg2 // will be a "ref" to (vreg1, 0). If there is a subsequent instruction // vreg3 = ASL vreg2, 2 // then bit 3 of vreg3 will be a "ref" to (vreg1, 0) as well. // The "bottom" case means that the bit's value cannot be determined, // and that this virtual register actually defines it. The "bottom" case // is discussed in detail in BitTracker.h. In fact, "bottom" is a "ref // to self", so for the vreg1 above, the bit 0 of it will be a "ref" to // (vreg1, 0), bit 1 will be a "ref" to (vreg1, 1), etc. // // The tracker implements the Wegman-Zadeck algorithm, originally developed // for SSA-based constant propagation. Each register is represented as // a sequence of bits, with the convention that bit 0 is the least signi- // ficant bit. Each bit is propagated individually. The class RegisterCell // implements the register's representation, and is also the subject of // the lattice operations in the tracker. // // The intended usage of the bit tracker is to create a target-specific // machine instruction evaluator, pass the evaluator to the BitTracker // object, and run the tracker. The tracker will then collect the bit // value information for a given machine function. After that, it can be // queried for the cells for each virtual register. // Sample code: // const TargetSpecificEvaluator TSE(TRI, MRI); // BitTracker BT(TSE, MF); // BT.run(); // ... // unsigned Reg = interestingRegister(); // RegisterCell RC = BT.get(Reg); // if (RC[3].is(1)) // Reg0bit3 = 1; // // The code below is intended to be fully target-independent. #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/IR/Constants.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetRegisterInfo.h" #include "BitTracker.h" using namespace llvm; typedef BitTracker BT; namespace { // Local trickery to pretty print a register (without the whole "%vreg" // business). struct printv { printv(unsigned r) : R(r) {} unsigned R; }; raw_ostream &operator<< (raw_ostream &OS, const printv &PV) { if (PV.R) OS << 'v' << TargetRegisterInfo::virtReg2Index(PV.R); else OS << 's'; return OS; } } raw_ostream &llvm::operator<<(raw_ostream &OS, const BT::BitValue &BV) { switch (BV.Type) { case BT::BitValue::Top: OS << 'T'; break; case BT::BitValue::Zero: OS << '0'; break; case BT::BitValue::One: OS << '1'; break; case BT::BitValue::Ref: OS << printv(BV.RefI.Reg) << '[' << BV.RefI.Pos << ']'; break; } return OS; } raw_ostream &llvm::operator<<(raw_ostream &OS, const BT::RegisterCell &RC) { unsigned n = RC.Bits.size(); OS << "{ w:" << n; // Instead of printing each bit value individually, try to group them // into logical segments, such as sequences of 0 or 1 bits or references // to consecutive bits (e.g. "bits 3-5 are same as bits 7-9 of reg xyz"). // "Start" will be the index of the beginning of the most recent segment. unsigned Start = 0; bool SeqRef = false; // A sequence of refs to consecutive bits. bool ConstRef = false; // A sequence of refs to the same bit. for (unsigned i = 1, n = RC.Bits.size(); i < n; ++i) { const BT::BitValue &V = RC[i]; const BT::BitValue &SV = RC[Start]; bool IsRef = (V.Type == BT::BitValue::Ref); // If the current value is the same as Start, skip to the next one. if (!IsRef && V == SV) continue; if (IsRef && SV.Type == BT::BitValue::Ref && V.RefI.Reg == SV.RefI.Reg) { if (Start+1 == i) { SeqRef = (V.RefI.Pos == SV.RefI.Pos+1); ConstRef = (V.RefI.Pos == SV.RefI.Pos); } if (SeqRef && V.RefI.Pos == SV.RefI.Pos+(i-Start)) continue; if (ConstRef && V.RefI.Pos == SV.RefI.Pos) continue; } // The current value is different. Print the previous one and reset // the Start. OS << " [" << Start; unsigned Count = i - Start; if (Count == 1) { OS << "]:" << SV; } else { OS << '-' << i-1 << "]:"; if (SV.Type == BT::BitValue::Ref && SeqRef) OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-' << SV.RefI.Pos+(Count-1) << ']'; else OS << SV; } Start = i; SeqRef = ConstRef = false; } OS << " [" << Start; unsigned Count = n - Start; if (n-Start == 1) { OS << "]:" << RC[Start]; } else { OS << '-' << n-1 << "]:"; const BT::BitValue &SV = RC[Start]; if (SV.Type == BT::BitValue::Ref && SeqRef) OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-' << SV.RefI.Pos+(Count-1) << ']'; else OS << SV; } OS << " }"; return OS; } BitTracker::BitTracker(const MachineEvaluator &E, MachineFunction &F) : Trace(false), ME(E), MF(F), MRI(F.getRegInfo()), Map(*new CellMapType) {} BitTracker::~BitTracker() { delete ⤅ } // If we were allowed to update a cell for a part of a register, the meet // operation would need to be parametrized by the register number and the // exact part of the register, so that the computer BitRefs correspond to // the actual bits of the "self" register. // While this cannot happen in the current implementation, I'm not sure // if this should be ruled out in the future. bool BT::RegisterCell::meet(const RegisterCell &RC, unsigned SelfR) { // An example when "meet" can be invoked with SelfR == 0 is a phi node // with a physical register as an operand. assert(SelfR == 0 || TargetRegisterInfo::isVirtualRegister(SelfR)); bool Changed = false; for (uint16_t i = 0, n = Bits.size(); i < n; ++i) { const BitValue &RCV = RC[i]; Changed |= Bits[i].meet(RCV, BitRef(SelfR, i)); } return Changed; } // Insert the entire cell RC into the current cell at position given by M. BT::RegisterCell &BT::RegisterCell::insert(const BT::RegisterCell &RC, const BitMask &M) { uint16_t B = M.first(), E = M.last(), W = width(); // Sanity: M must be a valid mask for *this. assert(B < W && E < W); // Sanity: the masked part of *this must have the same number of bits // as the source. assert(B > E || E-B+1 == RC.width()); // B <= E => E-B+1 = |RC|. assert(B <= E || E+(W-B)+1 == RC.width()); // E < B => E+(W-B)+1 = |RC|. if (B <= E) { for (uint16_t i = 0; i <= E-B; ++i) Bits[i+B] = RC[i]; } else { for (uint16_t i = 0; i < W-B; ++i) Bits[i+B] = RC[i]; for (uint16_t i = 0; i <= E; ++i) Bits[i] = RC[i+(W-B)]; } return *this; } BT::RegisterCell BT::RegisterCell::extract(const BitMask &M) const { uint16_t B = M.first(), E = M.last(), W = width(); assert(B < W && E < W); if (B <= E) { RegisterCell RC(E-B+1); for (uint16_t i = B; i <= E; ++i) RC.Bits[i-B] = Bits[i]; return RC; } RegisterCell RC(E+(W-B)+1); for (uint16_t i = 0; i < W-B; ++i) RC.Bits[i] = Bits[i+B]; for (uint16_t i = 0; i <= E; ++i) RC.Bits[i+(W-B)] = Bits[i]; return RC; } BT::RegisterCell &BT::RegisterCell::rol(uint16_t Sh) { // Rotate left (i.e. towards increasing bit indices). // Swap the two parts: [0..W-Sh-1] [W-Sh..W-1] uint16_t W = width(); Sh = Sh % W; if (Sh == 0) return *this; RegisterCell Tmp(W-Sh); // Tmp = [0..W-Sh-1]. for (uint16_t i = 0; i < W-Sh; ++i) Tmp[i] = Bits[i]; // Shift [W-Sh..W-1] to [0..Sh-1]. for (uint16_t i = 0; i < Sh; ++i) Bits[i] = Bits[W-Sh+i]; // Copy Tmp to [Sh..W-1]. for (uint16_t i = 0; i < W-Sh; ++i) Bits[i+Sh] = Tmp.Bits[i]; return *this; } BT::RegisterCell &BT::RegisterCell::fill(uint16_t B, uint16_t E, const BitValue &V) { assert(B <= E); while (B < E) Bits[B++] = V; return *this; } BT::RegisterCell &BT::RegisterCell::cat(const RegisterCell &RC) { // Append the cell given as the argument to the "this" cell. // Bit 0 of RC becomes bit W of the result, where W is this->width(). uint16_t W = width(), WRC = RC.width(); Bits.resize(W+WRC); for (uint16_t i = 0; i < WRC; ++i) Bits[i+W] = RC.Bits[i]; return *this; } uint16_t BT::RegisterCell::ct(bool B) const { uint16_t W = width(); uint16_t C = 0; BitValue V = B; while (C < W && Bits[C] == V) C++; return C; } uint16_t BT::RegisterCell::cl(bool B) const { uint16_t W = width(); uint16_t C = 0; BitValue V = B; while (C < W && Bits[W-(C+1)] == V) C++; return C; } bool BT::RegisterCell::operator== (const RegisterCell &RC) const { uint16_t W = Bits.size(); if (RC.Bits.size() != W) return false; for (uint16_t i = 0; i < W; ++i) if (Bits[i] != RC[i]) return false; return true; } uint16_t BT::MachineEvaluator::getRegBitWidth(const RegisterRef &RR) const { // The general problem is with finding a register class that corresponds // to a given reference reg:sub. There can be several such classes, and // since we only care about the register size, it does not matter which // such class we would find. // The easiest way to accomplish what we want is to // 1. find a physical register PhysR from the same class as RR.Reg, // 2. find a physical register PhysS that corresponds to PhysR:RR.Sub, // 3. find a register class that contains PhysS. unsigned PhysR; if (TargetRegisterInfo::isVirtualRegister(RR.Reg)) { const TargetRegisterClass *VC = MRI.getRegClass(RR.Reg); assert(VC->begin() != VC->end() && "Empty register class"); PhysR = *VC->begin(); } else { assert(TargetRegisterInfo::isPhysicalRegister(RR.Reg)); PhysR = RR.Reg; } unsigned PhysS = (RR.Sub == 0) ? PhysR : TRI.getSubReg(PhysR, RR.Sub); const TargetRegisterClass *RC = TRI.getMinimalPhysRegClass(PhysS); uint16_t BW = RC->getSize()*8; return BW; } BT::RegisterCell BT::MachineEvaluator::getCell(const RegisterRef &RR, const CellMapType &M) const { uint16_t BW = getRegBitWidth(RR); // Physical registers are assumed to be present in the map with an unknown // value. Don't actually insert anything in the map, just return the cell. if (TargetRegisterInfo::isPhysicalRegister(RR.Reg)) return RegisterCell::self(0, BW); assert(TargetRegisterInfo::isVirtualRegister(RR.Reg)); // For virtual registers that belong to a class that is not tracked, // generate an "unknown" value as well. const TargetRegisterClass *C = MRI.getRegClass(RR.Reg); if (!track(C)) return RegisterCell::self(0, BW); CellMapType::const_iterator F = M.find(RR.Reg); if (F != M.end()) { if (!RR.Sub) return F->second; BitMask M = mask(RR.Reg, RR.Sub); return F->second.extract(M); } // If not found, create a "top" entry, but do not insert it in the map. return RegisterCell::top(BW); } void BT::MachineEvaluator::putCell(const RegisterRef &RR, RegisterCell RC, CellMapType &M) const { // While updating the cell map can be done in a meaningful way for // a part of a register, it makes little sense to implement it as the // SSA representation would never contain such "partial definitions". if (!TargetRegisterInfo::isVirtualRegister(RR.Reg)) return; assert(RR.Sub == 0 && "Unexpected sub-register in definition"); // Eliminate all ref-to-reg-0 bit values: replace them with "self". for (unsigned i = 0, n = RC.width(); i < n; ++i) { const BitValue &V = RC[i]; if (V.Type == BitValue::Ref && V.RefI.Reg == 0) RC[i].RefI = BitRef(RR.Reg, i); } M[RR.Reg] = RC; } // Check if the cell represents a compile-time integer value. bool BT::MachineEvaluator::isInt(const RegisterCell &A) const { uint16_t W = A.width(); for (uint16_t i = 0; i < W; ++i) if (!A[i].is(0) && !A[i].is(1)) return false; return true; } // Convert a cell to the integer value. The result must fit in uint64_t. uint64_t BT::MachineEvaluator::toInt(const RegisterCell &A) const { assert(isInt(A)); uint64_t Val = 0; uint16_t W = A.width(); for (uint16_t i = 0; i < W; ++i) { Val <<= 1; Val |= A[i].is(1); } return Val; } // Evaluator helper functions. These implement some common operation on // register cells that can be used to implement target-specific instructions // in a target-specific evaluator. BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const { RegisterCell Res(W); // For bits beyond the 63rd, this will generate the sign bit of V. for (uint16_t i = 0; i < W; ++i) { Res[i] = BitValue(V & 1); V >>= 1; } return Res; } BT::RegisterCell BT::MachineEvaluator::eIMM(const ConstantInt *CI) const { APInt A = CI->getValue(); uint16_t BW = A.getBitWidth(); assert((unsigned)BW == A.getBitWidth() && "BitWidth overflow"); RegisterCell Res(BW); for (uint16_t i = 0; i < BW; ++i) Res[i] = A[i]; return Res; } BT::RegisterCell BT::MachineEvaluator::eADD(const RegisterCell &A1, const RegisterCell &A2) const { uint16_t W = A1.width(); assert(W == A2.width()); RegisterCell Res(W); bool Carry = false; uint16_t I; for (I = 0; I < W; ++I) { const BitValue &V1 = A1[I]; const BitValue &V2 = A2[I]; if (!V1.num() || !V2.num()) break; unsigned S = bool(V1) + bool(V2) + Carry; Res[I] = BitValue(S & 1); Carry = (S > 1); } for (; I < W; ++I) { const BitValue &V1 = A1[I]; const BitValue &V2 = A2[I]; // If the next bit is same as Carry, the result will be 0 plus the // other bit. The Carry bit will remain unchanged. if (V1.is(Carry)) Res[I] = BitValue::ref(V2); else if (V2.is(Carry)) Res[I] = BitValue::ref(V1); else break; } for (; I < W; ++I) Res[I] = BitValue::self(); return Res; } BT::RegisterCell BT::MachineEvaluator::eSUB(const RegisterCell &A1, const RegisterCell &A2) const { uint16_t W = A1.width(); assert(W == A2.width()); RegisterCell Res(W); bool Borrow = false; uint16_t I; for (I = 0; I < W; ++I) { const BitValue &V1 = A1[I]; const BitValue &V2 = A2[I]; if (!V1.num() || !V2.num()) break; unsigned S = bool(V1) - bool(V2) - Borrow; Res[I] = BitValue(S & 1); Borrow = (S > 1); } for (; I < W; ++I) { const BitValue &V1 = A1[I]; const BitValue &V2 = A2[I]; if (V1.is(Borrow)) { Res[I] = BitValue::ref(V2); break; } if (V2.is(Borrow)) Res[I] = BitValue::ref(V1); else break; } for (; I < W; ++I) Res[I] = BitValue::self(); return Res; } BT::RegisterCell BT::MachineEvaluator::eMLS(const RegisterCell &A1, const RegisterCell &A2) const { uint16_t W = A1.width() + A2.width(); uint16_t Z = A1.ct(0) + A2.ct(0); RegisterCell Res(W); Res.fill(0, Z, BitValue::Zero); Res.fill(Z, W, BitValue::self()); return Res; } BT::RegisterCell BT::MachineEvaluator::eMLU(const RegisterCell &A1, const RegisterCell &A2) const { uint16_t W = A1.width() + A2.width(); uint16_t Z = A1.ct(0) + A2.ct(0); RegisterCell Res(W); Res.fill(0, Z, BitValue::Zero); Res.fill(Z, W, BitValue::self()); return Res; } BT::RegisterCell BT::MachineEvaluator::eASL(const RegisterCell &A1, uint16_t Sh) const { assert(Sh <= A1.width()); RegisterCell Res = RegisterCell::ref(A1); Res.rol(Sh); Res.fill(0, Sh, BitValue::Zero); return Res; } BT::RegisterCell BT::MachineEvaluator::eLSR(const RegisterCell &A1, uint16_t Sh) const { uint16_t W = A1.width(); assert(Sh <= W); RegisterCell Res = RegisterCell::ref(A1); Res.rol(W-Sh); Res.fill(W-Sh, W, BitValue::Zero); return Res; } BT::RegisterCell BT::MachineEvaluator::eASR(const RegisterCell &A1, uint16_t Sh) const { uint16_t W = A1.width(); assert(Sh <= W); RegisterCell Res = RegisterCell::ref(A1); BitValue Sign = Res[W-1]; Res.rol(W-Sh); Res.fill(W-Sh, W, Sign); return Res; } BT::RegisterCell BT::MachineEvaluator::eAND(const RegisterCell &A1, const RegisterCell &A2) const { uint16_t W = A1.width(); assert(W == A2.width()); RegisterCell Res(W); for (uint16_t i = 0; i < W; ++i) { const BitValue &V1 = A1[i]; const BitValue &V2 = A2[i]; if (V1.is(1)) Res[i] = BitValue::ref(V2); else if (V2.is(1)) Res[i] = BitValue::ref(V1); else if (V1.is(0) || V2.is(0)) Res[i] = BitValue::Zero; else if (V1 == V2) Res[i] = V1; else Res[i] = BitValue::self(); } return Res; } BT::RegisterCell BT::MachineEvaluator::eORL(const RegisterCell &A1, const RegisterCell &A2) const { uint16_t W = A1.width(); assert(W == A2.width()); RegisterCell Res(W); for (uint16_t i = 0; i < W; ++i) { const BitValue &V1 = A1[i]; const BitValue &V2 = A2[i]; if (V1.is(1) || V2.is(1)) Res[i] = BitValue::One; else if (V1.is(0)) Res[i] = BitValue::ref(V2); else if (V2.is(0)) Res[i] = BitValue::ref(V1); else if (V1 == V2) Res[i] = V1; else Res[i] = BitValue::self(); } return Res; } BT::RegisterCell BT::MachineEvaluator::eXOR(const RegisterCell &A1, const RegisterCell &A2) const { uint16_t W = A1.width(); assert(W == A2.width()); RegisterCell Res(W); for (uint16_t i = 0; i < W; ++i) { const BitValue &V1 = A1[i]; const BitValue &V2 = A2[i]; if (V1.is(0)) Res[i] = BitValue::ref(V2); else if (V2.is(0)) Res[i] = BitValue::ref(V1); else if (V1 == V2) Res[i] = BitValue::Zero; else Res[i] = BitValue::self(); } return Res; } BT::RegisterCell BT::MachineEvaluator::eNOT(const RegisterCell &A1) const { uint16_t W = A1.width(); RegisterCell Res(W); for (uint16_t i = 0; i < W; ++i) { const BitValue &V = A1[i]; if (V.is(0)) Res[i] = BitValue::One; else if (V.is(1)) Res[i] = BitValue::Zero; else Res[i] = BitValue::self(); } return Res; } BT::RegisterCell BT::MachineEvaluator::eSET(const RegisterCell &A1, uint16_t BitN) const { assert(BitN < A1.width()); RegisterCell Res = RegisterCell::ref(A1); Res[BitN] = BitValue::One; return Res; } BT::RegisterCell BT::MachineEvaluator::eCLR(const RegisterCell &A1, uint16_t BitN) const { assert(BitN < A1.width()); RegisterCell Res = RegisterCell::ref(A1); Res[BitN] = BitValue::Zero; return Res; } BT::RegisterCell BT::MachineEvaluator::eCLB(const RegisterCell &A1, bool B, uint16_t W) const { uint16_t C = A1.cl(B), AW = A1.width(); // If the last leading non-B bit is not a constant, then we don't know // the real count. if ((C < AW && A1[AW-1-C].num()) || C == AW) return eIMM(C, W); return RegisterCell::self(0, W); } BT::RegisterCell BT::MachineEvaluator::eCTB(const RegisterCell &A1, bool B, uint16_t W) const { uint16_t C = A1.ct(B), AW = A1.width(); // If the last trailing non-B bit is not a constant, then we don't know // the real count. if ((C < AW && A1[C].num()) || C == AW) return eIMM(C, W); return RegisterCell::self(0, W); } BT::RegisterCell BT::MachineEvaluator::eSXT(const RegisterCell &A1, uint16_t FromN) const { uint16_t W = A1.width(); assert(FromN <= W); RegisterCell Res = RegisterCell::ref(A1); BitValue Sign = Res[FromN-1]; // Sign-extend "inreg". Res.fill(FromN, W, Sign); return Res; } BT::RegisterCell BT::MachineEvaluator::eZXT(const RegisterCell &A1, uint16_t FromN) const { uint16_t W = A1.width(); assert(FromN <= W); RegisterCell Res = RegisterCell::ref(A1); Res.fill(FromN, W, BitValue::Zero); return Res; } BT::RegisterCell BT::MachineEvaluator::eXTR(const RegisterCell &A1, uint16_t B, uint16_t E) const { uint16_t W = A1.width(); assert(B < W && E <= W); if (B == E) return RegisterCell(0); uint16_t Last = (E > 0) ? E-1 : W-1; RegisterCell Res = RegisterCell::ref(A1).extract(BT::BitMask(B, Last)); // Return shorter cell. return Res; } BT::RegisterCell BT::MachineEvaluator::eINS(const RegisterCell &A1, const RegisterCell &A2, uint16_t AtN) const { uint16_t W1 = A1.width(), W2 = A2.width(); (void)W1; assert(AtN < W1 && AtN+W2 <= W1); // Copy bits from A1, insert A2 at position AtN. RegisterCell Res = RegisterCell::ref(A1); if (W2 > 0) Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1)); return Res; } BT::BitMask BT::MachineEvaluator::mask(unsigned Reg, unsigned Sub) const { assert(Sub == 0 && "Generic BitTracker::mask called for Sub != 0"); uint16_t W = getRegBitWidth(Reg); assert(W > 0 && "Cannot generate mask for empty register"); return BitMask(0, W-1); } bool BT::MachineEvaluator::evaluate(const MachineInstr *MI, const CellMapType &Inputs, CellMapType &Outputs) const { unsigned Opc = MI->getOpcode(); switch (Opc) { case TargetOpcode::REG_SEQUENCE: { RegisterRef RD = MI->getOperand(0); assert(RD.Sub == 0); RegisterRef RS = MI->getOperand(1); unsigned SS = MI->getOperand(2).getImm(); RegisterRef RT = MI->getOperand(3); unsigned ST = MI->getOperand(4).getImm(); assert(SS != ST); uint16_t W = getRegBitWidth(RD); RegisterCell Res(W); Res.insert(RegisterCell::ref(getCell(RS, Inputs)), mask(RD.Reg, SS)); Res.insert(RegisterCell::ref(getCell(RT, Inputs)), mask(RD.Reg, ST)); putCell(RD, Res, Outputs); break; } case TargetOpcode::COPY: { // COPY can transfer a smaller register into a wider one. // If that is the case, fill the remaining high bits with 0. RegisterRef RD = MI->getOperand(0); RegisterRef RS = MI->getOperand(1); assert(RD.Sub == 0); uint16_t WD = getRegBitWidth(RD); uint16_t WS = getRegBitWidth(RS); assert(WD >= WS); RegisterCell Src = getCell(RS, Inputs); RegisterCell Res(WD); Res.insert(Src, BitMask(0, WS-1)); Res.fill(WS, WD, BitValue::Zero); putCell(RD, Res, Outputs); break; } default: return false; } return true; } // Main W-Z implementation. void BT::visitPHI(const MachineInstr *PI) { int ThisN = PI->getParent()->getNumber(); if (Trace) dbgs() << "Visit FI(BB#" << ThisN << "): " << *PI; const MachineOperand &MD = PI->getOperand(0); assert(MD.getSubReg() == 0 && "Unexpected sub-register in definition"); RegisterRef DefRR(MD); uint16_t DefBW = ME.getRegBitWidth(DefRR); RegisterCell DefC = ME.getCell(DefRR, Map); if (DefC == RegisterCell::self(DefRR.Reg, DefBW)) // XXX slow return; bool Changed = false; for (unsigned i = 1, n = PI->getNumOperands(); i < n; i += 2) { const MachineBasicBlock *PB = PI->getOperand(i+1).getMBB(); int PredN = PB->getNumber(); if (Trace) dbgs() << " edge BB#" << PredN << "->BB#" << ThisN; if (!EdgeExec.count(CFGEdge(PredN, ThisN))) { if (Trace) dbgs() << " not executable\n"; continue; } RegisterRef RU = PI->getOperand(i); RegisterCell ResC = ME.getCell(RU, Map); if (Trace) dbgs() << " input reg: " << PrintReg(RU.Reg, &ME.TRI, RU.Sub) << " cell: " << ResC << "\n"; Changed |= DefC.meet(ResC, DefRR.Reg); } if (Changed) { if (Trace) dbgs() << "Output: " << PrintReg(DefRR.Reg, &ME.TRI, DefRR.Sub) << " cell: " << DefC << "\n"; ME.putCell(DefRR, DefC, Map); visitUsesOf(DefRR.Reg); } } void BT::visitNonBranch(const MachineInstr *MI) { if (Trace) { int ThisN = MI->getParent()->getNumber(); dbgs() << "Visit MI(BB#" << ThisN << "): " << *MI; } if (MI->isDebugValue()) return; assert(!MI->isBranch() && "Unexpected branch instruction"); CellMapType ResMap; bool Eval = ME.evaluate(MI, Map, ResMap); if (Trace && Eval) { for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) { const MachineOperand &MO = MI->getOperand(i); if (!MO.isReg() || !MO.isUse()) continue; RegisterRef RU(MO); dbgs() << " input reg: " << PrintReg(RU.Reg, &ME.TRI, RU.Sub) << " cell: " << ME.getCell(RU, Map) << "\n"; } dbgs() << "Outputs:\n"; for (CellMapType::iterator I = ResMap.begin(), E = ResMap.end(); I != E; ++I) { RegisterRef RD(I->first); dbgs() << " " << PrintReg(I->first, &ME.TRI) << " cell: " << ME.getCell(RD, ResMap) << "\n"; } } // Iterate over all definitions of the instruction, and update the // cells accordingly. for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) { const MachineOperand &MO = MI->getOperand(i); // Visit register defs only. if (!MO.isReg() || !MO.isDef()) continue; RegisterRef RD(MO); assert(RD.Sub == 0 && "Unexpected sub-register in definition"); if (!TargetRegisterInfo::isVirtualRegister(RD.Reg)) continue; bool Changed = false; if (!Eval || ResMap.count(RD.Reg) == 0) { // Set to "ref" (aka "bottom"). uint16_t DefBW = ME.getRegBitWidth(RD); RegisterCell RefC = RegisterCell::self(RD.Reg, DefBW); if (RefC != ME.getCell(RD, Map)) { ME.putCell(RD, RefC, Map); Changed = true; } } else { RegisterCell DefC = ME.getCell(RD, Map); RegisterCell ResC = ME.getCell(RD, ResMap); // This is a non-phi instruction, so the values of the inputs come // from the same registers each time this instruction is evaluated. // During the propagation, the values of the inputs can become lowered // in the sense of the lattice operation, which may cause different // results to be calculated in subsequent evaluations. This should // not cause the bottoming of the result in the map, since the new // result is already reflecting the lowered inputs. for (uint16_t i = 0, w = DefC.width(); i < w; ++i) { BitValue &V = DefC[i]; // Bits that are already "bottom" should not be updated. if (V.Type == BitValue::Ref && V.RefI.Reg == RD.Reg) continue; // Same for those that are identical in DefC and ResC. if (V == ResC[i]) continue; V = ResC[i]; Changed = true; } if (Changed) ME.putCell(RD, DefC, Map); } if (Changed) visitUsesOf(RD.Reg); } } void BT::visitBranchesFrom(const MachineInstr *BI) { const MachineBasicBlock &B = *BI->getParent(); MachineBasicBlock::const_iterator It = BI, End = B.end(); BranchTargetList Targets, BTs; bool FallsThrough = true, DefaultToAll = false; int ThisN = B.getNumber(); do { BTs.clear(); const MachineInstr *MI = &*It; if (Trace) dbgs() << "Visit BR(BB#" << ThisN << "): " << *MI; assert(MI->isBranch() && "Expecting branch instruction"); InstrExec.insert(MI); bool Eval = ME.evaluate(MI, Map, BTs, FallsThrough); if (!Eval) { // If the evaluation failed, we will add all targets. Keep going in // the loop to mark all executable branches as such. DefaultToAll = true; FallsThrough = true; if (Trace) dbgs() << " failed to evaluate: will add all CFG successors\n"; } else if (!DefaultToAll) { // If evaluated successfully add the targets to the cumulative list. if (Trace) { dbgs() << " adding targets:"; for (unsigned i = 0, n = BTs.size(); i < n; ++i) dbgs() << " BB#" << BTs[i]->getNumber(); if (FallsThrough) dbgs() << "\n falls through\n"; else dbgs() << "\n does not fall through\n"; } Targets.insert(BTs.begin(), BTs.end()); } ++It; } while (FallsThrough && It != End); typedef MachineBasicBlock::const_succ_iterator succ_iterator; if (!DefaultToAll) { // Need to add all CFG successors that lead to EH landing pads. // There won't be explicit branches to these blocks, but they must // be processed. for (succ_iterator I = B.succ_begin(), E = B.succ_end(); I != E; ++I) { const MachineBasicBlock *SB = *I; if (SB->isEHPad()) Targets.insert(SB); } if (FallsThrough) { MachineFunction::const_iterator BIt = B.getIterator(); MachineFunction::const_iterator Next = std::next(BIt); if (Next != MF.end()) Targets.insert(&*Next); } } else { for (succ_iterator I = B.succ_begin(), E = B.succ_end(); I != E; ++I) Targets.insert(*I); } for (unsigned i = 0, n = Targets.size(); i < n; ++i) { int TargetN = Targets[i]->getNumber(); FlowQ.push(CFGEdge(ThisN, TargetN)); } } void BT::visitUsesOf(unsigned Reg) { if (Trace) dbgs() << "visiting uses of " << PrintReg(Reg, &ME.TRI) << "\n"; typedef MachineRegisterInfo::use_nodbg_iterator use_iterator; use_iterator End = MRI.use_nodbg_end(); for (use_iterator I = MRI.use_nodbg_begin(Reg); I != End; ++I) { MachineInstr *UseI = I->getParent(); if (!InstrExec.count(UseI)) continue; if (UseI->isPHI()) visitPHI(UseI); else if (!UseI->isBranch()) visitNonBranch(UseI); else visitBranchesFrom(UseI); } } BT::RegisterCell BT::get(RegisterRef RR) const { return ME.getCell(RR, Map); } void BT::put(RegisterRef RR, const RegisterCell &RC) { ME.putCell(RR, RC, Map); } // Replace all references to bits from OldRR with the corresponding bits // in NewRR. void BT::subst(RegisterRef OldRR, RegisterRef NewRR) { assert(Map.count(OldRR.Reg) > 0 && "OldRR not present in map"); BitMask OM = ME.mask(OldRR.Reg, OldRR.Sub); BitMask NM = ME.mask(NewRR.Reg, NewRR.Sub); uint16_t OMB = OM.first(), OME = OM.last(); uint16_t NMB = NM.first(), NME = NM.last(); (void)NME; assert((OME-OMB == NME-NMB) && "Substituting registers of different lengths"); for (CellMapType::iterator I = Map.begin(), E = Map.end(); I != E; ++I) { RegisterCell &RC = I->second; for (uint16_t i = 0, w = RC.width(); i < w; ++i) { BitValue &V = RC[i]; if (V.Type != BitValue::Ref || V.RefI.Reg != OldRR.Reg) continue; if (V.RefI.Pos < OMB || V.RefI.Pos > OME) continue; V.RefI.Reg = NewRR.Reg; V.RefI.Pos += NMB-OMB; } } } // Check if the block has been "executed" during propagation. (If not, the // block is dead, but it may still appear to be reachable.) bool BT::reached(const MachineBasicBlock *B) const { int BN = B->getNumber(); assert(BN >= 0); for (EdgeSetType::iterator I = EdgeExec.begin(), E = EdgeExec.end(); I != E; ++I) { if (I->second == BN) return true; } return false; } void BT::reset() { EdgeExec.clear(); InstrExec.clear(); Map.clear(); } void BT::run() { reset(); assert(FlowQ.empty()); typedef GraphTraits<const MachineFunction*> MachineFlowGraphTraits; const MachineBasicBlock *Entry = MachineFlowGraphTraits::getEntryNode(&MF); unsigned MaxBN = 0; for (MachineFunction::const_iterator I = MF.begin(), E = MF.end(); I != E; ++I) { assert(I->getNumber() >= 0 && "Disconnected block"); unsigned BN = I->getNumber(); if (BN > MaxBN) MaxBN = BN; } // Keep track of visited blocks. BitVector BlockScanned(MaxBN+1); int EntryN = Entry->getNumber(); // Generate a fake edge to get something to start with. FlowQ.push(CFGEdge(-1, EntryN)); while (!FlowQ.empty()) { CFGEdge Edge = FlowQ.front(); FlowQ.pop(); if (EdgeExec.count(Edge)) continue; EdgeExec.insert(Edge); const MachineBasicBlock &B = *MF.getBlockNumbered(Edge.second); MachineBasicBlock::const_iterator It = B.begin(), End = B.end(); // Visit PHI nodes first. while (It != End && It->isPHI()) { const MachineInstr *PI = &*It++; InstrExec.insert(PI); visitPHI(PI); } // If this block has already been visited through a flow graph edge, // then the instructions have already been processed. Any updates to // the cells would now only happen through visitUsesOf... if (BlockScanned[Edge.second]) continue; BlockScanned[Edge.second] = true; // Visit non-branch instructions. while (It != End && !It->isBranch()) { const MachineInstr *MI = &*It++; InstrExec.insert(MI); visitNonBranch(MI); } // If block end has been reached, add the fall-through edge to the queue. if (It == End) { MachineFunction::const_iterator BIt = B.getIterator(); MachineFunction::const_iterator Next = std::next(BIt); if (Next != MF.end() && B.isSuccessor(&*Next)) { int ThisN = B.getNumber(); int NextN = Next->getNumber(); FlowQ.push(CFGEdge(ThisN, NextN)); } } else { // Handle the remaining sequence of branches. This function will update // the work queue. visitBranchesFrom(It); } } // while (!FlowQ->empty()) if (Trace) { dbgs() << "Cells after propagation:\n"; for (CellMapType::iterator I = Map.begin(), E = Map.end(); I != E; ++I) dbgs() << PrintReg(I->first, &ME.TRI) << " -> " << I->second << "\n"; } }