path: root/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp

//===-- ScheduleDAGSimple.cpp - Implement a trivial DAG scheduler ---------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by James M. Laskey and is distributed under the
// University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This implements a simple two pass scheduler.  The first pass attempts to push
// backward any lengthy instructions and critical paths.  The second pass packs
// instructions into semi-optimal time slots.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "sched"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Visibility.h"
#include <algorithm>
#include <iostream>
using namespace llvm;


namespace {

static RegisterScheduler
  bfsDAGScheduler("none", "  No scheduling: breadth first sequencing",
                  createBFS_DAGScheduler);
static RegisterScheduler
  simpleDAGScheduler("simple",
                     "  Simple two pass scheduling: minimize critical path "
                     "and maximize processor utilization",
                      createSimpleDAGScheduler);
static RegisterScheduler
  noitinDAGScheduler("simple-noitin",
                     "  Simple two pass scheduling: Same as simple "
                     "except using generic latency",
                     createNoItinsDAGScheduler);
                     
class NodeInfo;
typedef NodeInfo *NodeInfoPtr;
typedef std::vector<NodeInfoPtr>           NIVector;
typedef std::vector<NodeInfoPtr>::iterator NIIterator;

//===--------------------------------------------------------------------===//
///
/// Node group -  This struct is used to manage flagged node groups.
///
class NodeGroup {
public:
  NodeGroup     *Next;
private:
  NIVector      Members;                // Group member nodes
  NodeInfo      *Dominator;             // Node with highest latency
  unsigned      Latency;                // Total latency of the group
  int           Pending;                // Number of visits pending before
                                        // adding to order  

public:
  // Ctor.
  NodeGroup() : Next(NULL), Dominator(NULL), Pending(0) {}

  // Accessors
  inline void setDominator(NodeInfo *D) { Dominator = D; }
  inline NodeInfo *getTop() { return Members.front(); }
  inline NodeInfo *getBottom() { return Members.back(); }
  inline NodeInfo *getDominator() { return Dominator; }
  inline void setLatency(unsigned L) { Latency = L; }
  inline unsigned getLatency() { return Latency; }
  inline int getPending() const { return Pending; }
  inline void setPending(int P)  { Pending = P; }
  inline int addPending(int I)  { return Pending += I; }

  // Pass thru
  inline bool group_empty() { return Members.empty(); }
  inline NIIterator group_begin() { return Members.begin(); }
  inline NIIterator group_end() { return Members.end(); }
  inline void group_push_back(const NodeInfoPtr &NI) {
    Members.push_back(NI);
  }
  inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) {
    return Members.insert(Pos, NI);
  }
  inline void group_insert(NIIterator Pos, NIIterator First,
                           NIIterator Last)