jdk-sandbox: comparison hotspot/src/share/vm/opto/chaitin.hpp

equal deleted inserted replaced

-:62219bdec449
+:22a05c7f3314
 // Compute effective degree as the sum of neighbors' _sizes.
 int effective_degree( uint lidx ) const;
 };
-// TEMPORARILY REPLACED WITH COMMAND LINE FLAG
+// The LiveRangeMap class is responsible for storing node to live range id mapping.
+// Each node is mapped to a live range id (a virtual register). Nodes that are
-//// !!!!! Magic Constants need to move into ad file
+// not considered for register allocation are given live range id 0.
-#ifdef SPARC
+class LiveRangeMap VALUE_OBJ_CLASS_SPEC {
-//#define FLOAT_PRESSURE 30  /*     SFLT_REG_mask.Size() - 1 */
-//#define INT_PRESSURE   23  /* NOTEMP_I_REG_mask.Size() - 1 */
+private:
-#define FLOAT_INCREMENT(regs) regs
-#else
+uint _max_lrg_id;
-//#define FLOAT_PRESSURE 6
-//#define INT_PRESSURE   6
+// Union-find map.  Declared as a short for speed.
-#define FLOAT_INCREMENT(regs) 1
+// Indexed by live-range number, it returns the compacted live-range number
-#endif
+LRG_List _uf_map;
+// Map from Nodes to live ranges
+LRG_List _names;
+// Straight out of Tarjan's union-find algorithm
+uint find_compress(const Node *node) {
+uint lrg_id = find_compress(_names[node->_idx]);
+_names.map(node->_idx, lrg_id);
+return lrg_id;
+}
+uint find_compress(uint lrg);
+public:
+const LRG_List& names() {
+return _names;
+}
+uint max_lrg_id() const {
+return _max_lrg_id;
+}
+void set_max_lrg_id(uint max_lrg_id) {
+_max_lrg_id = max_lrg_id;
+}
+uint size() const {
+return _names.Size();
+}
+uint live_range_id(uint idx) const {
+return _names[idx];
+}
+uint live_range_id(const Node *node) const {
+return _names[node->_idx];
+}
+uint uf_live_range_id(uint lrg_id) const {
+return _uf_map[lrg_id];
+}
+void map(uint idx, uint lrg_id) {
+_names.map(idx, lrg_id);
+}
+void uf_map(uint dst_lrg_id, uint src_lrg_id) {
+_uf_map.map(dst_lrg_id, src_lrg_id);
+}
+void extend(uint idx, uint lrg_id) {
+_names.extend(idx, lrg_id);
+}
+void uf_extend(uint dst_lrg_id, uint src_lrg_id) {
+_uf_map.extend(dst_lrg_id, src_lrg_id);
+}
+LiveRangeMap(uint unique)
+: _names(unique)
+, _uf_map(unique)
+, _max_lrg_id(0) {}
+uint find_id( const Node *n ) {
+uint retval = live_range_id(n);
+assert(retval == find(n),"Invalid node to lidx mapping");
+return retval;
+}
+// Reset the Union-Find map to identity
+void reset_uf_map(uint max_lrg_id);
+// Make all Nodes map directly to their final live range; no need for
+// the Union-Find mapping after this call.
+void compress_uf_map_for_nodes();
+uint find(uint lidx) {
+uint uf_lidx = _uf_map[lidx];
+return (uf_lidx == lidx) ? uf_lidx : find_compress(lidx);
+}
+// Convert a Node into a Live Range Index - a lidx
+uint find(const Node *node) {
+uint lidx = live_range_id(node);
+uint uf_lidx = _uf_map[lidx];
+return (uf_lidx == lidx) ? uf_lidx : find_compress(node);
+}
+// Like Find above, but no path compress, so bad asymptotic behavior
+uint find_const(uint lrg) const;
+// Like Find above, but no path compress, so bad asymptotic behavior
+uint find_const(const Node *node) const {
+if(node->_idx >= _names.Size()) {
+return 0; // not mapped, usual for debug dump
+}
+return find_const(_names[node->_idx]);
+}
+};
 //------------------------------Chaitin----------------------------------------
 // Briggs-Chaitin style allocation, mostly.
 class PhaseChaitin : public PhaseRegAlloc {
 friend class VMStructs;
 int _trip_cnt;
 int _alternate;
-uint _maxlrg;                 // Max live range number
 LRG &lrgs(uint idx) const { return _ifg->lrgs(idx); }
 PhaseLive *_live;             // Liveness, used in the interference graph
 PhaseIFG *_ifg;               // Interference graph (for original chunk)
 Node_List **_lrg_nodes;       // Array of node; lists for lrgs which spill
 VectorSet _spilled_once;      // Nodes that have been spilled
 VectorSet _spilled_twice;     // Nodes that have been spilled twice
-LRG_List _names;              // Map from Nodes to Live RanGes
-// Union-find map.  Declared as a short for speed.
-// Indexed by live-range number, it returns the compacted live-range number
-LRG_List _uf_map;
-// Reset the Union-Find map to identity
-void reset_uf_map( uint maxlrg );
-// Remove the need for the Union-Find mapping
-void compress_uf_map_for_nodes( );
 // Combine the Live Range Indices for these 2 Nodes into a single live
 // range.  Future requests for any Node in either live range will
 // return the live range index for the combined live range.
 void Union( const Node *src, const Node *dst );
 uint _simplified;             // Linked list head of simplified LRGs
 // Helper functions for Split()
 uint split_DEF( Node *def, Block *b, int loc, uint max, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx );
 uint split_USE( Node *def, Block *b, Node *use, uint useidx, uint max, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx );
-int clone_projs( Block *b, uint idx, Node *con, Node *copy, uint &maxlrg );
+bool clone_projs(Block *b, uint idx, Node *con, Node *copy, LiveRangeMap &lrg_map) {
+bool found_projs = clone_projs_shared(b, idx, con, copy, lrg_map.max_lrg_id());
+if(found_projs) {
+uint max_lrg_id = lrg_map.max_lrg_id();
+lrg_map.set_max_lrg_id(max_lrg_id + 1);
+}
+return found_projs;
+}
+//------------------------------clone_projs------------------------------------
+// After cloning some rematerialized instruction, clone any MachProj's that
+// follow it.  Example: Intel zero is XOR, kills flags.  Sparc FP constants
+// use G3 as an address temp.
+bool clone_projs(Block *b, uint idx, Node *con, Node *copy, uint &max_lrg_id) {
+bool found_projs = clone_projs_shared(b, idx, con, copy, max_lrg_id);
+if(found_projs) {
+max_lrg_id++;
+}
+return found_projs;
+}
+bool clone_projs_shared(Block *b, uint idx, Node *con, Node *copy, uint max_lrg_id);
 Node *split_Rematerialize(Node *def, Block *b, uint insidx, uint &maxlrg, GrowableArray<uint> splits,
 int slidx, uint *lrg2reach, Node **Reachblock, bool walkThru);
 // True if lidx is used before any real register is def'd in the block
 bool prompt_use( Block *b, uint lidx );
 Node *get_spillcopy_wide( Node *def, Node *use, uint uidx );
 public:
 PhaseChaitin( uint unique, PhaseCFG &cfg, Matcher &matcher );
 ~PhaseChaitin() {}
-// Convert a Node into a Live Range Index - a lidx
+LiveRangeMap _lrg_map;
-uint Find( const Node *n ) {
-uint lidx = n2lidx(n);
-uint uf_lidx = _uf_map[lidx];
-return (uf_lidx == lidx) ? uf_lidx : Find_compress(n);
-}
-uint Find_const( uint lrg ) const;
-uint Find_const( const Node *n ) const;
 // Do all the real work of allocate
 void Register_Allocate();
-uint n2lidx( const Node *n ) const { return _names[n->_idx]; }
 float high_frequency_lrg() const { return _high_frequency_lrg; }
 #ifndef PRODUCT
 bool trace_spilling() const { return _trace_spilling; }
 private:
 // De-SSA the world.  Assign registers to Nodes.  Use the same register for
 // all inputs to a PhiNode, effectively coalescing live ranges.  Insert
 // copies as needed.
 void de_ssa();
-uint Find_compress( const Node *n );
-uint Find( uint lidx ) {
-uint uf_lidx = _uf_map[lidx];
-return (uf_lidx == lidx) ? uf_lidx : Find_compress(lidx);
-}
-uint Find_compress( uint lidx );
-uint Find_id( const Node *n ) {
-uint retval = n2lidx(n);
-assert(retval == Find(n),"Invalid node to lidx mapping");
-return retval;
-}
 // Add edge between reg and everything in the vector.
 // Same as _ifg->add_vector(reg,live) EXCEPT use the RegMask
 // information to trim the set of interferences.  Return the
 // count of edges added.

changeset 17013	22a05c7f3314
parent 15944	095248beb690
child 19334	3aa9ca404965