improve "cannot yet select" errors a trivial amount: now

[oota-llvm.git] / lib / CodeGen / SplitKit.cpp

diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index fd18729b85b6479a25df42e5d94a1f246a042d71..38c94698799e2c6a147139556414163e5ae455bb 100644 (file)
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -24,6 +24,7 @@
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/GraphWriter.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
@@ -34,6 +35,52 @@ static cl::opt<bool>
 AllowSplit("spiller-splits-edges",
            cl::desc("Allow critical edge splitting during spilling"));
 
+//===----------------------------------------------------------------------===//
+//                                 Edge Bundles
+//===----------------------------------------------------------------------===//
+
+/// compute - Compute the edge bundles for MF. Bundles depend only on the CFG.
+void EdgeBundles::compute(const MachineFunction *mf) {
+  MF = mf;
+  EC.clear();
+  EC.grow(2 * MF->size());
+
+  for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E;
+       ++I) {
+    const MachineBasicBlock &MBB = *I;
+    unsigned OutE = 2 * MBB.getNumber() + 1;
+    // Join the outgoing bundle with the ingoing bundles of all successors.
+    for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),
+           SE = MBB.succ_end(); SI != SE; ++SI)
+      EC.join(OutE, 2 * (*SI)->getNumber());
+  }
+  EC.compress();
+}
+
+/// view - Visualize the annotated bipartite CFG with Graphviz.
+void EdgeBundles::view() const {
+  ViewGraph(*this, "EdgeBundles");
+}
+
+/// Specialize WriteGraph, the standard implementation won't work.
+raw_ostream &llvm::WriteGraph(raw_ostream &O, const EdgeBundles &G,
+                              bool ShortNames,
+                              const std::string &Title) {
+  const MachineFunction *MF = G.getMachineFunction();
+
+  O << "digraph {\n";
+  for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
+       I != E; ++I) {
+    unsigned BB = I->getNumber();
+    O << "\t\"BB#" << BB << "\" [ shape=box ]\n"
+      << '\t' << G.getBundle(BB, false) << " -> \"BB#" << BB << "\"\n"
+      << "\t\"BB#" << BB << "\" -> " << G.getBundle(BB, true) << '\n';
+  }
+  O << "}\n";
+  return O;
+}
+
+
 //===----------------------------------------------------------------------===//
 //                                 Split Analysis
 //===----------------------------------------------------------------------===//
@@ -325,6 +372,36 @@ const MachineLoop *SplitAnalysis::getBestSplitLoop() {
   return Best;
 }
 
+/// isBypassLoop - Return true if curli is live through Loop and has no uses
+/// inside the loop. Bypass loops are candidates for splitting because it can
+/// prevent interference inside the loop.
+bool SplitAnalysis::isBypassLoop(const MachineLoop *Loop) {
+  // If curli is live into the loop header and there are no uses in the loop, it
+  // must be live in the entire loop and live on at least one exiting edge.
+  return !usingLoops_.count(Loop) &&
+         lis_.isLiveInToMBB(*curli_, Loop->getHeader());
+}
+
+/// getBypassLoops - Get all the maximal bypass loops. These are the bypass
+/// loops whose parent is not a bypass loop.
+void SplitAnalysis::getBypassLoops(LoopPtrSet &BypassLoops) {
+  SmallVector<MachineLoop*, 8> Todo(loops_.begin(), loops_.end());
+  while (!Todo.empty()) {
+    MachineLoop *Loop = Todo.pop_back_val();
+    if (!usingLoops_.count(Loop)) {
+      // This is either a bypass loop or completely irrelevant.
+      if (lis_.isLiveInToMBB(*curli_, Loop->getHeader()))
+        BypassLoops.insert(Loop);
+      // Either way, skip the child loops.
+      continue;
+    }
+
+    // The child loops may be bypass loops.
+    Todo.append(Loop->begin(), Loop->end());
+  }
+}
+
+
 //===----------------------------------------------------------------------===//
 //                               LiveIntervalMap
 //===----------------------------------------------------------------------===//
@@ -1047,11 +1124,13 @@ void SplitEditor::splitAroundLoop(const MachineLoop *Loop) {
   // Create new live interval for the loop.
   openIntv();
 
-  // Insert copies in the predecessors.
-  for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(),
-       E = Blocks.Preds.end(); I != E; ++I) {
-    MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
-    enterIntvAtEnd(MBB);
+  // Insert copies in the predecessors if live-in to the header.
+  if (lis_.isLiveInToMBB(edit_.getParent(), Loop->getHeader())) {
+    for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(),
+           E = Blocks.Preds.end(); I != E; ++I) {
+      MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
+      enterIntvAtEnd(MBB);
+    }
   }
 
   // Switch all loop blocks.