1 //===-- LanaiInstrInfo.cpp - Lanai Instruction Information ------*- 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 // This file contains the Lanai implementation of the TargetInstrInfo class.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "Lanai.h"
15 #include "LanaiInstrInfo.h"
16 #include "LanaiMachineFunctionInfo.h"
17 #include "LanaiTargetMachine.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineInstrBuilder.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/Support/ErrorHandling.h"
24 #include "llvm/Support/TargetRegistry.h"
25 
26 using namespace llvm;
27 
28 #define GET_INSTRINFO_CTOR_DTOR
29 #include "LanaiGenInstrInfo.inc"
30 
31 LanaiInstrInfo::LanaiInstrInfo()
32     : LanaiGenInstrInfo(Lanai::ADJCALLSTACKDOWN, Lanai::ADJCALLSTACKUP),
33       RegisterInfo() {}
34 
35 void LanaiInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
36                                  MachineBasicBlock::iterator Position,
37                                  const DebugLoc &DL,
38                                  unsigned DestinationRegister,
39                                  unsigned SourceRegister,
40                                  bool KillSource) const {
41   if (!Lanai::GPRRegClass.contains(DestinationRegister, SourceRegister)) {
42     llvm_unreachable("Impossible reg-to-reg copy");
43   }
44 
45   BuildMI(MBB, Position, DL, get(Lanai::OR_I_LO), DestinationRegister)
46       .addReg(SourceRegister, getKillRegState(KillSource))
47       .addImm(0);
48 }
49 
50 void LanaiInstrInfo::storeRegToStackSlot(
51     MachineBasicBlock &MBB, MachineBasicBlock::iterator Position,
52     unsigned SourceRegister, bool IsKill, int FrameIndex,
53     const TargetRegisterClass *RegisterClass,
54     const TargetRegisterInfo *RegisterInfo) const {
55   DebugLoc DL;
56   if (Position != MBB.end()) {
57     DL = Position->getDebugLoc();
58   }
59 
60   if (!Lanai::GPRRegClass.hasSubClassEq(RegisterClass)) {
61     llvm_unreachable("Can't store this register to stack slot");
62   }
63   BuildMI(MBB, Position, DL, get(Lanai::SW_RI))
64       .addReg(SourceRegister, getKillRegState(IsKill))
65       .addFrameIndex(FrameIndex)
66       .addImm(0)
67       .addImm(LPAC::ADD);
68 }
69 
70 void LanaiInstrInfo::loadRegFromStackSlot(
71     MachineBasicBlock &MBB, MachineBasicBlock::iterator Position,
72     unsigned DestinationRegister, int FrameIndex,
73     const TargetRegisterClass *RegisterClass,
74     const TargetRegisterInfo *RegisterInfo) const {
75   DebugLoc DL;
76   if (Position != MBB.end()) {
77     DL = Position->getDebugLoc();
78   }
79 
80   if (!Lanai::GPRRegClass.hasSubClassEq(RegisterClass)) {
81     llvm_unreachable("Can't load this register from stack slot");
82   }
83   BuildMI(MBB, Position, DL, get(Lanai::LDW_RI), DestinationRegister)
84       .addFrameIndex(FrameIndex)
85       .addImm(0)
86       .addImm(LPAC::ADD);
87 }
88 
89 bool LanaiInstrInfo::areMemAccessesTriviallyDisjoint(MachineInstr *MIa,
90                                                      MachineInstr *MIb,
91                                                      AliasAnalysis *AA) const {
92   assert(MIa && MIa->mayLoadOrStore() && "MIa must be a load or store.");
93   assert(MIb && MIb->mayLoadOrStore() && "MIb must be a load or store.");
94 
95   if (MIa->hasUnmodeledSideEffects() || MIb->hasUnmodeledSideEffects() ||
96       MIa->hasOrderedMemoryRef() || MIb->hasOrderedMemoryRef())
97     return false;
98 
99   // Retrieve the base register, offset from the base register and width. Width
100   // is the size of memory that is being loaded/stored (e.g. 1, 2, 4).  If
101   // base registers are identical, and the offset of a lower memory access +
102   // the width doesn't overlap the offset of a higher memory access,
103   // then the memory accesses are different.
104   const TargetRegisterInfo *TRI = &getRegisterInfo();
105   unsigned BaseRegA = 0, BaseRegB = 0;
106   int64_t OffsetA = 0, OffsetB = 0;
107   unsigned int WidthA = 0, WidthB = 0;
108   if (getMemOpBaseRegImmOfsWidth(MIa, BaseRegA, OffsetA, WidthA, TRI) &&
109       getMemOpBaseRegImmOfsWidth(MIb, BaseRegB, OffsetB, WidthB, TRI)) {
110     if (BaseRegA == BaseRegB) {
111       int LowOffset = std::min(OffsetA, OffsetB);
112       int HighOffset = std::max(OffsetA, OffsetB);
113       int LowWidth = (LowOffset == OffsetA) ? WidthA : WidthB;
114       if (LowOffset + LowWidth <= HighOffset)
115         return true;
116     }
117   }
118   return false;
119 }
120 
121 bool LanaiInstrInfo::expandPostRAPseudo(MachineBasicBlock::iterator MI) const {
122   return false;
123 }
124 
125 static LPCC::CondCode GetOppositeBranchCondition(LPCC::CondCode CC) {
126   switch (CC) {
127   case LPCC::ICC_T: //  true
128     return LPCC::ICC_F;
129   case LPCC::ICC_F: //  false
130     return LPCC::ICC_T;
131   case LPCC::ICC_HI: //  high
132     return LPCC::ICC_LS;
133   case LPCC::ICC_LS: //  low or same
134     return LPCC::ICC_HI;
135   case LPCC::ICC_CC: //  carry cleared
136     return LPCC::ICC_CS;
137   case LPCC::ICC_CS: //  carry set
138     return LPCC::ICC_CC;
139   case LPCC::ICC_NE: //  not equal
140     return LPCC::ICC_EQ;
141   case LPCC::ICC_EQ: //  equal
142     return LPCC::ICC_NE;
143   case LPCC::ICC_VC: //  oVerflow cleared
144     return LPCC::ICC_VS;
145   case LPCC::ICC_VS: //  oVerflow set
146     return LPCC::ICC_VC;
147   case LPCC::ICC_PL: //  plus (note: 0 is "minus" too here)
148     return LPCC::ICC_MI;
149   case LPCC::ICC_MI: //  minus
150     return LPCC::ICC_PL;
151   case LPCC::ICC_GE: //  greater than or equal
152     return LPCC::ICC_LT;
153   case LPCC::ICC_LT: //  less than
154     return LPCC::ICC_GE;
155   case LPCC::ICC_GT: //  greater than
156     return LPCC::ICC_LE;
157   case LPCC::ICC_LE: //  less than or equal
158     return LPCC::ICC_GT;
159   default:
160     llvm_unreachable("Invalid condtional code");
161   }
162 }
163 
164 // The AnalyzeBranch function is used to examine conditional instructions and
165 // remove unnecessary instructions. This method is used by BranchFolder and
166 // IfConverter machine function passes to improve the CFG.
167 // - TrueBlock is set to the destination if condition evaluates true (it is the
168 //   nullptr if the destination is the fall-through branch);
169 // - FalseBlock is set to the destination if condition evaluates to false (it
170 //   is the nullptr if the branch is unconditional);
171 // - condition is populated with machine operands needed to generate the branch
172 //   to insert in InsertBranch;
173 // Returns: false if branch could successfully be analyzed.
174 bool LanaiInstrInfo::AnalyzeBranch(MachineBasicBlock &MBB,
175                                    MachineBasicBlock *&TrueBlock,
176                                    MachineBasicBlock *&FalseBlock,
177                                    SmallVectorImpl<MachineOperand> &Condition,
178                                    bool AllowModify) const {
179   // Iterator to current instruction being considered.
180   MachineBasicBlock::iterator Instruction = MBB.end();
181 
182   // Start from the bottom of the block and work up, examining the
183   // terminator instructions.
184   while (Instruction != MBB.begin()) {
185     --Instruction;
186 
187     // Skip over debug values.
188     if (Instruction->isDebugValue())
189       continue;
190 
191     // Working from the bottom, when we see a non-terminator
192     // instruction, we're done.
193     if (!isUnpredicatedTerminator(*Instruction))
194       break;
195 
196     // A terminator that isn't a branch can't easily be handled
197     // by this analysis.
198     if (!Instruction->isBranch())
199       return true;
200 
201     // Handle unconditional branches.
202     if (Instruction->getOpcode() == Lanai::BT) {
203       if (!AllowModify) {
204         TrueBlock = Instruction->getOperand(0).getMBB();
205         continue;
206       }
207 
208       // If the block has any instructions after a branch, delete them.
209       while (std::next(Instruction) != MBB.end()) {
210         std::next(Instruction)->eraseFromParent();
211       }
212 
213       Condition.clear();
214       FalseBlock = nullptr;
215 
216       // Delete the jump if it's equivalent to a fall-through.
217       if (MBB.isLayoutSuccessor(Instruction->getOperand(0).getMBB())) {
218         TrueBlock = nullptr;
219         Instruction->eraseFromParent();
220         Instruction = MBB.end();
221         continue;
222       }
223 
224       // TrueBlock is used to indicate the unconditional destination.
225       TrueBlock = Instruction->getOperand(0).getMBB();
226       continue;
227     }
228 
229     // Handle conditional branches
230     unsigned Opcode = Instruction->getOpcode();
231     if (Opcode != Lanai::BRCC)
232       return true; // Unknown opcode.
233 
234     // Multiple conditional branches are not handled here so only proceed if
235     // there are no conditions enqueued.
236     if (Condition.empty()) {
237       LPCC::CondCode BranchCond =
238           static_cast<LPCC::CondCode>(Instruction->getOperand(1).getImm());
239 
240       // TrueBlock is the target of the previously seen unconditional branch.
241       FalseBlock = TrueBlock;
242       TrueBlock = Instruction->getOperand(0).getMBB();
243       Condition.push_back(MachineOperand::CreateImm(BranchCond));
244       continue;
245     }
246 
247     // Multiple conditional branches are not handled.
248     return true;
249   }
250 
251   // Return false indicating branch successfully analyzed.
252   return false;
253 }
254 
255 // ReverseBranchCondition - Reverses the branch condition of the specified
256 // condition list, returning false on success and true if it cannot be
257 // reversed.
258 bool LanaiInstrInfo::ReverseBranchCondition(
259     SmallVectorImpl<llvm::MachineOperand> &Condition) const {
260   assert((Condition.size() == 1) &&
261          "Lanai branch conditions should have one component.");
262 
263   LPCC::CondCode BranchCond =
264       static_cast<LPCC::CondCode>(Condition[0].getImm());
265   Condition[0].setImm(GetOppositeBranchCondition(BranchCond));
266   return false;
267 }
268 
269 // Insert the branch with condition specified in condition and given targets
270 // (TrueBlock and FalseBlock). This function returns the number of machine
271 // instructions inserted.
272 unsigned LanaiInstrInfo::InsertBranch(MachineBasicBlock &MBB,
273                                       MachineBasicBlock *TrueBlock,
274                                       MachineBasicBlock *FalseBlock,
275                                       ArrayRef<MachineOperand> Condition,
276                                       const DebugLoc &DL) const {
277   // Shouldn't be a fall through.
278   assert(TrueBlock && "InsertBranch must not be told to insert a fallthrough");
279 
280   // If condition is empty then an unconditional branch is being inserted.
281   if (Condition.empty()) {
282     assert(!FalseBlock && "Unconditional branch with multiple successors!");
283     BuildMI(&MBB, DL, get(Lanai::BT)).addMBB(TrueBlock);
284     return 1;
285   }
286 
287   // Else a conditional branch is inserted.
288   assert((Condition.size() == 1) &&
289          "Lanai branch conditions should have one component.");
290   unsigned ConditionalCode = Condition[0].getImm();
291   BuildMI(&MBB, DL, get(Lanai::BRCC)).addMBB(TrueBlock).addImm(ConditionalCode);
292 
293   // If no false block, then false behavior is fall through and no branch needs
294   // to be inserted.
295   if (!FalseBlock)
296     return 1;
297 
298   BuildMI(&MBB, DL, get(Lanai::BT)).addMBB(FalseBlock);
299   return 2;
300 }
301 
302 unsigned LanaiInstrInfo::RemoveBranch(MachineBasicBlock &MBB) const {
303   MachineBasicBlock::iterator Instruction = MBB.end();
304   unsigned Count = 0;
305 
306   while (Instruction != MBB.begin()) {
307     --Instruction;
308     if (Instruction->isDebugValue())
309       continue;
310     if (Instruction->getOpcode() != Lanai::BT &&
311         Instruction->getOpcode() != Lanai::BRCC) {
312       break;
313     }
314 
315     // Remove the branch.
316     Instruction->eraseFromParent();
317     Instruction = MBB.end();
318     ++Count;
319   }
320 
321   return Count;
322 }
323 
324 unsigned LanaiInstrInfo::isLoadFromStackSlot(const MachineInstr *MI,
325                                              int &FrameIndex) const {
326   if (MI->getOpcode() == Lanai::LDW_RI)
327     if (MI->getOperand(1).isFI() && MI->getOperand(2).isImm() &&
328         MI->getOperand(2).getImm() == 0) {
329       FrameIndex = MI->getOperand(1).getIndex();
330       return MI->getOperand(0).getReg();
331     }
332   return 0;
333 }
334 
335 unsigned LanaiInstrInfo::isLoadFromStackSlotPostFE(const MachineInstr *MI,
336                                                    int &FrameIndex) const {
337   if (MI->getOpcode() == Lanai::LDW_RI) {
338     unsigned Reg;
339     if ((Reg = isLoadFromStackSlot(MI, FrameIndex)))
340       return Reg;
341     // Check for post-frame index elimination operations
342     const MachineMemOperand *Dummy;
343     return hasLoadFromStackSlot(MI, Dummy, FrameIndex);
344   }
345   return 0;
346 }
347 
348 unsigned LanaiInstrInfo::isStoreToStackSlot(const MachineInstr *MI,
349                                             int &FrameIndex) const {
350   if (MI->getOpcode() == Lanai::SW_RI)
351     if (MI->getOperand(0).isFI() && MI->getOperand(1).isImm() &&
352         MI->getOperand(1).getImm() == 0) {
353       FrameIndex = MI->getOperand(0).getIndex();
354       return MI->getOperand(2).getReg();
355     }
356   return 0;
357 }
358 
359 bool LanaiInstrInfo::getMemOpBaseRegImmOfsWidth(
360     MachineInstr *LdSt, unsigned &BaseReg, int64_t &Offset, unsigned &Width,
361     const TargetRegisterInfo *TRI) const {
362   // Handle only loads/stores with base register followed by immediate offset
363   // and with add as ALU op.
364   if (LdSt->getNumOperands() != 4)
365     return false;
366   if (!LdSt->getOperand(1).isReg() || !LdSt->getOperand(2).isImm() ||
367       !(LdSt->getOperand(3).isImm() &&
368         LdSt->getOperand(3).getImm() == LPAC::ADD))
369     return false;
370 
371   switch (LdSt->getOpcode()) {
372   default:
373     return false;
374   case Lanai::LDW_RI:
375   case Lanai::LDW_RR:
376   case Lanai::SW_RR:
377   case Lanai::SW_RI:
378     Width = 4;
379     break;
380   case Lanai::LDHs_RI:
381   case Lanai::LDHz_RI:
382   case Lanai::STH_RI:
383     Width = 2;
384     break;
385   case Lanai::LDBs_RI:
386   case Lanai::LDBz_RI:
387   case Lanai::STB_RI:
388     Width = 1;
389     break;
390   }
391 
392   BaseReg = LdSt->getOperand(1).getReg();
393   Offset = LdSt->getOperand(2).getImm();
394   return true;
395 }
396 
397 bool LanaiInstrInfo::getMemOpBaseRegImmOfs(
398     MachineInstr *LdSt, unsigned &BaseReg, int64_t &Offset,
399     const TargetRegisterInfo *TRI) const {
400   switch (LdSt->getOpcode()) {
401   default:
402     return false;
403   case Lanai::LDW_RI:
404   case Lanai::LDW_RR:
405   case Lanai::SW_RR:
406   case Lanai::SW_RI:
407   case Lanai::LDHs_RI:
408   case Lanai::LDHz_RI:
409   case Lanai::STH_RI:
410   case Lanai::LDBs_RI:
411   case Lanai::LDBz_RI:
412     unsigned Width;
413     return getMemOpBaseRegImmOfsWidth(LdSt, BaseReg, Offset, Width, TRI);
414   }
415 }
416