SelectionDAGISel.cpp revision 77ca41e5c3f99ee8962b21a7d90bb251a594a65e
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" 15381cb07544a2bc119e39969d7d508a6247773e1cEvan Cheng#include "llvm/CodeGen/SelectionDAGISel.h" 16f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman#include "SelectionDAGBuild.h" 175502bf67cd49221583c15472150905ce13184d36Anton Korobeynikov#include "llvm/ADT/BitVector.h" 18c7c3f110eda0ff8040e4bd99e38d3112b910810fJim Laskey#include "llvm/Analysis/AliasAnalysis.h" 195502bf67cd49221583c15472150905ce13184d36Anton Korobeynikov#include "llvm/Constants.h" 20adf6a965a321372c640845407195594835921eb4Chris Lattner#include "llvm/CallingConv.h" 211c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/DerivedTypes.h" 221c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Function.h" 2336ce69195ed488034d0bb11180cc2ebd923679c8Chris Lattner#include "llvm/GlobalVariable.h" 24ce7518ce92f45568dc7d4cbb863284afb962fec5Chris Lattner#include "llvm/InlineAsm.h" 251c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Instructions.h" 261c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Intrinsics.h" 2743970fec322d9e0153ca513de41d80af1c79bddeJim Laskey#include "llvm/IntrinsicInst.h" 2878eca170e9ac5db7fd525f9bbf27090fefcbb646Dan Gohman#include "llvm/CodeGen/FastISel.h" 295a29c9eed157af51a8d338b5a225b146881819e8Gordon Henriksen#include "llvm/CodeGen/GCStrategy.h" 305eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen#include "llvm/CodeGen/GCMetadata.h" 311c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/MachineFunction.h" 321c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/MachineFrameInfo.h" 331c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/MachineInstrBuilder.h" 3484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineJumpTableInfo.h" 3584bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineModuleInfo.h" 3684bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 37381cb07544a2bc119e39969d7d508a6247773e1cEvan Cheng#include "llvm/CodeGen/ScheduleDAG.h" 38eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey#include "llvm/CodeGen/SchedulerRegistry.h" 391c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/SelectionDAG.h" 406f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 411c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetData.h" 421c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetFrameInfo.h" 431c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetInstrInfo.h" 441c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetLowering.h" 451c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetMachine.h" 46124729155d860a0850eb4ef2a7cea4145e13a057Vladimir Prus#include "llvm/Target/TargetOptions.h" 47a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 48db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng#include "llvm/Support/Debug.h" 49db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng#include "llvm/Support/MathExtras.h" 50db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng#include "llvm/Support/Timer.h" 517e88103cdea8c36b2229dae8c60def14e3816512Jeff Cohen#include <algorithm> 521c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattnerusing namespace llvm; 531c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 54ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattnerstatic cl::opt<bool> 5570587ea813986bb0dbef71610091d496e28c22a6Chris LattnerEnableValueProp("enable-value-prop", cl::Hidden); 5670587ea813986bb0dbef71610091d496e28c22a6Chris Lattnerstatic cl::opt<bool> 57f00e74f4d64385e6b2ee29887114e7c8abdf1f17Duncan SandsEnableLegalizeTypes("enable-legalize-types", cl::Hidden); 5878eca170e9ac5db7fd525f9bbf27090fefcbb646Dan Gohmanstatic cl::opt<bool> 59293d5f8bc02a9148238b2c79484637f56de65b9cDan GohmanEnableFastISelVerbose("fast-isel-verbose", cl::Hidden, 60293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman cl::desc("Enable verbose messages in the experimental \"fast\" " 61293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman "instruction selector")); 62293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohmanstatic cl::opt<bool> 634344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan GohmanEnableFastISelAbort("fast-isel-abort", cl::Hidden, 644344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman cl::desc("Enable abort calls when \"fast\" instruction fails")); 658a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohmanstatic cl::opt<bool> 668a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan GohmanSchedLiveInCopies("schedule-livein-copies", 678a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman cl::desc("Schedule copies of livein registers"), 688a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman cl::init(false)); 69ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 70da8abb02397d7cd62a1e16e7c534edd7096ac873Chris Lattner#ifndef NDEBUG 717944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattnerstatic cl::opt<bool> 72462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewDAGCombine1("view-dag-combine1-dags", cl::Hidden, 73462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman cl::desc("Pop up a window to show dags before the first " 74462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman "dag combine pass")); 75462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool> 76462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden, 77462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman cl::desc("Pop up a window to show dags before legalize types")); 78462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool> 79462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewLegalizeDAGs("view-legalize-dags", cl::Hidden, 80462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman cl::desc("Pop up a window to show dags before legalize")); 81462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool> 82462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewDAGCombine2("view-dag-combine2-dags", cl::Hidden, 83462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman cl::desc("Pop up a window to show dags before the second " 84462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman "dag combine pass")); 85462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool> 86a9c2091cd38e401c846391c9951ff416e709b65eEvan ChengViewISelDAGs("view-isel-dags", cl::Hidden, 87a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng cl::desc("Pop up a window to show isel dags as they are selected")); 88a9c2091cd38e401c846391c9951ff416e709b65eEvan Chengstatic cl::opt<bool> 89a9c2091cd38e401c846391c9951ff416e709b65eEvan ChengViewSchedDAGs("view-sched-dags", cl::Hidden, 90a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng cl::desc("Pop up a window to show sched dags as they are processed")); 913e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohmanstatic cl::opt<bool> 923e1a7aef17575d9c7058a035449d57e3c7295ed0Dan GohmanViewSUnitDAGs("view-sunit-dags", cl::Hidden, 935bab78527a946632cd9614daa0b9a82ee7b5e1ccChris Lattner cl::desc("Pop up a window to show SUnit dags after they are processed")); 947944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattner#else 95462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic const bool ViewDAGCombine1 = false, 96462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false, 97462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman ViewDAGCombine2 = false, 98462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman ViewISelDAGs = false, ViewSchedDAGs = false, 99462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman ViewSUnitDAGs = false; 1007944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattner#endif 1017944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattner 102eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===// 103eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// 104eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// RegisterScheduler class - Track the registration of instruction schedulers. 105eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// 106eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===// 107eb577ba3b815a1fa4627b060dd2345d17abf672dJim LaskeyMachinePassRegistry RegisterScheduler::Registry; 108eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey 109eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===// 110eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// 111eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// ISHeuristic command line option for instruction schedulers. 112eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// 113eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===// 114844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<RegisterScheduler::FunctionPassCtor, false, 115844731a7f1909f55935e3514c9e713a62d67662eDan Gohman RegisterPassParser<RegisterScheduler> > 116844731a7f1909f55935e3514c9e713a62d67662eDan GohmanISHeuristic("pre-RA-sched", 117844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(&createDefaultScheduler), 118844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::desc("Instruction schedulers available (before register" 119844731a7f1909f55935e3514c9e713a62d67662eDan Gohman " allocation):")); 12013ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey 121844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterScheduler 122844731a7f1909f55935e3514c9e713a62d67662eDan GohmandefaultListDAGScheduler("default", " Best scheduler for the target", 123844731a7f1909f55935e3514c9e713a62d67662eDan Gohman createDefaultScheduler); 1244ef10867499aa146cd819c78d8d37a8353d4f0ffEvan Cheng 125f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmannamespace llvm { 126f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman //===--------------------------------------------------------------------===// 127f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// createDefaultScheduler - This creates an instruction scheduler appropriate 128f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// for the target. 129f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, 130f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman SelectionDAG *DAG, 131f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *BB, 132f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman bool Fast) { 133f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman TargetLowering &TLI = IS->getTargetLowering(); 134e7cf56aeeebed7423402fdf84c5b1aaf6830316eChris Lattner 135f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) { 136f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman return createTDListDAGScheduler(IS, DAG, BB, Fast); 1373fb2968f2febbcd8e05270270858b6f2afd4b342Chris Lattner } else { 138f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman assert(TLI.getSchedulingPreference() == 139f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman TargetLowering::SchedulingForRegPressure && "Unknown sched type!"); 140f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman return createBURRListDAGScheduler(IS, DAG, BB, Fast); 1413a508c94a6c6f124e8b0549358ce76deb92ab662Chris Lattner } 1423a508c94a6c6f124e8b0549358ce76deb92ab662Chris Lattner } 1431c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner} 1441c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 145ff9b373e8f5006c629af81e2619778b4c4f5249eEvan Cheng// EmitInstrWithCustomInserter - This method should be implemented by targets 146ff9b373e8f5006c629af81e2619778b4c4f5249eEvan Cheng// that mark instructions with the 'usesCustomDAGSchedInserter' flag. These 147025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner// instructions are special in various ways, which require special support to 148025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner// insert. The specified MachineInstr is created but not inserted into any 149025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner// basic blocks, and the scheduler passes ownership of it to this method. 150ff9b373e8f5006c629af81e2619778b4c4f5249eEvan ChengMachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI, 151025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner MachineBasicBlock *MBB) { 152832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << "If a target marks an instruction with " 153832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling << "'usesCustomDAGSchedInserter', it must implement " 154ff9b373e8f5006c629af81e2619778b4c4f5249eEvan Cheng << "TargetLowering::EmitInstrWithCustomInserter!\n"; 155025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner abort(); 156025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner return 0; 157025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner} 158025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner 1598a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// EmitLiveInCopy - Emit a copy for a live in physical register. If the 1608a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// physical register has only a single copy use, then coalesced the copy 1618a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// if possible. 1628a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohmanstatic void EmitLiveInCopy(MachineBasicBlock *MBB, 1638a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineBasicBlock::iterator &InsertPos, 1648a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman unsigned VirtReg, unsigned PhysReg, 1658a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterClass *RC, 1668a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman DenseMap<MachineInstr*, unsigned> &CopyRegMap, 1678a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const MachineRegisterInfo &MRI, 1688a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterInfo &TRI, 1698a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetInstrInfo &TII) { 1708a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman unsigned NumUses = 0; 1718a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineInstr *UseMI = NULL; 1728a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(VirtReg), 1738a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman UE = MRI.use_end(); UI != UE; ++UI) { 1748a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman UseMI = &*UI; 1758a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (++NumUses > 1) 1768a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman break; 1778a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 1788a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 1798a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // If the number of uses is not one, or the use is not a move instruction, 1808a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // don't coalesce. Also, only coalesce away a virtual register to virtual 1818a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // register copy. 1828a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman bool Coalesced = false; 1838a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman unsigned SrcReg, DstReg; 1848a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (NumUses == 1 && 1858a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman TII.isMoveInstr(*UseMI, SrcReg, DstReg) && 1868a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman TargetRegisterInfo::isVirtualRegister(DstReg)) { 1878a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman VirtReg = DstReg; 1888a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman Coalesced = true; 1898a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 1908a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 1918a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // Now find an ideal location to insert the copy. 1928a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineBasicBlock::iterator Pos = InsertPos; 1938a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman while (Pos != MBB->begin()) { 1948a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineInstr *PrevMI = prior(Pos); 1958a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman DenseMap<MachineInstr*, unsigned>::iterator RI = CopyRegMap.find(PrevMI); 1968a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // copyRegToReg might emit multiple instructions to do a copy. 1978a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman unsigned CopyDstReg = (RI == CopyRegMap.end()) ? 0 : RI->second; 1988a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (CopyDstReg && !TRI.regsOverlap(CopyDstReg, PhysReg)) 1998a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // This is what the BB looks like right now: 2008a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r1024 = mov r0 2018a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // ... 2028a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r1 = mov r1024 2038a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // 2048a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // We want to insert "r1025 = mov r1". Inserting this copy below the 2058a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // move to r1024 makes it impossible for that move to be coalesced. 2068a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // 2078a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r1025 = mov r1 2088a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r1024 = mov r0 2098a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // ... 2108a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r1 = mov 1024 2118a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r2 = mov 1025 2128a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman break; // Woot! Found a good location. 2138a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman --Pos; 2148a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 2158a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 2168a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman TII.copyRegToReg(*MBB, Pos, VirtReg, PhysReg, RC, RC); 2178a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman CopyRegMap.insert(std::make_pair(prior(Pos), VirtReg)); 2188a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (Coalesced) { 2198a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (&*InsertPos == UseMI) ++InsertPos; 2208a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MBB->erase(UseMI); 2218a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 2228a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman} 2238a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 2248a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// EmitLiveInCopies - If this is the first basic block in the function, 2258a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// and if it has live ins that need to be copied into vregs, emit the 2268a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// copies into the block. 2278a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohmanstatic void EmitLiveInCopies(MachineBasicBlock *EntryMBB, 2288a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const MachineRegisterInfo &MRI, 2298a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterInfo &TRI, 2308a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetInstrInfo &TII) { 2318a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (SchedLiveInCopies) { 2328a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // Emit the copies at a heuristically-determined location in the block. 2338a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman DenseMap<MachineInstr*, unsigned> CopyRegMap; 2348a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineBasicBlock::iterator InsertPos = EntryMBB->begin(); 2358a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(), 2368a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman E = MRI.livein_end(); LI != E; ++LI) 2378a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (LI->second) { 2388a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterClass *RC = MRI.getRegClass(LI->second); 2398a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman EmitLiveInCopy(EntryMBB, InsertPos, LI->second, LI->first, 2408a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman RC, CopyRegMap, MRI, TRI, TII); 2418a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 2428a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } else { 2438a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // Emit the copies into the top of the block. 2448a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(), 2458a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman E = MRI.livein_end(); LI != E; ++LI) 2468a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (LI->second) { 2478a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterClass *RC = MRI.getRegClass(LI->second); 2488a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman TII.copyRegToReg(*EntryMBB, EntryMBB->begin(), 2498a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman LI->second, LI->first, RC, RC); 2508a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 2518a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 2528a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman} 2538a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 2547041ee35adecb864e3e8df490aa73b0605fbfb5aChris Lattner//===----------------------------------------------------------------------===// 2557041ee35adecb864e3e8df490aa73b0605fbfb5aChris Lattner// SelectionDAGISel code 2567041ee35adecb864e3e8df490aa73b0605fbfb5aChris Lattner//===----------------------------------------------------------------------===// 2571c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 2587c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan GohmanSelectionDAGISel::SelectionDAGISel(TargetLowering &tli, bool fast) : 259ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman FunctionPass(&ID), TLI(tli), 2607c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman FuncInfo(new FunctionLoweringInfo(TLI)), 2617c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG(new SelectionDAG(TLI, *FuncInfo)), 2627c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL(new SelectionDAGLowering(*CurDAG, TLI, *FuncInfo)), 2637c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman GFI(), 2647c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman Fast(fast), 2657c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman DAGSize(0) 2667c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman{} 2677c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman 2687c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan GohmanSelectionDAGISel::~SelectionDAGISel() { 2697c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman delete SDL; 2707c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman delete CurDAG; 2717c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman delete FuncInfo; 2727c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman} 2737c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman 27483ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sandsunsigned SelectionDAGISel::MakeReg(MVT VT) { 27584bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT)); 2761c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner} 2771c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 278495a0b51915eb763576874f29192820b731edc22Chris Lattnervoid SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 279c7c3f110eda0ff8040e4bd99e38d3112b910810fJim Laskey AU.addRequired<AliasAnalysis>(); 2805eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen AU.addRequired<GCModuleInfo>(); 281c8d288f8fa9e46199a29e1954550c980f184bd1cChris Lattner AU.setPreservesAll(); 282495a0b51915eb763576874f29192820b731edc22Chris Lattner} 2831c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 2841c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattnerbool SelectionDAGISel::runOnFunction(Function &Fn) { 2854344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman // Do some sanity-checking on the command-line options. 2864344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman assert((!EnableFastISelVerbose || EnableFastISel) && 2874344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman "-fast-isel-verbose requires -fast-isel"); 2884344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman assert((!EnableFastISelAbort || EnableFastISel) && 2894344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman "-fast-isel-abort requires -fast-isel"); 2904344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman 2915f43f92c69aae9837064cf08291db1b36a82789fDan Gohman // Get alias analysis for load/store combining. 2925f43f92c69aae9837064cf08291db1b36a82789fDan Gohman AA = &getAnalysis<AliasAnalysis>(); 2935f43f92c69aae9837064cf08291db1b36a82789fDan Gohman 2948a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman TargetMachine &TM = TLI.getTargetMachine(); 2958a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineFunction &MF = MachineFunction::construct(&Fn, TM); 2968a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const MachineRegisterInfo &MRI = MF.getRegInfo(); 2978a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetInstrInfo &TII = *TM.getInstrInfo(); 2988a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterInfo &TRI = *TM.getRegisterInfo(); 2998a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 3005eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen if (MF.getFunction()->hasGC()) 3015eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen GFI = &getAnalysis<GCModuleInfo>().getFunctionInfo(*MF.getFunction()); 302ce2247755e56f99a2377b64a1a9d393726582b85Gordon Henriksen else 3035eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen GFI = 0; 30484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner RegInfo = &MF.getRegInfo(); 305832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "\n\n\n=== " << Fn.getName() << "\n"; 3061c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 307f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman FuncInfo->set(Fn, MF, EnableFastISel); 308d57dd5f4e6740520820bc0fca42a540e31c27a73Dan Gohman MachineModuleInfo *MMI = getAnalysisToUpdate<MachineModuleInfo>(); 309d57dd5f4e6740520820bc0fca42a540e31c27a73Dan Gohman CurDAG->init(MF, MMI); 3107c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->init(GFI, *AA); 3111c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 3121532f3ddd77c362dd5f613af06b4de636e3c5b0eDale Johannesen for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 3131532f3ddd77c362dd5f613af06b4de636e3c5b0eDale Johannesen if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator())) 3141532f3ddd77c362dd5f613af06b4de636e3c5b0eDale Johannesen // Mark landing pad. 3157c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman FuncInfo->MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad(); 3169fac0b5ff24e733072bdde68c7f34590c1892922Duncan Sands 317d57dd5f4e6740520820bc0fca42a540e31c27a73Dan Gohman SelectAllBasicBlocks(Fn, MF, MMI); 318edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 3198a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // If the first basic block in the function has live ins that need to be 3208a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // copied into vregs, emit the copies into the top of the block before 3218a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // emitting the code for the block. 3228a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman EmitLiveInCopies(MF.begin(), MRI, TRI, TII); 3238a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 324ad2070c667ebabf1650be63e6b3e0b411da86918Evan Cheng // Add function live-ins to entry block live-in set. 3258a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(), 3268a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman E = RegInfo->livein_end(); I != E; ++I) 3278a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MF.begin()->addLiveIn(I->first); 328ad2070c667ebabf1650be63e6b3e0b411da86918Evan Cheng 329f40708223e409a152834b1553c6883ff2035b957Duncan Sands#ifndef NDEBUG 3307c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman assert(FuncInfo->CatchInfoFound.size() == FuncInfo->CatchInfoLost.size() && 331f40708223e409a152834b1553c6883ff2035b957Duncan Sands "Not all catch info was assigned to a landing pad!"); 332f40708223e409a152834b1553c6883ff2035b957Duncan Sands#endif 333f40708223e409a152834b1553c6883ff2035b957Duncan Sands 3347c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman FuncInfo->clear(); 3357c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman 3361c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner return true; 3371c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner} 3381c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 339f40708223e409a152834b1553c6883ff2035b957Duncan Sandsstatic void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB, 340f40708223e409a152834b1553c6883ff2035b957Duncan Sands MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) { 341f40708223e409a152834b1553c6883ff2035b957Duncan Sands for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I) 342f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman if (EHSelectorInst *EHSel = dyn_cast<EHSelectorInst>(I)) { 343f40708223e409a152834b1553c6883ff2035b957Duncan Sands // Apply the catch info to DestBB. 344f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman AddCatchInfo(*EHSel, MMI, FLI.MBBMap[DestBB]); 345f40708223e409a152834b1553c6883ff2035b957Duncan Sands#ifndef NDEBUG 346560a737e073788463b9275c5e92ebc12f0ea62a2Duncan Sands if (!FLI.MBBMap[SrcBB]->isLandingPad()) 347f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman FLI.CatchInfoFound.insert(EHSel); 348f40708223e409a152834b1553c6883ff2035b957Duncan Sands#endif 349f40708223e409a152834b1553c6883ff2035b957Duncan Sands } 350f40708223e409a152834b1553c6883ff2035b957Duncan Sands} 351f40708223e409a152834b1553c6883ff2035b957Duncan Sands 35230e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// IsFixedFrameObjectWithPosOffset - Check if object is a fixed frame object and 35330e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// whether object offset >= 0. 35430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighoferstatic bool 355475871a144eb604ddaf37503397ba0941442e5fbDan GohmanIsFixedFrameObjectWithPosOffset(MachineFrameInfo * MFI, SDValue Op) { 35630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer if (!isa<FrameIndexSDNode>(Op)) return false; 35730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer 35830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer FrameIndexSDNode * FrameIdxNode = dyn_cast<FrameIndexSDNode>(Op); 35930e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer int FrameIdx = FrameIdxNode->getIndex(); 36030e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer return MFI->isFixedObjectIndex(FrameIdx) && 36130e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer MFI->getObjectOffset(FrameIdx) >= 0; 36230e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer} 36330e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer 36430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// IsPossiblyOverwrittenArgumentOfTailCall - Check if the operand could 36530e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// possibly be overwritten when lowering the outgoing arguments in a tail 36630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// call. Currently the implementation of this call is very conservative and 36730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// assumes all arguments sourcing from FORMAL_ARGUMENTS or a CopyFromReg with 36830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// virtual registers would be overwritten by direct lowering. 369475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanstatic bool IsPossiblyOverwrittenArgumentOfTailCall(SDValue Op, 37030e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer MachineFrameInfo * MFI) { 37130e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer RegisterSDNode * OpReg = NULL; 37230e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer if (Op.getOpcode() == ISD::FORMAL_ARGUMENTS || 37330e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer (Op.getOpcode()== ISD::CopyFromReg && 37430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer (OpReg = dyn_cast<RegisterSDNode>(Op.getOperand(1))) && 37530e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer (OpReg->getReg() >= TargetRegisterInfo::FirstVirtualRegister)) || 37630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer (Op.getOpcode() == ISD::LOAD && 37730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(1))) || 37830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer (Op.getOpcode() == ISD::MERGE_VALUES && 37999a6cb92d173c142073416c81efe6d3daeb80b49Gabor Greif Op.getOperand(Op.getResNo()).getOpcode() == ISD::LOAD && 38099a6cb92d173c142073416c81efe6d3daeb80b49Gabor Greif IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(Op.getResNo()). 38130e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer getOperand(1)))) 38230e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer return true; 38330e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer return false; 38430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer} 38530e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer 386c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer/// CheckDAGForTailCallsAndFixThem - This Function looks for CALL nodes in the 38748abc5cf6ba6d53513034aa8c68b0a9abd748190Arnold Schwaighofer/// DAG and fixes their tailcall attribute operand. 388c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighoferstatic void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG, 389c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer TargetLowering& TLI) { 390c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer SDNode * Ret = NULL; 391475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue Terminator = DAG.getRoot(); 392c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer 393c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // Find RET node. 394c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer if (Terminator.getOpcode() == ISD::RET) { 395ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif Ret = Terminator.getNode(); 396c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer } 397c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer 398c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // Fix tail call attribute of CALL nodes. 399c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(), 4000e5f1306b059b62d7725f324e087efbc8e7a782dDan Gohman BI = DAG.allnodes_end(); BI != BE; ) { 4010e5f1306b059b62d7725f324e087efbc8e7a782dDan Gohman --BI; 402095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman if (CallSDNode *TheCall = dyn_cast<CallSDNode>(BI)) { 403475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue OpRet(Ret, 0); 404475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue OpCall(BI, 0); 405095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman bool isMarkedTailCall = TheCall->isTailCall(); 406c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // If CALL node has tail call attribute set to true and the call is not 407c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // eligible (no RET or the target rejects) the attribute is fixed to 40848abc5cf6ba6d53513034aa8c68b0a9abd748190Arnold Schwaighofer // false. The TargetLowering::IsEligibleForTailCallOptimization function 409c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // must correctly identify tail call optimizable calls. 41030e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer if (!isMarkedTailCall) continue; 41130e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer if (Ret==NULL || 412095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman !TLI.IsEligibleForTailCallOptimization(TheCall, OpRet, DAG)) { 413095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman // Not eligible. Mark CALL node as non tail call. Note that we 414095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman // can modify the call node in place since calls are not CSE'd. 415095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman TheCall->setNotTailCall(); 41630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer } else { 41730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer // Look for tail call clobbered arguments. Emit a series of 41830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer // copyto/copyfrom virtual register nodes to protect them. 419475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SmallVector<SDValue, 32> Ops; 420095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman SDValue Chain = TheCall->getChain(), InFlag; 421095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman Ops.push_back(Chain); 422095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman Ops.push_back(TheCall->getCallee()); 423095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman for (unsigned i = 0, e = TheCall->getNumArgs(); i != e; ++i) { 424095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman SDValue Arg = TheCall->getArg(i); 425095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman bool isByVal = TheCall->getArgFlags(i).isByVal(); 426095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman MachineFunction &MF = DAG.getMachineFunction(); 427095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman MachineFrameInfo *MFI = MF.getFrameInfo(); 428095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman if (!isByVal && 429095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman IsPossiblyOverwrittenArgumentOfTailCall(Arg, MFI)) { 430095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman MVT VT = Arg.getValueType(); 431095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman unsigned VReg = MF.getRegInfo(). 432095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman createVirtualRegister(TLI.getRegClassFor(VT)); 433095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman Chain = DAG.getCopyToReg(Chain, VReg, Arg, InFlag); 434095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman InFlag = Chain.getValue(1); 435095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman Arg = DAG.getCopyFromReg(Chain, VReg, VT, InFlag); 436095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman Chain = Arg.getValue(1); 437095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman InFlag = Arg.getValue(2); 43830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer } 43930e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer Ops.push_back(Arg); 440095cc29f321382e1f7d295e262a28197f92c5491Dan Gohman Ops.push_back(TheCall->getArgFlagsVal(i)); 44130e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer } 44230e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer // Link in chain of CopyTo/CopyFromReg. 44330e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer Ops[0] = Chain; 44430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size()); 445c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer } 446c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer } 447c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer } 448c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer} 449c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer 450f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohmanvoid SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, 451f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman BasicBlock::iterator Begin, 4525edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman BasicBlock::iterator End) { 4537c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 454f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 455f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman MachineModuleInfo *MMI = CurDAG->getMachineModuleInfo(); 456f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 457f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (MMI && BB->isLandingPad()) { 458f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Add a label to mark the beginning of the landing pad. Deletion of the 459f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // landing pad can thus be detected via the MachineModuleInfo. 460f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman unsigned LabelID = MMI->addLandingPad(BB); 461f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->setRoot(CurDAG->getLabel(ISD::EH_LABEL, 462f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->getEntryNode(), LabelID)); 463f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 464f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Mark exception register as live in. 465f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman unsigned Reg = TLI.getExceptionAddressRegister(); 466f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (Reg) BB->addLiveIn(Reg); 467f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 468f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Mark exception selector register as live in. 469f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman Reg = TLI.getExceptionSelectorRegister(); 470f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (Reg) BB->addLiveIn(Reg); 471f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 472f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // FIXME: Hack around an exception handling flaw (PR1508): the personality 473f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // function and list of typeids logically belong to the invoke (or, if you 474f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // like, the basic block containing the invoke), and need to be associated 475f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // with it in the dwarf exception handling tables. Currently however the 476f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // information is provided by an intrinsic (eh.selector) that can be moved 477f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // to unexpected places by the optimizers: if the unwind edge is critical, 478f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // then breaking it can result in the intrinsics being in the successor of 479f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // the landing pad, not the landing pad itself. This results in exceptions 480f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // not being caught because no typeids are associated with the invoke. 481f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // This may not be the only way things can go wrong, but it is the only way 482f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // we try to work around for the moment. 483f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator()); 484f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 485f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (Br && Br->isUnconditional()) { // Critical edge? 486f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman BasicBlock::iterator I, E; 487f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I) 488f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman if (isa<EHSelectorInst>(I)) 489f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman break; 490f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 491f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (I == E) 492f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // No catch info found - try to extract some from the successor. 4937c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo); 494f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 495f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 496f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 497f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Lower all of the non-terminator instructions. 498f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman for (BasicBlock::iterator I = Begin; I != End; ++I) 499f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (!isa<TerminatorInst>(I)) 5007c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visit(*I); 501f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 502f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Ensure that all instructions which are used outside of their defining 503f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // blocks are available as virtual registers. Invoke is handled elsewhere. 504f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman for (BasicBlock::iterator I = Begin; I != End; ++I) 505f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (!I->use_empty() && !isa<PHINode>(I) && !isa<InvokeInst>(I)) { 5067c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman DenseMap<const Value*,unsigned>::iterator VMI =FuncInfo->ValueMap.find(I); 5077c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (VMI != FuncInfo->ValueMap.end()) 5087c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->CopyValueToVirtualRegister(I, VMI->second); 509f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 510f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 511f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Handle PHI nodes in successor blocks. 5123df24e667f04a7003342b534310919abc9c87418Dan Gohman if (End == LLVMBB->end()) { 5137c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman HandlePHINodesInSuccessorBlocks(LLVMBB); 5143df24e667f04a7003342b534310919abc9c87418Dan Gohman 5153df24e667f04a7003342b534310919abc9c87418Dan Gohman // Lower the terminator after the copies are emitted. 5163df24e667f04a7003342b534310919abc9c87418Dan Gohman SDL->visit(*LLVMBB->getTerminator()); 5173df24e667f04a7003342b534310919abc9c87418Dan Gohman } 5184198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 519a651cf67b77cd477dd7da4baa8688af2ccd4f7f6Chris Lattner // Make sure the root of the DAG is up-to-date. 5207c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getControlRoot()); 521c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer 522c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // Check whether calls in this block are real tail calls. Fix up CALL nodes 523c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // with correct tailcall attribute so that the target can rely on the tailcall 524c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // attribute indicating whether the call is really eligible for tail call 525c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // optimization. 5261937e2f6ca0e6a04c4ad5fdb5b606b5ed9533e74Dan Gohman if (PerformTailCallOpt) 5271937e2f6ca0e6a04c4ad5fdb5b606b5ed9533e74Dan Gohman CheckDAGForTailCallsAndFixThem(*CurDAG, TLI); 528f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 529f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Final step, emit the lowered DAG as machine code. 530f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 5317c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 5321c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner} 5331c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 534f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohmanvoid SelectionDAGISel::ComputeLiveOutVRegInfo() { 535ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner SmallPtrSet<SDNode*, 128> VisitedNodes; 536ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner SmallVector<SDNode*, 128> Worklist; 537ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 538ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif Worklist.push_back(CurDAG->getRoot().getNode()); 539ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 540ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner APInt Mask; 541ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner APInt KnownZero; 542ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner APInt KnownOne; 543ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 544ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner while (!Worklist.empty()) { 545ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner SDNode *N = Worklist.back(); 546ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner Worklist.pop_back(); 547ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 548ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner // If we've already seen this node, ignore it. 549ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (!VisitedNodes.insert(N)) 550ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner continue; 551ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 552ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner // Otherwise, add all chain operands to the worklist. 553ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 554ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (N->getOperand(i).getValueType() == MVT::Other) 555ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif Worklist.push_back(N->getOperand(i).getNode()); 556ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 557ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner // If this is a CopyToReg with a vreg dest, process it. 558ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (N->getOpcode() != ISD::CopyToReg) 559ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner continue; 560ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 561ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg(); 562ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (!TargetRegisterInfo::isVirtualRegister(DestReg)) 563ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner continue; 564ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 565ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner // Ignore non-scalar or non-integer values. 566475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue Src = N->getOperand(2); 567ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner MVT SrcVT = Src.getValueType(); 568ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (!SrcVT.isInteger() || SrcVT.isVector()) 569ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner continue; 570ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 571f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src); 572ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits()); 573f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne); 574ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 575ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner // Only install this information if it tells us something. 576ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) { 577ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner DestReg -= TargetRegisterInfo::FirstVirtualRegister; 578f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman FunctionLoweringInfo &FLI = CurDAG->getFunctionLoweringInfo(); 579ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (DestReg >= FLI.LiveOutRegInfo.size()) 580ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner FLI.LiveOutRegInfo.resize(DestReg+1); 581ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[DestReg]; 582ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner LOI.NumSignBits = NumSignBits; 583ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner LOI.KnownOne = NumSignBits; 584ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner LOI.KnownZero = NumSignBits; 585ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner } 586ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner } 587ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner} 588ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 589f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohmanvoid SelectionDAGISel::CodeGenAndEmitDAG() { 590462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman std::string GroupName; 591462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman if (TimePassesIsEnabled) 592462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman GroupName = "Instruction Selection and Scheduling"; 593462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman std::string BlockName; 594462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs || 595462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman ViewDAGCombine2 || ViewISelDAGs || ViewSchedDAGs || ViewSUnitDAGs) 596f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman BlockName = CurDAG->getMachineFunction().getFunction()->getName() + ':' + 597462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman BB->getBasicBlock()->getName(); 598462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 599462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman DOUT << "Initial selection DAG:\n"; 600f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 601462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 602f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName); 603417e11b9bf625b3626f8765d44248927fb200906Dan Gohman 604af21d55aee8d6852fedfd630395a3c7c95df8f12Chris Lattner // Run the DAG combiner in pre-legalize mode. 605ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng if (TimePassesIsEnabled) { 6065e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("DAG Combining 1", GroupName); 607f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Combine(false, *AA, Fast); 608ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } else { 609f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Combine(false, *AA, Fast); 610ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } 6112300f5504643eaddc307d3db8a3ccd224c4fa251Nate Begeman 612417e11b9bf625b3626f8765d44248927fb200906Dan Gohman DOUT << "Optimized lowered selection DAG:\n"; 613f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 614f00e74f4d64385e6b2ee29887114e7c8abdf1f17Duncan Sands 6151c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner // Second step, hack on the DAG until it only uses operations and types that 6161c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner // the target supports. 617f00e74f4d64385e6b2ee29887114e7c8abdf1f17Duncan Sands if (EnableLegalizeTypes) {// Enable this some day. 618f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " + 619f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman BlockName); 620462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 621462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman if (TimePassesIsEnabled) { 622462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman NamedRegionTimer T("Type Legalization", GroupName); 623f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->LegalizeTypes(); 624462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman } else { 625f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->LegalizeTypes(); 626462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman } 627462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 628462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman DOUT << "Type-legalized selection DAG:\n"; 629f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 630462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 63170587ea813986bb0dbef71610091d496e28c22a6Chris Lattner // TODO: enable a dag combine pass here. 63270587ea813986bb0dbef71610091d496e28c22a6Chris Lattner } 633f00e74f4d64385e6b2ee29887114e7c8abdf1f17Duncan Sands 634f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName); 635462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 636ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng if (TimePassesIsEnabled) { 6375e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("DAG Legalization", GroupName); 638f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Legalize(); 639ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } else { 640f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Legalize(); 641ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } 642f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman 643832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "Legalized selection DAG:\n"; 644f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 645f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman 646f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName); 647462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 648af21d55aee8d6852fedfd630395a3c7c95df8f12Chris Lattner // Run the DAG combiner in post-legalize mode. 649ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng if (TimePassesIsEnabled) { 6505e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("DAG Combining 2", GroupName); 651f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Combine(true, *AA, Fast); 652ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } else { 653f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Combine(true, *AA, Fast); 654ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } 6552300f5504643eaddc307d3db8a3ccd224c4fa251Nate Begeman 656417e11b9bf625b3626f8765d44248927fb200906Dan Gohman DOUT << "Optimized legalized selection DAG:\n"; 657f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 658417e11b9bf625b3626f8765d44248927fb200906Dan Gohman 659f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName); 660ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 661925a7e8ed6522f291b4ae559ccfa56db461016e3Dan Gohman if (!Fast && EnableValueProp) 662f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman ComputeLiveOutVRegInfo(); 663552c4a849422ad91fa9988255ae35aebbf3acf7bEvan Cheng 664a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner // Third, instruction select all of the operations to machine code, adding the 665a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner // code to the MachineBasicBlock. 666ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng if (TimePassesIsEnabled) { 6675e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("Instruction Selection", GroupName); 668f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman InstructionSelect(); 669ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } else { 670f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman InstructionSelect(); 671ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } 672db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng 673462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman DOUT << "Selected selection DAG:\n"; 674f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 675462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 676f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName); 677462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 6785e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman // Schedule machine code. 6795e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman ScheduleDAG *Scheduler; 6805e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman if (TimePassesIsEnabled) { 6815e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("Instruction Scheduling", GroupName); 682f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman Scheduler = Schedule(); 6835e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman } else { 684f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman Scheduler = Schedule(); 6855e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman } 6865e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman 687462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman if (ViewSUnitDAGs) Scheduler->viewGraph(); 688462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 689db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng // Emit machine code to BB. This can change 'BB' to the last block being 690db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng // inserted into. 691ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng if (TimePassesIsEnabled) { 6925e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("Instruction Creation", GroupName); 6935e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman BB = Scheduler->EmitSchedule(); 694ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } else { 6955e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman BB = Scheduler->EmitSchedule(); 6965e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman } 6975e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman 6985e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman // Free the scheduler state. 6995e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman if (TimePassesIsEnabled) { 7005e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName); 7015e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman delete Scheduler; 7025e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman } else { 7035e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman delete Scheduler; 704ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } 705db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng 706832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "Selected machine code:\n"; 7071c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner DEBUG(BB->dump()); 708f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman} 709f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman 710d57dd5f4e6740520820bc0fca42a540e31c27a73Dan Gohmanvoid SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF, 711d57dd5f4e6740520820bc0fca42a540e31c27a73Dan Gohman MachineModuleInfo *MMI) { 71239fd6e81b1b0de8b820155dc6a0dae226c109de6Evan Cheng for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { 71339fd6e81b1b0de8b820155dc6a0dae226c109de6Evan Cheng BasicBlock *LLVMBB = &*I; 7147c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = FuncInfo->MBBMap[LLVMBB]; 715f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 7163df24e667f04a7003342b534310919abc9c87418Dan Gohman BasicBlock::iterator const Begin = LLVMBB->begin(); 7173df24e667f04a7003342b534310919abc9c87418Dan Gohman BasicBlock::iterator const End = LLVMBB->end(); 7189f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng BasicBlock::iterator BI = Begin; 7195edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman 7205edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman // Lower any arguments needed in this block if this is the entry block. 72133134c4a75558288d663267c8991f6bd37a530afDan Gohman bool SuppressFastISel = false; 72233134c4a75558288d663267c8991f6bd37a530afDan Gohman if (LLVMBB == &Fn.getEntryBlock()) { 7235edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman LowerArguments(LLVMBB); 724f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 72533134c4a75558288d663267c8991f6bd37a530afDan Gohman // If any of the arguments has the byval attribute, forgo 72633134c4a75558288d663267c8991f6bd37a530afDan Gohman // fast-isel in the entry block. 72733134c4a75558288d663267c8991f6bd37a530afDan Gohman if (EnableFastISel) { 72833134c4a75558288d663267c8991f6bd37a530afDan Gohman unsigned j = 1; 72933134c4a75558288d663267c8991f6bd37a530afDan Gohman for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(); 73033134c4a75558288d663267c8991f6bd37a530afDan Gohman I != E; ++I, ++j) 73133134c4a75558288d663267c8991f6bd37a530afDan Gohman if (Fn.paramHasAttr(j, ParamAttr::ByVal)) { 73277ca41e5c3f99ee8962b21a7d90bb251a594a65eDan Gohman if (EnableFastISelVerbose || EnableFastISelAbort) 73377ca41e5c3f99ee8962b21a7d90bb251a594a65eDan Gohman cerr << "FastISel skips entry block due to byval argument\n"; 73433134c4a75558288d663267c8991f6bd37a530afDan Gohman SuppressFastISel = true; 73533134c4a75558288d663267c8991f6bd37a530afDan Gohman break; 73633134c4a75558288d663267c8991f6bd37a530afDan Gohman } 73733134c4a75558288d663267c8991f6bd37a530afDan Gohman } 73833134c4a75558288d663267c8991f6bd37a530afDan Gohman } 73933134c4a75558288d663267c8991f6bd37a530afDan Gohman 740f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Before doing SelectionDAG ISel, see if FastISel has been requested. 741f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // FastISel doesn't support EH landing pads, which require special handling. 74233134c4a75558288d663267c8991f6bd37a530afDan Gohman if (EnableFastISel && !SuppressFastISel && !BB->isLandingPad()) { 743d57dd5f4e6740520820bc0fca42a540e31c27a73Dan Gohman if (FastISel *F = TLI.createFastISel(*FuncInfo->MF, MMI, 744d57dd5f4e6740520820bc0fca42a540e31c27a73Dan Gohman FuncInfo->ValueMap, 7450586d91bb3e516d5826826522d9a90ed6ef74d86Dan Gohman FuncInfo->MBBMap, 7460586d91bb3e516d5826826522d9a90ed6ef74d86Dan Gohman FuncInfo->StaticAllocaMap)) { 7475edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman // Emit code for any incoming arguments. This must happen before 7485edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman // beginning FastISel on the entry block. 7495edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman if (LLVMBB == &Fn.getEntryBlock()) { 7505edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman CurDAG->setRoot(SDL->getControlRoot()); 7515edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman CodeGenAndEmitDAG(); 7525edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman SDL->clear(); 7535edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman } 7543df24e667f04a7003342b534310919abc9c87418Dan Gohman F->setCurrentBlock(BB); 7555edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman // Do FastISel on as many instructions as possible. 7569f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng for (; BI != End; ++BI) { 7573df24e667f04a7003342b534310919abc9c87418Dan Gohman // Just before the terminator instruction, insert instructions to 7583df24e667f04a7003342b534310919abc9c87418Dan Gohman // feed PHI nodes in successor blocks. 759a8657e3587eb71eb920c4f0d7d4baa58f33a277dDan Gohman if (isa<TerminatorInst>(BI)) 7603df24e667f04a7003342b534310919abc9c87418Dan Gohman if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, F)) { 7614344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman if (EnableFastISelVerbose || EnableFastISelAbort) { 762293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman cerr << "FastISel miss: "; 763293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman BI->dump(); 764293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman } 7654344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman if (EnableFastISelAbort) 766293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman assert(0 && "FastISel didn't handle a PHI in a successor"); 7673ee25dca5b2f321103e879fb125b7870683e7085Dan Gohman break; 7683df24e667f04a7003342b534310919abc9c87418Dan Gohman } 769f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 7703df24e667f04a7003342b534310919abc9c87418Dan Gohman // First try normal tablegen-generated "fast" selection. 7719f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng if (F->SelectInstruction(BI)) 7723df24e667f04a7003342b534310919abc9c87418Dan Gohman continue; 773f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 77499b218218c0ca3ebfdd568ddfeafa07842e9d69dDan Gohman // Next, try calling the target to attempt to handle the instruction. 7759f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng if (F->TargetSelectInstruction(BI)) 77699b218218c0ca3ebfdd568ddfeafa07842e9d69dDan Gohman continue; 77799b218218c0ca3ebfdd568ddfeafa07842e9d69dDan Gohman 7783df24e667f04a7003342b534310919abc9c87418Dan Gohman // Then handle certain instructions as single-LLVM-Instruction blocks. 779cf01f7a78c18224866595b4b493d03a3de305e1fDan Gohman if (isa<CallInst>(BI)) { 78077ca41e5c3f99ee8962b21a7d90bb251a594a65eDan Gohman if (EnableFastISelVerbose || EnableFastISelAbort) { 78177ca41e5c3f99ee8962b21a7d90bb251a594a65eDan Gohman cerr << "FastISel missed call: "; 78277ca41e5c3f99ee8962b21a7d90bb251a594a65eDan Gohman BI->dump(); 78377ca41e5c3f99ee8962b21a7d90bb251a594a65eDan Gohman } 78433134c4a75558288d663267c8991f6bd37a530afDan Gohman 7859f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng if (BI->getType() != Type::VoidTy) { 786a8657e3587eb71eb920c4f0d7d4baa58f33a277dDan Gohman unsigned &R = FuncInfo->ValueMap[BI]; 787f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (!R) 7889f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng R = FuncInfo->CreateRegForValue(BI); 789f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 790f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 7919f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng SelectBasicBlock(LLVMBB, BI, next(BI)); 792f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman continue; 793f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 794f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 795293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman // Otherwise, give up on FastISel for the rest of the block. 796293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman // For now, be a little lenient about non-branch terminators. 797293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman if (!isa<TerminatorInst>(BI) || isa<BranchInst>(BI)) { 7984344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman if (EnableFastISelVerbose || EnableFastISelAbort) { 799293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman cerr << "FastISel miss: "; 800293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman BI->dump(); 801293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman } 8024344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman if (EnableFastISelAbort) 803293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman // The "fast" selector couldn't handle something and bailed. 804293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman // For the purpose of debugging, just abort. 805293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman assert(0 && "FastISel didn't select the entire block"); 806f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 807f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman break; 808f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 809f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman delete F; 810f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 811f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 812f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 813d2ff647964ed242e67ac12f7d21a58c864309d95Dan Gohman // Run SelectionDAG instruction selection on the remainder of the block 814d2ff647964ed242e67ac12f7d21a58c864309d95Dan Gohman // not handled by FastISel. If FastISel is not run, this is the entire 8153df24e667f04a7003342b534310919abc9c87418Dan Gohman // block. 8169f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng if (BI != End) 8179f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng SelectBasicBlock(LLVMBB, BI, End); 818381cb07544a2bc119e39969d7d508a6247773e1cEvan Cheng 8197c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman FinishBasicBlock(); 82039fd6e81b1b0de8b820155dc6a0dae226c109de6Evan Cheng } 8210e5f1306b059b62d7725f324e087efbc8e7a782dDan Gohman} 8220e5f1306b059b62d7725f324e087efbc8e7a782dDan Gohman 823fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanvoid 8247c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan GohmanSelectionDAGISel::FinishBasicBlock() { 8251c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 826f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Perform target specific isel post processing. 827f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman InstructionSelectPostProcessing(); 828f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 829f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DOUT << "Target-post-processed machine code:\n"; 830f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(BB->dump()); 8314198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8324198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov DOUT << "Total amount of phi nodes to update: " 8337c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman << SDL->PHINodesToUpdate.size() << "\n"; 8347c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman DEBUG(for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) 8357c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman DOUT << "Node " << i << " : (" << SDL->PHINodesToUpdate[i].first 8367c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman << ", " << SDL->PHINodesToUpdate[i].second << ")\n";); 837f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman 838a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner // Next, now that we know what the last MBB the LLVM BB expanded is, update 8391c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner // PHI nodes in successors. 8407c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (SDL->SwitchCases.empty() && 8417c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->JTCases.empty() && 8427c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases.empty()) { 8437c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) { 8447c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman MachineInstr *PHI = SDL->PHINodesToUpdate[i].first; 845f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman assert(PHI->getOpcode() == TargetInstrInfo::PHI && 846f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman "This is not a machine PHI node that we are updating!"); 8477c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second, 8489ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 8499ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner PHI->addOperand(MachineOperand::CreateMBB(BB)); 850f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman } 8517c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->PHINodesToUpdate.clear(); 852f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman return; 8531c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner } 8544198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8557c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned i = 0, e = SDL->BitTestCases.size(); i != e; ++i) { 8564198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Lower header first, if it wasn't already lowered 8577c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (!SDL->BitTestCases[i].Emitted) { 8584198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Set the current basic block to the mbb we wish to insert the code into 8597c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = SDL->BitTestCases[i].Parent; 8607c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 8614198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Emit the code 8627c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitBitTestHeader(SDL->BitTestCases[i]); 8637c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getRoot()); 864f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 8657c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 8664198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 8674198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8687c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); j != ej; ++j) { 8694198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Set the current basic block to the mbb we wish to insert the code into 8707c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = SDL->BitTestCases[i].Cases[j].ThisBB; 8717c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 8724198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Emit the code 8734198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov if (j+1 != ej) 8747c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitBitTestCase(SDL->BitTestCases[i].Cases[j+1].ThisBB, 8757c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases[i].Reg, 8767c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases[i].Cases[j]); 8774198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov else 8787c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitBitTestCase(SDL->BitTestCases[i].Default, 8797c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases[i].Reg, 8807c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases[i].Cases[j]); 8814198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8824198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8837c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getRoot()); 884f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 8857c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 8864198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 8874198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8884198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Update PHI Nodes 8897c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) { 8907c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first; 8914198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov MachineBasicBlock *PHIBB = PHI->getParent(); 8924198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov assert(PHI->getOpcode() == TargetInstrInfo::PHI && 8934198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov "This is not a machine PHI node that we are updating!"); 8944198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // This is "default" BB. We have two jumps to it. From "header" BB and 8954198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // from last "case" BB. 8967c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (PHIBB == SDL->BitTestCases[i].Default) { 8977c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 8989ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 8997c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Parent)); 9007c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 9019ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 9027c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Cases. 9039ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner back().ThisBB)); 9044198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9054198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // One of "cases" BB. 9067c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); 9077c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman j != ej; ++j) { 9087c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman MachineBasicBlock* cBB = SDL->BitTestCases[i].Cases[j].ThisBB; 9094198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov if (cBB->succ_end() != 9104198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) { 9117c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 9129ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 9139ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner PHI->addOperand(MachineOperand::CreateMBB(cBB)); 9144198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9154198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9164198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9174198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9187c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases.clear(); 9194198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 9209453eea49bca1c3904047db495855c93e001d1cdNate Begeman // If the JumpTable record is filled in, then we need to emit a jump table. 9219453eea49bca1c3904047db495855c93e001d1cdNate Begeman // Updating the PHI nodes is tricky in this case, since we need to determine 9229453eea49bca1c3904047db495855c93e001d1cdNate Begeman // whether the PHI is a successor of the range check MBB or the jump table MBB 9237c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned i = 0, e = SDL->JTCases.size(); i != e; ++i) { 9243a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov // Lower header first, if it wasn't already lowered 9257c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (!SDL->JTCases[i].first.Emitted) { 9263a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov // Set the current basic block to the mbb we wish to insert the code into 9277c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = SDL->JTCases[i].first.HeaderBB; 9287c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 9293a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov // Emit the code 9307c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitJumpTableHeader(SDL->JTCases[i].second, SDL->JTCases[i].first); 9317c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getRoot()); 932f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 9337c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 9344198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9353a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov 93637efe6764568a3829fee26aba532283131d1a104Nate Begeman // Set the current basic block to the mbb we wish to insert the code into 9377c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = SDL->JTCases[i].second.MBB; 9387c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 93937efe6764568a3829fee26aba532283131d1a104Nate Begeman // Emit the code 9407c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitJumpTable(SDL->JTCases[i].second); 9417c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getRoot()); 942f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 9437c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 9443a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov 94537efe6764568a3829fee26aba532283131d1a104Nate Begeman // Update PHI Nodes 9467c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) { 9477c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first; 94837efe6764568a3829fee26aba532283131d1a104Nate Begeman MachineBasicBlock *PHIBB = PHI->getParent(); 94937efe6764568a3829fee26aba532283131d1a104Nate Begeman assert(PHI->getOpcode() == TargetInstrInfo::PHI && 95037efe6764568a3829fee26aba532283131d1a104Nate Begeman "This is not a machine PHI node that we are updating!"); 9514198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // "default" BB. We can go there only from header BB. 9527c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (PHIBB == SDL->JTCases[i].second.Default) { 9537c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 9549ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 9557c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateMBB(SDL->JTCases[i].first.HeaderBB)); 956f4360a478944af45d5f851a0903fbbfa44f520dcNate Begeman } 9574198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // JT BB. Just iterate over successors here 958f4360a478944af45d5f851a0903fbbfa44f520dcNate Begeman if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) { 9597c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 9609ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 9619ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner PHI->addOperand(MachineOperand::CreateMBB(BB)); 96237efe6764568a3829fee26aba532283131d1a104Nate Begeman } 96337efe6764568a3829fee26aba532283131d1a104Nate Begeman } 96437efe6764568a3829fee26aba532283131d1a104Nate Begeman } 9657c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->JTCases.clear(); 96637efe6764568a3829fee26aba532283131d1a104Nate Begeman 967b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner // If the switch block involved a branch to one of the actual successors, we 968b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner // need to update PHI nodes in that block. 9697c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) { 9707c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman MachineInstr *PHI = SDL->PHINodesToUpdate[i].first; 971b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner assert(PHI->getOpcode() == TargetInstrInfo::PHI && 972b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner "This is not a machine PHI node that we are updating!"); 973b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner if (BB->isSuccessor(PHI->getParent())) { 9747c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second, 9759ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 9769ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner PHI->addOperand(MachineOperand::CreateMBB(BB)); 977b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner } 978b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner } 979b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner 980f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman // If we generated any switch lowering information, build and codegen any 981f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman // additional DAGs necessary. 9827c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned i = 0, e = SDL->SwitchCases.size(); i != e; ++i) { 983f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman // Set the current basic block to the mbb we wish to insert the code into 9847c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = SDL->SwitchCases[i].ThisBB; 9857c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 986d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner 987f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman // Emit the code 9887c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitSwitchCase(SDL->SwitchCases[i]); 9897c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getRoot()); 990f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 9917c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 992d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner 993d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // Handle any PHI nodes in successors of this chunk, as if we were coming 994d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // from the original BB before switch expansion. Note that PHI nodes can 995d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // occur multiple times in PHINodesToUpdate. We have to be very careful to 996d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // handle them the right number of times. 9977c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman while ((BB = SDL->SwitchCases[i].TrueBB)) { // Handle LHS and RHS. 998d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner for (MachineBasicBlock::iterator Phi = BB->begin(); 999d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){ 1000d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // This value for this PHI node is recorded in PHINodesToUpdate, get it. 1001d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner for (unsigned pn = 0; ; ++pn) { 10027c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman assert(pn != SDL->PHINodesToUpdate.size() && 10037c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman "Didn't find PHI entry!"); 10047c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (SDL->PHINodesToUpdate[pn].first == Phi) { 10057c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman Phi->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pn]. 10069ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner second, false)); 10077c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman Phi->addOperand(MachineOperand::CreateMBB(SDL->SwitchCases[i].ThisBB)); 1008d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner break; 1009d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner } 1010d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner } 1011f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman } 1012d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner 1013d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // Don't process RHS if same block as LHS. 10147c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (BB == SDL->SwitchCases[i].FalseBB) 10157c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->SwitchCases[i].FalseBB = 0; 1016d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner 1017d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // If we haven't handled the RHS, do so now. Otherwise, we're done. 10187c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->SwitchCases[i].TrueBB = SDL->SwitchCases[i].FalseBB; 10197c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->SwitchCases[i].FalseBB = 0; 1020f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman } 10217c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman assert(SDL->SwitchCases[i].TrueBB == 0 && SDL->SwitchCases[i].FalseBB == 0); 1022a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner } 10237c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->SwitchCases.clear(); 10247c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman 10257c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->PHINodesToUpdate.clear(); 10261c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner} 1027a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 102813ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey 10295e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman/// Schedule - Pick a safe ordering for instructions for each 1030a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng/// target node in the graph. 10315e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman/// 1032f350b277f32d7d47f86c0e54f4aec4d470500618Dan GohmanScheduleDAG *SelectionDAGISel::Schedule() { 1033eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault(); 103413ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey 103513ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey if (!Ctor) { 1036eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey Ctor = ISHeuristic; 10379373beba6010dd34316a801c3a9b37ab9e048031Jim Laskey RegisterScheduler::setDefault(Ctor); 10384ef10867499aa146cd819c78d8d37a8353d4f0ffEvan Cheng } 103913ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey 1040f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman ScheduleDAG *Scheduler = Ctor(this, CurDAG, BB, Fast); 10415e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman Scheduler->Run(); 10423e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 10435e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman return Scheduler; 1044a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng} 10450e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 104603fc53c174e654adae4e42a0c352c7937de2cd87Chris Lattner 10479ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim LaskeyHazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() { 10489ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey return new HazardRecognizer(); 10499ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey} 10509ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey 1051755480681c795d585c73556c028b6143c46bda86Chris Lattner//===----------------------------------------------------------------------===// 1052755480681c795d585c73556c028b6143c46bda86Chris Lattner// Helper functions used by the generated instruction selector. 1053755480681c795d585c73556c028b6143c46bda86Chris Lattner//===----------------------------------------------------------------------===// 1054755480681c795d585c73556c028b6143c46bda86Chris Lattner// Calls to these methods are generated by tblgen. 1055755480681c795d585c73556c028b6143c46bda86Chris Lattner 1056755480681c795d585c73556c028b6143c46bda86Chris Lattner/// CheckAndMask - The isel is trying to match something like (and X, 255). If 1057755480681c795d585c73556c028b6143c46bda86Chris Lattner/// the dag combiner simplified the 255, we still want to match. RHS is the 1058755480681c795d585c73556c028b6143c46bda86Chris Lattner/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value 1059755480681c795d585c73556c028b6143c46bda86Chris Lattner/// specified in the .td file (e.g. 255). 1060475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanbool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS, 1061dc9b3d0bb5ed3a3f59cad61e264f0ec43c946459Dan Gohman int64_t DesiredMaskS) const { 10622e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman const APInt &ActualMask = RHS->getAPIntValue(); 10632e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 1064755480681c795d585c73556c028b6143c46bda86Chris Lattner 1065755480681c795d585c73556c028b6143c46bda86Chris Lattner // If the actual mask exactly matches, success! 1066755480681c795d585c73556c028b6143c46bda86Chris Lattner if (ActualMask == DesiredMask) 1067755480681c795d585c73556c028b6143c46bda86Chris Lattner return true; 1068755480681c795d585c73556c028b6143c46bda86Chris Lattner 1069755480681c795d585c73556c028b6143c46bda86Chris Lattner // If the actual AND mask is allowing unallowed bits, this doesn't match. 10702e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman if (ActualMask.intersects(~DesiredMask)) 1071755480681c795d585c73556c028b6143c46bda86Chris Lattner return false; 1072755480681c795d585c73556c028b6143c46bda86Chris Lattner 1073755480681c795d585c73556c028b6143c46bda86Chris Lattner // Otherwise, the DAG Combiner may have proven that the value coming in is 1074755480681c795d585c73556c028b6143c46bda86Chris Lattner // either already zero or is not demanded. Check for known zero input bits. 10752e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman APInt NeededMask = DesiredMask & ~ActualMask; 1076ea859be53ca13a1547c4675549946b74dc3c6f41Dan Gohman if (CurDAG->MaskedValueIsZero(LHS, NeededMask)) 1077755480681c795d585c73556c028b6143c46bda86Chris Lattner return true; 1078755480681c795d585c73556c028b6143c46bda86Chris Lattner 1079755480681c795d585c73556c028b6143c46bda86Chris Lattner // TODO: check to see if missing bits are just not demanded. 1080755480681c795d585c73556c028b6143c46bda86Chris Lattner 1081755480681c795d585c73556c028b6143c46bda86Chris Lattner // Otherwise, this pattern doesn't match. 1082755480681c795d585c73556c028b6143c46bda86Chris Lattner return false; 1083755480681c795d585c73556c028b6143c46bda86Chris Lattner} 1084755480681c795d585c73556c028b6143c46bda86Chris Lattner 1085755480681c795d585c73556c028b6143c46bda86Chris Lattner/// CheckOrMask - The isel is trying to match something like (or X, 255). If 1086755480681c795d585c73556c028b6143c46bda86Chris Lattner/// the dag combiner simplified the 255, we still want to match. RHS is the 1087755480681c795d585c73556c028b6143c46bda86Chris Lattner/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value 1088755480681c795d585c73556c028b6143c46bda86Chris Lattner/// specified in the .td file (e.g. 255). 1089475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanbool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS, 10902e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman int64_t DesiredMaskS) const { 10912e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman const APInt &ActualMask = RHS->getAPIntValue(); 10922e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 1093755480681c795d585c73556c028b6143c46bda86Chris Lattner 1094755480681c795d585c73556c028b6143c46bda86Chris Lattner // If the actual mask exactly matches, success! 1095755480681c795d585c73556c028b6143c46bda86Chris Lattner if (ActualMask == DesiredMask) 1096755480681c795d585c73556c028b6143c46bda86Chris Lattner return true; 1097755480681c795d585c73556c028b6143c46bda86Chris Lattner 1098755480681c795d585c73556c028b6143c46bda86Chris Lattner // If the actual AND mask is allowing unallowed bits, this doesn't match. 10992e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman if (ActualMask.intersects(~DesiredMask)) 1100755480681c795d585c73556c028b6143c46bda86Chris Lattner return false; 1101755480681c795d585c73556c028b6143c46bda86Chris Lattner 1102755480681c795d585c73556c028b6143c46bda86Chris Lattner // Otherwise, the DAG Combiner may have proven that the value coming in is 1103755480681c795d585c73556c028b6143c46bda86Chris Lattner // either already zero or is not demanded. Check for known zero input bits. 11042e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman APInt NeededMask = DesiredMask & ~ActualMask; 1105755480681c795d585c73556c028b6143c46bda86Chris Lattner 11062e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman APInt KnownZero, KnownOne; 1107ea859be53ca13a1547c4675549946b74dc3c6f41Dan Gohman CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne); 1108755480681c795d585c73556c028b6143c46bda86Chris Lattner 1109755480681c795d585c73556c028b6143c46bda86Chris Lattner // If all the missing bits in the or are already known to be set, match! 1110755480681c795d585c73556c028b6143c46bda86Chris Lattner if ((NeededMask & KnownOne) == NeededMask) 1111755480681c795d585c73556c028b6143c46bda86Chris Lattner return true; 1112755480681c795d585c73556c028b6143c46bda86Chris Lattner 1113755480681c795d585c73556c028b6143c46bda86Chris Lattner // TODO: check to see if missing bits are just not demanded. 1114755480681c795d585c73556c028b6143c46bda86Chris Lattner 1115755480681c795d585c73556c028b6143c46bda86Chris Lattner // Otherwise, this pattern doesn't match. 1116755480681c795d585c73556c028b6143c46bda86Chris Lattner return false; 1117755480681c795d585c73556c028b6143c46bda86Chris Lattner} 1118755480681c795d585c73556c028b6143c46bda86Chris Lattner 11199ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey 11200e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 11210e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner/// by tblgen. Others should not call it. 11220e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattnervoid SelectionDAGISel:: 1123f350b277f32d7d47f86c0e54f4aec4d470500618Dan GohmanSelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) { 1124475871a144eb604ddaf37503397ba0941442e5fbDan Gohman std::vector<SDValue> InOps; 11250e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner std::swap(InOps, Ops); 11260e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 11270e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner Ops.push_back(InOps[0]); // input chain. 11280e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner Ops.push_back(InOps[1]); // input asm string. 11290e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 11300e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner unsigned i = 2, e = InOps.size(); 11310e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner if (InOps[e-1].getValueType() == MVT::Flag) 11320e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner --e; // Don't process a flag operand if it is here. 11330e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 11340e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner while (i != e) { 1135f5aeb1a8e4cf272c7348376d185ef8d8267653e0Dan Gohman unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue(); 113686b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if ((Flags & 7) != 4 /*MEM*/) { 11370e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner // Just skip over this operand, copying the operands verbatim. 11380e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1); 11390e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner i += (Flags >> 3) + 1; 11400e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner } else { 11410e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner assert((Flags >> 3) == 1 && "Memory operand with multiple values?"); 11420e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner // Otherwise, this is a memory operand. Ask the target to select it. 1143475871a144eb604ddaf37503397ba0941442e5fbDan Gohman std::vector<SDValue> SelOps; 1144f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) { 1145832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << "Could not match memory address. Inline asm failure!\n"; 11460e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner exit(1); 11470e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner } 11480e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 11490e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner // Add this to the output node. 1150f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman MVT IntPtrTy = CurDAG->getTargetLoweringInfo().getPointerTy(); 115186b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen Ops.push_back(CurDAG->getTargetConstant(4/*MEM*/ | (SelOps.size()<< 3), 1152f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman IntPtrTy)); 11530e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); 11540e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner i += 2; 11550e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner } 11560e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner } 11570e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 11580e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner // Add the flag input back if present. 11590e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner if (e != InOps.size()) 11600e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner Ops.push_back(InOps.back()); 11610e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner} 1162794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 11631997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar SelectionDAGISel::ID = 0; 1164