blob: 69ff94b28c989b61b30f8dd1f1d26a013db98a87 [file] [log] [blame]
Chris Lattner1c08c712005-01-07 07:47:53 +00001//===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
Misha Brukmanedf128a2005-04-21 22:36:52 +00002//
Chris Lattner1c08c712005-01-07 07:47:53 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukmanedf128a2005-04-21 22:36:52 +00007//
Chris Lattner1c08c712005-01-07 07:47:53 +00008//===----------------------------------------------------------------------===//
9//
10// This implements the SelectionDAGISel class.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "isel"
Dan Gohman84fbac52009-02-06 17:22:58 +000015#include "ScheduleDAGSDNodes.h"
Dan Gohman2048b852009-11-23 18:04:58 +000016#include "SelectionDAGBuilder.h"
Dan Gohman6277eb22009-11-23 17:16:22 +000017#include "FunctionLoweringInfo.h"
Dan Gohman84fbac52009-02-06 17:22:58 +000018#include "llvm/CodeGen/SelectionDAGISel.h"
Jim Laskeyc7c3f112006-10-16 20:52:31 +000019#include "llvm/Analysis/AliasAnalysis.h"
Devang Patel713f0432009-09-16 21:09:07 +000020#include "llvm/Analysis/DebugInfo.h"
Anton Korobeynikov5502bf62007-04-04 21:14:49 +000021#include "llvm/Constants.h"
Chris Lattneradf6a962005-05-13 18:50:42 +000022#include "llvm/CallingConv.h"
Chris Lattner1c08c712005-01-07 07:47:53 +000023#include "llvm/DerivedTypes.h"
24#include "llvm/Function.h"
Chris Lattner36ce6912005-11-29 06:21:05 +000025#include "llvm/GlobalVariable.h"
Chris Lattnerce7518c2006-01-26 22:24:51 +000026#include "llvm/InlineAsm.h"
Chris Lattner1c08c712005-01-07 07:47:53 +000027#include "llvm/Instructions.h"
28#include "llvm/Intrinsics.h"
Jim Laskey43970fe2006-03-23 18:06:46 +000029#include "llvm/IntrinsicInst.h"
Chris Lattner75c478a2009-10-27 17:02:08 +000030#include "llvm/LLVMContext.h"
Dan Gohman78eca172008-08-19 22:33:34 +000031#include "llvm/CodeGen/FastISel.h"
Gordon Henriksen5a29c9e2008-08-17 12:56:54 +000032#include "llvm/CodeGen/GCStrategy.h"
Gordon Henriksen5eca0752008-08-17 18:44:35 +000033#include "llvm/CodeGen/GCMetadata.h"
Chris Lattner1c08c712005-01-07 07:47:53 +000034#include "llvm/CodeGen/MachineFunction.h"
Dan Gohmanad2afc22009-07-31 18:16:33 +000035#include "llvm/CodeGen/MachineFunctionAnalysis.h"
Chris Lattner1c08c712005-01-07 07:47:53 +000036#include "llvm/CodeGen/MachineFrameInfo.h"
37#include "llvm/CodeGen/MachineInstrBuilder.h"
Chris Lattner84bc5422007-12-31 04:13:23 +000038#include "llvm/CodeGen/MachineJumpTableInfo.h"
39#include "llvm/CodeGen/MachineModuleInfo.h"
40#include "llvm/CodeGen/MachineRegisterInfo.h"
Dan Gohmanfc54c552009-01-15 22:18:12 +000041#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
Jim Laskeyeb577ba2006-08-02 12:30:23 +000042#include "llvm/CodeGen/SchedulerRegistry.h"
Chris Lattner1c08c712005-01-07 07:47:53 +000043#include "llvm/CodeGen/SelectionDAG.h"
Devang Patel6e7a1612009-01-09 19:11:50 +000044#include "llvm/CodeGen/DwarfWriter.h"
Dan Gohman6f0d0242008-02-10 18:45:23 +000045#include "llvm/Target/TargetRegisterInfo.h"
Chris Lattner1c08c712005-01-07 07:47:53 +000046#include "llvm/Target/TargetData.h"
47#include "llvm/Target/TargetFrameInfo.h"
Dan Gohmane1f188f2009-10-29 22:30:23 +000048#include "llvm/Target/TargetIntrinsicInfo.h"
Chris Lattner1c08c712005-01-07 07:47:53 +000049#include "llvm/Target/TargetInstrInfo.h"
50#include "llvm/Target/TargetLowering.h"
51#include "llvm/Target/TargetMachine.h"
Vladimir Prus12472912006-05-23 13:43:15 +000052#include "llvm/Target/TargetOptions.h"
Chris Lattnera4f0b3a2006-08-27 12:54:02 +000053#include "llvm/Support/Compiler.h"
Evan Chengdb8d56b2008-06-30 20:45:06 +000054#include "llvm/Support/Debug.h"
Torok Edwin7d696d82009-07-11 13:10:19 +000055#include "llvm/Support/ErrorHandling.h"
Evan Chengdb8d56b2008-06-30 20:45:06 +000056#include "llvm/Support/MathExtras.h"
57#include "llvm/Support/Timer.h"
Daniel Dunbarce63ffb2009-07-25 00:23:56 +000058#include "llvm/Support/raw_ostream.h"
Chris Lattnerc19ae9d2010-03-04 19:46:56 +000059#include "llvm/ADT/Statistic.h"
Jeff Cohen7e881032006-02-24 02:52:40 +000060#include <algorithm>
Chris Lattner1c08c712005-01-07 07:47:53 +000061using namespace llvm;
62
Chris Lattnerc19ae9d2010-03-04 19:46:56 +000063STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
Chris Lattnerbed993d2010-03-28 19:46:56 +000064STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");
Chris Lattnerc19ae9d2010-03-04 19:46:56 +000065
Chris Lattneread0d882008-06-17 06:09:18 +000066static cl::opt<bool>
Dan Gohman293d5f82008-09-09 22:06:46 +000067EnableFastISelVerbose("fast-isel-verbose", cl::Hidden,
Dan Gohmand659d502008-10-20 21:30:12 +000068 cl::desc("Enable verbose messages in the \"fast\" "
Dan Gohman293d5f82008-09-09 22:06:46 +000069 "instruction selector"));
70static cl::opt<bool>
Dan Gohman4344a5d2008-09-09 23:05:00 +000071EnableFastISelAbort("fast-isel-abort", cl::Hidden,
72 cl::desc("Enable abort calls when \"fast\" instruction fails"));
Dan Gohman8a110532008-09-05 22:59:21 +000073static cl::opt<bool>
Evan Chengdf8ed022009-11-09 06:49:37 +000074SchedLiveInCopies("schedule-livein-copies", cl::Hidden,
Dan Gohman8a110532008-09-05 22:59:21 +000075 cl::desc("Schedule copies of livein registers"),
76 cl::init(false));
Chris Lattneread0d882008-06-17 06:09:18 +000077
Chris Lattnerda8abb02005-09-01 18:44:10 +000078#ifndef NDEBUG
Chris Lattner7944d9d2005-01-12 03:41:21 +000079static cl::opt<bool>
Dan Gohman462dc7f2008-07-21 20:00:07 +000080ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
81 cl::desc("Pop up a window to show dags before the first "
82 "dag combine pass"));
83static cl::opt<bool>
84ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
85 cl::desc("Pop up a window to show dags before legalize types"));
86static cl::opt<bool>
87ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
88 cl::desc("Pop up a window to show dags before legalize"));
89static cl::opt<bool>
90ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
91 cl::desc("Pop up a window to show dags before the second "
92 "dag combine pass"));
93static cl::opt<bool>
Duncan Sands25cf2272008-11-24 14:53:14 +000094ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
95 cl::desc("Pop up a window to show dags before the post legalize types"
96 " dag combine pass"));
97static cl::opt<bool>
Evan Chenga9c20912006-01-21 02:32:06 +000098ViewISelDAGs("view-isel-dags", cl::Hidden,
99 cl::desc("Pop up a window to show isel dags as they are selected"));
100static cl::opt<bool>
101ViewSchedDAGs("view-sched-dags", cl::Hidden,
102 cl::desc("Pop up a window to show sched dags as they are processed"));
Dan Gohman3e1a7ae2007-08-28 20:32:58 +0000103static cl::opt<bool>
104ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
Chris Lattner5bab7852008-01-25 17:24:52 +0000105 cl::desc("Pop up a window to show SUnit dags after they are processed"));
Chris Lattner7944d9d2005-01-12 03:41:21 +0000106#else
Dan Gohman462dc7f2008-07-21 20:00:07 +0000107static const bool ViewDAGCombine1 = false,
108 ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
109 ViewDAGCombine2 = false,
Duncan Sands25cf2272008-11-24 14:53:14 +0000110 ViewDAGCombineLT = false,
Dan Gohman462dc7f2008-07-21 20:00:07 +0000111 ViewISelDAGs = false, ViewSchedDAGs = false,
112 ViewSUnitDAGs = false;
Chris Lattner7944d9d2005-01-12 03:41:21 +0000113#endif
114
Jim Laskeyeb577ba2006-08-02 12:30:23 +0000115//===---------------------------------------------------------------------===//
116///
117/// RegisterScheduler class - Track the registration of instruction schedulers.
118///
119//===---------------------------------------------------------------------===//
120MachinePassRegistry RegisterScheduler::Registry;
121
122//===---------------------------------------------------------------------===//
123///
124/// ISHeuristic command line option for instruction schedulers.
125///
126//===---------------------------------------------------------------------===//
Dan Gohman844731a2008-05-13 00:00:25 +0000127static cl::opt<RegisterScheduler::FunctionPassCtor, false,
128 RegisterPassParser<RegisterScheduler> >
129ISHeuristic("pre-RA-sched",
130 cl::init(&createDefaultScheduler),
131 cl::desc("Instruction schedulers available (before register"
132 " allocation):"));
Jim Laskey13ec7022006-08-01 14:21:23 +0000133
Dan Gohman844731a2008-05-13 00:00:25 +0000134static RegisterScheduler
Dan Gohmanb8cab922008-10-14 20:25:08 +0000135defaultListDAGScheduler("default", "Best scheduler for the target",
Dan Gohman844731a2008-05-13 00:00:25 +0000136 createDefaultScheduler);
Evan Cheng4ef10862006-01-23 07:01:07 +0000137
Chris Lattner1c08c712005-01-07 07:47:53 +0000138namespace llvm {
139 //===--------------------------------------------------------------------===//
Jim Laskey9373beb2006-08-01 19:14:14 +0000140 /// createDefaultScheduler - This creates an instruction scheduler appropriate
141 /// for the target.
Dan Gohman47ac0f02009-02-11 04:27:20 +0000142 ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS,
Bill Wendling98a366d2009-04-29 23:29:43 +0000143 CodeGenOpt::Level OptLevel) {
Dan Gohmane9530ec2009-01-15 16:58:17 +0000144 const TargetLowering &TLI = IS->getTargetLowering();
145
Bill Wendling98a366d2009-04-29 23:29:43 +0000146 if (OptLevel == CodeGenOpt::None)
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +0000147 return createFastDAGScheduler(IS, OptLevel);
Dan Gohman9e76fea2008-11-20 03:11:19 +0000148 if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency)
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +0000149 return createTDListDAGScheduler(IS, OptLevel);
Dan Gohman9e76fea2008-11-20 03:11:19 +0000150 assert(TLI.getSchedulingPreference() ==
Bill Wendling187361b2010-01-23 10:26:57 +0000151 TargetLowering::SchedulingForRegPressure && "Unknown sched type!");
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +0000152 return createBURRListDAGScheduler(IS, OptLevel);
Jim Laskey9373beb2006-08-01 19:14:14 +0000153 }
Chris Lattner1c08c712005-01-07 07:47:53 +0000154}
155
Evan Chengff9b3732008-01-30 18:18:23 +0000156// EmitInstrWithCustomInserter - This method should be implemented by targets
Dan Gohman533297b2009-10-29 18:10:34 +0000157// that mark instructions with the 'usesCustomInserter' flag. These
Chris Lattner025c39b2005-08-26 20:54:47 +0000158// instructions are special in various ways, which require special support to
159// insert. The specified MachineInstr is created but not inserted into any
Dan Gohman533297b2009-10-29 18:10:34 +0000160// basic blocks, and this method is called to expand it into a sequence of
161// instructions, potentially also creating new basic blocks and control flow.
162// When new basic blocks are inserted and the edges from MBB to its successors
163// are modified, the method should insert pairs of <OldSucc, NewSucc> into the
164// DenseMap.
Evan Chengff9b3732008-01-30 18:18:23 +0000165MachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI,
Evan Chengfb2e7522009-09-18 21:02:19 +0000166 MachineBasicBlock *MBB,
167 DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) const {
Torok Edwinf3689232009-07-12 20:07:01 +0000168#ifndef NDEBUG
David Greene1a053232010-01-05 01:26:11 +0000169 dbgs() << "If a target marks an instruction with "
Dan Gohman533297b2009-10-29 18:10:34 +0000170 "'usesCustomInserter', it must implement "
Torok Edwinf3689232009-07-12 20:07:01 +0000171 "TargetLowering::EmitInstrWithCustomInserter!";
172#endif
Torok Edwinc23197a2009-07-14 16:55:14 +0000173 llvm_unreachable(0);
Daniel Dunbara279bc32009-09-20 02:20:51 +0000174 return 0;
Chris Lattner025c39b2005-08-26 20:54:47 +0000175}
176
Dan Gohman8a110532008-09-05 22:59:21 +0000177/// EmitLiveInCopy - Emit a copy for a live in physical register. If the
178/// physical register has only a single copy use, then coalesced the copy
179/// if possible.
180static void EmitLiveInCopy(MachineBasicBlock *MBB,
181 MachineBasicBlock::iterator &InsertPos,
182 unsigned VirtReg, unsigned PhysReg,
183 const TargetRegisterClass *RC,
184 DenseMap<MachineInstr*, unsigned> &CopyRegMap,
185 const MachineRegisterInfo &MRI,
186 const TargetRegisterInfo &TRI,
187 const TargetInstrInfo &TII) {
188 unsigned NumUses = 0;
189 MachineInstr *UseMI = NULL;
190 for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(VirtReg),
191 UE = MRI.use_end(); UI != UE; ++UI) {
192 UseMI = &*UI;
193 if (++NumUses > 1)
194 break;
195 }
196
197 // If the number of uses is not one, or the use is not a move instruction,
198 // don't coalesce. Also, only coalesce away a virtual register to virtual
199 // register copy.
200 bool Coalesced = false;
Evan Cheng04ee5a12009-01-20 19:12:24 +0000201 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
Dan Gohman8a110532008-09-05 22:59:21 +0000202 if (NumUses == 1 &&
Evan Cheng04ee5a12009-01-20 19:12:24 +0000203 TII.isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
Dan Gohman8a110532008-09-05 22:59:21 +0000204 TargetRegisterInfo::isVirtualRegister(DstReg)) {
205 VirtReg = DstReg;
206 Coalesced = true;
207 }
208
209 // Now find an ideal location to insert the copy.
210 MachineBasicBlock::iterator Pos = InsertPos;
211 while (Pos != MBB->begin()) {
212 MachineInstr *PrevMI = prior(Pos);
213 DenseMap<MachineInstr*, unsigned>::iterator RI = CopyRegMap.find(PrevMI);
214 // copyRegToReg might emit multiple instructions to do a copy.
215 unsigned CopyDstReg = (RI == CopyRegMap.end()) ? 0 : RI->second;
216 if (CopyDstReg && !TRI.regsOverlap(CopyDstReg, PhysReg))
217 // This is what the BB looks like right now:
218 // r1024 = mov r0
219 // ...
220 // r1 = mov r1024
221 //
222 // We want to insert "r1025 = mov r1". Inserting this copy below the
223 // move to r1024 makes it impossible for that move to be coalesced.
224 //
225 // r1025 = mov r1
226 // r1024 = mov r0
227 // ...
228 // r1 = mov 1024
229 // r2 = mov 1025
230 break; // Woot! Found a good location.
231 --Pos;
232 }
233
David Goodwinf1daf7d2009-07-08 23:10:31 +0000234 bool Emitted = TII.copyRegToReg(*MBB, Pos, VirtReg, PhysReg, RC, RC);
235 assert(Emitted && "Unable to issue a live-in copy instruction!\n");
236 (void) Emitted;
Daniel Dunbara279bc32009-09-20 02:20:51 +0000237
Zhongxing Xu931424a2009-10-16 05:42:28 +0000238 CopyRegMap.insert(std::make_pair(prior(Pos), VirtReg));
Dan Gohman8a110532008-09-05 22:59:21 +0000239 if (Coalesced) {
240 if (&*InsertPos == UseMI) ++InsertPos;
241 MBB->erase(UseMI);
242 }
243}
244
245/// EmitLiveInCopies - If this is the first basic block in the function,
246/// and if it has live ins that need to be copied into vregs, emit the
247/// copies into the block.
248static void EmitLiveInCopies(MachineBasicBlock *EntryMBB,
249 const MachineRegisterInfo &MRI,
250 const TargetRegisterInfo &TRI,
251 const TargetInstrInfo &TII) {
252 if (SchedLiveInCopies) {
253 // Emit the copies at a heuristically-determined location in the block.
254 DenseMap<MachineInstr*, unsigned> CopyRegMap;
255 MachineBasicBlock::iterator InsertPos = EntryMBB->begin();
256 for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(),
257 E = MRI.livein_end(); LI != E; ++LI)
258 if (LI->second) {
259 const TargetRegisterClass *RC = MRI.getRegClass(LI->second);
260 EmitLiveInCopy(EntryMBB, InsertPos, LI->second, LI->first,
261 RC, CopyRegMap, MRI, TRI, TII);
262 }
263 } else {
264 // Emit the copies into the top of the block.
265 for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(),
266 E = MRI.livein_end(); LI != E; ++LI)
267 if (LI->second) {
268 const TargetRegisterClass *RC = MRI.getRegClass(LI->second);
David Goodwinf1daf7d2009-07-08 23:10:31 +0000269 bool Emitted = TII.copyRegToReg(*EntryMBB, EntryMBB->begin(),
270 LI->second, LI->first, RC, RC);
271 assert(Emitted && "Unable to issue a live-in copy instruction!\n");
272 (void) Emitted;
Dan Gohman8a110532008-09-05 22:59:21 +0000273 }
274 }
275}
276
Chris Lattner7041ee32005-01-11 05:56:49 +0000277//===----------------------------------------------------------------------===//
278// SelectionDAGISel code
279//===----------------------------------------------------------------------===//
Chris Lattner1c08c712005-01-07 07:47:53 +0000280
Bill Wendling98a366d2009-04-29 23:29:43 +0000281SelectionDAGISel::SelectionDAGISel(TargetMachine &tm, CodeGenOpt::Level OL) :
Dan Gohmanad2afc22009-07-31 18:16:33 +0000282 MachineFunctionPass(&ID), TM(tm), TLI(*tm.getTargetLowering()),
Dan Gohman7c3234c2008-08-27 23:52:12 +0000283 FuncInfo(new FunctionLoweringInfo(TLI)),
284 CurDAG(new SelectionDAG(TLI, *FuncInfo)),
Dan Gohman2048b852009-11-23 18:04:58 +0000285 SDB(new SelectionDAGBuilder(*CurDAG, TLI, *FuncInfo, OL)),
Dan Gohman7c3234c2008-08-27 23:52:12 +0000286 GFI(),
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +0000287 OptLevel(OL),
Dan Gohman7c3234c2008-08-27 23:52:12 +0000288 DAGSize(0)
289{}
290
291SelectionDAGISel::~SelectionDAGISel() {
Dan Gohman2048b852009-11-23 18:04:58 +0000292 delete SDB;
Dan Gohman7c3234c2008-08-27 23:52:12 +0000293 delete CurDAG;
294 delete FuncInfo;
295}
296
Owen Andersone50ed302009-08-10 22:56:29 +0000297unsigned SelectionDAGISel::MakeReg(EVT VT) {
Chris Lattner84bc5422007-12-31 04:13:23 +0000298 return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
Chris Lattner1c08c712005-01-07 07:47:53 +0000299}
300
Chris Lattner495a0b52005-08-17 06:37:43 +0000301void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
Jim Laskeyc7c3f112006-10-16 20:52:31 +0000302 AU.addRequired<AliasAnalysis>();
Dan Gohmana3477fe2009-07-31 23:36:22 +0000303 AU.addPreserved<AliasAnalysis>();
Gordon Henriksen5eca0752008-08-17 18:44:35 +0000304 AU.addRequired<GCModuleInfo>();
Dan Gohmana3477fe2009-07-31 23:36:22 +0000305 AU.addPreserved<GCModuleInfo>();
Devang Patel6e7a1612009-01-09 19:11:50 +0000306 AU.addRequired<DwarfWriter>();
Dan Gohmana3477fe2009-07-31 23:36:22 +0000307 AU.addPreserved<DwarfWriter>();
Dan Gohmanad2afc22009-07-31 18:16:33 +0000308 MachineFunctionPass::getAnalysisUsage(AU);
Chris Lattner495a0b52005-08-17 06:37:43 +0000309}
Chris Lattner1c08c712005-01-07 07:47:53 +0000310
Dan Gohmanad2afc22009-07-31 18:16:33 +0000311bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
312 Function &Fn = *mf.getFunction();
313
Dan Gohman4344a5d2008-09-09 23:05:00 +0000314 // Do some sanity-checking on the command-line options.
315 assert((!EnableFastISelVerbose || EnableFastISel) &&
316 "-fast-isel-verbose requires -fast-isel");
317 assert((!EnableFastISelAbort || EnableFastISel) &&
318 "-fast-isel-abort requires -fast-isel");
319
Dan Gohman5f43f922007-08-27 16:26:13 +0000320 // Get alias analysis for load/store combining.
321 AA = &getAnalysis<AliasAnalysis>();
322
Dan Gohmanad2afc22009-07-31 18:16:33 +0000323 MF = &mf;
Dan Gohman8a110532008-09-05 22:59:21 +0000324 const TargetInstrInfo &TII = *TM.getInstrInfo();
325 const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
326
Dan Gohmanf7d6cd42009-08-01 03:51:09 +0000327 if (Fn.hasGC())
328 GFI = &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn);
Gordon Henriksence224772008-01-07 01:30:38 +0000329 else
Gordon Henriksen5eca0752008-08-17 18:44:35 +0000330 GFI = 0;
Dan Gohman79ce2762009-01-15 19:20:50 +0000331 RegInfo = &MF->getRegInfo();
David Greene1a053232010-01-05 01:26:11 +0000332 DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
Chris Lattner1c08c712005-01-07 07:47:53 +0000333
Duncan Sands1465d612009-01-28 13:14:17 +0000334 MachineModuleInfo *MMI = getAnalysisIfAvailable<MachineModuleInfo>();
335 DwarfWriter *DW = getAnalysisIfAvailable<DwarfWriter>();
Owen Anderson5dcaceb2009-07-09 18:44:09 +0000336 CurDAG->init(*MF, MMI, DW);
Dan Gohman6277eb22009-11-23 17:16:22 +0000337 FuncInfo->set(Fn, *MF, EnableFastISel);
Dan Gohman2048b852009-11-23 18:04:58 +0000338 SDB->init(GFI, *AA);
Chris Lattner1c08c712005-01-07 07:47:53 +0000339
Dale Johannesen1532f3d2008-04-02 00:25:04 +0000340 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
341 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator()))
342 // Mark landing pad.
Dan Gohman7c3234c2008-08-27 23:52:12 +0000343 FuncInfo->MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
Duncan Sands9fac0b52007-06-06 10:05:18 +0000344
Chris Lattnerd850ac72010-04-05 02:19:28 +0000345 SelectAllBasicBlocks(Fn, *MF, MMI, TII);
Misha Brukmanedf128a2005-04-21 22:36:52 +0000346
Dan Gohman8a110532008-09-05 22:59:21 +0000347 // If the first basic block in the function has live ins that need to be
348 // copied into vregs, emit the copies into the top of the block before
349 // emitting the code for the block.
Dan Gohman79ce2762009-01-15 19:20:50 +0000350 EmitLiveInCopies(MF->begin(), *RegInfo, TRI, TII);
Dan Gohman8a110532008-09-05 22:59:21 +0000351
Evan Chengad2070c2007-02-10 02:43:39 +0000352 // Add function live-ins to entry block live-in set.
Dan Gohman8a110532008-09-05 22:59:21 +0000353 for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(),
354 E = RegInfo->livein_end(); I != E; ++I)
Dan Gohman79ce2762009-01-15 19:20:50 +0000355 MF->begin()->addLiveIn(I->first);
Evan Chengad2070c2007-02-10 02:43:39 +0000356
Duncan Sandsf4070822007-06-15 19:04:19 +0000357#ifndef NDEBUG
Dan Gohman7c3234c2008-08-27 23:52:12 +0000358 assert(FuncInfo->CatchInfoFound.size() == FuncInfo->CatchInfoLost.size() &&
Duncan Sandsf4070822007-06-15 19:04:19 +0000359 "Not all catch info was assigned to a landing pad!");
360#endif
361
Dan Gohman7c3234c2008-08-27 23:52:12 +0000362 FuncInfo->clear();
363
Chris Lattner1c08c712005-01-07 07:47:53 +0000364 return true;
365}
366
Dan Gohman07f111e2009-12-05 00:27:08 +0000367/// SetDebugLoc - Update MF's and SDB's DebugLocs if debug information is
368/// attached with this instruction.
Chris Lattner23dbf662010-03-31 04:24:50 +0000369static void SetDebugLoc(Instruction *I, SelectionDAGBuilder *SDB,
Chris Lattner0eb41982009-12-28 20:45:51 +0000370 FastISel *FastIS, MachineFunction *MF) {
Chris Lattnerde4845c2010-04-02 19:42:39 +0000371 DebugLoc DL = I->getDebugLoc();
372 if (DL.isUnknown()) return;
Chris Lattner23dbf662010-03-31 04:24:50 +0000373
Chris Lattnerde4845c2010-04-02 19:42:39 +0000374 SDB->setCurDebugLoc(DL);
Dan Gohman07f111e2009-12-05 00:27:08 +0000375
Chris Lattner23dbf662010-03-31 04:24:50 +0000376 if (FastIS)
Chris Lattnerde4845c2010-04-02 19:42:39 +0000377 FastIS->setCurDebugLoc(DL);
Dan Gohman07f111e2009-12-05 00:27:08 +0000378
Chris Lattner23dbf662010-03-31 04:24:50 +0000379 // If the function doesn't have a default debug location yet, set
380 // it. This is kind of a hack.
381 if (MF->getDefaultDebugLoc().isUnknown())
Chris Lattnerde4845c2010-04-02 19:42:39 +0000382 MF->setDefaultDebugLoc(DL);
Dan Gohman07f111e2009-12-05 00:27:08 +0000383}
384
385/// ResetDebugLoc - Set MF's and SDB's DebugLocs to Unknown.
Chris Lattner3990b122009-12-28 23:41:32 +0000386static void ResetDebugLoc(SelectionDAGBuilder *SDB, FastISel *FastIS) {
Chris Lattnera4f2bb02010-04-02 20:17:23 +0000387 SDB->setCurDebugLoc(DebugLoc());
Dan Gohman07f111e2009-12-05 00:27:08 +0000388 if (FastIS)
Chris Lattnera4f2bb02010-04-02 20:17:23 +0000389 FastIS->setCurDebugLoc(DebugLoc());
Dan Gohman07f111e2009-12-05 00:27:08 +0000390}
391
Dan Gohmanf350b272008-08-23 02:25:05 +0000392void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB,
393 BasicBlock::iterator Begin,
Dan Gohmanb4afb132009-11-20 02:51:26 +0000394 BasicBlock::iterator End,
395 bool &HadTailCall) {
Dan Gohman2048b852009-11-23 18:04:58 +0000396 SDB->setCurrentBasicBlock(BB);
Dan Gohmanf350b272008-08-23 02:25:05 +0000397
Dan Gohman98ca4f22009-08-05 01:29:28 +0000398 // Lower all of the non-terminator instructions. If a call is emitted
399 // as a tail call, cease emitting nodes for this block.
Dan Gohman2048b852009-11-23 18:04:58 +0000400 for (BasicBlock::iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
Chris Lattner23dbf662010-03-31 04:24:50 +0000401 SetDebugLoc(I, SDB, 0, MF);
Dan Gohman07f111e2009-12-05 00:27:08 +0000402
403 if (!isa<TerminatorInst>(I)) {
Dan Gohman2048b852009-11-23 18:04:58 +0000404 SDB->visit(*I);
Dan Gohman07f111e2009-12-05 00:27:08 +0000405
406 // Set the current debug location back to "unknown" so that it doesn't
407 // spuriously apply to subsequent instructions.
408 ResetDebugLoc(SDB, 0);
409 }
Devang Patel123eaa72009-09-16 20:39:11 +0000410 }
Dan Gohmanf350b272008-08-23 02:25:05 +0000411
Dan Gohman2048b852009-11-23 18:04:58 +0000412 if (!SDB->HasTailCall) {
Dan Gohman98ca4f22009-08-05 01:29:28 +0000413 // Ensure that all instructions which are used outside of their defining
414 // blocks are available as virtual registers. Invoke is handled elsewhere.
415 for (BasicBlock::iterator I = Begin; I != End; ++I)
416 if (!isa<PHINode>(I) && !isa<InvokeInst>(I))
Dan Gohman2048b852009-11-23 18:04:58 +0000417 SDB->CopyToExportRegsIfNeeded(I);
Dan Gohmanf350b272008-08-23 02:25:05 +0000418
Dan Gohman98ca4f22009-08-05 01:29:28 +0000419 // Handle PHI nodes in successor blocks.
420 if (End == LLVMBB->end()) {
421 HandlePHINodesInSuccessorBlocks(LLVMBB);
Dan Gohman3df24e62008-09-03 23:12:08 +0000422
Dan Gohman98ca4f22009-08-05 01:29:28 +0000423 // Lower the terminator after the copies are emitted.
Chris Lattner23dbf662010-03-31 04:24:50 +0000424 SetDebugLoc(LLVMBB->getTerminator(), SDB, 0, MF);
Dan Gohman2048b852009-11-23 18:04:58 +0000425 SDB->visit(*LLVMBB->getTerminator());
Dan Gohman07f111e2009-12-05 00:27:08 +0000426 ResetDebugLoc(SDB, 0);
Dan Gohman98ca4f22009-08-05 01:29:28 +0000427 }
Dan Gohman3df24e62008-09-03 23:12:08 +0000428 }
Daniel Dunbara279bc32009-09-20 02:20:51 +0000429
Chris Lattnera651cf62005-01-17 19:43:36 +0000430 // Make sure the root of the DAG is up-to-date.
Dan Gohman2048b852009-11-23 18:04:58 +0000431 CurDAG->setRoot(SDB->getControlRoot());
Arnold Schwaighoferc85e1712007-10-11 19:40:01 +0000432
Dan Gohmanf350b272008-08-23 02:25:05 +0000433 // Final step, emit the lowered DAG as machine code.
434 CodeGenAndEmitDAG();
Dan Gohman2048b852009-11-23 18:04:58 +0000435 HadTailCall = SDB->HasTailCall;
436 SDB->clear();
Chris Lattner1c08c712005-01-07 07:47:53 +0000437}
438
Evan Cheng54e146b2010-01-09 00:21:08 +0000439namespace {
440/// WorkListRemover - This class is a DAGUpdateListener that removes any deleted
441/// nodes from the worklist.
442class SDOPsWorkListRemover : public SelectionDAG::DAGUpdateListener {
443 SmallVector<SDNode*, 128> &Worklist;
Chris Lattner25e0ab92010-03-14 19:43:04 +0000444 SmallPtrSet<SDNode*, 128> &InWorklist;
Evan Cheng54e146b2010-01-09 00:21:08 +0000445public:
Chris Lattner25e0ab92010-03-14 19:43:04 +0000446 SDOPsWorkListRemover(SmallVector<SDNode*, 128> &wl,
447 SmallPtrSet<SDNode*, 128> &inwl)
448 : Worklist(wl), InWorklist(inwl) {}
Evan Cheng54e146b2010-01-09 00:21:08 +0000449
Chris Lattner25e0ab92010-03-14 19:43:04 +0000450 void RemoveFromWorklist(SDNode *N) {
451 if (!InWorklist.erase(N)) return;
452
453 SmallVector<SDNode*, 128>::iterator I =
454 std::find(Worklist.begin(), Worklist.end(), N);
455 assert(I != Worklist.end() && "Not in worklist");
456
457 *I = Worklist.back();
458 Worklist.pop_back();
459 }
460
Evan Cheng54e146b2010-01-09 00:21:08 +0000461 virtual void NodeDeleted(SDNode *N, SDNode *E) {
Chris Lattner25e0ab92010-03-14 19:43:04 +0000462 RemoveFromWorklist(N);
Evan Cheng54e146b2010-01-09 00:21:08 +0000463 }
464
465 virtual void NodeUpdated(SDNode *N) {
466 // Ignore updates.
467 }
468};
469}
470
Evan Cheng046632f2010-02-10 02:17:34 +0000471/// TrivialTruncElim - Eliminate some trivial nops that can result from
472/// ShrinkDemandedOps: (trunc (ext n)) -> n.
473static bool TrivialTruncElim(SDValue Op,
474 TargetLowering::TargetLoweringOpt &TLO) {
475 SDValue N0 = Op.getOperand(0);
476 EVT VT = Op.getValueType();
477 if ((N0.getOpcode() == ISD::ZERO_EXTEND ||
478 N0.getOpcode() == ISD::SIGN_EXTEND ||
479 N0.getOpcode() == ISD::ANY_EXTEND) &&
480 N0.getOperand(0).getValueType() == VT) {
481 return TLO.CombineTo(Op, N0.getOperand(0));
482 }
483 return false;
484}
485
Evan Cheng54eb4c22010-01-06 19:43:21 +0000486/// ShrinkDemandedOps - A late transformation pass that shrink expressions
487/// using TargetLowering::TargetLoweringOpt::ShrinkDemandedOp. It converts
488/// x+y to (VT)((SmallVT)x+(SmallVT)y) if the casts are free.
Evan Chengd40d03e2010-01-06 19:38:29 +0000489void SelectionDAGISel::ShrinkDemandedOps() {
490 SmallVector<SDNode*, 128> Worklist;
Chris Lattner25e0ab92010-03-14 19:43:04 +0000491 SmallPtrSet<SDNode*, 128> InWorklist;
Evan Chengd40d03e2010-01-06 19:38:29 +0000492
493 // Add all the dag nodes to the worklist.
494 Worklist.reserve(CurDAG->allnodes_size());
495 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
Chris Lattner25e0ab92010-03-14 19:43:04 +0000496 E = CurDAG->allnodes_end(); I != E; ++I) {
Evan Chengd40d03e2010-01-06 19:38:29 +0000497 Worklist.push_back(I);
Chris Lattner25e0ab92010-03-14 19:43:04 +0000498 InWorklist.insert(I);
499 }
Evan Chengd40d03e2010-01-06 19:38:29 +0000500
501 TargetLowering::TargetLoweringOpt TLO(*CurDAG, true);
502 while (!Worklist.empty()) {
Benjamin Kramer7b1e2a52010-01-07 17:27:56 +0000503 SDNode *N = Worklist.pop_back_val();
Chris Lattner25e0ab92010-03-14 19:43:04 +0000504 InWorklist.erase(N);
Evan Chengd40d03e2010-01-06 19:38:29 +0000505
506 if (N->use_empty() && N != CurDAG->getRoot().getNode()) {
Chris Lattnerc4a3f232010-03-14 19:46:02 +0000507 // Deleting this node may make its operands dead, add them to the worklist
508 // if they aren't already there.
509 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
510 if (InWorklist.insert(N->getOperand(i).getNode()))
511 Worklist.push_back(N->getOperand(i).getNode());
512
Evan Cheng54e146b2010-01-09 00:21:08 +0000513 CurDAG->DeleteNode(N);
Evan Chengd40d03e2010-01-06 19:38:29 +0000514 continue;
515 }
516
517 // Run ShrinkDemandedOp on scalar binary operations.
Chris Lattner25e0ab92010-03-14 19:43:04 +0000518 if (N->getNumValues() != 1 ||
519 !N->getValueType(0).isSimple() || !N->getValueType(0).isInteger())
520 continue;
521
522 unsigned BitWidth = N->getValueType(0).getScalarType().getSizeInBits();
523 APInt Demanded = APInt::getAllOnesValue(BitWidth);
524 APInt KnownZero, KnownOne;
525 if (!TLI.SimplifyDemandedBits(SDValue(N, 0), Demanded,
526 KnownZero, KnownOne, TLO) &&
527 (N->getOpcode() != ISD::TRUNCATE ||
528 !TrivialTruncElim(SDValue(N, 0), TLO)))
529 continue;
530
531 // Revisit the node.
532 assert(!InWorklist.count(N) && "Already in worklist");
533 Worklist.push_back(N);
534 InWorklist.insert(N);
Evan Chengd40d03e2010-01-06 19:38:29 +0000535
Chris Lattner25e0ab92010-03-14 19:43:04 +0000536 // Replace the old value with the new one.
537 DEBUG(errs() << "\nShrinkDemandedOps replacing ";
538 TLO.Old.getNode()->dump(CurDAG);
539 errs() << "\nWith: ";
540 TLO.New.getNode()->dump(CurDAG);
541 errs() << '\n');
Evan Chengd40d03e2010-01-06 19:38:29 +0000542
Chris Lattner25e0ab92010-03-14 19:43:04 +0000543 if (InWorklist.insert(TLO.New.getNode()))
544 Worklist.push_back(TLO.New.getNode());
Evan Cheng54e146b2010-01-09 00:21:08 +0000545
Chris Lattner25e0ab92010-03-14 19:43:04 +0000546 SDOPsWorkListRemover DeadNodes(Worklist, InWorklist);
547 CurDAG->ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, &DeadNodes);
Evan Chengd40d03e2010-01-06 19:38:29 +0000548
Chris Lattner25e0ab92010-03-14 19:43:04 +0000549 if (!TLO.Old.getNode()->use_empty()) continue;
550
551 for (unsigned i = 0, e = TLO.Old.getNode()->getNumOperands();
552 i != e; ++i) {
553 SDNode *OpNode = TLO.Old.getNode()->getOperand(i).getNode();
554 if (OpNode->hasOneUse()) {
555 // Add OpNode to the end of the list to revisit.
556 DeadNodes.RemoveFromWorklist(OpNode);
557 Worklist.push_back(OpNode);
558 InWorklist.insert(OpNode);
Evan Chengd40d03e2010-01-06 19:38:29 +0000559 }
560 }
Chris Lattner25e0ab92010-03-14 19:43:04 +0000561
562 DeadNodes.RemoveFromWorklist(TLO.Old.getNode());
563 CurDAG->DeleteNode(TLO.Old.getNode());
Evan Chengd40d03e2010-01-06 19:38:29 +0000564 }
565}
566
Dan Gohmanf350b272008-08-23 02:25:05 +0000567void SelectionDAGISel::ComputeLiveOutVRegInfo() {
Chris Lattneread0d882008-06-17 06:09:18 +0000568 SmallPtrSet<SDNode*, 128> VisitedNodes;
569 SmallVector<SDNode*, 128> Worklist;
Daniel Dunbara279bc32009-09-20 02:20:51 +0000570
Gabor Greifba36cb52008-08-28 21:40:38 +0000571 Worklist.push_back(CurDAG->getRoot().getNode());
Daniel Dunbara279bc32009-09-20 02:20:51 +0000572
Chris Lattneread0d882008-06-17 06:09:18 +0000573 APInt Mask;
574 APInt KnownZero;
575 APInt KnownOne;
Daniel Dunbara279bc32009-09-20 02:20:51 +0000576
Benjamin Kramer7b1e2a52010-01-07 17:27:56 +0000577 do {
578 SDNode *N = Worklist.pop_back_val();
Daniel Dunbara279bc32009-09-20 02:20:51 +0000579
Chris Lattneread0d882008-06-17 06:09:18 +0000580 // If we've already seen this node, ignore it.
581 if (!VisitedNodes.insert(N))
582 continue;
Daniel Dunbara279bc32009-09-20 02:20:51 +0000583
Chris Lattneread0d882008-06-17 06:09:18 +0000584 // Otherwise, add all chain operands to the worklist.
585 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
Owen Anderson825b72b2009-08-11 20:47:22 +0000586 if (N->getOperand(i).getValueType() == MVT::Other)
Gabor Greifba36cb52008-08-28 21:40:38 +0000587 Worklist.push_back(N->getOperand(i).getNode());
Daniel Dunbara279bc32009-09-20 02:20:51 +0000588
Chris Lattneread0d882008-06-17 06:09:18 +0000589 // If this is a CopyToReg with a vreg dest, process it.
590 if (N->getOpcode() != ISD::CopyToReg)
591 continue;
Daniel Dunbara279bc32009-09-20 02:20:51 +0000592
Chris Lattneread0d882008-06-17 06:09:18 +0000593 unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
594 if (!TargetRegisterInfo::isVirtualRegister(DestReg))
595 continue;
Daniel Dunbara279bc32009-09-20 02:20:51 +0000596
Chris Lattneread0d882008-06-17 06:09:18 +0000597 // Ignore non-scalar or non-integer values.
Dan Gohman475871a2008-07-27 21:46:04 +0000598 SDValue Src = N->getOperand(2);
Owen Andersone50ed302009-08-10 22:56:29 +0000599 EVT SrcVT = Src.getValueType();
Chris Lattneread0d882008-06-17 06:09:18 +0000600 if (!SrcVT.isInteger() || SrcVT.isVector())
601 continue;
Daniel Dunbara279bc32009-09-20 02:20:51 +0000602
Dan Gohmanf350b272008-08-23 02:25:05 +0000603 unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
Chris Lattneread0d882008-06-17 06:09:18 +0000604 Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits());
Dan Gohmanf350b272008-08-23 02:25:05 +0000605 CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne);
Daniel Dunbara279bc32009-09-20 02:20:51 +0000606
Chris Lattneread0d882008-06-17 06:09:18 +0000607 // Only install this information if it tells us something.
608 if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) {
609 DestReg -= TargetRegisterInfo::FirstVirtualRegister;
Dan Gohmanf7d6cd42009-08-01 03:51:09 +0000610 if (DestReg >= FuncInfo->LiveOutRegInfo.size())
611 FuncInfo->LiveOutRegInfo.resize(DestReg+1);
612 FunctionLoweringInfo::LiveOutInfo &LOI =
613 FuncInfo->LiveOutRegInfo[DestReg];
Chris Lattneread0d882008-06-17 06:09:18 +0000614 LOI.NumSignBits = NumSignBits;
Dan Gohmana80efce2009-03-27 23:55:04 +0000615 LOI.KnownOne = KnownOne;
616 LOI.KnownZero = KnownZero;
Chris Lattneread0d882008-06-17 06:09:18 +0000617 }
Benjamin Kramer7b1e2a52010-01-07 17:27:56 +0000618 } while (!Worklist.empty());
Chris Lattneread0d882008-06-17 06:09:18 +0000619}
620
Dan Gohmanf350b272008-08-23 02:25:05 +0000621void SelectionDAGISel::CodeGenAndEmitDAG() {
Dan Gohman462dc7f2008-07-21 20:00:07 +0000622 std::string GroupName;
623 if (TimePassesIsEnabled)
624 GroupName = "Instruction Selection and Scheduling";
625 std::string BlockName;
626 if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
Duncan Sands25cf2272008-11-24 14:53:14 +0000627 ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
628 ViewSUnitDAGs)
Dan Gohmanf7d6cd42009-08-01 03:51:09 +0000629 BlockName = MF->getFunction()->getNameStr() + ":" +
Daniel Dunbarf6ccee52009-07-24 08:24:36 +0000630 BB->getBasicBlock()->getNameStr();
Dan Gohman462dc7f2008-07-21 20:00:07 +0000631
David Greene1a053232010-01-05 01:26:11 +0000632 DEBUG(dbgs() << "Initial selection DAG:\n");
Dan Gohmanf350b272008-08-23 02:25:05 +0000633 DEBUG(CurDAG->dump());
Dan Gohman462dc7f2008-07-21 20:00:07 +0000634
Dan Gohmanf350b272008-08-23 02:25:05 +0000635 if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName);
Dan Gohman417e11b2007-10-08 15:12:17 +0000636
Chris Lattneraf21d552005-10-10 16:47:10 +0000637 // Run the DAG combiner in pre-legalize mode.
Evan Chengebffb662008-07-01 17:59:20 +0000638 if (TimePassesIsEnabled) {
Dan Gohman5e843682008-07-14 18:19:29 +0000639 NamedRegionTimer T("DAG Combining 1", GroupName);
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +0000640 CurDAG->Combine(Unrestricted, *AA, OptLevel);
Evan Chengebffb662008-07-01 17:59:20 +0000641 } else {
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +0000642 CurDAG->Combine(Unrestricted, *AA, OptLevel);
Evan Chengebffb662008-07-01 17:59:20 +0000643 }
Daniel Dunbara279bc32009-09-20 02:20:51 +0000644
David Greene1a053232010-01-05 01:26:11 +0000645 DEBUG(dbgs() << "Optimized lowered selection DAG:\n");
Dan Gohmanf350b272008-08-23 02:25:05 +0000646 DEBUG(CurDAG->dump());
Daniel Dunbara279bc32009-09-20 02:20:51 +0000647
Chris Lattner1c08c712005-01-07 07:47:53 +0000648 // Second step, hack on the DAG until it only uses operations and types that
649 // the target supports.
Dan Gohman714efc62009-12-05 17:51:33 +0000650 if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " +
651 BlockName);
Dan Gohman462dc7f2008-07-21 20:00:07 +0000652
Dan Gohman714efc62009-12-05 17:51:33 +0000653 bool Changed;
654 if (TimePassesIsEnabled) {
655 NamedRegionTimer T("Type Legalization", GroupName);
656 Changed = CurDAG->LegalizeTypes();
657 } else {
658 Changed = CurDAG->LegalizeTypes();
659 }
660
David Greene1a053232010-01-05 01:26:11 +0000661 DEBUG(dbgs() << "Type-legalized selection DAG:\n");
Dan Gohman714efc62009-12-05 17:51:33 +0000662 DEBUG(CurDAG->dump());
663
664 if (Changed) {
665 if (ViewDAGCombineLT)
666 CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
667
668 // Run the DAG combiner in post-type-legalize mode.
Dan Gohman462dc7f2008-07-21 20:00:07 +0000669 if (TimePassesIsEnabled) {
Dan Gohman714efc62009-12-05 17:51:33 +0000670 NamedRegionTimer T("DAG Combining after legalize types", GroupName);
671 CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);
Dan Gohman462dc7f2008-07-21 20:00:07 +0000672 } else {
Dan Gohman714efc62009-12-05 17:51:33 +0000673 CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);
Dan Gohman462dc7f2008-07-21 20:00:07 +0000674 }
675
David Greene1a053232010-01-05 01:26:11 +0000676 DEBUG(dbgs() << "Optimized type-legalized selection DAG:\n");
Dan Gohmanf350b272008-08-23 02:25:05 +0000677 DEBUG(CurDAG->dump());
Dan Gohman714efc62009-12-05 17:51:33 +0000678 }
Dan Gohman462dc7f2008-07-21 20:00:07 +0000679
Dan Gohman714efc62009-12-05 17:51:33 +0000680 if (TimePassesIsEnabled) {
681 NamedRegionTimer T("Vector Legalization", GroupName);
682 Changed = CurDAG->LegalizeVectors();
683 } else {
684 Changed = CurDAG->LegalizeVectors();
685 }
Duncan Sands25cf2272008-11-24 14:53:14 +0000686
Dan Gohman714efc62009-12-05 17:51:33 +0000687 if (Changed) {
Eli Friedman5c22c802009-05-23 12:35:30 +0000688 if (TimePassesIsEnabled) {
Dan Gohman714efc62009-12-05 17:51:33 +0000689 NamedRegionTimer T("Type Legalization 2", GroupName);
Bill Wendling98820072009-12-28 01:51:30 +0000690 CurDAG->LegalizeTypes();
Eli Friedman5c22c802009-05-23 12:35:30 +0000691 } else {
Bill Wendling98820072009-12-28 01:51:30 +0000692 CurDAG->LegalizeTypes();
Eli Friedman5c22c802009-05-23 12:35:30 +0000693 }
694
Dan Gohman714efc62009-12-05 17:51:33 +0000695 if (ViewDAGCombineLT)
696 CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
Eli Friedman5c22c802009-05-23 12:35:30 +0000697
Dan Gohman714efc62009-12-05 17:51:33 +0000698 // Run the DAG combiner in post-type-legalize mode.
699 if (TimePassesIsEnabled) {
700 NamedRegionTimer T("DAG Combining after legalize vectors", GroupName);
701 CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
702 } else {
703 CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
Eli Friedman5c22c802009-05-23 12:35:30 +0000704 }
Dan Gohman714efc62009-12-05 17:51:33 +0000705
David Greene1a053232010-01-05 01:26:11 +0000706 DEBUG(dbgs() << "Optimized vector-legalized selection DAG:\n");
Dan Gohman714efc62009-12-05 17:51:33 +0000707 DEBUG(CurDAG->dump());
Chris Lattner70587ea2008-07-10 23:37:50 +0000708 }
Daniel Dunbara279bc32009-09-20 02:20:51 +0000709
Dan Gohmanf350b272008-08-23 02:25:05 +0000710 if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName);
Dan Gohman462dc7f2008-07-21 20:00:07 +0000711
Evan Chengebffb662008-07-01 17:59:20 +0000712 if (TimePassesIsEnabled) {
Dan Gohman5e843682008-07-14 18:19:29 +0000713 NamedRegionTimer T("DAG Legalization", GroupName);
Dan Gohman714efc62009-12-05 17:51:33 +0000714 CurDAG->Legalize(OptLevel);
Evan Chengebffb662008-07-01 17:59:20 +0000715 } else {
Dan Gohman714efc62009-12-05 17:51:33 +0000716 CurDAG->Legalize(OptLevel);
Evan Chengebffb662008-07-01 17:59:20 +0000717 }
Daniel Dunbara279bc32009-09-20 02:20:51 +0000718
David Greene1a053232010-01-05 01:26:11 +0000719 DEBUG(dbgs() << "Legalized selection DAG:\n");
Dan Gohmanf350b272008-08-23 02:25:05 +0000720 DEBUG(CurDAG->dump());
Daniel Dunbara279bc32009-09-20 02:20:51 +0000721
Dan Gohmanf350b272008-08-23 02:25:05 +0000722 if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName);
Dan Gohman462dc7f2008-07-21 20:00:07 +0000723
Chris Lattneraf21d552005-10-10 16:47:10 +0000724 // Run the DAG combiner in post-legalize mode.
Evan Chengebffb662008-07-01 17:59:20 +0000725 if (TimePassesIsEnabled) {
Dan Gohman5e843682008-07-14 18:19:29 +0000726 NamedRegionTimer T("DAG Combining 2", GroupName);
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +0000727 CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
Evan Chengebffb662008-07-01 17:59:20 +0000728 } else {
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +0000729 CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
Evan Chengebffb662008-07-01 17:59:20 +0000730 }
Daniel Dunbara279bc32009-09-20 02:20:51 +0000731
David Greene1a053232010-01-05 01:26:11 +0000732 DEBUG(dbgs() << "Optimized legalized selection DAG:\n");
Dan Gohmanf350b272008-08-23 02:25:05 +0000733 DEBUG(CurDAG->dump());
Dan Gohman417e11b2007-10-08 15:12:17 +0000734
Evan Chengd40d03e2010-01-06 19:38:29 +0000735 if (OptLevel != CodeGenOpt::None) {
736 ShrinkDemandedOps();
Dan Gohmanf350b272008-08-23 02:25:05 +0000737 ComputeLiveOutVRegInfo();
Evan Chengd40d03e2010-01-06 19:38:29 +0000738 }
Evan Cheng552c4a82006-04-28 02:09:19 +0000739
Chris Lattner552186d2010-03-14 19:27:55 +0000740 if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName);
741
Chris Lattnera33ef482005-03-30 01:10:47 +0000742 // Third, instruction select all of the operations to machine code, adding the
743 // code to the MachineBasicBlock.
Evan Chengebffb662008-07-01 17:59:20 +0000744 if (TimePassesIsEnabled) {
Dan Gohman5e843682008-07-14 18:19:29 +0000745 NamedRegionTimer T("Instruction Selection", GroupName);
Chris Lattner7c306da2010-03-02 06:34:30 +0000746 DoInstructionSelection();
Evan Chengebffb662008-07-01 17:59:20 +0000747 } else {
Chris Lattner7c306da2010-03-02 06:34:30 +0000748 DoInstructionSelection();
Evan Chengebffb662008-07-01 17:59:20 +0000749 }
Evan Chengdb8d56b2008-06-30 20:45:06 +0000750
David Greene1a053232010-01-05 01:26:11 +0000751 DEBUG(dbgs() << "Selected selection DAG:\n");
Dan Gohmanf350b272008-08-23 02:25:05 +0000752 DEBUG(CurDAG->dump());
Dan Gohman462dc7f2008-07-21 20:00:07 +0000753
Dan Gohmanf350b272008-08-23 02:25:05 +0000754 if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName);
Dan Gohman462dc7f2008-07-21 20:00:07 +0000755
Dan Gohman5e843682008-07-14 18:19:29 +0000756 // Schedule machine code.
Dan Gohman47ac0f02009-02-11 04:27:20 +0000757 ScheduleDAGSDNodes *Scheduler = CreateScheduler();
Dan Gohman5e843682008-07-14 18:19:29 +0000758 if (TimePassesIsEnabled) {
759 NamedRegionTimer T("Instruction Scheduling", GroupName);
Dan Gohman47ac0f02009-02-11 04:27:20 +0000760 Scheduler->Run(CurDAG, BB, BB->end());
Dan Gohman5e843682008-07-14 18:19:29 +0000761 } else {
Dan Gohman47ac0f02009-02-11 04:27:20 +0000762 Scheduler->Run(CurDAG, BB, BB->end());
Dan Gohman5e843682008-07-14 18:19:29 +0000763 }
764
Dan Gohman462dc7f2008-07-21 20:00:07 +0000765 if (ViewSUnitDAGs) Scheduler->viewGraph();
766
Daniel Dunbara279bc32009-09-20 02:20:51 +0000767 // Emit machine code to BB. This can change 'BB' to the last block being
Evan Chengdb8d56b2008-06-30 20:45:06 +0000768 // inserted into.
Evan Chengebffb662008-07-01 17:59:20 +0000769 if (TimePassesIsEnabled) {
Dan Gohman5e843682008-07-14 18:19:29 +0000770 NamedRegionTimer T("Instruction Creation", GroupName);
Dan Gohman2048b852009-11-23 18:04:58 +0000771 BB = Scheduler->EmitSchedule(&SDB->EdgeMapping);
Evan Chengebffb662008-07-01 17:59:20 +0000772 } else {
Dan Gohman2048b852009-11-23 18:04:58 +0000773 BB = Scheduler->EmitSchedule(&SDB->EdgeMapping);
Dan Gohman5e843682008-07-14 18:19:29 +0000774 }
775
776 // Free the scheduler state.
777 if (TimePassesIsEnabled) {
778 NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName);
779 delete Scheduler;
780 } else {
781 delete Scheduler;
Evan Chengebffb662008-07-01 17:59:20 +0000782 }
Evan Chengdb8d56b2008-06-30 20:45:06 +0000783
David Greene1a053232010-01-05 01:26:11 +0000784 DEBUG(dbgs() << "Selected machine code:\n");
Chris Lattner1c08c712005-01-07 07:47:53 +0000785 DEBUG(BB->dump());
Daniel Dunbara279bc32009-09-20 02:20:51 +0000786}
Chris Lattner1c08c712005-01-07 07:47:53 +0000787
Chris Lattner7c306da2010-03-02 06:34:30 +0000788void SelectionDAGISel::DoInstructionSelection() {
789 DEBUG(errs() << "===== Instruction selection begins:\n");
790
791 PreprocessISelDAG();
792
793 // Select target instructions for the DAG.
794 {
795 // Number all nodes with a topological order and set DAGSize.
796 DAGSize = CurDAG->AssignTopologicalOrder();
797
798 // Create a dummy node (which is not added to allnodes), that adds
799 // a reference to the root node, preventing it from being deleted,
800 // and tracking any changes of the root.
801 HandleSDNode Dummy(CurDAG->getRoot());
802 ISelPosition = SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode());
803 ++ISelPosition;
804
805 // The AllNodes list is now topological-sorted. Visit the
806 // nodes by starting at the end of the list (the root of the
807 // graph) and preceding back toward the beginning (the entry
808 // node).
809 while (ISelPosition != CurDAG->allnodes_begin()) {
810 SDNode *Node = --ISelPosition;
811 // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
812 // but there are currently some corner cases that it misses. Also, this
813 // makes it theoretically possible to disable the DAGCombiner.
814 if (Node->use_empty())
815 continue;
816
817 SDNode *ResNode = Select(Node);
818
Chris Lattner82dd3d32010-03-02 07:50:03 +0000819 // FIXME: This is pretty gross. 'Select' should be changed to not return
820 // anything at all and this code should be nuked with a tactical strike.
821
Chris Lattner7c306da2010-03-02 06:34:30 +0000822 // If node should not be replaced, continue with the next one.
Chris Lattner82dd3d32010-03-02 07:50:03 +0000823 if (ResNode == Node || Node->getOpcode() == ISD::DELETED_NODE)
Chris Lattner7c306da2010-03-02 06:34:30 +0000824 continue;
825 // Replace node.
826 if (ResNode)
827 ReplaceUses(Node, ResNode);
828
829 // If after the replacement this node is not used any more,
830 // remove this dead node.
831 if (Node->use_empty()) { // Don't delete EntryToken, etc.
832 ISelUpdater ISU(ISelPosition);
833 CurDAG->RemoveDeadNode(Node, &ISU);
834 }
835 }
836
837 CurDAG->setRoot(Dummy.getValue());
838 }
839 DEBUG(errs() << "===== Instruction selection ends:\n");
840
841 PostprocessISelDAG();
Chris Lattner7c306da2010-03-02 06:34:30 +0000842}
843
844
Dan Gohman79ce2762009-01-15 19:20:50 +0000845void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn,
846 MachineFunction &MF,
Dan Gohmandd5b58a2008-10-14 23:54:11 +0000847 MachineModuleInfo *MMI,
848 const TargetInstrInfo &TII) {
Dan Gohmana43abd12008-09-29 21:55:50 +0000849 // Initialize the Fast-ISel state, if needed.
850 FastISel *FastIS = 0;
851 if (EnableFastISel)
Chris Lattnerd850ac72010-04-05 02:19:28 +0000852 FastIS = TLI.createFastISel(MF, MMI,
Dan Gohmana43abd12008-09-29 21:55:50 +0000853 FuncInfo->ValueMap,
854 FuncInfo->MBBMap,
Dan Gohmandd5b58a2008-10-14 23:54:11 +0000855 FuncInfo->StaticAllocaMap
856#ifndef NDEBUG
857 , FuncInfo->CatchInfoLost
858#endif
859 );
Dan Gohmana43abd12008-09-29 21:55:50 +0000860
861 // Iterate over all basic blocks in the function.
Evan Cheng39fd6e82008-08-07 00:43:25 +0000862 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
863 BasicBlock *LLVMBB = &*I;
Dan Gohman7c3234c2008-08-27 23:52:12 +0000864 BB = FuncInfo->MBBMap[LLVMBB];
Dan Gohmanf350b272008-08-23 02:25:05 +0000865
Dan Gohman3df24e62008-09-03 23:12:08 +0000866 BasicBlock::iterator const Begin = LLVMBB->begin();
867 BasicBlock::iterator const End = LLVMBB->end();
Evan Cheng9f118502008-09-08 16:01:27 +0000868 BasicBlock::iterator BI = Begin;
Dan Gohman5edd3612008-08-28 20:28:56 +0000869
870 // Lower any arguments needed in this block if this is the entry block.
Dan Gohman33134c42008-09-25 17:05:24 +0000871 bool SuppressFastISel = false;
872 if (LLVMBB == &Fn.getEntryBlock()) {
Dan Gohman5edd3612008-08-28 20:28:56 +0000873 LowerArguments(LLVMBB);
Dan Gohmanf350b272008-08-23 02:25:05 +0000874
Dan Gohman33134c42008-09-25 17:05:24 +0000875 // If any of the arguments has the byval attribute, forgo
876 // fast-isel in the entry block.
Dan Gohmana43abd12008-09-29 21:55:50 +0000877 if (FastIS) {
Dan Gohman33134c42008-09-25 17:05:24 +0000878 unsigned j = 1;
879 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end();
880 I != E; ++I, ++j)
Devang Patel05988662008-09-25 21:00:45 +0000881 if (Fn.paramHasAttr(j, Attribute::ByVal)) {
Dan Gohman77ca41e2008-09-25 17:21:42 +0000882 if (EnableFastISelVerbose || EnableFastISelAbort)
David Greene1a053232010-01-05 01:26:11 +0000883 dbgs() << "FastISel skips entry block due to byval argument\n";
Dan Gohman33134c42008-09-25 17:05:24 +0000884 SuppressFastISel = true;
885 break;
886 }
887 }
888 }
889
Dan Gohmandd5b58a2008-10-14 23:54:11 +0000890 if (MMI && BB->isLandingPad()) {
891 // Add a label to mark the beginning of the landing pad. Deletion of the
892 // landing pad can thus be detected via the MachineModuleInfo.
Chris Lattner7561d482010-03-14 02:33:54 +0000893 MCSymbol *Label = MMI->addLandingPad(BB);
Dan Gohmandd5b58a2008-10-14 23:54:11 +0000894
Chris Lattner518bb532010-02-09 19:54:29 +0000895 const TargetInstrDesc &II = TII.get(TargetOpcode::EH_LABEL);
Chris Lattner7561d482010-03-14 02:33:54 +0000896 BuildMI(BB, SDB->getCurDebugLoc(), II).addSym(Label);
Dan Gohmandd5b58a2008-10-14 23:54:11 +0000897
898 // Mark exception register as live in.
899 unsigned Reg = TLI.getExceptionAddressRegister();
900 if (Reg) BB->addLiveIn(Reg);
901
902 // Mark exception selector register as live in.
903 Reg = TLI.getExceptionSelectorRegister();
904 if (Reg) BB->addLiveIn(Reg);
905
906 // FIXME: Hack around an exception handling flaw (PR1508): the personality
907 // function and list of typeids logically belong to the invoke (or, if you
908 // like, the basic block containing the invoke), and need to be associated
909 // with it in the dwarf exception handling tables. Currently however the
910 // information is provided by an intrinsic (eh.selector) that can be moved
911 // to unexpected places by the optimizers: if the unwind edge is critical,
912 // then breaking it can result in the intrinsics being in the successor of
Jim Grosbachf4549b02010-01-15 00:36:15 +0000913 // the landing pad, not the landing pad itself. This results
914 // in exceptions not being caught because no typeids are associated with
915 // the invoke. This may not be the only way things can go wrong, but it
916 // is the only way we try to work around for the moment.
Dan Gohmandd5b58a2008-10-14 23:54:11 +0000917 BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator());
918
919 if (Br && Br->isUnconditional()) { // Critical edge?
920 BasicBlock::iterator I, E;
921 for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I)
922 if (isa<EHSelectorInst>(I))
923 break;
924
925 if (I == E)
926 // No catch info found - try to extract some from the successor.
Dan Gohman5fca8b12009-11-23 18:12:11 +0000927 CopyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo);
Dan Gohmandd5b58a2008-10-14 23:54:11 +0000928 }
929 }
930
Dan Gohmanf350b272008-08-23 02:25:05 +0000931 // Before doing SelectionDAG ISel, see if FastISel has been requested.
Dan Gohmandd5b58a2008-10-14 23:54:11 +0000932 if (FastIS && !SuppressFastISel) {
Dan Gohmana43abd12008-09-29 21:55:50 +0000933 // Emit code for any incoming arguments. This must happen before
934 // beginning FastISel on the entry block.
935 if (LLVMBB == &Fn.getEntryBlock()) {
Dan Gohman2048b852009-11-23 18:04:58 +0000936 CurDAG->setRoot(SDB->getControlRoot());
Dan Gohmana43abd12008-09-29 21:55:50 +0000937 CodeGenAndEmitDAG();
Dan Gohman2048b852009-11-23 18:04:58 +0000938 SDB->clear();
Dan Gohmana43abd12008-09-29 21:55:50 +0000939 }
Dan Gohman241f4642008-10-04 00:56:36 +0000940 FastIS->startNewBlock(BB);
Dan Gohmana43abd12008-09-29 21:55:50 +0000941 // Do FastISel on as many instructions as possible.
942 for (; BI != End; ++BI) {
943 // Just before the terminator instruction, insert instructions to
944 // feed PHI nodes in successor blocks.
945 if (isa<TerminatorInst>(BI))
946 if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, FastIS)) {
Chris Lattnerc19ae9d2010-03-04 19:46:56 +0000947 ++NumFastIselFailures;
Dan Gohman07f111e2009-12-05 00:27:08 +0000948 ResetDebugLoc(SDB, FastIS);
Dan Gohman4344a5d2008-09-09 23:05:00 +0000949 if (EnableFastISelVerbose || EnableFastISelAbort) {
David Greene1a053232010-01-05 01:26:11 +0000950 dbgs() << "FastISel miss: ";
Dan Gohman293d5f82008-09-09 22:06:46 +0000951 BI->dump();
952 }
Daniel Dunbara279bc32009-09-20 02:20:51 +0000953 assert(!EnableFastISelAbort &&
Torok Edwinf3689232009-07-12 20:07:01 +0000954 "FastISel didn't handle a PHI in a successor");
Dan Gohmana43abd12008-09-29 21:55:50 +0000955 break;
Dan Gohmanf350b272008-08-23 02:25:05 +0000956 }
Dan Gohmana43abd12008-09-29 21:55:50 +0000957
Chris Lattner23dbf662010-03-31 04:24:50 +0000958 SetDebugLoc(BI, SDB, FastIS, &MF);
Dan Gohman381ca552009-12-05 01:29:04 +0000959
Dan Gohman21c14e32010-01-12 04:32:35 +0000960 // Try to select the instruction with FastISel.
Dan Gohman07f111e2009-12-05 00:27:08 +0000961 if (FastIS->SelectInstruction(BI)) {
962 ResetDebugLoc(SDB, FastIS);
Dan Gohmana43abd12008-09-29 21:55:50 +0000963 continue;
Dan Gohman07f111e2009-12-05 00:27:08 +0000964 }
Dan Gohmana43abd12008-09-29 21:55:50 +0000965
Dan Gohman07f111e2009-12-05 00:27:08 +0000966 // Clear out the debug location so that it doesn't carry over to
967 // unrelated instructions.
968 ResetDebugLoc(SDB, FastIS);
Dan Gohmana43abd12008-09-29 21:55:50 +0000969
970 // Then handle certain instructions as single-LLVM-Instruction blocks.
971 if (isa<CallInst>(BI)) {
Chris Lattnerc19ae9d2010-03-04 19:46:56 +0000972 ++NumFastIselFailures;
Dan Gohmana43abd12008-09-29 21:55:50 +0000973 if (EnableFastISelVerbose || EnableFastISelAbort) {
David Greene1a053232010-01-05 01:26:11 +0000974 dbgs() << "FastISel missed call: ";
Dan Gohmana43abd12008-09-29 21:55:50 +0000975 BI->dump();
976 }
977
Benjamin Kramerf0127052010-01-05 13:12:22 +0000978 if (!BI->getType()->isVoidTy()) {
Dan Gohmana43abd12008-09-29 21:55:50 +0000979 unsigned &R = FuncInfo->ValueMap[BI];
980 if (!R)
981 R = FuncInfo->CreateRegForValue(BI);
982 }
983
Dan Gohmanb4afb132009-11-20 02:51:26 +0000984 bool HadTailCall = false;
Chris Lattner7896c9f2009-12-03 00:50:42 +0000985 SelectBasicBlock(LLVMBB, BI, llvm::next(BI), HadTailCall);
Dan Gohmanb4afb132009-11-20 02:51:26 +0000986
987 // If the call was emitted as a tail call, we're done with the block.
988 if (HadTailCall) {
989 BI = End;
990 break;
991 }
992
Dan Gohman241f4642008-10-04 00:56:36 +0000993 // If the instruction was codegen'd with multiple blocks,
994 // inform the FastISel object where to resume inserting.
995 FastIS->setCurrentBlock(BB);
Dan Gohmana43abd12008-09-29 21:55:50 +0000996 continue;
Dan Gohmanf350b272008-08-23 02:25:05 +0000997 }
Dan Gohmana43abd12008-09-29 21:55:50 +0000998
999 // Otherwise, give up on FastISel for the rest of the block.
1000 // For now, be a little lenient about non-branch terminators.
1001 if (!isa<TerminatorInst>(BI) || isa<BranchInst>(BI)) {
Chris Lattnerc19ae9d2010-03-04 19:46:56 +00001002 ++NumFastIselFailures;
Dan Gohmana43abd12008-09-29 21:55:50 +00001003 if (EnableFastISelVerbose || EnableFastISelAbort) {
David Greene1a053232010-01-05 01:26:11 +00001004 dbgs() << "FastISel miss: ";
Dan Gohmana43abd12008-09-29 21:55:50 +00001005 BI->dump();
1006 }
1007 if (EnableFastISelAbort)
1008 // The "fast" selector couldn't handle something and bailed.
1009 // For the purpose of debugging, just abort.
Torok Edwinc23197a2009-07-14 16:55:14 +00001010 llvm_unreachable("FastISel didn't select the entire block");
Dan Gohmana43abd12008-09-29 21:55:50 +00001011 }
1012 break;
Dan Gohmanf350b272008-08-23 02:25:05 +00001013 }
1014 }
1015
Dan Gohmand2ff6472008-09-02 20:17:56 +00001016 // Run SelectionDAG instruction selection on the remainder of the block
1017 // not handled by FastISel. If FastISel is not run, this is the entire
Dan Gohman3df24e62008-09-03 23:12:08 +00001018 // block.
Devang Patel390f3ac2009-04-16 01:33:10 +00001019 if (BI != End) {
Dan Gohmanb4afb132009-11-20 02:51:26 +00001020 bool HadTailCall;
1021 SelectBasicBlock(LLVMBB, BI, End, HadTailCall);
Devang Patel390f3ac2009-04-16 01:33:10 +00001022 }
Dan Gohmanf350b272008-08-23 02:25:05 +00001023
Dan Gohman7c3234c2008-08-27 23:52:12 +00001024 FinishBasicBlock();
Evan Cheng39fd6e82008-08-07 00:43:25 +00001025 }
Dan Gohmana43abd12008-09-29 21:55:50 +00001026
1027 delete FastIS;
Dan Gohman0e5f1302008-07-07 23:02:41 +00001028}
1029
Dan Gohmanfed90b62008-07-28 21:51:04 +00001030void
Dan Gohman7c3234c2008-08-27 23:52:12 +00001031SelectionDAGISel::FinishBasicBlock() {
Dan Gohmanf350b272008-08-23 02:25:05 +00001032
David Greene1a053232010-01-05 01:26:11 +00001033 DEBUG(dbgs() << "Target-post-processed machine code:\n");
Dan Gohmanf350b272008-08-23 02:25:05 +00001034 DEBUG(BB->dump());
Nate Begemanf15485a2006-03-27 01:32:24 +00001035
David Greene1a053232010-01-05 01:26:11 +00001036 DEBUG(dbgs() << "Total amount of phi nodes to update: "
Dan Gohman2048b852009-11-23 18:04:58 +00001037 << SDB->PHINodesToUpdate.size() << "\n");
1038 DEBUG(for (unsigned i = 0, e = SDB->PHINodesToUpdate.size(); i != e; ++i)
David Greene1a053232010-01-05 01:26:11 +00001039 dbgs() << "Node " << i << " : ("
Dan Gohman2048b852009-11-23 18:04:58 +00001040 << SDB->PHINodesToUpdate[i].first
1041 << ", " << SDB->PHINodesToUpdate[i].second << ")\n");
Daniel Dunbara279bc32009-09-20 02:20:51 +00001042
Chris Lattnera33ef482005-03-30 01:10:47 +00001043 // Next, now that we know what the last MBB the LLVM BB expanded is, update
Chris Lattner1c08c712005-01-07 07:47:53 +00001044 // PHI nodes in successors.
Dan Gohman2048b852009-11-23 18:04:58 +00001045 if (SDB->SwitchCases.empty() &&
1046 SDB->JTCases.empty() &&
1047 SDB->BitTestCases.empty()) {
1048 for (unsigned i = 0, e = SDB->PHINodesToUpdate.size(); i != e; ++i) {
1049 MachineInstr *PHI = SDB->PHINodesToUpdate[i].first;
Chris Lattner518bb532010-02-09 19:54:29 +00001050 assert(PHI->isPHI() &&
Nate Begemanf15485a2006-03-27 01:32:24 +00001051 "This is not a machine PHI node that we are updating!");
Jakob Stoklund Olesen580bba22010-03-05 21:49:10 +00001052 if (!BB->isSuccessor(PHI->getParent()))
1053 continue;
Dan Gohman2048b852009-11-23 18:04:58 +00001054 PHI->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[i].second,
Chris Lattner9ce2e9d2007-12-30 00:57:42 +00001055 false));
1056 PHI->addOperand(MachineOperand::CreateMBB(BB));
Nate Begemanf15485a2006-03-27 01:32:24 +00001057 }
Dan Gohman2048b852009-11-23 18:04:58 +00001058 SDB->PHINodesToUpdate.clear();
Nate Begemanf15485a2006-03-27 01:32:24 +00001059 return;
Chris Lattner1c08c712005-01-07 07:47:53 +00001060 }
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001061
Dan Gohman2048b852009-11-23 18:04:58 +00001062 for (unsigned i = 0, e = SDB->BitTestCases.size(); i != e; ++i) {
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001063 // Lower header first, if it wasn't already lowered
Dan Gohman2048b852009-11-23 18:04:58 +00001064 if (!SDB->BitTestCases[i].Emitted) {
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001065 // Set the current basic block to the mbb we wish to insert the code into
Dan Gohman2048b852009-11-23 18:04:58 +00001066 BB = SDB->BitTestCases[i].Parent;
1067 SDB->setCurrentBasicBlock(BB);
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001068 // Emit the code
Dan Gohman2048b852009-11-23 18:04:58 +00001069 SDB->visitBitTestHeader(SDB->BitTestCases[i]);
1070 CurDAG->setRoot(SDB->getRoot());
Dan Gohmanf350b272008-08-23 02:25:05 +00001071 CodeGenAndEmitDAG();
Dan Gohman2048b852009-11-23 18:04:58 +00001072 SDB->clear();
Daniel Dunbara279bc32009-09-20 02:20:51 +00001073 }
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001074
Dan Gohman2048b852009-11-23 18:04:58 +00001075 for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) {
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001076 // Set the current basic block to the mbb we wish to insert the code into
Dan Gohman2048b852009-11-23 18:04:58 +00001077 BB = SDB->BitTestCases[i].Cases[j].ThisBB;
1078 SDB->setCurrentBasicBlock(BB);
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001079 // Emit the code
1080 if (j+1 != ej)
Dan Gohman2048b852009-11-23 18:04:58 +00001081 SDB->visitBitTestCase(SDB->BitTestCases[i].Cases[j+1].ThisBB,
1082 SDB->BitTestCases[i].Reg,
1083 SDB->BitTestCases[i].Cases[j]);
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001084 else
Dan Gohman2048b852009-11-23 18:04:58 +00001085 SDB->visitBitTestCase(SDB->BitTestCases[i].Default,
1086 SDB->BitTestCases[i].Reg,
1087 SDB->BitTestCases[i].Cases[j]);
Daniel Dunbara279bc32009-09-20 02:20:51 +00001088
1089
Dan Gohman2048b852009-11-23 18:04:58 +00001090 CurDAG->setRoot(SDB->getRoot());
Dan Gohmanf350b272008-08-23 02:25:05 +00001091 CodeGenAndEmitDAG();
Dan Gohman2048b852009-11-23 18:04:58 +00001092 SDB->clear();
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001093 }
1094
1095 // Update PHI Nodes
Dan Gohman2048b852009-11-23 18:04:58 +00001096 for (unsigned pi = 0, pe = SDB->PHINodesToUpdate.size(); pi != pe; ++pi) {
1097 MachineInstr *PHI = SDB->PHINodesToUpdate[pi].first;
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001098 MachineBasicBlock *PHIBB = PHI->getParent();
Chris Lattner518bb532010-02-09 19:54:29 +00001099 assert(PHI->isPHI() &&
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001100 "This is not a machine PHI node that we are updating!");
1101 // This is "default" BB. We have two jumps to it. From "header" BB and
1102 // from last "case" BB.
Dan Gohman2048b852009-11-23 18:04:58 +00001103 if (PHIBB == SDB->BitTestCases[i].Default) {
Jim Grosbachf4549b02010-01-15 00:36:15 +00001104 PHI->addOperand(MachineOperand::
1105 CreateReg(SDB->PHINodesToUpdate[pi].second, false));
Dan Gohman2048b852009-11-23 18:04:58 +00001106 PHI->addOperand(MachineOperand::CreateMBB(SDB->BitTestCases[i].Parent));
Jim Grosbachf4549b02010-01-15 00:36:15 +00001107 PHI->addOperand(MachineOperand::
1108 CreateReg(SDB->PHINodesToUpdate[pi].second, false));
Dan Gohman2048b852009-11-23 18:04:58 +00001109 PHI->addOperand(MachineOperand::CreateMBB(SDB->BitTestCases[i].Cases.
Chris Lattner9ce2e9d2007-12-30 00:57:42 +00001110 back().ThisBB));
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001111 }
1112 // One of "cases" BB.
Dan Gohman2048b852009-11-23 18:04:58 +00001113 for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size();
Dan Gohman7c3234c2008-08-27 23:52:12 +00001114 j != ej; ++j) {
Dan Gohman2048b852009-11-23 18:04:58 +00001115 MachineBasicBlock* cBB = SDB->BitTestCases[i].Cases[j].ThisBB;
Jakob Stoklund Olesendd437ba2010-01-11 21:02:33 +00001116 if (cBB->isSuccessor(PHIBB)) {
Jim Grosbachf4549b02010-01-15 00:36:15 +00001117 PHI->addOperand(MachineOperand::
1118 CreateReg(SDB->PHINodesToUpdate[pi].second, false));
Chris Lattner9ce2e9d2007-12-30 00:57:42 +00001119 PHI->addOperand(MachineOperand::CreateMBB(cBB));
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001120 }
1121 }
1122 }
1123 }
Dan Gohman2048b852009-11-23 18:04:58 +00001124 SDB->BitTestCases.clear();
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001125
Nate Begeman9453eea2006-04-23 06:26:20 +00001126 // If the JumpTable record is filled in, then we need to emit a jump table.
1127 // Updating the PHI nodes is tricky in this case, since we need to determine
1128 // whether the PHI is a successor of the range check MBB or the jump table MBB
Dan Gohman2048b852009-11-23 18:04:58 +00001129 for (unsigned i = 0, e = SDB->JTCases.size(); i != e; ++i) {
Anton Korobeynikov3a84b9b2007-03-25 15:07:15 +00001130 // Lower header first, if it wasn't already lowered
Dan Gohman2048b852009-11-23 18:04:58 +00001131 if (!SDB->JTCases[i].first.Emitted) {
Anton Korobeynikov3a84b9b2007-03-25 15:07:15 +00001132 // Set the current basic block to the mbb we wish to insert the code into
Dan Gohman2048b852009-11-23 18:04:58 +00001133 BB = SDB->JTCases[i].first.HeaderBB;
1134 SDB->setCurrentBasicBlock(BB);
Anton Korobeynikov3a84b9b2007-03-25 15:07:15 +00001135 // Emit the code
Dan Gohman2048b852009-11-23 18:04:58 +00001136 SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first);
1137 CurDAG->setRoot(SDB->getRoot());
Dan Gohmanf350b272008-08-23 02:25:05 +00001138 CodeGenAndEmitDAG();
Dan Gohman2048b852009-11-23 18:04:58 +00001139 SDB->clear();
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001140 }
Daniel Dunbara279bc32009-09-20 02:20:51 +00001141
Nate Begeman37efe672006-04-22 18:53:45 +00001142 // Set the current basic block to the mbb we wish to insert the code into
Dan Gohman2048b852009-11-23 18:04:58 +00001143 BB = SDB->JTCases[i].second.MBB;
1144 SDB->setCurrentBasicBlock(BB);
Nate Begeman37efe672006-04-22 18:53:45 +00001145 // Emit the code
Dan Gohman2048b852009-11-23 18:04:58 +00001146 SDB->visitJumpTable(SDB->JTCases[i].second);
1147 CurDAG->setRoot(SDB->getRoot());
Dan Gohmanf350b272008-08-23 02:25:05 +00001148 CodeGenAndEmitDAG();
Dan Gohman2048b852009-11-23 18:04:58 +00001149 SDB->clear();
Daniel Dunbara279bc32009-09-20 02:20:51 +00001150
Nate Begeman37efe672006-04-22 18:53:45 +00001151 // Update PHI Nodes
Dan Gohman2048b852009-11-23 18:04:58 +00001152 for (unsigned pi = 0, pe = SDB->PHINodesToUpdate.size(); pi != pe; ++pi) {
1153 MachineInstr *PHI = SDB->PHINodesToUpdate[pi].first;
Nate Begeman37efe672006-04-22 18:53:45 +00001154 MachineBasicBlock *PHIBB = PHI->getParent();
Chris Lattner518bb532010-02-09 19:54:29 +00001155 assert(PHI->isPHI() &&
Nate Begeman37efe672006-04-22 18:53:45 +00001156 "This is not a machine PHI node that we are updating!");
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001157 // "default" BB. We can go there only from header BB.
Dan Gohman2048b852009-11-23 18:04:58 +00001158 if (PHIBB == SDB->JTCases[i].second.Default) {
Evan Chengce319102009-09-19 09:51:03 +00001159 PHI->addOperand
Dan Gohman2048b852009-11-23 18:04:58 +00001160 (MachineOperand::CreateReg(SDB->PHINodesToUpdate[pi].second, false));
Evan Chengce319102009-09-19 09:51:03 +00001161 PHI->addOperand
Dan Gohman2048b852009-11-23 18:04:58 +00001162 (MachineOperand::CreateMBB(SDB->JTCases[i].first.HeaderBB));
Nate Begemanf4360a42006-05-03 03:48:02 +00001163 }
Anton Korobeynikov4198c582007-04-09 12:31:58 +00001164 // JT BB. Just iterate over successors here
Jakob Stoklund Olesendd437ba2010-01-11 21:02:33 +00001165 if (BB->isSuccessor(PHIBB)) {
Evan Chengce319102009-09-19 09:51:03 +00001166 PHI->addOperand
Dan Gohman2048b852009-11-23 18:04:58 +00001167 (MachineOperand::CreateReg(SDB->PHINodesToUpdate[pi].second, false));
Chris Lattner9ce2e9d2007-12-30 00:57:42 +00001168 PHI->addOperand(MachineOperand::CreateMBB(BB));
Nate Begeman37efe672006-04-22 18:53:45 +00001169 }
1170 }
Nate Begeman37efe672006-04-22 18:53:45 +00001171 }
Dan Gohman2048b852009-11-23 18:04:58 +00001172 SDB->JTCases.clear();
Daniel Dunbara279bc32009-09-20 02:20:51 +00001173
Chris Lattnerb2e806e2006-10-22 23:00:53 +00001174 // If the switch block involved a branch to one of the actual successors, we
1175 // need to update PHI nodes in that block.
Dan Gohman2048b852009-11-23 18:04:58 +00001176 for (unsigned i = 0, e = SDB->PHINodesToUpdate.size(); i != e; ++i) {
1177 MachineInstr *PHI = SDB->PHINodesToUpdate[i].first;
Chris Lattner518bb532010-02-09 19:54:29 +00001178 assert(PHI->isPHI() &&
Chris Lattnerb2e806e2006-10-22 23:00:53 +00001179 "This is not a machine PHI node that we are updating!");
1180 if (BB->isSuccessor(PHI->getParent())) {
Dan Gohman2048b852009-11-23 18:04:58 +00001181 PHI->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[i].second,
Chris Lattner9ce2e9d2007-12-30 00:57:42 +00001182 false));
1183 PHI->addOperand(MachineOperand::CreateMBB(BB));
Chris Lattnerb2e806e2006-10-22 23:00:53 +00001184 }
1185 }
Daniel Dunbara279bc32009-09-20 02:20:51 +00001186
Nate Begemanf15485a2006-03-27 01:32:24 +00001187 // If we generated any switch lowering information, build and codegen any
1188 // additional DAGs necessary.
Dan Gohman2048b852009-11-23 18:04:58 +00001189 for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) {
Nate Begemanf15485a2006-03-27 01:32:24 +00001190 // Set the current basic block to the mbb we wish to insert the code into
Dan Gohman2048b852009-11-23 18:04:58 +00001191 MachineBasicBlock *ThisBB = BB = SDB->SwitchCases[i].ThisBB;
1192 SDB->setCurrentBasicBlock(BB);
Daniel Dunbara279bc32009-09-20 02:20:51 +00001193
Nate Begemanf15485a2006-03-27 01:32:24 +00001194 // Emit the code
Dan Gohman2048b852009-11-23 18:04:58 +00001195 SDB->visitSwitchCase(SDB->SwitchCases[i]);
1196 CurDAG->setRoot(SDB->getRoot());
Dan Gohmanf350b272008-08-23 02:25:05 +00001197 CodeGenAndEmitDAG();
Daniel Dunbara279bc32009-09-20 02:20:51 +00001198
Chris Lattnerd5e93c02006-09-07 01:59:34 +00001199 // Handle any PHI nodes in successors of this chunk, as if we were coming
1200 // from the original BB before switch expansion. Note that PHI nodes can
1201 // occur multiple times in PHINodesToUpdate. We have to be very careful to
1202 // handle them the right number of times.
Dan Gohman2048b852009-11-23 18:04:58 +00001203 while ((BB = SDB->SwitchCases[i].TrueBB)) { // Handle LHS and RHS.
Evan Chengfb2e7522009-09-18 21:02:19 +00001204 // If new BB's are created during scheduling, the edges may have been
Evan Chengce319102009-09-19 09:51:03 +00001205 // updated. That is, the edge from ThisBB to BB may have been split and
1206 // BB's predecessor is now another block.
Evan Chengfb2e7522009-09-18 21:02:19 +00001207 DenseMap<MachineBasicBlock*, MachineBasicBlock*>::iterator EI =
Dan Gohman2048b852009-11-23 18:04:58 +00001208 SDB->EdgeMapping.find(BB);
1209 if (EI != SDB->EdgeMapping.end())
Evan Chengfb2e7522009-09-18 21:02:19 +00001210 ThisBB = EI->second;
Jakob Stoklund Olesendd437ba2010-01-11 21:02:33 +00001211
1212 // BB may have been removed from the CFG if a branch was constant folded.
1213 if (ThisBB->isSuccessor(BB)) {
1214 for (MachineBasicBlock::iterator Phi = BB->begin();
Chris Lattner518bb532010-02-09 19:54:29 +00001215 Phi != BB->end() && Phi->isPHI();
Jakob Stoklund Olesendd437ba2010-01-11 21:02:33 +00001216 ++Phi) {
1217 // This value for this PHI node is recorded in PHINodesToUpdate.
1218 for (unsigned pn = 0; ; ++pn) {
1219 assert(pn != SDB->PHINodesToUpdate.size() &&
1220 "Didn't find PHI entry!");
1221 if (SDB->PHINodesToUpdate[pn].first == Phi) {
1222 Phi->addOperand(MachineOperand::
1223 CreateReg(SDB->PHINodesToUpdate[pn].second,
1224 false));
1225 Phi->addOperand(MachineOperand::CreateMBB(ThisBB));
1226 break;
1227 }
Evan Cheng8be58a12009-09-18 08:26:06 +00001228 }
Chris Lattnerd5e93c02006-09-07 01:59:34 +00001229 }
Nate Begemanf15485a2006-03-27 01:32:24 +00001230 }
Daniel Dunbara279bc32009-09-20 02:20:51 +00001231
Chris Lattnerd5e93c02006-09-07 01:59:34 +00001232 // Don't process RHS if same block as LHS.
Dan Gohman2048b852009-11-23 18:04:58 +00001233 if (BB == SDB->SwitchCases[i].FalseBB)
1234 SDB->SwitchCases[i].FalseBB = 0;
Daniel Dunbara279bc32009-09-20 02:20:51 +00001235
Chris Lattnerd5e93c02006-09-07 01:59:34 +00001236 // If we haven't handled the RHS, do so now. Otherwise, we're done.
Dan Gohman2048b852009-11-23 18:04:58 +00001237 SDB->SwitchCases[i].TrueBB = SDB->SwitchCases[i].FalseBB;
1238 SDB->SwitchCases[i].FalseBB = 0;
Nate Begemanf15485a2006-03-27 01:32:24 +00001239 }
Dan Gohman2048b852009-11-23 18:04:58 +00001240 assert(SDB->SwitchCases[i].TrueBB == 0 && SDB->SwitchCases[i].FalseBB == 0);
1241 SDB->clear();
Chris Lattnera33ef482005-03-30 01:10:47 +00001242 }
Dan Gohman2048b852009-11-23 18:04:58 +00001243 SDB->SwitchCases.clear();
Dan Gohman7c3234c2008-08-27 23:52:12 +00001244
Dan Gohman2048b852009-11-23 18:04:58 +00001245 SDB->PHINodesToUpdate.clear();
Chris Lattner1c08c712005-01-07 07:47:53 +00001246}
Evan Chenga9c20912006-01-21 02:32:06 +00001247
Jim Laskey13ec7022006-08-01 14:21:23 +00001248
Dan Gohman0a3776d2009-02-06 18:26:51 +00001249/// Create the scheduler. If a specific scheduler was specified
1250/// via the SchedulerRegistry, use it, otherwise select the
1251/// one preferred by the target.
Dan Gohman5e843682008-07-14 18:19:29 +00001252///
Dan Gohman47ac0f02009-02-11 04:27:20 +00001253ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
Jim Laskeyeb577ba2006-08-02 12:30:23 +00001254 RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
Daniel Dunbara279bc32009-09-20 02:20:51 +00001255
Jim Laskey13ec7022006-08-01 14:21:23 +00001256 if (!Ctor) {
Jim Laskeyeb577ba2006-08-02 12:30:23 +00001257 Ctor = ISHeuristic;
Jim Laskey9373beb2006-08-01 19:14:14 +00001258 RegisterScheduler::setDefault(Ctor);
Evan Cheng4ef10862006-01-23 07:01:07 +00001259 }
Daniel Dunbara279bc32009-09-20 02:20:51 +00001260
Bill Wendlingbe8cc2a2009-04-29 00:15:41 +00001261 return Ctor(this, OptLevel);
Evan Chenga9c20912006-01-21 02:32:06 +00001262}
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001263
Dan Gohmanfc54c552009-01-15 22:18:12 +00001264ScheduleHazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
1265 return new ScheduleHazardRecognizer();
Jim Laskey9ff542f2006-08-01 18:29:48 +00001266}
1267
Chris Lattner75548062006-10-11 03:58:02 +00001268//===----------------------------------------------------------------------===//
1269// Helper functions used by the generated instruction selector.
1270//===----------------------------------------------------------------------===//
1271// Calls to these methods are generated by tblgen.
1272
1273/// CheckAndMask - The isel is trying to match something like (and X, 255). If
1274/// the dag combiner simplified the 255, we still want to match. RHS is the
1275/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
1276/// specified in the .td file (e.g. 255).
Daniel Dunbara279bc32009-09-20 02:20:51 +00001277bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
Dan Gohmandc9b3d02007-07-24 23:00:27 +00001278 int64_t DesiredMaskS) const {
Dan Gohman2e68b6f2008-02-25 21:11:39 +00001279 const APInt &ActualMask = RHS->getAPIntValue();
1280 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
Daniel Dunbara279bc32009-09-20 02:20:51 +00001281
Chris Lattner75548062006-10-11 03:58:02 +00001282 // If the actual mask exactly matches, success!
1283 if (ActualMask == DesiredMask)
1284 return true;
Daniel Dunbara279bc32009-09-20 02:20:51 +00001285
Chris Lattner75548062006-10-11 03:58:02 +00001286 // If the actual AND mask is allowing unallowed bits, this doesn't match.
Dan Gohman2e68b6f2008-02-25 21:11:39 +00001287 if (ActualMask.intersects(~DesiredMask))
Chris Lattner75548062006-10-11 03:58:02 +00001288 return false;
Daniel Dunbara279bc32009-09-20 02:20:51 +00001289
Chris Lattner75548062006-10-11 03:58:02 +00001290 // Otherwise, the DAG Combiner may have proven that the value coming in is
1291 // either already zero or is not demanded. Check for known zero input bits.
Dan Gohman2e68b6f2008-02-25 21:11:39 +00001292 APInt NeededMask = DesiredMask & ~ActualMask;
Dan Gohmanea859be2007-06-22 14:59:07 +00001293 if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
Chris Lattner75548062006-10-11 03:58:02 +00001294 return true;
Daniel Dunbara279bc32009-09-20 02:20:51 +00001295
Chris Lattner75548062006-10-11 03:58:02 +00001296 // TODO: check to see if missing bits are just not demanded.
1297
1298 // Otherwise, this pattern doesn't match.
1299 return false;
1300}
1301
1302/// CheckOrMask - The isel is trying to match something like (or X, 255). If
1303/// the dag combiner simplified the 255, we still want to match. RHS is the
1304/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
1305/// specified in the .td file (e.g. 255).
Daniel Dunbara279bc32009-09-20 02:20:51 +00001306bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
Dan Gohman2e68b6f2008-02-25 21:11:39 +00001307 int64_t DesiredMaskS) const {
1308 const APInt &ActualMask = RHS->getAPIntValue();
1309 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
Daniel Dunbara279bc32009-09-20 02:20:51 +00001310
Chris Lattner75548062006-10-11 03:58:02 +00001311 // If the actual mask exactly matches, success!
1312 if (ActualMask == DesiredMask)
1313 return true;
Daniel Dunbara279bc32009-09-20 02:20:51 +00001314
Chris Lattner75548062006-10-11 03:58:02 +00001315 // If the actual AND mask is allowing unallowed bits, this doesn't match.
Dan Gohman2e68b6f2008-02-25 21:11:39 +00001316 if (ActualMask.intersects(~DesiredMask))
Chris Lattner75548062006-10-11 03:58:02 +00001317 return false;
Daniel Dunbara279bc32009-09-20 02:20:51 +00001318
Chris Lattner75548062006-10-11 03:58:02 +00001319 // Otherwise, the DAG Combiner may have proven that the value coming in is
1320 // either already zero or is not demanded. Check for known zero input bits.
Dan Gohman2e68b6f2008-02-25 21:11:39 +00001321 APInt NeededMask = DesiredMask & ~ActualMask;
Daniel Dunbara279bc32009-09-20 02:20:51 +00001322
Dan Gohman2e68b6f2008-02-25 21:11:39 +00001323 APInt KnownZero, KnownOne;
Dan Gohmanea859be2007-06-22 14:59:07 +00001324 CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
Daniel Dunbara279bc32009-09-20 02:20:51 +00001325
Chris Lattner75548062006-10-11 03:58:02 +00001326 // If all the missing bits in the or are already known to be set, match!
1327 if ((NeededMask & KnownOne) == NeededMask)
1328 return true;
Daniel Dunbara279bc32009-09-20 02:20:51 +00001329
Chris Lattner75548062006-10-11 03:58:02 +00001330 // TODO: check to see if missing bits are just not demanded.
Daniel Dunbara279bc32009-09-20 02:20:51 +00001331
Chris Lattner75548062006-10-11 03:58:02 +00001332 // Otherwise, this pattern doesn't match.
1333 return false;
1334}
1335
Jim Laskey9ff542f2006-08-01 18:29:48 +00001336
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001337/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
1338/// by tblgen. Others should not call it.
1339void SelectionDAGISel::
Dan Gohmanf350b272008-08-23 02:25:05 +00001340SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) {
Dan Gohman475871a2008-07-27 21:46:04 +00001341 std::vector<SDValue> InOps;
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001342 std::swap(InOps, Ops);
1343
1344 Ops.push_back(InOps[0]); // input chain.
1345 Ops.push_back(InOps[1]); // input asm string.
1346
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001347 unsigned i = 2, e = InOps.size();
Owen Anderson825b72b2009-08-11 20:47:22 +00001348 if (InOps[e-1].getValueType() == MVT::Flag)
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001349 --e; // Don't process a flag operand if it is here.
Daniel Dunbara279bc32009-09-20 02:20:51 +00001350
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001351 while (i != e) {
Dan Gohmanf5aeb1a2008-09-12 16:56:44 +00001352 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
Dale Johannesen86b49f82008-09-24 01:07:17 +00001353 if ((Flags & 7) != 4 /*MEM*/) {
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001354 // Just skip over this operand, copying the operands verbatim.
Evan Cheng697cbbf2009-03-20 18:03:34 +00001355 Ops.insert(Ops.end(), InOps.begin()+i,
1356 InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1);
1357 i += InlineAsm::getNumOperandRegisters(Flags) + 1;
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001358 } else {
Evan Cheng697cbbf2009-03-20 18:03:34 +00001359 assert(InlineAsm::getNumOperandRegisters(Flags) == 1 &&
1360 "Memory operand with multiple values?");
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001361 // Otherwise, this is a memory operand. Ask the target to select it.
Dan Gohman475871a2008-07-27 21:46:04 +00001362 std::vector<SDValue> SelOps;
Dan Gohmanf350b272008-08-23 02:25:05 +00001363 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) {
Torok Edwin7d696d82009-07-11 13:10:19 +00001364 llvm_report_error("Could not match memory address. Inline asm"
1365 " failure!");
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001366 }
Daniel Dunbara279bc32009-09-20 02:20:51 +00001367
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001368 // Add this to the output node.
Dale Johannesen86b49f82008-09-24 01:07:17 +00001369 Ops.push_back(CurDAG->getTargetConstant(4/*MEM*/ | (SelOps.size()<< 3),
Dale Johannesen99499332009-12-23 07:32:51 +00001370 MVT::i32));
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001371 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
1372 i += 2;
1373 }
1374 }
Daniel Dunbara279bc32009-09-20 02:20:51 +00001375
Chris Lattner0e43f2b2006-02-24 02:13:54 +00001376 // Add the flag input back if present.
1377 if (e != InOps.size())
1378 Ops.push_back(InOps.back());
1379}
Devang Patel794fd752007-05-01 21:15:47 +00001380
Owen Andersone50ed302009-08-10 22:56:29 +00001381/// findFlagUse - Return use of EVT::Flag value produced by the specified
Anton Korobeynikovc1c6ef82009-05-08 18:51:58 +00001382/// SDNode.
1383///
1384static SDNode *findFlagUse(SDNode *N) {
1385 unsigned FlagResNo = N->getNumValues()-1;
1386 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
1387 SDUse &Use = I.getUse();
1388 if (Use.getResNo() == FlagResNo)
1389 return Use.getUser();
1390 }
1391 return NULL;
1392}
1393
1394/// findNonImmUse - Return true if "Use" is a non-immediate use of "Def".
1395/// This function recursively traverses up the operand chain, ignoring
1396/// certain nodes.
1397static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
Chris Lattnerd1b73822010-03-02 22:20:06 +00001398 SDNode *Root, SmallPtrSet<SDNode*, 16> &Visited,
1399 bool IgnoreChains) {
Chris Lattnerda244a02010-02-23 19:32:27 +00001400 // The NodeID's are given uniques ID's where a node ID is guaranteed to be
1401 // greater than all of its (recursive) operands. If we scan to a point where
1402 // 'use' is smaller than the node we're scanning for, then we know we will
1403 // never find it.
1404 //
1405 // The Use may be -1 (unassigned) if it is a newly allocated node. This can
1406 // happen because we scan down to newly selected nodes in the case of flag
1407 // uses.
1408 if ((Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1))
1409 return false;
1410
1411 // Don't revisit nodes if we already scanned it and didn't fail, we know we
1412 // won't fail if we scan it again.
1413 if (!Visited.insert(Use))
Anton Korobeynikovc1c6ef82009-05-08 18:51:58 +00001414 return false;
1415
1416 for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {
Chris Lattnerd1b73822010-03-02 22:20:06 +00001417 // Ignore chain uses, they are validated by HandleMergeInputChains.
1418 if (Use->getOperand(i).getValueType() == MVT::Other && IgnoreChains)
1419 continue;
1420
Anton Korobeynikovc1c6ef82009-05-08 18:51:58 +00001421 SDNode *N = Use->getOperand(i).getNode();
1422 if (N == Def) {
1423 if (Use == ImmedUse || Use == Root)
1424 continue; // We are not looking for immediate use.
1425 assert(N != Root);
1426 return true;
1427 }
1428
1429 // Traverse up the operand chain.
Chris Lattnerd1b73822010-03-02 22:20:06 +00001430 if (findNonImmUse(N, Def, ImmedUse, Root, Visited, IgnoreChains))
Anton Korobeynikovc1c6ef82009-05-08 18:51:58 +00001431 return true;
1432 }
1433 return false;
1434}
1435
Evan Cheng014bf212010-02-15 19:41:07 +00001436/// IsProfitableToFold - Returns true if it's profitable to fold the specific
1437/// operand node N of U during instruction selection that starts at Root.
1438bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
1439 SDNode *Root) const {
1440 if (OptLevel == CodeGenOpt::None) return false;
1441 return N.hasOneUse();
1442}
1443
1444/// IsLegalToFold - Returns true if the specific operand node N of
1445/// U can be folded during instruction selection that starts at Root.
Chris Lattnerd1b73822010-03-02 22:20:06 +00001446bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
1447 bool IgnoreChains) const {
Anton Korobeynikovc1c6ef82009-05-08 18:51:58 +00001448 if (OptLevel == CodeGenOpt::None) return false;
1449
1450 // If Root use can somehow reach N through a path that that doesn't contain
1451 // U then folding N would create a cycle. e.g. In the following
1452 // diagram, Root can reach N through X. If N is folded into into Root, then
1453 // X is both a predecessor and a successor of U.
1454 //
1455 // [N*] //
1456 // ^ ^ //
1457 // / \ //
1458 // [U*] [X]? //
1459 // ^ ^ //
1460 // \ / //
1461 // \ / //
1462 // [Root*] //
1463 //
1464 // * indicates nodes to be folded together.
1465 //
1466 // If Root produces a flag, then it gets (even more) interesting. Since it
1467 // will be "glued" together with its flag use in the scheduler, we need to
1468 // check if it might reach N.
1469 //
1470 // [N*] //
1471 // ^ ^ //
1472 // / \ //
1473 // [U*] [X]? //
1474 // ^ ^ //
1475 // \ \ //
1476 // \ | //
1477 // [Root*] | //
1478 // ^ | //
1479 // f | //
1480 // | / //
1481 // [Y] / //
1482 // ^ / //
1483 // f / //
1484 // | / //
1485 // [FU] //
1486 //
1487 // If FU (flag use) indirectly reaches N (the load), and Root folds N
1488 // (call it Fold), then X is a predecessor of FU and a successor of
1489 // Fold. But since Fold and FU are flagged together, this will create
1490 // a cycle in the scheduling graph.
1491
Chris Lattner9bbcd5e2010-03-05 05:49:45 +00001492 // If the node has flags, walk down the graph to the "lowest" node in the
1493 // flagged set.
Owen Andersone50ed302009-08-10 22:56:29 +00001494 EVT VT = Root->getValueType(Root->getNumValues()-1);
Owen Anderson825b72b2009-08-11 20:47:22 +00001495 while (VT == MVT::Flag) {
Anton Korobeynikovc1c6ef82009-05-08 18:51:58 +00001496 SDNode *FU = findFlagUse(Root);
1497 if (FU == NULL)
1498 break;
1499 Root = FU;
1500 VT = Root->getValueType(Root->getNumValues()-1);
Chris Lattner18fdaba2010-03-05 06:19:13 +00001501
1502 // If our query node has a flag result with a use, we've walked up it. If
1503 // the user (which has already been selected) has a chain or indirectly uses
1504 // the chain, our WalkChainUsers predicate will not consider it. Because of
1505 // this, we cannot ignore chains in this predicate.
1506 IgnoreChains = false;
Anton Korobeynikovc1c6ef82009-05-08 18:51:58 +00001507 }
Chris Lattner18fdaba2010-03-05 06:19:13 +00001508
Anton Korobeynikovc1c6ef82009-05-08 18:51:58 +00001509
Chris Lattner9bbcd5e2010-03-05 05:49:45 +00001510 SmallPtrSet<SDNode*, 16> Visited;
1511 return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains);
Anton Korobeynikovc1c6ef82009-05-08 18:51:58 +00001512}
1513
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001514SDNode *SelectionDAGISel::Select_INLINEASM(SDNode *N) {
1515 std::vector<SDValue> Ops(N->op_begin(), N->op_end());
Dan Gohmane1f188f2009-10-29 22:30:23 +00001516 SelectInlineAsmMemoryOperands(Ops);
1517
1518 std::vector<EVT> VTs;
1519 VTs.push_back(MVT::Other);
1520 VTs.push_back(MVT::Flag);
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001521 SDValue New = CurDAG->getNode(ISD::INLINEASM, N->getDebugLoc(),
Dan Gohmane1f188f2009-10-29 22:30:23 +00001522 VTs, &Ops[0], Ops.size());
Chris Lattnerd1b73822010-03-02 22:20:06 +00001523 New->setNodeId(-1);
Dan Gohmane1f188f2009-10-29 22:30:23 +00001524 return New.getNode();
1525}
1526
Dan Gohmaneeb3a002010-01-05 01:24:18 +00001527SDNode *SelectionDAGISel::Select_UNDEF(SDNode *N) {
Chris Lattner518bb532010-02-09 19:54:29 +00001528 return CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF,N->getValueType(0));
Dan Gohmane1f188f2009-10-29 22:30:23 +00001529}
1530
Chris Lattner2a49d572010-02-28 22:37:22 +00001531/// GetVBR - decode a vbr encoding whose top bit is set.
1532ALWAYS_INLINE static uint64_t
1533GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
1534 assert(Val >= 128 && "Not a VBR");
1535 Val &= 127; // Remove first vbr bit.
1536
1537 unsigned Shift = 7;
1538 uint64_t NextBits;
1539 do {
Chris Lattner14df8dc2010-02-28 22:38:43 +00001540 NextBits = MatcherTable[Idx++];
Chris Lattner2a49d572010-02-28 22:37:22 +00001541 Val |= (NextBits&127) << Shift;
1542 Shift += 7;
1543 } while (NextBits & 128);
1544
1545 return Val;
1546}
1547
Chris Lattner2a49d572010-02-28 22:37:22 +00001548
1549/// UpdateChainsAndFlags - When a match is complete, this method updates uses of
1550/// interior flag and chain results to use the new flag and chain results.
Chris Lattner82dd3d32010-03-02 07:50:03 +00001551void SelectionDAGISel::
1552UpdateChainsAndFlags(SDNode *NodeToMatch, SDValue InputChain,
1553 const SmallVectorImpl<SDNode*> &ChainNodesMatched,
1554 SDValue InputFlag,
1555 const SmallVectorImpl<SDNode*> &FlagResultNodesMatched,
1556 bool isMorphNodeTo) {
1557 SmallVector<SDNode*, 4> NowDeadNodes;
1558
1559 ISelUpdater ISU(ISelPosition);
1560
Chris Lattner2a49d572010-02-28 22:37:22 +00001561 // Now that all the normal results are replaced, we replace the chain and
1562 // flag results if present.
1563 if (!ChainNodesMatched.empty()) {
1564 assert(InputChain.getNode() != 0 &&
1565 "Matched input chains but didn't produce a chain");
1566 // Loop over all of the nodes we matched that produced a chain result.
1567 // Replace all the chain results with the final chain we ended up with.
1568 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
1569 SDNode *ChainNode = ChainNodesMatched[i];
1570
Chris Lattner82dd3d32010-03-02 07:50:03 +00001571 // If this node was already deleted, don't look at it.
1572 if (ChainNode->getOpcode() == ISD::DELETED_NODE)
1573 continue;
1574
Chris Lattner2a49d572010-02-28 22:37:22 +00001575 // Don't replace the results of the root node if we're doing a
1576 // MorphNodeTo.
1577 if (ChainNode == NodeToMatch && isMorphNodeTo)
1578 continue;
1579
1580 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
1581 if (ChainVal.getValueType() == MVT::Flag)
1582 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
1583 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
Chris Lattner82dd3d32010-03-02 07:50:03 +00001584 CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain, &ISU);
1585
Chris Lattner856fb392010-03-28 05:28:31 +00001586 // If the node became dead and we haven't already seen it, delete it.
1587 if (ChainNode->use_empty() &&
1588 !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), ChainNode))
Chris Lattner82dd3d32010-03-02 07:50:03 +00001589 NowDeadNodes.push_back(ChainNode);
Chris Lattner2a49d572010-02-28 22:37:22 +00001590 }
1591 }
1592
1593 // If the result produces a flag, update any flag results in the matched
1594 // pattern with the flag result.
1595 if (InputFlag.getNode() != 0) {
1596 // Handle any interior nodes explicitly marked.
1597 for (unsigned i = 0, e = FlagResultNodesMatched.size(); i != e; ++i) {
1598 SDNode *FRN = FlagResultNodesMatched[i];
Chris Lattner82dd3d32010-03-02 07:50:03 +00001599
1600 // If this node was already deleted, don't look at it.
1601 if (FRN->getOpcode() == ISD::DELETED_NODE)
1602 continue;
1603
Chris Lattner2a49d572010-02-28 22:37:22 +00001604 assert(FRN->getValueType(FRN->getNumValues()-1) == MVT::Flag &&
1605 "Doesn't have a flag result");
1606 CurDAG->ReplaceAllUsesOfValueWith(SDValue(FRN, FRN->getNumValues()-1),
Chris Lattner82dd3d32010-03-02 07:50:03 +00001607 InputFlag, &ISU);
1608
Chris Lattner19e37cb2010-03-28 04:54:33 +00001609 // If the node became dead and we haven't already seen it, delete it.
1610 if (FRN->use_empty() &&
1611 !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), FRN))
Chris Lattner82dd3d32010-03-02 07:50:03 +00001612 NowDeadNodes.push_back(FRN);
Chris Lattner2a49d572010-02-28 22:37:22 +00001613 }
1614 }
1615
Chris Lattner82dd3d32010-03-02 07:50:03 +00001616 if (!NowDeadNodes.empty())
1617 CurDAG->RemoveDeadNodes(NowDeadNodes, &ISU);
1618
Chris Lattner2a49d572010-02-28 22:37:22 +00001619 DEBUG(errs() << "ISEL: Match complete!\n");
1620}
1621
Chris Lattnerc6d7ad32010-03-02 02:22:10 +00001622enum ChainResult {
1623 CR_Simple,
1624 CR_InducesCycle,
1625 CR_LeadsToInteriorNode
1626};
1627
1628/// WalkChainUsers - Walk down the users of the specified chained node that is
1629/// part of the pattern we're matching, looking at all of the users we find.
1630/// This determines whether something is an interior node, whether we have a
1631/// non-pattern node in between two pattern nodes (which prevent folding because
1632/// it would induce a cycle) and whether we have a TokenFactor node sandwiched
1633/// between pattern nodes (in which case the TF becomes part of the pattern).
1634///
1635/// The walk we do here is guaranteed to be small because we quickly get down to
1636/// already selected nodes "below" us.
1637static ChainResult
1638WalkChainUsers(SDNode *ChainedNode,
1639 SmallVectorImpl<SDNode*> &ChainedNodesInPattern,
1640 SmallVectorImpl<SDNode*> &InteriorChainedNodes) {
1641 ChainResult Result = CR_Simple;
1642
1643 for (SDNode::use_iterator UI = ChainedNode->use_begin(),
1644 E = ChainedNode->use_end(); UI != E; ++UI) {
1645 // Make sure the use is of the chain, not some other value we produce.
1646 if (UI.getUse().getValueType() != MVT::Other) continue;
1647
1648 SDNode *User = *UI;
1649
1650 // If we see an already-selected machine node, then we've gone beyond the
1651 // pattern that we're selecting down into the already selected chunk of the
1652 // DAG.
1653 if (User->isMachineOpcode() ||
Chris Lattnerc6d7ad32010-03-02 02:22:10 +00001654 User->getOpcode() == ISD::HANDLENODE) // Root of the graph.
1655 continue;
Chris Lattnerd1b73822010-03-02 22:20:06 +00001656
1657 if (User->getOpcode() == ISD::CopyToReg ||
1658 User->getOpcode() == ISD::CopyFromReg ||
Chris Lattner7561d482010-03-14 02:33:54 +00001659 User->getOpcode() == ISD::INLINEASM ||
1660 User->getOpcode() == ISD::EH_LABEL) {
Chris Lattnerd1b73822010-03-02 22:20:06 +00001661 // If their node ID got reset to -1 then they've already been selected.
1662 // Treat them like a MachineOpcode.
1663 if (User->getNodeId() == -1)
1664 continue;
1665 }
Chris Lattnerc6d7ad32010-03-02 02:22:10 +00001666
1667 // If we have a TokenFactor, we handle it specially.
1668 if (User->getOpcode() != ISD::TokenFactor) {
1669 // If the node isn't a token factor and isn't part of our pattern, then it
1670 // must be a random chained node in between two nodes we're selecting.
1671 // This happens when we have something like:
1672 // x = load ptr
1673 // call
1674 // y = x+4
1675 // store y -> ptr
1676 // Because we structurally match the load/store as a read/modify/write,
1677 // but the call is chained between them. We cannot fold in this case
1678 // because it would induce a cycle in the graph.
1679 if (!std::count(ChainedNodesInPattern.begin(),
1680 ChainedNodesInPattern.end(), User))
1681 return CR_InducesCycle;
1682
1683 // Otherwise we found a node that is part of our pattern. For example in:
1684 // x = load ptr
1685 // y = x+4
1686 // store y -> ptr
1687 // This would happen when we're scanning down from the load and see the
1688 // store as a user. Record that there is a use of ChainedNode that is
1689 // part of the pattern and keep scanning uses.
1690 Result = CR_LeadsToInteriorNode;
1691 InteriorChainedNodes.push_back(User);
1692 continue;
1693 }
1694
1695 // If we found a TokenFactor, there are two cases to consider: first if the
1696 // TokenFactor is just hanging "below" the pattern we're matching (i.e. no
1697 // uses of the TF are in our pattern) we just want to ignore it. Second,
1698 // the TokenFactor can be sandwiched in between two chained nodes, like so:
1699 // [Load chain]
1700 // ^
1701 // |
1702 // [Load]
1703 // ^ ^
1704 // | \ DAG's like cheese
1705 // / \ do you?
1706 // / |
1707 // [TokenFactor] [Op]
1708 // ^ ^
1709 // | |
1710 // \ /
1711 // \ /
1712 // [Store]
1713 //
1714 // In this case, the TokenFactor becomes part of our match and we rewrite it
1715 // as a new TokenFactor.
1716 //
1717 // To distinguish these two cases, do a recursive walk down the uses.
1718 switch (WalkChainUsers(User, ChainedNodesInPattern, InteriorChainedNodes)) {
1719 case CR_Simple:
1720 // If the uses of the TokenFactor are just already-selected nodes, ignore
1721 // it, it is "below" our pattern.
1722 continue;
1723 case CR_InducesCycle:
1724 // If the uses of the TokenFactor lead to nodes that are not part of our
1725 // pattern that are not selected, folding would turn this into a cycle,
1726 // bail out now.
1727 return CR_InducesCycle;
1728 case CR_LeadsToInteriorNode:
1729 break; // Otherwise, keep processing.
1730 }
1731
1732 // Okay, we know we're in the interesting interior case. The TokenFactor
1733 // is now going to be considered part of the pattern so that we rewrite its
1734 // uses (it may have uses that are not part of the pattern) with the
1735 // ultimate chain result of the generated code. We will also add its chain
1736 // inputs as inputs to the ultimate TokenFactor we create.
1737 Result = CR_LeadsToInteriorNode;
1738 ChainedNodesInPattern.push_back(User);
1739 InteriorChainedNodes.push_back(User);
1740 continue;
1741 }
1742
1743 return Result;
1744}
1745
Chris Lattner6b307922010-03-02 00:00:03 +00001746/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
Chris Lattner00592ec2010-03-02 19:34:59 +00001747/// operation for when the pattern matched at least one node with a chains. The
Chris Lattnerc6d7ad32010-03-02 02:22:10 +00001748/// input vector contains a list of all of the chained nodes that we match. We
1749/// must determine if this is a valid thing to cover (i.e. matching it won't
1750/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
1751/// be used as the input node chain for the generated nodes.
Chris Lattner6b307922010-03-02 00:00:03 +00001752static SDValue
Chris Lattnerc6d7ad32010-03-02 02:22:10 +00001753HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
Chris Lattner6b307922010-03-02 00:00:03 +00001754 SelectionDAG *CurDAG) {
Chris Lattnerc6d7ad32010-03-02 02:22:10 +00001755 // Walk all of the chained nodes we've matched, recursively scanning down the
1756 // users of the chain result. This adds any TokenFactor nodes that are caught
1757 // in between chained nodes to the chained and interior nodes list.
1758 SmallVector<SDNode*, 3> InteriorChainedNodes;
1759 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
1760 if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched,
1761 InteriorChainedNodes) == CR_InducesCycle)
1762 return SDValue(); // Would induce a cycle.
1763 }
Chris Lattner6b307922010-03-02 00:00:03 +00001764
Chris Lattnerc6d7ad32010-03-02 02:22:10 +00001765 // Okay, we have walked all the matched nodes and collected TokenFactor nodes
1766 // that we are interested in. Form our input TokenFactor node.
Chris Lattner6b307922010-03-02 00:00:03 +00001767 SmallVector<SDValue, 3> InputChains;
1768 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
Chris Lattnerc6d7ad32010-03-02 02:22:10 +00001769 // Add the input chain of this node to the InputChains list (which will be
1770 // the operands of the generated TokenFactor) if it's not an interior node.
1771 SDNode *N = ChainNodesMatched[i];
1772 if (N->getOpcode() != ISD::TokenFactor) {
1773 if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N))
1774 continue;
1775
1776 // Otherwise, add the input chain.
1777 SDValue InChain = ChainNodesMatched[i]->getOperand(0);
1778 assert(InChain.getValueType() == MVT::Other && "Not a chain");
Chris Lattner6b307922010-03-02 00:00:03 +00001779 InputChains.push_back(InChain);
Chris Lattnerc6d7ad32010-03-02 02:22:10 +00001780 continue;
1781 }
1782
1783 // If we have a token factor, we want to add all inputs of the token factor
1784 // that are not part of the pattern we're matching.
1785 for (unsigned op = 0, e = N->getNumOperands(); op != e; ++op) {
1786 if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
Chris Lattner6183fbd2010-03-02 02:37:23 +00001787 N->getOperand(op).getNode()))
1788 InputChains.push_back(N->getOperand(op));
Chris Lattnerc6d7ad32010-03-02 02:22:10 +00001789 }
Chris Lattner6b307922010-03-02 00:00:03 +00001790 }
1791
1792 SDValue Res;
1793 if (InputChains.size() == 1)
1794 return InputChains[0];
1795 return CurDAG->getNode(ISD::TokenFactor, ChainNodesMatched[0]->getDebugLoc(),
1796 MVT::Other, &InputChains[0], InputChains.size());
1797}
Chris Lattner2a49d572010-02-28 22:37:22 +00001798
Chris Lattner3ff1e4d2010-03-02 06:55:04 +00001799/// MorphNode - Handle morphing a node in place for the selector.
1800SDNode *SelectionDAGISel::
1801MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
1802 const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo) {
1803 // It is possible we're using MorphNodeTo to replace a node with no
1804 // normal results with one that has a normal result (or we could be
1805 // adding a chain) and the input could have flags and chains as well.
Chris Lattnercaa88702010-03-28 08:43:23 +00001806 // In this case we need to shift the operands down.
Chris Lattner3ff1e4d2010-03-02 06:55:04 +00001807 // FIXME: This is a horrible hack and broken in obscure cases, no worse
Chris Lattnera6f86932010-03-27 18:54:50 +00001808 // than the old isel though.
Chris Lattner3ff1e4d2010-03-02 06:55:04 +00001809 int OldFlagResultNo = -1, OldChainResultNo = -1;
1810
1811 unsigned NTMNumResults = Node->getNumValues();
1812 if (Node->getValueType(NTMNumResults-1) == MVT::Flag) {
1813 OldFlagResultNo = NTMNumResults-1;
1814 if (NTMNumResults != 1 &&
1815 Node->getValueType(NTMNumResults-2) == MVT::Other)
1816 OldChainResultNo = NTMNumResults-2;
1817 } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
1818 OldChainResultNo = NTMNumResults-1;
1819
Chris Lattner61c97f62010-03-02 07:14:49 +00001820 // Call the underlying SelectionDAG routine to do the transmogrification. Note
1821 // that this deletes operands of the old node that become dead.
Chris Lattner3ff1e4d2010-03-02 06:55:04 +00001822 SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops, NumOps);
1823
1824 // MorphNodeTo can operate in two ways: if an existing node with the
1825 // specified operands exists, it can just return it. Otherwise, it
1826 // updates the node in place to have the requested operands.
1827 if (Res == Node) {
1828 // If we updated the node in place, reset the node ID. To the isel,
1829 // this should be just like a newly allocated machine node.
1830 Res->setNodeId(-1);
1831 }
1832
1833 unsigned ResNumResults = Res->getNumValues();
1834 // Move the flag if needed.
1835 if ((EmitNodeInfo & OPFL_FlagOutput) && OldFlagResultNo != -1 &&
1836 (unsigned)OldFlagResultNo != ResNumResults-1)
1837 CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldFlagResultNo),
1838 SDValue(Res, ResNumResults-1));
1839
1840 if ((EmitNodeInfo & OPFL_FlagOutput) != 0)
1841 --ResNumResults;
1842
1843 // Move the chain reference if needed.
1844 if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
1845 (unsigned)OldChainResultNo != ResNumResults-1)
1846 CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo),
1847 SDValue(Res, ResNumResults-1));
1848
1849 // Otherwise, no replacement happened because the node already exists. Replace
1850 // Uses of the old node with the new one.
1851 if (Res != Node)
1852 CurDAG->ReplaceAllUsesWith(Node, Res);
1853
1854 return Res;
1855}
1856
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00001857/// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
1858ALWAYS_INLINE static bool
Chris Lattnerda828e32010-03-03 07:46:25 +00001859CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1860 SDValue N, const SmallVectorImpl<SDValue> &RecordedNodes) {
1861 // Accept if it is exactly the same as a previously recorded node.
1862 unsigned RecNo = MatcherTable[MatcherIndex++];
1863 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
1864 return N == RecordedNodes[RecNo];
1865}
1866
1867/// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
1868ALWAYS_INLINE static bool
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00001869CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1870 SelectionDAGISel &SDISel) {
1871 return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]);
1872}
1873
1874/// CheckNodePredicate - Implements OP_CheckNodePredicate.
1875ALWAYS_INLINE static bool
1876CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1877 SelectionDAGISel &SDISel, SDNode *N) {
1878 return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]);
1879}
1880
1881ALWAYS_INLINE static bool
1882CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1883 SDNode *N) {
Chris Lattnerd5d5a3d2010-03-25 06:33:05 +00001884 uint16_t Opc = MatcherTable[MatcherIndex++];
1885 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
1886 return N->getOpcode() == Opc;
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00001887}
1888
1889ALWAYS_INLINE static bool
1890CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1891 SDValue N, const TargetLowering &TLI) {
1892 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
1893 if (N.getValueType() == VT) return true;
1894
1895 // Handle the case when VT is iPTR.
1896 return VT == MVT::iPTR && N.getValueType() == TLI.getPointerTy();
1897}
1898
1899ALWAYS_INLINE static bool
Chris Lattnerda828e32010-03-03 07:46:25 +00001900CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1901 SDValue N, const TargetLowering &TLI,
1902 unsigned ChildNo) {
1903 if (ChildNo >= N.getNumOperands())
1904 return false; // Match fails if out of range child #.
1905 return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI);
1906}
1907
1908
1909ALWAYS_INLINE static bool
1910CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1911 SDValue N) {
1912 return cast<CondCodeSDNode>(N)->get() ==
1913 (ISD::CondCode)MatcherTable[MatcherIndex++];
1914}
1915
1916ALWAYS_INLINE static bool
1917CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1918 SDValue N, const TargetLowering &TLI) {
1919 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
1920 if (cast<VTSDNode>(N)->getVT() == VT)
1921 return true;
1922
1923 // Handle the case when VT is iPTR.
1924 return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI.getPointerTy();
1925}
1926
1927ALWAYS_INLINE static bool
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00001928CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1929 SDValue N) {
1930 int64_t Val = MatcherTable[MatcherIndex++];
1931 if (Val & 128)
1932 Val = GetVBR(Val, MatcherTable, MatcherIndex);
1933
1934 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
1935 return C != 0 && C->getSExtValue() == Val;
1936}
1937
Chris Lattnerda828e32010-03-03 07:46:25 +00001938ALWAYS_INLINE static bool
1939CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1940 SDValue N, SelectionDAGISel &SDISel) {
1941 int64_t Val = MatcherTable[MatcherIndex++];
1942 if (Val & 128)
1943 Val = GetVBR(Val, MatcherTable, MatcherIndex);
1944
1945 if (N->getOpcode() != ISD::AND) return false;
1946
1947 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
1948 return C != 0 && SDISel.CheckAndMask(N.getOperand(0), C, Val);
1949}
1950
1951ALWAYS_INLINE static bool
1952CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
1953 SDValue N, SelectionDAGISel &SDISel) {
1954 int64_t Val = MatcherTable[MatcherIndex++];
1955 if (Val & 128)
1956 Val = GetVBR(Val, MatcherTable, MatcherIndex);
1957
1958 if (N->getOpcode() != ISD::OR) return false;
1959
1960 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
1961 return C != 0 && SDISel.CheckOrMask(N.getOperand(0), C, Val);
1962}
1963
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00001964/// IsPredicateKnownToFail - If we know how and can do so without pushing a
1965/// scope, evaluate the current node. If the current predicate is known to
1966/// fail, set Result=true and return anything. If the current predicate is
1967/// known to pass, set Result=false and return the MatcherIndex to continue
1968/// with. If the current predicate is unknown, set Result=false and return the
1969/// MatcherIndex to continue with.
1970static unsigned IsPredicateKnownToFail(const unsigned char *Table,
1971 unsigned Index, SDValue N,
Chris Lattnerda828e32010-03-03 07:46:25 +00001972 bool &Result, SelectionDAGISel &SDISel,
1973 SmallVectorImpl<SDValue> &RecordedNodes){
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00001974 switch (Table[Index++]) {
1975 default:
1976 Result = false;
1977 return Index-1; // Could not evaluate this predicate.
Chris Lattnerda828e32010-03-03 07:46:25 +00001978 case SelectionDAGISel::OPC_CheckSame:
1979 Result = !::CheckSame(Table, Index, N, RecordedNodes);
1980 return Index;
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00001981 case SelectionDAGISel::OPC_CheckPatternPredicate:
Chris Lattnerda828e32010-03-03 07:46:25 +00001982 Result = !::CheckPatternPredicate(Table, Index, SDISel);
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00001983 return Index;
1984 case SelectionDAGISel::OPC_CheckPredicate:
Chris Lattnerda828e32010-03-03 07:46:25 +00001985 Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode());
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00001986 return Index;
1987 case SelectionDAGISel::OPC_CheckOpcode:
1988 Result = !::CheckOpcode(Table, Index, N.getNode());
1989 return Index;
1990 case SelectionDAGISel::OPC_CheckType:
1991 Result = !::CheckType(Table, Index, N, SDISel.TLI);
1992 return Index;
1993 case SelectionDAGISel::OPC_CheckChild0Type:
1994 case SelectionDAGISel::OPC_CheckChild1Type:
1995 case SelectionDAGISel::OPC_CheckChild2Type:
1996 case SelectionDAGISel::OPC_CheckChild3Type:
1997 case SelectionDAGISel::OPC_CheckChild4Type:
1998 case SelectionDAGISel::OPC_CheckChild5Type:
1999 case SelectionDAGISel::OPC_CheckChild6Type:
Chris Lattnerda828e32010-03-03 07:46:25 +00002000 case SelectionDAGISel::OPC_CheckChild7Type:
2001 Result = !::CheckChildType(Table, Index, N, SDISel.TLI,
2002 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Type);
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002003 return Index;
Chris Lattnerda828e32010-03-03 07:46:25 +00002004 case SelectionDAGISel::OPC_CheckCondCode:
2005 Result = !::CheckCondCode(Table, Index, N);
2006 return Index;
2007 case SelectionDAGISel::OPC_CheckValueType:
2008 Result = !::CheckValueType(Table, Index, N, SDISel.TLI);
2009 return Index;
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002010 case SelectionDAGISel::OPC_CheckInteger:
2011 Result = !::CheckInteger(Table, Index, N);
2012 return Index;
Chris Lattnerda828e32010-03-03 07:46:25 +00002013 case SelectionDAGISel::OPC_CheckAndImm:
2014 Result = !::CheckAndImm(Table, Index, N, SDISel);
2015 return Index;
2016 case SelectionDAGISel::OPC_CheckOrImm:
2017 Result = !::CheckOrImm(Table, Index, N, SDISel);
2018 return Index;
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002019 }
2020}
2021
Chris Lattner3ff1e4d2010-03-02 06:55:04 +00002022
Chris Lattner2a49d572010-02-28 22:37:22 +00002023struct MatchScope {
2024 /// FailIndex - If this match fails, this is the index to continue with.
2025 unsigned FailIndex;
2026
2027 /// NodeStack - The node stack when the scope was formed.
2028 SmallVector<SDValue, 4> NodeStack;
2029
2030 /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
2031 unsigned NumRecordedNodes;
2032
2033 /// NumMatchedMemRefs - The number of matched memref entries.
2034 unsigned NumMatchedMemRefs;
2035
2036 /// InputChain/InputFlag - The current chain/flag
2037 SDValue InputChain, InputFlag;
2038
2039 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
2040 bool HasChainNodesMatched, HasFlagResultNodesMatched;
2041};
2042
2043SDNode *SelectionDAGISel::
2044SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
2045 unsigned TableSize) {
2046 // FIXME: Should these even be selected? Handle these cases in the caller?
2047 switch (NodeToMatch->getOpcode()) {
2048 default:
2049 break;
2050 case ISD::EntryToken: // These nodes remain the same.
2051 case ISD::BasicBlock:
2052 case ISD::Register:
Chris Lattner3b9d6212010-03-14 17:53:23 +00002053 //case ISD::VALUETYPE:
2054 //case ISD::CONDCODE:
Chris Lattner2a49d572010-02-28 22:37:22 +00002055 case ISD::HANDLENODE:
2056 case ISD::TargetConstant:
2057 case ISD::TargetConstantFP:
2058 case ISD::TargetConstantPool:
2059 case ISD::TargetFrameIndex:
2060 case ISD::TargetExternalSymbol:
2061 case ISD::TargetBlockAddress:
2062 case ISD::TargetJumpTable:
2063 case ISD::TargetGlobalTLSAddress:
2064 case ISD::TargetGlobalAddress:
2065 case ISD::TokenFactor:
2066 case ISD::CopyFromReg:
2067 case ISD::CopyToReg:
Chris Lattner7561d482010-03-14 02:33:54 +00002068 case ISD::EH_LABEL:
Chris Lattnerd1b73822010-03-02 22:20:06 +00002069 NodeToMatch->setNodeId(-1); // Mark selected.
Chris Lattner2a49d572010-02-28 22:37:22 +00002070 return 0;
2071 case ISD::AssertSext:
2072 case ISD::AssertZext:
2073 CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0),
2074 NodeToMatch->getOperand(0));
2075 return 0;
2076 case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch);
Chris Lattner2a49d572010-02-28 22:37:22 +00002077 case ISD::UNDEF: return Select_UNDEF(NodeToMatch);
2078 }
2079
2080 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
2081
2082 // Set up the node stack with NodeToMatch as the only node on the stack.
2083 SmallVector<SDValue, 8> NodeStack;
2084 SDValue N = SDValue(NodeToMatch, 0);
2085 NodeStack.push_back(N);
2086
2087 // MatchScopes - Scopes used when matching, if a match failure happens, this
2088 // indicates where to continue checking.
2089 SmallVector<MatchScope, 8> MatchScopes;
2090
2091 // RecordedNodes - This is the set of nodes that have been recorded by the
2092 // state machine.
2093 SmallVector<SDValue, 8> RecordedNodes;
2094
2095 // MatchedMemRefs - This is the set of MemRef's we've seen in the input
2096 // pattern.
2097 SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
2098
2099 // These are the current input chain and flag for use when generating nodes.
2100 // Various Emit operations change these. For example, emitting a copytoreg
2101 // uses and updates these.
2102 SDValue InputChain, InputFlag;
2103
2104 // ChainNodesMatched - If a pattern matches nodes that have input/output
2105 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
2106 // which ones they are. The result is captured into this list so that we can
2107 // update the chain results when the pattern is complete.
2108 SmallVector<SDNode*, 3> ChainNodesMatched;
2109 SmallVector<SDNode*, 3> FlagResultNodesMatched;
2110
2111 DEBUG(errs() << "ISEL: Starting pattern match on root node: ";
2112 NodeToMatch->dump(CurDAG);
2113 errs() << '\n');
2114
Chris Lattner7390eeb2010-03-01 18:47:11 +00002115 // Determine where to start the interpreter. Normally we start at opcode #0,
2116 // but if the state machine starts with an OPC_SwitchOpcode, then we
2117 // accelerate the first lookup (which is guaranteed to be hot) with the
2118 // OpcodeOffset table.
Chris Lattner2a49d572010-02-28 22:37:22 +00002119 unsigned MatcherIndex = 0;
Chris Lattner7390eeb2010-03-01 18:47:11 +00002120
2121 if (!OpcodeOffset.empty()) {
2122 // Already computed the OpcodeOffset table, just index into it.
2123 if (N.getOpcode() < OpcodeOffset.size())
2124 MatcherIndex = OpcodeOffset[N.getOpcode()];
2125 DEBUG(errs() << " Initial Opcode index to " << MatcherIndex << "\n");
2126
2127 } else if (MatcherTable[0] == OPC_SwitchOpcode) {
2128 // Otherwise, the table isn't computed, but the state machine does start
2129 // with an OPC_SwitchOpcode instruction. Populate the table now, since this
2130 // is the first time we're selecting an instruction.
2131 unsigned Idx = 1;
2132 while (1) {
2133 // Get the size of this case.
2134 unsigned CaseSize = MatcherTable[Idx++];
2135 if (CaseSize & 128)
2136 CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
2137 if (CaseSize == 0) break;
2138
2139 // Get the opcode, add the index to the table.
Chris Lattnerd5d5a3d2010-03-25 06:33:05 +00002140 uint16_t Opc = MatcherTable[Idx++];
2141 Opc |= (unsigned short)MatcherTable[Idx++] << 8;
Chris Lattner7390eeb2010-03-01 18:47:11 +00002142 if (Opc >= OpcodeOffset.size())
2143 OpcodeOffset.resize((Opc+1)*2);
2144 OpcodeOffset[Opc] = Idx;
2145 Idx += CaseSize;
2146 }
2147
2148 // Okay, do the lookup for the first opcode.
2149 if (N.getOpcode() < OpcodeOffset.size())
2150 MatcherIndex = OpcodeOffset[N.getOpcode()];
2151 }
2152
Chris Lattner2a49d572010-02-28 22:37:22 +00002153 while (1) {
2154 assert(MatcherIndex < TableSize && "Invalid index");
Dan Gohman19b38262010-03-09 02:15:05 +00002155#ifndef NDEBUG
2156 unsigned CurrentOpcodeIndex = MatcherIndex;
2157#endif
Chris Lattner2a49d572010-02-28 22:37:22 +00002158 BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
2159 switch (Opcode) {
2160 case OPC_Scope: {
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002161 // Okay, the semantics of this operation are that we should push a scope
2162 // then evaluate the first child. However, pushing a scope only to have
2163 // the first check fail (which then pops it) is inefficient. If we can
2164 // determine immediately that the first check (or first several) will
2165 // immediately fail, don't even bother pushing a scope for them.
2166 unsigned FailIndex;
2167
2168 while (1) {
2169 unsigned NumToSkip = MatcherTable[MatcherIndex++];
2170 if (NumToSkip & 128)
2171 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
2172 // Found the end of the scope with no match.
2173 if (NumToSkip == 0) {
2174 FailIndex = 0;
2175 break;
2176 }
2177
2178 FailIndex = MatcherIndex+NumToSkip;
2179
Chris Lattnera6f86932010-03-27 18:54:50 +00002180 unsigned MatcherIndexOfPredicate = MatcherIndex;
2181 (void)MatcherIndexOfPredicate; // silence warning.
2182
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002183 // If we can't evaluate this predicate without pushing a scope (e.g. if
2184 // it is a 'MoveParent') or if the predicate succeeds on this node, we
2185 // push the scope and evaluate the full predicate chain.
2186 bool Result;
2187 MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
Chris Lattnerda828e32010-03-03 07:46:25 +00002188 Result, *this, RecordedNodes);
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002189 if (!Result)
2190 break;
2191
Chris Lattnera6f86932010-03-27 18:54:50 +00002192 DEBUG(errs() << " Skipped scope entry (due to false predicate) at "
2193 << "index " << MatcherIndexOfPredicate
2194 << ", continuing at " << FailIndex << "\n");
Chris Lattnerbed993d2010-03-28 19:46:56 +00002195 ++NumDAGIselRetries;
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002196
2197 // Otherwise, we know that this case of the Scope is guaranteed to fail,
2198 // move to the next case.
2199 MatcherIndex = FailIndex;
2200 }
2201
2202 // If the whole scope failed to match, bail.
2203 if (FailIndex == 0) break;
2204
Chris Lattner2a49d572010-02-28 22:37:22 +00002205 // Push a MatchScope which indicates where to go if the first child fails
2206 // to match.
2207 MatchScope NewEntry;
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002208 NewEntry.FailIndex = FailIndex;
Chris Lattner2a49d572010-02-28 22:37:22 +00002209 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
2210 NewEntry.NumRecordedNodes = RecordedNodes.size();
2211 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
2212 NewEntry.InputChain = InputChain;
2213 NewEntry.InputFlag = InputFlag;
2214 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
2215 NewEntry.HasFlagResultNodesMatched = !FlagResultNodesMatched.empty();
2216 MatchScopes.push_back(NewEntry);
2217 continue;
2218 }
2219 case OPC_RecordNode:
2220 // Remember this node, it may end up being an operand in the pattern.
2221 RecordedNodes.push_back(N);
2222 continue;
2223
2224 case OPC_RecordChild0: case OPC_RecordChild1:
2225 case OPC_RecordChild2: case OPC_RecordChild3:
2226 case OPC_RecordChild4: case OPC_RecordChild5:
2227 case OPC_RecordChild6: case OPC_RecordChild7: {
2228 unsigned ChildNo = Opcode-OPC_RecordChild0;
2229 if (ChildNo >= N.getNumOperands())
2230 break; // Match fails if out of range child #.
2231
2232 RecordedNodes.push_back(N->getOperand(ChildNo));
2233 continue;
2234 }
2235 case OPC_RecordMemRef:
2236 MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
2237 continue;
2238
2239 case OPC_CaptureFlagInput:
2240 // If the current node has an input flag, capture it in InputFlag.
2241 if (N->getNumOperands() != 0 &&
2242 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag)
2243 InputFlag = N->getOperand(N->getNumOperands()-1);
2244 continue;
2245
2246 case OPC_MoveChild: {
2247 unsigned ChildNo = MatcherTable[MatcherIndex++];
2248 if (ChildNo >= N.getNumOperands())
2249 break; // Match fails if out of range child #.
2250 N = N.getOperand(ChildNo);
2251 NodeStack.push_back(N);
2252 continue;
2253 }
2254
2255 case OPC_MoveParent:
2256 // Pop the current node off the NodeStack.
2257 NodeStack.pop_back();
2258 assert(!NodeStack.empty() && "Node stack imbalance!");
2259 N = NodeStack.back();
2260 continue;
2261
Chris Lattnerda828e32010-03-03 07:46:25 +00002262 case OPC_CheckSame:
2263 if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002264 continue;
Chris Lattner2a49d572010-02-28 22:37:22 +00002265 case OPC_CheckPatternPredicate:
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002266 if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002267 continue;
2268 case OPC_CheckPredicate:
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002269 if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this,
2270 N.getNode()))
2271 break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002272 continue;
Chris Lattner57bf8a42010-03-04 01:23:08 +00002273 case OPC_CheckComplexPat: {
2274 unsigned CPNum = MatcherTable[MatcherIndex++];
2275 unsigned RecNo = MatcherTable[MatcherIndex++];
2276 assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
2277 if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo], CPNum,
2278 RecordedNodes))
Chris Lattner2a49d572010-02-28 22:37:22 +00002279 break;
2280 continue;
Chris Lattner57bf8a42010-03-04 01:23:08 +00002281 }
Chris Lattner2a49d572010-02-28 22:37:22 +00002282 case OPC_CheckOpcode:
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002283 if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
2284 continue;
2285
2286 case OPC_CheckType:
2287 if (!::CheckType(MatcherTable, MatcherIndex, N, TLI)) break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002288 continue;
2289
Chris Lattnereb669212010-03-01 06:59:22 +00002290 case OPC_SwitchOpcode: {
2291 unsigned CurNodeOpcode = N.getOpcode();
Chris Lattner7d892d62010-03-01 07:43:08 +00002292 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
Chris Lattnereb669212010-03-01 06:59:22 +00002293 unsigned CaseSize;
2294 while (1) {
2295 // Get the size of this case.
2296 CaseSize = MatcherTable[MatcherIndex++];
2297 if (CaseSize & 128)
2298 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
2299 if (CaseSize == 0) break;
2300
Chris Lattnerd5d5a3d2010-03-25 06:33:05 +00002301 uint16_t Opc = MatcherTable[MatcherIndex++];
2302 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
2303
Chris Lattnereb669212010-03-01 06:59:22 +00002304 // If the opcode matches, then we will execute this case.
Chris Lattnerd5d5a3d2010-03-25 06:33:05 +00002305 if (CurNodeOpcode == Opc)
Chris Lattnereb669212010-03-01 06:59:22 +00002306 break;
2307
2308 // Otherwise, skip over this case.
2309 MatcherIndex += CaseSize;
2310 }
2311
Chris Lattnercfe2eab2010-03-03 06:28:15 +00002312 // If no cases matched, bail out.
Chris Lattnereb669212010-03-01 06:59:22 +00002313 if (CaseSize == 0) break;
2314
2315 // Otherwise, execute the case we found.
2316 DEBUG(errs() << " OpcodeSwitch from " << SwitchStart
2317 << " to " << MatcherIndex << "\n");
2318 continue;
2319 }
2320
Chris Lattnercfe2eab2010-03-03 06:28:15 +00002321 case OPC_SwitchType: {
2322 MVT::SimpleValueType CurNodeVT = N.getValueType().getSimpleVT().SimpleTy;
2323 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
2324 unsigned CaseSize;
2325 while (1) {
2326 // Get the size of this case.
2327 CaseSize = MatcherTable[MatcherIndex++];
2328 if (CaseSize & 128)
2329 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
2330 if (CaseSize == 0) break;
2331
2332 MVT::SimpleValueType CaseVT =
2333 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2334 if (CaseVT == MVT::iPTR)
2335 CaseVT = TLI.getPointerTy().SimpleTy;
2336
2337 // If the VT matches, then we will execute this case.
2338 if (CurNodeVT == CaseVT)
2339 break;
2340
2341 // Otherwise, skip over this case.
2342 MatcherIndex += CaseSize;
2343 }
2344
2345 // If no cases matched, bail out.
2346 if (CaseSize == 0) break;
2347
2348 // Otherwise, execute the case we found.
2349 DEBUG(errs() << " TypeSwitch[" << EVT(CurNodeVT).getEVTString()
2350 << "] from " << SwitchStart << " to " << MatcherIndex<<'\n');
2351 continue;
2352 }
Chris Lattner2a49d572010-02-28 22:37:22 +00002353 case OPC_CheckChild0Type: case OPC_CheckChild1Type:
2354 case OPC_CheckChild2Type: case OPC_CheckChild3Type:
2355 case OPC_CheckChild4Type: case OPC_CheckChild5Type:
Chris Lattnerda828e32010-03-03 07:46:25 +00002356 case OPC_CheckChild6Type: case OPC_CheckChild7Type:
2357 if (!::CheckChildType(MatcherTable, MatcherIndex, N, TLI,
2358 Opcode-OPC_CheckChild0Type))
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002359 break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002360 continue;
Chris Lattner2a49d572010-02-28 22:37:22 +00002361 case OPC_CheckCondCode:
Chris Lattnerda828e32010-03-03 07:46:25 +00002362 if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002363 continue;
Chris Lattnerda828e32010-03-03 07:46:25 +00002364 case OPC_CheckValueType:
2365 if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI)) break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002366 continue;
Chris Lattnerf1b7c7d2010-03-03 07:31:15 +00002367 case OPC_CheckInteger:
2368 if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002369 continue;
Chris Lattnerda828e32010-03-03 07:46:25 +00002370 case OPC_CheckAndImm:
2371 if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002372 continue;
Chris Lattnerda828e32010-03-03 07:46:25 +00002373 case OPC_CheckOrImm:
2374 if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002375 continue;
Chris Lattner2a49d572010-02-28 22:37:22 +00002376
2377 case OPC_CheckFoldableChainNode: {
2378 assert(NodeStack.size() != 1 && "No parent node");
2379 // Verify that all intermediate nodes between the root and this one have
2380 // a single use.
2381 bool HasMultipleUses = false;
2382 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i)
2383 if (!NodeStack[i].hasOneUse()) {
2384 HasMultipleUses = true;
2385 break;
2386 }
2387 if (HasMultipleUses) break;
2388
2389 // Check to see that the target thinks this is profitable to fold and that
2390 // we can fold it without inducing cycles in the graph.
2391 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
2392 NodeToMatch) ||
2393 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
Chris Lattnerd1b73822010-03-02 22:20:06 +00002394 NodeToMatch, true/*We validate our own chains*/))
Chris Lattner2a49d572010-02-28 22:37:22 +00002395 break;
2396
2397 continue;
2398 }
Chris Lattner2a49d572010-02-28 22:37:22 +00002399 case OPC_EmitInteger: {
2400 MVT::SimpleValueType VT =
2401 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2402 int64_t Val = MatcherTable[MatcherIndex++];
2403 if (Val & 128)
2404 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2405 RecordedNodes.push_back(CurDAG->getTargetConstant(Val, VT));
2406 continue;
2407 }
2408 case OPC_EmitRegister: {
2409 MVT::SimpleValueType VT =
2410 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2411 unsigned RegNo = MatcherTable[MatcherIndex++];
2412 RecordedNodes.push_back(CurDAG->getRegister(RegNo, VT));
2413 continue;
2414 }
2415
2416 case OPC_EmitConvertToTarget: {
2417 // Convert from IMM/FPIMM to target version.
2418 unsigned RecNo = MatcherTable[MatcherIndex++];
2419 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2420 SDValue Imm = RecordedNodes[RecNo];
2421
2422 if (Imm->getOpcode() == ISD::Constant) {
2423 int64_t Val = cast<ConstantSDNode>(Imm)->getZExtValue();
2424 Imm = CurDAG->getTargetConstant(Val, Imm.getValueType());
2425 } else if (Imm->getOpcode() == ISD::ConstantFP) {
2426 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
2427 Imm = CurDAG->getTargetConstantFP(*Val, Imm.getValueType());
2428 }
2429
2430 RecordedNodes.push_back(Imm);
2431 continue;
2432 }
2433
Chris Lattneraa4e3392010-03-28 05:50:16 +00002434 case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0
2435 case OPC_EmitMergeInputChains1_1: { // OPC_EmitMergeInputChains, 1, 1
2436 // These are space-optimized forms of OPC_EmitMergeInputChains.
2437 assert(InputChain.getNode() == 0 &&
2438 "EmitMergeInputChains should be the first chain producing node");
2439 assert(ChainNodesMatched.empty() &&
2440 "Should only have one EmitMergeInputChains per match");
2441
2442 // Read all of the chained nodes.
2443 unsigned RecNo = Opcode == OPC_EmitMergeInputChains1_1;
2444 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2445 ChainNodesMatched.push_back(RecordedNodes[RecNo].getNode());
2446
2447 // FIXME: What if other value results of the node have uses not matched
2448 // by this pattern?
2449 if (ChainNodesMatched.back() != NodeToMatch &&
2450 !RecordedNodes[RecNo].hasOneUse()) {
2451 ChainNodesMatched.clear();
2452 break;
2453 }
2454
2455 // Merge the input chains if they are not intra-pattern references.
2456 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
2457
2458 if (InputChain.getNode() == 0)
2459 break; // Failed to merge.
2460 continue;
2461 }
2462
Chris Lattner2a49d572010-02-28 22:37:22 +00002463 case OPC_EmitMergeInputChains: {
2464 assert(InputChain.getNode() == 0 &&
2465 "EmitMergeInputChains should be the first chain producing node");
2466 // This node gets a list of nodes we matched in the input that have
2467 // chains. We want to token factor all of the input chains to these nodes
2468 // together. However, if any of the input chains is actually one of the
2469 // nodes matched in this pattern, then we have an intra-match reference.
2470 // Ignore these because the newly token factored chain should not refer to
2471 // the old nodes.
2472 unsigned NumChains = MatcherTable[MatcherIndex++];
2473 assert(NumChains != 0 && "Can't TF zero chains");
2474
2475 assert(ChainNodesMatched.empty() &&
2476 "Should only have one EmitMergeInputChains per match");
2477
Chris Lattner2a49d572010-02-28 22:37:22 +00002478 // Read all of the chained nodes.
Chris Lattner00592ec2010-03-02 19:34:59 +00002479 for (unsigned i = 0; i != NumChains; ++i) {
2480 unsigned RecNo = MatcherTable[MatcherIndex++];
Chris Lattner2a49d572010-02-28 22:37:22 +00002481 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2482 ChainNodesMatched.push_back(RecordedNodes[RecNo].getNode());
2483
2484 // FIXME: What if other value results of the node have uses not matched
2485 // by this pattern?
2486 if (ChainNodesMatched.back() != NodeToMatch &&
2487 !RecordedNodes[RecNo].hasOneUse()) {
2488 ChainNodesMatched.clear();
2489 break;
2490 }
2491 }
Chris Lattner6b307922010-03-02 00:00:03 +00002492
2493 // If the inner loop broke out, the match fails.
2494 if (ChainNodesMatched.empty())
2495 break;
Chris Lattner2a49d572010-02-28 22:37:22 +00002496
Chris Lattner6b307922010-03-02 00:00:03 +00002497 // Merge the input chains if they are not intra-pattern references.
2498 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
2499
2500 if (InputChain.getNode() == 0)
2501 break; // Failed to merge.
Chris Lattner2a49d572010-02-28 22:37:22 +00002502
Chris Lattner2a49d572010-02-28 22:37:22 +00002503 continue;
2504 }
2505
2506 case OPC_EmitCopyToReg: {
2507 unsigned RecNo = MatcherTable[MatcherIndex++];
2508 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2509 unsigned DestPhysReg = MatcherTable[MatcherIndex++];
2510
2511 if (InputChain.getNode() == 0)
2512 InputChain = CurDAG->getEntryNode();
2513
2514 InputChain = CurDAG->getCopyToReg(InputChain, NodeToMatch->getDebugLoc(),
2515 DestPhysReg, RecordedNodes[RecNo],
2516 InputFlag);
2517
2518 InputFlag = InputChain.getValue(1);
2519 continue;
2520 }
2521
2522 case OPC_EmitNodeXForm: {
2523 unsigned XFormNo = MatcherTable[MatcherIndex++];
2524 unsigned RecNo = MatcherTable[MatcherIndex++];
2525 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2526 RecordedNodes.push_back(RunSDNodeXForm(RecordedNodes[RecNo], XFormNo));
2527 continue;
2528 }
2529
2530 case OPC_EmitNode:
2531 case OPC_MorphNodeTo: {
Chris Lattner14df8dc2010-02-28 22:38:43 +00002532 uint16_t TargetOpc = MatcherTable[MatcherIndex++];
2533 TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
Chris Lattner2a49d572010-02-28 22:37:22 +00002534 unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
2535 // Get the result VT list.
2536 unsigned NumVTs = MatcherTable[MatcherIndex++];
2537 SmallVector<EVT, 4> VTs;
2538 for (unsigned i = 0; i != NumVTs; ++i) {
2539 MVT::SimpleValueType VT =
2540 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2541 if (VT == MVT::iPTR) VT = TLI.getPointerTy().SimpleTy;
2542 VTs.push_back(VT);
2543 }
2544
2545 if (EmitNodeInfo & OPFL_Chain)
2546 VTs.push_back(MVT::Other);
2547 if (EmitNodeInfo & OPFL_FlagOutput)
2548 VTs.push_back(MVT::Flag);
2549
Chris Lattner7d892d62010-03-01 07:43:08 +00002550 // This is hot code, so optimize the two most common cases of 1 and 2
2551 // results.
2552 SDVTList VTList;
2553 if (VTs.size() == 1)
2554 VTList = CurDAG->getVTList(VTs[0]);
2555 else if (VTs.size() == 2)
2556 VTList = CurDAG->getVTList(VTs[0], VTs[1]);
2557 else
2558 VTList = CurDAG->getVTList(VTs.data(), VTs.size());
Chris Lattner2a49d572010-02-28 22:37:22 +00002559
2560 // Get the operand list.
2561 unsigned NumOps = MatcherTable[MatcherIndex++];
2562 SmallVector<SDValue, 8> Ops;
2563 for (unsigned i = 0; i != NumOps; ++i) {
2564 unsigned RecNo = MatcherTable[MatcherIndex++];
2565 if (RecNo & 128)
2566 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
2567
2568 assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
2569 Ops.push_back(RecordedNodes[RecNo]);
2570 }
2571
2572 // If there are variadic operands to add, handle them now.
2573 if (EmitNodeInfo & OPFL_VariadicInfo) {
2574 // Determine the start index to copy from.
2575 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
2576 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
2577 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
2578 "Invalid variadic node");
2579 // Copy all of the variadic operands, not including a potential flag
2580 // input.
2581 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
2582 i != e; ++i) {
2583 SDValue V = NodeToMatch->getOperand(i);
2584 if (V.getValueType() == MVT::Flag) break;
2585 Ops.push_back(V);
2586 }
2587 }
2588
2589 // If this has chain/flag inputs, add them.
2590 if (EmitNodeInfo & OPFL_Chain)
2591 Ops.push_back(InputChain);
2592 if ((EmitNodeInfo & OPFL_FlagInput) && InputFlag.getNode() != 0)
2593 Ops.push_back(InputFlag);
2594
2595 // Create the node.
2596 SDNode *Res = 0;
2597 if (Opcode != OPC_MorphNodeTo) {
2598 // If this is a normal EmitNode command, just create the new node and
2599 // add the results to the RecordedNodes list.
2600 Res = CurDAG->getMachineNode(TargetOpc, NodeToMatch->getDebugLoc(),
2601 VTList, Ops.data(), Ops.size());
2602
2603 // Add all the non-flag/non-chain results to the RecordedNodes list.
2604 for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
2605 if (VTs[i] == MVT::Other || VTs[i] == MVT::Flag) break;
2606 RecordedNodes.push_back(SDValue(Res, i));
2607 }
2608
2609 } else {
Chris Lattner3ff1e4d2010-03-02 06:55:04 +00002610 Res = MorphNode(NodeToMatch, TargetOpc, VTList, Ops.data(), Ops.size(),
2611 EmitNodeInfo);
Chris Lattner2a49d572010-02-28 22:37:22 +00002612 }
2613
2614 // If the node had chain/flag results, update our notion of the current
2615 // chain and flag.
Chris Lattner82dd3d32010-03-02 07:50:03 +00002616 if (EmitNodeInfo & OPFL_FlagOutput) {
Chris Lattner2a49d572010-02-28 22:37:22 +00002617 InputFlag = SDValue(Res, VTs.size()-1);
2618 if (EmitNodeInfo & OPFL_Chain)
2619 InputChain = SDValue(Res, VTs.size()-2);
2620 } else if (EmitNodeInfo & OPFL_Chain)
2621 InputChain = SDValue(Res, VTs.size()-1);
2622
2623 // If the OPFL_MemRefs flag is set on this node, slap all of the
2624 // accumulated memrefs onto it.
2625 //
2626 // FIXME: This is vastly incorrect for patterns with multiple outputs
2627 // instructions that access memory and for ComplexPatterns that match
2628 // loads.
2629 if (EmitNodeInfo & OPFL_MemRefs) {
2630 MachineSDNode::mmo_iterator MemRefs =
2631 MF->allocateMemRefsArray(MatchedMemRefs.size());
2632 std::copy(MatchedMemRefs.begin(), MatchedMemRefs.end(), MemRefs);
2633 cast<MachineSDNode>(Res)
2634 ->setMemRefs(MemRefs, MemRefs + MatchedMemRefs.size());
2635 }
2636
2637 DEBUG(errs() << " "
2638 << (Opcode == OPC_MorphNodeTo ? "Morphed" : "Created")
2639 << " node: "; Res->dump(CurDAG); errs() << "\n");
2640
2641 // If this was a MorphNodeTo then we're completely done!
2642 if (Opcode == OPC_MorphNodeTo) {
2643 // Update chain and flag uses.
2644 UpdateChainsAndFlags(NodeToMatch, InputChain, ChainNodesMatched,
Chris Lattner82dd3d32010-03-02 07:50:03 +00002645 InputFlag, FlagResultNodesMatched, true);
2646 return Res;
Chris Lattner2a49d572010-02-28 22:37:22 +00002647 }
2648
2649 continue;
2650 }
2651
2652 case OPC_MarkFlagResults: {
2653 unsigned NumNodes = MatcherTable[MatcherIndex++];
2654
2655 // Read and remember all the flag-result nodes.
2656 for (unsigned i = 0; i != NumNodes; ++i) {
2657 unsigned RecNo = MatcherTable[MatcherIndex++];
2658 if (RecNo & 128)
2659 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
2660
2661 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2662 FlagResultNodesMatched.push_back(RecordedNodes[RecNo].getNode());
2663 }
2664 continue;
2665 }
2666
2667 case OPC_CompleteMatch: {
2668 // The match has been completed, and any new nodes (if any) have been
2669 // created. Patch up references to the matched dag to use the newly
2670 // created nodes.
2671 unsigned NumResults = MatcherTable[MatcherIndex++];
2672
2673 for (unsigned i = 0; i != NumResults; ++i) {
2674 unsigned ResSlot = MatcherTable[MatcherIndex++];
2675 if (ResSlot & 128)
2676 ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
2677
2678 assert(ResSlot < RecordedNodes.size() && "Invalid CheckSame");
2679 SDValue Res = RecordedNodes[ResSlot];
2680
Chris Lattnerb0e483e2010-03-28 05:54:03 +00002681 assert(i < NodeToMatch->getNumValues() &&
2682 NodeToMatch->getValueType(i) != MVT::Other &&
2683 NodeToMatch->getValueType(i) != MVT::Flag &&
2684 "Invalid number of results to complete!");
Chris Lattner2a49d572010-02-28 22:37:22 +00002685 assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
2686 NodeToMatch->getValueType(i) == MVT::iPTR ||
2687 Res.getValueType() == MVT::iPTR ||
2688 NodeToMatch->getValueType(i).getSizeInBits() ==
2689 Res.getValueType().getSizeInBits()) &&
2690 "invalid replacement");
2691 CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res);
2692 }
2693
2694 // If the root node defines a flag, add it to the flag nodes to update
2695 // list.
2696 if (NodeToMatch->getValueType(NodeToMatch->getNumValues()-1) == MVT::Flag)
2697 FlagResultNodesMatched.push_back(NodeToMatch);
2698
2699 // Update chain and flag uses.
2700 UpdateChainsAndFlags(NodeToMatch, InputChain, ChainNodesMatched,
Chris Lattner82dd3d32010-03-02 07:50:03 +00002701 InputFlag, FlagResultNodesMatched, false);
Chris Lattner2a49d572010-02-28 22:37:22 +00002702
2703 assert(NodeToMatch->use_empty() &&
2704 "Didn't replace all uses of the node?");
2705
2706 // FIXME: We just return here, which interacts correctly with SelectRoot
2707 // above. We should fix this to not return an SDNode* anymore.
2708 return 0;
2709 }
2710 }
2711
2712 // If the code reached this point, then the match failed. See if there is
2713 // another child to try in the current 'Scope', otherwise pop it until we
2714 // find a case to check.
Dan Gohman19b38262010-03-09 02:15:05 +00002715 DEBUG(errs() << " Match failed at index " << CurrentOpcodeIndex << "\n");
Chris Lattnerbed993d2010-03-28 19:46:56 +00002716 ++NumDAGIselRetries;
Chris Lattner2a49d572010-02-28 22:37:22 +00002717 while (1) {
2718 if (MatchScopes.empty()) {
2719 CannotYetSelect(NodeToMatch);
2720 return 0;
2721 }
2722
2723 // Restore the interpreter state back to the point where the scope was
2724 // formed.
2725 MatchScope &LastScope = MatchScopes.back();
2726 RecordedNodes.resize(LastScope.NumRecordedNodes);
2727 NodeStack.clear();
2728 NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
2729 N = NodeStack.back();
2730
Chris Lattner2a49d572010-02-28 22:37:22 +00002731 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
2732 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
2733 MatcherIndex = LastScope.FailIndex;
2734
Dan Gohman19b38262010-03-09 02:15:05 +00002735 DEBUG(errs() << " Continuing at " << MatcherIndex << "\n");
2736
Chris Lattner2a49d572010-02-28 22:37:22 +00002737 InputChain = LastScope.InputChain;
2738 InputFlag = LastScope.InputFlag;
2739 if (!LastScope.HasChainNodesMatched)
2740 ChainNodesMatched.clear();
2741 if (!LastScope.HasFlagResultNodesMatched)
2742 FlagResultNodesMatched.clear();
2743
2744 // Check to see what the offset is at the new MatcherIndex. If it is zero
2745 // we have reached the end of this scope, otherwise we have another child
2746 // in the current scope to try.
2747 unsigned NumToSkip = MatcherTable[MatcherIndex++];
2748 if (NumToSkip & 128)
2749 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
2750
2751 // If we have another child in this scope to match, update FailIndex and
2752 // try it.
2753 if (NumToSkip != 0) {
2754 LastScope.FailIndex = MatcherIndex+NumToSkip;
2755 break;
2756 }
2757
2758 // End of this scope, pop it and try the next child in the containing
2759 // scope.
2760 MatchScopes.pop_back();
2761 }
2762 }
2763}
2764
2765
2766
Dan Gohmaneeb3a002010-01-05 01:24:18 +00002767void SelectionDAGISel::CannotYetSelect(SDNode *N) {
Dan Gohmane1f188f2009-10-29 22:30:23 +00002768 std::string msg;
2769 raw_string_ostream Msg(msg);
2770 Msg << "Cannot yet select: ";
Chris Lattner2c4afd12010-03-04 00:21:16 +00002771
2772 if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
2773 N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&
2774 N->getOpcode() != ISD::INTRINSIC_VOID) {
2775 N->printrFull(Msg, CurDAG);
2776 } else {
2777 bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
2778 unsigned iid =
2779 cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue();
2780 if (iid < Intrinsic::num_intrinsics)
2781 Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid);
2782 else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
2783 Msg << "target intrinsic %" << TII->getName(iid);
2784 else
2785 Msg << "unknown intrinsic #" << iid;
2786 }
Dan Gohmane1f188f2009-10-29 22:30:23 +00002787 llvm_report_error(Msg.str());
2788}
2789
Devang Patel19974732007-05-03 01:11:54 +00002790char SelectionDAGISel::ID = 0;