The approach I'd suggest is:
1) Add maps from ElementId to index to cc::PropertyTrees (these would be in addition to the existing maps like transform_id_to_index_map which map from owner id to index). For SPv1, PropertyTreeBuilder can create the maps. Setting/clearing ElementId on a cc::Layer already triggers a property tree rebuild, so we don't need to worry about the maps becoming stale.
2) Change the animation-related callers of LayerTreeImpl::LayerIdByElementId to use the maps in property trees instead (currently, these callers first convert element id to layer id, then use the id_to_index_map to get a property tree node index).
3) Make PaintArtifactCompositor create the new maps when building cc property trees.
4) Eventually (e.g. when SPv2 is ready to ship, or if/when every cc Layer has an ElementId in SPv1), the owner_id in each property tree node should become a 'stable_id' that's the same as ElementId, and then we only need one set of maps in cc::PropertyTrees.

Other things we need:
1) ElementAnimations instances in cc depend on their corresponding LayerImpls to determine whether they're affecting the pending tree, the active tree, or both. See ElementAnimations::InitAffectedElementTypes. This logic either needs to be reworked or deleted. I'm actually not seeing why we need to know this anymore (since individual animations now know which trees they affect, we don't have the risk of starting an animation before it has a corresponding element in the active tree). loyso@, do you see any reason we still need to track ElementAnimations::has_element_in_active_list and has_element_in_pending_list? Without them we'll send extra notifications in some situations, but they'll just be ignored I think.
2) LayerTreeHostImpl::ElementIsAnimatingChanged needs to be changed so that it directly updates property tree nodes instead of calling into LayerImpl.

Sounds good, I will pick this back up presuming you meant to transfer ownership back to me, but if you or others already have something in flight or would like to do it just let me know.

I wanted to better understand how a simple animation fails with current SPv2 code path and contrast with SPv1 thus necessitating the above work. After hacking  http://crbug.com/674317#c6  a brief recap of my notes working backwards as:

- AnimationPlayer::NotifyAnimationStarted is never called
- cc::AnimationPlayer.element_animations_ is null
- in animation_player UpdateTickingState is_ticking is never true
- AnimationHost::UpdateAnimationState never sees NeedsTickAnims() as true
- ElementAnimations never see InitAffectedElementTypes and ElementRegistered called
- thus we never turn on ElementAnimations::has_element_in_active_list, which means we never add the animation player to the list of ticking players in AnimationPlayer::UpdateTickingState
- mutator_host_client->IsElementInList(..., ElementListType::{ACTIVE,PENDING}) in ElementAnimations::InitAffectedElementTypes() never returns true for the involved element_id_
- LayerTree::IsElementInList always returns false
- LayerTree::LayerByElementId does not contain the element id
- LayerTree::RegisterElement is never called. There are only two callsites, (1) cc::Layer::SetLayerTreeHost and (2) Layer::SetElementId().

In SPv1, cc::Layer element id is set via
CompositedLayerMapping::updateElementIdAndCompositorMutableProperties. However,
the layer tree host is still null at that time. LayerTree::RegisterElement
ends up being called in Layer::SetLayerTreeHost once we have a host (retrieved
via the parent, see Layer::SetParent).

In SPv2's PaintArtifactCompositor (which currently rebuilds all layers each
time) the input host is first always nullptr in calls to
cc::Layer::SetLayerTreeHost when we're removing all layers, and so we never
call host->GetLayerTree()->RegisterElement(). When we subsequently do call
cc::Layer::AddChild() to add the new layers to the root layer, we've not
set element id on either the root or new layer(s), so the call stack as:

cc::Layer::AddChild
cc::Layer::InsertChild
cc::Layer::SetParent
cc::PictureLayer::SetLayerTreeHost
cc::Layer::SetLayerTreeHost

doesn't end up calling LayerTree::RegisterElement.

Just a side note: As for SPv1, those two callsites correspond to two cases:
1) We set ElementId for an orphaned layer, so RegisterElement needs to be called on addition.
2) We set ElementId for a layer which is already added into the tree, so we call RegisterElement right from the SetElementId.

Overall: For the current cc/animation code you need to call AnimationHost::RegisterElement to indicate a creation of the pending/active target element.

re#1: What do you mean by "individual animations now know which trees they affect"? Do you mean cc::Animation::  affects_active_elements_ and affects_pending_elements_?

We call set_affects_active_elements in ActivateAnimations for a ticking player. So it depends on Player's activation. Fun fact: we erase cc::Animation if it has no active AND pending targets. Can we erase active/pending logic for individual cc::Animations?

We promote animations in AnimationPlayer::PromoteStartedAnimations (See the creation of AnimationEvent::STARTED for cc::Animation with needs_synchronized_start_time) only for ticking players. We start to tick a player only if it has a target element as active. This is how we deal with rasterization delays (pending tree activation process).

AnimationPlayer::PromoteStartedAnimations only promotes animations that affect active elements. The logic for preventing ticking animations without active observers used to be needed because there was no notion of which types of observers an animation affected, so without this logic we could start an animation even before the corresponding layer was in the active tree (which meant that by the time we started drawing the layer, we were already partway through the animation). But with the current logic, an animation won't start affecting active elements until the pending tree activation process is done, so even if we tick the animation, it won't get past the Starting state.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8

commit 8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8
Author: wkorman <wkorman@chromium.org>
Date: Tue Jan 03 23:55:33 2017

Store compositor element id in paint properties for animated objects.

BUG= 674258 , 674317 
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2

Review-Url: https://codereview.chromium.org/2608543002
Cr-Commit-Position: refs/heads/master@{#441255}

[modify] https://crrev.com/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8/third_party/WebKit/Source/core/paint/PaintPropertyTreeBuilder.cpp
[modify] https://crrev.com/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8/third_party/WebKit/Source/core/paint/PaintPropertyTreeBuilderTest.cpp
[modify] https://crrev.com/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8/third_party/WebKit/Source/core/paint/PaintPropertyTreeBuilderTest.h
[modify] https://crrev.com/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8/third_party/WebKit/Source/core/paint/PaintPropertyTreeUpdateTests.cpp
[add] https://crrev.com/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8/third_party/WebKit/Source/core/paint/test_data/opacity-animation.html
[add] https://crrev.com/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8/third_party/WebKit/Source/core/paint/test_data/transform-animation.html
[modify] https://crrev.com/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8/third_party/WebKit/Source/platform/graphics/paint/EffectPaintPropertyNode.cpp
[modify] https://crrev.com/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8/third_party/WebKit/Source/platform/graphics/paint/EffectPaintPropertyNode.h
[modify] https://crrev.com/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8/third_party/WebKit/Source/platform/graphics/paint/TransformPaintPropertyNode.cpp
[modify] https://crrev.com/8a4ccdb5a2bef0e128a64cea83fa9de3daf785a8/third_party/WebKit/Source/platform/graphics/paint/TransformPaintPropertyNode.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/6f1b23711b3e28fd78646e3adfe0ca7986bd94b5

commit 6f1b23711b3e28fd78646e3adfe0ca7986bd94b5
Author: wkorman <wkorman@chromium.org>
Date: Wed Jan 04 23:41:24 2017

Add documentation on cc/Blink nodes, ids, and indices.

BUG= 674258 
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2

Review-Url: https://codereview.chromium.org/2610963002
Cr-Commit-Position: refs/heads/master@{#441514}

[modify] https://crrev.com/6f1b23711b3e28fd78646e3adfe0ca7986bd94b5/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp
[modify] https://crrev.com/6f1b23711b3e28fd78646e3adfe0ca7986bd94b5/third_party/WebKit/Source/platform/graphics/paint/README.md

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/a4c2d8689df6df3e4645b24beb4d69a41f644e9a

commit a4c2d8689df6df3e4645b24beb4d69a41f644e9a
Author: wkorman <wkorman@chromium.org>
Date: Thu Jan 05 01:16:37 2017

Rename cc property tree node owner_id to owning_layer_id.

Also added brief documentation on the primary node id fields. While it's
slightly redundant IMO it's still helpful for new folks reading the code
given how many different types of ids are in the code base.

BUG= 674258 
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel

Review-Url: https://codereview.chromium.org/2612883002
Cr-Commit-Position: refs/heads/master@{#441541}

[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/input/scroll_state.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/layers/layer_utils.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/clip_node.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/clip_node.h
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/draw_property_utils.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/effect_node.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/effect_node.h
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/layer_tree_host_common_unittest.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/layer_tree_host_impl.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/layer_tree_impl.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/property_tree.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/property_tree_builder.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/scroll_node.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/scroll_node.h
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/transform_node.cc
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/cc/trees/transform_node.h
[modify] https://crrev.com/a4c2d8689df6df3e4645b24beb4d69a41f644e9a/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/e14c8ed4a52032ed6569a95febe1d2c73af782dc

commit e14c8ed4a52032ed6569a95febe1d2c73af782dc
Author: wkorman <wkorman@chromium.org>
Date: Tue Jan 10 22:29:10 2017

Build mapping from element id to transform/effect nodes.

Update cc PropertyTreeBuilder to build additional maps from element id
(used for animation purposes) to the involved transform and effect
nodes.

This map is currently unused but will be used in subsequent patches so
as to eventually allow us to remove the existing maps from layer id to
these same nodes.

This is also a required step for SPv2 composited animation support
wherein, again in a subsequent patch, we will populate these maps in
PaintArtifactCompositor.

BUG= 674258 
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel

Review-Url: https://codereview.chromium.org/2612093002
Cr-Commit-Position: refs/heads/master@{#442711}

[modify] https://crrev.com/e14c8ed4a52032ed6569a95febe1d2c73af782dc/cc/trees/layer_tree_host_unittest.cc
[modify] https://crrev.com/e14c8ed4a52032ed6569a95febe1d2c73af782dc/cc/trees/property_tree.cc
[modify] https://crrev.com/e14c8ed4a52032ed6569a95febe1d2c73af782dc/cc/trees/property_tree.h
[modify] https://crrev.com/e14c8ed4a52032ed6569a95febe1d2c73af782dc/cc/trees/property_tree_builder.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/d7ab6d03146c909de6078e21b59a4cdeb0b233d2

commit d7ab6d03146c909de6078e21b59a4cdeb0b233d2
Author: wkorman <wkorman@chromium.org>
Date: Wed Jan 11 00:50:00 2017

Revise LayerTreeHostImpl to use new element-id-to-node-index maps.

Improves on element-id-to-layer-id followed by layer-id-to-node-index lookups.

BUG= 674258 
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel;master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2

Review-Url: https://codereview.chromium.org/2619383004
Cr-Commit-Position: refs/heads/master@{#442743}

[modify] https://crrev.com/d7ab6d03146c909de6078e21b59a4cdeb0b233d2/cc/trees/layer_tree_host_impl.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/c2d1f65f2eaf620936ed56c42fe3e6235674600b

commit c2d1f65f2eaf620936ed56c42fe3e6235674600b
Author: wkorman <wkorman@chromium.org>
Date: Wed Jan 11 22:45:32 2017

Clarify property tree id-to-index map names.

Follow-up from discussion on http://crrev.com/2612093002.

BUG= 674258 
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel

Review-Url: https://codereview.chromium.org/2616353003
Cr-Commit-Position: refs/heads/master@{#443027}

[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/input/scrollbar_animation_controller_linear_fade.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/input/scrollbar_animation_controller_thinning.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/layers/layer.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/layers/layer_impl.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/layers/render_surface_impl.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/trees/layer_tree_host_common_unittest.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/trees/layer_tree_host_impl.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/trees/layer_tree_host_unittest.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/trees/layer_tree_impl.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/trees/property_tree.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/trees/property_tree.h
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/cc/trees/property_tree_builder.cc
[modify] https://crrev.com/c2d1f65f2eaf620936ed56c42fe3e6235674600b/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/d8a99a8083a992e00dc0316cc621ad9f0d9b6699

commit d8a99a8083a992e00dc0316cc621ad9f0d9b6699
Author: wkorman <wkorman@chromium.org>
Date: Thu Jan 12 20:43:02 2017

Add map from element id to scroll node index.

Essentially a scroll node specific version of
http://crrev.com/2612093002 which was only omitted there
in the interest of incrementality.

BUG= 674258 
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel

Review-Url: https://codereview.chromium.org/2623313003
Cr-Commit-Position: refs/heads/master@{#443348}

[modify] https://crrev.com/d8a99a8083a992e00dc0316cc621ad9f0d9b6699/cc/trees/layer_tree_host_impl.cc
[modify] https://crrev.com/d8a99a8083a992e00dc0316cc621ad9f0d9b6699/cc/trees/layer_tree_host_unittest.cc
[modify] https://crrev.com/d8a99a8083a992e00dc0316cc621ad9f0d9b6699/cc/trees/property_tree.cc
[modify] https://crrev.com/d8a99a8083a992e00dc0316cc621ad9f0d9b6699/cc/trees/property_tree.h
[modify] https://crrev.com/d8a99a8083a992e00dc0316cc621ad9f0d9b6699/cc/trees/property_tree_builder.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/c51a822ea88495a1a4de015933f940b8618db0dd

commit c51a822ea88495a1a4de015933f940b8618db0dd
Author: wkorman <wkorman@chromium.org>
Date: Fri Jan 13 21:41:53 2017

Rename a few compositor property tree methods for clarity.

BUG= 674258 
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2

Review-Url: https://codereview.chromium.org/2626353002
Cr-Commit-Position: refs/heads/master@{#443681}

[modify] https://crrev.com/c51a822ea88495a1a4de015933f940b8618db0dd/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/9bf3bd10297e90363f9d68ba23569ba4e2fe57da

commit 9bf3bd10297e90363f9d68ba23569ba4e2fe57da
Author: wkorman <wkorman@chromium.org>
Date: Tue Jan 17 21:28:21 2017

Factor PropertyTreeManager out of PaintArtifactCompositor.

BUG= 674258 
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2

Review-Url: https://codereview.chromium.org/2627113005
Cr-Commit-Position: refs/heads/master@{#444150}

[modify] https://crrev.com/9bf3bd10297e90363f9d68ba23569ba4e2fe57da/third_party/WebKit/Source/platform/BUILD.gn
[modify] https://crrev.com/9bf3bd10297e90363f9d68ba23569ba4e2fe57da/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp
[add] https://crrev.com/9bf3bd10297e90363f9d68ba23569ba4e2fe57da/third_party/WebKit/Source/platform/graphics/compositing/PropertyTreeManager.cpp
[add] https://crrev.com/9bf3bd10297e90363f9d68ba23569ba4e2fe57da/third_party/WebKit/Source/platform/graphics/compositing/PropertyTreeManager.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/a26a3a7b14e17d5d76b393f7df52210346b359cb

commit a26a3a7b14e17d5d76b393f7df52210346b359cb
Author: wkorman <wkorman@chromium.org>
Date: Mon Jan 23 20:49:42 2017

Populate cc element id maps for transform/effect nodes.

Scroll nodes are being handled similarly in
http://crrev.com/2638333007.

BUG= 674258 
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2

Review-Url: https://codereview.chromium.org/2642183003
Cr-Commit-Position: refs/heads/master@{#445477}

[modify] https://crrev.com/a26a3a7b14e17d5d76b393f7df52210346b359cb/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositorTest.cpp
[modify] https://crrev.com/a26a3a7b14e17d5d76b393f7df52210346b359cb/third_party/WebKit/Source/platform/graphics/compositing/PropertyTreeManager.cpp

Remaining work here is the "Other things we need" items ajuma@ mentioned above:

1) ElementAnimations instances in cc depend on their corresponding LayerImpls to determine whether they're affecting the pending tree, the active tree, or both.
2) LayerTreeHostImpl::ElementIsAnimatingChanged needs to be changed so that it directly updates property tree nodes instead of calling into LayerImpl.

There is a DCHECK I wanted to add to cc side code that is only failing on animation trying to tick through layer id, so I can take adding element id to effect and transform node, which should cover 2).

The remaining (1) is part of  issue 709137  so duping to that as it will fall out of that more comprehensive effort.