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/SelectionDAG.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
#include <algorithm>
using namespace llvm;

namespace {
//===----------------------------------------------------------------------===//
///
/// BitsIterator - Provides iteration through individual bits in a bit vector.
///
template<class T>
class BitsIterator {
private:
  T Bits;                               // Bits left to iterate through

public:
  /// Ctor.
  BitsIterator(T Initial) : Bits(Initial) {}
  
  /// Next - Returns the next bit set or zero if exhausted.
  inline T Next() {
    // Get the rightmost bit set
    T Result = Bits & -Bits;
    // Remove from rest
    Bits &= ~Result;
    // Return single bit or zero
    return Result;
  }
};
  
//===----------------------------------------------------------------------===//


//===----------------------------------------------------------------------===//
///
/// ResourceTally - Manages the use of resources over time intervals.  Each
/// item (slot) in the tally vector represents the resources used at a given
/// moment.  A bit set to 1 indicates that a resource is in use, otherwise
/// available.  An assumption is made that the tally is large enough to schedule 
/// all current instructions (asserts otherwise.)
///
template<class T>
class ResourceTally {
private:
  std::vector<T> Tally;                 // Resources used per slot
  typedef typename std::vector<T>::iterator Iter;
                                        // Tally iterator 
  
  /// SlotsAvailable - Returns true if all units are available.
	///
  bool SlotsAvailable(Iter Begin, unsigned N, unsigned ResourceSet,
                                              unsigned &Resource) {
    assert(N && "Must check availability with N != 0");
    // Determine end of interval
    Iter End = Begin + N;
    assert(End <= Tally.end() && "Tally is not large enough for schedule");
    
    // Iterate thru each resource
    BitsIterator<T> Resources(ResourceSet & ~*Begin);
    while (unsigned Res = Resources.Next()) {
      // Check if resource is available for next N slots
      Iter Interval = End;
      do {
        Interval--;
        if (*Interval & Res) break;
      } while (Interval != Begin);
      
      // If available for N
      if (Interval == Begin) {
        // Success
        Resource = Res;
        return true;
      }
    }
    
    // No luck
    Resource = 0;
    return false;
  }
	
	/// RetrySlot - Finds a good candidate slot to retry search.
  Iter RetrySlot(Iter Begin, unsigned N, unsigned ResourceSet) {
    assert(N && "Must check availability with N != 0");
    // Determine end of interval
    Iter End = Begin + N;
    assert(End <= Tally.end() && "Tally is not large enough for schedule");
		
		while (Begin != End--) {
			// Clear units in use
			ResourceSet &= ~*End;
			// If no units left then we should go no further 
			if (!ResourceSet) return End + 1;
		}
		// Made it all the way through
		return Begin;
	}
  
  /// FindAndReserveStages - Return true if the stages can be completed. If
  /// so mark as busy.
  bool FindAndReserveStages(Iter Begin,
                            InstrStage *Stage, InstrStage *StageEnd) {
    // If at last stage then we're done
    if (Stage == StageEnd) return true;
    // Get number of cycles for current stage
    unsigned N = Stage->Cycles;
    // Check to see if N slots are available, if not fail
    unsigned Resource;
    if (!SlotsAvailable(Begin, N, Stage->Units, Resource)) return false;
    // Check to see if remaining stages are available, if not fail
    if (!FindAndReserveStages(Begin + N, Stage + 1, StageEnd)) return false;
    // Reserve resource
    Reserve(Begin, N, Resource);
    // Success
    return true;
  }

  /// Reserve - Mark busy (set) the specified N slots.
  void Reserve(Iter Begin, unsigned N, unsigned Resource) {
    // Determine end of interval
    Iter End = Begin + N;
    assert(End <= Tally.end() && "Tally is not large enough for schedule");
 
    // Set resource bit in each slot
    for (; Begin < End; Begin++)
      *Begin |= Resource;
  }

  /// FindSlots - Starting from Begin, locate consecutive slots where all stages
  /// can be completed.  Returns the address of first slot.
  Iter FindSlots(Iter Begin, InstrStage *StageBegin, InstrStage *StageEnd) {
    // Track position      
    Iter Cursor = Begin;
    
    // Try all possible slots forward
    while (true) {
      // Try at cursor, if successful return position.
      if (FindAndReserveStages(Cursor, StageBegin, StageEnd)) return Cursor;
      // Locate a better position
			Cursor = RetrySlot(Cursor + 1, StageBegin->Cycles, StageBegin->Units);
    }
  }
  
public:
  /// Initialize - Resize and zero the tally to the specified number of time
  /// slots.
  inline void Initialize(unsigned N) {
    Tally.assign(N, 0);   // Initialize tally to all zeros.
  }

  // FindAndReserve - Locate an ideal slot for the specified stages and mark
  // as busy.
  unsigned FindAndReserve(unsigned Slot, InstrStage *StageBegin,
                                         InstrStage *StageEnd) {
		// Where to begin 
		Iter Begin = Tally.begin() + Slot;
		// Find a free slot
		Iter Where = FindSlots(Begin, StageBegin, StageEnd);
		// Distance is slot number
		unsigned Final = Where - Tally.begin();
    return Final;
  }

};

//===----------------------------------------------------------------------===//
///
/// ScheduleDAGSimple - Simple two pass scheduler.
///
class ScheduleDAGSimple : public ScheduleDAG {
private:
  ResourceTally<unsigned> Tally;        // Resource usage tally
  unsigned NSlots;                      // Total latency
  static const unsigned NotFound = ~0U; // Search marker
  
public:

  // Ctor.
  ScheduleDAGSimple(SchedHeuristics hstc, SelectionDAG &dag,
                    MachineBasicBlock *bb, const TargetMachine &tm)
    : ScheduleDAG(hstc, dag, bb, tm), Tally(), NSlots(0) {
    assert(&TII && "Target doesn't provide instr info?");
    assert(&MRI && "Target doesn't provide register info?");
  }

  virtual ~ScheduleDAGSimple() {};

  void Schedule();

private:
  static bool isDefiner(NodeInfo *A, NodeInfo *B);
  void IncludeNode(NodeInfo *NI);
  void VisitAll();
  void GatherSchedulingInfo();
  void FakeGroupDominators(); 
  bool isStrongDependency(NodeInfo *A, NodeInfo *B);
  bool isWeakDependency(NodeInfo *A, NodeInfo *B);
  void ScheduleBackward();
  void ScheduleForward