-PBQP::Graph RegAllocPBQP::constructPBQPProblem() {
-
- typedef std::vector<const LiveInterval*> LIVector;
- typedef std::vector<unsigned> RegVector;
-
- // This will store the physical intervals for easy reference.
- LIVector physIntervals;
-
- // Start by clearing the old node <-> live interval mappings & allowed sets
- li2Node.clear();
- node2LI.clear();
- allowedSets.clear();
-
- // Populate physIntervals, update preg use:
- for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
- itr != end; ++itr) {
-
- if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
- physIntervals.push_back(itr->second);
- mri->setPhysRegUsed(itr->second->reg);
- }
- }
-
- // Iterate over vreg intervals, construct live interval <-> node number
- // mappings.
- for (RegSet::const_iterator itr = vregsToAlloc.begin(),
- end = vregsToAlloc.end();
- itr != end; ++itr) {
- const LiveInterval *li = &lis->getInterval(*itr);
-
- li2Node[li] = node2LI.size();
- node2LI.push_back(li);
- }
-
- // Get the set of potential coalesces.
- CoalesceMap coalesces;
-
- if (pbqpCoalescing) {
- coalesces = findCoalesces();
- }
-
- // Construct a PBQP solver for this problem
- PBQP::Graph problem;
- problemNodes.resize(vregsToAlloc.size());
-
- // Resize allowedSets container appropriately.
- allowedSets.resize(vregsToAlloc.size());
-
- BitVector ReservedRegs = tri->getReservedRegs(*mf);
-
- // Iterate over virtual register intervals to compute allowed sets...
- for (unsigned node = 0; node < node2LI.size(); ++node) {
-
- // Grab pointers to the interval and its register class.
- const LiveInterval *li = node2LI[node];
- const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
-
- // Start by assuming all allocable registers in the class are allowed...
- RegVector liAllowed;
- TargetRegisterClass::iterator aob = liRC->allocation_order_begin(*mf);
- TargetRegisterClass::iterator aoe = liRC->allocation_order_end(*mf);
- for (TargetRegisterClass::iterator it = aob; it != aoe; ++it)
- if (!ReservedRegs.test(*it))
- liAllowed.push_back(*it);
-
- // Eliminate the physical registers which overlap with this range, along
- // with all their aliases.
- for (LIVector::iterator pItr = physIntervals.begin(),
- pEnd = physIntervals.end(); pItr != pEnd; ++pItr) {
-
- if (!li->overlaps(**pItr))
- continue;
-
- unsigned pReg = (*pItr)->reg;
-
- // If we get here then the live intervals overlap, but we're still ok
- // if they're coalescable.
- if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) {
- DEBUG(dbgs() << "CoalescingOverride: (" << li->reg << ", " << pReg << ")\n");
- continue;
- }
-
- // If we get here then we have a genuine exclusion.
-
- // Remove the overlapping reg...
- RegVector::iterator eraseItr =
- std::find(liAllowed.begin(), liAllowed.end(), pReg);
-
- if (eraseItr != liAllowed.end())
- liAllowed.erase(eraseItr);
-
- const unsigned *aliasItr = tri->getAliasSet(pReg);
-
- if (aliasItr != 0) {
- // ...and its aliases.
- for (; *aliasItr != 0; ++aliasItr) {
- RegVector::iterator eraseItr =
- std::find(liAllowed.begin(), liAllowed.end(), *aliasItr);
-
- if (eraseItr != liAllowed.end()) {
- liAllowed.erase(eraseItr);
- }
- }
- }
- }
-
- // Copy the allowed set into a member vector for use when constructing cost
- // vectors & matrices, and mapping PBQP solutions back to assignments.
- allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end());
-
- // Set the spill cost to the interval weight, or epsilon if the
- // interval weight is zero
- PBQP::PBQPNum spillCost = (li->weight != 0.0) ?
- li->weight : std::numeric_limits<PBQP::PBQPNum>::min();
-
- // Build a cost vector for this interval.
- problemNodes[node] =
- problem.addNode(
- buildCostVector(li->reg, allowedSets[node], coalesces, spillCost));
-
- }
-
-
- // Now add the cost matrices...
- for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) {
- const LiveInterval *li = node2LI[node1];
-
- // Test for live range overlaps and insert interference matrices.
- for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) {
- const LiveInterval *li2 = node2LI[node2];
-
- CoalesceMap::const_iterator cmItr =
- coalesces.find(RegPair(li->reg, li2->reg));
-
- PBQP::Matrix *m = 0;
-
- if (cmItr != coalesces.end()) {
- m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2],
- cmItr->second);
- }
- else if (li->overlaps(*li2)) {
- m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]);
- }
-
- if (m != 0) {
- problem.addEdge(problemNodes[node1],
- problemNodes[node2],
- *m);
-
- delete m;
- }
- }
- }
-
- assert(problem.getNumNodes() == allowedSets.size());
-/*
- std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
- << problem.getNumEdges() << " edges.\n";
-
- problem.printDot(std::cerr);
-*/
- // We're done, PBQP problem constructed - return it.
- return problem;
-}
-