llvm/lib/Target/Hexagon/HexagonGlobalRegion.cpp - llvm-project.git - Git at Google

 //===-- HexagonGlobalRegion.cpp - VLIW global scheduling infrastructure ---===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // Basic infrastructure for global scheduling. Liveness update.
 // This is the least complete portion. Basically it is empty infrastructure
 // to be extended and improved.
 // Currently in place only trace region formation routines and non fully
 // functional skeleton for incremental liveness update.
 //
 //===----------------------------------------------------------------------===//
 #define DEBUG_TYPE "global_sched"
 #include "HexagonGlobalRegion.h"
 #include "HexagonTargetMachine.h"
 #include "llvm/Support/raw_ostream.h"

 using namespace llvm;

 LivenessInfo::LivenessInfo(const TargetInstrInfo *TII,
                            const TargetRegisterInfo *TRI,
                            MachineBasicBlock *MBB)
     : TII(TII), TRI(TRI) {
   LiveIns.resize(TRI->getNumRegs());
   LiveOuts.resize(TRI->getNumRegs());

   LiveIns.reset();
   LiveOuts.reset();

   // Live-ins are simple, just copy from MBB.
   for (const auto &LI : MBB->liveins())
     setUsed(LiveIns, LI.PhysReg);

   // Live-outs are concatenation of all the BB successors.
   // As of now, we are only dealing with a-cyclic regions
   // with side exits, but no side entrances.
   for (const MachineBasicBlock *Succ : MBB->successors())
     for (const auto &LI : Succ->liveins())
       setUsed(LiveOuts, LI.PhysReg);
 }

 // Pessimistically check if at least one def of this register in this
 // instruction (bundle or not) is done under predication.
 static bool isPredicatedDef(MachineInstr *MI, unsigned Reg,
                             const HexagonInstrInfo *QII) {
   if (!MI->isBundle())
     return QII->isPredicated(*MI);
   MachineBasicBlock *Parent = MI->getParent();
   if (!Parent)
     return false;
   MachineBasicBlock::instr_iterator MII = MI->getIterator();
   MachineBasicBlock::instr_iterator MIIE = Parent->instr_end();
   for (++MII; MII != MIIE && MII->isInsideBundle(); ++MII) {
     if (!QII->isPredicated(*MII))
       continue;
     for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
       const MachineOperand &MO = MII->getOperand(i);
       if (!MO.isReg())
         continue;
       if (MO.isDef() && !MO.isDead() && MO.getReg() == Reg) {
         LLVM_DEBUG(dbgs() << "\t\tCond def: "; MII->dump());
         return true;
       }
     }
   }
   return false;
 }

 /// Determine def/use set for MI.
 /// Beware, if def is conditional, like here:
 /// BUNDLE %PC<imp-def>, %R0<imp-def>, %P0<imp-use,kill>, %R16<imp-use>
 ///   * %R0<def> = LDriuh_cdnNotPt %P0<kill,internal>, %R16, 0;
 ///   * %P0<def> = C2_cmpeqi %R16, 0;
 /// It is not a statefull definition of R0.
 ///
 void LivenessInfo::parseOperands(MachineInstr *MI, BitVector &Gen,
                                  BitVector &Kill, BitVector &Use) {
   const auto *QII = static_cast<const HexagonInstrInfo *>(TII);

   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
     if (!MO.isReg())
       continue;
     // If it is a predicated instruction, it may, or may not
     // be setting its destination, and we do not know it
     // at the compile time.
     if (MO.isDef() && !MO.isDead()) {
       if (isPredicatedDef(MI, MO.getReg(), QII))
         LLVM_DEBUG(dbgs() << "\tConditional define of "
                           << printReg(MO.getReg(), TRI) << " in ";
                    MI->dump());
       else
         setUsed(Gen, MO.getReg());
     }
     if (MO.isKill())
       setUsed(Kill, MO.getReg());
     if (MO.isUse())
       setUsed(Use, MO.getReg());
   }
 }

 void LivenessInfo::parseOperandsWithReset(MachineInstr *MI, BitVector &Gen,
                                           BitVector &Kill, BitVector &Use) {
   Gen.reset();
   Use.reset();
   Kill.reset();
   parseOperands(MI, Gen, Kill, Use);
 }

 /// setUsed - Set the register and its sub-registers as being used.
 /// Taken from RegScavenger::setUsed().
 void LivenessInfo::setUsed(BitVector &Set, unsigned Reg) {
   Set.set(Reg);

   for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
     Set.set(*SubRegs);
 }

 #ifndef NDEBUG
 static void dumpRI(const TargetRegisterInfo *TRI, BitVector &Set) {
   for (unsigned i = 0; i < Set.size(); i++)
     if (Set.test(i))
       LLVM_DEBUG(dbgs() << " " << printReg(i, TRI));
 }
 #endif

 // This function incrementally updates liveness for the given BB.
 // First it gathers LiveOut set, and then iterates bottom-up
 // over bundles/instructions while updating live set.
 void LivenessInfo::UpdateLiveness(MachineBasicBlock *MBB) {
   BitVector NewLiveIns(TRI->getNumRegs());
   BitVector NewLiveOuts(TRI->getNumRegs());
   BitVector LiveIns(TRI->getNumRegs());
   BitVector LocalGen(TRI->getNumRegs());
   BitVector LocalUse(TRI->getNumRegs());
   BitVector LocalKill(TRI->getNumRegs());

   NewLiveIns.reset();
   NewLiveOuts.reset();

   LLVM_DEBUG(dbgs() << "\n\t\tUpdateLiveness for BB(" << MBB->getNumber()
                     << ")\n");

   // Original Live-ins are simple, just copy from MBB.
   for (const auto &LI : MBB->liveins())
     setUsed(NewLiveIns, LI.PhysReg);

   // Live-outs are concatenation of all the BB successors.
   // As of now, we are only dealing with a-cyclic regions
   // with side exits, but no side entrances.
   for (const MachineBasicBlock *Succ : MBB->successors())
     for (const auto &LI : Succ->liveins())
       setUsed(NewLiveOuts, LI.PhysReg);

   LiveIns = NewLiveIns;
   // This needs to be a sequential walk, not parallel update.
   LLVM_DEBUG(dbgs() << "\t\tOriginal live ins :\t"; dumpRI(TRI, NewLiveIns);
              dbgs() << "\n");
   LLVM_DEBUG(dbgs() << "\t\tOriginal live outs:\t"; dumpRI(TRI, NewLiveOuts);
              dbgs() << "\n");

   NewLiveIns = NewLiveOuts;
   // Scan BB backwards to get exposed uses.
   // TODO: Handle predicates if needed.
   std::vector<MachineInstr *> BundleList;
   for (MachineBasicBlock::iterator MI = MBB->begin(), MIE = MBB->end();
        MI != MIE; ++MI)
     if (!MI->isDebugInstr())
       BundleList.push_back(&*MI);

   while (!BundleList.empty()) {
     MachineInstr *MI = BundleList.back();
     BundleList.pop_back();
     parseOperandsWithReset(MI, LocalGen, LocalKill, LocalUse);
     LLVM_DEBUG(dbgs() << "\t\tIncr gen:\t"; dumpRI(TRI, LocalGen);
                dbgs() << "\n");
     LLVM_DEBUG(dbgs() << "\t\tIncr use:\t"; dumpRI(TRI, LocalUse);
                dbgs() << "\n");
     // NewLiveIns = (NewLiveIns - LocalGen) U LocalUse.
     BitVector NotGen(LocalGen);
     NotGen.flip();
     NewLiveIns &= NotGen;
     NewLiveIns |= LocalUse;
   }

   LLVM_DEBUG(dbgs() << "\t\tAnswer:\t"; dumpRI(TRI, NewLiveIns);
              dbgs() << "\n");

   // TODO: Consider implementing a register aliasing filter if duplicate
   // live-in entries become problematic.

   // Set new live in.
   LLVM_DEBUG(dbgs() << "\t\tNew LiveIn       :\t");

   for (unsigned i = 0; i < LiveIns.size(); ++i) {
     if (NewLiveIns.test(i))
       LLVM_DEBUG(dbgs() << " " << printReg(i, TRI));
     if (LiveIns.test(i) == NewLiveIns.test(i))
       continue;
     if (LiveIns.test(i))
       MBB->removeLiveIn(i);
     if (NewLiveIns.test(i))
       MBB->addLiveIn(i);
   }
   LLVM_DEBUG(dbgs() << "\n");
 }

 void LivenessInfo::dump() {
   for (unsigned i = 0; i < LiveIns.size(); i++)
     if (LiveIns.test(i))
       LLVM_DEBUG(dbgs() << "\t\tlive-in:  " << printReg(i, TRI) << "\n");
   for (unsigned i = 0; i < LiveOuts.size(); i++)
     if (LiveOuts.test(i))
       LLVM_DEBUG(dbgs() << "\t\tlive-out: " << printReg(i, TRI) << "\n");
 }

 ///
 /// BasicBlockRegion Methods.
 ///
 BasicBlockRegion::BasicBlockRegion(const TargetInstrInfo *TII,
                                    const TargetRegisterInfo *TRI,
                                    MachineBasicBlock *MBB)
     : TII(TII), TRI(TRI) {
   // Should be the root BB.
   Elements.push_back(MBB);
   ElementIndex[MBB] = 0;
   LiveInfo[MBB] = std::make_unique<LivenessInfo>(TII, TRI, MBB);
 }

 BasicBlockRegion::~BasicBlockRegion() {
   LiveInfo.clear();
   Elements.clear();
   ElementIndex.clear();
 }

 LivenessInfo *BasicBlockRegion::getLivenessInfoForBB(MachineBasicBlock *MBB) {
   auto It = LiveInfo.find(MBB);
   assert(It != LiveInfo.end() && "Missing Liveness info");
   assert(It->second && "Missing Liveness info");
   return It->second.get();
 }

 void BasicBlockRegion::addBBtoRegion(MachineBasicBlock *MBB) {
   // It is OK to have duplicates if we reparse for additional BBs.
   if (LiveInfo.find(MBB) != LiveInfo.end())
     return;
   ElementIndex[MBB] = static_cast<unsigned>(Elements.size());
   Elements.push_back(MBB);
   LiveInfo[MBB] = std::make_unique<LivenessInfo>(TII, TRI, MBB);
 }
	//===-- HexagonGlobalRegion.cpp - VLIW global scheduling infrastructure ---===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	// Basic infrastructure for global scheduling. Liveness update.
	// This is the least complete portion. Basically it is empty infrastructure
	// to be extended and improved.
	// Currently in place only trace region formation routines and non fully
	// functional skeleton for incremental liveness update.
	//
	//===----------------------------------------------------------------------===//
	#define DEBUG_TYPE "global_sched"
	#include "HexagonGlobalRegion.h"
	#include "HexagonTargetMachine.h"
	#include "llvm/Support/raw_ostream.h"

	using namespace llvm;

	LivenessInfo::LivenessInfo(const TargetInstrInfo *TII,
	const TargetRegisterInfo *TRI,
	MachineBasicBlock *MBB)
	: TII(TII), TRI(TRI) {
	LiveIns.resize(TRI->getNumRegs());
	LiveOuts.resize(TRI->getNumRegs());

	LiveIns.reset();
	LiveOuts.reset();

	// Live-ins are simple, just copy from MBB.
	for (const auto &LI : MBB->liveins())
	setUsed(LiveIns, LI.PhysReg);

	// Live-outs are concatenation of all the BB successors.
	// As of now, we are only dealing with a-cyclic regions
	// with side exits, but no side entrances.
	for (const MachineBasicBlock *Succ : MBB->successors())
	for (const auto &LI : Succ->liveins())
	setUsed(LiveOuts, LI.PhysReg);
	}

	// Pessimistically check if at least one def of this register in this
	// instruction (bundle or not) is done under predication.
	static bool isPredicatedDef(MachineInstr *MI, unsigned Reg,
	const HexagonInstrInfo *QII) {
	if (!MI->isBundle())
	return QII->isPredicated(*MI);
	MachineBasicBlock *Parent = MI->getParent();
	if (!Parent)
	return false;
	MachineBasicBlock::instr_iterator MII = MI->getIterator();
	MachineBasicBlock::instr_iterator MIIE = Parent->instr_end();
	for (++MII; MII != MIIE && MII->isInsideBundle(); ++MII) {
	if (!QII->isPredicated(*MII))
	continue;
	for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
	const MachineOperand &MO = MII->getOperand(i);
	if (!MO.isReg())
	continue;
	if (MO.isDef() && !MO.isDead() && MO.getReg() == Reg) {
	LLVM_DEBUG(dbgs() << "\t\tCond def: "; MII->dump());
	return true;
	}
	}
	}
	return false;
	}

	/// Determine def/use set for MI.
	/// Beware, if def is conditional, like here:
	/// BUNDLE %PC<imp-def>, %R0<imp-def>, %P0<imp-use,kill>, %R16<imp-use>
	/// * %R0<def> = LDriuh_cdnNotPt %P0<kill,internal>, %R16, 0;
	/// * %P0<def> = C2_cmpeqi %R16, 0;
	/// It is not a statefull definition of R0.
	///
	void LivenessInfo::parseOperands(MachineInstr *MI, BitVector &Gen,
	BitVector &Kill, BitVector &Use) {
	const auto QII = static_cast<const HexagonInstrInfo >(TII);

	for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
	const MachineOperand &MO = MI->getOperand(i);
	if (!MO.isReg())
	continue;
	// If it is a predicated instruction, it may, or may not
	// be setting its destination, and we do not know it
	// at the compile time.
	if (MO.isDef() && !MO.isDead()) {
	if (isPredicatedDef(MI, MO.getReg(), QII))
	LLVM_DEBUG(dbgs() << "\tConditional define of "
	<< printReg(MO.getReg(), TRI) << " in ";
	MI->dump());
	else
	setUsed(Gen, MO.getReg());
	}
	if (MO.isKill())
	setUsed(Kill, MO.getReg());
	if (MO.isUse())
	setUsed(Use, MO.getReg());
	}
	}

	void LivenessInfo::parseOperandsWithReset(MachineInstr *MI, BitVector &Gen,
	BitVector &Kill, BitVector &Use) {
	Gen.reset();
	Use.reset();
	Kill.reset();
	parseOperands(MI, Gen, Kill, Use);
	}

	/// setUsed - Set the register and its sub-registers as being used.
	/// Taken from RegScavenger::setUsed().
	void LivenessInfo::setUsed(BitVector &Set, unsigned Reg) {
	Set.set(Reg);

	for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
	Set.set(*SubRegs);
	}

	#ifndef NDEBUG
	static void dumpRI(const TargetRegisterInfo *TRI, BitVector &Set) {
	for (unsigned i = 0; i < Set.size(); i++)
	if (Set.test(i))
	LLVM_DEBUG(dbgs() << " " << printReg(i, TRI));
	}
	#endif

	// This function incrementally updates liveness for the given BB.
	// First it gathers LiveOut set, and then iterates bottom-up
	// over bundles/instructions while updating live set.
	void LivenessInfo::UpdateLiveness(MachineBasicBlock *MBB) {
	BitVector NewLiveIns(TRI->getNumRegs());
	BitVector NewLiveOuts(TRI->getNumRegs());
	BitVector LiveIns(TRI->getNumRegs());
	BitVector LocalGen(TRI->getNumRegs());
	BitVector LocalUse(TRI->getNumRegs());
	BitVector LocalKill(TRI->getNumRegs());

	NewLiveIns.reset();
	NewLiveOuts.reset();

	LLVM_DEBUG(dbgs() << "\n\t\tUpdateLiveness for BB(" << MBB->getNumber()
	<< ")\n");

	// Original Live-ins are simple, just copy from MBB.
	for (const auto &LI : MBB->liveins())
	setUsed(NewLiveIns, LI.PhysReg);

	// Live-outs are concatenation of all the BB successors.
	// As of now, we are only dealing with a-cyclic regions
	// with side exits, but no side entrances.
	for (const MachineBasicBlock *Succ : MBB->successors())
	for (const auto &LI : Succ->liveins())
	setUsed(NewLiveOuts, LI.PhysReg);

	LiveIns = NewLiveIns;
	// This needs to be a sequential walk, not parallel update.
	LLVM_DEBUG(dbgs() << "\t\tOriginal live ins :\t"; dumpRI(TRI, NewLiveIns);
	dbgs() << "\n");
	LLVM_DEBUG(dbgs() << "\t\tOriginal live outs:\t"; dumpRI(TRI, NewLiveOuts);
	dbgs() << "\n");

	NewLiveIns = NewLiveOuts;
	// Scan BB backwards to get exposed uses.
	// TODO: Handle predicates if needed.
	std::vector<MachineInstr *> BundleList;
	for (MachineBasicBlock::iterator MI = MBB->begin(), MIE = MBB->end();
	MI != MIE; ++MI)
	if (!MI->isDebugInstr())
	BundleList.push_back(&*MI);

	while (!BundleList.empty()) {
	MachineInstr *MI = BundleList.back();
	BundleList.pop_back();
	parseOperandsWithReset(MI, LocalGen, LocalKill, LocalUse);
	LLVM_DEBUG(dbgs() << "\t\tIncr gen:\t"; dumpRI(TRI, LocalGen);
	dbgs() << "\n");
	LLVM_DEBUG(dbgs() << "\t\tIncr use:\t"; dumpRI(TRI, LocalUse);
	dbgs() << "\n");
	// NewLiveIns = (NewLiveIns - LocalGen) U LocalUse.
	BitVector NotGen(LocalGen);
	NotGen.flip();
	NewLiveIns &= NotGen;
	NewLiveIns \|= LocalUse;
	}

	LLVM_DEBUG(dbgs() << "\t\tAnswer:\t"; dumpRI(TRI, NewLiveIns);
	dbgs() << "\n");

	// TODO: Consider implementing a register aliasing filter if duplicate
	// live-in entries become problematic.

	// Set new live in.
	LLVM_DEBUG(dbgs() << "\t\tNew LiveIn :\t");

	for (unsigned i = 0; i < LiveIns.size(); ++i) {
	if (NewLiveIns.test(i))
	LLVM_DEBUG(dbgs() << " " << printReg(i, TRI));
	if (LiveIns.test(i) == NewLiveIns.test(i))
	continue;
	if (LiveIns.test(i))
	MBB->removeLiveIn(i);
	if (NewLiveIns.test(i))
	MBB->addLiveIn(i);
	}
	LLVM_DEBUG(dbgs() << "\n");
	}

	void LivenessInfo::dump() {
	for (unsigned i = 0; i < LiveIns.size(); i++)
	if (LiveIns.test(i))
	LLVM_DEBUG(dbgs() << "\t\tlive-in: " << printReg(i, TRI) << "\n");
	for (unsigned i = 0; i < LiveOuts.size(); i++)
	if (LiveOuts.test(i))
	LLVM_DEBUG(dbgs() << "\t\tlive-out: " << printReg(i, TRI) << "\n");
	}

	///
	/// BasicBlockRegion Methods.
	///
	BasicBlockRegion::BasicBlockRegion(const TargetInstrInfo *TII,
	const TargetRegisterInfo *TRI,
	MachineBasicBlock *MBB)
	: TII(TII), TRI(TRI) {
	// Should be the root BB.
	Elements.push_back(MBB);
	ElementIndex[MBB] = 0;
	LiveInfo[MBB] = std::make_unique<LivenessInfo>(TII, TRI, MBB);
	}

	BasicBlockRegion::~BasicBlockRegion() {
	LiveInfo.clear();
	Elements.clear();
	ElementIndex.clear();
	}

	LivenessInfo BasicBlockRegion::getLivenessInfoForBB(MachineBasicBlock MBB) {
	auto It = LiveInfo.find(MBB);
	assert(It != LiveInfo.end() && "Missing Liveness info");
	assert(It->second && "Missing Liveness info");
	return It->second.get();
	}

	void BasicBlockRegion::addBBtoRegion(MachineBasicBlock *MBB) {
	// It is OK to have duplicates if we reparse for additional BBs.
	if (LiveInfo.find(MBB) != LiveInfo.end())
	return;
	ElementIndex[MBB] = static_cast<unsigned>(Elements.size());
	Elements.push_back(MBB);
	LiveInfo[MBB] = std::make_unique<LivenessInfo>(TII, TRI, MBB);
	}