//===--------------- RegClique_Fer.cpp - Set of Registers -----------------===//
//
//              Register Allocation via Coloring of Chordal Graphs 
//
// This class implements a set of registers. It distinguises between virtual
// and machine registes.
//
// Date: May 27th, 2006
//
//===----------------------------------------------------------------------===//
//
// This class implements a set of registers. It is mostly used to represent
// cliques of registers. A clique of register is a set of register whose live
// ranges overlap at the same point in the control flow graph of the SSA-form
// program.
//===----------------------------------------------------------------------===//

namespace llvm {
 
class RegClique_Fer {

    public:

    /// Constructor method. It will initialize this register set with the out
    /// set of the given machine block. The out set of a basic block is the
    /// set of variables alive at the end of the basic block. It can be
    /// obtained by the union of live sets of all the edges that leave the
    /// basic block.
    RegClique_Fer(
                   MachineFunction & mf,
                   MachineBasicBlock & mbb,
                   EdgeLiveness_Fernando * edge_liveness
                  );


    /// Constructor method. It will initialize this register set with the
    /// virtual registers alive in the edge that links mbb1 to mbb2. Notice
    /// that if mbb2 is not a successor of mbb1, no register will be in this
    /// register set.
    RegClique_Fer(
                   MachineFunction & mf,
                   const MachineBasicBlock & mbb1,
                   const MachineBasicBlock & mbb2,
                   EdgeLiveness_Fernando * edge_liveness
                  );


    /// This method adds the register given as parameter to this register set.
    void add_reg(const MachineOperand & temporary);


    /// This method removes the register given as parameter from this register
    /// set. It will return true if the register was present in the set, and
    /// false otherwise.
    bool remove_reg(const MachineOperand & temporary);


    /// Returns a string in the format (r1, r2, ..., rm)+(t1, t2, ..., tn),
    /// where ri represents a machine register, and t1 represents a temporary
    /// (also called virtual) register.
    std::string to_string();


    /// Add the registers used implicitly by the given instruction to this
    /// register set. Implicit registers are always physical registers; they
    /// appear mostly in call instructions.
    void handle_implicit_regs(const MachineInstr & mi);

    private:

    /// Internal representation of the set: one vector for virtual
    /// registers, and another vector for physical registers.
    /// This is the vector for virtual registers.
    std::vector<bool> virt_reg;

    /// Internal representation of the set: one vector for virtual
    /// registers, and another vector for physical registers.
    /// This is the vector for physical registers.
    std::vector<bool> phys_reg;

    /// Target architecture specific information can be accessed through this
    /// interface.
    const TargetMachine * target_machine;

    /// Information about the bank of registers implemented by the actual
    /// machine can be accessed through this interface.
    const MRegisterInfo * m_reg_info;

    /// This vector keeps track of which registers can be used for register
    /// allocation purposes. Some registers cannot be used to hold the value
    /// of temporaries. For example, the ESP register in X86, or the fp
    /// register in MIPS. The cell corresponding to such registers in the
    /// vector below will be false. The other cells will be true;
    std::vector<bool> allocatable_regs;
};


//===--------------------------------------------------------------------------
// Constructor method. It will initialize this register set with the out
// set of the given machine block. The out set of a basic block is the set of
// variables alive at the end of the basic block. It can be obtained by the
// union of live sets of all the edges that leave the basic block.
//===--------------------------------------------------------------------------
RegClique_Fer::RegClique_Fer(
                              MachineFunction & mf,
                              MachineBasicBlock & mbb,
                              EdgeLiveness_Fernando * edge_liveness
                            )
{
    this->target_machine = & mf.getTarget();
    unsigned nv = edge_liveness->get_num_virtual_registers();
    this->virt_reg.assign(nv, false);
    this->m_reg_info = this->target_machine->getRegisterInfo();
    this->phys_reg.assign(this->m_reg_info->getNumRegs(), false);
    this->allocatable_regs = this->m_reg_info->getAllocatableSet(mf);

    for(MachineBasicBlock::const_succ_iterator succ_aux = mbb.succ_begin();
                                      succ_aux != mbb.succ_end(); succ_aux++) {
        const MachineBasicBlock* succ_mbb = *succ_aux;
        const std::vector<bool> & succ_live =
                        edge_liveness->get_live_variables(mbb, *succ_mbb);
        for (unsigned i = 0; i < succ_live.size(); i++) {
            if(succ_live[i]) {
                this->virt_reg[i] = true;
            }
        }
    }
    // Finally, if the last block in the function is a return, make sure to
    // add the live out set of the function to this set of registers.
    const TargetInstrInfo & tii = * (this->target_machine->getInstrInfo());
    if (!mbb.empty() && tii.isReturn(mbb.back().getOpcode())) {
        MachineInstr *return_inst = & mbb.back();
        for (MachineFunction::liveout_iterator iter = mf.liveout_begin(),
                                 end = mf.liveout_end(); iter != end; ++iter) {
            assert(MRegisterInfo::isPhysicalRegister(*iter) &&
                                    "Cannot have a live-in virtual register!");
            this->phys_reg[*iter] = true;
      }
    }
}


//===--------------------------------------------------------------------------
// Constructor method. It will initialize this register set with the virtual
// registers alive in the edge that links mbb1 to mbb2. Notice that if mbb2
// is not a successor of mbb1, no register will be in this register set.
//===--------------------------------------------------------------------------
RegClique_Fer::RegClique_Fer(
                              MachineFunction & mf,
                              const MachineBasicBlock & mbb1,
                              const MachineBasicBlock & mbb2,
                              EdgeLiveness_Fernando * edge_liveness
                             )
{
    this->target_machine = & mf.getTarget();
    unsigned nv = edge_liveness->get_num_virtual_registers();
    this->virt_reg.assign(nv, false);
    this->m_reg_info = this->target_machine->getRegisterInfo();
    this->phys_reg.assign(this->m_reg_info->getNumRegs(), false);
    this->allocatable_regs = this->m_reg_info->getAllocatableSet(mf);

    const std::vector<bool> & live_set =
                                 edge_liveness->get_live_variables(mbb1, mbb2);
    for (unsigned i = 0; i < live_set.size(); i++) {
        if(live_set[i]) {
            this->virt_reg[i] = true;
        }
    }
}


//===--------------------------------------------------------------------------
// This method removes the register given as parameter from this register set.
// It will return true if the register was present in the set, and false
// otherwise. If the machine operand passed as parameter does not contain a
// register, a run time error will be produced.
//===--------------------------------------------------------------------------
bool RegClique_Fer::remove_reg(const MachineOperand & temporary) {

    assert(temporary.isRegister() && "Non-register operand in reg set.");
    assert(temporary.getReg() && "Non-valid register operand in reg set.");

    unsigned reg_num = temporary.getReg();
    if(MRegisterInfo::isVirtualRegister(reg_num)) {
        unsigned base_reg = reg_num - MRegisterInfo::FirstVirtualRegister;
        assert(this->virt_reg.size() > base_reg &&
               "RegClique_Fer: not valid temporary register.");
        if(this->virt_reg[base_reg]) {
            this->virt_reg[base_reg] = false;
            return true;
        }
    } else if(MRegisterInfo::isPhysicalRegister(reg_num)) {
        if(this->phys_reg.size() > reg_num) {
            if(this->phys_reg[reg_num]) {
                this->phys_reg[reg_num] = false;
                return true;
            }
        }
    }
    return false;
}


//===--------------------------------------------------------------------------
// This method adds the register given as parameter to this register set.
// If the machine operand passed as parameter does not contain a register,
// a run time error will be produced.
//===--------------------------------------------------------------------------
inline void RegClique_Fer::add_reg(const MachineOperand & temporary) {

    assert(temporary.isRegister() && "Non-register operand in reg set.");
    assert(temporary.getReg() && "Non-register operand in register set.");

    unsigned reg_num = temporary.getReg();
    if(MRegisterInfo::isVirtualRegister(reg_num)) {
        unsigned base_reg = reg_num - MRegisterInfo::FirstVirtualRegister;
        assert(this->virt_reg.size() > base_reg &&
               "RegClique_Fer: not valid temporary register.");
        this->virt_reg[base_reg] = true;
    } else if(MRegisterInfo::isPhysicalRegister(reg_num)) {
        if(this->allocatable_regs[reg_num]) {
            if (this->phys_reg.size() <= reg_num) {
                this->phys_reg.resize(reg_num + 1);
            }
            this->phys_reg[reg_num] = true;
        }
    }

}


//===--------------------------------------------------------------------------
// Add the registers used implicitly by this instruction to this register set.
// Implicit registers are always physical registers; they appear mostly in
// call instructions.
//===--------------------------------------------------------------------------
inline void RegClique_Fer::handle_implicit_regs(
                                               const MachineInstr & mi) {
    const TargetInstrInfo & tii = * (this->target_machine->getInstrInfo());
    const TargetInstrDescriptor &tid = tii.get(mi.getOpcode());

    for (const unsigned *implicit_use = tid.ImplicitUses;
                                               *implicit_use; ++implicit_use) {
        if (this->phys_reg.size() <= *implicit_use) {
            this->phys_reg.resize(*implicit_use + 1);
        }
        this->phys_reg[*implicit_use] = true;
    }
    for (const unsigned *implicit_def = tid.ImplicitDefs;
                                               *implicit_def; ++implicit_def) {
        if (this->phys_reg.size() > *implicit_def) {
            this->phys_reg[*implicit_def] = false;
        }
    }
}


//===--------------------------------------------------------------------------
// Returns a string in the format (r1, r2, ..., rm)+(t1, t2, ..., tn), where
// ri represents a machine register, and t1 represents a temporary (also called
// virtual) register.
//===--------------------------------------------------------------------------
inline std::string RegClique_Fer::to_string() {
    bool isFirst = true;
    std::ostringstream aux;

    // first, generate a string for the physical registers:
    aux << "(";
    for (unsigned i = 0, e = this->phys_reg.size(); i != e; ++i) {
        if(this->phys_reg[i]) {
            if(isFirst) {
                isFirst = false;
                aux << "r" << i;
            } else {
                aux << ", " << "r" << i;
            }
        }
    }

    // Now, take care of the virtual registers:
    isFirst = true;
    aux << ")+(";
    for (unsigned i = 0, e = this->virt_reg.size(); i != e; ++i) {
        if(this->virt_reg[i]) {
            if(isFirst) {
                isFirst = false;
                aux << "t" << i;
            } else {
                aux << ", " << "t" << i;
            }
        }
    }

    aux << ")";
    return aux.str();
}

} // end of llvm namespace