1 /*
   2  * Copyright (c) 2000, 2019, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #ifndef SHARE_OPTO_OUTPUT_HPP
  26 #define SHARE_OPTO_OUTPUT_HPP
  27 
  28 #include "opto/ad.hpp"
  29 #include "opto/block.hpp"
  30 #include "opto/node.hpp"
  31 
  32 class Arena;
  33 class Bundle;
  34 class Block;
  35 class Block_Array;
  36 class Node;
  37 class Node_Array;
  38 class Node_List;
  39 class PhaseCFG;
  40 class PhaseChaitin;
  41 class Pipeline_Use_Element;
  42 class Pipeline_Use;
  43 
  44 #ifndef PRODUCT
  45 #define DEBUG_ARG(x) , x
  46 #else
  47 #define DEBUG_ARG(x)
  48 #endif
  49 
  50 // Define the initial sizes for allocation of the resizable code buffer
  51 enum {
  52   initial_const_capacity =   4 * 1024,
  53 };
  54 
  55 //------------------------------Scheduling----------------------------------
  56 // This class contains all the information necessary to implement instruction
  57 // scheduling and bundling.
  58 class Scheduling {
  59 
  60 private:
  61   // Arena to use
  62   Arena *_arena;
  63 
  64   // Control-Flow Graph info
  65   PhaseCFG *_cfg;
  66 
  67   // Register Allocation info
  68   PhaseRegAlloc *_regalloc;
  69 
  70   // Number of nodes in the method
  71   uint _node_bundling_limit;
  72 
  73   // List of scheduled nodes. Generated in reverse order
  74   Node_List _scheduled;
  75 
  76   // List of nodes currently available for choosing for scheduling
  77   Node_List _available;
  78 
  79   // For each instruction beginning a bundle, the number of following
  80   // nodes to be bundled with it.
  81   Bundle *_node_bundling_base;
  82 
  83   // Mapping from register to Node
  84   Node_List _reg_node;
  85 
  86   // Free list for pinch nodes.
  87   Node_List _pinch_free_list;
  88 
  89   // Latency from the beginning of the containing basic block (base 1)
  90   // for each node.
  91   unsigned short *_node_latency;
  92 
  93   // Number of uses of this node within the containing basic block.
  94   short *_uses;
  95 
  96   // Schedulable portion of current block.  Skips Region/Phi/CreateEx up
  97   // front, branch+proj at end.  Also skips Catch/CProj (same as
  98   // branch-at-end), plus just-prior exception-throwing call.
  99   uint _bb_start, _bb_end;
 100 
 101   // Latency from the end of the basic block as scheduled
 102   unsigned short *_current_latency;
 103 
 104   // Remember the next node
 105   Node *_next_node;
 106 
 107   // Use this for an unconditional branch delay slot
 108   Node *_unconditional_delay_slot;
 109 
 110   // Pointer to a Nop
 111   MachNopNode *_nop;
 112 
 113   // Length of the current bundle, in instructions
 114   uint _bundle_instr_count;
 115 
 116   // Current Cycle number, for computing latencies and bundling
 117   uint _bundle_cycle_number;
 118 
 119   // Bundle information
 120   Pipeline_Use_Element _bundle_use_elements[resource_count];
 121   Pipeline_Use         _bundle_use;
 122 
 123   // Dump the available list
 124   void dump_available() const;
 125 
 126 public:
 127   Scheduling(Arena *arena, Compile &compile);
 128 
 129   // Destructor
 130   NOT_PRODUCT( ~Scheduling(); )
 131 
 132   // Step ahead "i" cycles
 133   void step(uint i);
 134 
 135   // Step ahead 1 cycle, and clear the bundle state (for example,
 136   // at a branch target)
 137   void step_and_clear();
 138 
 139   Bundle* node_bundling(const Node *n) {
 140     assert(valid_bundle_info(n), "oob");
 141     return (&_node_bundling_base[n->_idx]);
 142   }
 143 
 144   bool valid_bundle_info(const Node *n) const {
 145     return (_node_bundling_limit > n->_idx);
 146   }
 147 
 148   bool starts_bundle(const Node *n) const {
 149     return (_node_bundling_limit > n->_idx && _node_bundling_base[n->_idx].starts_bundle());
 150   }
 151 
 152   // Do the scheduling
 153   void DoScheduling();
 154 
 155   // Compute the local latencies walking forward over the list of
 156   // nodes for a basic block
 157   void ComputeLocalLatenciesForward(const Block *bb);
 158 
 159   // Compute the register antidependencies within a basic block
 160   void ComputeRegisterAntidependencies(Block *bb);
 161   void verify_do_def( Node *n, OptoReg::Name def, const char *msg );
 162   void verify_good_schedule( Block *b, const char *msg );
 163   void anti_do_def( Block *b, Node *def, OptoReg::Name def_reg, int is_def );
 164   void anti_do_use( Block *b, Node *use, OptoReg::Name use_reg );
 165 
 166   // Add a node to the current bundle
 167   void AddNodeToBundle(Node *n, const Block *bb);
 168 
 169   // Add a node to the list of available nodes
 170   void AddNodeToAvailableList(Node *n);
 171 
 172   // Compute the local use count for the nodes in a block, and compute
 173   // the list of instructions with no uses in the block as available
 174   void ComputeUseCount(const Block *bb);
 175 
 176   // Choose an instruction from the available list to add to the bundle
 177   Node * ChooseNodeToBundle();
 178 
 179   // See if this Node fits into the currently accumulating bundle
 180   bool NodeFitsInBundle(Node *n);
 181 
 182   // Decrement the use count for a node
 183  void DecrementUseCounts(Node *n, const Block *bb);
 184 
 185   // Garbage collect pinch nodes for reuse by other blocks.
 186   void garbage_collect_pinch_nodes();
 187   // Clean up a pinch node for reuse (helper for above).
 188   void cleanup_pinch( Node *pinch );
 189 
 190   // Information for statistics gathering
 191 #ifndef PRODUCT
 192 private:
 193   // Gather information on size of nops relative to total
 194   uint _branches, _unconditional_delays;
 195 
 196   static uint _total_nop_size, _total_method_size;
 197   static uint _total_branches, _total_unconditional_delays;
 198   static uint _total_instructions_per_bundle[Pipeline::_max_instrs_per_cycle+1];
 199 
 200 public:
 201   static void print_statistics();
 202 
 203   static void increment_instructions_per_bundle(uint i) {
 204     _total_instructions_per_bundle[i]++;
 205   }
 206 
 207   static void increment_nop_size(uint s) {
 208     _total_nop_size += s;
 209   }
 210 
 211   static void increment_method_size(uint s) {
 212     _total_method_size += s;
 213   }
 214 #endif
 215 
 216 };
 217 
 218 #endif // SHARE_OPTO_OUTPUT_HPP