include/llvm/CodeGen/FastISel.h

   1 //===-- FastISel.h - Definition of the FastISel class ---*- 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 /// \file
  11 /// This file defines the FastISel class.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_FASTISEL_H
  16 #define LLVM_CODEGEN_FASTISEL_H
  17
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/CodeGen/MachineBasicBlock.h"
  20
  21 namespace llvm {
  22
  23 class AllocaInst;
  24 class Constant;
  25 class ConstantFP;
  26 class CallInst;
  27 class DataLayout;
  28 class FunctionLoweringInfo;
  29 class Instruction;
  30 class LoadInst;
  31 class MVT;
  32 class MachineConstantPool;
  33 class MachineFrameInfo;
  34 class MachineFunction;
  35 class MachineInstr;
  36 class MachineRegisterInfo;
  37 class TargetInstrInfo;
  38 class TargetLibraryInfo;
  39 class TargetLowering;
  40 class TargetMachine;
  41 class TargetRegisterClass;
  42 class TargetRegisterInfo;
  43 class User;
  44 class Value;
  45
  46 /// This is a fast-path instruction selection class that generates poor code and
  47 /// doesn't support illegal types or non-trivial lowering, but runs quickly.
  48 class FastISel {
  49 protected:
  50   DenseMap<const Value *, unsigned> LocalValueMap;
  51   FunctionLoweringInfo &FuncInfo;
  52   MachineRegisterInfo &MRI;
  53   MachineFrameInfo &MFI;
  54   MachineConstantPool &MCP;
  55   DebugLoc DbgLoc;
  56   const TargetMachine &TM;
  57   const DataLayout &DL;
  58   const TargetInstrInfo &TII;
  59   const TargetLowering &TLI;
  60   const TargetRegisterInfo &TRI;
  61   const TargetLibraryInfo *LibInfo;
  62
  63   /// The position of the last instruction for materializing constants for use
  64   /// in the current block. It resets to EmitStartPt when it makes sense (for
  65   /// example, it's usually profitable to avoid function calls between the
  66   /// definition and the use)
  67   MachineInstr *LastLocalValue;
  68
  69   /// The top most instruction in the current block that is allowed for emitting
  70   /// local variables. LastLocalValue resets to EmitStartPt when it makes sense
  71   /// (for example, on function calls)
  72   MachineInstr *EmitStartPt;
  73
  74 public:
  75   /// Return the position of the last instruction emitted for materializing
  76   /// constants for use in the current block.
  77   MachineInstr *getLastLocalValue() { return LastLocalValue; }
  78
  79   /// Update the position of the last instruction emitted for materializing
  80   /// constants for use in the current block.
  81   void setLastLocalValue(MachineInstr *I) {
  82     EmitStartPt = I;
  83     LastLocalValue = I;
  84   }
  85
  86   /// Set the current block to which generated machine instructions will be
  87   /// appended, and clear the local CSE map.
  88   void startNewBlock();
  89
  90   /// Return current debug location information.
  91   DebugLoc getCurDebugLoc() const { return DbgLoc; }
  92
  93   /// Do "fast" instruction selection for function arguments and append machine
  94   /// instructions to the current block. Return true if it is successful.
  95   bool LowerArguments();
  96
  97   /// Do "fast" instruction selection for the given LLVM IR instruction, and
  98   /// append generated machine instructions to the current block. Return true if
  99   /// selection was successful.
 100   bool SelectInstruction(const Instruction *I);
 101
 102   /// Do "fast" instruction selection for the given LLVM IR operator
 103   /// (Instruction or ConstantExpr), and append generated machine instructions
 104   /// to the current block. Return true if selection was successful.
 105   bool SelectOperator(const User *I, unsigned Opcode);
 106
 107   /// Create a virtual register and arrange for it to be assigned the value for
 108   /// the given LLVM value.
 109   unsigned getRegForValue(const Value *V);
 110
 111   /// Look up the value to see if its value is already cached in a register. It
 112   /// may be defined by instructions across blocks or defined locally.
 113   unsigned lookUpRegForValue(const Value *V);
 114
 115   /// This is a wrapper around getRegForValue that also takes care of truncating
 116   /// or sign-extending the given getelementptr index value.
 117   std::pair<unsigned, bool> getRegForGEPIndex(const Value *V);
 118
 119   /// \brief We're checking to see if we can fold \p LI into \p FoldInst. Note
 120   /// that we could have a sequence where multiple LLVM IR instructions are
 121   /// folded into the same machineinstr.  For example we could have:
 122   ///
 123   ///   A: x = load i32 *P
 124   ///   B: y = icmp A, 42
 125   ///   C: br y, ...
 126   ///
 127   /// In this scenario, \p LI is "A", and \p FoldInst is "C".  We know about "B"
 128   /// (and any other folded instructions) because it is between A and C.
 129   ///
 130   /// If we succeed folding, return true.
 131   bool tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst);
 132
 133   /// \brief The specified machine instr operand is a vreg, and that vreg is
 134   /// being provided by the specified load instruction.  If possible, try to
 135   /// fold the load as an operand to the instruction, returning true if
 136   /// possible.
 137   ///
 138   /// This method should be implemented by targets.
 139   virtual bool tryToFoldLoadIntoMI(MachineInstr * /*MI*/, unsigned /*OpNo*/,
 140                                    const LoadInst * /*LI*/) {
 141     return false;
 142   }
 143
 144   /// Reset InsertPt to prepare for inserting instructions into the current
 145   /// block.
 146   void recomputeInsertPt();
 147
 148   /// Remove all dead instructions between the I and E.
 149   void removeDeadCode(MachineBasicBlock::iterator I,
 150                       MachineBasicBlock::iterator E);
 151
 152   struct SavePoint {
 153     MachineBasicBlock::iterator InsertPt;
 154     DebugLoc DL;
 155   };
 156
 157   /// Prepare InsertPt to begin inserting instructions into the local value area
 158   /// and return the old insert position.
 159   SavePoint enterLocalValueArea();
 160
 161   /// Reset InsertPt to the given old insert position.
 162   void leaveLocalValueArea(SavePoint Old);
 163
 164   virtual ~FastISel();
 165
 166 protected:
 167   explicit FastISel(FunctionLoweringInfo &funcInfo,
 168                     const TargetLibraryInfo *libInfo);
 169
 170   /// This method is called by target-independent code when the normal FastISel
 171   /// process fails to select an instruction.  This gives targets a chance to
 172   /// emit code for anything that doesn't fit into FastISel's framework. It
 173   /// returns true if it was successful.
 174   virtual bool
 175   TargetSelectInstruction(const Instruction *I) = 0;
 176
 177   /// This method is called by target-independent code to do target specific
 178   /// argument lowering. It returns true if it was successful.
 179   virtual bool FastLowerArguments();
 180
 181   /// This method is called by target-independent code to request that an
 182   /// instruction with the given type and opcode be emitted.
 183   virtual unsigned FastEmit_(MVT VT,
 184                              MVT RetVT,
 185                              unsigned Opcode);
 186
 187   /// This method is called by target-independent code to request that an
 188   /// instruction with the given type, opcode, and register operand be emitted.
 189   virtual unsigned FastEmit_r(MVT VT,
 190                               MVT RetVT,
 191                               unsigned Opcode,
 192                               unsigned Op0, bool Op0IsKill);
 193
 194   /// This method is called by target-independent code to request that an
 195   /// instruction with the given type, opcode, and register operands be emitted.
 196   virtual unsigned FastEmit_rr(MVT VT,
 197                                MVT RetVT,
 198                                unsigned Opcode,
 199                                unsigned Op0, bool Op0IsKill,
 200                                unsigned Op1, bool Op1IsKill);
 201
 202   /// This method is called by target-independent code to request that an
 203   /// instruction with the given type, opcode, and register and immediate
 204   /// operands be emitted.
 205   virtual unsigned FastEmit_ri(MVT VT,
 206                                MVT RetVT,
 207                                unsigned Opcode,
 208                                unsigned Op0, bool Op0IsKill,
 209                                uint64_t Imm);
 210
 211   /// This method is called by target-independent code to request that an
 212   /// instruction with the given type, opcode, and register and floating-point
 213   /// immediate operands be emitted.
 214   virtual unsigned FastEmit_rf(MVT VT,
 215                                MVT RetVT,
 216                                unsigned Opcode,
 217                                unsigned Op0, bool Op0IsKill,
 218                                const ConstantFP *FPImm);
 219
 220   /// This method is called by target-independent code to request that an
 221   /// instruction with the given type, opcode, and register and immediate
 222   /// operands be emitted.
 223   virtual unsigned FastEmit_rri(MVT VT,
 224                                 MVT RetVT,
 225                                 unsigned Opcode,
 226                                 unsigned Op0, bool Op0IsKill,
 227                                 unsigned Op1, bool Op1IsKill,
 228                                 uint64_t Imm);
 229
 230   /// \brief This method is a wrapper of FastEmit_ri.
 231   ///
 232   /// It first tries to emit an instruction with an immediate operand using
 233   /// FastEmit_ri.  If that fails, it materializes the immediate into a register
 234   /// and try FastEmit_rr instead.
 235   unsigned FastEmit_ri_(MVT VT,
 236                         unsigned Opcode,
 237                         unsigned Op0, bool Op0IsKill,
 238                         uint64_t Imm, MVT ImmType);
 239
 240   /// This method is called by target-independent code to request that an
 241   /// instruction with the given type, opcode, and immediate operand be emitted.
 242   virtual unsigned FastEmit_i(MVT VT,
 243                               MVT RetVT,
 244                               unsigned Opcode,
 245                               uint64_t Imm);
 246
 247   /// This method is called by target-independent code to request that an
 248   /// instruction with the given type, opcode, and floating-point immediate
 249   /// operand be emitted.
 250   virtual unsigned FastEmit_f(MVT VT,
 251                               MVT RetVT,
 252                               unsigned Opcode,
 253                               const ConstantFP *FPImm);
 254
 255   /// Emit a MachineInstr with no operands and a result register in the given
 256   /// register class.
 257   unsigned FastEmitInst_(unsigned MachineInstOpcode,
 258                          const TargetRegisterClass *RC);
 259
 260   /// Emit a MachineInstr with one register operand and a result register in the
 261   /// given register class.
 262   unsigned FastEmitInst_r(unsigned MachineInstOpcode,
 263                           const TargetRegisterClass *RC,
 264                           unsigned Op0, bool Op0IsKill);
 265
 266   /// Emit a MachineInstr with two register operands and a result register in
 267   /// the given register class.
 268   unsigned FastEmitInst_rr(unsigned MachineInstOpcode,
 269                            const TargetRegisterClass *RC,
 270                            unsigned Op0, bool Op0IsKill,
 271                            unsigned Op1, bool Op1IsKill);
 272
 273   /// Emit a MachineInstr with three register operands and a result register in
 274   /// the given register class.
 275   unsigned FastEmitInst_rrr(unsigned MachineInstOpcode,
 276                            const TargetRegisterClass *RC,
 277                            unsigned Op0, bool Op0IsKill,
 278                            unsigned Op1, bool Op1IsKill,
 279                            unsigned Op2, bool Op2IsKill);
 280
 281   /// Emit a MachineInstr with a register operand, an immediate, and a result
 282   /// register in the given register class.
 283   unsigned FastEmitInst_ri(unsigned MachineInstOpcode,
 284                            const TargetRegisterClass *RC,
 285                            unsigned Op0, bool Op0IsKill,
 286                            uint64_t Imm);
 287
 288   /// Emit a MachineInstr with one register operand and two immediate operands.
 289   unsigned FastEmitInst_rii(unsigned MachineInstOpcode,
 290                            const TargetRegisterClass *RC,
 291                            unsigned Op0, bool Op0IsKill,
 292                            uint64_t Imm1, uint64_t Imm2);
 293
 294   /// Emit a MachineInstr with two register operands and a result register in
 295   /// the given register class.
 296   unsigned FastEmitInst_rf(unsigned MachineInstOpcode,
 297                            const TargetRegisterClass *RC,
 298                            unsigned Op0, bool Op0IsKill,
 299                            const ConstantFP *FPImm);
 300
 301   /// Emit a MachineInstr with two register operands, an immediate, and a result
 302   /// register in the given register class.
 303   unsigned FastEmitInst_rri(unsigned MachineInstOpcode,
 304                             const TargetRegisterClass *RC,
 305                             unsigned Op0, bool Op0IsKill,
 306                             unsigned Op1, bool Op1IsKill,
 307                             uint64_t Imm);
 308
 309   /// Emit a MachineInstr with two register operands, two immediates operands,
 310   /// and a result register in the given register class.
 311   unsigned FastEmitInst_rrii(unsigned MachineInstOpcode,
 312                              const TargetRegisterClass *RC,
 313                              unsigned Op0, bool Op0IsKill,
 314                              unsigned Op1, bool Op1IsKill,
 315                              uint64_t Imm1, uint64_t Imm2);
 316
 317   /// Emit a MachineInstr with a single immediate operand, and a result register
 318   /// in the given register class.
 319   unsigned FastEmitInst_i(unsigned MachineInstrOpcode,
 320                           const TargetRegisterClass *RC,
 321                           uint64_t Imm);
 322
 323   /// Emit a MachineInstr with a two immediate operands.
 324   unsigned FastEmitInst_ii(unsigned MachineInstrOpcode,
 325                           const TargetRegisterClass *RC,
 326                           uint64_t Imm1, uint64_t Imm2);
 327
 328   /// Emit a MachineInstr for an extract_subreg from a specified index of a
 329   /// superregister to a specified type.
 330   unsigned FastEmitInst_extractsubreg(MVT RetVT,
 331                                       unsigned Op0, bool Op0IsKill,
 332                                       uint32_t Idx);
 333
 334   /// Emit MachineInstrs to compute the value of Op with all but the least
 335   /// significant bit set to zero.
 336   unsigned FastEmitZExtFromI1(MVT VT,
 337                               unsigned Op0, bool Op0IsKill);
 338
 339   /// Emit an unconditional branch to the given block, unless it is the
 340   /// immediate (fall-through) successor, and update the CFG.
 341   void FastEmitBranch(MachineBasicBlock *MBB, DebugLoc DL);
 342
 343   void UpdateValueMap(const Value* I, unsigned Reg, unsigned NumRegs = 1);
 344
 345   unsigned createResultReg(const TargetRegisterClass *RC);
 346
 347   /// Try to constrain Op so that it is usable by argument OpNum of the provided
 348   /// MCInstrDesc. If this fails, create a new virtual register in the correct
 349   /// class and COPY the value there.
 350   unsigned constrainOperandRegClass(const MCInstrDesc &II, unsigned Op,
 351                                     unsigned OpNum);
 352
 353   /// Emit a constant in a register using target-specific logic, such as
 354   /// constant pool loads.
 355   virtual unsigned TargetMaterializeConstant(const Constant* C) {
 356     return 0;
 357   }
 358
 359   /// Emit an alloca address in a register using target-specific logic.
 360   virtual unsigned TargetMaterializeAlloca(const AllocaInst* C) {
 361     return 0;
 362   }
 363
 364   virtual unsigned TargetMaterializeFloatZero(const ConstantFP* CF) {
 365     return 0;
 366   }
 367
 368   /// \brief Check if \c Add is an add that can be safely folded into \c GEP.
 369   ///
 370   /// \c Add can be folded into \c GEP if:
 371   /// - \c Add is an add,
 372   /// - \c Add's size matches \c GEP's,
 373   /// - \c Add is in the same basic block as \c GEP, and
 374   /// - \c Add has a constant operand.
 375   bool canFoldAddIntoGEP(const User *GEP, const Value *Add);
 376
 377   /// Test whether the given value has exactly one use.
 378   bool hasTrivialKill(const Value *V) const;
 379
 380   /// \brief Create a machine mem operand from the given instruction.
 381   MachineMemOperand *createMachineMemOperandFor(const Instruction *I) const;
 382
 383 private:
 384   bool SelectBinaryOp(const User *I, unsigned ISDOpcode);
 385
 386   bool SelectFNeg(const User *I);
 387
 388   bool SelectGetElementPtr(const User *I);
 389
 390   bool SelectStackmap(const CallInst *I);
 391   bool SelectCall(const User *I);
 392
 393   bool SelectBitCast(const User *I);
 394
 395   bool SelectCast(const User *I, unsigned Opcode);
 396
 397   bool SelectExtractValue(const User *I);
 398
 399   bool SelectInsertValue(const User *I);
 400
 401   /// \brief Handle PHI nodes in successor blocks.
 402   ///
 403   /// Emit code to ensure constants are copied into registers when needed.
 404   /// Remember the virtual registers that need to be added to the Machine PHI
 405   /// nodes as input.  We cannot just directly add them, because expansion might
 406   /// result in multiple MBB's for one BB.  As such, the start of the BB might
 407   /// correspond to a different MBB than the end.
 408   bool HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB);
 409
 410   /// Helper for getRegForVale. This function is called when the value isn't
 411   /// already available in a register and must be materialized with new
 412   /// instructions.
 413   unsigned materializeRegForValue(const Value *V, MVT VT);
 414
 415   /// Clears LocalValueMap and moves the area for the new local variables to the
 416   /// beginning of the block. It helps to avoid spilling cached variables across
 417   /// heavy instructions like calls.
 418   void flushLocalValueMap();
 419
 420   bool addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
 421                            const CallInst *CI, unsigned StartIdx);
 422 };
 423
 424 }
 425
 426 #endif