MipsInstrInfo.cpp revision 718cb665ca6ce2bc4d8e8479f46a45db91b49f86
1//===- MipsInstrInfo.cpp - Mips Instruction Information ---------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Bruno Cardoso Lopes and is distributed under the 6// University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains the Mips implementation of the TargetInstrInfo class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "Mips.h" 15#include "MipsInstrInfo.h" 16#include "llvm/ADT/STLExtras.h" 17#include "llvm/CodeGen/MachineInstrBuilder.h" 18#include "MipsGenInstrInfo.inc" 19 20using namespace llvm; 21 22// TODO: Add the subtarget support on this constructor 23MipsInstrInfo::MipsInstrInfo(MipsTargetMachine &tm) 24 : TargetInstrInfo(MipsInsts, array_lengthof(MipsInsts)), 25 TM(tm), RI(*this) {} 26 27static bool isZeroImm(const MachineOperand &op) { 28 return op.isImmediate() && op.getImmedValue() == 0; 29} 30 31/// Return true if the instruction is a register to register move and 32/// leave the source and dest operands in the passed parameters. 33bool MipsInstrInfo:: 34isMoveInstr(const MachineInstr &MI, unsigned &SrcReg, unsigned &DstReg) const 35{ 36 // addu $dst, $src, $zero || addu $dst, $zero, $src 37 // or $dst, $src, $zero || or $dst, $zero, $src 38 if ((MI.getOpcode() == Mips::ADDu) || (MI.getOpcode() == Mips::OR)) 39 { 40 if (MI.getOperand(1).getReg() == Mips::ZERO) { 41 DstReg = MI.getOperand(0).getReg(); 42 SrcReg = MI.getOperand(2).getReg(); 43 return true; 44 } else if (MI.getOperand(2).getReg() == Mips::ZERO) { 45 DstReg = MI.getOperand(0).getReg(); 46 SrcReg = MI.getOperand(1).getReg(); 47 return true; 48 } 49 } 50 51 // addiu $dst, $src, 0 52 if (MI.getOpcode() == Mips::ADDiu) 53 { 54 if ((MI.getOperand(1).isRegister()) && (isZeroImm(MI.getOperand(2)))) { 55 DstReg = MI.getOperand(0).getReg(); 56 SrcReg = MI.getOperand(1).getReg(); 57 return true; 58 } 59 } 60 return false; 61} 62 63/// isLoadFromStackSlot - If the specified machine instruction is a direct 64/// load from a stack slot, return the virtual or physical register number of 65/// the destination along with the FrameIndex of the loaded stack slot. If 66/// not, return 0. This predicate must return 0 if the instruction has 67/// any side effects other than loading from the stack slot. 68unsigned MipsInstrInfo:: 69isLoadFromStackSlot(MachineInstr *MI, int &FrameIndex) const 70{ 71 if (MI->getOpcode() == Mips::LW) 72 { 73 if ((MI->getOperand(2).isFrameIndex()) && // is a stack slot 74 (MI->getOperand(1).isImmediate()) && // the imm is zero 75 (isZeroImm(MI->getOperand(1)))) 76 { 77 FrameIndex = MI->getOperand(2).getFrameIndex(); 78 return MI->getOperand(0).getReg(); 79 } 80 } 81 82 return 0; 83} 84 85/// isStoreToStackSlot - If the specified machine instruction is a direct 86/// store to a stack slot, return the virtual or physical register number of 87/// the source reg along with the FrameIndex of the loaded stack slot. If 88/// not, return 0. This predicate must return 0 if the instruction has 89/// any side effects other than storing to the stack slot. 90unsigned MipsInstrInfo:: 91isStoreToStackSlot(MachineInstr *MI, int &FrameIndex) const 92{ 93 if (MI->getOpcode() == Mips::SW) { 94 if ((MI->getOperand(0).isFrameIndex()) && // is a stack slot 95 (MI->getOperand(1).isImmediate()) && // the imm is zero 96 (isZeroImm(MI->getOperand(1)))) 97 { 98 FrameIndex = MI->getOperand(0).getFrameIndex(); 99 return MI->getOperand(2).getReg(); 100 } 101 } 102 return 0; 103} 104 105/// insertNoop - If data hazard condition is found insert the target nop 106/// instruction. 107void MipsInstrInfo:: 108insertNoop(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const 109{ 110 BuildMI(MBB, MI, get(Mips::NOP)); 111} 112 113//===----------------------------------------------------------------------===// 114// Branch Analysis 115//===----------------------------------------------------------------------===// 116 117/// GetCondFromBranchOpc - Return the Mips CC that matches 118/// the correspondent Branch instruction opcode. 119static Mips::CondCode GetCondFromBranchOpc(unsigned BrOpc) 120{ 121 switch (BrOpc) { 122 default: return Mips::COND_INVALID; 123 case Mips::BEQ : return Mips::COND_E; 124 case Mips::BNE : return Mips::COND_NE; 125 case Mips::BGTZ : return Mips::COND_GZ; 126 case Mips::BGEZ : return Mips::COND_GEZ; 127 case Mips::BLTZ : return Mips::COND_LZ; 128 case Mips::BLEZ : return Mips::COND_LEZ; 129 } 130} 131 132/// GetCondBranchFromCond - Return the Branch instruction 133/// opcode that matches the cc. 134unsigned Mips::GetCondBranchFromCond(Mips::CondCode CC) 135{ 136 switch (CC) { 137 default: assert(0 && "Illegal condition code!"); 138 case Mips::COND_E : return Mips::BEQ; 139 case Mips::COND_NE : return Mips::BNE; 140 case Mips::COND_GZ : return Mips::BGTZ; 141 case Mips::COND_GEZ : return Mips::BGEZ; 142 case Mips::COND_LZ : return Mips::BLTZ; 143 case Mips::COND_LEZ : return Mips::BLEZ; 144 } 145} 146 147/// GetOppositeBranchCondition - Return the inverse of the specified 148/// condition, e.g. turning COND_E to COND_NE. 149Mips::CondCode Mips::GetOppositeBranchCondition(Mips::CondCode CC) 150{ 151 switch (CC) { 152 default: assert(0 && "Illegal condition code!"); 153 case Mips::COND_E : return Mips::COND_NE; 154 case Mips::COND_NE : return Mips::COND_E; 155 case Mips::COND_GZ : return Mips::COND_LEZ; 156 case Mips::COND_GEZ : return Mips::COND_LZ; 157 case Mips::COND_LZ : return Mips::COND_GEZ; 158 case Mips::COND_LEZ : return Mips::COND_GZ; 159 } 160} 161 162bool MipsInstrInfo::AnalyzeBranch(MachineBasicBlock &MBB, 163 MachineBasicBlock *&TBB, 164 MachineBasicBlock *&FBB, 165 std::vector<MachineOperand> &Cond) const 166{ 167 // If the block has no terminators, it just falls into the block after it. 168 MachineBasicBlock::iterator I = MBB.end(); 169 if (I == MBB.begin() || !isUnpredicatedTerminator(--I)) 170 return false; 171 172 // Get the last instruction in the block. 173 MachineInstr *LastInst = I; 174 175 // If there is only one terminator instruction, process it. 176 unsigned LastOpc = LastInst->getOpcode(); 177 if (I == MBB.begin() || !isUnpredicatedTerminator(--I)) { 178 if (!isBranch(LastInst->getOpcode())) 179 return true; 180 181 // Unconditional branch 182 if (LastOpc == Mips::J) { 183 TBB = LastInst->getOperand(0).getMachineBasicBlock(); 184 return false; 185 } 186 187 Mips::CondCode BranchCode = GetCondFromBranchOpc(LastInst->getOpcode()); 188 if (BranchCode == Mips::COND_INVALID) 189 return true; // Can't handle indirect branch. 190 191 // Conditional branch 192 // Block ends with fall-through condbranch. 193 if (LastOpc != Mips::COND_INVALID) { 194 int LastNumOp = LastInst->getNumOperands(); 195 196 TBB = LastInst->getOperand(LastNumOp-1).getMachineBasicBlock(); 197 Cond.push_back(MachineOperand::CreateImm(BranchCode)); 198 199 for (int i=0; i<LastNumOp-1; i++) { 200 Cond.push_back(LastInst->getOperand(i)); 201 } 202 203 return false; 204 } 205 } 206 207 // Get the instruction before it if it is a terminator. 208 MachineInstr *SecondLastInst = I; 209 210 // If there are three terminators, we don't know what sort of block this is. 211 if (SecondLastInst && I != MBB.begin() && isUnpredicatedTerminator(--I)) 212 return true; 213 214 // If the block ends with Mips::J and a Mips::BNE/Mips::BEQ, handle it. 215 unsigned SecondLastOpc = SecondLastInst->getOpcode(); 216 Mips::CondCode BranchCode = GetCondFromBranchOpc(SecondLastOpc); 217 218 if (SecondLastOpc != Mips::COND_INVALID && LastOpc == Mips::J) { 219 int SecondNumOp = SecondLastInst->getNumOperands(); 220 221 TBB = SecondLastInst->getOperand(SecondNumOp-1).getMachineBasicBlock(); 222 Cond.push_back(MachineOperand::CreateImm(BranchCode)); 223 224 for (int i=0; i<SecondNumOp-1; i++) { 225 Cond.push_back(SecondLastInst->getOperand(i)); 226 } 227 228 FBB = LastInst->getOperand(0).getMachineBasicBlock(); 229 return false; 230 } 231 232 // If the block ends with two unconditional branches, handle it. The last 233 // one is not executed, so remove it. 234 if ((SecondLastOpc == Mips::J) && (LastOpc == Mips::J)) { 235 TBB = SecondLastInst->getOperand(0).getMachineBasicBlock(); 236 I = LastInst; 237 I->eraseFromParent(); 238 return false; 239 } 240 241 // Otherwise, can't handle this. 242 return true; 243} 244 245unsigned MipsInstrInfo:: 246InsertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, 247 MachineBasicBlock *FBB, const std::vector<MachineOperand> &Cond) 248 const 249{ 250 // Shouldn't be a fall through. 251 assert(TBB && "InsertBranch must not be told to insert a fallthrough"); 252 assert((Cond.size() == 3 || Cond.size() == 2 || Cond.size() == 0) && 253 "Mips branch conditions can have two|three components!"); 254 255 if (FBB == 0) { // One way branch. 256 if (Cond.empty()) { 257 // Unconditional branch? 258 BuildMI(&MBB, get(Mips::J)).addMBB(TBB); 259 } else { 260 // Conditional branch. 261 unsigned Opc = GetCondBranchFromCond((Mips::CondCode)Cond[0].getImm()); 262 const TargetInstrDescriptor &TID = get(Opc); 263 264 if (TID.numOperands == 3) 265 BuildMI(&MBB, TID).addReg(Cond[1].getReg()) 266 .addReg(Cond[2].getReg()) 267 .addMBB(TBB); 268 else 269 BuildMI(&MBB, TID).addReg(Cond[1].getReg()) 270 .addMBB(TBB); 271 272 } 273 return 1; 274 } 275 276 // Two-way Conditional branch. 277 unsigned Opc = GetCondBranchFromCond((Mips::CondCode)Cond[0].getImm()); 278 const TargetInstrDescriptor &TID = get(Opc); 279 280 if (TID.numOperands == 3) 281 BuildMI(&MBB, TID).addReg(Cond[1].getReg()) 282 .addReg(Cond[2].getReg()) 283 .addMBB(TBB); 284 else 285 BuildMI(&MBB, TID).addReg(Cond[1].getReg()) 286 .addMBB(TBB); 287 288 BuildMI(&MBB, get(Mips::J)).addMBB(FBB); 289 return 2; 290} 291 292unsigned MipsInstrInfo:: 293RemoveBranch(MachineBasicBlock &MBB) const 294{ 295 MachineBasicBlock::iterator I = MBB.end(); 296 if (I == MBB.begin()) return 0; 297 --I; 298 if (I->getOpcode() != Mips::J && 299 GetCondFromBranchOpc(I->getOpcode()) == Mips::COND_INVALID) 300 return 0; 301 302 // Remove the branch. 303 I->eraseFromParent(); 304 305 I = MBB.end(); 306 307 if (I == MBB.begin()) return 1; 308 --I; 309 if (GetCondFromBranchOpc(I->getOpcode()) == Mips::COND_INVALID) 310 return 1; 311 312 // Remove the branch. 313 I->eraseFromParent(); 314 return 2; 315} 316 317/// BlockHasNoFallThrough - Analyse if MachineBasicBlock does not 318/// fall-through into its successor block. 319bool MipsInstrInfo:: 320BlockHasNoFallThrough(MachineBasicBlock &MBB) const 321{ 322 if (MBB.empty()) return false; 323 324 switch (MBB.back().getOpcode()) { 325 case Mips::RET: // Return. 326 case Mips::JR: // Indirect branch. 327 case Mips::J: // Uncond branch. 328 return true; 329 default: return false; 330 } 331} 332 333/// ReverseBranchCondition - Return the inverse opcode of the 334/// specified Branch instruction. 335bool MipsInstrInfo:: 336ReverseBranchCondition(std::vector<MachineOperand> &Cond) const 337{ 338 assert( (Cond.size() == 3 || Cond.size() == 2) && 339 "Invalid Mips branch condition!"); 340 Cond[0].setImm(GetOppositeBranchCondition((Mips::CondCode)Cond[0].getImm())); 341 return false; 342} 343 344 345