1 //===- BitTracker.h ---------------------------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H 11 #define LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H 12 13 #include "llvm/ADT/DenseSet.h" 14 #include "llvm/ADT/SetVector.h" 15 #include "llvm/ADT/SmallVector.h" 16 #include "llvm/CodeGen/MachineInstr.h" 17 #include "llvm/CodeGen/MachineOperand.h" 18 #include <cassert> 19 #include <cstdint> 20 #include <map> 21 #include <queue> 22 #include <set> 23 #include <utility> 24 25 namespace llvm { 26 27 class BitVector; 28 class ConstantInt; 29 class MachineRegisterInfo; 30 class MachineBasicBlock; 31 class MachineFunction; 32 class raw_ostream; 33 class TargetRegisterClass; 34 class TargetRegisterInfo; 35 36 struct BitTracker { 37 struct BitRef; 38 struct RegisterRef; 39 struct BitValue; 40 struct BitMask; 41 struct RegisterCell; 42 struct MachineEvaluator; 43 44 using BranchTargetList = SetVector<const MachineBasicBlock *>; 45 using CellMapType = std::map<unsigned, RegisterCell>; 46 47 BitTracker(const MachineEvaluator &E, MachineFunction &F); 48 ~BitTracker(); 49 50 void run(); 51 void trace(bool On = false) { Trace = On; } 52 bool has(unsigned Reg) const; 53 const RegisterCell &lookup(unsigned Reg) const; 54 RegisterCell get(RegisterRef RR) const; 55 void put(RegisterRef RR, const RegisterCell &RC); 56 void subst(RegisterRef OldRR, RegisterRef NewRR); 57 bool reached(const MachineBasicBlock *B) const; 58 void visit(const MachineInstr &MI); 59 60 void print_cells(raw_ostream &OS) const; 61 62 private: 63 void visitPHI(const MachineInstr &PI); 64 void visitNonBranch(const MachineInstr &MI); 65 void visitBranchesFrom(const MachineInstr &BI); 66 void visitUsesOf(unsigned Reg); 67 68 using CFGEdge = std::pair<int, int>; 69 using EdgeSetType = std::set<CFGEdge>; 70 using InstrSetType = std::set<const MachineInstr *>; 71 using EdgeQueueType = std::queue<CFGEdge>; 72 73 // Priority queue of instructions using modified registers, ordered by 74 // their relative position in a basic block. 75 struct UseQueueType { 76 UseQueueType() : Uses(Dist) {} 77 78 unsigned size() const { 79 return Uses.size(); 80 } 81 bool empty() const { 82 return size() == 0; 83 } 84 MachineInstr *front() const { 85 return Uses.top(); 86 } 87 void push(MachineInstr *MI) { 88 if (Set.insert(MI).second) 89 Uses.push(MI); 90 } 91 void pop() { 92 Set.erase(front()); 93 Uses.pop(); 94 } 95 void reset() { 96 Dist.clear(); 97 } 98 private: 99 struct Cmp { 100 Cmp(DenseMap<const MachineInstr*,unsigned> &Map) : Dist(Map) {} 101 bool operator()(const MachineInstr *MI, const MachineInstr *MJ) const; 102 DenseMap<const MachineInstr*,unsigned> &Dist; 103 }; 104 std::priority_queue<MachineInstr*, std::vector<MachineInstr*>, Cmp> Uses; 105 DenseSet<const MachineInstr*> Set; // Set to avoid adding duplicate entries. 106 DenseMap<const MachineInstr*,unsigned> Dist; 107 }; 108 109 void reset(); 110 void runEdgeQueue(BitVector &BlockScanned); 111 void runUseQueue(); 112 113 const MachineEvaluator &ME; 114 MachineFunction &MF; 115 MachineRegisterInfo &MRI; 116 CellMapType ⤅ 117 118 EdgeSetType EdgeExec; // Executable flow graph edges. 119 InstrSetType InstrExec; // Executable instructions. 120 UseQueueType UseQ; // Work queue of register uses. 121 EdgeQueueType FlowQ; // Work queue of CFG edges. 122 DenseSet<unsigned> ReachedBB; // Cache of reached blocks. 123 bool Trace; // Enable tracing for debugging. 124 }; 125 126 // Abstraction of a reference to bit at position Pos from a register Reg. 127 struct BitTracker::BitRef { 128 BitRef(unsigned R = 0, uint16_t P = 0) : Reg(R), Pos(P) {} 129 130 bool operator== (const BitRef &BR) const { 131 // If Reg is 0, disregard Pos. 132 return Reg == BR.Reg && (Reg == 0 || Pos == BR.Pos); 133 } 134 135 unsigned Reg; 136 uint16_t Pos; 137 }; 138 139 // Abstraction of a register reference in MachineOperand. It contains the 140 // register number and the subregister index. 141 struct BitTracker::RegisterRef { 142 RegisterRef(unsigned R = 0, unsigned S = 0) 143 : Reg(R), Sub(S) {} 144 RegisterRef(const MachineOperand &MO) 145 : Reg(MO.getReg()), Sub(MO.getSubReg()) {} 146 147 unsigned Reg, Sub; 148 }; 149 150 // Value that a single bit can take. This is outside of the context of 151 // any register, it is more of an abstraction of the two-element set of 152 // possible bit values. One extension here is the "Ref" type, which 153 // indicates that this bit takes the same value as the bit described by 154 // RefInfo. 155 struct BitTracker::BitValue { 156 enum ValueType { 157 Top, // Bit not yet defined. 158 Zero, // Bit = 0. 159 One, // Bit = 1. 160 Ref // Bit value same as the one described in RefI. 161 // Conceptually, there is no explicit "bottom" value: the lattice's 162 // bottom will be expressed as a "ref to itself", which, in the context 163 // of registers, could be read as "this value of this bit is defined by 164 // this bit". 165 // The ordering is: 166 // x <= Top, 167 // Self <= x, where "Self" is "ref to itself". 168 // This makes the value lattice different for each virtual register 169 // (even for each bit in the same virtual register), since the "bottom" 170 // for one register will be a simple "ref" for another register. 171 // Since we do not store the "Self" bit and register number, the meet 172 // operation will need to take it as a parameter. 173 // 174 // In practice there is a special case for values that are not associa- 175 // ted with any specific virtual register. An example would be a value 176 // corresponding to a bit of a physical register, or an intermediate 177 // value obtained in some computation (such as instruction evaluation). 178 // Such cases are identical to the usual Ref type, but the register 179 // number is 0. In such case the Pos field of the reference is ignored. 180 // 181 // What is worthy of notice is that in value V (that is a "ref"), as long 182 // as the RefI.Reg is not 0, it may actually be the same register as the 183 // one in which V will be contained. If the RefI.Pos refers to the posi- 184 // tion of V, then V is assumed to be "bottom" (as a "ref to itself"), 185 // otherwise V is taken to be identical to the referenced bit of the 186 // same register. 187 // If RefI.Reg is 0, however, such a reference to the same register is 188 // not possible. Any value V that is a "ref", and whose RefI.Reg is 0 189 // is treated as "bottom". 190 }; 191 ValueType Type; 192 BitRef RefI; 193 194 BitValue(ValueType T = Top) : Type(T) {} 195 BitValue(bool B) : Type(B ? One : Zero) {} 196 BitValue(unsigned Reg, uint16_t Pos) : Type(Ref), RefI(Reg, Pos) {} 197 198 bool operator== (const BitValue &V) const { 199 if (Type != V.Type) 200 return false; 201 if (Type == Ref && !(RefI == V.RefI)) 202 return false; 203 return true; 204 } 205 bool operator!= (const BitValue &V) const { 206 return !operator==(V); 207 } 208 209 bool is(unsigned T) const { 210 assert(T == 0 || T == 1); 211 return T == 0 ? Type == Zero 212 : (T == 1 ? Type == One : false); 213 } 214 215 // The "meet" operation is the "." operation in a semilattice (L, ., T, B): 216 // (1) x.x = x 217 // (2) x.y = y.x 218 // (3) x.(y.z) = (x.y).z 219 // (4) x.T = x (i.e. T = "top") 220 // (5) x.B = B (i.e. B = "bottom") 221 // 222 // This "meet" function will update the value of the "*this" object with 223 // the newly calculated one, and return "true" if the value of *this has 224 // changed, and "false" otherwise. 225 // To prove that it satisfies the conditions (1)-(5), it is sufficient 226 // to show that a relation 227 // x <= y <=> x.y = x 228 // defines a partial order (i.e. that "meet" is same as "infimum"). 229 bool meet(const BitValue &V, const BitRef &Self) { 230 // First, check the cases where there is nothing to be done. 231 if (Type == Ref && RefI == Self) // Bottom.meet(V) = Bottom (i.e. This) 232 return false; 233 if (V.Type == Top) // This.meet(Top) = This 234 return false; 235 if (*this == V) // This.meet(This) = This 236 return false; 237 238 // At this point, we know that the value of "this" will change. 239 // If it is Top, it will become the same as V, otherwise it will 240 // become "bottom" (i.e. Self). 241 if (Type == Top) { 242 Type = V.Type; 243 RefI = V.RefI; // This may be irrelevant, but copy anyway. 244 return true; 245 } 246 // Become "bottom". 247 Type = Ref; 248 RefI = Self; 249 return true; 250 } 251 252 // Create a reference to the bit value V. 253 static BitValue ref(const BitValue &V); 254 // Create a "self". 255 static BitValue self(const BitRef &Self = BitRef()); 256 257 bool num() const { 258 return Type == Zero || Type == One; 259 } 260 261 operator bool() const { 262 assert(Type == Zero || Type == One); 263 return Type == One; 264 } 265 266 friend raw_ostream &operator<<(raw_ostream &OS, const BitValue &BV); 267 }; 268 269 // This operation must be idempotent, i.e. ref(ref(V)) == ref(V). 270 inline BitTracker::BitValue 271 BitTracker::BitValue::ref(const BitValue &V) { 272 if (V.Type != Ref) 273 return BitValue(V.Type); 274 if (V.RefI.Reg != 0) 275 return BitValue(V.RefI.Reg, V.RefI.Pos); 276 return self(); 277 } 278 279 inline BitTracker::BitValue 280 BitTracker::BitValue::self(const BitRef &Self) { 281 return BitValue(Self.Reg, Self.Pos); 282 } 283 284 // A sequence of bits starting from index B up to and including index E. 285 // If E < B, the mask represents two sections: [0..E] and [B..W) where 286 // W is the width of the register. 287 struct BitTracker::BitMask { 288 BitMask() = default; 289 BitMask(uint16_t b, uint16_t e) : B(b), E(e) {} 290 291 uint16_t first() const { return B; } 292 uint16_t last() const { return E; } 293 294 private: 295 uint16_t B = 0; 296 uint16_t E = 0; 297 }; 298 299 // Representation of a register: a list of BitValues. 300 struct BitTracker::RegisterCell { 301 RegisterCell(uint16_t Width = DefaultBitN) : Bits(Width) {} 302 303 uint16_t width() const { 304 return Bits.size(); 305 } 306 307 const BitValue &operator[](uint16_t BitN) const { 308 assert(BitN < Bits.size()); 309 return Bits[BitN]; 310 } 311 BitValue &operator[](uint16_t BitN) { 312 assert(BitN < Bits.size()); 313 return Bits[BitN]; 314 } 315 316 bool meet(const RegisterCell &RC, unsigned SelfR); 317 RegisterCell &insert(const RegisterCell &RC, const BitMask &M); 318 RegisterCell extract(const BitMask &M) const; // Returns a new cell. 319 RegisterCell &rol(uint16_t Sh); // Rotate left. 320 RegisterCell &fill(uint16_t B, uint16_t E, const BitValue &V); 321 RegisterCell &cat(const RegisterCell &RC); // Concatenate. 322 uint16_t cl(bool B) const; 323 uint16_t ct(bool B) const; 324 325 bool operator== (const RegisterCell &RC) const; 326 bool operator!= (const RegisterCell &RC) const { 327 return !operator==(RC); 328 } 329 330 // Replace the ref-to-reg-0 bit values with the given register. 331 RegisterCell ®ify(unsigned R); 332 333 // Generate a "ref" cell for the corresponding register. In the resulting 334 // cell each bit will be described as being the same as the corresponding 335 // bit in register Reg (i.e. the cell is "defined" by register Reg). 336 static RegisterCell self(unsigned Reg, uint16_t Width); 337 // Generate a "top" cell of given size. 338 static RegisterCell top(uint16_t Width); 339 // Generate a cell that is a "ref" to another cell. 340 static RegisterCell ref(const RegisterCell &C); 341 342 private: 343 // The DefaultBitN is here only to avoid frequent reallocation of the 344 // memory in the vector. 345 static const unsigned DefaultBitN = 32; 346 using BitValueList = SmallVector<BitValue, DefaultBitN>; 347 BitValueList Bits; 348 349 friend raw_ostream &operator<<(raw_ostream &OS, const RegisterCell &RC); 350 }; 351 352 inline bool BitTracker::has(unsigned Reg) const { 353 return Map.find(Reg) != Map.end(); 354 } 355 356 inline const BitTracker::RegisterCell& 357 BitTracker::lookup(unsigned Reg) const { 358 CellMapType::const_iterator F = Map.find(Reg); 359 assert(F != Map.end()); 360 return F->second; 361 } 362 363 inline BitTracker::RegisterCell 364 BitTracker::RegisterCell::self(unsigned Reg, uint16_t Width) { 365 RegisterCell RC(Width); 366 for (uint16_t i = 0; i < Width; ++i) 367 RC.Bits[i] = BitValue::self(BitRef(Reg, i)); 368 return RC; 369 } 370 371 inline BitTracker::RegisterCell 372 BitTracker::RegisterCell::top(uint16_t Width) { 373 RegisterCell RC(Width); 374 for (uint16_t i = 0; i < Width; ++i) 375 RC.Bits[i] = BitValue(BitValue::Top); 376 return RC; 377 } 378 379 inline BitTracker::RegisterCell 380 BitTracker::RegisterCell::ref(const RegisterCell &C) { 381 uint16_t W = C.width(); 382 RegisterCell RC(W); 383 for (unsigned i = 0; i < W; ++i) 384 RC[i] = BitValue::ref(C[i]); 385 return RC; 386 } 387 388 // A class to evaluate target's instructions and update the cell maps. 389 // This is used internally by the bit tracker. A target that wants to 390 // utilize this should implement the evaluation functions (noted below) 391 // in a subclass of this class. 392 struct BitTracker::MachineEvaluator { 393 MachineEvaluator(const TargetRegisterInfo &T, MachineRegisterInfo &M) 394 : TRI(T), MRI(M) {} 395 virtual ~MachineEvaluator() = default; 396 397 uint16_t getRegBitWidth(const RegisterRef &RR) const; 398 399 RegisterCell getCell(const RegisterRef &RR, const CellMapType &M) const; 400 void putCell(const RegisterRef &RR, RegisterCell RC, CellMapType &M) const; 401 402 // A result of any operation should use refs to the source cells, not 403 // the cells directly. This function is a convenience wrapper to quickly 404 // generate a ref for a cell corresponding to a register reference. 405 RegisterCell getRef(const RegisterRef &RR, const CellMapType &M) const { 406 RegisterCell RC = getCell(RR, M); 407 return RegisterCell::ref(RC); 408 } 409 410 // Helper functions. 411 // Check if a cell is an immediate value (i.e. all bits are either 0 or 1). 412 bool isInt(const RegisterCell &A) const; 413 // Convert cell to an immediate value. 414 uint64_t toInt(const RegisterCell &A) const; 415 416 // Generate cell from an immediate value. 417 RegisterCell eIMM(int64_t V, uint16_t W) const; 418 RegisterCell eIMM(const ConstantInt *CI) const; 419 420 // Arithmetic. 421 RegisterCell eADD(const RegisterCell &A1, const RegisterCell &A2) const; 422 RegisterCell eSUB(const RegisterCell &A1, const RegisterCell &A2) const; 423 RegisterCell eMLS(const RegisterCell &A1, const RegisterCell &A2) const; 424 RegisterCell eMLU(const RegisterCell &A1, const RegisterCell &A2) const; 425 426 // Shifts. 427 RegisterCell eASL(const RegisterCell &A1, uint16_t Sh) const; 428 RegisterCell eLSR(const RegisterCell &A1, uint16_t Sh) const; 429 RegisterCell eASR(const RegisterCell &A1, uint16_t Sh) const; 430 431 // Logical. 432 RegisterCell eAND(const RegisterCell &A1, const RegisterCell &A2) const; 433 RegisterCell eORL(const RegisterCell &A1, const RegisterCell &A2) const; 434 RegisterCell eXOR(const RegisterCell &A1, const RegisterCell &A2) const; 435 RegisterCell eNOT(const RegisterCell &A1) const; 436 437 // Set bit, clear bit. 438 RegisterCell eSET(const RegisterCell &A1, uint16_t BitN) const; 439 RegisterCell eCLR(const RegisterCell &A1, uint16_t BitN) const; 440 441 // Count leading/trailing bits (zeros/ones). 442 RegisterCell eCLB(const RegisterCell &A1, bool B, uint16_t W) const; 443 RegisterCell eCTB(const RegisterCell &A1, bool B, uint16_t W) const; 444 445 // Sign/zero extension. 446 RegisterCell eSXT(const RegisterCell &A1, uint16_t FromN) const; 447 RegisterCell eZXT(const RegisterCell &A1, uint16_t FromN) const; 448 449 // Extract/insert 450 // XTR R,b,e: extract bits from A1 starting at bit b, ending at e-1. 451 // INS R,S,b: take R and replace bits starting from b with S. 452 RegisterCell eXTR(const RegisterCell &A1, uint16_t B, uint16_t E) const; 453 RegisterCell eINS(const RegisterCell &A1, const RegisterCell &A2, 454 uint16_t AtN) const; 455 456 // User-provided functions for individual targets: 457 458 // Return a sub-register mask that indicates which bits in Reg belong 459 // to the subregister Sub. These bits are assumed to be contiguous in 460 // the super-register, and have the same ordering in the sub-register 461 // as in the super-register. It is valid to call this function with 462 // Sub == 0, in this case, the function should return a mask that spans 463 // the entire register Reg (which is what the default implementation 464 // does). 465 virtual BitMask mask(unsigned Reg, unsigned Sub) const; 466 // Indicate whether a given register class should be tracked. 467 virtual bool track(const TargetRegisterClass *RC) const { return true; } 468 // Evaluate a non-branching machine instruction, given the cell map with 469 // the input values. Place the results in the Outputs map. Return "true" 470 // if evaluation succeeded, "false" otherwise. 471 virtual bool evaluate(const MachineInstr &MI, const CellMapType &Inputs, 472 CellMapType &Outputs) const; 473 // Evaluate a branch, given the cell map with the input values. Fill out 474 // a list of all possible branch targets and indicate (through a flag) 475 // whether the branch could fall-through. Return "true" if this information 476 // has been successfully computed, "false" otherwise. 477 virtual bool evaluate(const MachineInstr &BI, const CellMapType &Inputs, 478 BranchTargetList &Targets, bool &FallsThru) const = 0; 479 // Given a register class RC, return a register class that should be assumed 480 // when a register from class RC is used with a subregister of index Idx. 481 virtual const TargetRegisterClass& 482 composeWithSubRegIndex(const TargetRegisterClass &RC, unsigned Idx) const { 483 if (Idx == 0) 484 return RC; 485 llvm_unreachable("Unimplemented composeWithSubRegIndex"); 486 } 487 // Return the size in bits of the physical register Reg. 488 virtual uint16_t getPhysRegBitWidth(unsigned Reg) const; 489 490 const TargetRegisterInfo &TRI; 491 MachineRegisterInfo &MRI; 492 }; 493 494 } // end namespace llvm 495 496 #endif // LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H 497