Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 1 | //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===// |
Misha Brukman | edf128a | 2005-04-21 22:36:52 +0000 | [diff] [blame] | 2 | // |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Misha Brukman | edf128a | 2005-04-21 22:36:52 +0000 | [diff] [blame] | 7 | // |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This implements the SelectionDAGISel class. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #define DEBUG_TYPE "isel" |
Evan Cheng | 381cb07 | 2008-08-08 07:27:28 +0000 | [diff] [blame] | 15 | #include "llvm/CodeGen/SelectionDAGISel.h" |
Dan Gohman | f0cbcd4 | 2008-09-03 16:12:24 +0000 | [diff] [blame] | 16 | #include "SelectionDAGBuild.h" |
Anton Korobeynikov | 5502bf6 | 2007-04-04 21:14:49 +0000 | [diff] [blame] | 17 | #include "llvm/ADT/BitVector.h" |
Jim Laskey | c7c3f11 | 2006-10-16 20:52:31 +0000 | [diff] [blame] | 18 | #include "llvm/Analysis/AliasAnalysis.h" |
Anton Korobeynikov | 5502bf6 | 2007-04-04 21:14:49 +0000 | [diff] [blame] | 19 | #include "llvm/Constants.h" |
Chris Lattner | adf6a96 | 2005-05-13 18:50:42 +0000 | [diff] [blame] | 20 | #include "llvm/CallingConv.h" |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 21 | #include "llvm/DerivedTypes.h" |
| 22 | #include "llvm/Function.h" |
Chris Lattner | 36ce691 | 2005-11-29 06:21:05 +0000 | [diff] [blame] | 23 | #include "llvm/GlobalVariable.h" |
Chris Lattner | ce7518c | 2006-01-26 22:24:51 +0000 | [diff] [blame] | 24 | #include "llvm/InlineAsm.h" |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 25 | #include "llvm/Instructions.h" |
| 26 | #include "llvm/Intrinsics.h" |
Jim Laskey | 43970fe | 2006-03-23 18:06:46 +0000 | [diff] [blame] | 27 | #include "llvm/IntrinsicInst.h" |
Reid Spencer | 5694b6e | 2007-04-09 06:17:21 +0000 | [diff] [blame] | 28 | #include "llvm/ParameterAttributes.h" |
Dan Gohman | 78eca17 | 2008-08-19 22:33:34 +0000 | [diff] [blame] | 29 | #include "llvm/CodeGen/FastISel.h" |
Gordon Henriksen | 5a29c9e | 2008-08-17 12:56:54 +0000 | [diff] [blame] | 30 | #include "llvm/CodeGen/GCStrategy.h" |
Gordon Henriksen | 5eca075 | 2008-08-17 18:44:35 +0000 | [diff] [blame] | 31 | #include "llvm/CodeGen/GCMetadata.h" |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 32 | #include "llvm/CodeGen/MachineFunction.h" |
| 33 | #include "llvm/CodeGen/MachineFrameInfo.h" |
| 34 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
Chris Lattner | 84bc542 | 2007-12-31 04:13:23 +0000 | [diff] [blame] | 35 | #include "llvm/CodeGen/MachineJumpTableInfo.h" |
| 36 | #include "llvm/CodeGen/MachineModuleInfo.h" |
| 37 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Evan Cheng | 381cb07 | 2008-08-08 07:27:28 +0000 | [diff] [blame] | 38 | #include "llvm/CodeGen/ScheduleDAG.h" |
Jim Laskey | eb577ba | 2006-08-02 12:30:23 +0000 | [diff] [blame] | 39 | #include "llvm/CodeGen/SchedulerRegistry.h" |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 40 | #include "llvm/CodeGen/SelectionDAG.h" |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 41 | #include "llvm/Target/TargetRegisterInfo.h" |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 42 | #include "llvm/Target/TargetData.h" |
| 43 | #include "llvm/Target/TargetFrameInfo.h" |
| 44 | #include "llvm/Target/TargetInstrInfo.h" |
| 45 | #include "llvm/Target/TargetLowering.h" |
| 46 | #include "llvm/Target/TargetMachine.h" |
Vladimir Prus | 1247291 | 2006-05-23 13:43:15 +0000 | [diff] [blame] | 47 | #include "llvm/Target/TargetOptions.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 48 | #include "llvm/Support/Compiler.h" |
Evan Cheng | db8d56b | 2008-06-30 20:45:06 +0000 | [diff] [blame] | 49 | #include "llvm/Support/Debug.h" |
| 50 | #include "llvm/Support/MathExtras.h" |
| 51 | #include "llvm/Support/Timer.h" |
Jeff Cohen | 7e88103 | 2006-02-24 02:52:40 +0000 | [diff] [blame] | 52 | #include <algorithm> |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 53 | using namespace llvm; |
| 54 | |
Chris Lattner | ead0d88 | 2008-06-17 06:09:18 +0000 | [diff] [blame] | 55 | static cl::opt<bool> |
Chris Lattner | 70587ea | 2008-07-10 23:37:50 +0000 | [diff] [blame] | 56 | EnableValueProp("enable-value-prop", cl::Hidden); |
| 57 | static cl::opt<bool> |
Duncan Sands | f00e74f | 2008-07-17 17:06:03 +0000 | [diff] [blame] | 58 | EnableLegalizeTypes("enable-legalize-types", cl::Hidden); |
Dan Gohman | 78eca17 | 2008-08-19 22:33:34 +0000 | [diff] [blame] | 59 | static cl::opt<bool> |
| 60 | EnableFastISel("fast-isel", cl::Hidden, |
| 61 | cl::desc("Enable the experimental \"fast\" instruction selector")); |
Dan Gohman | 3e697cf | 2008-08-20 00:47:54 +0000 | [diff] [blame] | 62 | static cl::opt<bool> |
Dan Gohman | 293d5f8 | 2008-09-09 22:06:46 +0000 | [diff] [blame] | 63 | EnableFastISelVerbose("fast-isel-verbose", cl::Hidden, |
| 64 | cl::desc("Enable verbose messages in the experimental \"fast\" " |
| 65 | "instruction selector")); |
| 66 | static cl::opt<bool> |
Dan Gohman | 4344a5d | 2008-09-09 23:05:00 +0000 | [diff] [blame] | 67 | EnableFastISelAbort("fast-isel-abort", cl::Hidden, |
| 68 | cl::desc("Enable abort calls when \"fast\" instruction fails")); |
Dan Gohman | 8a11053 | 2008-09-05 22:59:21 +0000 | [diff] [blame] | 69 | static cl::opt<bool> |
| 70 | SchedLiveInCopies("schedule-livein-copies", |
| 71 | cl::desc("Schedule copies of livein registers"), |
| 72 | cl::init(false)); |
Chris Lattner | ead0d88 | 2008-06-17 06:09:18 +0000 | [diff] [blame] | 73 | |
Chris Lattner | da8abb0 | 2005-09-01 18:44:10 +0000 | [diff] [blame] | 74 | #ifndef NDEBUG |
Chris Lattner | 7944d9d | 2005-01-12 03:41:21 +0000 | [diff] [blame] | 75 | static cl::opt<bool> |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 76 | ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden, |
| 77 | cl::desc("Pop up a window to show dags before the first " |
| 78 | "dag combine pass")); |
| 79 | static cl::opt<bool> |
| 80 | ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden, |
| 81 | cl::desc("Pop up a window to show dags before legalize types")); |
| 82 | static cl::opt<bool> |
| 83 | ViewLegalizeDAGs("view-legalize-dags", cl::Hidden, |
| 84 | cl::desc("Pop up a window to show dags before legalize")); |
| 85 | static cl::opt<bool> |
| 86 | ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden, |
| 87 | cl::desc("Pop up a window to show dags before the second " |
| 88 | "dag combine pass")); |
| 89 | static cl::opt<bool> |
Evan Cheng | a9c2091 | 2006-01-21 02:32:06 +0000 | [diff] [blame] | 90 | ViewISelDAGs("view-isel-dags", cl::Hidden, |
| 91 | cl::desc("Pop up a window to show isel dags as they are selected")); |
| 92 | static cl::opt<bool> |
| 93 | ViewSchedDAGs("view-sched-dags", cl::Hidden, |
| 94 | cl::desc("Pop up a window to show sched dags as they are processed")); |
Dan Gohman | 3e1a7ae | 2007-08-28 20:32:58 +0000 | [diff] [blame] | 95 | static cl::opt<bool> |
| 96 | ViewSUnitDAGs("view-sunit-dags", cl::Hidden, |
Chris Lattner | 5bab785 | 2008-01-25 17:24:52 +0000 | [diff] [blame] | 97 | cl::desc("Pop up a window to show SUnit dags after they are processed")); |
Chris Lattner | 7944d9d | 2005-01-12 03:41:21 +0000 | [diff] [blame] | 98 | #else |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 99 | static const bool ViewDAGCombine1 = false, |
| 100 | ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false, |
| 101 | ViewDAGCombine2 = false, |
| 102 | ViewISelDAGs = false, ViewSchedDAGs = false, |
| 103 | ViewSUnitDAGs = false; |
Chris Lattner | 7944d9d | 2005-01-12 03:41:21 +0000 | [diff] [blame] | 104 | #endif |
| 105 | |
Jim Laskey | eb577ba | 2006-08-02 12:30:23 +0000 | [diff] [blame] | 106 | //===---------------------------------------------------------------------===// |
| 107 | /// |
| 108 | /// RegisterScheduler class - Track the registration of instruction schedulers. |
| 109 | /// |
| 110 | //===---------------------------------------------------------------------===// |
| 111 | MachinePassRegistry RegisterScheduler::Registry; |
| 112 | |
| 113 | //===---------------------------------------------------------------------===// |
| 114 | /// |
| 115 | /// ISHeuristic command line option for instruction schedulers. |
| 116 | /// |
| 117 | //===---------------------------------------------------------------------===// |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 118 | static cl::opt<RegisterScheduler::FunctionPassCtor, false, |
| 119 | RegisterPassParser<RegisterScheduler> > |
| 120 | ISHeuristic("pre-RA-sched", |
| 121 | cl::init(&createDefaultScheduler), |
| 122 | cl::desc("Instruction schedulers available (before register" |
| 123 | " allocation):")); |
Jim Laskey | 13ec702 | 2006-08-01 14:21:23 +0000 | [diff] [blame] | 124 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 125 | static RegisterScheduler |
| 126 | defaultListDAGScheduler("default", " Best scheduler for the target", |
| 127 | createDefaultScheduler); |
Evan Cheng | 4ef1086 | 2006-01-23 07:01:07 +0000 | [diff] [blame] | 128 | |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 129 | namespace llvm { |
| 130 | //===--------------------------------------------------------------------===// |
Jim Laskey | 9373beb | 2006-08-01 19:14:14 +0000 | [diff] [blame] | 131 | /// createDefaultScheduler - This creates an instruction scheduler appropriate |
| 132 | /// for the target. |
| 133 | ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, |
| 134 | SelectionDAG *DAG, |
Evan Cheng | 4576f6d | 2008-07-01 18:05:03 +0000 | [diff] [blame] | 135 | MachineBasicBlock *BB, |
| 136 | bool Fast) { |
Jim Laskey | 9373beb | 2006-08-01 19:14:14 +0000 | [diff] [blame] | 137 | TargetLowering &TLI = IS->getTargetLowering(); |
| 138 | |
| 139 | if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) { |
Evan Cheng | 4576f6d | 2008-07-01 18:05:03 +0000 | [diff] [blame] | 140 | return createTDListDAGScheduler(IS, DAG, BB, Fast); |
Jim Laskey | 9373beb | 2006-08-01 19:14:14 +0000 | [diff] [blame] | 141 | } else { |
| 142 | assert(TLI.getSchedulingPreference() == |
| 143 | TargetLowering::SchedulingForRegPressure && "Unknown sched type!"); |
Evan Cheng | 4576f6d | 2008-07-01 18:05:03 +0000 | [diff] [blame] | 144 | return createBURRListDAGScheduler(IS, DAG, BB, Fast); |
Jim Laskey | 9373beb | 2006-08-01 19:14:14 +0000 | [diff] [blame] | 145 | } |
| 146 | } |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 147 | } |
| 148 | |
Evan Cheng | ff9b373 | 2008-01-30 18:18:23 +0000 | [diff] [blame] | 149 | // EmitInstrWithCustomInserter - This method should be implemented by targets |
| 150 | // that mark instructions with the 'usesCustomDAGSchedInserter' flag. These |
Chris Lattner | 025c39b | 2005-08-26 20:54:47 +0000 | [diff] [blame] | 151 | // instructions are special in various ways, which require special support to |
| 152 | // insert. The specified MachineInstr is created but not inserted into any |
| 153 | // basic blocks, and the scheduler passes ownership of it to this method. |
Evan Cheng | ff9b373 | 2008-01-30 18:18:23 +0000 | [diff] [blame] | 154 | MachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI, |
Chris Lattner | 025c39b | 2005-08-26 20:54:47 +0000 | [diff] [blame] | 155 | MachineBasicBlock *MBB) { |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 156 | cerr << "If a target marks an instruction with " |
| 157 | << "'usesCustomDAGSchedInserter', it must implement " |
Evan Cheng | ff9b373 | 2008-01-30 18:18:23 +0000 | [diff] [blame] | 158 | << "TargetLowering::EmitInstrWithCustomInserter!\n"; |
Chris Lattner | 025c39b | 2005-08-26 20:54:47 +0000 | [diff] [blame] | 159 | abort(); |
| 160 | return 0; |
| 161 | } |
| 162 | |
Dan Gohman | 8a11053 | 2008-09-05 22:59:21 +0000 | [diff] [blame] | 163 | /// EmitLiveInCopy - Emit a copy for a live in physical register. If the |
| 164 | /// physical register has only a single copy use, then coalesced the copy |
| 165 | /// if possible. |
| 166 | static void EmitLiveInCopy(MachineBasicBlock *MBB, |
| 167 | MachineBasicBlock::iterator &InsertPos, |
| 168 | unsigned VirtReg, unsigned PhysReg, |
| 169 | const TargetRegisterClass *RC, |
| 170 | DenseMap<MachineInstr*, unsigned> &CopyRegMap, |
| 171 | const MachineRegisterInfo &MRI, |
| 172 | const TargetRegisterInfo &TRI, |
| 173 | const TargetInstrInfo &TII) { |
| 174 | unsigned NumUses = 0; |
| 175 | MachineInstr *UseMI = NULL; |
| 176 | for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(VirtReg), |
| 177 | UE = MRI.use_end(); UI != UE; ++UI) { |
| 178 | UseMI = &*UI; |
| 179 | if (++NumUses > 1) |
| 180 | break; |
| 181 | } |
| 182 | |
| 183 | // If the number of uses is not one, or the use is not a move instruction, |
| 184 | // don't coalesce. Also, only coalesce away a virtual register to virtual |
| 185 | // register copy. |
| 186 | bool Coalesced = false; |
| 187 | unsigned SrcReg, DstReg; |
| 188 | if (NumUses == 1 && |
| 189 | TII.isMoveInstr(*UseMI, SrcReg, DstReg) && |
| 190 | TargetRegisterInfo::isVirtualRegister(DstReg)) { |
| 191 | VirtReg = DstReg; |
| 192 | Coalesced = true; |
| 193 | } |
| 194 | |
| 195 | // Now find an ideal location to insert the copy. |
| 196 | MachineBasicBlock::iterator Pos = InsertPos; |
| 197 | while (Pos != MBB->begin()) { |
| 198 | MachineInstr *PrevMI = prior(Pos); |
| 199 | DenseMap<MachineInstr*, unsigned>::iterator RI = CopyRegMap.find(PrevMI); |
| 200 | // copyRegToReg might emit multiple instructions to do a copy. |
| 201 | unsigned CopyDstReg = (RI == CopyRegMap.end()) ? 0 : RI->second; |
| 202 | if (CopyDstReg && !TRI.regsOverlap(CopyDstReg, PhysReg)) |
| 203 | // This is what the BB looks like right now: |
| 204 | // r1024 = mov r0 |
| 205 | // ... |
| 206 | // r1 = mov r1024 |
| 207 | // |
| 208 | // We want to insert "r1025 = mov r1". Inserting this copy below the |
| 209 | // move to r1024 makes it impossible for that move to be coalesced. |
| 210 | // |
| 211 | // r1025 = mov r1 |
| 212 | // r1024 = mov r0 |
| 213 | // ... |
| 214 | // r1 = mov 1024 |
| 215 | // r2 = mov 1025 |
| 216 | break; // Woot! Found a good location. |
| 217 | --Pos; |
| 218 | } |
| 219 | |
| 220 | TII.copyRegToReg(*MBB, Pos, VirtReg, PhysReg, RC, RC); |
| 221 | CopyRegMap.insert(std::make_pair(prior(Pos), VirtReg)); |
| 222 | if (Coalesced) { |
| 223 | if (&*InsertPos == UseMI) ++InsertPos; |
| 224 | MBB->erase(UseMI); |
| 225 | } |
| 226 | } |
| 227 | |
| 228 | /// EmitLiveInCopies - If this is the first basic block in the function, |
| 229 | /// and if it has live ins that need to be copied into vregs, emit the |
| 230 | /// copies into the block. |
| 231 | static void EmitLiveInCopies(MachineBasicBlock *EntryMBB, |
| 232 | const MachineRegisterInfo &MRI, |
| 233 | const TargetRegisterInfo &TRI, |
| 234 | const TargetInstrInfo &TII) { |
| 235 | if (SchedLiveInCopies) { |
| 236 | // Emit the copies at a heuristically-determined location in the block. |
| 237 | DenseMap<MachineInstr*, unsigned> CopyRegMap; |
| 238 | MachineBasicBlock::iterator InsertPos = EntryMBB->begin(); |
| 239 | for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(), |
| 240 | E = MRI.livein_end(); LI != E; ++LI) |
| 241 | if (LI->second) { |
| 242 | const TargetRegisterClass *RC = MRI.getRegClass(LI->second); |
| 243 | EmitLiveInCopy(EntryMBB, InsertPos, LI->second, LI->first, |
| 244 | RC, CopyRegMap, MRI, TRI, TII); |
| 245 | } |
| 246 | } else { |
| 247 | // Emit the copies into the top of the block. |
| 248 | for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(), |
| 249 | E = MRI.livein_end(); LI != E; ++LI) |
| 250 | if (LI->second) { |
| 251 | const TargetRegisterClass *RC = MRI.getRegClass(LI->second); |
| 252 | TII.copyRegToReg(*EntryMBB, EntryMBB->begin(), |
| 253 | LI->second, LI->first, RC, RC); |
| 254 | } |
| 255 | } |
| 256 | } |
| 257 | |
Chris Lattner | 7041ee3 | 2005-01-11 05:56:49 +0000 | [diff] [blame] | 258 | //===----------------------------------------------------------------------===// |
| 259 | // SelectionDAGISel code |
| 260 | //===----------------------------------------------------------------------===// |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 261 | |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 262 | SelectionDAGISel::SelectionDAGISel(TargetLowering &tli, bool fast) : |
Dan Gohman | ae73dc1 | 2008-09-04 17:05:41 +0000 | [diff] [blame] | 263 | FunctionPass(&ID), TLI(tli), |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 264 | FuncInfo(new FunctionLoweringInfo(TLI)), |
| 265 | CurDAG(new SelectionDAG(TLI, *FuncInfo)), |
| 266 | SDL(new SelectionDAGLowering(*CurDAG, TLI, *FuncInfo)), |
| 267 | GFI(), |
| 268 | Fast(fast), |
| 269 | DAGSize(0) |
| 270 | {} |
| 271 | |
| 272 | SelectionDAGISel::~SelectionDAGISel() { |
| 273 | delete SDL; |
| 274 | delete CurDAG; |
| 275 | delete FuncInfo; |
| 276 | } |
| 277 | |
Duncan Sands | 83ec4b6 | 2008-06-06 12:08:01 +0000 | [diff] [blame] | 278 | unsigned SelectionDAGISel::MakeReg(MVT VT) { |
Chris Lattner | 84bc542 | 2007-12-31 04:13:23 +0000 | [diff] [blame] | 279 | return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT)); |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 280 | } |
| 281 | |
Chris Lattner | 495a0b5 | 2005-08-17 06:37:43 +0000 | [diff] [blame] | 282 | void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { |
Jim Laskey | c7c3f11 | 2006-10-16 20:52:31 +0000 | [diff] [blame] | 283 | AU.addRequired<AliasAnalysis>(); |
Gordon Henriksen | 5eca075 | 2008-08-17 18:44:35 +0000 | [diff] [blame] | 284 | AU.addRequired<GCModuleInfo>(); |
Chris Lattner | c8d288f | 2007-03-31 04:18:03 +0000 | [diff] [blame] | 285 | AU.setPreservesAll(); |
Chris Lattner | 495a0b5 | 2005-08-17 06:37:43 +0000 | [diff] [blame] | 286 | } |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 287 | |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 288 | bool SelectionDAGISel::runOnFunction(Function &Fn) { |
Dan Gohman | 4344a5d | 2008-09-09 23:05:00 +0000 | [diff] [blame] | 289 | // Do some sanity-checking on the command-line options. |
| 290 | assert((!EnableFastISelVerbose || EnableFastISel) && |
| 291 | "-fast-isel-verbose requires -fast-isel"); |
| 292 | assert((!EnableFastISelAbort || EnableFastISel) && |
| 293 | "-fast-isel-abort requires -fast-isel"); |
| 294 | |
Dan Gohman | 5f43f92 | 2007-08-27 16:26:13 +0000 | [diff] [blame] | 295 | // Get alias analysis for load/store combining. |
| 296 | AA = &getAnalysis<AliasAnalysis>(); |
| 297 | |
Dan Gohman | 8a11053 | 2008-09-05 22:59:21 +0000 | [diff] [blame] | 298 | TargetMachine &TM = TLI.getTargetMachine(); |
| 299 | MachineFunction &MF = MachineFunction::construct(&Fn, TM); |
| 300 | const MachineRegisterInfo &MRI = MF.getRegInfo(); |
| 301 | const TargetInstrInfo &TII = *TM.getInstrInfo(); |
| 302 | const TargetRegisterInfo &TRI = *TM.getRegisterInfo(); |
| 303 | |
Gordon Henriksen | 5eca075 | 2008-08-17 18:44:35 +0000 | [diff] [blame] | 304 | if (MF.getFunction()->hasGC()) |
| 305 | GFI = &getAnalysis<GCModuleInfo>().getFunctionInfo(*MF.getFunction()); |
Gordon Henriksen | ce22477 | 2008-01-07 01:30:38 +0000 | [diff] [blame] | 306 | else |
Gordon Henriksen | 5eca075 | 2008-08-17 18:44:35 +0000 | [diff] [blame] | 307 | GFI = 0; |
Chris Lattner | 84bc542 | 2007-12-31 04:13:23 +0000 | [diff] [blame] | 308 | RegInfo = &MF.getRegInfo(); |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 309 | DOUT << "\n\n\n=== " << Fn.getName() << "\n"; |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 310 | |
Dan Gohman | f0cbcd4 | 2008-09-03 16:12:24 +0000 | [diff] [blame] | 311 | FuncInfo->set(Fn, MF, EnableFastISel); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 312 | CurDAG->init(MF, getAnalysisToUpdate<MachineModuleInfo>()); |
| 313 | SDL->init(GFI, *AA); |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 314 | |
Dale Johannesen | 1532f3d | 2008-04-02 00:25:04 +0000 | [diff] [blame] | 315 | for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) |
| 316 | if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator())) |
| 317 | // Mark landing pad. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 318 | FuncInfo->MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad(); |
Duncan Sands | 9fac0b5 | 2007-06-06 10:05:18 +0000 | [diff] [blame] | 319 | |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 320 | SelectAllBasicBlocks(Fn, MF); |
Misha Brukman | edf128a | 2005-04-21 22:36:52 +0000 | [diff] [blame] | 321 | |
Dan Gohman | 8a11053 | 2008-09-05 22:59:21 +0000 | [diff] [blame] | 322 | // If the first basic block in the function has live ins that need to be |
| 323 | // copied into vregs, emit the copies into the top of the block before |
| 324 | // emitting the code for the block. |
| 325 | EmitLiveInCopies(MF.begin(), MRI, TRI, TII); |
| 326 | |
Evan Cheng | ad2070c | 2007-02-10 02:43:39 +0000 | [diff] [blame] | 327 | // Add function live-ins to entry block live-in set. |
Dan Gohman | 8a11053 | 2008-09-05 22:59:21 +0000 | [diff] [blame] | 328 | for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(), |
| 329 | E = RegInfo->livein_end(); I != E; ++I) |
| 330 | MF.begin()->addLiveIn(I->first); |
Evan Cheng | ad2070c | 2007-02-10 02:43:39 +0000 | [diff] [blame] | 331 | |
Duncan Sands | f407082 | 2007-06-15 19:04:19 +0000 | [diff] [blame] | 332 | #ifndef NDEBUG |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 333 | assert(FuncInfo->CatchInfoFound.size() == FuncInfo->CatchInfoLost.size() && |
Duncan Sands | f407082 | 2007-06-15 19:04:19 +0000 | [diff] [blame] | 334 | "Not all catch info was assigned to a landing pad!"); |
| 335 | #endif |
| 336 | |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 337 | FuncInfo->clear(); |
| 338 | |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 339 | return true; |
| 340 | } |
| 341 | |
Duncan Sands | f407082 | 2007-06-15 19:04:19 +0000 | [diff] [blame] | 342 | static void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB, |
| 343 | MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) { |
Duncan Sands | f407082 | 2007-06-15 19:04:19 +0000 | [diff] [blame] | 344 | for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I) |
Dan Gohman | f0cbcd4 | 2008-09-03 16:12:24 +0000 | [diff] [blame] | 345 | if (EHSelectorInst *EHSel = dyn_cast<EHSelectorInst>(I)) { |
Duncan Sands | f407082 | 2007-06-15 19:04:19 +0000 | [diff] [blame] | 346 | // Apply the catch info to DestBB. |
Dan Gohman | f0cbcd4 | 2008-09-03 16:12:24 +0000 | [diff] [blame] | 347 | AddCatchInfo(*EHSel, MMI, FLI.MBBMap[DestBB]); |
Duncan Sands | f407082 | 2007-06-15 19:04:19 +0000 | [diff] [blame] | 348 | #ifndef NDEBUG |
Duncan Sands | 560a737 | 2007-11-15 09:54:37 +0000 | [diff] [blame] | 349 | if (!FLI.MBBMap[SrcBB]->isLandingPad()) |
Dan Gohman | f0cbcd4 | 2008-09-03 16:12:24 +0000 | [diff] [blame] | 350 | FLI.CatchInfoFound.insert(EHSel); |
Duncan Sands | f407082 | 2007-06-15 19:04:19 +0000 | [diff] [blame] | 351 | #endif |
| 352 | } |
| 353 | } |
| 354 | |
Arnold Schwaighofer | 30e62c0 | 2008-04-30 09:16:33 +0000 | [diff] [blame] | 355 | /// IsFixedFrameObjectWithPosOffset - Check if object is a fixed frame object and |
| 356 | /// whether object offset >= 0. |
| 357 | static bool |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 358 | IsFixedFrameObjectWithPosOffset(MachineFrameInfo * MFI, SDValue Op) { |
Arnold Schwaighofer | 30e62c0 | 2008-04-30 09:16:33 +0000 | [diff] [blame] | 359 | if (!isa<FrameIndexSDNode>(Op)) return false; |
| 360 | |
| 361 | FrameIndexSDNode * FrameIdxNode = dyn_cast<FrameIndexSDNode>(Op); |
| 362 | int FrameIdx = FrameIdxNode->getIndex(); |
| 363 | return MFI->isFixedObjectIndex(FrameIdx) && |
| 364 | MFI->getObjectOffset(FrameIdx) >= 0; |
| 365 | } |
| 366 | |
| 367 | /// IsPossiblyOverwrittenArgumentOfTailCall - Check if the operand could |
| 368 | /// possibly be overwritten when lowering the outgoing arguments in a tail |
| 369 | /// call. Currently the implementation of this call is very conservative and |
| 370 | /// assumes all arguments sourcing from FORMAL_ARGUMENTS or a CopyFromReg with |
| 371 | /// virtual registers would be overwritten by direct lowering. |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 372 | static bool IsPossiblyOverwrittenArgumentOfTailCall(SDValue Op, |
Arnold Schwaighofer | 30e62c0 | 2008-04-30 09:16:33 +0000 | [diff] [blame] | 373 | MachineFrameInfo * MFI) { |
| 374 | RegisterSDNode * OpReg = NULL; |
| 375 | if (Op.getOpcode() == ISD::FORMAL_ARGUMENTS || |
| 376 | (Op.getOpcode()== ISD::CopyFromReg && |
| 377 | (OpReg = dyn_cast<RegisterSDNode>(Op.getOperand(1))) && |
| 378 | (OpReg->getReg() >= TargetRegisterInfo::FirstVirtualRegister)) || |
| 379 | (Op.getOpcode() == ISD::LOAD && |
| 380 | IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(1))) || |
| 381 | (Op.getOpcode() == ISD::MERGE_VALUES && |
Gabor Greif | 99a6cb9 | 2008-08-26 22:36:50 +0000 | [diff] [blame] | 382 | Op.getOperand(Op.getResNo()).getOpcode() == ISD::LOAD && |
| 383 | IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(Op.getResNo()). |
Arnold Schwaighofer | 30e62c0 | 2008-04-30 09:16:33 +0000 | [diff] [blame] | 384 | getOperand(1)))) |
| 385 | return true; |
| 386 | return false; |
| 387 | } |
| 388 | |
Arnold Schwaighofer | c85e171 | 2007-10-11 19:40:01 +0000 | [diff] [blame] | 389 | /// CheckDAGForTailCallsAndFixThem - This Function looks for CALL nodes in the |
Arnold Schwaighofer | 48abc5c | 2007-10-12 21:30:57 +0000 | [diff] [blame] | 390 | /// DAG and fixes their tailcall attribute operand. |
Arnold Schwaighofer | c85e171 | 2007-10-11 19:40:01 +0000 | [diff] [blame] | 391 | static void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG, |
| 392 | TargetLowering& TLI) { |
| 393 | SDNode * Ret = NULL; |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 394 | SDValue Terminator = DAG.getRoot(); |
Arnold Schwaighofer | c85e171 | 2007-10-11 19:40:01 +0000 | [diff] [blame] | 395 | |
| 396 | // Find RET node. |
| 397 | if (Terminator.getOpcode() == ISD::RET) { |
Gabor Greif | ba36cb5 | 2008-08-28 21:40:38 +0000 | [diff] [blame] | 398 | Ret = Terminator.getNode(); |
Arnold Schwaighofer | c85e171 | 2007-10-11 19:40:01 +0000 | [diff] [blame] | 399 | } |
| 400 | |
| 401 | // Fix tail call attribute of CALL nodes. |
| 402 | for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(), |
Dan Gohman | 0e5f130 | 2008-07-07 23:02:41 +0000 | [diff] [blame] | 403 | BI = DAG.allnodes_end(); BI != BE; ) { |
| 404 | --BI; |
Dan Gohman | 095cc29 | 2008-09-13 01:54:27 +0000 | [diff] [blame] | 405 | if (CallSDNode *TheCall = dyn_cast<CallSDNode>(BI)) { |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 406 | SDValue OpRet(Ret, 0); |
| 407 | SDValue OpCall(BI, 0); |
Dan Gohman | 095cc29 | 2008-09-13 01:54:27 +0000 | [diff] [blame] | 408 | bool isMarkedTailCall = TheCall->isTailCall(); |
Arnold Schwaighofer | c85e171 | 2007-10-11 19:40:01 +0000 | [diff] [blame] | 409 | // If CALL node has tail call attribute set to true and the call is not |
| 410 | // eligible (no RET or the target rejects) the attribute is fixed to |
Arnold Schwaighofer | 48abc5c | 2007-10-12 21:30:57 +0000 | [diff] [blame] | 411 | // false. The TargetLowering::IsEligibleForTailCallOptimization function |
Arnold Schwaighofer | c85e171 | 2007-10-11 19:40:01 +0000 | [diff] [blame] | 412 | // must correctly identify tail call optimizable calls. |
Arnold Schwaighofer | 30e62c0 | 2008-04-30 09:16:33 +0000 | [diff] [blame] | 413 | if (!isMarkedTailCall) continue; |
| 414 | if (Ret==NULL || |
Dan Gohman | 095cc29 | 2008-09-13 01:54:27 +0000 | [diff] [blame] | 415 | !TLI.IsEligibleForTailCallOptimization(TheCall, OpRet, DAG)) { |
| 416 | // Not eligible. Mark CALL node as non tail call. Note that we |
| 417 | // can modify the call node in place since calls are not CSE'd. |
| 418 | TheCall->setNotTailCall(); |
Arnold Schwaighofer | 30e62c0 | 2008-04-30 09:16:33 +0000 | [diff] [blame] | 419 | } else { |
| 420 | // Look for tail call clobbered arguments. Emit a series of |
| 421 | // copyto/copyfrom virtual register nodes to protect them. |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 422 | SmallVector<SDValue, 32> Ops; |
Dan Gohman | 095cc29 | 2008-09-13 01:54:27 +0000 | [diff] [blame] | 423 | SDValue Chain = TheCall->getChain(), InFlag; |
| 424 | Ops.push_back(Chain); |
| 425 | Ops.push_back(TheCall->getCallee()); |
| 426 | for (unsigned i = 0, e = TheCall->getNumArgs(); i != e; ++i) { |
| 427 | SDValue Arg = TheCall->getArg(i); |
| 428 | bool isByVal = TheCall->getArgFlags(i).isByVal(); |
| 429 | MachineFunction &MF = DAG.getMachineFunction(); |
| 430 | MachineFrameInfo *MFI = MF.getFrameInfo(); |
| 431 | if (!isByVal && |
| 432 | IsPossiblyOverwrittenArgumentOfTailCall(Arg, MFI)) { |
| 433 | MVT VT = Arg.getValueType(); |
| 434 | unsigned VReg = MF.getRegInfo(). |
| 435 | createVirtualRegister(TLI.getRegClassFor(VT)); |
| 436 | Chain = DAG.getCopyToReg(Chain, VReg, Arg, InFlag); |
| 437 | InFlag = Chain.getValue(1); |
| 438 | Arg = DAG.getCopyFromReg(Chain, VReg, VT, InFlag); |
| 439 | Chain = Arg.getValue(1); |
| 440 | InFlag = Arg.getValue(2); |
Arnold Schwaighofer | 30e62c0 | 2008-04-30 09:16:33 +0000 | [diff] [blame] | 441 | } |
| 442 | Ops.push_back(Arg); |
Dan Gohman | 095cc29 | 2008-09-13 01:54:27 +0000 | [diff] [blame] | 443 | Ops.push_back(TheCall->getArgFlagsVal(i)); |
Arnold Schwaighofer | 30e62c0 | 2008-04-30 09:16:33 +0000 | [diff] [blame] | 444 | } |
| 445 | // Link in chain of CopyTo/CopyFromReg. |
| 446 | Ops[0] = Chain; |
| 447 | DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size()); |
Arnold Schwaighofer | c85e171 | 2007-10-11 19:40:01 +0000 | [diff] [blame] | 448 | } |
| 449 | } |
| 450 | } |
| 451 | } |
| 452 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 453 | void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, |
| 454 | BasicBlock::iterator Begin, |
Dan Gohman | 5edd361 | 2008-08-28 20:28:56 +0000 | [diff] [blame] | 455 | BasicBlock::iterator End) { |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 456 | SDL->setCurrentBasicBlock(BB); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 457 | |
| 458 | MachineModuleInfo *MMI = CurDAG->getMachineModuleInfo(); |
| 459 | |
| 460 | if (MMI && BB->isLandingPad()) { |
| 461 | // Add a label to mark the beginning of the landing pad. Deletion of the |
| 462 | // landing pad can thus be detected via the MachineModuleInfo. |
| 463 | unsigned LabelID = MMI->addLandingPad(BB); |
| 464 | CurDAG->setRoot(CurDAG->getLabel(ISD::EH_LABEL, |
| 465 | CurDAG->getEntryNode(), LabelID)); |
| 466 | |
| 467 | // Mark exception register as live in. |
| 468 | unsigned Reg = TLI.getExceptionAddressRegister(); |
| 469 | if (Reg) BB->addLiveIn(Reg); |
| 470 | |
| 471 | // Mark exception selector register as live in. |
| 472 | Reg = TLI.getExceptionSelectorRegister(); |
| 473 | if (Reg) BB->addLiveIn(Reg); |
| 474 | |
| 475 | // FIXME: Hack around an exception handling flaw (PR1508): the personality |
| 476 | // function and list of typeids logically belong to the invoke (or, if you |
| 477 | // like, the basic block containing the invoke), and need to be associated |
| 478 | // with it in the dwarf exception handling tables. Currently however the |
| 479 | // information is provided by an intrinsic (eh.selector) that can be moved |
| 480 | // to unexpected places by the optimizers: if the unwind edge is critical, |
| 481 | // then breaking it can result in the intrinsics being in the successor of |
| 482 | // the landing pad, not the landing pad itself. This results in exceptions |
| 483 | // not being caught because no typeids are associated with the invoke. |
| 484 | // This may not be the only way things can go wrong, but it is the only way |
| 485 | // we try to work around for the moment. |
| 486 | BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator()); |
| 487 | |
| 488 | if (Br && Br->isUnconditional()) { // Critical edge? |
| 489 | BasicBlock::iterator I, E; |
| 490 | for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I) |
Dan Gohman | f0cbcd4 | 2008-09-03 16:12:24 +0000 | [diff] [blame] | 491 | if (isa<EHSelectorInst>(I)) |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 492 | break; |
| 493 | |
| 494 | if (I == E) |
| 495 | // No catch info found - try to extract some from the successor. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 496 | copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 497 | } |
| 498 | } |
| 499 | |
| 500 | // Lower all of the non-terminator instructions. |
| 501 | for (BasicBlock::iterator I = Begin; I != End; ++I) |
| 502 | if (!isa<TerminatorInst>(I)) |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 503 | SDL->visit(*I); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 504 | |
| 505 | // Ensure that all instructions which are used outside of their defining |
| 506 | // blocks are available as virtual registers. Invoke is handled elsewhere. |
| 507 | for (BasicBlock::iterator I = Begin; I != End; ++I) |
| 508 | if (!I->use_empty() && !isa<PHINode>(I) && !isa<InvokeInst>(I)) { |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 509 | DenseMap<const Value*,unsigned>::iterator VMI =FuncInfo->ValueMap.find(I); |
| 510 | if (VMI != FuncInfo->ValueMap.end()) |
| 511 | SDL->CopyValueToVirtualRegister(I, VMI->second); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 512 | } |
| 513 | |
| 514 | // Handle PHI nodes in successor blocks. |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 515 | if (End == LLVMBB->end()) { |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 516 | HandlePHINodesInSuccessorBlocks(LLVMBB); |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 517 | |
| 518 | // Lower the terminator after the copies are emitted. |
| 519 | SDL->visit(*LLVMBB->getTerminator()); |
| 520 | } |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 521 | |
Chris Lattner | a651cf6 | 2005-01-17 19:43:36 +0000 | [diff] [blame] | 522 | // Make sure the root of the DAG is up-to-date. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 523 | CurDAG->setRoot(SDL->getControlRoot()); |
Arnold Schwaighofer | c85e171 | 2007-10-11 19:40:01 +0000 | [diff] [blame] | 524 | |
| 525 | // Check whether calls in this block are real tail calls. Fix up CALL nodes |
| 526 | // with correct tailcall attribute so that the target can rely on the tailcall |
| 527 | // attribute indicating whether the call is really eligible for tail call |
| 528 | // optimization. |
Dan Gohman | 1937e2f | 2008-09-16 01:42:28 +0000 | [diff] [blame] | 529 | if (PerformTailCallOpt) |
| 530 | CheckDAGForTailCallsAndFixThem(*CurDAG, TLI); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 531 | |
| 532 | // Final step, emit the lowered DAG as machine code. |
| 533 | CodeGenAndEmitDAG(); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 534 | SDL->clear(); |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 535 | } |
| 536 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 537 | void SelectionDAGISel::ComputeLiveOutVRegInfo() { |
Chris Lattner | ead0d88 | 2008-06-17 06:09:18 +0000 | [diff] [blame] | 538 | SmallPtrSet<SDNode*, 128> VisitedNodes; |
| 539 | SmallVector<SDNode*, 128> Worklist; |
| 540 | |
Gabor Greif | ba36cb5 | 2008-08-28 21:40:38 +0000 | [diff] [blame] | 541 | Worklist.push_back(CurDAG->getRoot().getNode()); |
Chris Lattner | ead0d88 | 2008-06-17 06:09:18 +0000 | [diff] [blame] | 542 | |
| 543 | APInt Mask; |
| 544 | APInt KnownZero; |
| 545 | APInt KnownOne; |
| 546 | |
| 547 | while (!Worklist.empty()) { |
| 548 | SDNode *N = Worklist.back(); |
| 549 | Worklist.pop_back(); |
| 550 | |
| 551 | // If we've already seen this node, ignore it. |
| 552 | if (!VisitedNodes.insert(N)) |
| 553 | continue; |
| 554 | |
| 555 | // Otherwise, add all chain operands to the worklist. |
| 556 | for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) |
| 557 | if (N->getOperand(i).getValueType() == MVT::Other) |
Gabor Greif | ba36cb5 | 2008-08-28 21:40:38 +0000 | [diff] [blame] | 558 | Worklist.push_back(N->getOperand(i).getNode()); |
Chris Lattner | ead0d88 | 2008-06-17 06:09:18 +0000 | [diff] [blame] | 559 | |
| 560 | // If this is a CopyToReg with a vreg dest, process it. |
| 561 | if (N->getOpcode() != ISD::CopyToReg) |
| 562 | continue; |
| 563 | |
| 564 | unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg(); |
| 565 | if (!TargetRegisterInfo::isVirtualRegister(DestReg)) |
| 566 | continue; |
| 567 | |
| 568 | // Ignore non-scalar or non-integer values. |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 569 | SDValue Src = N->getOperand(2); |
Chris Lattner | ead0d88 | 2008-06-17 06:09:18 +0000 | [diff] [blame] | 570 | MVT SrcVT = Src.getValueType(); |
| 571 | if (!SrcVT.isInteger() || SrcVT.isVector()) |
| 572 | continue; |
| 573 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 574 | unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src); |
Chris Lattner | ead0d88 | 2008-06-17 06:09:18 +0000 | [diff] [blame] | 575 | Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits()); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 576 | CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne); |
Chris Lattner | ead0d88 | 2008-06-17 06:09:18 +0000 | [diff] [blame] | 577 | |
| 578 | // Only install this information if it tells us something. |
| 579 | if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) { |
| 580 | DestReg -= TargetRegisterInfo::FirstVirtualRegister; |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 581 | FunctionLoweringInfo &FLI = CurDAG->getFunctionLoweringInfo(); |
Chris Lattner | ead0d88 | 2008-06-17 06:09:18 +0000 | [diff] [blame] | 582 | if (DestReg >= FLI.LiveOutRegInfo.size()) |
| 583 | FLI.LiveOutRegInfo.resize(DestReg+1); |
| 584 | FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[DestReg]; |
| 585 | LOI.NumSignBits = NumSignBits; |
| 586 | LOI.KnownOne = NumSignBits; |
| 587 | LOI.KnownZero = NumSignBits; |
| 588 | } |
| 589 | } |
| 590 | } |
| 591 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 592 | void SelectionDAGISel::CodeGenAndEmitDAG() { |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 593 | std::string GroupName; |
| 594 | if (TimePassesIsEnabled) |
| 595 | GroupName = "Instruction Selection and Scheduling"; |
| 596 | std::string BlockName; |
| 597 | if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs || |
| 598 | ViewDAGCombine2 || ViewISelDAGs || ViewSchedDAGs || ViewSUnitDAGs) |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 599 | BlockName = CurDAG->getMachineFunction().getFunction()->getName() + ':' + |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 600 | BB->getBasicBlock()->getName(); |
| 601 | |
| 602 | DOUT << "Initial selection DAG:\n"; |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 603 | DEBUG(CurDAG->dump()); |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 604 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 605 | if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName); |
Dan Gohman | 417e11b | 2007-10-08 15:12:17 +0000 | [diff] [blame] | 606 | |
Chris Lattner | af21d55 | 2005-10-10 16:47:10 +0000 | [diff] [blame] | 607 | // Run the DAG combiner in pre-legalize mode. |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 608 | if (TimePassesIsEnabled) { |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 609 | NamedRegionTimer T("DAG Combining 1", GroupName); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 610 | CurDAG->Combine(false, *AA, Fast); |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 611 | } else { |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 612 | CurDAG->Combine(false, *AA, Fast); |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 613 | } |
Nate Begeman | 2300f55 | 2005-09-07 00:15:36 +0000 | [diff] [blame] | 614 | |
Dan Gohman | 417e11b | 2007-10-08 15:12:17 +0000 | [diff] [blame] | 615 | DOUT << "Optimized lowered selection DAG:\n"; |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 616 | DEBUG(CurDAG->dump()); |
Duncan Sands | f00e74f | 2008-07-17 17:06:03 +0000 | [diff] [blame] | 617 | |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 618 | // Second step, hack on the DAG until it only uses operations and types that |
| 619 | // the target supports. |
Duncan Sands | f00e74f | 2008-07-17 17:06:03 +0000 | [diff] [blame] | 620 | if (EnableLegalizeTypes) {// Enable this some day. |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 621 | if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " + |
| 622 | BlockName); |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 623 | |
| 624 | if (TimePassesIsEnabled) { |
| 625 | NamedRegionTimer T("Type Legalization", GroupName); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 626 | CurDAG->LegalizeTypes(); |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 627 | } else { |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 628 | CurDAG->LegalizeTypes(); |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 629 | } |
| 630 | |
| 631 | DOUT << "Type-legalized selection DAG:\n"; |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 632 | DEBUG(CurDAG->dump()); |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 633 | |
Chris Lattner | 70587ea | 2008-07-10 23:37:50 +0000 | [diff] [blame] | 634 | // TODO: enable a dag combine pass here. |
| 635 | } |
Duncan Sands | f00e74f | 2008-07-17 17:06:03 +0000 | [diff] [blame] | 636 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 637 | if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName); |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 638 | |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 639 | if (TimePassesIsEnabled) { |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 640 | NamedRegionTimer T("DAG Legalization", GroupName); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 641 | CurDAG->Legalize(); |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 642 | } else { |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 643 | CurDAG->Legalize(); |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 644 | } |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 645 | |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 646 | DOUT << "Legalized selection DAG:\n"; |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 647 | DEBUG(CurDAG->dump()); |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 648 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 649 | if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName); |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 650 | |
Chris Lattner | af21d55 | 2005-10-10 16:47:10 +0000 | [diff] [blame] | 651 | // Run the DAG combiner in post-legalize mode. |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 652 | if (TimePassesIsEnabled) { |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 653 | NamedRegionTimer T("DAG Combining 2", GroupName); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 654 | CurDAG->Combine(true, *AA, Fast); |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 655 | } else { |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 656 | CurDAG->Combine(true, *AA, Fast); |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 657 | } |
Nate Begeman | 2300f55 | 2005-09-07 00:15:36 +0000 | [diff] [blame] | 658 | |
Dan Gohman | 417e11b | 2007-10-08 15:12:17 +0000 | [diff] [blame] | 659 | DOUT << "Optimized legalized selection DAG:\n"; |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 660 | DEBUG(CurDAG->dump()); |
Dan Gohman | 417e11b | 2007-10-08 15:12:17 +0000 | [diff] [blame] | 661 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 662 | if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName); |
Chris Lattner | ead0d88 | 2008-06-17 06:09:18 +0000 | [diff] [blame] | 663 | |
Dan Gohman | 925a7e8 | 2008-08-13 19:47:40 +0000 | [diff] [blame] | 664 | if (!Fast && EnableValueProp) |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 665 | ComputeLiveOutVRegInfo(); |
Evan Cheng | 552c4a8 | 2006-04-28 02:09:19 +0000 | [diff] [blame] | 666 | |
Chris Lattner | a33ef48 | 2005-03-30 01:10:47 +0000 | [diff] [blame] | 667 | // Third, instruction select all of the operations to machine code, adding the |
| 668 | // code to the MachineBasicBlock. |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 669 | if (TimePassesIsEnabled) { |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 670 | NamedRegionTimer T("Instruction Selection", GroupName); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 671 | InstructionSelect(); |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 672 | } else { |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 673 | InstructionSelect(); |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 674 | } |
Evan Cheng | db8d56b | 2008-06-30 20:45:06 +0000 | [diff] [blame] | 675 | |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 676 | DOUT << "Selected selection DAG:\n"; |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 677 | DEBUG(CurDAG->dump()); |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 678 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 679 | if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName); |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 680 | |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 681 | // Schedule machine code. |
| 682 | ScheduleDAG *Scheduler; |
| 683 | if (TimePassesIsEnabled) { |
| 684 | NamedRegionTimer T("Instruction Scheduling", GroupName); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 685 | Scheduler = Schedule(); |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 686 | } else { |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 687 | Scheduler = Schedule(); |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 688 | } |
| 689 | |
Dan Gohman | 462dc7f | 2008-07-21 20:00:07 +0000 | [diff] [blame] | 690 | if (ViewSUnitDAGs) Scheduler->viewGraph(); |
| 691 | |
Evan Cheng | db8d56b | 2008-06-30 20:45:06 +0000 | [diff] [blame] | 692 | // Emit machine code to BB. This can change 'BB' to the last block being |
| 693 | // inserted into. |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 694 | if (TimePassesIsEnabled) { |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 695 | NamedRegionTimer T("Instruction Creation", GroupName); |
| 696 | BB = Scheduler->EmitSchedule(); |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 697 | } else { |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 698 | BB = Scheduler->EmitSchedule(); |
| 699 | } |
| 700 | |
| 701 | // Free the scheduler state. |
| 702 | if (TimePassesIsEnabled) { |
| 703 | NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName); |
| 704 | delete Scheduler; |
| 705 | } else { |
| 706 | delete Scheduler; |
Evan Cheng | ebffb66 | 2008-07-01 17:59:20 +0000 | [diff] [blame] | 707 | } |
Evan Cheng | db8d56b | 2008-06-30 20:45:06 +0000 | [diff] [blame] | 708 | |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 709 | DOUT << "Selected machine code:\n"; |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 710 | DEBUG(BB->dump()); |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 711 | } |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 712 | |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 713 | void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF) { |
Evan Cheng | 39fd6e8 | 2008-08-07 00:43:25 +0000 | [diff] [blame] | 714 | for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { |
| 715 | BasicBlock *LLVMBB = &*I; |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 716 | BB = FuncInfo->MBBMap[LLVMBB]; |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 717 | |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 718 | BasicBlock::iterator const Begin = LLVMBB->begin(); |
| 719 | BasicBlock::iterator const End = LLVMBB->end(); |
Evan Cheng | 9f11850 | 2008-09-08 16:01:27 +0000 | [diff] [blame] | 720 | BasicBlock::iterator BI = Begin; |
Dan Gohman | 5edd361 | 2008-08-28 20:28:56 +0000 | [diff] [blame] | 721 | |
| 722 | // Lower any arguments needed in this block if this is the entry block. |
| 723 | if (LLVMBB == &Fn.getEntryBlock()) |
| 724 | LowerArguments(LLVMBB); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 725 | |
| 726 | // Before doing SelectionDAG ISel, see if FastISel has been requested. |
| 727 | // FastISel doesn't support EH landing pads, which require special handling. |
| 728 | if (EnableFastISel && !BB->isLandingPad()) { |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 729 | if (FastISel *F = TLI.createFastISel(*FuncInfo->MF, FuncInfo->ValueMap, |
Dan Gohman | 0586d91 | 2008-09-10 20:11:02 +0000 | [diff] [blame] | 730 | FuncInfo->MBBMap, |
| 731 | FuncInfo->StaticAllocaMap)) { |
Dan Gohman | 5edd361 | 2008-08-28 20:28:56 +0000 | [diff] [blame] | 732 | // Emit code for any incoming arguments. This must happen before |
| 733 | // beginning FastISel on the entry block. |
| 734 | if (LLVMBB == &Fn.getEntryBlock()) { |
| 735 | CurDAG->setRoot(SDL->getControlRoot()); |
| 736 | CodeGenAndEmitDAG(); |
| 737 | SDL->clear(); |
| 738 | } |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 739 | F->setCurrentBlock(BB); |
Dan Gohman | 5edd361 | 2008-08-28 20:28:56 +0000 | [diff] [blame] | 740 | // Do FastISel on as many instructions as possible. |
Evan Cheng | 9f11850 | 2008-09-08 16:01:27 +0000 | [diff] [blame] | 741 | for (; BI != End; ++BI) { |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 742 | // Just before the terminator instruction, insert instructions to |
| 743 | // feed PHI nodes in successor blocks. |
Dan Gohman | a8657e3 | 2008-09-08 20:37:59 +0000 | [diff] [blame] | 744 | if (isa<TerminatorInst>(BI)) |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 745 | if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, F)) { |
Dan Gohman | 4344a5d | 2008-09-09 23:05:00 +0000 | [diff] [blame] | 746 | if (EnableFastISelVerbose || EnableFastISelAbort) { |
Dan Gohman | 293d5f8 | 2008-09-09 22:06:46 +0000 | [diff] [blame] | 747 | cerr << "FastISel miss: "; |
| 748 | BI->dump(); |
| 749 | } |
Dan Gohman | 4344a5d | 2008-09-09 23:05:00 +0000 | [diff] [blame] | 750 | if (EnableFastISelAbort) |
Dan Gohman | 293d5f8 | 2008-09-09 22:06:46 +0000 | [diff] [blame] | 751 | assert(0 && "FastISel didn't handle a PHI in a successor"); |
Dan Gohman | 3ee25dc | 2008-09-10 15:52:34 +0000 | [diff] [blame] | 752 | break; |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 753 | } |
| 754 | |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 755 | // First try normal tablegen-generated "fast" selection. |
Evan Cheng | 9f11850 | 2008-09-08 16:01:27 +0000 | [diff] [blame] | 756 | if (F->SelectInstruction(BI)) |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 757 | continue; |
| 758 | |
| 759 | // Next, try calling the target to attempt to handle the instruction. |
Evan Cheng | 9f11850 | 2008-09-08 16:01:27 +0000 | [diff] [blame] | 760 | if (F->TargetSelectInstruction(BI)) |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 761 | continue; |
| 762 | |
| 763 | // Then handle certain instructions as single-LLVM-Instruction blocks. |
Dan Gohman | cf01f7a | 2008-09-09 02:40:04 +0000 | [diff] [blame] | 764 | if (isa<CallInst>(BI)) { |
Evan Cheng | 9f11850 | 2008-09-08 16:01:27 +0000 | [diff] [blame] | 765 | if (BI->getType() != Type::VoidTy) { |
Dan Gohman | a8657e3 | 2008-09-08 20:37:59 +0000 | [diff] [blame] | 766 | unsigned &R = FuncInfo->ValueMap[BI]; |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 767 | if (!R) |
Evan Cheng | 9f11850 | 2008-09-08 16:01:27 +0000 | [diff] [blame] | 768 | R = FuncInfo->CreateRegForValue(BI); |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 769 | } |
| 770 | |
Evan Cheng | 9f11850 | 2008-09-08 16:01:27 +0000 | [diff] [blame] | 771 | SelectBasicBlock(LLVMBB, BI, next(BI)); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 772 | continue; |
| 773 | } |
| 774 | |
Dan Gohman | 293d5f8 | 2008-09-09 22:06:46 +0000 | [diff] [blame] | 775 | // Otherwise, give up on FastISel for the rest of the block. |
| 776 | // For now, be a little lenient about non-branch terminators. |
| 777 | if (!isa<TerminatorInst>(BI) || isa<BranchInst>(BI)) { |
Dan Gohman | 4344a5d | 2008-09-09 23:05:00 +0000 | [diff] [blame] | 778 | if (EnableFastISelVerbose || EnableFastISelAbort) { |
Dan Gohman | 293d5f8 | 2008-09-09 22:06:46 +0000 | [diff] [blame] | 779 | cerr << "FastISel miss: "; |
| 780 | BI->dump(); |
| 781 | } |
Dan Gohman | 4344a5d | 2008-09-09 23:05:00 +0000 | [diff] [blame] | 782 | if (EnableFastISelAbort) |
Dan Gohman | 293d5f8 | 2008-09-09 22:06:46 +0000 | [diff] [blame] | 783 | // The "fast" selector couldn't handle something and bailed. |
| 784 | // For the purpose of debugging, just abort. |
| 785 | assert(0 && "FastISel didn't select the entire block"); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 786 | } |
| 787 | break; |
| 788 | } |
| 789 | delete F; |
| 790 | } |
| 791 | } |
| 792 | |
Dan Gohman | d2ff647 | 2008-09-02 20:17:56 +0000 | [diff] [blame] | 793 | // Run SelectionDAG instruction selection on the remainder of the block |
| 794 | // not handled by FastISel. If FastISel is not run, this is the entire |
Dan Gohman | 3df24e6 | 2008-09-03 23:12:08 +0000 | [diff] [blame] | 795 | // block. |
Evan Cheng | 9f11850 | 2008-09-08 16:01:27 +0000 | [diff] [blame] | 796 | if (BI != End) |
| 797 | SelectBasicBlock(LLVMBB, BI, End); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 798 | |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 799 | FinishBasicBlock(); |
Evan Cheng | 39fd6e8 | 2008-08-07 00:43:25 +0000 | [diff] [blame] | 800 | } |
Dan Gohman | 0e5f130 | 2008-07-07 23:02:41 +0000 | [diff] [blame] | 801 | } |
| 802 | |
Dan Gohman | fed90b6 | 2008-07-28 21:51:04 +0000 | [diff] [blame] | 803 | void |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 804 | SelectionDAGISel::FinishBasicBlock() { |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 805 | |
| 806 | // Perform target specific isel post processing. |
| 807 | InstructionSelectPostProcessing(); |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 808 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 809 | DOUT << "Target-post-processed machine code:\n"; |
| 810 | DEBUG(BB->dump()); |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 811 | |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 812 | DOUT << "Total amount of phi nodes to update: " |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 813 | << SDL->PHINodesToUpdate.size() << "\n"; |
| 814 | DEBUG(for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) |
| 815 | DOUT << "Node " << i << " : (" << SDL->PHINodesToUpdate[i].first |
| 816 | << ", " << SDL->PHINodesToUpdate[i].second << ")\n";); |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 817 | |
Chris Lattner | a33ef48 | 2005-03-30 01:10:47 +0000 | [diff] [blame] | 818 | // Next, now that we know what the last MBB the LLVM BB expanded is, update |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 819 | // PHI nodes in successors. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 820 | if (SDL->SwitchCases.empty() && |
| 821 | SDL->JTCases.empty() && |
| 822 | SDL->BitTestCases.empty()) { |
| 823 | for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) { |
| 824 | MachineInstr *PHI = SDL->PHINodesToUpdate[i].first; |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 825 | assert(PHI->getOpcode() == TargetInstrInfo::PHI && |
| 826 | "This is not a machine PHI node that we are updating!"); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 827 | PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second, |
Chris Lattner | 9ce2e9d | 2007-12-30 00:57:42 +0000 | [diff] [blame] | 828 | false)); |
| 829 | PHI->addOperand(MachineOperand::CreateMBB(BB)); |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 830 | } |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 831 | SDL->PHINodesToUpdate.clear(); |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 832 | return; |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 833 | } |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 834 | |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 835 | for (unsigned i = 0, e = SDL->BitTestCases.size(); i != e; ++i) { |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 836 | // Lower header first, if it wasn't already lowered |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 837 | if (!SDL->BitTestCases[i].Emitted) { |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 838 | // Set the current basic block to the mbb we wish to insert the code into |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 839 | BB = SDL->BitTestCases[i].Parent; |
| 840 | SDL->setCurrentBasicBlock(BB); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 841 | // Emit the code |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 842 | SDL->visitBitTestHeader(SDL->BitTestCases[i]); |
| 843 | CurDAG->setRoot(SDL->getRoot()); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 844 | CodeGenAndEmitDAG(); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 845 | SDL->clear(); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 846 | } |
| 847 | |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 848 | for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); j != ej; ++j) { |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 849 | // Set the current basic block to the mbb we wish to insert the code into |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 850 | BB = SDL->BitTestCases[i].Cases[j].ThisBB; |
| 851 | SDL->setCurrentBasicBlock(BB); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 852 | // Emit the code |
| 853 | if (j+1 != ej) |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 854 | SDL->visitBitTestCase(SDL->BitTestCases[i].Cases[j+1].ThisBB, |
| 855 | SDL->BitTestCases[i].Reg, |
| 856 | SDL->BitTestCases[i].Cases[j]); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 857 | else |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 858 | SDL->visitBitTestCase(SDL->BitTestCases[i].Default, |
| 859 | SDL->BitTestCases[i].Reg, |
| 860 | SDL->BitTestCases[i].Cases[j]); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 861 | |
| 862 | |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 863 | CurDAG->setRoot(SDL->getRoot()); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 864 | CodeGenAndEmitDAG(); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 865 | SDL->clear(); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 866 | } |
| 867 | |
| 868 | // Update PHI Nodes |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 869 | for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) { |
| 870 | MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first; |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 871 | MachineBasicBlock *PHIBB = PHI->getParent(); |
| 872 | assert(PHI->getOpcode() == TargetInstrInfo::PHI && |
| 873 | "This is not a machine PHI node that we are updating!"); |
| 874 | // This is "default" BB. We have two jumps to it. From "header" BB and |
| 875 | // from last "case" BB. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 876 | if (PHIBB == SDL->BitTestCases[i].Default) { |
| 877 | PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, |
Chris Lattner | 9ce2e9d | 2007-12-30 00:57:42 +0000 | [diff] [blame] | 878 | false)); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 879 | PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Parent)); |
| 880 | PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, |
Chris Lattner | 9ce2e9d | 2007-12-30 00:57:42 +0000 | [diff] [blame] | 881 | false)); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 882 | PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Cases. |
Chris Lattner | 9ce2e9d | 2007-12-30 00:57:42 +0000 | [diff] [blame] | 883 | back().ThisBB)); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 884 | } |
| 885 | // One of "cases" BB. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 886 | for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); |
| 887 | j != ej; ++j) { |
| 888 | MachineBasicBlock* cBB = SDL->BitTestCases[i].Cases[j].ThisBB; |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 889 | if (cBB->succ_end() != |
| 890 | std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) { |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 891 | PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, |
Chris Lattner | 9ce2e9d | 2007-12-30 00:57:42 +0000 | [diff] [blame] | 892 | false)); |
| 893 | PHI->addOperand(MachineOperand::CreateMBB(cBB)); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 894 | } |
| 895 | } |
| 896 | } |
| 897 | } |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 898 | SDL->BitTestCases.clear(); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 899 | |
Nate Begeman | 9453eea | 2006-04-23 06:26:20 +0000 | [diff] [blame] | 900 | // If the JumpTable record is filled in, then we need to emit a jump table. |
| 901 | // Updating the PHI nodes is tricky in this case, since we need to determine |
| 902 | // whether the PHI is a successor of the range check MBB or the jump table MBB |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 903 | for (unsigned i = 0, e = SDL->JTCases.size(); i != e; ++i) { |
Anton Korobeynikov | 3a84b9b | 2007-03-25 15:07:15 +0000 | [diff] [blame] | 904 | // Lower header first, if it wasn't already lowered |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 905 | if (!SDL->JTCases[i].first.Emitted) { |
Anton Korobeynikov | 3a84b9b | 2007-03-25 15:07:15 +0000 | [diff] [blame] | 906 | // Set the current basic block to the mbb we wish to insert the code into |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 907 | BB = SDL->JTCases[i].first.HeaderBB; |
| 908 | SDL->setCurrentBasicBlock(BB); |
Anton Korobeynikov | 3a84b9b | 2007-03-25 15:07:15 +0000 | [diff] [blame] | 909 | // Emit the code |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 910 | SDL->visitJumpTableHeader(SDL->JTCases[i].second, SDL->JTCases[i].first); |
| 911 | CurDAG->setRoot(SDL->getRoot()); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 912 | CodeGenAndEmitDAG(); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 913 | SDL->clear(); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 914 | } |
Anton Korobeynikov | 3a84b9b | 2007-03-25 15:07:15 +0000 | [diff] [blame] | 915 | |
Nate Begeman | 37efe67 | 2006-04-22 18:53:45 +0000 | [diff] [blame] | 916 | // Set the current basic block to the mbb we wish to insert the code into |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 917 | BB = SDL->JTCases[i].second.MBB; |
| 918 | SDL->setCurrentBasicBlock(BB); |
Nate Begeman | 37efe67 | 2006-04-22 18:53:45 +0000 | [diff] [blame] | 919 | // Emit the code |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 920 | SDL->visitJumpTable(SDL->JTCases[i].second); |
| 921 | CurDAG->setRoot(SDL->getRoot()); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 922 | CodeGenAndEmitDAG(); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 923 | SDL->clear(); |
Anton Korobeynikov | 3a84b9b | 2007-03-25 15:07:15 +0000 | [diff] [blame] | 924 | |
Nate Begeman | 37efe67 | 2006-04-22 18:53:45 +0000 | [diff] [blame] | 925 | // Update PHI Nodes |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 926 | for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) { |
| 927 | MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first; |
Nate Begeman | 37efe67 | 2006-04-22 18:53:45 +0000 | [diff] [blame] | 928 | MachineBasicBlock *PHIBB = PHI->getParent(); |
| 929 | assert(PHI->getOpcode() == TargetInstrInfo::PHI && |
| 930 | "This is not a machine PHI node that we are updating!"); |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 931 | // "default" BB. We can go there only from header BB. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 932 | if (PHIBB == SDL->JTCases[i].second.Default) { |
| 933 | PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, |
Chris Lattner | 9ce2e9d | 2007-12-30 00:57:42 +0000 | [diff] [blame] | 934 | false)); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 935 | PHI->addOperand(MachineOperand::CreateMBB(SDL->JTCases[i].first.HeaderBB)); |
Nate Begeman | f4360a4 | 2006-05-03 03:48:02 +0000 | [diff] [blame] | 936 | } |
Anton Korobeynikov | 4198c58 | 2007-04-09 12:31:58 +0000 | [diff] [blame] | 937 | // JT BB. Just iterate over successors here |
Nate Begeman | f4360a4 | 2006-05-03 03:48:02 +0000 | [diff] [blame] | 938 | if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) { |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 939 | PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, |
Chris Lattner | 9ce2e9d | 2007-12-30 00:57:42 +0000 | [diff] [blame] | 940 | false)); |
| 941 | PHI->addOperand(MachineOperand::CreateMBB(BB)); |
Nate Begeman | 37efe67 | 2006-04-22 18:53:45 +0000 | [diff] [blame] | 942 | } |
| 943 | } |
Nate Begeman | 37efe67 | 2006-04-22 18:53:45 +0000 | [diff] [blame] | 944 | } |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 945 | SDL->JTCases.clear(); |
Nate Begeman | 37efe67 | 2006-04-22 18:53:45 +0000 | [diff] [blame] | 946 | |
Chris Lattner | b2e806e | 2006-10-22 23:00:53 +0000 | [diff] [blame] | 947 | // If the switch block involved a branch to one of the actual successors, we |
| 948 | // need to update PHI nodes in that block. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 949 | for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) { |
| 950 | MachineInstr *PHI = SDL->PHINodesToUpdate[i].first; |
Chris Lattner | b2e806e | 2006-10-22 23:00:53 +0000 | [diff] [blame] | 951 | assert(PHI->getOpcode() == TargetInstrInfo::PHI && |
| 952 | "This is not a machine PHI node that we are updating!"); |
| 953 | if (BB->isSuccessor(PHI->getParent())) { |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 954 | PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second, |
Chris Lattner | 9ce2e9d | 2007-12-30 00:57:42 +0000 | [diff] [blame] | 955 | false)); |
| 956 | PHI->addOperand(MachineOperand::CreateMBB(BB)); |
Chris Lattner | b2e806e | 2006-10-22 23:00:53 +0000 | [diff] [blame] | 957 | } |
| 958 | } |
| 959 | |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 960 | // If we generated any switch lowering information, build and codegen any |
| 961 | // additional DAGs necessary. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 962 | for (unsigned i = 0, e = SDL->SwitchCases.size(); i != e; ++i) { |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 963 | // Set the current basic block to the mbb we wish to insert the code into |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 964 | BB = SDL->SwitchCases[i].ThisBB; |
| 965 | SDL->setCurrentBasicBlock(BB); |
Chris Lattner | d5e93c0 | 2006-09-07 01:59:34 +0000 | [diff] [blame] | 966 | |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 967 | // Emit the code |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 968 | SDL->visitSwitchCase(SDL->SwitchCases[i]); |
| 969 | CurDAG->setRoot(SDL->getRoot()); |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 970 | CodeGenAndEmitDAG(); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 971 | SDL->clear(); |
Chris Lattner | d5e93c0 | 2006-09-07 01:59:34 +0000 | [diff] [blame] | 972 | |
| 973 | // Handle any PHI nodes in successors of this chunk, as if we were coming |
| 974 | // from the original BB before switch expansion. Note that PHI nodes can |
| 975 | // occur multiple times in PHINodesToUpdate. We have to be very careful to |
| 976 | // handle them the right number of times. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 977 | while ((BB = SDL->SwitchCases[i].TrueBB)) { // Handle LHS and RHS. |
Chris Lattner | d5e93c0 | 2006-09-07 01:59:34 +0000 | [diff] [blame] | 978 | for (MachineBasicBlock::iterator Phi = BB->begin(); |
| 979 | Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){ |
| 980 | // This value for this PHI node is recorded in PHINodesToUpdate, get it. |
| 981 | for (unsigned pn = 0; ; ++pn) { |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 982 | assert(pn != SDL->PHINodesToUpdate.size() && |
| 983 | "Didn't find PHI entry!"); |
| 984 | if (SDL->PHINodesToUpdate[pn].first == Phi) { |
| 985 | Phi->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pn]. |
Chris Lattner | 9ce2e9d | 2007-12-30 00:57:42 +0000 | [diff] [blame] | 986 | second, false)); |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 987 | Phi->addOperand(MachineOperand::CreateMBB(SDL->SwitchCases[i].ThisBB)); |
Chris Lattner | d5e93c0 | 2006-09-07 01:59:34 +0000 | [diff] [blame] | 988 | break; |
| 989 | } |
| 990 | } |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 991 | } |
Chris Lattner | d5e93c0 | 2006-09-07 01:59:34 +0000 | [diff] [blame] | 992 | |
| 993 | // Don't process RHS if same block as LHS. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 994 | if (BB == SDL->SwitchCases[i].FalseBB) |
| 995 | SDL->SwitchCases[i].FalseBB = 0; |
Chris Lattner | d5e93c0 | 2006-09-07 01:59:34 +0000 | [diff] [blame] | 996 | |
| 997 | // If we haven't handled the RHS, do so now. Otherwise, we're done. |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 998 | SDL->SwitchCases[i].TrueBB = SDL->SwitchCases[i].FalseBB; |
| 999 | SDL->SwitchCases[i].FalseBB = 0; |
Nate Begeman | f15485a | 2006-03-27 01:32:24 +0000 | [diff] [blame] | 1000 | } |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 1001 | assert(SDL->SwitchCases[i].TrueBB == 0 && SDL->SwitchCases[i].FalseBB == 0); |
Chris Lattner | a33ef48 | 2005-03-30 01:10:47 +0000 | [diff] [blame] | 1002 | } |
Dan Gohman | 7c3234c | 2008-08-27 23:52:12 +0000 | [diff] [blame] | 1003 | SDL->SwitchCases.clear(); |
| 1004 | |
| 1005 | SDL->PHINodesToUpdate.clear(); |
Chris Lattner | 1c08c71 | 2005-01-07 07:47:53 +0000 | [diff] [blame] | 1006 | } |
Evan Cheng | a9c2091 | 2006-01-21 02:32:06 +0000 | [diff] [blame] | 1007 | |
Jim Laskey | 13ec702 | 2006-08-01 14:21:23 +0000 | [diff] [blame] | 1008 | |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 1009 | /// Schedule - Pick a safe ordering for instructions for each |
Evan Cheng | a9c2091 | 2006-01-21 02:32:06 +0000 | [diff] [blame] | 1010 | /// target node in the graph. |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 1011 | /// |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 1012 | ScheduleDAG *SelectionDAGISel::Schedule() { |
Jim Laskey | eb577ba | 2006-08-02 12:30:23 +0000 | [diff] [blame] | 1013 | RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault(); |
Jim Laskey | 13ec702 | 2006-08-01 14:21:23 +0000 | [diff] [blame] | 1014 | |
| 1015 | if (!Ctor) { |
Jim Laskey | eb577ba | 2006-08-02 12:30:23 +0000 | [diff] [blame] | 1016 | Ctor = ISHeuristic; |
Jim Laskey | 9373beb | 2006-08-01 19:14:14 +0000 | [diff] [blame] | 1017 | RegisterScheduler::setDefault(Ctor); |
Evan Cheng | 4ef1086 | 2006-01-23 07:01:07 +0000 | [diff] [blame] | 1018 | } |
Jim Laskey | 13ec702 | 2006-08-01 14:21:23 +0000 | [diff] [blame] | 1019 | |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 1020 | ScheduleDAG *Scheduler = Ctor(this, CurDAG, BB, Fast); |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 1021 | Scheduler->Run(); |
Dan Gohman | 3e1a7ae | 2007-08-28 20:32:58 +0000 | [diff] [blame] | 1022 | |
Dan Gohman | 5e84368 | 2008-07-14 18:19:29 +0000 | [diff] [blame] | 1023 | return Scheduler; |
Evan Cheng | a9c2091 | 2006-01-21 02:32:06 +0000 | [diff] [blame] | 1024 | } |
Chris Lattner | 0e43f2b | 2006-02-24 02:13:54 +0000 | [diff] [blame] | 1025 | |
Chris Lattner | 03fc53c | 2006-03-06 00:22:00 +0000 | [diff] [blame] | 1026 | |
Jim Laskey | 9ff542f | 2006-08-01 18:29:48 +0000 | [diff] [blame] | 1027 | HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() { |
| 1028 | return new HazardRecognizer(); |
| 1029 | } |
| 1030 | |
Chris Lattner | 7554806 | 2006-10-11 03:58:02 +0000 | [diff] [blame] | 1031 | //===----------------------------------------------------------------------===// |
| 1032 | // Helper functions used by the generated instruction selector. |
| 1033 | //===----------------------------------------------------------------------===// |
| 1034 | // Calls to these methods are generated by tblgen. |
| 1035 | |
| 1036 | /// CheckAndMask - The isel is trying to match something like (and X, 255). If |
| 1037 | /// the dag combiner simplified the 255, we still want to match. RHS is the |
| 1038 | /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value |
| 1039 | /// specified in the .td file (e.g. 255). |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 1040 | bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS, |
Dan Gohman | dc9b3d0 | 2007-07-24 23:00:27 +0000 | [diff] [blame] | 1041 | int64_t DesiredMaskS) const { |
Dan Gohman | 2e68b6f | 2008-02-25 21:11:39 +0000 | [diff] [blame] | 1042 | const APInt &ActualMask = RHS->getAPIntValue(); |
| 1043 | const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); |
Chris Lattner | 7554806 | 2006-10-11 03:58:02 +0000 | [diff] [blame] | 1044 | |
| 1045 | // If the actual mask exactly matches, success! |
| 1046 | if (ActualMask == DesiredMask) |
| 1047 | return true; |
| 1048 | |
| 1049 | // If the actual AND mask is allowing unallowed bits, this doesn't match. |
Dan Gohman | 2e68b6f | 2008-02-25 21:11:39 +0000 | [diff] [blame] | 1050 | if (ActualMask.intersects(~DesiredMask)) |
Chris Lattner | 7554806 | 2006-10-11 03:58:02 +0000 | [diff] [blame] | 1051 | return false; |
| 1052 | |
| 1053 | // Otherwise, the DAG Combiner may have proven that the value coming in is |
| 1054 | // either already zero or is not demanded. Check for known zero input bits. |
Dan Gohman | 2e68b6f | 2008-02-25 21:11:39 +0000 | [diff] [blame] | 1055 | APInt NeededMask = DesiredMask & ~ActualMask; |
Dan Gohman | ea859be | 2007-06-22 14:59:07 +0000 | [diff] [blame] | 1056 | if (CurDAG->MaskedValueIsZero(LHS, NeededMask)) |
Chris Lattner | 7554806 | 2006-10-11 03:58:02 +0000 | [diff] [blame] | 1057 | return true; |
| 1058 | |
| 1059 | // TODO: check to see if missing bits are just not demanded. |
| 1060 | |
| 1061 | // Otherwise, this pattern doesn't match. |
| 1062 | return false; |
| 1063 | } |
| 1064 | |
| 1065 | /// CheckOrMask - The isel is trying to match something like (or X, 255). If |
| 1066 | /// the dag combiner simplified the 255, we still want to match. RHS is the |
| 1067 | /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value |
| 1068 | /// specified in the .td file (e.g. 255). |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 1069 | bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS, |
Dan Gohman | 2e68b6f | 2008-02-25 21:11:39 +0000 | [diff] [blame] | 1070 | int64_t DesiredMaskS) const { |
| 1071 | const APInt &ActualMask = RHS->getAPIntValue(); |
| 1072 | const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); |
Chris Lattner | 7554806 | 2006-10-11 03:58:02 +0000 | [diff] [blame] | 1073 | |
| 1074 | // If the actual mask exactly matches, success! |
| 1075 | if (ActualMask == DesiredMask) |
| 1076 | return true; |
| 1077 | |
| 1078 | // If the actual AND mask is allowing unallowed bits, this doesn't match. |
Dan Gohman | 2e68b6f | 2008-02-25 21:11:39 +0000 | [diff] [blame] | 1079 | if (ActualMask.intersects(~DesiredMask)) |
Chris Lattner | 7554806 | 2006-10-11 03:58:02 +0000 | [diff] [blame] | 1080 | return false; |
| 1081 | |
| 1082 | // Otherwise, the DAG Combiner may have proven that the value coming in is |
| 1083 | // either already zero or is not demanded. Check for known zero input bits. |
Dan Gohman | 2e68b6f | 2008-02-25 21:11:39 +0000 | [diff] [blame] | 1084 | APInt NeededMask = DesiredMask & ~ActualMask; |
Chris Lattner | 7554806 | 2006-10-11 03:58:02 +0000 | [diff] [blame] | 1085 | |
Dan Gohman | 2e68b6f | 2008-02-25 21:11:39 +0000 | [diff] [blame] | 1086 | APInt KnownZero, KnownOne; |
Dan Gohman | ea859be | 2007-06-22 14:59:07 +0000 | [diff] [blame] | 1087 | CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne); |
Chris Lattner | 7554806 | 2006-10-11 03:58:02 +0000 | [diff] [blame] | 1088 | |
| 1089 | // If all the missing bits in the or are already known to be set, match! |
| 1090 | if ((NeededMask & KnownOne) == NeededMask) |
| 1091 | return true; |
| 1092 | |
| 1093 | // TODO: check to see if missing bits are just not demanded. |
| 1094 | |
| 1095 | // Otherwise, this pattern doesn't match. |
| 1096 | return false; |
| 1097 | } |
| 1098 | |
Jim Laskey | 9ff542f | 2006-08-01 18:29:48 +0000 | [diff] [blame] | 1099 | |
Chris Lattner | 0e43f2b | 2006-02-24 02:13:54 +0000 | [diff] [blame] | 1100 | /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated |
| 1101 | /// by tblgen. Others should not call it. |
| 1102 | void SelectionDAGISel:: |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 1103 | SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) { |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 1104 | std::vector<SDValue> InOps; |
Chris Lattner | 0e43f2b | 2006-02-24 02:13:54 +0000 | [diff] [blame] | 1105 | std::swap(InOps, Ops); |
| 1106 | |
| 1107 | Ops.push_back(InOps[0]); // input chain. |
| 1108 | Ops.push_back(InOps[1]); // input asm string. |
| 1109 | |
Chris Lattner | 0e43f2b | 2006-02-24 02:13:54 +0000 | [diff] [blame] | 1110 | unsigned i = 2, e = InOps.size(); |
| 1111 | if (InOps[e-1].getValueType() == MVT::Flag) |
| 1112 | --e; // Don't process a flag operand if it is here. |
| 1113 | |
| 1114 | while (i != e) { |
Dan Gohman | f5aeb1a | 2008-09-12 16:56:44 +0000 | [diff] [blame] | 1115 | unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue(); |
Dale Johannesen | 91aac10 | 2008-09-17 21:13:11 +0000 | [diff] [blame] | 1116 | if ((Flags & 7) != 4 /*MEM*/ && |
| 1117 | (Flags & 7) != 7 /*MEM OVERLAPS EARLYCLOBBER*/) { |
Chris Lattner | 0e43f2b | 2006-02-24 02:13:54 +0000 | [diff] [blame] | 1118 | // Just skip over this operand, copying the operands verbatim. |
| 1119 | Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1); |
| 1120 | i += (Flags >> 3) + 1; |
| 1121 | } else { |
| 1122 | assert((Flags >> 3) == 1 && "Memory operand with multiple values?"); |
| 1123 | // Otherwise, this is a memory operand. Ask the target to select it. |
Dan Gohman | 475871a | 2008-07-27 21:46:04 +0000 | [diff] [blame] | 1124 | std::vector<SDValue> SelOps; |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 1125 | if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) { |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 1126 | cerr << "Could not match memory address. Inline asm failure!\n"; |
Chris Lattner | 0e43f2b | 2006-02-24 02:13:54 +0000 | [diff] [blame] | 1127 | exit(1); |
| 1128 | } |
| 1129 | |
| 1130 | // Add this to the output node. |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 1131 | MVT IntPtrTy = CurDAG->getTargetLoweringInfo().getPointerTy(); |
Dale Johannesen | 91aac10 | 2008-09-17 21:13:11 +0000 | [diff] [blame] | 1132 | Ops.push_back(CurDAG->getTargetConstant((Flags & 7) | (SelOps.size()<< 3), |
Dan Gohman | f350b27 | 2008-08-23 02:25:05 +0000 | [diff] [blame] | 1133 | IntPtrTy)); |
Chris Lattner | 0e43f2b | 2006-02-24 02:13:54 +0000 | [diff] [blame] | 1134 | Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); |
| 1135 | i += 2; |
| 1136 | } |
| 1137 | } |
| 1138 | |
| 1139 | // Add the flag input back if present. |
| 1140 | if (e != InOps.size()) |
| 1141 | Ops.push_back(InOps.back()); |
| 1142 | } |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 1143 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 1144 | char SelectionDAGISel::ID = 0; |