SelectionDAGISel.cpp revision 0586d91bb3e516d5826826522d9a90ed6ef74d86
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" 285694b6e90eaf94fa7a21f101a8e4424d813a85ceReid Spencer#include "llvm/ParameterAttributes.h" 2978eca170e9ac5db7fd525f9bbf27090fefcbb646Dan Gohman#include "llvm/CodeGen/FastISel.h" 305a29c9eed157af51a8d338b5a225b146881819e8Gordon Henriksen#include "llvm/CodeGen/GCStrategy.h" 315eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen#include "llvm/CodeGen/GCMetadata.h" 321c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/MachineFunction.h" 331c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/MachineFrameInfo.h" 341c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/MachineInstrBuilder.h" 3584bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineJumpTableInfo.h" 3684bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineModuleInfo.h" 3784bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 38381cb07544a2bc119e39969d7d508a6247773e1cEvan Cheng#include "llvm/CodeGen/ScheduleDAG.h" 39eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey#include "llvm/CodeGen/SchedulerRegistry.h" 401c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/CodeGen/SelectionDAG.h" 416f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 421c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetData.h" 431c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetFrameInfo.h" 441c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetInstrInfo.h" 451c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetLowering.h" 461c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner#include "llvm/Target/TargetMachine.h" 47124729155d860a0850eb4ef2a7cea4145e13a057Vladimir Prus#include "llvm/Target/TargetOptions.h" 48a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 49db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng#include "llvm/Support/Debug.h" 50db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng#include "llvm/Support/MathExtras.h" 51db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng#include "llvm/Support/Timer.h" 527e88103cdea8c36b2229dae8c60def14e3816512Jeff Cohen#include <algorithm> 531c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattnerusing namespace llvm; 541c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 55ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattnerstatic cl::opt<bool> 5670587ea813986bb0dbef71610091d496e28c22a6Chris LattnerEnableValueProp("enable-value-prop", cl::Hidden); 5770587ea813986bb0dbef71610091d496e28c22a6Chris Lattnerstatic cl::opt<bool> 58f00e74f4d64385e6b2ee29887114e7c8abdf1f17Duncan SandsEnableLegalizeTypes("enable-legalize-types", cl::Hidden); 5978eca170e9ac5db7fd525f9bbf27090fefcbb646Dan Gohmanstatic cl::opt<bool> 6078eca170e9ac5db7fd525f9bbf27090fefcbb646Dan GohmanEnableFastISel("fast-isel", cl::Hidden, 6178eca170e9ac5db7fd525f9bbf27090fefcbb646Dan Gohman cl::desc("Enable the experimental \"fast\" instruction selector")); 623e697cfa979538c77459a3e4237e9bc1ac638761Dan Gohmanstatic cl::opt<bool> 63293d5f8bc02a9148238b2c79484637f56de65b9cDan GohmanEnableFastISelVerbose("fast-isel-verbose", cl::Hidden, 64293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman cl::desc("Enable verbose messages in the experimental \"fast\" " 65293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman "instruction selector")); 66293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohmanstatic cl::opt<bool> 674344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan GohmanEnableFastISelAbort("fast-isel-abort", cl::Hidden, 684344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman cl::desc("Enable abort calls when \"fast\" instruction fails")); 698a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohmanstatic cl::opt<bool> 708a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan GohmanSchedLiveInCopies("schedule-livein-copies", 718a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman cl::desc("Schedule copies of livein registers"), 728a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman cl::init(false)); 73ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 74da8abb02397d7cd62a1e16e7c534edd7096ac873Chris Lattner#ifndef NDEBUG 757944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattnerstatic cl::opt<bool> 76462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewDAGCombine1("view-dag-combine1-dags", cl::Hidden, 77462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman cl::desc("Pop up a window to show dags before the first " 78462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman "dag combine pass")); 79462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool> 80462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden, 81462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman cl::desc("Pop up a window to show dags before legalize types")); 82462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool> 83462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewLegalizeDAGs("view-legalize-dags", cl::Hidden, 84462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman cl::desc("Pop up a window to show dags before legalize")); 85462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool> 86462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan GohmanViewDAGCombine2("view-dag-combine2-dags", cl::Hidden, 87462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman cl::desc("Pop up a window to show dags before the second " 88462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman "dag combine pass")); 89462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic cl::opt<bool> 90a9c2091cd38e401c846391c9951ff416e709b65eEvan ChengViewISelDAGs("view-isel-dags", cl::Hidden, 91a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng cl::desc("Pop up a window to show isel dags as they are selected")); 92a9c2091cd38e401c846391c9951ff416e709b65eEvan Chengstatic cl::opt<bool> 93a9c2091cd38e401c846391c9951ff416e709b65eEvan ChengViewSchedDAGs("view-sched-dags", cl::Hidden, 94a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng cl::desc("Pop up a window to show sched dags as they are processed")); 953e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohmanstatic cl::opt<bool> 963e1a7aef17575d9c7058a035449d57e3c7295ed0Dan GohmanViewSUnitDAGs("view-sunit-dags", cl::Hidden, 975bab78527a946632cd9614daa0b9a82ee7b5e1ccChris Lattner cl::desc("Pop up a window to show SUnit dags after they are processed")); 987944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattner#else 99462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohmanstatic const bool ViewDAGCombine1 = false, 100462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false, 101462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman ViewDAGCombine2 = false, 102462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman ViewISelDAGs = false, ViewSchedDAGs = false, 103462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman ViewSUnitDAGs = false; 1047944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattner#endif 1057944d9d9957db1efe085d9df3ea89826f50029b7Chris Lattner 106eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===// 107eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// 108eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// RegisterScheduler class - Track the registration of instruction schedulers. 109eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// 110eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===// 111eb577ba3b815a1fa4627b060dd2345d17abf672dJim LaskeyMachinePassRegistry RegisterScheduler::Registry; 112eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey 113eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===// 114eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// 115eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// ISHeuristic command line option for instruction schedulers. 116eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey/// 117eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey//===---------------------------------------------------------------------===// 118844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<RegisterScheduler::FunctionPassCtor, false, 119844731a7f1909f55935e3514c9e713a62d67662eDan Gohman RegisterPassParser<RegisterScheduler> > 120844731a7f1909f55935e3514c9e713a62d67662eDan GohmanISHeuristic("pre-RA-sched", 121844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(&createDefaultScheduler), 122844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::desc("Instruction schedulers available (before register" 123844731a7f1909f55935e3514c9e713a62d67662eDan Gohman " allocation):")); 12413ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey 125844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterScheduler 126844731a7f1909f55935e3514c9e713a62d67662eDan GohmandefaultListDAGScheduler("default", " Best scheduler for the target", 127844731a7f1909f55935e3514c9e713a62d67662eDan Gohman createDefaultScheduler); 1284ef10867499aa146cd819c78d8d37a8353d4f0ffEvan Cheng 129f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohmannamespace llvm { 130f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman //===--------------------------------------------------------------------===// 131f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// createDefaultScheduler - This creates an instruction scheduler appropriate 132f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman /// for the target. 133f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, 134f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman SelectionDAG *DAG, 135f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman MachineBasicBlock *BB, 136f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman bool Fast) { 137f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman TargetLowering &TLI = IS->getTargetLowering(); 138e7cf56aeeebed7423402fdf84c5b1aaf6830316eChris Lattner 139f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) { 140f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman return createTDListDAGScheduler(IS, DAG, BB, Fast); 1413fb2968f2febbcd8e05270270858b6f2afd4b342Chris Lattner } else { 142f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman assert(TLI.getSchedulingPreference() == 143f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman TargetLowering::SchedulingForRegPressure && "Unknown sched type!"); 144f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman return createBURRListDAGScheduler(IS, DAG, BB, Fast); 1453a508c94a6c6f124e8b0549358ce76deb92ab662Chris Lattner } 1463a508c94a6c6f124e8b0549358ce76deb92ab662Chris Lattner } 1471c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner} 1481c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 149ff9b373e8f5006c629af81e2619778b4c4f5249eEvan Cheng// EmitInstrWithCustomInserter - This method should be implemented by targets 150ff9b373e8f5006c629af81e2619778b4c4f5249eEvan Cheng// that mark instructions with the 'usesCustomDAGSchedInserter' flag. These 151025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner// instructions are special in various ways, which require special support to 152025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner// insert. The specified MachineInstr is created but not inserted into any 153025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner// basic blocks, and the scheduler passes ownership of it to this method. 154ff9b373e8f5006c629af81e2619778b4c4f5249eEvan ChengMachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI, 155025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner MachineBasicBlock *MBB) { 156832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << "If a target marks an instruction with " 157832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling << "'usesCustomDAGSchedInserter', it must implement " 158ff9b373e8f5006c629af81e2619778b4c4f5249eEvan Cheng << "TargetLowering::EmitInstrWithCustomInserter!\n"; 159025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner abort(); 160025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner return 0; 161025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner} 162025c39bf36b6bc2f35a5544338de6cf96fa511a9Chris Lattner 1638a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// EmitLiveInCopy - Emit a copy for a live in physical register. If the 1648a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// physical register has only a single copy use, then coalesced the copy 1658a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// if possible. 1668a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohmanstatic void EmitLiveInCopy(MachineBasicBlock *MBB, 1678a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineBasicBlock::iterator &InsertPos, 1688a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman unsigned VirtReg, unsigned PhysReg, 1698a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterClass *RC, 1708a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman DenseMap<MachineInstr*, unsigned> &CopyRegMap, 1718a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const MachineRegisterInfo &MRI, 1728a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterInfo &TRI, 1738a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetInstrInfo &TII) { 1748a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman unsigned NumUses = 0; 1758a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineInstr *UseMI = NULL; 1768a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(VirtReg), 1778a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman UE = MRI.use_end(); UI != UE; ++UI) { 1788a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman UseMI = &*UI; 1798a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (++NumUses > 1) 1808a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman break; 1818a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 1828a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 1838a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // If the number of uses is not one, or the use is not a move instruction, 1848a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // don't coalesce. Also, only coalesce away a virtual register to virtual 1858a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // register copy. 1868a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman bool Coalesced = false; 1878a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman unsigned SrcReg, DstReg; 1888a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (NumUses == 1 && 1898a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman TII.isMoveInstr(*UseMI, SrcReg, DstReg) && 1908a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman TargetRegisterInfo::isVirtualRegister(DstReg)) { 1918a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman VirtReg = DstReg; 1928a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman Coalesced = true; 1938a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 1948a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 1958a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // Now find an ideal location to insert the copy. 1968a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineBasicBlock::iterator Pos = InsertPos; 1978a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman while (Pos != MBB->begin()) { 1988a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineInstr *PrevMI = prior(Pos); 1998a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman DenseMap<MachineInstr*, unsigned>::iterator RI = CopyRegMap.find(PrevMI); 2008a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // copyRegToReg might emit multiple instructions to do a copy. 2018a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman unsigned CopyDstReg = (RI == CopyRegMap.end()) ? 0 : RI->second; 2028a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (CopyDstReg && !TRI.regsOverlap(CopyDstReg, PhysReg)) 2038a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // This is what the BB looks like right now: 2048a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r1024 = mov r0 2058a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // ... 2068a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r1 = mov r1024 2078a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // 2088a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // We want to insert "r1025 = mov r1". Inserting this copy below the 2098a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // move to r1024 makes it impossible for that move to be coalesced. 2108a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // 2118a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r1025 = mov r1 2128a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r1024 = mov r0 2138a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // ... 2148a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r1 = mov 1024 2158a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // r2 = mov 1025 2168a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman break; // Woot! Found a good location. 2178a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman --Pos; 2188a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 2198a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 2208a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman TII.copyRegToReg(*MBB, Pos, VirtReg, PhysReg, RC, RC); 2218a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman CopyRegMap.insert(std::make_pair(prior(Pos), VirtReg)); 2228a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (Coalesced) { 2238a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (&*InsertPos == UseMI) ++InsertPos; 2248a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MBB->erase(UseMI); 2258a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 2268a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman} 2278a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 2288a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// EmitLiveInCopies - If this is the first basic block in the function, 2298a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// and if it has live ins that need to be copied into vregs, emit the 2308a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman/// copies into the block. 2318a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohmanstatic void EmitLiveInCopies(MachineBasicBlock *EntryMBB, 2328a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const MachineRegisterInfo &MRI, 2338a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterInfo &TRI, 2348a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetInstrInfo &TII) { 2358a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (SchedLiveInCopies) { 2368a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // Emit the copies at a heuristically-determined location in the block. 2378a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman DenseMap<MachineInstr*, unsigned> CopyRegMap; 2388a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineBasicBlock::iterator InsertPos = EntryMBB->begin(); 2398a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(), 2408a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman E = MRI.livein_end(); LI != E; ++LI) 2418a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (LI->second) { 2428a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterClass *RC = MRI.getRegClass(LI->second); 2438a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman EmitLiveInCopy(EntryMBB, InsertPos, LI->second, LI->first, 2448a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman RC, CopyRegMap, MRI, TRI, TII); 2458a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 2468a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } else { 2478a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // Emit the copies into the top of the block. 2488a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(), 2498a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman E = MRI.livein_end(); LI != E; ++LI) 2508a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman if (LI->second) { 2518a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterClass *RC = MRI.getRegClass(LI->second); 2528a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman TII.copyRegToReg(*EntryMBB, EntryMBB->begin(), 2538a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman LI->second, LI->first, RC, RC); 2548a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 2558a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman } 2568a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman} 2578a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 2587041ee35adecb864e3e8df490aa73b0605fbfb5aChris Lattner//===----------------------------------------------------------------------===// 2597041ee35adecb864e3e8df490aa73b0605fbfb5aChris Lattner// SelectionDAGISel code 2607041ee35adecb864e3e8df490aa73b0605fbfb5aChris Lattner//===----------------------------------------------------------------------===// 2611c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 2627c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan GohmanSelectionDAGISel::SelectionDAGISel(TargetLowering &tli, bool fast) : 263ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman FunctionPass(&ID), TLI(tli), 2647c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman FuncInfo(new FunctionLoweringInfo(TLI)), 2657c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG(new SelectionDAG(TLI, *FuncInfo)), 2667c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL(new SelectionDAGLowering(*CurDAG, TLI, *FuncInfo)), 2677c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman GFI(), 2687c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman Fast(fast), 2697c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman DAGSize(0) 2707c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman{} 2717c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman 2727c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan GohmanSelectionDAGISel::~SelectionDAGISel() { 2737c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman delete SDL; 2747c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman delete CurDAG; 2757c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman delete FuncInfo; 2767c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman} 2777c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman 27883ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sandsunsigned SelectionDAGISel::MakeReg(MVT VT) { 27984bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT)); 2801c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner} 2811c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 282495a0b51915eb763576874f29192820b731edc22Chris Lattnervoid SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 283c7c3f110eda0ff8040e4bd99e38d3112b910810fJim Laskey AU.addRequired<AliasAnalysis>(); 2845eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen AU.addRequired<GCModuleInfo>(); 285c8d288f8fa9e46199a29e1954550c980f184bd1cChris Lattner AU.setPreservesAll(); 286495a0b51915eb763576874f29192820b731edc22Chris Lattner} 2871c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 2881c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattnerbool SelectionDAGISel::runOnFunction(Function &Fn) { 2894344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman // Do some sanity-checking on the command-line options. 2904344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman assert((!EnableFastISelVerbose || EnableFastISel) && 2914344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman "-fast-isel-verbose requires -fast-isel"); 2924344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman assert((!EnableFastISelAbort || EnableFastISel) && 2934344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman "-fast-isel-abort requires -fast-isel"); 2944344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman 2955f43f92c69aae9837064cf08291db1b36a82789fDan Gohman // Get alias analysis for load/store combining. 2965f43f92c69aae9837064cf08291db1b36a82789fDan Gohman AA = &getAnalysis<AliasAnalysis>(); 2975f43f92c69aae9837064cf08291db1b36a82789fDan Gohman 2988a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman TargetMachine &TM = TLI.getTargetMachine(); 2998a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MachineFunction &MF = MachineFunction::construct(&Fn, TM); 3008a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const MachineRegisterInfo &MRI = MF.getRegInfo(); 3018a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetInstrInfo &TII = *TM.getInstrInfo(); 3028a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman const TargetRegisterInfo &TRI = *TM.getRegisterInfo(); 3038a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 3045eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen if (MF.getFunction()->hasGC()) 3055eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen GFI = &getAnalysis<GCModuleInfo>().getFunctionInfo(*MF.getFunction()); 306ce2247755e56f99a2377b64a1a9d393726582b85Gordon Henriksen else 3075eca075b74d62c621b160aa216b4cd50829a2cc7Gordon Henriksen GFI = 0; 30884bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner RegInfo = &MF.getRegInfo(); 309832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "\n\n\n=== " << Fn.getName() << "\n"; 3101c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 311f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman FuncInfo->set(Fn, MF, EnableFastISel); 3127c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->init(MF, getAnalysisToUpdate<MachineModuleInfo>()); 3137c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->init(GFI, *AA); 3141c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 3151532f3ddd77c362dd5f613af06b4de636e3c5b0eDale Johannesen for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 3161532f3ddd77c362dd5f613af06b4de636e3c5b0eDale Johannesen if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator())) 3171532f3ddd77c362dd5f613af06b4de636e3c5b0eDale Johannesen // Mark landing pad. 3187c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman FuncInfo->MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad(); 3199fac0b5ff24e733072bdde68c7f34590c1892922Duncan Sands 3207c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SelectAllBasicBlocks(Fn, MF); 321edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 3228a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // If the first basic block in the function has live ins that need to be 3238a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // copied into vregs, emit the copies into the top of the block before 3248a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman // emitting the code for the block. 3258a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman EmitLiveInCopies(MF.begin(), MRI, TRI, TII); 3268a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman 327ad2070c667ebabf1650be63e6b3e0b411da86918Evan Cheng // Add function live-ins to entry block live-in set. 3288a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(), 3298a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman E = RegInfo->livein_end(); I != E; ++I) 3308a11053f3ca7efb29312c4293c4fdb5d2ca3e20fDan Gohman MF.begin()->addLiveIn(I->first); 331ad2070c667ebabf1650be63e6b3e0b411da86918Evan Cheng 332f40708223e409a152834b1553c6883ff2035b957Duncan Sands#ifndef NDEBUG 3337c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman assert(FuncInfo->CatchInfoFound.size() == FuncInfo->CatchInfoLost.size() && 334f40708223e409a152834b1553c6883ff2035b957Duncan Sands "Not all catch info was assigned to a landing pad!"); 335f40708223e409a152834b1553c6883ff2035b957Duncan Sands#endif 336f40708223e409a152834b1553c6883ff2035b957Duncan Sands 3377c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman FuncInfo->clear(); 3387c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman 3391c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner return true; 3401c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner} 3411c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 342f40708223e409a152834b1553c6883ff2035b957Duncan Sandsstatic void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB, 343f40708223e409a152834b1553c6883ff2035b957Duncan Sands MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) { 344f40708223e409a152834b1553c6883ff2035b957Duncan Sands for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I) 345f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman if (EHSelectorInst *EHSel = dyn_cast<EHSelectorInst>(I)) { 346f40708223e409a152834b1553c6883ff2035b957Duncan Sands // Apply the catch info to DestBB. 347f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman AddCatchInfo(*EHSel, MMI, FLI.MBBMap[DestBB]); 348f40708223e409a152834b1553c6883ff2035b957Duncan Sands#ifndef NDEBUG 349560a737e073788463b9275c5e92ebc12f0ea62a2Duncan Sands if (!FLI.MBBMap[SrcBB]->isLandingPad()) 350f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman FLI.CatchInfoFound.insert(EHSel); 351f40708223e409a152834b1553c6883ff2035b957Duncan Sands#endif 352f40708223e409a152834b1553c6883ff2035b957Duncan Sands } 353f40708223e409a152834b1553c6883ff2035b957Duncan Sands} 354f40708223e409a152834b1553c6883ff2035b957Duncan Sands 35530e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// IsFixedFrameObjectWithPosOffset - Check if object is a fixed frame object and 35630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// whether object offset >= 0. 35730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighoferstatic bool 358475871a144eb604ddaf37503397ba0941442e5fbDan GohmanIsFixedFrameObjectWithPosOffset(MachineFrameInfo * MFI, SDValue Op) { 35930e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer if (!isa<FrameIndexSDNode>(Op)) return false; 36030e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer 36130e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer FrameIndexSDNode * FrameIdxNode = dyn_cast<FrameIndexSDNode>(Op); 36230e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer int FrameIdx = FrameIdxNode->getIndex(); 36330e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer return MFI->isFixedObjectIndex(FrameIdx) && 36430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer MFI->getObjectOffset(FrameIdx) >= 0; 36530e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer} 36630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer 36730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// IsPossiblyOverwrittenArgumentOfTailCall - Check if the operand could 36830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// possibly be overwritten when lowering the outgoing arguments in a tail 36930e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// call. Currently the implementation of this call is very conservative and 37030e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// assumes all arguments sourcing from FORMAL_ARGUMENTS or a CopyFromReg with 37130e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer/// virtual registers would be overwritten by direct lowering. 372475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanstatic bool IsPossiblyOverwrittenArgumentOfTailCall(SDValue Op, 37330e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer MachineFrameInfo * MFI) { 37430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer RegisterSDNode * OpReg = NULL; 37530e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer if (Op.getOpcode() == ISD::FORMAL_ARGUMENTS || 37630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer (Op.getOpcode()== ISD::CopyFromReg && 37730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer (OpReg = dyn_cast<RegisterSDNode>(Op.getOperand(1))) && 37830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer (OpReg->getReg() >= TargetRegisterInfo::FirstVirtualRegister)) || 37930e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer (Op.getOpcode() == ISD::LOAD && 38030e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(1))) || 38130e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer (Op.getOpcode() == ISD::MERGE_VALUES && 38299a6cb92d173c142073416c81efe6d3daeb80b49Gabor Greif Op.getOperand(Op.getResNo()).getOpcode() == ISD::LOAD && 38399a6cb92d173c142073416c81efe6d3daeb80b49Gabor Greif IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(Op.getResNo()). 38430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer getOperand(1)))) 38530e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer return true; 38630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer return false; 38730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer} 38830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer 389c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer/// CheckDAGForTailCallsAndFixThem - This Function looks for CALL nodes in the 39048abc5cf6ba6d53513034aa8c68b0a9abd748190Arnold Schwaighofer/// DAG and fixes their tailcall attribute operand. 391c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighoferstatic void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG, 392c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer TargetLowering& TLI) { 393c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer SDNode * Ret = NULL; 394475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue Terminator = DAG.getRoot(); 395c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer 396c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // Find RET node. 397c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer if (Terminator.getOpcode() == ISD::RET) { 398ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif Ret = Terminator.getNode(); 399c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer } 400c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer 401c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // Fix tail call attribute of CALL nodes. 402c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(), 4030e5f1306b059b62d7725f324e087efbc8e7a782dDan Gohman BI = DAG.allnodes_end(); BI != BE; ) { 4040e5f1306b059b62d7725f324e087efbc8e7a782dDan Gohman --BI; 405c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer if (BI->getOpcode() == ISD::CALL) { 406475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue OpRet(Ret, 0); 407475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue OpCall(BI, 0); 408c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer bool isMarkedTailCall = 409c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer cast<ConstantSDNode>(OpCall.getOperand(3))->getValue() != 0; 410c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // If CALL node has tail call attribute set to true and the call is not 411c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // eligible (no RET or the target rejects) the attribute is fixed to 41248abc5cf6ba6d53513034aa8c68b0a9abd748190Arnold Schwaighofer // false. The TargetLowering::IsEligibleForTailCallOptimization function 413c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // must correctly identify tail call optimizable calls. 41430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer if (!isMarkedTailCall) continue; 41530e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer if (Ret==NULL || 41630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer !TLI.IsEligibleForTailCallOptimization(OpCall, OpRet, DAG)) { 41730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer // Not eligible. Mark CALL node as non tail call. 418475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SmallVector<SDValue, 32> Ops; 419c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer unsigned idx=0; 420ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif for(SDNode::op_iterator I =OpCall.getNode()->op_begin(), 421ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif E = OpCall.getNode()->op_end(); I != E; I++, idx++) { 422c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer if (idx!=3) 423c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer Ops.push_back(*I); 42430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer else 425c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer Ops.push_back(DAG.getConstant(false, TLI.getPointerTy())); 426c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer } 427c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size()); 42830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer } else { 42930e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer // Look for tail call clobbered arguments. Emit a series of 43030e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer // copyto/copyfrom virtual register nodes to protect them. 431475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SmallVector<SDValue, 32> Ops; 432475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue Chain = OpCall.getOperand(0), InFlag; 43330e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer unsigned idx=0; 434ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif for(SDNode::op_iterator I = OpCall.getNode()->op_begin(), 435ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif E = OpCall.getNode()->op_end(); I != E; I++, idx++) { 436475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue Arg = *I; 43730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer if (idx > 4 && (idx % 2)) { 43830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer bool isByVal = cast<ARG_FLAGSSDNode>(OpCall.getOperand(idx+1))-> 43930e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer getArgFlags().isByVal(); 44030e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer MachineFunction &MF = DAG.getMachineFunction(); 44130e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer MachineFrameInfo *MFI = MF.getFrameInfo(); 44230e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer if (!isByVal && 44330e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer IsPossiblyOverwrittenArgumentOfTailCall(Arg, MFI)) { 44483ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands MVT VT = Arg.getValueType(); 44530e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer unsigned VReg = MF.getRegInfo(). 44630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer createVirtualRegister(TLI.getRegClassFor(VT)); 44730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer Chain = DAG.getCopyToReg(Chain, VReg, Arg, InFlag); 44830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer InFlag = Chain.getValue(1); 44930e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer Arg = DAG.getCopyFromReg(Chain, VReg, VT, InFlag); 45030e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer Chain = Arg.getValue(1); 45130e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer InFlag = Arg.getValue(2); 45230e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer } 45330e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer } 45430e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer Ops.push_back(Arg); 45530e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer } 45630e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer // Link in chain of CopyTo/CopyFromReg. 45730e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer Ops[0] = Chain; 45830e62c098b5841259f8026df1c5c45c7c1182a38Arnold Schwaighofer DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size()); 459c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer } 460c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer } 461c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer } 462c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer} 463c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer 464f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohmanvoid SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, 465f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman BasicBlock::iterator Begin, 4665edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman BasicBlock::iterator End) { 4677c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 468f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 469f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman MachineModuleInfo *MMI = CurDAG->getMachineModuleInfo(); 470f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 471f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (MMI && BB->isLandingPad()) { 472f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Add a label to mark the beginning of the landing pad. Deletion of the 473f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // landing pad can thus be detected via the MachineModuleInfo. 474f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman unsigned LabelID = MMI->addLandingPad(BB); 475f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->setRoot(CurDAG->getLabel(ISD::EH_LABEL, 476f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->getEntryNode(), LabelID)); 477f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 478f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Mark exception register as live in. 479f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman unsigned Reg = TLI.getExceptionAddressRegister(); 480f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (Reg) BB->addLiveIn(Reg); 481f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 482f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Mark exception selector register as live in. 483f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman Reg = TLI.getExceptionSelectorRegister(); 484f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (Reg) BB->addLiveIn(Reg); 485f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 486f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // FIXME: Hack around an exception handling flaw (PR1508): the personality 487f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // function and list of typeids logically belong to the invoke (or, if you 488f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // like, the basic block containing the invoke), and need to be associated 489f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // with it in the dwarf exception handling tables. Currently however the 490f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // information is provided by an intrinsic (eh.selector) that can be moved 491f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // to unexpected places by the optimizers: if the unwind edge is critical, 492f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // then breaking it can result in the intrinsics being in the successor of 493f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // the landing pad, not the landing pad itself. This results in exceptions 494f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // not being caught because no typeids are associated with the invoke. 495f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // This may not be the only way things can go wrong, but it is the only way 496f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // we try to work around for the moment. 497f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator()); 498f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 499f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (Br && Br->isUnconditional()) { // Critical edge? 500f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman BasicBlock::iterator I, E; 501f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I) 502f0cbcd48804961b05359ee41859bbd7774f41fe0Dan Gohman if (isa<EHSelectorInst>(I)) 503f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman break; 504f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 505f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (I == E) 506f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // No catch info found - try to extract some from the successor. 5077c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo); 508f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 509f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 510f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 511f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Lower all of the non-terminator instructions. 512f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman for (BasicBlock::iterator I = Begin; I != End; ++I) 513f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (!isa<TerminatorInst>(I)) 5147c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visit(*I); 515f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 516f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Ensure that all instructions which are used outside of their defining 517f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // blocks are available as virtual registers. Invoke is handled elsewhere. 518f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman for (BasicBlock::iterator I = Begin; I != End; ++I) 519f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (!I->use_empty() && !isa<PHINode>(I) && !isa<InvokeInst>(I)) { 5207c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman DenseMap<const Value*,unsigned>::iterator VMI =FuncInfo->ValueMap.find(I); 5217c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (VMI != FuncInfo->ValueMap.end()) 5227c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->CopyValueToVirtualRegister(I, VMI->second); 523f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 524f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 525f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Handle PHI nodes in successor blocks. 5263df24e667f04a7003342b534310919abc9c87418Dan Gohman if (End == LLVMBB->end()) { 5277c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman HandlePHINodesInSuccessorBlocks(LLVMBB); 5283df24e667f04a7003342b534310919abc9c87418Dan Gohman 5293df24e667f04a7003342b534310919abc9c87418Dan Gohman // Lower the terminator after the copies are emitted. 5303df24e667f04a7003342b534310919abc9c87418Dan Gohman SDL->visit(*LLVMBB->getTerminator()); 5313df24e667f04a7003342b534310919abc9c87418Dan Gohman } 5324198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 533a651cf67b77cd477dd7da4baa8688af2ccd4f7f6Chris Lattner // Make sure the root of the DAG is up-to-date. 5347c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getControlRoot()); 535c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer 536c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // Check whether calls in this block are real tail calls. Fix up CALL nodes 537c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // with correct tailcall attribute so that the target can rely on the tailcall 538c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // attribute indicating whether the call is really eligible for tail call 539c85e1716f0e45e4c18a9ef2fbe431a51ac3a4252Arnold Schwaighofer // optimization. 540f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CheckDAGForTailCallsAndFixThem(*CurDAG, TLI); 541f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 542f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Final step, emit the lowered DAG as machine code. 543f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 5447c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 5451c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner} 5461c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 547f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohmanvoid SelectionDAGISel::ComputeLiveOutVRegInfo() { 548ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner SmallPtrSet<SDNode*, 128> VisitedNodes; 549ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner SmallVector<SDNode*, 128> Worklist; 550ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 551ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif Worklist.push_back(CurDAG->getRoot().getNode()); 552ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 553ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner APInt Mask; 554ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner APInt KnownZero; 555ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner APInt KnownOne; 556ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 557ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner while (!Worklist.empty()) { 558ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner SDNode *N = Worklist.back(); 559ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner Worklist.pop_back(); 560ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 561ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner // If we've already seen this node, ignore it. 562ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (!VisitedNodes.insert(N)) 563ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner continue; 564ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 565ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner // Otherwise, add all chain operands to the worklist. 566ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 567ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (N->getOperand(i).getValueType() == MVT::Other) 568ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif Worklist.push_back(N->getOperand(i).getNode()); 569ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 570ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner // If this is a CopyToReg with a vreg dest, process it. 571ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (N->getOpcode() != ISD::CopyToReg) 572ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner continue; 573ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 574ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg(); 575ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (!TargetRegisterInfo::isVirtualRegister(DestReg)) 576ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner continue; 577ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 578ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner // Ignore non-scalar or non-integer values. 579475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue Src = N->getOperand(2); 580ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner MVT SrcVT = Src.getValueType(); 581ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (!SrcVT.isInteger() || SrcVT.isVector()) 582ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner continue; 583ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 584f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src); 585ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits()); 586f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne); 587ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 588ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner // Only install this information if it tells us something. 589ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) { 590ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner DestReg -= TargetRegisterInfo::FirstVirtualRegister; 591f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman FunctionLoweringInfo &FLI = CurDAG->getFunctionLoweringInfo(); 592ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner if (DestReg >= FLI.LiveOutRegInfo.size()) 593ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner FLI.LiveOutRegInfo.resize(DestReg+1); 594ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[DestReg]; 595ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner LOI.NumSignBits = NumSignBits; 596ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner LOI.KnownOne = NumSignBits; 597ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner LOI.KnownZero = NumSignBits; 598ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner } 599ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner } 600ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner} 601ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 602f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohmanvoid SelectionDAGISel::CodeGenAndEmitDAG() { 603462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman std::string GroupName; 604462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman if (TimePassesIsEnabled) 605462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman GroupName = "Instruction Selection and Scheduling"; 606462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman std::string BlockName; 607462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs || 608462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman ViewDAGCombine2 || ViewISelDAGs || ViewSchedDAGs || ViewSUnitDAGs) 609f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman BlockName = CurDAG->getMachineFunction().getFunction()->getName() + ':' + 610462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman BB->getBasicBlock()->getName(); 611462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 612462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman DOUT << "Initial selection DAG:\n"; 613f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 614462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 615f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName); 616417e11b9bf625b3626f8765d44248927fb200906Dan Gohman 617af21d55aee8d6852fedfd630395a3c7c95df8f12Chris Lattner // Run the DAG combiner in pre-legalize mode. 618ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng if (TimePassesIsEnabled) { 6195e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("DAG Combining 1", GroupName); 620f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Combine(false, *AA, Fast); 621ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } else { 622f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Combine(false, *AA, Fast); 623ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } 6242300f5504643eaddc307d3db8a3ccd224c4fa251Nate Begeman 625417e11b9bf625b3626f8765d44248927fb200906Dan Gohman DOUT << "Optimized lowered selection DAG:\n"; 626f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 627f00e74f4d64385e6b2ee29887114e7c8abdf1f17Duncan Sands 6281c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner // Second step, hack on the DAG until it only uses operations and types that 6291c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner // the target supports. 630f00e74f4d64385e6b2ee29887114e7c8abdf1f17Duncan Sands if (EnableLegalizeTypes) {// Enable this some day. 631f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " + 632f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman BlockName); 633462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 634462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman if (TimePassesIsEnabled) { 635462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman NamedRegionTimer T("Type Legalization", GroupName); 636f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->LegalizeTypes(); 637462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman } else { 638f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->LegalizeTypes(); 639462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman } 640462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 641462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman DOUT << "Type-legalized selection DAG:\n"; 642f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 643462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 64470587ea813986bb0dbef71610091d496e28c22a6Chris Lattner // TODO: enable a dag combine pass here. 64570587ea813986bb0dbef71610091d496e28c22a6Chris Lattner } 646f00e74f4d64385e6b2ee29887114e7c8abdf1f17Duncan Sands 647f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName); 648462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 649ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng if (TimePassesIsEnabled) { 6505e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("DAG Legalization", GroupName); 651f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Legalize(); 652ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } else { 653f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Legalize(); 654ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } 655f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman 656832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "Legalized selection DAG:\n"; 657f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 658f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman 659f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName); 660462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 661af21d55aee8d6852fedfd630395a3c7c95df8f12Chris Lattner // Run the DAG combiner in post-legalize mode. 662ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng if (TimePassesIsEnabled) { 6635e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("DAG Combining 2", GroupName); 664f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Combine(true, *AA, Fast); 665ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } else { 666f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CurDAG->Combine(true, *AA, Fast); 667ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } 6682300f5504643eaddc307d3db8a3ccd224c4fa251Nate Begeman 669417e11b9bf625b3626f8765d44248927fb200906Dan Gohman DOUT << "Optimized legalized selection DAG:\n"; 670f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 671417e11b9bf625b3626f8765d44248927fb200906Dan Gohman 672f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName); 673ead0d88ad7659dabd66cc3149af97d98256fca84Chris Lattner 674925a7e8ed6522f291b4ae559ccfa56db461016e3Dan Gohman if (!Fast && EnableValueProp) 675f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman ComputeLiveOutVRegInfo(); 676552c4a849422ad91fa9988255ae35aebbf3acf7bEvan Cheng 677a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner // Third, instruction select all of the operations to machine code, adding the 678a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner // code to the MachineBasicBlock. 679ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng if (TimePassesIsEnabled) { 6805e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("Instruction Selection", GroupName); 681f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman InstructionSelect(); 682ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } else { 683f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman InstructionSelect(); 684ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } 685db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng 686462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman DOUT << "Selected selection DAG:\n"; 687f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(CurDAG->dump()); 688462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 689f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName); 690462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 6915e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman // Schedule machine code. 6925e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman ScheduleDAG *Scheduler; 6935e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman if (TimePassesIsEnabled) { 6945e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("Instruction Scheduling", GroupName); 695f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman Scheduler = Schedule(); 6965e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman } else { 697f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman Scheduler = Schedule(); 6985e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman } 6995e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman 700462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman if (ViewSUnitDAGs) Scheduler->viewGraph(); 701462dc7f4960e5074ddf4769ec8b2ef1ba7a4d2c8Dan Gohman 702db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng // Emit machine code to BB. This can change 'BB' to the last block being 703db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng // inserted into. 704ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng if (TimePassesIsEnabled) { 7055e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("Instruction Creation", GroupName); 7065e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman BB = Scheduler->EmitSchedule(); 707ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } else { 7085e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman BB = Scheduler->EmitSchedule(); 7095e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman } 7105e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman 7115e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman // Free the scheduler state. 7125e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman if (TimePassesIsEnabled) { 7135e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName); 7145e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman delete Scheduler; 7155e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman } else { 7165e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman delete Scheduler; 717ebffb660a68384dd8b5e2ff36d68e94a3920611bEvan Cheng } 718db8d56b825efeb576d67b9dbe39d736d93306222Evan Cheng 719832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "Selected machine code:\n"; 7201c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner DEBUG(BB->dump()); 721f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman} 722f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman 7237c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohmanvoid SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF) { 72439fd6e81b1b0de8b820155dc6a0dae226c109de6Evan Cheng for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { 72539fd6e81b1b0de8b820155dc6a0dae226c109de6Evan Cheng BasicBlock *LLVMBB = &*I; 7267c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = FuncInfo->MBBMap[LLVMBB]; 727f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 7283df24e667f04a7003342b534310919abc9c87418Dan Gohman BasicBlock::iterator const Begin = LLVMBB->begin(); 7293df24e667f04a7003342b534310919abc9c87418Dan Gohman BasicBlock::iterator const End = LLVMBB->end(); 7309f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng BasicBlock::iterator BI = Begin; 7315edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman 7325edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman // Lower any arguments needed in this block if this is the entry block. 7335edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman if (LLVMBB == &Fn.getEntryBlock()) 7345edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman LowerArguments(LLVMBB); 735f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 736f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Before doing SelectionDAG ISel, see if FastISel has been requested. 737f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // FastISel doesn't support EH landing pads, which require special handling. 738f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (EnableFastISel && !BB->isLandingPad()) { 7393df24e667f04a7003342b534310919abc9c87418Dan Gohman if (FastISel *F = TLI.createFastISel(*FuncInfo->MF, FuncInfo->ValueMap, 7400586d91bb3e516d5826826522d9a90ed6ef74d86Dan Gohman FuncInfo->MBBMap, 7410586d91bb3e516d5826826522d9a90ed6ef74d86Dan Gohman FuncInfo->StaticAllocaMap)) { 7425edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman // Emit code for any incoming arguments. This must happen before 7435edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman // beginning FastISel on the entry block. 7445edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman if (LLVMBB == &Fn.getEntryBlock()) { 7455edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman CurDAG->setRoot(SDL->getControlRoot()); 7465edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman CodeGenAndEmitDAG(); 7475edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman SDL->clear(); 7485edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman } 7493df24e667f04a7003342b534310919abc9c87418Dan Gohman F->setCurrentBlock(BB); 7505edd361497f4c78a20fcbb75c6e7e94ff8046ed1Dan Gohman // Do FastISel on as many instructions as possible. 7519f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng for (; BI != End; ++BI) { 7523df24e667f04a7003342b534310919abc9c87418Dan Gohman // Just before the terminator instruction, insert instructions to 7533df24e667f04a7003342b534310919abc9c87418Dan Gohman // feed PHI nodes in successor blocks. 754a8657e3587eb71eb920c4f0d7d4baa58f33a277dDan Gohman if (isa<TerminatorInst>(BI)) 7553df24e667f04a7003342b534310919abc9c87418Dan Gohman if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, F)) { 7564344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman if (EnableFastISelVerbose || EnableFastISelAbort) { 757293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman cerr << "FastISel miss: "; 758293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman BI->dump(); 759293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman } 7604344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman if (EnableFastISelAbort) 761293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman assert(0 && "FastISel didn't handle a PHI in a successor"); 7623ee25dca5b2f321103e879fb125b7870683e7085Dan Gohman break; 7633df24e667f04a7003342b534310919abc9c87418Dan Gohman } 764f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 7653df24e667f04a7003342b534310919abc9c87418Dan Gohman // First try normal tablegen-generated "fast" selection. 7669f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng if (F->SelectInstruction(BI)) 7673df24e667f04a7003342b534310919abc9c87418Dan Gohman continue; 768f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 76999b218218c0ca3ebfdd568ddfeafa07842e9d69dDan Gohman // Next, try calling the target to attempt to handle the instruction. 7709f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng if (F->TargetSelectInstruction(BI)) 77199b218218c0ca3ebfdd568ddfeafa07842e9d69dDan Gohman continue; 77299b218218c0ca3ebfdd568ddfeafa07842e9d69dDan Gohman 7733df24e667f04a7003342b534310919abc9c87418Dan Gohman // Then handle certain instructions as single-LLVM-Instruction blocks. 774cf01f7a78c18224866595b4b493d03a3de305e1fDan Gohman if (isa<CallInst>(BI)) { 7759f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng if (BI->getType() != Type::VoidTy) { 776a8657e3587eb71eb920c4f0d7d4baa58f33a277dDan Gohman unsigned &R = FuncInfo->ValueMap[BI]; 777f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (!R) 7789f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng R = FuncInfo->CreateRegForValue(BI); 779f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 780f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 7819f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng SelectBasicBlock(LLVMBB, BI, next(BI)); 782f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman continue; 783f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 784f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 785293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman // Otherwise, give up on FastISel for the rest of the block. 786293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman // For now, be a little lenient about non-branch terminators. 787293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman if (!isa<TerminatorInst>(BI) || isa<BranchInst>(BI)) { 7884344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman if (EnableFastISelVerbose || EnableFastISelAbort) { 789293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman cerr << "FastISel miss: "; 790293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman BI->dump(); 791293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman } 7924344a5d0d7b280f0b891e0e6a4413b059d9080b3Dan Gohman if (EnableFastISelAbort) 793293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman // The "fast" selector couldn't handle something and bailed. 794293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman // For the purpose of debugging, just abort. 795293d5f8bc02a9148238b2c79484637f56de65b9cDan Gohman assert(0 && "FastISel didn't select the entire block"); 796f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 797f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman break; 798f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 799f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman delete F; 800f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 801f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman } 802f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 803d2ff647964ed242e67ac12f7d21a58c864309d95Dan Gohman // Run SelectionDAG instruction selection on the remainder of the block 804d2ff647964ed242e67ac12f7d21a58c864309d95Dan Gohman // not handled by FastISel. If FastISel is not run, this is the entire 8053df24e667f04a7003342b534310919abc9c87418Dan Gohman // block. 8069f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng if (BI != End) 8079f1185076d60153fd35feb3cadb1b4cd8debc0b6Evan Cheng SelectBasicBlock(LLVMBB, BI, End); 808381cb07544a2bc119e39969d7d508a6247773e1cEvan Cheng 8097c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman FinishBasicBlock(); 81039fd6e81b1b0de8b820155dc6a0dae226c109de6Evan Cheng } 8110e5f1306b059b62d7725f324e087efbc8e7a782dDan Gohman} 8120e5f1306b059b62d7725f324e087efbc8e7a782dDan Gohman 813fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanvoid 8147c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan GohmanSelectionDAGISel::FinishBasicBlock() { 8151c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner 816f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman // Perform target specific isel post processing. 817f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman InstructionSelectPostProcessing(); 818f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 819f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DOUT << "Target-post-processed machine code:\n"; 820f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman DEBUG(BB->dump()); 8214198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8224198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov DOUT << "Total amount of phi nodes to update: " 8237c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman << SDL->PHINodesToUpdate.size() << "\n"; 8247c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman DEBUG(for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) 8257c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman DOUT << "Node " << i << " : (" << SDL->PHINodesToUpdate[i].first 8267c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman << ", " << SDL->PHINodesToUpdate[i].second << ")\n";); 827f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman 828a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner // Next, now that we know what the last MBB the LLVM BB expanded is, update 8291c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner // PHI nodes in successors. 8307c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (SDL->SwitchCases.empty() && 8317c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->JTCases.empty() && 8327c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases.empty()) { 8337c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) { 8347c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman MachineInstr *PHI = SDL->PHINodesToUpdate[i].first; 835f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman assert(PHI->getOpcode() == TargetInstrInfo::PHI && 836f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman "This is not a machine PHI node that we are updating!"); 8377c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second, 8389ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 8399ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner PHI->addOperand(MachineOperand::CreateMBB(BB)); 840f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman } 8417c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->PHINodesToUpdate.clear(); 842f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman return; 8431c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner } 8444198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8457c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned i = 0, e = SDL->BitTestCases.size(); i != e; ++i) { 8464198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Lower header first, if it wasn't already lowered 8477c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (!SDL->BitTestCases[i].Emitted) { 8484198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Set the current basic block to the mbb we wish to insert the code into 8497c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = SDL->BitTestCases[i].Parent; 8507c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 8514198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Emit the code 8527c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitBitTestHeader(SDL->BitTestCases[i]); 8537c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getRoot()); 854f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 8557c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 8564198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 8574198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8587c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); j != ej; ++j) { 8594198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Set the current basic block to the mbb we wish to insert the code into 8607c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = SDL->BitTestCases[i].Cases[j].ThisBB; 8617c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 8624198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Emit the code 8634198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov if (j+1 != ej) 8647c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitBitTestCase(SDL->BitTestCases[i].Cases[j+1].ThisBB, 8657c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases[i].Reg, 8667c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases[i].Cases[j]); 8674198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov else 8687c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitBitTestCase(SDL->BitTestCases[i].Default, 8697c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases[i].Reg, 8707c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases[i].Cases[j]); 8714198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8724198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8737c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getRoot()); 874f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 8757c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 8764198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 8774198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 8784198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // Update PHI Nodes 8797c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) { 8807c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first; 8814198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov MachineBasicBlock *PHIBB = PHI->getParent(); 8824198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov assert(PHI->getOpcode() == TargetInstrInfo::PHI && 8834198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov "This is not a machine PHI node that we are updating!"); 8844198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // This is "default" BB. We have two jumps to it. From "header" BB and 8854198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // from last "case" BB. 8867c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (PHIBB == SDL->BitTestCases[i].Default) { 8877c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 8889ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 8897c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Parent)); 8907c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 8919ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 8927c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Cases. 8939ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner back().ThisBB)); 8944198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 8954198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // One of "cases" BB. 8967c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); 8977c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman j != ej; ++j) { 8987c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman MachineBasicBlock* cBB = SDL->BitTestCases[i].Cases[j].ThisBB; 8994198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov if (cBB->succ_end() != 9004198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) { 9017c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 9029ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 9039ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner PHI->addOperand(MachineOperand::CreateMBB(cBB)); 9044198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9054198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9064198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9074198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9087c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->BitTestCases.clear(); 9094198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov 9109453eea49bca1c3904047db495855c93e001d1cdNate Begeman // If the JumpTable record is filled in, then we need to emit a jump table. 9119453eea49bca1c3904047db495855c93e001d1cdNate Begeman // Updating the PHI nodes is tricky in this case, since we need to determine 9129453eea49bca1c3904047db495855c93e001d1cdNate Begeman // whether the PHI is a successor of the range check MBB or the jump table MBB 9137c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned i = 0, e = SDL->JTCases.size(); i != e; ++i) { 9143a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov // Lower header first, if it wasn't already lowered 9157c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (!SDL->JTCases[i].first.Emitted) { 9163a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov // Set the current basic block to the mbb we wish to insert the code into 9177c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = SDL->JTCases[i].first.HeaderBB; 9187c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 9193a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov // Emit the code 9207c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitJumpTableHeader(SDL->JTCases[i].second, SDL->JTCases[i].first); 9217c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getRoot()); 922f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 9237c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 9244198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov } 9253a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov 92637efe6764568a3829fee26aba532283131d1a104Nate Begeman // Set the current basic block to the mbb we wish to insert the code into 9277c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = SDL->JTCases[i].second.MBB; 9287c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 92937efe6764568a3829fee26aba532283131d1a104Nate Begeman // Emit the code 9307c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitJumpTable(SDL->JTCases[i].second); 9317c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getRoot()); 932f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 9337c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 9343a84b9baf67c938454840d10d9e53269c755cd3eAnton Korobeynikov 93537efe6764568a3829fee26aba532283131d1a104Nate Begeman // Update PHI Nodes 9367c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) { 9377c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first; 93837efe6764568a3829fee26aba532283131d1a104Nate Begeman MachineBasicBlock *PHIBB = PHI->getParent(); 93937efe6764568a3829fee26aba532283131d1a104Nate Begeman assert(PHI->getOpcode() == TargetInstrInfo::PHI && 94037efe6764568a3829fee26aba532283131d1a104Nate Begeman "This is not a machine PHI node that we are updating!"); 9414198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // "default" BB. We can go there only from header BB. 9427c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (PHIBB == SDL->JTCases[i].second.Default) { 9437c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 9449ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 9457c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateMBB(SDL->JTCases[i].first.HeaderBB)); 946f4360a478944af45d5f851a0903fbbfa44f520dcNate Begeman } 9474198c58c716cbe4516ac3a1a407a3cd52548bc3bAnton Korobeynikov // JT BB. Just iterate over successors here 948f4360a478944af45d5f851a0903fbbfa44f520dcNate Begeman if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) { 9497c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 9509ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 9519ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner PHI->addOperand(MachineOperand::CreateMBB(BB)); 95237efe6764568a3829fee26aba532283131d1a104Nate Begeman } 95337efe6764568a3829fee26aba532283131d1a104Nate Begeman } 95437efe6764568a3829fee26aba532283131d1a104Nate Begeman } 9557c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->JTCases.clear(); 95637efe6764568a3829fee26aba532283131d1a104Nate Begeman 957b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner // If the switch block involved a branch to one of the actual successors, we 958b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner // need to update PHI nodes in that block. 9597c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) { 9607c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman MachineInstr *PHI = SDL->PHINodesToUpdate[i].first; 961b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner assert(PHI->getOpcode() == TargetInstrInfo::PHI && 962b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner "This is not a machine PHI node that we are updating!"); 963b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner if (BB->isSuccessor(PHI->getParent())) { 9647c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second, 9659ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner false)); 9669ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner PHI->addOperand(MachineOperand::CreateMBB(BB)); 967b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner } 968b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner } 969b2e806eecd85c98367f038817e742ef183dd9f87Chris Lattner 970f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman // If we generated any switch lowering information, build and codegen any 971f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman // additional DAGs necessary. 9727c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman for (unsigned i = 0, e = SDL->SwitchCases.size(); i != e; ++i) { 973f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman // Set the current basic block to the mbb we wish to insert the code into 9747c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman BB = SDL->SwitchCases[i].ThisBB; 9757c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->setCurrentBasicBlock(BB); 976d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner 977f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman // Emit the code 9787c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->visitSwitchCase(SDL->SwitchCases[i]); 9797c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman CurDAG->setRoot(SDL->getRoot()); 980f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman CodeGenAndEmitDAG(); 9817c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->clear(); 982d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner 983d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // Handle any PHI nodes in successors of this chunk, as if we were coming 984d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // from the original BB before switch expansion. Note that PHI nodes can 985d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // occur multiple times in PHINodesToUpdate. We have to be very careful to 986d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // handle them the right number of times. 9877c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman while ((BB = SDL->SwitchCases[i].TrueBB)) { // Handle LHS and RHS. 988d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner for (MachineBasicBlock::iterator Phi = BB->begin(); 989d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){ 990d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // This value for this PHI node is recorded in PHINodesToUpdate, get it. 991d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner for (unsigned pn = 0; ; ++pn) { 9927c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman assert(pn != SDL->PHINodesToUpdate.size() && 9937c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman "Didn't find PHI entry!"); 9947c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (SDL->PHINodesToUpdate[pn].first == Phi) { 9957c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman Phi->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pn]. 9969ce2e9d5a07cb3e0176cb32838231243829d67c5Chris Lattner second, false)); 9977c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman Phi->addOperand(MachineOperand::CreateMBB(SDL->SwitchCases[i].ThisBB)); 998d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner break; 999d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner } 1000d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner } 1001f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman } 1002d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner 1003d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // Don't process RHS if same block as LHS. 10047c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman if (BB == SDL->SwitchCases[i].FalseBB) 10057c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->SwitchCases[i].FalseBB = 0; 1006d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner 1007d5e93c07957844e3086fb12d686b93dbbd2524c2Chris Lattner // If we haven't handled the RHS, do so now. Otherwise, we're done. 10087c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->SwitchCases[i].TrueBB = SDL->SwitchCases[i].FalseBB; 10097c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->SwitchCases[i].FalseBB = 0; 1010f15485a8d0dff5f720b7ad27346129ac5c3ec503Nate Begeman } 10117c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman assert(SDL->SwitchCases[i].TrueBB == 0 && SDL->SwitchCases[i].FalseBB == 0); 1012a33ef4816d2c192e36e7c025d18c66e89ef9d311Chris Lattner } 10137c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->SwitchCases.clear(); 10147c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman 10157c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman SDL->PHINodesToUpdate.clear(); 10161c08c714bb3d07c3b39f06bfcbb4559fefca73f9Chris Lattner} 1017a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 101813ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey 10195e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman/// Schedule - Pick a safe ordering for instructions for each 1020a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng/// target node in the graph. 10215e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman/// 1022f350b277f32d7d47f86c0e54f4aec4d470500618Dan GohmanScheduleDAG *SelectionDAGISel::Schedule() { 1023eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault(); 102413ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey 102513ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey if (!Ctor) { 1026eb577ba3b815a1fa4627b060dd2345d17abf672dJim Laskey Ctor = ISHeuristic; 10279373beba6010dd34316a801c3a9b37ab9e048031Jim Laskey RegisterScheduler::setDefault(Ctor); 10284ef10867499aa146cd819c78d8d37a8353d4f0ffEvan Cheng } 102913ec702c430b91ee49b9e6d9581cd95412f216c8Jim Laskey 1030f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman ScheduleDAG *Scheduler = Ctor(this, CurDAG, BB, Fast); 10315e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman Scheduler->Run(); 10323e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 10335e84368b26415b3bb7f3f8d9cff3e05938dd82d0Dan Gohman return Scheduler; 1034a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng} 10350e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 103603fc53c174e654adae4e42a0c352c7937de2cd87Chris Lattner 10379ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim LaskeyHazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() { 10389ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey return new HazardRecognizer(); 10399ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey} 10409ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey 1041755480681c795d585c73556c028b6143c46bda86Chris Lattner//===----------------------------------------------------------------------===// 1042755480681c795d585c73556c028b6143c46bda86Chris Lattner// Helper functions used by the generated instruction selector. 1043755480681c795d585c73556c028b6143c46bda86Chris Lattner//===----------------------------------------------------------------------===// 1044755480681c795d585c73556c028b6143c46bda86Chris Lattner// Calls to these methods are generated by tblgen. 1045755480681c795d585c73556c028b6143c46bda86Chris Lattner 1046755480681c795d585c73556c028b6143c46bda86Chris Lattner/// CheckAndMask - The isel is trying to match something like (and X, 255). If 1047755480681c795d585c73556c028b6143c46bda86Chris Lattner/// the dag combiner simplified the 255, we still want to match. RHS is the 1048755480681c795d585c73556c028b6143c46bda86Chris Lattner/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value 1049755480681c795d585c73556c028b6143c46bda86Chris Lattner/// specified in the .td file (e.g. 255). 1050475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanbool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS, 1051dc9b3d0bb5ed3a3f59cad61e264f0ec43c946459Dan Gohman int64_t DesiredMaskS) const { 10522e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman const APInt &ActualMask = RHS->getAPIntValue(); 10532e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 1054755480681c795d585c73556c028b6143c46bda86Chris Lattner 1055755480681c795d585c73556c028b6143c46bda86Chris Lattner // If the actual mask exactly matches, success! 1056755480681c795d585c73556c028b6143c46bda86Chris Lattner if (ActualMask == DesiredMask) 1057755480681c795d585c73556c028b6143c46bda86Chris Lattner return true; 1058755480681c795d585c73556c028b6143c46bda86Chris Lattner 1059755480681c795d585c73556c028b6143c46bda86Chris Lattner // If the actual AND mask is allowing unallowed bits, this doesn't match. 10602e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman if (ActualMask.intersects(~DesiredMask)) 1061755480681c795d585c73556c028b6143c46bda86Chris Lattner return false; 1062755480681c795d585c73556c028b6143c46bda86Chris Lattner 1063755480681c795d585c73556c028b6143c46bda86Chris Lattner // Otherwise, the DAG Combiner may have proven that the value coming in is 1064755480681c795d585c73556c028b6143c46bda86Chris Lattner // either already zero or is not demanded. Check for known zero input bits. 10652e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman APInt NeededMask = DesiredMask & ~ActualMask; 1066ea859be53ca13a1547c4675549946b74dc3c6f41Dan Gohman if (CurDAG->MaskedValueIsZero(LHS, NeededMask)) 1067755480681c795d585c73556c028b6143c46bda86Chris Lattner return true; 1068755480681c795d585c73556c028b6143c46bda86Chris Lattner 1069755480681c795d585c73556c028b6143c46bda86Chris Lattner // TODO: check to see if missing bits are just not demanded. 1070755480681c795d585c73556c028b6143c46bda86Chris Lattner 1071755480681c795d585c73556c028b6143c46bda86Chris Lattner // Otherwise, this pattern doesn't match. 1072755480681c795d585c73556c028b6143c46bda86Chris Lattner return false; 1073755480681c795d585c73556c028b6143c46bda86Chris Lattner} 1074755480681c795d585c73556c028b6143c46bda86Chris Lattner 1075755480681c795d585c73556c028b6143c46bda86Chris Lattner/// CheckOrMask - The isel is trying to match something like (or X, 255). If 1076755480681c795d585c73556c028b6143c46bda86Chris Lattner/// the dag combiner simplified the 255, we still want to match. RHS is the 1077755480681c795d585c73556c028b6143c46bda86Chris Lattner/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value 1078755480681c795d585c73556c028b6143c46bda86Chris Lattner/// specified in the .td file (e.g. 255). 1079475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanbool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS, 10802e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman int64_t DesiredMaskS) const { 10812e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman const APInt &ActualMask = RHS->getAPIntValue(); 10822e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 1083755480681c795d585c73556c028b6143c46bda86Chris Lattner 1084755480681c795d585c73556c028b6143c46bda86Chris Lattner // If the actual mask exactly matches, success! 1085755480681c795d585c73556c028b6143c46bda86Chris Lattner if (ActualMask == DesiredMask) 1086755480681c795d585c73556c028b6143c46bda86Chris Lattner return true; 1087755480681c795d585c73556c028b6143c46bda86Chris Lattner 1088755480681c795d585c73556c028b6143c46bda86Chris Lattner // If the actual AND mask is allowing unallowed bits, this doesn't match. 10892e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman if (ActualMask.intersects(~DesiredMask)) 1090755480681c795d585c73556c028b6143c46bda86Chris Lattner return false; 1091755480681c795d585c73556c028b6143c46bda86Chris Lattner 1092755480681c795d585c73556c028b6143c46bda86Chris Lattner // Otherwise, the DAG Combiner may have proven that the value coming in is 1093755480681c795d585c73556c028b6143c46bda86Chris Lattner // either already zero or is not demanded. Check for known zero input bits. 10942e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman APInt NeededMask = DesiredMask & ~ActualMask; 1095755480681c795d585c73556c028b6143c46bda86Chris Lattner 10962e68b6f52d0979575b2f02ed29717d907ba0684cDan Gohman APInt KnownZero, KnownOne; 1097ea859be53ca13a1547c4675549946b74dc3c6f41Dan Gohman CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne); 1098755480681c795d585c73556c028b6143c46bda86Chris Lattner 1099755480681c795d585c73556c028b6143c46bda86Chris Lattner // If all the missing bits in the or are already known to be set, match! 1100755480681c795d585c73556c028b6143c46bda86Chris Lattner if ((NeededMask & KnownOne) == NeededMask) 1101755480681c795d585c73556c028b6143c46bda86Chris Lattner return true; 1102755480681c795d585c73556c028b6143c46bda86Chris Lattner 1103755480681c795d585c73556c028b6143c46bda86Chris Lattner // TODO: check to see if missing bits are just not demanded. 1104755480681c795d585c73556c028b6143c46bda86Chris Lattner 1105755480681c795d585c73556c028b6143c46bda86Chris Lattner // Otherwise, this pattern doesn't match. 1106755480681c795d585c73556c028b6143c46bda86Chris Lattner return false; 1107755480681c795d585c73556c028b6143c46bda86Chris Lattner} 1108755480681c795d585c73556c028b6143c46bda86Chris Lattner 11099ff542f2cce5bf7bf3cf9f692cf3ec0690ad2b3bJim Laskey 11100e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 11110e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner/// by tblgen. Others should not call it. 11120e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattnervoid SelectionDAGISel:: 1113f350b277f32d7d47f86c0e54f4aec4d470500618Dan GohmanSelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) { 1114475871a144eb604ddaf37503397ba0941442e5fbDan Gohman std::vector<SDValue> InOps; 11150e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner std::swap(InOps, Ops); 11160e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 11170e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner Ops.push_back(InOps[0]); // input chain. 11180e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner Ops.push_back(InOps[1]); // input asm string. 11190e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 11200e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner unsigned i = 2, e = InOps.size(); 11210e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner if (InOps[e-1].getValueType() == MVT::Flag) 11220e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner --e; // Don't process a flag operand if it is here. 11230e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 11240e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner while (i != e) { 11250e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue(); 11260e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner if ((Flags & 7) != 4 /*MEM*/) { 11270e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner // Just skip over this operand, copying the operands verbatim. 11280e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1); 11290e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner i += (Flags >> 3) + 1; 11300e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner } else { 11310e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner assert((Flags >> 3) == 1 && "Memory operand with multiple values?"); 11320e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner // Otherwise, this is a memory operand. Ask the target to select it. 1133475871a144eb604ddaf37503397ba0941442e5fbDan Gohman std::vector<SDValue> SelOps; 1134f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) { 1135832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << "Could not match memory address. Inline asm failure!\n"; 11360e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner exit(1); 11370e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner } 11380e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 11390e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner // Add this to the output node. 1140f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman MVT IntPtrTy = CurDAG->getTargetLoweringInfo().getPointerTy(); 1141f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman Ops.push_back(CurDAG->getTargetConstant(4/*MEM*/ | (SelOps.size() << 3), 1142f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman IntPtrTy)); 11430e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); 11440e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner i += 2; 11450e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner } 11460e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner } 11470e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner 11480e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner // Add the flag input back if present. 11490e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner if (e != InOps.size()) 11500e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner Ops.push_back(InOps.back()); 11510e43f2ba114df7bfc1f70d0ef62b663f6ea4c09dChris Lattner} 1152794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 11531997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar SelectionDAGISel::ID = 0; 1154