1 //===-- RISCVInsertWriteVXRM.cpp - Insert Write of RISC-V VXRM CSR --------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass inserts writes to the VXRM CSR as needed by vector instructions. 10 // Each instruction that uses VXRM carries an operand that contains its required 11 // VXRM value. This pass tries to optimize placement to avoid redundant writes 12 // to VXRM. 13 // 14 // This is done using 2 dataflow algorithms. The first is a forward data flow 15 // to calculate where a VXRM value is available. The second is a backwards 16 // dataflow to determine where a VXRM value is anticipated. 17 // 18 // Finally, we use the results of these two dataflows to insert VXRM writes 19 // where a value is anticipated, but not available. 20 // 21 // FIXME: This pass does not split critical edges, so there can still be some 22 // redundancy. 23 // 24 // FIXME: If we are willing to have writes that aren't always needed, we could 25 // reduce the number of VXRM writes in some cases. 26 //===----------------------------------------------------------------------===// 27 28 #include "MCTargetDesc/RISCVBaseInfo.h" 29 #include "RISCV.h" 30 #include "RISCVSubtarget.h" 31 #include "llvm/CodeGen/MachineFunctionPass.h" 32 #include <queue> 33 34 using namespace llvm; 35 36 #define DEBUG_TYPE "riscv-insert-write-vxrm" 37 #define RISCV_INSERT_WRITE_VXRM_NAME "RISC-V Insert Write VXRM Pass" 38 39 namespace { 40 41 class VXRMInfo { 42 uint8_t VXRMImm = 0; 43 44 enum : uint8_t { 45 Uninitialized, 46 Static, 47 Unknown, 48 } State = Uninitialized; 49 50 public: 51 VXRMInfo() {} 52 53 static VXRMInfo getUnknown() { 54 VXRMInfo Info; 55 Info.setUnknown(); 56 return Info; 57 } 58 59 bool isValid() const { return State != Uninitialized; } 60 void setUnknown() { State = Unknown; } 61 bool isUnknown() const { return State == Unknown; } 62 63 bool isStatic() const { return State == Static; } 64 65 void setVXRMImm(unsigned Imm) { 66 assert(Imm <= 3 && "Unexpected VXRM value"); 67 VXRMImm = Imm; 68 State = Static; 69 } 70 unsigned getVXRMImm() const { 71 assert(isStatic() && VXRMImm <= 3 && "Unexpected state"); 72 return VXRMImm; 73 } 74 75 bool operator==(const VXRMInfo &Other) const { 76 // Uninitialized is only equal to another Uninitialized. 77 if (State != Other.State) 78 return false; 79 80 if (isStatic()) 81 return VXRMImm == Other.VXRMImm; 82 83 assert((isValid() || isUnknown()) && "Unexpected state"); 84 return true; 85 } 86 87 bool operator!=(const VXRMInfo &Other) const { return !(*this == Other); } 88 89 // Calculate the VXRMInfo visible to a block assuming this and Other are 90 // both predecessors. 91 VXRMInfo intersect(const VXRMInfo &Other) const { 92 // If the new value isn't valid, ignore it. 93 if (!Other.isValid()) 94 return *this; 95 96 // If this value isn't valid, this must be the first predecessor, use it. 97 if (!isValid()) 98 return Other; 99 100 // If either is unknown, the result is unknown. 101 if (isUnknown() || Other.isUnknown()) 102 return VXRMInfo::getUnknown(); 103 104 // If we have an exact match, return this. 105 if (*this == Other) 106 return *this; 107 108 // Otherwise the result is unknown. 109 return VXRMInfo::getUnknown(); 110 } 111 112 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 113 /// Support for debugging, callable in GDB: V->dump() 114 LLVM_DUMP_METHOD void dump() const { 115 print(dbgs()); 116 dbgs() << "\n"; 117 } 118 119 void print(raw_ostream &OS) const { 120 OS << '{'; 121 if (!isValid()) 122 OS << "Uninitialized"; 123 else if (isUnknown()) 124 OS << "Unknown"; 125 else 126 OS << getVXRMImm(); 127 OS << '}'; 128 } 129 #endif 130 }; 131 132 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 133 LLVM_ATTRIBUTE_USED 134 inline raw_ostream &operator<<(raw_ostream &OS, const VXRMInfo &V) { 135 V.print(OS); 136 return OS; 137 } 138 #endif 139 140 struct BlockData { 141 // Indicates if the block uses VXRM. Uninitialized means no use. 142 VXRMInfo VXRMUse; 143 144 // Indicates the VXRM output from the block. Unitialized means transparent. 145 VXRMInfo VXRMOut; 146 147 // Keeps track of the available VXRM value at the start of the basic bloc. 148 VXRMInfo AvailableIn; 149 150 // Keeps track of the available VXRM value at the end of the basic block. 151 VXRMInfo AvailableOut; 152 153 // Keeps track of what VXRM is anticipated at the start of the basic block. 154 VXRMInfo AnticipatedIn; 155 156 // Keeps track of what VXRM is anticipated at the end of the basic block. 157 VXRMInfo AnticipatedOut; 158 159 // Keeps track of whether the block is already in the queue. 160 bool InQueue; 161 162 BlockData() = default; 163 }; 164 165 class RISCVInsertWriteVXRM : public MachineFunctionPass { 166 const TargetInstrInfo *TII; 167 168 std::vector<BlockData> BlockInfo; 169 std::queue<const MachineBasicBlock *> WorkList; 170 171 public: 172 static char ID; 173 174 RISCVInsertWriteVXRM() : MachineFunctionPass(ID) {} 175 176 bool runOnMachineFunction(MachineFunction &MF) override; 177 178 void getAnalysisUsage(AnalysisUsage &AU) const override { 179 AU.setPreservesCFG(); 180 MachineFunctionPass::getAnalysisUsage(AU); 181 } 182 183 StringRef getPassName() const override { 184 return RISCV_INSERT_WRITE_VXRM_NAME; 185 } 186 187 private: 188 bool computeVXRMChanges(const MachineBasicBlock &MBB); 189 void computeAvailable(const MachineBasicBlock &MBB); 190 void computeAnticipated(const MachineBasicBlock &MBB); 191 void emitWriteVXRM(MachineBasicBlock &MBB); 192 }; 193 194 } // end anonymous namespace 195 196 char RISCVInsertWriteVXRM::ID = 0; 197 198 INITIALIZE_PASS(RISCVInsertWriteVXRM, DEBUG_TYPE, RISCV_INSERT_WRITE_VXRM_NAME, 199 false, false) 200 201 bool RISCVInsertWriteVXRM::computeVXRMChanges(const MachineBasicBlock &MBB) { 202 BlockData &BBInfo = BlockInfo[MBB.getNumber()]; 203 204 bool NeedVXRMWrite = false; 205 for (const MachineInstr &MI : MBB) { 206 int VXRMIdx = RISCVII::getVXRMOpNum(MI.getDesc()); 207 if (VXRMIdx >= 0) { 208 unsigned NewVXRMImm = MI.getOperand(VXRMIdx).getImm(); 209 210 if (!BBInfo.VXRMUse.isValid()) 211 BBInfo.VXRMUse.setVXRMImm(NewVXRMImm); 212 213 BBInfo.VXRMOut.setVXRMImm(NewVXRMImm); 214 NeedVXRMWrite = true; 215 continue; 216 } 217 218 if (MI.isCall() || MI.isInlineAsm() || MI.modifiesRegister(RISCV::VXRM)) { 219 if (!BBInfo.VXRMUse.isValid()) 220 BBInfo.VXRMUse.setUnknown(); 221 222 BBInfo.VXRMOut.setUnknown(); 223 } 224 } 225 226 return NeedVXRMWrite; 227 } 228 229 void RISCVInsertWriteVXRM::computeAvailable(const MachineBasicBlock &MBB) { 230 BlockData &BBInfo = BlockInfo[MBB.getNumber()]; 231 232 BBInfo.InQueue = false; 233 234 VXRMInfo Available; 235 if (MBB.pred_empty()) { 236 Available.setUnknown(); 237 } else { 238 for (const MachineBasicBlock *P : MBB.predecessors()) 239 Available = Available.intersect(BlockInfo[P->getNumber()].AvailableOut); 240 } 241 242 // If we don't have any valid available info, wait until we do. 243 if (!Available.isValid()) 244 return; 245 246 if (Available != BBInfo.AvailableIn) { 247 BBInfo.AvailableIn = Available; 248 LLVM_DEBUG(dbgs() << "AvailableIn state of " << printMBBReference(MBB) 249 << " changed to " << BBInfo.AvailableIn << "\n"); 250 } 251 252 if (BBInfo.VXRMOut.isValid()) 253 Available = BBInfo.VXRMOut; 254 255 if (Available == BBInfo.AvailableOut) 256 return; 257 258 BBInfo.AvailableOut = Available; 259 LLVM_DEBUG(dbgs() << "AvailableOut state of " << printMBBReference(MBB) 260 << " changed to " << BBInfo.AvailableOut << "\n"); 261 262 // Add the successors to the work list so that we can propagate. 263 for (MachineBasicBlock *S : MBB.successors()) { 264 if (!BlockInfo[S->getNumber()].InQueue) { 265 BlockInfo[S->getNumber()].InQueue = true; 266 WorkList.push(S); 267 } 268 } 269 } 270 271 void RISCVInsertWriteVXRM::computeAnticipated(const MachineBasicBlock &MBB) { 272 BlockData &BBInfo = BlockInfo[MBB.getNumber()]; 273 274 BBInfo.InQueue = false; 275 276 VXRMInfo Anticipated; 277 if (MBB.succ_empty()) { 278 Anticipated.setUnknown(); 279 } else { 280 for (const MachineBasicBlock *S : MBB.successors()) 281 Anticipated = 282 Anticipated.intersect(BlockInfo[S->getNumber()].AnticipatedIn); 283 } 284 285 // If we don't have any valid anticipated info, wait until we do. 286 if (!Anticipated.isValid()) 287 return; 288 289 if (Anticipated != BBInfo.AnticipatedOut) { 290 BBInfo.AnticipatedOut = Anticipated; 291 LLVM_DEBUG(dbgs() << "AnticipatedOut state of " << printMBBReference(MBB) 292 << " changed to " << BBInfo.AnticipatedOut << "\n"); 293 } 294 295 // If this block reads VXRM, copy it. 296 if (BBInfo.VXRMUse.isValid()) 297 Anticipated = BBInfo.VXRMUse; 298 299 if (Anticipated == BBInfo.AnticipatedIn) 300 return; 301 302 BBInfo.AnticipatedIn = Anticipated; 303 LLVM_DEBUG(dbgs() << "AnticipatedIn state of " << printMBBReference(MBB) 304 << " changed to " << BBInfo.AnticipatedIn << "\n"); 305 306 // Add the predecessors to the work list so that we can propagate. 307 for (MachineBasicBlock *P : MBB.predecessors()) { 308 if (!BlockInfo[P->getNumber()].InQueue) { 309 BlockInfo[P->getNumber()].InQueue = true; 310 WorkList.push(P); 311 } 312 } 313 } 314 315 void RISCVInsertWriteVXRM::emitWriteVXRM(MachineBasicBlock &MBB) { 316 const BlockData &BBInfo = BlockInfo[MBB.getNumber()]; 317 318 VXRMInfo Info = BBInfo.AvailableIn; 319 320 // Flag to indicates we need to insert a VXRM write. We want to delay it as 321 // late as possible in this block. 322 bool PendingInsert = false; 323 324 // Insert VXRM write if anticipated and not available. 325 if (BBInfo.AnticipatedIn.isStatic()) { 326 // If this is the entry block and the value is anticipated, insert. 327 if (MBB.isEntryBlock()) { 328 PendingInsert = true; 329 } else { 330 // Search for any predecessors that wouldn't satisfy our requirement and 331 // insert a write VXRM if needed. 332 // NOTE: If one predecessor is able to provide the requirement, but 333 // another isn't, it means we have a critical edge. The better placement 334 // would be to split the critical edge. 335 for (MachineBasicBlock *P : MBB.predecessors()) { 336 const BlockData &PInfo = BlockInfo[P->getNumber()]; 337 // If it's available out of the predecessor, then we're ok. 338 if (PInfo.AvailableOut.isStatic() && 339 PInfo.AvailableOut.getVXRMImm() == 340 BBInfo.AnticipatedIn.getVXRMImm()) 341 continue; 342 // If the predecessor anticipates this value for all its succesors, 343 // then a write to VXRM would have already occured before this block is 344 // executed. 345 if (PInfo.AnticipatedOut.isStatic() && 346 PInfo.AnticipatedOut.getVXRMImm() == 347 BBInfo.AnticipatedIn.getVXRMImm()) 348 continue; 349 PendingInsert = true; 350 break; 351 } 352 } 353 354 Info = BBInfo.AnticipatedIn; 355 } 356 357 for (MachineInstr &MI : MBB) { 358 int VXRMIdx = RISCVII::getVXRMOpNum(MI.getDesc()); 359 if (VXRMIdx >= 0) { 360 unsigned NewVXRMImm = MI.getOperand(VXRMIdx).getImm(); 361 362 if (PendingInsert || !Info.isStatic() || 363 Info.getVXRMImm() != NewVXRMImm) { 364 assert((!PendingInsert || 365 (Info.isStatic() && Info.getVXRMImm() == NewVXRMImm)) && 366 "Pending VXRM insertion mismatch"); 367 LLVM_DEBUG(dbgs() << "Inserting before "; MI.print(dbgs())); 368 BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(RISCV::WriteVXRMImm)) 369 .addImm(NewVXRMImm); 370 PendingInsert = false; 371 } 372 373 MI.addOperand(MachineOperand::CreateReg(RISCV::VXRM, /*IsDef*/ false, 374 /*IsImp*/ true)); 375 Info.setVXRMImm(NewVXRMImm); 376 continue; 377 } 378 379 if (MI.isCall() || MI.isInlineAsm() || MI.modifiesRegister(RISCV::VXRM)) 380 Info.setUnknown(); 381 } 382 383 // If all our successors anticipate a value, do the insert. 384 // NOTE: It's possible that not all predecessors of our successor provide the 385 // correct value. This can occur on critical edges. If we don't split the 386 // critical edge we'll also have a write vxrm in the succesor that is 387 // redundant with this one. 388 if (PendingInsert || 389 (BBInfo.AnticipatedOut.isStatic() && 390 (!Info.isStatic() || 391 Info.getVXRMImm() != BBInfo.AnticipatedOut.getVXRMImm()))) { 392 assert((!PendingInsert || 393 (Info.isStatic() && BBInfo.AnticipatedOut.isStatic() && 394 Info.getVXRMImm() == BBInfo.AnticipatedOut.getVXRMImm())) && 395 "Pending VXRM insertion mismatch"); 396 LLVM_DEBUG(dbgs() << "Inserting at end of " << printMBBReference(MBB) 397 << " changing to " << BBInfo.AnticipatedOut << "\n"); 398 BuildMI(MBB, MBB.getFirstTerminator(), DebugLoc(), 399 TII->get(RISCV::WriteVXRMImm)) 400 .addImm(BBInfo.AnticipatedOut.getVXRMImm()); 401 } 402 } 403 404 bool RISCVInsertWriteVXRM::runOnMachineFunction(MachineFunction &MF) { 405 // Skip if the vector extension is not enabled. 406 const RISCVSubtarget &ST = MF.getSubtarget<RISCVSubtarget>(); 407 if (!ST.hasVInstructions()) 408 return false; 409 410 TII = ST.getInstrInfo(); 411 412 assert(BlockInfo.empty() && "Expect empty block infos"); 413 BlockInfo.resize(MF.getNumBlockIDs()); 414 415 // Phase 1 - collect block information. 416 bool NeedVXRMChange = false; 417 for (const MachineBasicBlock &MBB : MF) 418 NeedVXRMChange |= computeVXRMChanges(MBB); 419 420 if (!NeedVXRMChange) { 421 BlockInfo.clear(); 422 return false; 423 } 424 425 // Phase 2 - Compute available VXRM using a forward walk. 426 for (const MachineBasicBlock &MBB : MF) { 427 WorkList.push(&MBB); 428 BlockInfo[MBB.getNumber()].InQueue = true; 429 } 430 while (!WorkList.empty()) { 431 const MachineBasicBlock &MBB = *WorkList.front(); 432 WorkList.pop(); 433 computeAvailable(MBB); 434 } 435 436 // Phase 3 - Compute anticipated VXRM using a backwards walk. 437 for (const MachineBasicBlock &MBB : llvm::reverse(MF)) { 438 WorkList.push(&MBB); 439 BlockInfo[MBB.getNumber()].InQueue = true; 440 } 441 while (!WorkList.empty()) { 442 const MachineBasicBlock &MBB = *WorkList.front(); 443 WorkList.pop(); 444 computeAnticipated(MBB); 445 } 446 447 // Phase 4 - Emit VXRM writes at the earliest place possible. 448 for (MachineBasicBlock &MBB : MF) 449 emitWriteVXRM(MBB); 450 451 BlockInfo.clear(); 452 453 return true; 454 } 455 456 FunctionPass *llvm::createRISCVInsertWriteVXRMPass() { 457 return new RISCVInsertWriteVXRM(); 458 } 459