[PBQP] Cautiously update edge costs in the solver
authorArnaud A. de Grandmaison <arnaud.degrandmaison@arm.com>
Wed, 11 Feb 2015 08:25:36 +0000 (08:25 +0000)
committerArnaud A. de Grandmaison <arnaud.degrandmaison@arm.com>
Wed, 11 Feb 2015 08:25:36 +0000 (08:25 +0000)
commitde79026d5e781842b0f97e00b2fbc8ef081ebeee
tree648fd50e69b6eb5dd41f8e08971b2c8cfcc78fe3
parent9fd8cdc00917ee50db665292a47c1262d98ae00e
[PBQP] Cautiously update edge costs in the solver

The NodeMetadata are maintained in an incremental way. When an edge between
2 nodes has its cost updated, in the course of graph reduction for example,
the NodeMetadata need first to have the old edge cost removed, then the new
edge cost added. Only once the NodeMetadata have been fully updated, it
becomes safe to consider promoting the nodes to the
ConservativelyAllocatable or OptimallyReducible sets. Previously, this
promotion was occuring right after the removing the old cost, and this was
breaking the assumption that a ConservativelyAllocatable should not be
spilled.

This patch also adds asserts to:
 - enforces the invariant that a node's reduction can not be downgraded,
 - only not provably allocatable or optimally reducible nodes can be spilled.

llvm-svn: 228816
llvm/include/llvm/CodeGen/PBQP/Graph.h
llvm/include/llvm/CodeGen/PBQP/ReductionRules.h
llvm/include/llvm/CodeGen/RegAllocPBQP.h
llvm/lib/CodeGen/RegAllocPBQP.cpp
llvm/lib/Target/AArch64/AArch64PBQPRegAlloc.cpp