//===--- RDFCopy.cpp ------------------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Simplistic RDF-based copy propagation.

#include "RDFCopy.h"
#include "RDFGraph.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/Support/CommandLine.h"

#include <atomic>

#ifndef NDEBUG
static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
static unsigned CpCount = 0;
#endif

using namespace llvm;
using namespace rdf;

void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, MachineInstr *MI) {
  assert(MI->getOpcode() == TargetOpcode::COPY);
  const MachineOperand &Op0 = MI->getOperand(0), &Op1 = MI->getOperand(1);
  RegisterRef DstR = { Op0.getReg(), Op0.getSubReg() };
  RegisterRef SrcR = { Op1.getReg(), Op1.getSubReg() };
  auto FS = DefM.find(SrcR);
  if (FS == DefM.end() || FS->second.empty())
    return;
  Copies.push_back(SA.Id);
  RDefMap[SrcR][SA.Id] = FS->second.top()->Id;
  // Insert DstR into the map.
  RDefMap[DstR];
}


void CopyPropagation::updateMap(NodeAddr<InstrNode*> IA) {
  RegisterSet RRs;
  for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
    RRs.insert(RA.Addr->getRegRef());
  bool Common = false;
  for (auto &R : RDefMap) {
    if (!RRs.count(R.first))
      continue;
    Common = true;
    break;
  }
  if (!Common)
    return;

  for (auto &R : RDefMap) {
    if (!RRs.count(R.first))
      continue;
    auto F = DefM.find(R.first);
    if (F == DefM.end() || F->second.empty())
      continue;
    R.second[IA.Id] = F->second.top()->Id;
  }
}


bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
  bool Changed = false;
  auto BA = DFG.getFunc().Addr->findBlock(B, DFG);
  DFG.markBlock(BA.Id, DefM);

  for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
    if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {
      NodeAddr<StmtNode*> SA = IA;
      MachineInstr *MI = SA.Addr->getCode();
      if (MI->isCopy())
        recordCopy(SA, MI);
    }

    updateMap(IA);
    DFG.pushDefs(IA, DefM);
  }

  MachineDomTreeNode *N = MDT.getNode(B);
  for (auto I : *N)
    Changed |= scanBlock(I->getBlock());

  DFG.releaseBlock(BA.Id, DefM);
  return Changed;
}


bool CopyPropagation::run() {
  scanBlock(&DFG.getMF().front());

  if (trace()) {
    dbgs() << "Copies:\n";
    for (auto I : Copies)
      dbgs() << *DFG.addr<StmtNode*>(I).Addr->getCode();
    dbgs() << "\nRDef map:\n";
    for (auto R : RDefMap) {
      dbgs() << Print<RegisterRef>(R.first, DFG) << " -> {";
      for (auto &M : R.second)
        dbgs() << ' ' << Print<NodeId>(M.first, DFG) << ':'
               << Print<NodeId>(M.second, DFG);
      dbgs() << " }\n";
    }
  }

  bool Changed = false;
  NodeSet Deleted;
#ifndef NDEBUG
  bool HasLimit = CpLimit.getNumOccurrences() > 0;
#endif

  for (auto I : Copies) {
#ifndef NDEBUG
    if (HasLimit && CpCount >= CpLimit)
      break;
#endif
    if (Deleted.count(I))
      continue;
    auto SA = DFG.addr<InstrNode*>(I);
    NodeList Ds = SA.Addr->members_if(DFG.IsDef, DFG);
    if (Ds.size() != 1)
      continue;
    NodeAddr<DefNode*> DA = Ds[0];
    RegisterRef DR0 = DA.Addr->getRegRef();
    NodeList Us = SA.Addr->members_if(DFG.IsUse, DFG);
    if (Us.size() != 1)
      continue;
    NodeAddr<UseNode*> UA0 = Us[0];
    RegisterRef UR0 = UA0.Addr->getRegRef();
    NodeId RD0 = UA0.Addr->getReachingDef();

    for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) {
      auto UA = DFG.addr<UseNode*>(N);
      NextN = UA.Addr->getSibling();
      uint16_t F = UA.Addr->getFlags();
      if ((F & NodeAttrs::PhiRef) || (F & NodeAttrs::Fixed))
        continue;
      if (UA.Addr->getRegRef() != DR0)
        continue;
      NodeAddr<InstrNode*> IA = UA.Addr->getOwner(DFG);
      assert(DFG.IsCode<NodeAttrs::Stmt>(IA));
      MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
      if (RDefMap[UR0][IA.Id] != RD0)
        continue;
      MachineOperand &Op = UA.Addr->getOp();
      if (Op.isTied())
        continue;
      if (trace()) {
        dbgs() << "can replace " << Print<RegisterRef>(DR0, DFG)
               << " with " << Print<RegisterRef>(UR0, DFG) << " in "
               << *NodeAddr<StmtNode*>(IA).Addr->getCode();
      }

      Op.setReg(UR0.Reg);
      Op.setSubReg(UR0.Sub);
      Changed = true;
#ifndef NDEBUG
      if (HasLimit && CpCount >= CpLimit)
        break;
      CpCount++;
#endif

      if (MI->isCopy()) {
        MachineOperand &Op0 = MI->getOperand(0), &Op1 = MI->getOperand(1);
        if (Op0.getReg() == Op1.getReg() && Op0.getSubReg() == Op1.getSubReg())
          MI->eraseFromParent();
        Deleted.insert(IA.Id);
      }
    }
  }

  return Changed;
}