Fix constant propagation of induction variables. by dnovillo · Pull Request #1181 · KhronosGroup/SPIRV-Tools

dnovillo · 2018-01-08T17:13:12Z

This fixes #1143.
When an instruction transitions from constant to bottom (varying) in the
lattice, we were telling the propagator that the instruction was
varying, but never updating the actual value in the values table.

This led to incorrect value substitutions at the end of propagation.

alan-baker · 2018-01-08T17:59:37Z

test/opt/ccp_test.cpp

+         %16 = OpLabel
+
+; The Phi should never be considered to have the value %int_0.
+; CHECK: OpSLessThan %bool {{%\d+}} %int_10


It might be clearer to capture the result id of the phi above and ensure it is used in the less than.

alan-baker · 2018-01-08T18:00:05Z

test/opt/ccp_test.cpp

+
+; This conditional was wrongly converted into an always-true jump due to the
+; bad meet evaluation of %27.
+; CHECK: OpBranchConditional {{%\d+}} {{%\d+}} {{%\d+}}


Same here, capture the less than result and ensure its the condition of the branch.

alan-baker · 2018-01-08T18:03:14Z

source/opt/ccp_pass.h

+  // into the |values_| table. Returns SSAPropagator::kVarying.
+  SSAPropagator::PropStatus MarkInstructionVarying(ir::Instruction* instr);
+
+  // Returns true if |id| is a varying value.


The parameter name seem slightly confusing. |id| is not a SSA id, but I think that would the intuition. Suggest changing it to |val|.

It actually is an SSA id. I'll clarify. The values table maps SSA ids to SSA ids. I've added a new constant kVaryingSSAId in the code and documented its semantics.

Recommend renaming the method to IsVaryingValueId.
And the method comment should be

// Returns true if |id| is the sentinel id indicating a varying value. It is never a valid SSA id.

OR: delete the method and test against kVaryingSentinelValueId everywhere. That is probably less readable, though.

alan-baker

Minor changes.

dneto0 · 2018-01-08T18:38:15Z

source/opt/ccp_pass.cpp

 namespace opt {

+bool CCPPass::IsVaryingValue(uint32_t id) const {
+  return id == std::numeric_limits<uint32_t>::max();


You should use a named constant value for this, to document and enforce consistency with MarkInstructionVarying.

E.g. enum { kVaryingValueSentinelId = std::numeric_limits<uint32_t>::max(); };

dneto0 · 2018-01-08T18:42:17Z

source/opt/ccp_pass.h

+  // into the |values_| table. Returns SSAPropagator::kVarying.
+  SSAPropagator::PropStatus MarkInstructionVarying(ir::Instruction* instr);
+
+  // Returns true if |id| is a varying value.


Recommend renaming the method to IsVaryingValueId.
And the method comment should be

// Returns true if |id| is the sentinel id indicating a varying value. It is never a valid SSA id.

OR: delete the method and test against kVaryingSentinelValueId everywhere. That is probably less readable, though.

dneto0 · 2018-01-08T18:45:39Z

test/opt/ccp_test.cpp

+         %18 = OpSLessThan %bool %22 %int_10
+
+; This conditional was wrongly converted into an always-true jump due to the
+; bad meet evaluation of %27.


I think you mean %22 here. The example has changed since you first looked at it.

dneto0 · 2018-01-08T18:49:06Z

test/opt/ccp_test.cpp

+
+; This Phi should not have all constant arguments:
+; CHECK: OpPhi %int %int_0 {{%\d+}} {{%\d+}} {{%\d+}}
+         %22 = OpPhi %int %int_0 %12 %21 %15


Should test like this:

; CHECK [[phi:%\w+]] = OpPhi %int %int_0 {{%\w+}} [[induction_var:%\w+]] {{\d+}}

Then later as @alan-baker suggests, use [[phi]] in the OpSLessThan.
Also later add

; CHECK: [[induction_var]] = OpIAdd %int [[phi]] %int_1

dneto0 · 2018-01-08T18:54:47Z

source/opt/ccp_pass.h

+
  // Constant manager for the parent IR context.  Used to record new constants
  // generated during propagation.
  analysis::ConstantManager* const_mgr_;


You must also update the comment for the values_ member. Should say that an SSA id can map to the kVaryingValueSentinelId to indicate that the id has been proven to be varying.

dneto0 · 2018-01-08T18:56:42Z

source/opt/propagator.cpp

          return;
        }

+        // If |use_instr| is a Phi, ignore this edge.  Phi instructions can form


I'd probably put this first in the sequence of tests. It might save some time.

dnovillo

Thanks. PTAL.

dnovillo · 2018-01-08T18:27:38Z

source/opt/ccp_pass.h

+  // into the |values_| table. Returns SSAPropagator::kVarying.
+  SSAPropagator::PropStatus MarkInstructionVarying(ir::Instruction* instr);
+
+  // Returns true if |id| is a varying value.


It actually is an SSA id. I'll clarify. The values table maps SSA ids to SSA ids. I've added a new constant kVaryingSSAId in the code and documented its semantics.

dnovillo · 2018-01-08T19:06:08Z

test/opt/ccp_test.cpp

+         %16 = OpLabel
+
+; The Phi should never be considered to have the value %int_0.
+; CHECK: OpSLessThan %bool {{%\d+}} %int_10


dnovillo · 2018-01-08T19:09:00Z

test/opt/ccp_test.cpp

+
+; This conditional was wrongly converted into an always-true jump due to the
+; bad meet evaluation of %27.
+; CHECK: OpBranchConditional {{%\d+}} {{%\d+}} {{%\d+}}


dnovillo

Thanks. PTAL.

dnovillo · 2018-01-08T19:19:37Z

source/opt/ccp_pass.h

+
  // Constant manager for the parent IR context.  Used to record new constants
  // generated during propagation.
  analysis::ConstantManager* const_mgr_;


dnovillo · 2018-01-08T19:20:35Z

source/opt/propagator.cpp

          return;
        }

+        // If |use_instr| is a Phi, ignore this edge.  Phi instructions can form


s-perron

One of the if statements look strange. Could you please clarify?

s-perron · 2018-01-08T19:28:33Z

source/opt/ccp_pass.cpp

    if (it != values_.end()) {
      values_[instr->result_id()] = it->second;
      return SSAPropagator::kInteresting;
+    } else if (IsVaryingValue(it->second)) {


This looks odd. If it == values_.end() then load it->second?

Fixed, thanks. The case can actually never happen because the propagator is guaranteed to always have generated a value of the RHS of an OpCopyObject (it works in def-use and dominator order, after all). However, it would've failed to mark the LHS varying if the RHS was varying and would mark the instruction interesting, causing an additional go around the propagator.

s-perron

LGTM

This fixes KhronosGroup#1143. When an instruction transitions from constant to bottom (varying) in the lattice, we were telling the propagator that the instruction was varying, but never updating the actual value in the values table. This led to incorrect value substitutions at the end of propagation. The patch also re-enables CCP in -O and -Os.

dnovillo · 2018-01-08T20:36:52Z

Re-based and pushed to head as e5560d6.

dnovillo self-assigned this Jan 8, 2018

dnovillo requested review from alan-baker, dneto0 and s-perron January 8, 2018 17:13

alan-baker reviewed Jan 8, 2018

View reviewed changes

alan-baker requested changes Jan 8, 2018

View reviewed changes

dneto0 requested changes Jan 8, 2018

View reviewed changes

dnovillo commented Jan 8, 2018

View reviewed changes

alan-baker approved these changes Jan 8, 2018

View reviewed changes

s-perron requested changes Jan 8, 2018

View reviewed changes

s-perron approved these changes Jan 8, 2018

View reviewed changes

dnovillo force-pushed the const-prop branch from 4db35ac to e5560d6 Compare January 8, 2018 20:35

dnovillo merged commit e5560d6 into KhronosGroup:master Jan 8, 2018

Conversation

dnovillo commented Jan 8, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alan-baker left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dnovillo left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dnovillo left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

s-perron left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dnovillo Jan 8, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

s-perron left a comment

Choose a reason for hiding this comment

Uh oh!

dnovillo commented Jan 8, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

dnovillo Jan 8, 2018 •

edited

Loading