Top

PhaseIdealLoop クラス, 及びループに関する高レベル中間語(Ideal)クラス (LoopNode, CountedLoopNode, CountedLoopEndNode, LoopLimitNode, IdealLoopTree, PhaseIdealLoop, LoopTreeIterator)

これらは, C2 JIT Compiler 内の処理フェーズおよび関連する高レベル中間語を表すクラス. より具体的に言うと, ループ最適化処理を表すクラス.

概要(Summary)

bytecode 命令にループを表す命令はないが, ループを検出することは最適化を行う上では極めて重要になる. そこでパースが終わった後, C2 はループの検出を行う.

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
    //
    //                  I D E A L I Z E D   L O O P S
    //
    // Idealized loops are the set of loops I perform more interesting
    // transformations on, beyond simple hoisting.

パース終了時のループは「自分自身が入力となっている RegionNode」という形になっている. C2 は regular loops の loop header となっている RegionNode を検出し, LoopNode で置き換える.

また, ループの中でも制御変数が固定の初期値から始まり固定の増分幅で変化していくもの(Fortran の DO ループ的なもの)については, 特に最適化しやすいので特別に CountedLoopNode というノードに変換する. なお, CountedLoopNode に関連したノードとして以下のノードがある.

CountedLoopNode が表すループの終了判定を示す特殊な IfNode.

CountedLoopNode の終了時の制御変数の値を表す Node (終値ぴったりで終わるとは限らず, 初期値と増分によっては終値を微妙に超えることがある. LoopLimitNode は正確な終了時の値を計算する).

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
    //------------------------------Counted Loops----------------------------------
    // Counted loops are all trip-counted loops, with exactly 1 trip-counter exit
    // path (and maybe some other exit paths).  The trip-counter exit is always
    // last in the loop.  The trip-counter have to stride by a constant;
    // the exit value is also loop invariant.

    // CountedLoopNodes and CountedLoopEndNodes come in matched pairs.  The
    // CountedLoopNode has the incoming loop control and the loop-back-control
    // which is always the IfTrue before the matching CountedLoopEndNode.  The
    // CountedLoopEndNode has an incoming control (possibly not the
    // CountedLoopNode if there is control flow in the loop), the post-increment
    // trip-counter value, and the limit.  The trip-counter value is always of
    // the form (Op old-trip-counter stride).  The old-trip-counter is produced
    // by a Phi connected to the CountedLoopNode.  The stride is constant.
    // The Op is any commutable opcode, including Add, Mul, Xor.  The
    // CountedLoopEndNode also takes in the loop-invariant limit value.

    // From a CountedLoopNode I can reach the matching CountedLoopEndNode via the
    // loop-back control.  From CountedLoopEndNodes I can reach CountedLoopNodes
    // via the old-trip-counter from the Op node.

クラス一覧(class list)

LoopNode

概要(Summary)

RegionNode クラスのサブクラス.

ループになっている制御構造を表す Node.

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
    // Simple loop header.  Fall in path on left, loop-back path on right.
    class LoopNode : public RegionNode {

使われ方(Usage)

生成箇所(where its instances are created)

以下の箇所で(のみ)生成されている.

そして, この関数は現在は以下のパスで(のみ)呼び出されている.

PhaseIdealLoop::build_and_optimize()
-> IdealLoopTree::beautify_loops()
   -> IdealLoopTree::split_outer_loop()
-> IdealLoopTree::iteration_split()
   -> IdealLoopTree::iteration_split_impl()
      -> PhaseIdealLoop::partial_peel()

内部構造(Internal structure)

(control input も含めて) 3つの入力ノードを持つ. それぞれの入力の意味は以下の通り (この enum の順で入力される).

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
      // Names for edge indices
      enum { Self=0, EntryControl, LoopBackControl };

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
      LoopNode( Node *entry, Node *backedge ) : RegionNode(3), _loop_flags(0), _unswitch_count(0) {
        init_class_id(Class_Loop);
        init_req(EntryControl, entry);
        init_req(LoopBackControl, backedge);
      }

詳細(Details)

See: here for details

CountedLoopNode

概要(Summary)

特殊な LoopNode クラス.

制御変数が固定の初期値から始まり固定の増分幅で変化していくループを表す Node.

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
    // CountedLoopNodes head simple counted loops.  CountedLoopNodes have as
    // inputs the incoming loop-start control and the loop-back control, so they
    // act like RegionNodes.  They also take in the initial trip counter, the
    // loop-invariant stride and the loop-invariant limit value.  CountedLoopNodes
    // produce a loop-body control and the trip counter value.  Since
    // CountedLoopNodes behave like RegionNodes I still have a standard CFG model.

    class CountedLoopNode : public LoopNode {

使われ方(Usage)

PhaseIdealLoop::is_counted_loop() 内で(のみ)生成されている. そして, この関数は現在は以下のパスで(のみ)呼び出されている.

PhaseIdealLoop::build_and_optimize()
-> IdealLoopTree::counted_loop()
   -> PhaseIdealLoop::is_counted_loop()

内部構造(Internal structure)

(control input も含めて) 3つの入力ノードを持つ. それぞれの入力の意味は以下の通り.

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
      CountedLoopNode( Node *entry, Node *backedge )
        : LoopNode(entry, backedge), _main_idx(0), _trip_count(max_juint),
          _profile_trip_cnt(COUNT_UNKNOWN), _unrolled_count_log2(0),
          _node_count_before_unroll(0) {
        init_class_id(Class_CountedLoop);
        // Initialize _trip_count to the largest possible value.
        // Will be reset (lower) if the loop's trip count is known.
      }

詳細(Details)

See: here for details

CountedLoopEndNode

概要(Summary)

CountedLoopNode クラスと併用される Node.

CountedLoopNode が表すループの終了判定を示す特殊な IfNode.

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
    // CountedLoopEndNodes end simple trip counted loops.  They act much like
    // IfNodes.
    class CountedLoopEndNode : public IfNode {

使われ方(Usage)

PhaseIdealLoop::is_counted_loop() 内で(のみ)生成されている. そして, この関数は現在は以下のパスで(のみ)呼び出されている.

PhaseIdealLoop::build_and_optimize()
-> IdealLoopTree::counted_loop()
   -> PhaseIdealLoop::is_counted_loop()

内部構造(Internal structure)

(control input も含めて) 2つの入力ノードを持つ. それぞれの入力の意味は以下の通り.

(<= 基本的に IfNode と同じ. というか PhaseIdealLoop::is_counted_loop() 内で IfNode を置き換えて作成するので, 入力はそのまま引き継ぐ).

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
      CountedLoopEndNode( Node *control, Node *test, float prob, float cnt )
        : IfNode( control, test, prob, cnt) {
        init_class_id(Class_CountedLoopEnd);
      }

詳細(Details)

See: here for details

LoopLimitNode

概要(Summary)

CountedLoopNode クラスと併用される Node.

CountedLoopNode の終了時の制御変数の値を表す (終値ぴったりで終わるとは限らず, 初期値と増分によっては終値を微妙に超えることがある. LoopLimitNode は正確な終了時の値を計算する).

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
    // Counted Loop limit node which represents exact final iterator value:
    // trip_count = (limit - init_trip + stride - 1)/stride
    // final_value= trip_count * stride + init_trip.
    // Use HW instructions to calculate it when it can overflow in integer.
    // Note, final_value should fit into integer since counted loop has
    // limit check: limit <= max_int-stride.
    class LoopLimitNode : public Node {

使われ方(Usage)

PhaseIdealLoop::exact_limit() 内で(のみ)生成されている.

内部構造(Internal structure)

(control input も含めて) 4つの入力ノードを持つ. ただし control input は常に空 (0 が設定される).

その他の 3つは以下の通り.

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
      LoopLimitNode( Compile* C, Node *init, Node *limit, Node *stride ) : Node(0,init,limit,stride) {
        // Put it on the Macro nodes list to optimize during macro nodes expansion.
        init_flags(Flag_is_macro);
        C->add_macro_node(this);
      }

詳細(Details)

See: here for details

PhaseIdealLoop

概要(Summary)

Phase クラスの具象サブクラスの1つ.

ループの最適化を行う.

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
    // Computes the mapping from Nodes to IdealLoopTrees.  Organizes IdealLoopTrees into a
    // loop tree.  Drives the loop-based transformations on the ideal graph.
    class PhaseIdealLoop : public PhaseTransform {

使われ方(Usage)

以下の箇所で(のみ)使用されている.

詳細(Details)

See: here for details

IdealLoopTree

概要(Summary)

PhaseIdealLoop クラス内で使用される補助クラス(ResourceObjクラス).

コード中のループ構造を (そのネスト構造も含めて) 表すためのクラス. 1つの IdealLoopTree オブジェクトが 1つのループに対応する.

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
    class IdealLoopTree : public ResourceObj {

使われ方(Usage)

インスタンスの格納場所(where its instances are stored)

以下の箇所に(のみ)格納されている.

(正確には, このフィールドは IdealLoopTree の木構造を格納するフィールド. IdealLoopTree オブジェクトは _parent フィールド, _next フィールド, 及び _child フィールドで次の IdealLoopTree オブジェクトを指せる構造になっている. その PhaseIdealLoop 用の IdealLoopTree オブジェクトは全てこの木構造に格納されている)

各ループの開始点となる Node や終端点となる Node (正確にはそれらの Node::_idx フィールドの値) から IdealLoopTree オブジェクトへの写像

(正確には, このフィールドは Node_Array オブジェクトを格納するフィールド. IdealLoopTree オブジェクトは Node オブジェクトではないが Node* にキャストして格納されている)

(格納している IdealLoopTree オブジェクト自体は, PhaseIdealLoop::_ltree_root に格納されているものと重複)

生成箇所(where its instances are created)

以下の箇所で(のみ)生成されている.

そして, これらの関数は現在は以下のパスで(のみ)呼び出されている.

PhaseIdealLoop::build_and_optimize()
-> PhaseIdealLoop::build_loop_tree()
   -> PhaseIdealLoop::build_loop_tree_impl()
-> IdealLoopTree::beautify_loops()
   -> IdealLoopTree::merge_many_backedges()

詳細(Details)

See: here for details

LoopTreeIterator

概要(Summary)

PhaseIdealLoop クラス内で使用される補助クラス.

ある IdealLoopTree を起点としてその子要素をたどるためのイテレータクラス(StackObjクラス). なお, 辿る順番は preorder で left-to-right.

    ((cite: hotspot/src/share/vm/opto/loopnode.hpp))
    // Iterate over the loop tree using a preorder, left-to-right traversal.
    //
    // Example that visits all counted loops from within PhaseIdealLoop
    //
    //  for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
    //   IdealLoopTree* lpt = iter.current();
    //   if (!lpt->is_counted()) continue;
    //   ...
    class LoopTreeIterator : public StackObj {

使われ方(Usage)

以下の箇所で(のみ)使用されている.

詳細(Details)

See: here for details

This document is available under the GNU GENERAL PUBLIC LICENSE Version 2.