SelectionDAGISel.cpp revision 9882007003b12466df717cdf66824120ede405be
11c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner//===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
2edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman//
31c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner//                     The LLVM Compiler Infrastructure
41c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner//
54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source
64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details.
7edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman//
81c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner//===----------------------------------------------------------------------===//
91c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner//
101c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner// This implements the SelectionDAGISel class.
111c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner//
121c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner//===----------------------------------------------------------------------===//
131c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
141c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#define DEBUG_TYPE "isel"
1584fbac580941548a6ab1121ed3b0ffdc4e2bc080Dan Gohman#include "ScheduleDAGSDNodes.h"
162048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman#include "SelectionDAGBuilder.h"
176277eb2bb997a5da0808a8a5a57f18fd9faaf336Dan Gohman#include "FunctionLoweringInfo.h"
1884fbac580941548a6ab1121ed3b0ffdc4e2bc080Dan Gohman#include "llvm/CodeGen/SelectionDAGISel.h"
19c7c3f110eda0ff8040e4bd99e38d3112b910810fJim Laskey#include "llvm/Analysis/AliasAnalysis.h"
20713f043c16220b746804f668a72f4e0344cbe4d1Devang Patel#include "llvm/Analysis/DebugInfo.h"
215502bf67cd49221583c15472150905ce13184d36Anton Korobeynikov#include "llvm/Constants.h"
22adf6a965a321372c640845407195594835921eb4Chris Lattner#include "llvm/CallingConv.h"
231c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/DerivedTypes.h"
241c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Function.h"
2536ce69195ed488034d0bb11180cc2ebd923679c8Chris Lattner#include "llvm/GlobalVariable.h"
26ce7518ce92f45568dc7d4cbb863284afb962fec5Chris Lattner#include "llvm/InlineAsm.h"
271c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Instructions.h"
281c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Intrinsics.h"
2943970fec322d9e0153ca513de41d80af1c79bddeJim Laskey#include "llvm/IntrinsicInst.h"
3075c478a96a542dc386152e00518441e63d22058dChris Lattner#include "llvm/LLVMContext.h"
3178eca170e9ac5db7fd525f9bbf27090fefcbb646Dan Gohman#include "llvm/CodeGen/FastISel.h"
325a29c9eed157af51a8d338b5a225b146881819e8Gordon Henriksen#include "llvm/CodeGen/GCStrategy.h"
335eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen#include "llvm/CodeGen/GCMetadata.h"
341c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/MachineFunction.h"
35ad2afc2a421a0e41603d5eee412d4d8c77e9bc1cDan Gohman#include "llvm/CodeGen/MachineFunctionAnalysis.h"
361c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/MachineFrameInfo.h"
371c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/MachineInstrBuilder.h"
3884bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineJumpTableInfo.h"
3984bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineModuleInfo.h"
4084bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h"
41fc54c552963545a81e4ea38e60460590afb2d5aeDan Gohman#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
42eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey#include "llvm/CodeGen/SchedulerRegistry.h"
431c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/SelectionDAG.h"
446e7a1617ac4a34792d9097b8d3644b72f57a45f7Devang Patel#include "llvm/CodeGen/DwarfWriter.h"
456f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h"
461c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetData.h"
471c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetFrameInfo.h"
48e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman#include "llvm/Target/TargetIntrinsicInfo.h"
491c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetInstrInfo.h"
501c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetLowering.h"
511c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetMachine.h"
52124729155d860a0850eb4ef2a7cea4145e13a057Vladimir Prus#include "llvm/Target/TargetOptions.h"
53a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h"
54db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng#include "llvm/Support/Debug.h"
557d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h"
56db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng#include "llvm/Support/MathExtras.h"
57db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng#include "llvm/Support/Timer.h"
58ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h"
597e88103cdea8c36b2229dae8c60def14e3816512Jeff Cohen#include <algorithm>
601c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattnerusing namespace llvm;
611c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
62ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattnerstatic cl::opt<bool>
63293d5f8bc02a9148238b2c79484637f56de65b9cDan GohmanEnableFastISelVerbose("fast-isel-verbose", cl::Hidden,
64d659d50482e2f9edf8f436e4a1aa30c68c6d020bDan Gohman          cl::desc("Enable verbose messages in the \"fast\" "
65293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman                   "instruction selector"));
66293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohmanstatic cl::opt<bool>
674344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan GohmanEnableFastISelAbort("fast-isel-abort", cl::Hidden,
684344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman          cl::desc("Enable abort calls when \"fast\" instruction fails"));
698a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohmanstatic cl::opt<bool>
70df8ed024735b651d6e0082262d4e7a00b2fa4d32Evan ChengSchedLiveInCopies("schedule-livein-copies", cl::Hidden,
718a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                  cl::desc("Schedule copies of livein registers"),
728a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                  cl::init(false));
73ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner
74da8abb02397d7cd62a1e16e7c534edd7096ac873Chris Lattner#ifndef NDEBUG
757944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattnerstatic cl::opt<bool>
76462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
77462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman          cl::desc("Pop up a window to show dags before the first "
78462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman                   "dag combine pass"));
79462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool>
80462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
81462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman          cl::desc("Pop up a window to show dags before legalize types"));
82462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool>
83462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
84462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman          cl::desc("Pop up a window to show dags before legalize"));
85462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool>
86462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
87462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman          cl::desc("Pop up a window to show dags before the second "
88462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman                   "dag combine pass"));
89462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool>
9025cf2275ff7de3de3bc0e508abaf457413d74725Duncan SandsViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
9125cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands          cl::desc("Pop up a window to show dags before the post legalize types"
9225cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands                   " dag combine pass"));
9325cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sandsstatic cl::opt<bool>
94a9c2091cd38e401c846391c9951ff416e709b65eEvan ChengViewISelDAGs("view-isel-dags", cl::Hidden,
95a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng          cl::desc("Pop up a window to show isel dags as they are selected"));
96a9c2091cd38e401c846391c9951ff416e709b65eEvan Chengstatic cl::opt<bool>
97a9c2091cd38e401c846391c9951ff416e709b65eEvan ChengViewSchedDAGs("view-sched-dags", cl::Hidden,
98a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng          cl::desc("Pop up a window to show sched dags as they are processed"));
993e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohmanstatic cl::opt<bool>
1003e1a7aef17575d9c7058a035449d57e3c7295ed0Dan GohmanViewSUnitDAGs("view-sunit-dags", cl::Hidden,
1015bab78527a946632cd9614daa0b9a82ee7b5e1ccChris Lattner      cl::desc("Pop up a window to show SUnit dags after they are processed"));
1027944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattner#else
103462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic const bool ViewDAGCombine1 = false,
104462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman                  ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
105462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman                  ViewDAGCombine2 = false,
10625cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands                  ViewDAGCombineLT = false,
107462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman                  ViewISelDAGs = false, ViewSchedDAGs = false,
108462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman                  ViewSUnitDAGs = false;
1097944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattner#endif
1107944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattner
111eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===//
112eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey///
113eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// RegisterScheduler class - Track the registration of instruction schedulers.
114eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey///
115eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===//
116eb577ba3b815a1fa4627b060dd2345d17abf672dJim LaskeyMachinePassRegistry RegisterScheduler::Registry;
117eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey
118eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===//
119eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey///
120eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// ISHeuristic command line option for instruction schedulers.
121eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey///
122eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===//
123844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<RegisterScheduler::FunctionPassCtor, false,
124844731a7f1909f55935e3514c9e713a62d67662eDan Gohman               RegisterPassParser<RegisterScheduler> >
125844731a7f1909f55935e3514c9e713a62d67662eDan GohmanISHeuristic("pre-RA-sched",
126844731a7f1909f55935e3514c9e713a62d67662eDan Gohman            cl::init(&createDefaultScheduler),
127844731a7f1909f55935e3514c9e713a62d67662eDan Gohman            cl::desc("Instruction schedulers available (before register"
128844731a7f1909f55935e3514c9e713a62d67662eDan Gohman                     " allocation):"));
12913ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey
130844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterScheduler
131b8cab9227a0f6ffbdaae33e3c64268e265008a6aDan GohmandefaultListDAGScheduler("default", "Best scheduler for the target",
132844731a7f1909f55935e3514c9e713a62d67662eDan Gohman                        createDefaultScheduler);
1334ef10867499aa146cd819c78d8d37a8353d4f0ffEvan Cheng
134f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmannamespace llvm {
135f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman  //===--------------------------------------------------------------------===//
136f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman  /// createDefaultScheduler - This creates an instruction scheduler appropriate
137f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman  /// for the target.
13847ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman  ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS,
13998a366d547772010e94609e4584489b3e5ce0043Bill Wendling                                             CodeGenOpt::Level OptLevel) {
140e9530ecae4897fe8157bd4d7616043bd8c0484e2Dan Gohman    const TargetLowering &TLI = IS->getTargetLowering();
141e9530ecae4897fe8157bd4d7616043bd8c0484e2Dan Gohman
14298a366d547772010e94609e4584489b3e5ce0043Bill Wendling    if (OptLevel == CodeGenOpt::None)
143be8cc2a3dedeb7685f07e68cdc4b9502eb97eb2bBill Wendling      return createFastDAGScheduler(IS, OptLevel);
1449e76fea3abd4229749e6ead46a0016cabff4a056Dan Gohman    if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency)
145be8cc2a3dedeb7685f07e68cdc4b9502eb97eb2bBill Wendling      return createTDListDAGScheduler(IS, OptLevel);
1469e76fea3abd4229749e6ead46a0016cabff4a056Dan Gohman    assert(TLI.getSchedulingPreference() ==
1479e76fea3abd4229749e6ead46a0016cabff4a056Dan Gohman         TargetLowering::SchedulingForRegPressure && "Unknown sched type!");
148be8cc2a3dedeb7685f07e68cdc4b9502eb97eb2bBill Wendling    return createBURRListDAGScheduler(IS, OptLevel);
1493a508c94a6c6f124e8b0549358ce76deb92ab662Chris Lattner  }
1501c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner}
1511c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
152ff9b373e8f5006c629af81e2619778b4c4f5249eEvan Cheng// EmitInstrWithCustomInserter - This method should be implemented by targets
153533297b58da8c74bec65551e1aface9801fc2259Dan Gohman// that mark instructions with the 'usesCustomInserter' flag.  These
154025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner// instructions are special in various ways, which require special support to
155025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner// insert.  The specified MachineInstr is created but not inserted into any
156533297b58da8c74bec65551e1aface9801fc2259Dan Gohman// basic blocks, and this method is called to expand it into a sequence of
157533297b58da8c74bec65551e1aface9801fc2259Dan Gohman// instructions, potentially also creating new basic blocks and control flow.
158533297b58da8c74bec65551e1aface9801fc2259Dan Gohman// When new basic blocks are inserted and the edges from MBB to its successors
159533297b58da8c74bec65551e1aface9801fc2259Dan Gohman// are modified, the method should insert pairs of <OldSucc, NewSucc> into the
160533297b58da8c74bec65551e1aface9801fc2259Dan Gohman// DenseMap.
161ff9b373e8f5006c629af81e2619778b4c4f5249eEvan ChengMachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI,
162fb2e752e4175920d0531f2afc93a23d0cdf4db14Evan Cheng                                                         MachineBasicBlock *MBB,
163fb2e752e4175920d0531f2afc93a23d0cdf4db14Evan Cheng                   DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) const {
164f36892335b4919b9120e48a792e6b3630b9de978Torok Edwin#ifndef NDEBUG
1654437ae213d5435390f0750213b53ec807c047f22Chris Lattner  errs() << "If a target marks an instruction with "
166533297b58da8c74bec65551e1aface9801fc2259Dan Gohman          "'usesCustomInserter', it must implement "
167f36892335b4919b9120e48a792e6b3630b9de978Torok Edwin          "TargetLowering::EmitInstrWithCustomInserter!";
168f36892335b4919b9120e48a792e6b3630b9de978Torok Edwin#endif
169c23197a26f34f559ea9797de51e187087c039c42Torok Edwin  llvm_unreachable(0);
170a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar  return 0;
171025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner}
172025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner
1738a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// EmitLiveInCopy - Emit a copy for a live in physical register. If the
1748a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// physical register has only a single copy use, then coalesced the copy
1758a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// if possible.
1768a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohmanstatic void EmitLiveInCopy(MachineBasicBlock *MBB,
1778a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                           MachineBasicBlock::iterator &InsertPos,
1788a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                           unsigned VirtReg, unsigned PhysReg,
1798a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                           const TargetRegisterClass *RC,
1808a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                           DenseMap<MachineInstr*, unsigned> &CopyRegMap,
1818a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                           const MachineRegisterInfo &MRI,
1828a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                           const TargetRegisterInfo &TRI,
1838a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                           const TargetInstrInfo &TII) {
1848a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  unsigned NumUses = 0;
1858a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  MachineInstr *UseMI = NULL;
1868a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(VirtReg),
1878a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman         UE = MRI.use_end(); UI != UE; ++UI) {
1888a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    UseMI = &*UI;
1898a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    if (++NumUses > 1)
1908a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      break;
1918a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  }
1928a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman
1938a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  // If the number of uses is not one, or the use is not a move instruction,
1948a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  // don't coalesce. Also, only coalesce away a virtual register to virtual
1958a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  // register copy.
1968a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  bool Coalesced = false;
19704ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng  unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
1988a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  if (NumUses == 1 &&
19904ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng      TII.isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
2008a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      TargetRegisterInfo::isVirtualRegister(DstReg)) {
2018a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    VirtReg = DstReg;
2028a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    Coalesced = true;
2038a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  }
2048a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman
2058a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  // Now find an ideal location to insert the copy.
2068a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  MachineBasicBlock::iterator Pos = InsertPos;
2078a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  while (Pos != MBB->begin()) {
2088a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    MachineInstr *PrevMI = prior(Pos);
2098a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    DenseMap<MachineInstr*, unsigned>::iterator RI = CopyRegMap.find(PrevMI);
2108a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    // copyRegToReg might emit multiple instructions to do a copy.
2118a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    unsigned CopyDstReg = (RI == CopyRegMap.end()) ? 0 : RI->second;
2128a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    if (CopyDstReg && !TRI.regsOverlap(CopyDstReg, PhysReg))
2138a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // This is what the BB looks like right now:
2148a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // r1024 = mov r0
2158a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // ...
2168a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // r1    = mov r1024
2178a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      //
2188a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // We want to insert "r1025 = mov r1". Inserting this copy below the
2198a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // move to r1024 makes it impossible for that move to be coalesced.
2208a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      //
2218a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // r1025 = mov r1
2228a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // r1024 = mov r0
2238a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // ...
2248a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // r1    = mov 1024
2258a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      // r2    = mov 1025
2268a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      break; // Woot! Found a good location.
2278a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    --Pos;
2288a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  }
2298a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman
230f1daf7d8abebd6e0104a6b41a774ccbb19a51c60David Goodwin  bool Emitted = TII.copyRegToReg(*MBB, Pos, VirtReg, PhysReg, RC, RC);
231f1daf7d8abebd6e0104a6b41a774ccbb19a51c60David Goodwin  assert(Emitted && "Unable to issue a live-in copy instruction!\n");
232f1daf7d8abebd6e0104a6b41a774ccbb19a51c60David Goodwin  (void) Emitted;
233a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
234931424a7d8b8b15ddda7308d6c5b08277d8bdc0eZhongxing Xu  CopyRegMap.insert(std::make_pair(prior(Pos), VirtReg));
2358a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  if (Coalesced) {
2368a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    if (&*InsertPos == UseMI) ++InsertPos;
2378a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    MBB->erase(UseMI);
2388a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  }
2398a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman}
2408a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman
2418a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// EmitLiveInCopies - If this is the first basic block in the function,
2428a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// and if it has live ins that need to be copied into vregs, emit the
2438a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// copies into the block.
2448a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohmanstatic void EmitLiveInCopies(MachineBasicBlock *EntryMBB,
2458a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                             const MachineRegisterInfo &MRI,
2468a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                             const TargetRegisterInfo &TRI,
2478a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                             const TargetInstrInfo &TII) {
2488a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  if (SchedLiveInCopies) {
2498a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    // Emit the copies at a heuristically-determined location in the block.
2508a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    DenseMap<MachineInstr*, unsigned> CopyRegMap;
2518a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    MachineBasicBlock::iterator InsertPos = EntryMBB->begin();
2528a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(),
2538a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman           E = MRI.livein_end(); LI != E; ++LI)
2548a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      if (LI->second) {
2558a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman        const TargetRegisterClass *RC = MRI.getRegClass(LI->second);
2568a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman        EmitLiveInCopy(EntryMBB, InsertPos, LI->second, LI->first,
2578a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman                       RC, CopyRegMap, MRI, TRI, TII);
2588a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      }
2598a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  } else {
2608a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    // Emit the copies into the top of the block.
2618a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman    for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(),
2628a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman           E = MRI.livein_end(); LI != E; ++LI)
2638a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      if (LI->second) {
2648a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman        const TargetRegisterClass *RC = MRI.getRegClass(LI->second);
265f1daf7d8abebd6e0104a6b41a774ccbb19a51c60David Goodwin        bool Emitted = TII.copyRegToReg(*EntryMBB, EntryMBB->begin(),
266f1daf7d8abebd6e0104a6b41a774ccbb19a51c60David Goodwin                                        LI->second, LI->first, RC, RC);
267f1daf7d8abebd6e0104a6b41a774ccbb19a51c60David Goodwin        assert(Emitted && "Unable to issue a live-in copy instruction!\n");
268f1daf7d8abebd6e0104a6b41a774ccbb19a51c60David Goodwin        (void) Emitted;
2698a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman      }
2708a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  }
2718a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman}
2728a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman
2737041ee35adecb864e3e8df490aa73b0605fbfb5aChris Lattner//===----------------------------------------------------------------------===//
2747041ee35adecb864e3e8df490aa73b0605fbfb5aChris Lattner// SelectionDAGISel code
2757041ee35adecb864e3e8df490aa73b0605fbfb5aChris Lattner//===----------------------------------------------------------------------===//
2761c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
27798a366d547772010e94609e4584489b3e5ce0043Bill WendlingSelectionDAGISel::SelectionDAGISel(TargetMachine &tm, CodeGenOpt::Level OL) :
278ad2afc2a421a0e41603d5eee412d4d8c77e9bc1cDan Gohman  MachineFunctionPass(&ID), TM(tm), TLI(*tm.getTargetLowering()),
2797c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman  FuncInfo(new FunctionLoweringInfo(TLI)),
2807c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman  CurDAG(new SelectionDAG(TLI, *FuncInfo)),
2812048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  SDB(new SelectionDAGBuilder(*CurDAG, TLI, *FuncInfo, OL)),
2827c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman  GFI(),
283be8cc2a3dedeb7685f07e68cdc4b9502eb97eb2bBill Wendling  OptLevel(OL),
2847c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman  DAGSize(0)
2857c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman{}
2867c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman
2877c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan GohmanSelectionDAGISel::~SelectionDAGISel() {
2882048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  delete SDB;
2897c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman  delete CurDAG;
2907c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman  delete FuncInfo;
2917c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman}
2927c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman
293e50ed30282bb5b4a9ed952580523f2dda16215acOwen Andersonunsigned SelectionDAGISel::MakeReg(EVT VT) {
29484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner  return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
2951c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner}
2961c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
297495a0b51915eb763576874f29192820b731edc22Chris Lattnervoid SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
298c7c3f110eda0ff8040e4bd99e38d3112b910810fJim Laskey  AU.addRequired<AliasAnalysis>();
299a3477fe06df794e0eae26ea243f25912c619a6c4Dan Gohman  AU.addPreserved<AliasAnalysis>();
3005eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen  AU.addRequired<GCModuleInfo>();
301a3477fe06df794e0eae26ea243f25912c619a6c4Dan Gohman  AU.addPreserved<GCModuleInfo>();
3026e7a1617ac4a34792d9097b8d3644b72f57a45f7Devang Patel  AU.addRequired<DwarfWriter>();
303a3477fe06df794e0eae26ea243f25912c619a6c4Dan Gohman  AU.addPreserved<DwarfWriter>();
304ad2afc2a421a0e41603d5eee412d4d8c77e9bc1cDan Gohman  MachineFunctionPass::getAnalysisUsage(AU);
305495a0b51915eb763576874f29192820b731edc22Chris Lattner}
3061c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
307ad2afc2a421a0e41603d5eee412d4d8c77e9bc1cDan Gohmanbool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
308ad2afc2a421a0e41603d5eee412d4d8c77e9bc1cDan Gohman  Function &Fn = *mf.getFunction();
309ad2afc2a421a0e41603d5eee412d4d8c77e9bc1cDan Gohman
3104344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman  // Do some sanity-checking on the command-line options.
3114344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman  assert((!EnableFastISelVerbose || EnableFastISel) &&
3124344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman         "-fast-isel-verbose requires -fast-isel");
3134344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman  assert((!EnableFastISelAbort || EnableFastISel) &&
3144344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman         "-fast-isel-abort requires -fast-isel");
3154344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman
3165f43f92c69aae9837064cf08291db1b36a82789fDan Gohman  // Get alias analysis for load/store combining.
3175f43f92c69aae9837064cf08291db1b36a82789fDan Gohman  AA = &getAnalysis<AliasAnalysis>();
3185f43f92c69aae9837064cf08291db1b36a82789fDan Gohman
319ad2afc2a421a0e41603d5eee412d4d8c77e9bc1cDan Gohman  MF = &mf;
3208a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  const TargetInstrInfo &TII = *TM.getInstrInfo();
3218a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
3228a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman
323f7d6cd46e920776bb33913b2498347cf99358dc4Dan Gohman  if (Fn.hasGC())
324f7d6cd46e920776bb33913b2498347cf99358dc4Dan Gohman    GFI = &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn);
325ce2247755e56f99a2377b64a1a9d393726582b85Gordon Henriksen  else
3265eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen    GFI = 0;
32779ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman  RegInfo = &MF->getRegInfo();
328ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar  DEBUG(errs() << "\n\n\n=== " << Fn.getName() << "\n");
3291c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
3301465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands  MachineModuleInfo *MMI = getAnalysisIfAvailable<MachineModuleInfo>();
3311465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands  DwarfWriter *DW = getAnalysisIfAvailable<DwarfWriter>();
3325dcaceb0a6a7fcf508d9898547e10d374b0e4cd1Owen Anderson  CurDAG->init(*MF, MMI, DW);
3336277eb2bb997a5da0808a8a5a57f18fd9faaf336Dan Gohman  FuncInfo->set(Fn, *MF, EnableFastISel);
3342048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  SDB->init(GFI, *AA);
3351c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
3361532f3ddd77c362dd5f613af06b4de636e3c5b0eDale Johannesen  for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
3371532f3ddd77c362dd5f613af06b4de636e3c5b0eDale Johannesen    if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator()))
3381532f3ddd77c362dd5f613af06b4de636e3c5b0eDale Johannesen      // Mark landing pad.
3397c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman      FuncInfo->MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
3409fac0b5ff24e733072bdde68c7f34590c1892922Duncan Sands
34179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman  SelectAllBasicBlocks(Fn, *MF, MMI, DW, TII);
342edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman
3438a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  // If the first basic block in the function has live ins that need to be
3448a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  // copied into vregs, emit the copies into the top of the block before
3458a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  // emitting the code for the block.
34679ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman  EmitLiveInCopies(MF->begin(), *RegInfo, TRI, TII);
3478a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman
348ad2070c667ebabf1650be63e6b3e0b411da86918Evan Cheng  // Add function live-ins to entry block live-in set.
3498a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman  for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(),
3508a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman         E = RegInfo->livein_end(); I != E; ++I)
35179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman    MF->begin()->addLiveIn(I->first);
352ad2070c667ebabf1650be63e6b3e0b411da86918Evan Cheng
353f40708223e409a152834b1553c6883ff2035b957Duncan Sands#ifndef NDEBUG
3547c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman  assert(FuncInfo->CatchInfoFound.size() == FuncInfo->CatchInfoLost.size() &&
355f40708223e409a152834b1553c6883ff2035b957Duncan Sands         "Not all catch info was assigned to a landing pad!");
356f40708223e409a152834b1553c6883ff2035b957Duncan Sands#endif
357f40708223e409a152834b1553c6883ff2035b957Duncan Sands
3587c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman  FuncInfo->clear();
3597c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman
3601c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner  return true;
3611c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner}
3621c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
36307f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman/// SetDebugLoc - Update MF's and SDB's DebugLocs if debug information is
36407f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman/// attached with this instruction.
36507f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohmanstatic void SetDebugLoc(unsigned MDDbgKind,
36607f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman                        MetadataContext &TheMetadata,
36707f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman                        Instruction *I,
36807f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman                        SelectionDAGBuilder *SDB,
36907f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman                        FastISel *FastIS,
37007f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman                        MachineFunction *MF) {
37107f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman  if (!isa<DbgInfoIntrinsic>(I))
37207f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman    if (MDNode *Dbg = TheMetadata.getMD(MDDbgKind, I)) {
37307f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      DILocation DILoc(Dbg);
37407f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      DebugLoc Loc = ExtractDebugLocation(DILoc, MF->getDebugLocInfo());
37507f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman
37607f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      SDB->setCurDebugLoc(Loc);
37707f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman
37807f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      if (FastIS)
37907f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman        FastIS->setCurDebugLoc(Loc);
38007f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman
38107f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      // If the function doesn't have a default debug location yet, set
38207f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      // it. This is kind of a hack.
38307f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      if (MF->getDefaultDebugLoc().isUnknown())
38407f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman        MF->setDefaultDebugLoc(Loc);
38507f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman    }
38607f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman}
38707f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman
38807f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman/// ResetDebugLoc - Set MF's and SDB's DebugLocs to Unknown.
38907f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohmanstatic void ResetDebugLoc(SelectionDAGBuilder *SDB,
39007f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman                          FastISel *FastIS) {
39107f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman  SDB->setCurDebugLoc(DebugLoc::getUnknownLoc());
39207f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman  if (FastIS)
393688fb80334e1ad7b259a051411bb72e18abea9e7Dan Gohman    FastIS->setCurDebugLoc(DebugLoc::getUnknownLoc());
39407f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman}
39507f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman
396f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohmanvoid SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB,
397f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman                                        BasicBlock::iterator Begin,
398b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman                                        BasicBlock::iterator End,
399b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman                                        bool &HadTailCall) {
4002048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  SDB->setCurrentBasicBlock(BB);
401e30e678865b8dc1b69ef1c26e7567ffd1300553cDevang Patel  MetadataContext &TheMetadata = LLVMBB->getParent()->getContext().getMetadata();
402a2148402ce39fb3aad09e98a32078d3853a01ae9Devang Patel  unsigned MDDbgKind = TheMetadata.getMDKind("dbg");
403f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman
40498ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman  // Lower all of the non-terminator instructions. If a call is emitted
40598ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman  // as a tail call, cease emitting nodes for this block.
4062048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  for (BasicBlock::iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
40707f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman    if (MDDbgKind)
40807f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      SetDebugLoc(MDDbgKind, TheMetadata, I, SDB, 0, MF);
40907f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman
41007f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman    if (!isa<TerminatorInst>(I)) {
4112048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->visit(*I);
41207f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman
41307f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      // Set the current debug location back to "unknown" so that it doesn't
41407f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      // spuriously apply to subsequent instructions.
41507f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      ResetDebugLoc(SDB, 0);
41607f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman    }
417123eaa71b50f5ac2ea2233685baedddbb72f387bDevang Patel  }
418f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman
4192048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  if (!SDB->HasTailCall) {
42098ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman    // Ensure that all instructions which are used outside of their defining
42198ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman    // blocks are available as virtual registers.  Invoke is handled elsewhere.
42298ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman    for (BasicBlock::iterator I = Begin; I != End; ++I)
42398ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman      if (!isa<PHINode>(I) && !isa<InvokeInst>(I))
4242048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        SDB->CopyToExportRegsIfNeeded(I);
425f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman
42698ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman    // Handle PHI nodes in successor blocks.
42798ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman    if (End == LLVMBB->end()) {
42898ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman      HandlePHINodesInSuccessorBlocks(LLVMBB);
4293df24e667f04a7003342b534310919abc9c87418Dan Gohman
43098ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman      // Lower the terminator after the copies are emitted.
43107f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      SetDebugLoc(MDDbgKind, TheMetadata, LLVMBB->getTerminator(), SDB, 0, MF);
4322048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->visit(*LLVMBB->getTerminator());
43307f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman      ResetDebugLoc(SDB, 0);
43498ca4f2a325f72374a477f9deba7d09e8999c29bDan Gohman    }
4353df24e667f04a7003342b534310919abc9c87418Dan Gohman  }
436a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
437a651cf67b77cd477dd7da4baa8688af2ccd4f7f6Chris Lattner  // Make sure the root of the DAG is up-to-date.
4382048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  CurDAG->setRoot(SDB->getControlRoot());
439c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer
440f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  // Final step, emit the lowered DAG as machine code.
441f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  CodeGenAndEmitDAG();
4422048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  HadTailCall = SDB->HasTailCall;
4432048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  SDB->clear();
4441c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner}
4451c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
446f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohmanvoid SelectionDAGISel::ComputeLiveOutVRegInfo() {
447ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner  SmallPtrSet<SDNode*, 128> VisitedNodes;
448ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner  SmallVector<SDNode*, 128> Worklist;
449a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
450ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif  Worklist.push_back(CurDAG->getRoot().getNode());
451a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
452ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner  APInt Mask;
453ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner  APInt KnownZero;
454ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner  APInt KnownOne;
455a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
456ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner  while (!Worklist.empty()) {
457ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    SDNode *N = Worklist.back();
458ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    Worklist.pop_back();
459a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
460ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    // If we've already seen this node, ignore it.
461ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    if (!VisitedNodes.insert(N))
462ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner      continue;
463a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
464ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    // Otherwise, add all chain operands to the worklist.
465ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
466825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson      if (N->getOperand(i).getValueType() == MVT::Other)
467ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif        Worklist.push_back(N->getOperand(i).getNode());
468a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
469ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    // If this is a CopyToReg with a vreg dest, process it.
470ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    if (N->getOpcode() != ISD::CopyToReg)
471ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner      continue;
472a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
473ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
474ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    if (!TargetRegisterInfo::isVirtualRegister(DestReg))
475ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner      continue;
476a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
477ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    // Ignore non-scalar or non-integer values.
478475871a144eb604ddaf37503397ba0941442e5fbDan Gohman    SDValue Src = N->getOperand(2);
479e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson    EVT SrcVT = Src.getValueType();
480ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    if (!SrcVT.isInteger() || SrcVT.isVector())
481ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner      continue;
482a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
483f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman    unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
484ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits());
485f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman    CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne);
486a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
487ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    // Only install this information if it tells us something.
488ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) {
489ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner      DestReg -= TargetRegisterInfo::FirstVirtualRegister;
490f7d6cd46e920776bb33913b2498347cf99358dc4Dan Gohman      if (DestReg >= FuncInfo->LiveOutRegInfo.size())
491f7d6cd46e920776bb33913b2498347cf99358dc4Dan Gohman        FuncInfo->LiveOutRegInfo.resize(DestReg+1);
492f7d6cd46e920776bb33913b2498347cf99358dc4Dan Gohman      FunctionLoweringInfo::LiveOutInfo &LOI =
493f7d6cd46e920776bb33913b2498347cf99358dc4Dan Gohman        FuncInfo->LiveOutRegInfo[DestReg];
494ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner      LOI.NumSignBits = NumSignBits;
495a80efceb93211a22e13dfc68198da4a25c1a7762Dan Gohman      LOI.KnownOne = KnownOne;
496a80efceb93211a22e13dfc68198da4a25c1a7762Dan Gohman      LOI.KnownZero = KnownZero;
497ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner    }
498ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner  }
499ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner}
500ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner
501f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohmanvoid SelectionDAGISel::CodeGenAndEmitDAG() {
502462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman  std::string GroupName;
503462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman  if (TimePassesIsEnabled)
504462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman    GroupName = "Instruction Selection and Scheduling";
505462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman  std::string BlockName;
506462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman  if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
50725cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands      ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
50825cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands      ViewSUnitDAGs)
509f7d6cd46e920776bb33913b2498347cf99358dc4Dan Gohman    BlockName = MF->getFunction()->getNameStr() + ":" +
510f6ccee5a9d2b9573f679bca6266ade3eb8cd3f88Daniel Dunbar                BB->getBasicBlock()->getNameStr();
511462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman
512bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner  DEBUG(errs() << "Initial selection DAG:\n");
513f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  DEBUG(CurDAG->dump());
514462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman
515f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName);
516417e11b9bf625b3626f8765d44248927fb200906Dan Gohman
517af21d55aee8d6852fedfd630395a3c7c95df8f12Chris Lattner  // Run the DAG combiner in pre-legalize mode.
518ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  if (TimePassesIsEnabled) {
5195e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman    NamedRegionTimer T("DAG Combining 1", GroupName);
520be8cc2a3dedeb7685f07e68cdc4b9502eb97eb2bBill Wendling    CurDAG->Combine(Unrestricted, *AA, OptLevel);
521ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  } else {
522be8cc2a3dedeb7685f07e68cdc4b9502eb97eb2bBill Wendling    CurDAG->Combine(Unrestricted, *AA, OptLevel);
523ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  }
524a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
525bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner  DEBUG(errs() << "Optimized lowered selection DAG:\n");
526f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  DEBUG(CurDAG->dump());
527a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
5281c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner  // Second step, hack on the DAG until it only uses operations and types that
5291c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner  // the target supports.
530714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " +
531714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman                                               BlockName);
532714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman
533714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  bool Changed;
534714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  if (TimePassesIsEnabled) {
535714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    NamedRegionTimer T("Type Legalization", GroupName);
536714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    Changed = CurDAG->LegalizeTypes();
537714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  } else {
538714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    Changed = CurDAG->LegalizeTypes();
539714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  }
540714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman
541714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  DEBUG(errs() << "Type-legalized selection DAG:\n");
542714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  DEBUG(CurDAG->dump());
543462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman
544714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  if (Changed) {
545714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    if (ViewDAGCombineLT)
546714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman      CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
547714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman
548714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    // Run the DAG combiner in post-type-legalize mode.
549462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman    if (TimePassesIsEnabled) {
550714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman      NamedRegionTimer T("DAG Combining after legalize types", GroupName);
551714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman      CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);
552462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman    } else {
553714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman      CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);
554462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman    }
555462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman
556714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    DEBUG(errs() << "Optimized type-legalized selection DAG:\n");
557f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman    DEBUG(CurDAG->dump());
558714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  }
559462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman
560714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  if (TimePassesIsEnabled) {
561714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    NamedRegionTimer T("Vector Legalization", GroupName);
562714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    Changed = CurDAG->LegalizeVectors();
563714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  } else {
564714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    Changed = CurDAG->LegalizeVectors();
565714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  }
5665c22c8074404797f1313b1334757254fb5c6487aEli Friedman
567714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman  if (Changed) {
5685c22c8074404797f1313b1334757254fb5c6487aEli Friedman    if (TimePassesIsEnabled) {
569714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman      NamedRegionTimer T("Type Legalization 2", GroupName);
5709882007003b12466df717cdf66824120ede405beBill Wendling      CurDAG->LegalizeTypes();
5715c22c8074404797f1313b1334757254fb5c6487aEli Friedman    } else {
5729882007003b12466df717cdf66824120ede405beBill Wendling      CurDAG->LegalizeTypes();
5735c22c8074404797f1313b1334757254fb5c6487aEli Friedman    }
5745c22c8074404797f1313b1334757254fb5c6487aEli Friedman
575714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    if (ViewDAGCombineLT)
576714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman      CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
5775c22c8074404797f1313b1334757254fb5c6487aEli Friedman
578714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    // Run the DAG combiner in post-type-legalize mode.
579714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    if (TimePassesIsEnabled) {
580714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman      NamedRegionTimer T("DAG Combining after legalize vectors", GroupName);
581714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman      CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
582714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    } else {
583714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman      CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
5845c22c8074404797f1313b1334757254fb5c6487aEli Friedman    }
585714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman
586714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    DEBUG(errs() << "Optimized vector-legalized selection DAG:\n");
587714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    DEBUG(CurDAG->dump());
58870587ea813986bb0dbef71610091d496e28c22a6Chris Lattner  }
589a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
590f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName);
591462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman
592ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  if (TimePassesIsEnabled) {
5935e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman    NamedRegionTimer T("DAG Legalization", GroupName);
594714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    CurDAG->Legalize(OptLevel);
595ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  } else {
596714efc63d4319b771d89a95aa7a42d400f03d8c9Dan Gohman    CurDAG->Legalize(OptLevel);
597ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  }
598a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
599bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner  DEBUG(errs() << "Legalized selection DAG:\n");
600f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  DEBUG(CurDAG->dump());
601a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
602f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName);
603462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman
604af21d55aee8d6852fedfd630395a3c7c95df8f12Chris Lattner  // Run the DAG combiner in post-legalize mode.
605ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  if (TimePassesIsEnabled) {
6065e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman    NamedRegionTimer T("DAG Combining 2", GroupName);
607be8cc2a3dedeb7685f07e68cdc4b9502eb97eb2bBill Wendling    CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
608ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  } else {
609be8cc2a3dedeb7685f07e68cdc4b9502eb97eb2bBill Wendling    CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
610ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  }
611a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
612bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner  DEBUG(errs() << "Optimized legalized selection DAG:\n");
613f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  DEBUG(CurDAG->dump());
614417e11b9bf625b3626f8765d44248927fb200906Dan Gohman
615f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName);
616a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
61798a366d547772010e94609e4584489b3e5ce0043Bill Wendling  if (OptLevel != CodeGenOpt::None)
618f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman    ComputeLiveOutVRegInfo();
619552c4a849422ad91fa9988255ae35aebbf3acf7bEvan Cheng
620a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner  // Third, instruction select all of the operations to machine code, adding the
621a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner  // code to the MachineBasicBlock.
622ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  if (TimePassesIsEnabled) {
6235e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman    NamedRegionTimer T("Instruction Selection", GroupName);
624f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman    InstructionSelect();
625ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  } else {
626f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman    InstructionSelect();
627ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  }
628db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng
629bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner  DEBUG(errs() << "Selected selection DAG:\n");
630f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  DEBUG(CurDAG->dump());
631462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman
632f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName);
633462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman
6345e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman  // Schedule machine code.
63547ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman  ScheduleDAGSDNodes *Scheduler = CreateScheduler();
6365e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman  if (TimePassesIsEnabled) {
6375e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman    NamedRegionTimer T("Instruction Scheduling", GroupName);
63847ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman    Scheduler->Run(CurDAG, BB, BB->end());
6395e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman  } else {
64047ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman    Scheduler->Run(CurDAG, BB, BB->end());
6415e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman  }
6425e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman
643462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman  if (ViewSUnitDAGs) Scheduler->viewGraph();
644462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman
645a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar  // Emit machine code to BB.  This can change 'BB' to the last block being
646db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng  // inserted into.
647ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  if (TimePassesIsEnabled) {
6485e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman    NamedRegionTimer T("Instruction Creation", GroupName);
6492048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    BB = Scheduler->EmitSchedule(&SDB->EdgeMapping);
650ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  } else {
6512048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    BB = Scheduler->EmitSchedule(&SDB->EdgeMapping);
6525e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman  }
6535e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman
6545e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman  // Free the scheduler state.
6555e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman  if (TimePassesIsEnabled) {
6565e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman    NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName);
6575e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman    delete Scheduler;
6585e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman  } else {
6595e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman    delete Scheduler;
660ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng  }
661db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng
662bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner  DEBUG(errs() << "Selected machine code:\n");
6631c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner  DEBUG(BB->dump());
664a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar}
665f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman
66679ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohmanvoid SelectionDAGISel::SelectAllBasicBlocks(Function &Fn,
66779ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman                                            MachineFunction &MF,
668dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman                                            MachineModuleInfo *MMI,
66983489bb7700c69b7a4a8da59365c42d3f5c8129bDevang Patel                                            DwarfWriter *DW,
670dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman                                            const TargetInstrInfo &TII) {
671a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman  // Initialize the Fast-ISel state, if needed.
672a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman  FastISel *FastIS = 0;
673a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman  if (EnableFastISel)
67479ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman    FastIS = TLI.createFastISel(MF, MMI, DW,
675a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman                                FuncInfo->ValueMap,
676a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman                                FuncInfo->MBBMap,
677dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman                                FuncInfo->StaticAllocaMap
678dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman#ifndef NDEBUG
679dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman                                , FuncInfo->CatchInfoLost
680dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman#endif
681dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman                                );
682a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman
683e30e678865b8dc1b69ef1c26e7567ffd1300553cDevang Patel  MetadataContext &TheMetadata = Fn.getContext().getMetadata();
684a2148402ce39fb3aad09e98a32078d3853a01ae9Devang Patel  unsigned MDDbgKind = TheMetadata.getMDKind("dbg");
685123eaa71b50f5ac2ea2233685baedddbb72f387bDevang Patel
686a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman  // Iterate over all basic blocks in the function.
68739fd6e81b1b0de8b820155dc6a0dae226c109de6Evan Cheng  for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
68839fd6e81b1b0de8b820155dc6a0dae226c109de6Evan Cheng    BasicBlock *LLVMBB = &*I;
6897c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman    BB = FuncInfo->MBBMap[LLVMBB];
690f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman
6913df24e667f04a7003342b534310919abc9c87418Dan Gohman    BasicBlock::iterator const Begin = LLVMBB->begin();
6923df24e667f04a7003342b534310919abc9c87418Dan Gohman    BasicBlock::iterator const End = LLVMBB->end();
6939f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng    BasicBlock::iterator BI = Begin;
6945edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman
6955edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman    // Lower any arguments needed in this block if this is the entry block.
69633134c4a75558288d663267c8991f6bd37a530afDan Gohman    bool SuppressFastISel = false;
69733134c4a75558288d663267c8991f6bd37a530afDan Gohman    if (LLVMBB == &Fn.getEntryBlock()) {
6985edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman      LowerArguments(LLVMBB);
699f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman
70033134c4a75558288d663267c8991f6bd37a530afDan Gohman      // If any of the arguments has the byval attribute, forgo
70133134c4a75558288d663267c8991f6bd37a530afDan Gohman      // fast-isel in the entry block.
702a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman      if (FastIS) {
70333134c4a75558288d663267c8991f6bd37a530afDan Gohman        unsigned j = 1;
70433134c4a75558288d663267c8991f6bd37a530afDan Gohman        for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end();
70533134c4a75558288d663267c8991f6bd37a530afDan Gohman             I != E; ++I, ++j)
7060598866c052147c31b808391f58434ce3dbfb838Devang Patel          if (Fn.paramHasAttr(j, Attribute::ByVal)) {
70777ca41e5c3f99ee8962b21a7d90bb251a594a65eDan Gohman            if (EnableFastISelVerbose || EnableFastISelAbort)
7084437ae213d5435390f0750213b53ec807c047f22Chris Lattner              errs() << "FastISel skips entry block due to byval argument\n";
70933134c4a75558288d663267c8991f6bd37a530afDan Gohman            SuppressFastISel = true;
71033134c4a75558288d663267c8991f6bd37a530afDan Gohman            break;
71133134c4a75558288d663267c8991f6bd37a530afDan Gohman          }
71233134c4a75558288d663267c8991f6bd37a530afDan Gohman      }
71333134c4a75558288d663267c8991f6bd37a530afDan Gohman    }
71433134c4a75558288d663267c8991f6bd37a530afDan Gohman
715dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman    if (MMI && BB->isLandingPad()) {
716dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // Add a label to mark the beginning of the landing pad.  Deletion of the
717dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // landing pad can thus be detected via the MachineModuleInfo.
718dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      unsigned LabelID = MMI->addLandingPad(BB);
719dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman
720dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      const TargetInstrDesc &II = TII.get(TargetInstrInfo::EH_LABEL);
7212048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      BuildMI(BB, SDB->getCurDebugLoc(), II).addImm(LabelID);
722dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman
723dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // Mark exception register as live in.
724dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      unsigned Reg = TLI.getExceptionAddressRegister();
725dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      if (Reg) BB->addLiveIn(Reg);
726dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman
727dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // Mark exception selector register as live in.
728dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      Reg = TLI.getExceptionSelectorRegister();
729dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      if (Reg) BB->addLiveIn(Reg);
730dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman
731dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // FIXME: Hack around an exception handling flaw (PR1508): the personality
732dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // function and list of typeids logically belong to the invoke (or, if you
733dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // like, the basic block containing the invoke), and need to be associated
734dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // with it in the dwarf exception handling tables.  Currently however the
735dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // information is provided by an intrinsic (eh.selector) that can be moved
736dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // to unexpected places by the optimizers: if the unwind edge is critical,
737dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // then breaking it can result in the intrinsics being in the successor of
738dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // the landing pad, not the landing pad itself.  This results in exceptions
739dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // not being caught because no typeids are associated with the invoke.
740dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // This may not be the only way things can go wrong, but it is the only way
741dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      // we try to work around for the moment.
742dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator());
743dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman
744dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      if (Br && Br->isUnconditional()) { // Critical edge?
745dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman        BasicBlock::iterator I, E;
746dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman        for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I)
747dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman          if (isa<EHSelectorInst>(I))
748dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman            break;
749dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman
750dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman        if (I == E)
751dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman          // No catch info found - try to extract some from the successor.
7525fca8b1c8dc0b9efb0a9822222a6505d1eea6bddDan Gohman          CopyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo);
753dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman      }
754dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman    }
755dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman
756f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman    // Before doing SelectionDAG ISel, see if FastISel has been requested.
757dd5b58ad7be78be90390074f0df138778af5c895Dan Gohman    if (FastIS && !SuppressFastISel) {
758a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman      // Emit code for any incoming arguments. This must happen before
759a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman      // beginning FastISel on the entry block.
760a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman      if (LLVMBB == &Fn.getEntryBlock()) {
7612048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        CurDAG->setRoot(SDB->getControlRoot());
762a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        CodeGenAndEmitDAG();
7632048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        SDB->clear();
764a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman      }
765241f464d24a6c22721607841069bbeb17b3f71e6Dan Gohman      FastIS->startNewBlock(BB);
766a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman      // Do FastISel on as many instructions as possible.
767a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman      for (; BI != End; ++BI) {
768a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        // Just before the terminator instruction, insert instructions to
769a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        // feed PHI nodes in successor blocks.
770a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        if (isa<TerminatorInst>(BI))
771a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman          if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, FastIS)) {
77207f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman            ResetDebugLoc(SDB, FastIS);
77377ca41e5c3f99ee8962b21a7d90bb251a594a65eDan Gohman            if (EnableFastISelVerbose || EnableFastISelAbort) {
7744437ae213d5435390f0750213b53ec807c047f22Chris Lattner              errs() << "FastISel miss: ";
77577ca41e5c3f99ee8962b21a7d90bb251a594a65eDan Gohman              BI->dump();
77677ca41e5c3f99ee8962b21a7d90bb251a594a65eDan Gohman            }
777a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar            assert(!EnableFastISelAbort &&
778f36892335b4919b9120e48a792e6b3630b9de978Torok Edwin                   "FastISel didn't handle a PHI in a successor");
779a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman            break;
780a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman          }
78133134c4a75558288d663267c8991f6bd37a530afDan Gohman
782381ca5572e3c37824e1c5be0fa02f7b5bdd4a1ceDan Gohman        if (MDDbgKind)
783381ca5572e3c37824e1c5be0fa02f7b5bdd4a1ceDan Gohman          SetDebugLoc(MDDbgKind, TheMetadata, BI, SDB, FastIS, &MF);
784381ca5572e3c37824e1c5be0fa02f7b5bdd4a1ceDan Gohman
785a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        // First try normal tablegen-generated "fast" selection.
78607f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman        if (FastIS->SelectInstruction(BI)) {
78707f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman          ResetDebugLoc(SDB, FastIS);
788a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman          continue;
78907f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman        }
790a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman
79107f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman        // Clear out the debug location so that it doesn't carry over to
79207f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman        // unrelated instructions.
79307f111e7b746747cade8371eeaf8c613058cb3a0Dan Gohman        ResetDebugLoc(SDB, FastIS);
794f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman
795a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        // Then handle certain instructions as single-LLVM-Instruction blocks.
796a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        if (isa<CallInst>(BI)) {
797a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman          if (EnableFastISelVerbose || EnableFastISelAbort) {
7984437ae213d5435390f0750213b53ec807c047f22Chris Lattner            errs() << "FastISel missed call: ";
799a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman            BI->dump();
800f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman          }
801f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman
8021d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson          if (BI->getType() != Type::getVoidTy(*CurDAG->getContext())) {
803a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman            unsigned &R = FuncInfo->ValueMap[BI];
804a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman            if (!R)
805a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman              R = FuncInfo->CreateRegForValue(BI);
806f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman          }
807a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman
808b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman          bool HadTailCall = false;
8097896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner          SelectBasicBlock(LLVMBB, BI, llvm::next(BI), HadTailCall);
810b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman
811b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman          // If the call was emitted as a tail call, we're done with the block.
812b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman          if (HadTailCall) {
813b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman            BI = End;
814b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman            break;
815b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman          }
816b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman
817241f464d24a6c22721607841069bbeb17b3f71e6Dan Gohman          // If the instruction was codegen'd with multiple blocks,
818241f464d24a6c22721607841069bbeb17b3f71e6Dan Gohman          // inform the FastISel object where to resume inserting.
819241f464d24a6c22721607841069bbeb17b3f71e6Dan Gohman          FastIS->setCurrentBlock(BB);
820a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman          continue;
821f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman        }
822a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman
823a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        // Otherwise, give up on FastISel for the rest of the block.
824a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        // For now, be a little lenient about non-branch terminators.
825a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        if (!isa<TerminatorInst>(BI) || isa<BranchInst>(BI)) {
826a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman          if (EnableFastISelVerbose || EnableFastISelAbort) {
8274437ae213d5435390f0750213b53ec807c047f22Chris Lattner            errs() << "FastISel miss: ";
828a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman            BI->dump();
829a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman          }
830a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman          if (EnableFastISelAbort)
831a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman            // The "fast" selector couldn't handle something and bailed.
832a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman            // For the purpose of debugging, just abort.
833c23197a26f34f559ea9797de51e187087c039c42Torok Edwin            llvm_unreachable("FastISel didn't select the entire block");
834a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        }
835a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman        break;
836f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman      }
837f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman    }
838f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman
839d2ff647964ed242e67ac12f7d21a58c864309d95Dan Gohman    // Run SelectionDAG instruction selection on the remainder of the block
840d2ff647964ed242e67ac12f7d21a58c864309d95Dan Gohman    // not handled by FastISel. If FastISel is not run, this is the entire
8413df24e667f04a7003342b534310919abc9c87418Dan Gohman    // block.
842390f3ace34855a3d4c9e0adf468976375f8c6dc1Devang Patel    if (BI != End) {
843b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman      bool HadTailCall;
844b4afb137efbc38462707bab9f5e8bc5c2d07cd2dDan Gohman      SelectBasicBlock(LLVMBB, BI, End, HadTailCall);
845390f3ace34855a3d4c9e0adf468976375f8c6dc1Devang Patel    }
846381cb07544a2bc119e39969d7d508a6247773e1cEvan Cheng
8477c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman    FinishBasicBlock();
84839fd6e81b1b0de8b820155dc6a0dae226c109de6Evan Cheng  }
849a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman
850a43abd102f123f6d3bd9ad92045f8119e3fb6153Dan Gohman  delete FastIS;
8510e5f1306b059b62d7725f324e087efbc8e7a782dDan Gohman}
8520e5f1306b059b62d7725f324e087efbc8e7a782dDan Gohman
853fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanvoid
8547c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan GohmanSelectionDAGISel::FinishBasicBlock() {
8551c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner
856bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner  DEBUG(errs() << "Target-post-processed machine code:\n");
857f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman  DEBUG(BB->dump());
8584198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov
859bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner  DEBUG(errs() << "Total amount of phi nodes to update: "
8602048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman               << SDB->PHINodesToUpdate.size() << "\n");
8612048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  DEBUG(for (unsigned i = 0, e = SDB->PHINodesToUpdate.size(); i != e; ++i)
862bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner          errs() << "Node " << i << " : ("
8632048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman                 << SDB->PHINodesToUpdate[i].first
8642048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman                 << ", " << SDB->PHINodesToUpdate[i].second << ")\n");
865a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
866a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner  // Next, now that we know what the last MBB the LLVM BB expanded is, update
8671c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner  // PHI nodes in successors.
8682048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  if (SDB->SwitchCases.empty() &&
8692048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->JTCases.empty() &&
8702048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->BitTestCases.empty()) {
8712048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    for (unsigned i = 0, e = SDB->PHINodesToUpdate.size(); i != e; ++i) {
8722048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      MachineInstr *PHI = SDB->PHINodesToUpdate[i].first;
873f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman      assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
874f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman             "This is not a machine PHI node that we are updating!");
8752048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      PHI->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[i].second,
8769ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner                                                false));
8779ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner      PHI->addOperand(MachineOperand::CreateMBB(BB));
878f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman    }
8792048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    SDB->PHINodesToUpdate.clear();
880f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman    return;
8811c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner  }
8824198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov
8832048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  for (unsigned i = 0, e = SDB->BitTestCases.size(); i != e; ++i) {
8844198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov    // Lower header first, if it wasn't already lowered
8852048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    if (!SDB->BitTestCases[i].Emitted) {
8864198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      // Set the current basic block to the mbb we wish to insert the code into
8872048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      BB = SDB->BitTestCases[i].Parent;
8882048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->setCurrentBasicBlock(BB);
8894198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      // Emit the code
8902048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->visitBitTestHeader(SDB->BitTestCases[i]);
8912048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      CurDAG->setRoot(SDB->getRoot());
892f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman      CodeGenAndEmitDAG();
8932048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->clear();
894a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar    }
8954198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov
8962048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) {
8974198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      // Set the current basic block to the mbb we wish to insert the code into
8982048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      BB = SDB->BitTestCases[i].Cases[j].ThisBB;
8992048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->setCurrentBasicBlock(BB);
9004198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      // Emit the code
9014198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      if (j+1 != ej)
9022048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        SDB->visitBitTestCase(SDB->BitTestCases[i].Cases[j+1].ThisBB,
9032048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman                              SDB->BitTestCases[i].Reg,
9042048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman                              SDB->BitTestCases[i].Cases[j]);
9054198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      else
9062048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        SDB->visitBitTestCase(SDB->BitTestCases[i].Default,
9072048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman                              SDB->BitTestCases[i].Reg,
9082048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman                              SDB->BitTestCases[i].Cases[j]);
909a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
910a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
9112048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      CurDAG->setRoot(SDB->getRoot());
912f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman      CodeGenAndEmitDAG();
9132048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->clear();
9144198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov    }
9154198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov
9164198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov    // Update PHI Nodes
9172048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    for (unsigned pi = 0, pe = SDB->PHINodesToUpdate.size(); pi != pe; ++pi) {
9182048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      MachineInstr *PHI = SDB->PHINodesToUpdate[pi].first;
9194198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      MachineBasicBlock *PHIBB = PHI->getParent();
9204198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
9214198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov             "This is not a machine PHI node that we are updating!");
9224198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      // This is "default" BB. We have two jumps to it. From "header" BB and
9234198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      // from last "case" BB.
9242048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      if (PHIBB == SDB->BitTestCases[i].Default) {
9252048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        PHI->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[pi].second,
9269ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner                                                  false));
9272048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        PHI->addOperand(MachineOperand::CreateMBB(SDB->BitTestCases[i].Parent));
9282048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        PHI->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[pi].second,
9299ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner                                                  false));
9302048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        PHI->addOperand(MachineOperand::CreateMBB(SDB->BitTestCases[i].Cases.
9319ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner                                                  back().ThisBB));
9324198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      }
9334198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      // One of "cases" BB.
9342048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size();
9357c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman           j != ej; ++j) {
9362048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        MachineBasicBlock* cBB = SDB->BitTestCases[i].Cases[j].ThisBB;
9374198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov        if (cBB->succ_end() !=
9384198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov            std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) {
9392048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman          PHI->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[pi].second,
9409ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner                                                    false));
9419ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner          PHI->addOperand(MachineOperand::CreateMBB(cBB));
9424198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov        }
9434198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      }
9444198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov    }
9454198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov  }
9462048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  SDB->BitTestCases.clear();
9474198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov
9489453eea49bca1c3904047db495855c93e001d1cdNate Begeman  // If the JumpTable record is filled in, then we need to emit a jump table.
9499453eea49bca1c3904047db495855c93e001d1cdNate Begeman  // Updating the PHI nodes is tricky in this case, since we need to determine
9509453eea49bca1c3904047db495855c93e001d1cdNate Begeman  // whether the PHI is a successor of the range check MBB or the jump table MBB
9512048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  for (unsigned i = 0, e = SDB->JTCases.size(); i != e; ++i) {
9523a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov    // Lower header first, if it wasn't already lowered
9532048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    if (!SDB->JTCases[i].first.Emitted) {
9543a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov      // Set the current basic block to the mbb we wish to insert the code into
9552048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      BB = SDB->JTCases[i].first.HeaderBB;
9562048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->setCurrentBasicBlock(BB);
9573a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov      // Emit the code
9582048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first);
9592048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      CurDAG->setRoot(SDB->getRoot());
960f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman      CodeGenAndEmitDAG();
9612048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->clear();
9624198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov    }
963a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
96437efe6764568a3829fee26aba532283131d1a104Nate Begeman    // Set the current basic block to the mbb we wish to insert the code into
9652048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    BB = SDB->JTCases[i].second.MBB;
9662048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    SDB->setCurrentBasicBlock(BB);
96737efe6764568a3829fee26aba532283131d1a104Nate Begeman    // Emit the code
9682048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    SDB->visitJumpTable(SDB->JTCases[i].second);
9692048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    CurDAG->setRoot(SDB->getRoot());
970f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman    CodeGenAndEmitDAG();
9712048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    SDB->clear();
972a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
97337efe6764568a3829fee26aba532283131d1a104Nate Begeman    // Update PHI Nodes
9742048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    for (unsigned pi = 0, pe = SDB->PHINodesToUpdate.size(); pi != pe; ++pi) {
9752048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      MachineInstr *PHI = SDB->PHINodesToUpdate[pi].first;
97637efe6764568a3829fee26aba532283131d1a104Nate Begeman      MachineBasicBlock *PHIBB = PHI->getParent();
97737efe6764568a3829fee26aba532283131d1a104Nate Begeman      assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
97837efe6764568a3829fee26aba532283131d1a104Nate Begeman             "This is not a machine PHI node that we are updating!");
9794198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      // "default" BB. We can go there only from header BB.
9802048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      if (PHIBB == SDB->JTCases[i].second.Default) {
981ce31910eae5bd4896fa6c27798e7b26885691d3bEvan Cheng        PHI->addOperand
9822048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman          (MachineOperand::CreateReg(SDB->PHINodesToUpdate[pi].second, false));
983ce31910eae5bd4896fa6c27798e7b26885691d3bEvan Cheng        PHI->addOperand
9842048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman          (MachineOperand::CreateMBB(SDB->JTCases[i].first.HeaderBB));
985f4360a478944af45d5f851a0903fbbfa44f520dcNate Begeman      }
9864198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov      // JT BB. Just iterate over successors here
987f4360a478944af45d5f851a0903fbbfa44f520dcNate Begeman      if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
988ce31910eae5bd4896fa6c27798e7b26885691d3bEvan Cheng        PHI->addOperand
9892048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman          (MachineOperand::CreateReg(SDB->PHINodesToUpdate[pi].second, false));
9909ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner        PHI->addOperand(MachineOperand::CreateMBB(BB));
99137efe6764568a3829fee26aba532283131d1a104Nate Begeman      }
99237efe6764568a3829fee26aba532283131d1a104Nate Begeman    }
99337efe6764568a3829fee26aba532283131d1a104Nate Begeman  }
9942048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  SDB->JTCases.clear();
995a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
996b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner  // If the switch block involved a branch to one of the actual successors, we
997b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner  // need to update PHI nodes in that block.
9982048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  for (unsigned i = 0, e = SDB->PHINodesToUpdate.size(); i != e; ++i) {
9992048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    MachineInstr *PHI = SDB->PHINodesToUpdate[i].first;
1000b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner    assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
1001b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner           "This is not a machine PHI node that we are updating!");
1002b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner    if (BB->isSuccessor(PHI->getParent())) {
10032048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      PHI->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[i].second,
10049ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner                                                false));
10059ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner      PHI->addOperand(MachineOperand::CreateMBB(BB));
1006b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner    }
1007b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner  }
1008a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1009f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman  // If we generated any switch lowering information, build and codegen any
1010f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman  // additional DAGs necessary.
10112048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) {
1012f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman    // Set the current basic block to the mbb we wish to insert the code into
10132048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    MachineBasicBlock *ThisBB = BB = SDB->SwitchCases[i].ThisBB;
10142048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    SDB->setCurrentBasicBlock(BB);
1015a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1016f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman    // Emit the code
10172048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    SDB->visitSwitchCase(SDB->SwitchCases[i]);
10182048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    CurDAG->setRoot(SDB->getRoot());
1019f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman    CodeGenAndEmitDAG();
1020a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1021d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner    // Handle any PHI nodes in successors of this chunk, as if we were coming
1022d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner    // from the original BB before switch expansion.  Note that PHI nodes can
1023d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner    // occur multiple times in PHINodesToUpdate.  We have to be very careful to
1024d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner    // handle them the right number of times.
10252048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    while ((BB = SDB->SwitchCases[i].TrueBB)) {  // Handle LHS and RHS.
1026fb2e752e4175920d0531f2afc93a23d0cdf4db14Evan Cheng      // If new BB's are created during scheduling, the edges may have been
1027ce31910eae5bd4896fa6c27798e7b26885691d3bEvan Cheng      // updated. That is, the edge from ThisBB to BB may have been split and
1028ce31910eae5bd4896fa6c27798e7b26885691d3bEvan Cheng      // BB's predecessor is now another block.
1029fb2e752e4175920d0531f2afc93a23d0cdf4db14Evan Cheng      DenseMap<MachineBasicBlock*, MachineBasicBlock*>::iterator EI =
10302048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        SDB->EdgeMapping.find(BB);
10312048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      if (EI != SDB->EdgeMapping.end())
1032fb2e752e4175920d0531f2afc93a23d0cdf4db14Evan Cheng        ThisBB = EI->second;
1033d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner      for (MachineBasicBlock::iterator Phi = BB->begin();
1034d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner           Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){
1035d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner        // This value for this PHI node is recorded in PHINodesToUpdate, get it.
1036d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner        for (unsigned pn = 0; ; ++pn) {
10372048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman          assert(pn != SDB->PHINodesToUpdate.size() &&
10387c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman                 "Didn't find PHI entry!");
10392048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman          if (SDB->PHINodesToUpdate[pn].first == Phi) {
10402048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman            Phi->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[pn].
10418be58a11868ae081c195c107cd39a07f1f523877Evan Cheng                                                      second, false));
1042fb2e752e4175920d0531f2afc93a23d0cdf4db14Evan Cheng            Phi->addOperand(MachineOperand::CreateMBB(ThisBB));
1043d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner            break;
10448be58a11868ae081c195c107cd39a07f1f523877Evan Cheng          }
1045d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner        }
1046f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman      }
1047a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1048d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner      // Don't process RHS if same block as LHS.
10492048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      if (BB == SDB->SwitchCases[i].FalseBB)
10502048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman        SDB->SwitchCases[i].FalseBB = 0;
1051a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1052d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner      // If we haven't handled the RHS, do so now.  Otherwise, we're done.
10532048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->SwitchCases[i].TrueBB = SDB->SwitchCases[i].FalseBB;
10542048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman      SDB->SwitchCases[i].FalseBB = 0;
1055f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman    }
10562048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    assert(SDB->SwitchCases[i].TrueBB == 0 && SDB->SwitchCases[i].FalseBB == 0);
10572048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman    SDB->clear();
1058a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner  }
10592048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  SDB->SwitchCases.clear();
10607c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman
10612048b85c7c2c987874b9423e682ec8e60b60574bDan Gohman  SDB->PHINodesToUpdate.clear();
10621c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner}
1063a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng
106413ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey
10650a3776dc6f702d4e3f4a189df7f43d8f99957773Dan Gohman/// Create the scheduler. If a specific scheduler was specified
10660a3776dc6f702d4e3f4a189df7f43d8f99957773Dan Gohman/// via the SchedulerRegistry, use it, otherwise select the
10670a3776dc6f702d4e3f4a189df7f43d8f99957773Dan Gohman/// one preferred by the target.
10685e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman///
106947ac0f0c7c39289f5970688154e385be22b7f293Dan GohmanScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
1070eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey  RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
1071a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
107213ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey  if (!Ctor) {
1073eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey    Ctor = ISHeuristic;
10749373beba6010dd34316a801c3a9b37ab9e048031Jim Laskey    RegisterScheduler::setDefault(Ctor);
10754ef10867499aa146cd819c78d8d37a8353d4f0ffEvan Cheng  }
1076a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1077be8cc2a3dedeb7685f07e68cdc4b9502eb97eb2bBill Wendling  return Ctor(this, OptLevel);
1078a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng}
10790e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner
1080fc54c552963545a81e4ea38e60460590afb2d5aeDan GohmanScheduleHazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
1081fc54c552963545a81e4ea38e60460590afb2d5aeDan Gohman  return new ScheduleHazardRecognizer();
10829ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey}
10839ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey
1084755480681c795d585c73556c028b6143c46bda86Chris Lattner//===----------------------------------------------------------------------===//
1085755480681c795d585c73556c028b6143c46bda86Chris Lattner// Helper functions used by the generated instruction selector.
1086755480681c795d585c73556c028b6143c46bda86Chris Lattner//===----------------------------------------------------------------------===//
1087755480681c795d585c73556c028b6143c46bda86Chris Lattner// Calls to these methods are generated by tblgen.
1088755480681c795d585c73556c028b6143c46bda86Chris Lattner
1089755480681c795d585c73556c028b6143c46bda86Chris Lattner/// CheckAndMask - The isel is trying to match something like (and X, 255).  If
1090755480681c795d585c73556c028b6143c46bda86Chris Lattner/// the dag combiner simplified the 255, we still want to match.  RHS is the
1091755480681c795d585c73556c028b6143c46bda86Chris Lattner/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
1092755480681c795d585c73556c028b6143c46bda86Chris Lattner/// specified in the .td file (e.g. 255).
1093a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbarbool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
1094dc9b3d0bb5ed3a3f59cad61e264f0ec43c946459Dan Gohman                                    int64_t DesiredMaskS) const {
10952e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman  const APInt &ActualMask = RHS->getAPIntValue();
10962e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman  const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
1097a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1098755480681c795d585c73556c028b6143c46bda86Chris Lattner  // If the actual mask exactly matches, success!
1099755480681c795d585c73556c028b6143c46bda86Chris Lattner  if (ActualMask == DesiredMask)
1100755480681c795d585c73556c028b6143c46bda86Chris Lattner    return true;
1101a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1102755480681c795d585c73556c028b6143c46bda86Chris Lattner  // If the actual AND mask is allowing unallowed bits, this doesn't match.
11032e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman  if (ActualMask.intersects(~DesiredMask))
1104755480681c795d585c73556c028b6143c46bda86Chris Lattner    return false;
1105a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1106755480681c795d585c73556c028b6143c46bda86Chris Lattner  // Otherwise, the DAG Combiner may have proven that the value coming in is
1107755480681c795d585c73556c028b6143c46bda86Chris Lattner  // either already zero or is not demanded.  Check for known zero input bits.
11082e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman  APInt NeededMask = DesiredMask & ~ActualMask;
1109ea859be53ca13a1547c4675549946b74dc3c6f41Dan Gohman  if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
1110755480681c795d585c73556c028b6143c46bda86Chris Lattner    return true;
1111a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1112755480681c795d585c73556c028b6143c46bda86Chris Lattner  // TODO: check to see if missing bits are just not demanded.
1113755480681c795d585c73556c028b6143c46bda86Chris Lattner
1114755480681c795d585c73556c028b6143c46bda86Chris Lattner  // Otherwise, this pattern doesn't match.
1115755480681c795d585c73556c028b6143c46bda86Chris Lattner  return false;
1116755480681c795d585c73556c028b6143c46bda86Chris Lattner}
1117755480681c795d585c73556c028b6143c46bda86Chris Lattner
1118755480681c795d585c73556c028b6143c46bda86Chris Lattner/// CheckOrMask - The isel is trying to match something like (or X, 255).  If
1119755480681c795d585c73556c028b6143c46bda86Chris Lattner/// the dag combiner simplified the 255, we still want to match.  RHS is the
1120755480681c795d585c73556c028b6143c46bda86Chris Lattner/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
1121755480681c795d585c73556c028b6143c46bda86Chris Lattner/// specified in the .td file (e.g. 255).
1122a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbarbool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
11232e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman                                   int64_t DesiredMaskS) const {
11242e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman  const APInt &ActualMask = RHS->getAPIntValue();
11252e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman  const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
1126a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1127755480681c795d585c73556c028b6143c46bda86Chris Lattner  // If the actual mask exactly matches, success!
1128755480681c795d585c73556c028b6143c46bda86Chris Lattner  if (ActualMask == DesiredMask)
1129755480681c795d585c73556c028b6143c46bda86Chris Lattner    return true;
1130a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1131755480681c795d585c73556c028b6143c46bda86Chris Lattner  // If the actual AND mask is allowing unallowed bits, this doesn't match.
11322e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman  if (ActualMask.intersects(~DesiredMask))
1133755480681c795d585c73556c028b6143c46bda86Chris Lattner    return false;
1134a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1135755480681c795d585c73556c028b6143c46bda86Chris Lattner  // Otherwise, the DAG Combiner may have proven that the value coming in is
1136755480681c795d585c73556c028b6143c46bda86Chris Lattner  // either already zero or is not demanded.  Check for known zero input bits.
11372e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman  APInt NeededMask = DesiredMask & ~ActualMask;
1138a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
11392e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman  APInt KnownZero, KnownOne;
1140ea859be53ca13a1547c4675549946b74dc3c6f41Dan Gohman  CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
1141a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1142755480681c795d585c73556c028b6143c46bda86Chris Lattner  // If all the missing bits in the or are already known to be set, match!
1143755480681c795d585c73556c028b6143c46bda86Chris Lattner  if ((NeededMask & KnownOne) == NeededMask)
1144755480681c795d585c73556c028b6143c46bda86Chris Lattner    return true;
1145a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1146755480681c795d585c73556c028b6143c46bda86Chris Lattner  // TODO: check to see if missing bits are just not demanded.
1147a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
1148755480681c795d585c73556c028b6143c46bda86Chris Lattner  // Otherwise, this pattern doesn't match.
1149755480681c795d585c73556c028b6143c46bda86Chris Lattner  return false;
1150755480681c795d585c73556c028b6143c46bda86Chris Lattner}
1151755480681c795d585c73556c028b6143c46bda86Chris Lattner
11529ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey
11530e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
11540e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner/// by tblgen.  Others should not call it.
11550e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattnervoid SelectionDAGISel::
1156f350b277f32d7d47f86c0e54f4aec4d470500618Dan GohmanSelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) {
1157475871a144eb604ddaf37503397ba0941442e5fbDan Gohman  std::vector<SDValue> InOps;
11580e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner  std::swap(InOps, Ops);
11590e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner
11600e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner  Ops.push_back(InOps[0]);  // input chain.
11610e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner  Ops.push_back(InOps[1]);  // input asm string.
11620e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner
11630e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner  unsigned i = 2, e = InOps.size();
1164825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson  if (InOps[e-1].getValueType() == MVT::Flag)
11650e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner    --e;  // Don't process a flag operand if it is here.
1166a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
11670e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner  while (i != e) {
1168f5aeb1a8e4cf272c7348376d185ef8d8267653e0Dan Gohman    unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
116986b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen    if ((Flags & 7) != 4 /*MEM*/) {
11700e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner      // Just skip over this operand, copying the operands verbatim.
1171697cbbfb00c318f98d6eb51945f077e2bfe8781eEvan Cheng      Ops.insert(Ops.end(), InOps.begin()+i,
1172697cbbfb00c318f98d6eb51945f077e2bfe8781eEvan Cheng                 InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1);
1173697cbbfb00c318f98d6eb51945f077e2bfe8781eEvan Cheng      i += InlineAsm::getNumOperandRegisters(Flags) + 1;
11740e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner    } else {
1175697cbbfb00c318f98d6eb51945f077e2bfe8781eEvan Cheng      assert(InlineAsm::getNumOperandRegisters(Flags) == 1 &&
1176697cbbfb00c318f98d6eb51945f077e2bfe8781eEvan Cheng             "Memory operand with multiple values?");
11770e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner      // Otherwise, this is a memory operand.  Ask the target to select it.
1178475871a144eb604ddaf37503397ba0941442e5fbDan Gohman      std::vector<SDValue> SelOps;
1179f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman      if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) {
11807d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin        llvm_report_error("Could not match memory address.  Inline asm"
11817d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin                          " failure!");
11820e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner      }
1183a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
11840e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner      // Add this to the output node.
118586b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen      Ops.push_back(CurDAG->getTargetConstant(4/*MEM*/ | (SelOps.size()<< 3),
11869949933d6eb406bc74f7df7a0180a11c050a236fDale Johannesen                                              MVT::i32));
11870e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner      Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
11880e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner      i += 2;
11890e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner    }
11900e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner  }
1191a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar
11920e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner  // Add the flag input back if present.
11930e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner  if (e != InOps.size())
11940e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner    Ops.push_back(InOps.back());
11950e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner}
1196794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel
1197e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson/// findFlagUse - Return use of EVT::Flag value produced by the specified
1198c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// SDNode.
1199c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov///
1200c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikovstatic SDNode *findFlagUse(SDNode *N) {
1201c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  unsigned FlagResNo = N->getNumValues()-1;
1202c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
1203c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    SDUse &Use = I.getUse();
1204c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    if (Use.getResNo() == FlagResNo)
1205c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov      return Use.getUser();
1206c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  }
1207c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  return NULL;
1208c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov}
1209c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov
1210c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// findNonImmUse - Return true if "Use" is a non-immediate use of "Def".
1211c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// This function recursively traverses up the operand chain, ignoring
1212c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// certain nodes.
1213c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikovstatic bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
1214c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov                          SDNode *Root,
1215c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov                          SmallPtrSet<SDNode*, 16> &Visited) {
1216c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  if (Use->getNodeId() < Def->getNodeId() ||
1217c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov      !Visited.insert(Use))
1218c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    return false;
1219c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov
1220c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {
1221c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    SDNode *N = Use->getOperand(i).getNode();
1222c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    if (N == Def) {
1223c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov      if (Use == ImmedUse || Use == Root)
1224c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov        continue;  // We are not looking for immediate use.
1225c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov      assert(N != Root);
1226c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov      return true;
1227c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    }
1228c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov
1229c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    // Traverse up the operand chain.
1230c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    if (findNonImmUse(N, Def, ImmedUse, Root, Visited))
1231c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov      return true;
1232c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  }
1233c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  return false;
1234c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov}
1235c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov
1236c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// isNonImmUse - Start searching from Root up the DAG to check is Def can
1237c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// be reached. Return true if that's the case. However, ignore direct uses
1238c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// by ImmedUse (which would be U in the example illustrated in
1239c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// IsLegalAndProfitableToFold) and by Root (which can happen in the store
1240c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// case).
1241c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// FIXME: to be really generic, we should allow direct use by any node
1242c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// that is being folded. But realisticly since we only fold loads which
1243c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// have one non-chain use, we only need to watch out for load/op/store
1244c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// and load/op/cmp case where the root (store / cmp) may reach the load via
1245c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// its chain operand.
1246c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikovstatic inline bool isNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse) {
1247c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  SmallPtrSet<SDNode*, 16> Visited;
1248c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  return findNonImmUse(Root, Def, ImmedUse, Root, Visited);
1249c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov}
1250c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov
1251c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// IsLegalAndProfitableToFold - Returns true if the specific operand node N of
1252c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// U can be folded during instruction selection that starts at Root and
1253c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov/// folding N is profitable.
1254c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikovbool SelectionDAGISel::IsLegalAndProfitableToFold(SDNode *N, SDNode *U,
1255c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov                                                  SDNode *Root) const {
1256c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  if (OptLevel == CodeGenOpt::None) return false;
1257c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov
1258c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // If Root use can somehow reach N through a path that that doesn't contain
1259c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // U then folding N would create a cycle. e.g. In the following
1260c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // diagram, Root can reach N through X. If N is folded into into Root, then
1261c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // X is both a predecessor and a successor of U.
1262c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //
1263c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //          [N*]           //
1264c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //         ^   ^           //
1265c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //        /     \          //
1266c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //      [U*]    [X]?       //
1267c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //        ^     ^          //
1268c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //         \   /           //
1269c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //          \ /            //
1270c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //         [Root*]         //
1271c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //
1272c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // * indicates nodes to be folded together.
1273c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //
1274c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // If Root produces a flag, then it gets (even more) interesting. Since it
1275c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // will be "glued" together with its flag use in the scheduler, we need to
1276c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // check if it might reach N.
1277c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //
1278c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //          [N*]           //
1279c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //         ^   ^           //
1280c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //        /     \          //
1281c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //      [U*]    [X]?       //
1282c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //        ^       ^        //
1283c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //         \       \       //
1284c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //          \      |       //
1285c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //         [Root*] |       //
1286c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //          ^      |       //
1287c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //          f      |       //
1288c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //          |      /       //
1289c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //         [Y]    /        //
1290c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //           ^   /         //
1291c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //           f  /          //
1292c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //           | /           //
1293c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //          [FU]           //
1294c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  //
1295c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // If FU (flag use) indirectly reaches N (the load), and Root folds N
1296c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // (call it Fold), then X is a predecessor of FU and a successor of
1297c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // Fold. But since Fold and FU are flagged together, this will create
1298c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  // a cycle in the scheduling graph.
1299c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov
1300e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson  EVT VT = Root->getValueType(Root->getNumValues()-1);
1301825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson  while (VT == MVT::Flag) {
1302c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    SDNode *FU = findFlagUse(Root);
1303c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    if (FU == NULL)
1304c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov      break;
1305c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    Root = FU;
1306c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov    VT = Root->getValueType(Root->getNumValues()-1);
1307c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  }
1308c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov
1309c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov  return !isNonImmUse(Root, N, U);
1310c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov}
1311c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov
1312e1f188fe27050ec812e5b64cc996e6bb93300392Dan GohmanSDNode *SelectionDAGISel::Select_INLINEASM(SDValue N) {
1313e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  std::vector<SDValue> Ops(N.getNode()->op_begin(), N.getNode()->op_end());
1314e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  SelectInlineAsmMemoryOperands(Ops);
1315e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman
1316e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  std::vector<EVT> VTs;
1317e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  VTs.push_back(MVT::Other);
1318e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  VTs.push_back(MVT::Flag);
1319e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  SDValue New = CurDAG->getNode(ISD::INLINEASM, N.getDebugLoc(),
1320e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman                                VTs, &Ops[0], Ops.size());
1321e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  return New.getNode();
1322e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman}
1323e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman
1324e1f188fe27050ec812e5b64cc996e6bb93300392Dan GohmanSDNode *SelectionDAGISel::Select_UNDEF(const SDValue &N) {
1325e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  return CurDAG->SelectNodeTo(N.getNode(), TargetInstrInfo::IMPLICIT_DEF,
1326e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman                              N.getValueType());
1327e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman}
1328e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman
1329e1f188fe27050ec812e5b64cc996e6bb93300392Dan GohmanSDNode *SelectionDAGISel::Select_EH_LABEL(const SDValue &N) {
1330e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  SDValue Chain = N.getOperand(0);
1331e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  unsigned C = cast<LabelSDNode>(N)->getLabelID();
1332e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  SDValue Tmp = CurDAG->getTargetConstant(C, MVT::i32);
1333e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  return CurDAG->SelectNodeTo(N.getNode(), TargetInstrInfo::EH_LABEL,
1334e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman                              MVT::Other, Tmp, Chain);
1335e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman}
1336e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman
1337e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohmanvoid SelectionDAGISel::CannotYetSelect(SDValue N) {
1338e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  std::string msg;
1339e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  raw_string_ostream Msg(msg);
1340e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  Msg << "Cannot yet select: ";
1341e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  N.getNode()->print(Msg, CurDAG);
1342e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  llvm_report_error(Msg.str());
1343e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman}
1344e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman
1345e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohmanvoid SelectionDAGISel::CannotYetSelectIntrinsic(SDValue N) {
1346e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  errs() << "Cannot yet select: ";
1347e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  unsigned iid =
1348e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman    cast<ConstantSDNode>(N.getOperand(N.getOperand(0).getValueType() == MVT::Other))->getZExtValue();
1349e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  if (iid < Intrinsic::num_intrinsics)
1350e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman    llvm_report_error("Cannot yet select: intrinsic %" + Intrinsic::getName((Intrinsic::ID)iid));
1351e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman  else if (const TargetIntrinsicInfo *tii = TM.getIntrinsicInfo())
1352e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman    llvm_report_error(Twine("Cannot yet select: target intrinsic %") +
1353e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman                      tii->getName(iid));
1354e1f188fe27050ec812e5b64cc996e6bb93300392Dan Gohman}
1355c1c6ef8f74fc550f29cfec1f2fb699dd8c2fb94eAnton Korobeynikov
13561997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar SelectionDAGISel::ID = 0;
1357