<commit_before>//===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the ScheduleDAG class, which is used as the common
// base class for SelectionDAG-based instruction scheduler.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_SCHEDULEDAG_H
#define LLVM_CODEGEN_SCHEDULEDAG_H

#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallSet.h"

namespace llvm {
  struct InstrStage;
  struct SUnit;
  class MachineConstantPool;
  class MachineFunction;
  class MachineModuleInfo;
  class MachineRegisterInfo;
  class MachineInstr;
  class TargetRegisterInfo;
  class SelectionDAG;
  class SelectionDAGISel;
  class TargetInstrInfo;
  class TargetInstrDesc;
  class TargetLowering;
  class TargetMachine;
  class TargetRegisterClass;

  /// HazardRecognizer - This determines whether or not an instruction can be
  /// issued this cycle, and whether or not a noop needs to be inserted to handle
  /// the hazard.
  class HazardRecognizer {
  public:
    virtual ~HazardRecognizer();
    
    enum HazardType {
      NoHazard,      // This instruction can be emitted at this cycle.
      Hazard,        // This instruction can't be emitted at this cycle.
      NoopHazard     // This instruction can't be emitted, and needs noops.
    };
    
    /// getHazardType - Return the hazard type of emitting this node.  There are
    /// three possible results.  Either:
    ///  * NoHazard: it is legal to issue this instruction on this cycle.
    ///  * Hazard: issuing this instruction would stall the machine.  If some
    ///     other instruction is available, issue it first.
    ///  * NoopHazard: issuing this instruction would break the program.  If
    ///     some other instruction can be issued, do so, otherwise issue a noop.
    virtual HazardType getHazardType(SDNode *) {
      return NoHazard;
    }
    
    /// EmitInstruction - This callback is invoked when an instruction is
    /// emitted, to advance the hazard state.
    virtual void EmitInstruction(SDNode *) {}
    
    /// AdvanceCycle - This callback is invoked when no instructions can be
    /// issued on this cycle without a hazard.  This should increment the
    /// internal state of the hazard recognizer so that previously "Hazard"
    /// instructions will now not be hazards.
    virtual void AdvanceCycle() {}
    
    /// EmitNoop - This callback is invoked when a noop was added to the
    /// instruction stream.
    virtual void EmitNoop() {}
  };

  /// SDep - Scheduling dependency. It keeps track of dependent nodes,
  /// cost of the depdenency, etc.
  struct SDep {
    SUnit    *Dep;           // Dependent - either a predecessor or a successor.
    unsigned  Reg;           // If non-zero, this dep is a phy register dependency.
    int       Cost;          // Cost of the dependency.
    bool      isCtrl    : 1; // True iff it's a control dependency.
    bool      isSpecial : 1; // True iff it's a special ctrl dep added during sched.
    SDep(SUnit *d, unsigned r, int t, bool c, bool s)
      : Dep(d), Reg(r), Cost(t), isCtrl(c), isSpecial(s) {}
  };

  /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
  /// a group of nodes flagged together.
  struct SUnit {
  private:
    SDNode *Node;                       // Representative node.
    MachineInstr *Instr;                // Alternatively, a MachineInstr.
  public:
    SUnit *OrigNode;                    // If not this, the node from which
                                        // this node was cloned.
    
    // Preds/Succs - The SUnits before/after us in the graph.  The boolean value
    // is true if the edge is a token chain edge, false if it is a value edge. 
    SmallVector<SDep, 4> Preds;  // All sunit predecessors.
    SmallVector<SDep, 4> Succs;  // All sunit successors.

    typedef SmallVector<SDep, 4>::iterator pred_iterator;
    typedef SmallVector<SDep, 4>::iterator succ_iterator;
    typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator;
    typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator;
    
    unsigned NodeNum;                   // Entry # of node in the node vector.
    unsigned NodeQueueId;               // Queue id of node.
    unsigned short Latency;             // Node latency.
    short NumPreds;                     // # of non-control preds.
    short NumSuccs;                     // # of non-control sucss.
    short NumPredsLeft;                 // # of preds not scheduled.
    short NumSuccsLeft;                 // # of succs not scheduled.
    bool isTwoAddress     : 1;          // Is a two-address instruction.
    bool isCommutable     : 1;          // Is a commutable instruction.
    bool hasPhysRegDefs   : 1;          // Has physreg defs that are being used.
    bool isPending        : 1;          // True once pending.
    bool isAvailable      : 1;          // True once available.
    bool isScheduled      : 1;          // True once scheduled.
    unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
    unsigned Cycle;                     // Once scheduled, the cycle of the op.
    unsigned Depth;                     // Node depth;
    unsigned Height;                    // Node height;
    const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null.
    const TargetRegisterClass *CopySrcRC;
    
    /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent
    /// an SDNode and any nodes flagged to it.
    SUnit(SDNode *node, unsigned nodenum)
      : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
        Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
        isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
        isPending(false), isAvailable(false), isScheduled(false),
        CycleBound(0), Cycle(0), Depth(0), Height(0),
        CopyDstRC(NULL), CopySrcRC(NULL) {}

    /// SUnit - Construct an SUnit for post-regalloc scheduling to represent
    /// a MachineInstr.
    SUnit(MachineInstr *instr, unsigned nodenum)
      : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
        Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
        isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
        isPending(false), isAvailable(false), isScheduled(false),
        CycleBound(0), Cycle(0), Depth(0), Height(0),
        CopyDstRC(NULL), CopySrcRC(NULL) {}

    /// setNode - Assign the representative SDNode for this SUnit.
    /// This may be used during pre-regalloc scheduling.
    void setNode(SDNode *N) {
      assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
      Node = N;
    }

    /// getNode - Return the representative SDNode for this SUnit.
    /// This may be used during pre-regalloc scheduling.
    SDNode *getNode() const {
      assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
      return Node;
    }

    /// setInstr - Assign the instruction for the SUnit.
    /// This may be used during post-regalloc scheduling.
    void setInstr(MachineInstr *MI) {
      assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
      Instr = MI;
    }

    /// getInstr - Return the representative MachineInstr for this SUnit.
    /// This may be used during post-regalloc scheduling.
    MachineInstr *getInstr() const {
      assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
      return Instr;
    }

    /// addPred - This adds the specified node as a pred of the current node if
    /// not already.  This returns true if this is a new pred.
    bool addPred(SUnit *N, bool isCtrl, bool isSpecial,
                 unsigned PhyReg = 0, int Cost = 1) {
      for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
        if (Preds[i].Dep == N &&
            Preds[i].isCtrl == isCtrl && Preds[i].isSpecial == isSpecial)
          return false;
      Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isSpecial));
      N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl, isSpecial));
      if (!isCtrl) {
        ++NumPreds;
        ++N->NumSuccs;
      }
      if (!N->isScheduled)
        ++NumPredsLeft;
      if (!isScheduled)
        ++N->NumSuccsLeft;
      return true;
    }

    bool removePred(SUnit *N, bool isCtrl, bool isSpecial) {
      for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end();
           I != E; ++I)
        if (I->Dep == N && I->isCtrl == isCtrl && I->isSpecial == isSpecial) {
          bool FoundSucc = false;
          for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(),
                 EE = N->Succs.end(); II != EE; ++II)
            if (II->Dep == this &&
                II->isCtrl == isCtrl && II->isSpecial == isSpecial) {
              FoundSucc = true;
              N->Succs.erase(II);
              break;
            }
          assert(FoundSucc && "Mismatching preds / succs lists!");
          Preds.erase(I);
          if (!isCtrl) {
            --NumPreds;
            --N->NumSuccs;
          }
          if (!N->isScheduled)
            --NumPredsLeft;
          if (!isScheduled)
            --N->NumSuccsLeft;
          return true;
        }
      return false;
    }

    bool isPred(SUnit *N) {
      for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
        if (Preds[i].Dep == N)
          return true;
      return false;
    }
    
    bool isSucc(SUnit *N) {
      for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
        if (Succs[i].Dep == N)
          return true;
      return false;
    }
    
    void dump(const SelectionDAG *G) const;
    void dumpAll(const SelectionDAG *G) const;
  };

  //===--------------------------------------------------------------------===//
  /// SchedulingPriorityQueue - This interface is used to plug different
  /// priorities computation algorithms into the list scheduler. It implements
  /// the interface of a standard priority queue, where nodes are inserted in 
  /// arbitrary order and returned in priority order.  The computation of the
  /// priority and the representation of the queue are totally up to the
  /// implementation to decide.
  /// 
  class SchedulingPriorityQueue {
  public:
    virtual ~SchedulingPriorityQueue() {}
  
    virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
    virtual void addNode(const SUnit *SU) = 0;
    virtual void updateNode(const SUnit *SU) = 0;
    virtual void releaseState() = 0;

    virtual unsigned size() const = 0;
    virtual bool empty() const = 0;
    virtual void push(SUnit *U) = 0;
  
    virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
    virtual SUnit *pop() = 0;

    virtual void remove(SUnit *SU) = 0;

    /// ScheduledNode - As each node is scheduled, this method is invoked.  This
    /// allows the priority function to adjust the priority of related
    /// unscheduled nodes, for example.
    ///
    virtual void ScheduledNode(SUnit *) {}

    virtual void UnscheduledNode(SUnit *) {}
  };

  class ScheduleDAG {
  public:
    SelectionDAG *DAG;                    // DAG of the current basic block
    MachineBasicBlock *BB;                // Current basic block
    const TargetMachine &TM;              // Target processor
    const TargetInstrInfo *TII;           // Target instruction information
    const TargetRegisterInfo *TRI;        // Target processor register info
    TargetLowering *TLI;                  // Target lowering info
    MachineFunction *MF;                  // Machine function
    MachineRegisterInfo &MRI;             // Virtual/real register map
    MachineConstantPool *ConstPool;       // Target constant pool
    std::vector<SUnit*> Sequence;         // The schedule. Null SUnit*'s
                                          // represent noop instructions.
    std::vector<SUnit> SUnits;            // The scheduling units.
    SmallSet<SDNode*, 16> CommuteSet;     // Nodes that should be commuted.

    ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb,
                const TargetMachine &tm);

    virtual ~ScheduleDAG() {}

    /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered
    /// using 'dot'.
    ///
    void viewGraph();
  
    /// Run - perform scheduling.
    ///
    void Run();

    /// isPassiveNode - Return true if the node is a non-scheduled leaf.
    ///
    static bool isPassiveNode(SDNode *Node) {
      if (isa<ConstantSDNode>(Node))       return true;
      if (isa<ConstantFPSDNode>(Node))     return true;
      if (isa<RegisterSDNode>(Node))       return true;
      if (isa<GlobalAddressSDNode>(Node))  return true;
      if (isa<BasicBlockSDNode>(Node))     return true;
      if (isa<FrameIndexSDNode>(Node))     return true;
      if (isa<ConstantPoolSDNode>(Node))   return true;
      if (isa<JumpTableSDNode>(Node))      return true;
      if (isa<ExternalSymbolSDNode>(Node)) return true;
      if (isa<MemOperandSDNode>(Node))     return true;
      if (Node->getOpcode() == ISD::EntryToken) return true;
      return false;
    }

    /// NewSUnit - Creates a new SUnit and return a ptr to it.
    ///
    SUnit *NewSUnit(SDNode *N) {
      SUnits.push_back(SUnit(N, (unsigned)SUnits.size()));
      SUnits.back().OrigNode = &SUnits.back();
      return &SUnits.back();
    }

    /// Clone - Creates a clone of the specified SUnit. It does not copy the
    /// predecessors / successors info nor the temporary scheduling states.
    SUnit *Clone(SUnit *N);
    
    /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
    /// This SUnit graph is similar to the SelectionDAG, but represents flagged
    /// together nodes with a single SUnit.
    void BuildSchedUnits();

    /// ComputeLatency - Compute node latency.<commit_msg>Add a version of NewSUnit for creating units with MachineInstrs.<commit_after>//===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the ScheduleDAG class, which is used as the common
// base class for SelectionDAG-based instruction scheduler.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_SCHEDULEDAG_H
#define LLVM_CODEGEN_SCHEDULEDAG_H

#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallSet.h"

namespace llvm {
  struct InstrStage;
  struct SUnit;
  class MachineConstantPool;
  class MachineFunction;
  class MachineModuleInfo;
  class MachineRegisterInfo;
  class MachineInstr;
  class TargetRegisterInfo;
  class SelectionDAG;
  class SelectionDAGISel;
  class TargetInstrInfo;
  class TargetInstrDesc;
  class TargetLowering;
  class TargetMachine;
  class TargetRegisterClass;

  /// HazardRecognizer - This determines whether or not an instruction can be
  /// issued this cycle, and whether or not a noop needs to be inserted to handle
  /// the hazard.
  class HazardRecognizer {
  public:
    virtual ~HazardRecognizer();
    
    enum HazardType {
      NoHazard,      // This instruction can be emitted at this cycle.
      Hazard,        // This instruction can't be emitted at this cycle.
      NoopHazard     // This instruction can't be emitted, and needs noops.
    };
    
    /// getHazardType - Return the hazard type of emitting this node.  There are
    /// three possible results.  Either:
    ///  * NoHazard: it is legal to issue this instruction on this cycle.
    ///  * Hazard: issuing this instruction would stall the machine.  If some
    ///     other instruction is available, issue it first.
    ///  * NoopHazard: issuing this instruction would break the program.  If
    ///     some other instruction can be issued, do so, otherwise issue a noop.
    virtual HazardType getHazardType(SDNode *) {
      return NoHazard;
    }
    
    /// EmitInstruction - This callback is invoked when an instruction is
    /// emitted, to advance the hazard state.
    virtual void EmitInstruction(SDNode *) {}
    
    /// AdvanceCycle - This callback is invoked when no instructions can be
    /// issued on this cycle without a hazard.  This should increment the
    /// internal state of the hazard recognizer so that previously "Hazard"
    /// instructions will now not be hazards.
    virtual void AdvanceCycle() {}
    
    /// EmitNoop - This callback is invoked when a noop was added to the
    /// instruction stream.
    virtual void EmitNoop() {}
  };

  /// SDep - Scheduling dependency. It keeps track of dependent nodes,
  /// cost of the depdenency, etc.
  struct SDep {
    SUnit    *Dep;           // Dependent - either a predecessor or a successor.
    unsigned  Reg;           // If non-zero, this dep is a phy register dependency.
    int       Cost;          // Cost of the dependency.
    bool      isCtrl    : 1; // True iff it's a control dependency.
    bool      isSpecial : 1; // True iff it's a special ctrl dep added during sched.
    SDep(SUnit *d, unsigned r, int t, bool c, bool s)
      : Dep(d), Reg(r), Cost(t), isCtrl(c), isSpecial(s) {}
  };

  /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
  /// a group of nodes flagged together.
  struct SUnit {
  private:
    SDNode *Node;                       // Representative node.
    MachineInstr *Instr;                // Alternatively, a MachineInstr.
  public:
    SUnit *OrigNode;                    // If not this, the node from which
                                        // this node was cloned.
    
    // Preds/Succs - The SUnits before/after us in the graph.  The boolean value
    // is true if the edge is a token chain edge, false if it is a value edge. 
    SmallVector<SDep, 4> Preds;  // All sunit predecessors.
    SmallVector<SDep, 4> Succs;  // All sunit successors.

    typedef SmallVector<SDep, 4>::iterator pred_iterator;
    typedef SmallVector<SDep, 4>::iterator succ_iterator;
    typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator;
    typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator;
    
    unsigned NodeNum;                   // Entry # of node in the node vector.
    unsigned NodeQueueId;               // Queue id of node.
    unsigned short Latency;             // Node latency.
    short NumPreds;                     // # of non-control preds.
    short NumSuccs;                     // # of non-control sucss.
    short NumPredsLeft;                 // # of preds not scheduled.
    short NumSuccsLeft;                 // # of succs not scheduled.
    bool isTwoAddress     : 1;          // Is a two-address instruction.
    bool isCommutable     : 1;          // Is a commutable instruction.
    bool hasPhysRegDefs   : 1;          // Has physreg defs that are being used.
    bool isPending        : 1;          // True once pending.
    bool isAvailable      : 1;          // True once available.
    bool isScheduled      : 1;          // True once scheduled.
    unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
    unsigned Cycle;                     // Once scheduled, the cycle of the op.
    unsigned Depth;                     // Node depth;
    unsigned Height;                    // Node height;
    const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null.
    const TargetRegisterClass *CopySrcRC;
    
    /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent
    /// an SDNode and any nodes flagged to it.
    SUnit(SDNode *node, unsigned nodenum)
      : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
        Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
        isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
        isPending(false), isAvailable(false), isScheduled(false),
        CycleBound(0), Cycle(0), Depth(0), Height(0),
        CopyDstRC(NULL), CopySrcRC(NULL) {}

    /// SUnit - Construct an SUnit for post-regalloc scheduling to represent
    /// a MachineInstr.
    SUnit(MachineInstr *instr, unsigned nodenum)
      : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
        Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
        isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
        isPending(false), isAvailable(false), isScheduled(false),
        CycleBound(0), Cycle(0), Depth(0), Height(0),
        CopyDstRC(NULL), CopySrcRC(NULL) {}

    /// setNode - Assign the representative SDNode for this SUnit.
    /// This may be used during pre-regalloc scheduling.
    void setNode(SDNode *N) {
      assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
      Node = N;
    }

    /// getNode - Return the representative SDNode for this SUnit.
    /// This may be used during pre-regalloc scheduling.
    SDNode *getNode() const {
      assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
      return Node;
    }

    /// setInstr - Assign the instruction for the SUnit.
    /// This may be used during post-regalloc scheduling.
    void setInstr(MachineInstr *MI) {
      assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
      Instr = MI;
    }

    /// getInstr - Return the representative MachineInstr for this SUnit.
    /// This may be used during post-regalloc scheduling.
    MachineInstr *getInstr() const {
      assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
      return Instr;
    }

    /// addPred - This adds the specified node as a pred of the current node if
    /// not already.  This returns true if this is a new pred.
    bool addPred(SUnit *N, bool isCtrl, bool isSpecial,
                 unsigned PhyReg = 0, int Cost = 1) {
      for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
        if (Preds[i].Dep == N &&
            Preds[i].isCtrl == isCtrl && Preds[i].isSpecial == isSpecial)
          return false;
      Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isSpecial));
      N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl, isSpecial));
      if (!isCtrl) {
        ++NumPreds;
        ++N->NumSuccs;
      }
      if (!N->isScheduled)
        ++NumPredsLeft;
      if (!isScheduled)
        ++N->NumSuccsLeft;
      return true;
    }

    bool removePred(SUnit *N, bool isCtrl, bool isSpecial) {
      for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end();
           I != E; ++I)
        if (I->Dep == N && I->isCtrl == isCtrl && I->isSpecial == isSpecial) {
          bool FoundSucc = false;
          for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(),
                 EE = N->Succs.end(); II != EE; ++II)
            if (II->Dep == this &&
                II->isCtrl == isCtrl && II->isSpecial == isSpecial) {
              FoundSucc = true;
              N->Succs.erase(II);
              break;
            }
          assert(FoundSucc && "Mismatching preds / succs lists!");
          Preds.erase(I);
          if (!isCtrl) {
            --NumPreds;
            --N->NumSuccs;
          }
          if (!N->isScheduled)
            --NumPredsLeft;
          if (!isScheduled)
            --N->NumSuccsLeft;
          return true;
        }
      return false;
    }

    bool isPred(SUnit *N) {
      for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
        if (Preds[i].Dep == N)
          return true;
      return false;
    }
    
    bool isSucc(SUnit *N) {
      for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
        if (Succs[i].Dep == N)
          return true;
      return false;
    }
    
    void dump(const SelectionDAG *G) const;
    void dumpAll(const SelectionDAG *G) const;
  };

  //===--------------------------------------------------------------------===//
  /// SchedulingPriorityQueue - This interface is used to plug different
  /// priorities computation algorithms into the list scheduler. It implements
  /// the interface of a standard priority queue, where nodes are inserted in 
  /// arbitrary order and returned in priority order.  The computation of the
  /// priority and the representation of the queue are totally up to the
  /// implementation to decide.
  /// 
  class SchedulingPriorityQueue {
  public:
    virtual ~SchedulingPriorityQueue() {}
  
    virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
    virtual void addNode(const SUnit *SU) = 0;
    virtual void updateNode(const SUnit *SU) = 0;
    virtual void releaseState() = 0;

    virtual unsigned size() const = 0;
    virtual bool empty() const = 0;
    virtual void push(SUnit *U) = 0;
  
    virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
    virtual SUnit *pop() = 0;

    virtual void remove(SUnit *SU) = 0;

    /// ScheduledNode - As each node is scheduled, this method is invoked.  This
    /// allows the priority function to adjust the priority of related
    /// unscheduled nodes, for example.
    ///
    virtual void ScheduledNode(SUnit *) {}

    virtual void UnscheduledNode(SUnit *) {}
  };

  class ScheduleDAG {
  public:
    SelectionDAG *DAG;                    // DAG of the current basic block
    MachineBasicBlock *BB;                // Current basic block
    const TargetMachine &TM;              // Target processor
    const TargetInstrInfo *TII;           // Target instruction information
    const TargetRegisterInfo *TRI;        // Target processor register info
    TargetLowering *TLI;                  // Target lowering info
    MachineFunction *MF;                  // Machine function
    MachineRegisterInfo &MRI;             // Virtual/real register map
    MachineConstantPool *ConstPool;       // Target constant pool
    std::vector<SUnit*> Sequence;         // The schedule. Null SUnit*'s
                                          // represent noop instructions.
    std::vector<SUnit> SUnits;            // The scheduling units.
    SmallSet<SDNode*, 16> CommuteSet;     // Nodes that should be commuted.

    ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb,
                const TargetMachine &tm);

    virtual ~ScheduleDAG() {}

    /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered
    /// using 'dot'.
    ///
    void viewGraph();
  
    /// Run - perform scheduling.
    ///
    void Run();

    /// isPassiveNode - Return true if the node is a non-scheduled leaf.
    ///
    static bool isPassiveNode(SDNode *Node) {
      if (isa<ConstantSDNode>(Node))       return true;
      if (isa<ConstantFPSDNode>(Node))     return true;
      if (isa<RegisterSDNode>(Node))       return true;
      if (isa<GlobalAddressSDNode>(Node))  return true;
      if (isa<BasicBlockSDNode>(Node))     return true;
      if (isa<FrameIndexSDNode>(Node))     return true;
      if (isa<ConstantPoolSDNode>(Node))   return true;
      if (isa<JumpTableSDNode>(Node))      return true;
      if (isa<ExternalSymbolSDNode>(Node)) return true;
      if (isa<MemOperandSDNode>(Node))     return true;
      if (Node->getOpcode() == ISD::EntryToken) return true;
      return false;
    }

    /// NewSUnit - Creates a new SUnit and return a ptr to it.
    ///
    SUnit *NewSUnit(SDNode *N) {
      SUnits.push_back(SUnit(N, (unsigned)SUnits.size()));
      SUnits.back().OrigNode = &SUnits.back();
      return &SUnits.back();
    }

    /// NewSUnit - Creates a new SUnit and return a ptr to it.
    ///
    SUnit *NewSUnit(MachineInstr *MI) {
      SUnits.push_back(SUnit(MI, (unsigned)SUnits.size()));
      SUnits.back().OrigNode = &SUnits.back();
      return &SUnits.back();
    }

    /// Clone - Creates a clone of the specified SUnit. It does not copy the
    /// predecessors / successors info nor the temporary scheduling states.
    SUnit *Clone(SUnit *N);
    
    /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
    /// This SUnit graph is similar to the SelectionDAG, but represents flagged
    /// together nodes with a single SUnit.
    void BuildSchedUnits();

    /// ComputeLatency - Compute node latency.
{'fraction_non_alphanumeric': 0.12033786367270326, 'fraction_numerical': 0.003962598630470298, 'mean_word_length': 2.1129625622159707, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 83, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4872433', 'n_tokens_mistral': 8390, 'n_tokens_neox': 8077, 'n_words': 2752}