hiraditya (Aditya Kumar)
User

Projects

User does not belong to any projects.

User Details

User Since
Mar 5 2014, 4:23 PM (185 w, 1 d)

Recent Activity

Tue, Sep 12

hiraditya committed rL313116: [GVNHoist] Factor out reachability to search for anticipable instructions….
[GVNHoist] Factor out reachability to search for anticipable instructions…
Tue, Sep 12, 10:29 PM
hiraditya closed D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly by committing rL313116: [GVNHoist] Factor out reachability to search for anticipable instructions….
Tue, Sep 12, 10:29 PM

Fri, Sep 8

hiraditya updated the diff for D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

use depth_first

Fri, Sep 8, 3:44 PM
hiraditya updated the diff for D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

added auto to relevant places.

Fri, Sep 8, 2:59 PM

Thu, Sep 7

hiraditya added a comment to D36423: [libc++] Introsort based sorting function.

Ping!

Thu, Sep 7, 9:27 AM

Wed, Sep 6

hiraditya added inline comments to D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.
Wed, Sep 6, 2:30 PM
hiraditya updated the diff for D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

use any_of instead of iterating over the successors.

Wed, Sep 6, 2:29 PM

Aug 23 2017

hiraditya closed D34224: [NFC] remove trailing WS.

Closed by commit: rL311283

Aug 23 2017, 2:46 PM
hiraditya updated the diff for D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

Addressed @dberlin 's comments.

Aug 23 2017, 9:19 AM
hiraditya added a comment to D36113: [Loop Vectorize] Vectorize Loops with Backward Dependence.

Two high-level thoughts:

  1. Is this transformation always profitable even if we don't later vectorize? I worry that you're taking a stream of accesses that generally appear in order and making them appear out of order. That could have odd effects. Maybe this should all be a utility that the vectorizer uses more directly?

Agreed, we will evaluate if we can this pass as a utility for vectorizer. In the past we tried that but got stuck because we were unable to recompute loop-access-info once the instructions have been reordered. Maybe you can help us here.

Aug 23 2017, 9:18 AM
hiraditya added a comment to D36113: [Loop Vectorize] Vectorize Loops with Backward Dependence.

Two high-level thoughts:

  1. Is this transformation always profitable even if we don't later vectorize? I worry that you're taking a stream of accesses that generally appear in order and making them appear out of order. That could have odd effects. Maybe this should all be a utility that the vectorizer uses more directly?
  2. I don't think a goal of this should be to provide backup handling of things that LICM misses but MemorySSA can prove are loop invariant. We should improve LICM by making it use MemorySSA (see work on this in D35741 - pushing this along might help?). We could run LICM right before we vectorize too.
Aug 23 2017, 8:58 AM

Aug 21 2017

hiraditya updated the diff for D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

Updated MemorySSA updates.
Outlined functions from codegen part.

Aug 21 2017, 3:31 PM

Aug 20 2017

hiraditya added a comment to D36423: [libc++] Introsort based sorting function.

Results with the patch.

Aug 20 2017, 1:19 PM
hiraditya committed rL311283: [NFC] remove trailing WS.
[NFC] remove trailing WS
Aug 20 2017, 3:41 AM
hiraditya committed rL311281: [Loop Vectorize] Added a separate metadata.
[Loop Vectorize] Added a separate metadata
Aug 20 2017, 3:34 AM
hiraditya closed D36220: [Loop Vectorize] Added a separate metadata by committing rL311281: [Loop Vectorize] Added a separate metadata.
Aug 20 2017, 3:34 AM

Aug 17 2017

hiraditya added a reviewer for D34566: [loop idiom Recognition] support memcpy for multiple consecutive loads and stores: hiraditya.
Aug 17 2017, 8:37 AM

Aug 15 2017

hiraditya added a reviewer for D36220: [Loop Vectorize] Added a separate metadata : hiraditya.
Aug 15 2017, 10:22 AM
hiraditya added inline comments to D36113: [Loop Vectorize] Vectorize Loops with Backward Dependence.
Aug 15 2017, 10:16 AM

Aug 11 2017

hiraditya added inline comments to D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.
Aug 11 2017, 12:06 PM
hiraditya updated the diff for D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

Remove dead comments.

Aug 11 2017, 12:05 PM
hiraditya updated the diff for D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

Added Comments

Aug 11 2017, 9:26 AM

Aug 10 2017

hiraditya updated the diff for D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

Based on suggestions from @dberlin, I have updated the patch:

  1. Compute iterated post-dominance frontiers
  2. Iterate on post-dominator tree to insert CHIargs more efficiently
Aug 10 2017, 4:24 PM

Aug 7 2017

hiraditya added a comment to D36113: [Loop Vectorize] Vectorize Loops with Backward Dependence.

@hfinkel , I'd appreciate your feedback, and suggestions for improvement.
Thanks,

Aug 7 2017, 9:20 AM

Aug 3 2017

hiraditya added a comment to D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

I tried a simple df walk like this, it crashes the compiler for the test cases llvm/test/Transforms/GVNHoist/infinite-loop-indirect.ll, and llvm/test/Transforms/GVNHoist/infinite-loop-direct.ll:

auto PrevBB = PDT->getNode(nullptr);
 for (auto it = df_begin(PrevBB); it != df_end(PrevBB);
      ++it) {
 }

These test cases are added in this patch.

Thanks,

I tried running loop like yours in a couple of my unittests (DominatorTreeTest.cpp) and it seems to work:

auto PrevBB = PDT->getNode(nullptr);
for (auto it = df_begin(PrevBB); it != df_end(PrevBB);
     ++it) {
  auto BB = it->getBlock();
  outs() << (BB ? BB->getName() : "virtual root") << "\n";
}

Could you prepare a reduced repro for the crash you saw?

Thanks,
Kuba

Aug 3 2017, 2:36 PM
hiraditya added a comment to D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

Can you illustrate how to perform a DFS walk on a post-dom tree with your patch. Also, how would I get the (virtual) root node of post-dom tree.

Thanks,

You can get the virtual root by calling PDT.getNode(nullptr). Then you can use something like llvm/ADT/DepthFirstIterator.h or llvm/ADT/PostOrderIterator.h to run DFS on it. Implementing a custom DFS should also be easy.

Aug 3 2017, 2:15 PM
hiraditya added a comment to D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.
Aug 3 2017, 1:22 PM
hiraditya added inline comments to D36113: [Loop Vectorize] Vectorize Loops with Backward Dependence.
Aug 3 2017, 7:56 AM

Aug 2 2017

hiraditya added inline comments to D36113: [Loop Vectorize] Vectorize Loops with Backward Dependence.
Aug 2 2017, 8:03 AM
hiraditya added a comment to D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

For some reason phabricator missed the following comments:

Aug 2 2017, 8:00 AM

Aug 1 2017

hiraditya updated subscribers of D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

Such a mapping is by definition n^2 space, and i'm having trouble seeing why it is necessary.

Here is what you are doing:
For each instruction with the same VN:

find the post-dominance frontier of the block of the instruction
Insert a chi there, with certain arguments.

This is unnecessarily wasteful (you may compute the same pdf again and again).

Here is what SSUPRE (and you), should do:

Collect all the blocks of the instructions with the same VN into defining blocks.
Compute the PDF using IDFCalculator.
Place empty chis in the PDF.

At this point, you have two options:

Walk post-dominator tree top-down and use a stack to store the last value you see.
When you hit a chi from a given edge, the value to use as the argument is at the top of the stack.

This is O(Basic Blocks)

Aug 1 2017, 9:04 AM

Jul 27 2017

hiraditya added a comment to D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

FYI: IDFCalculator can compute the PostDominanceFrontier in linear time.

I was unable to find how to pass the root node of inverse graph, because there might be more than one root.
Thanks,

No.
The graph always has one root, virtual or not.
Once kuba's latest patch is committed, it will *always* be virtual, actually.

But i'm not sure why that would stop you one way or the other?
The IDF calculator only asks for the defining blocks, not the root.
You can hand it all CFG blocks and it should work fine.

Jul 27 2017, 3:33 PM

Jul 26 2017

hiraditya added a comment to D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.

FYI: IDFCalculator can compute the PostDominanceFrontier in linear time.

Jul 26 2017, 3:31 PM
hiraditya created D35918: [GVNHoist] Factor out reachability to search for anticipable instructions quickly.
Jul 26 2017, 2:37 PM
hiraditya added inline comments to D35597: [Dominators] Move root-finding out of DomTreeBase and simplify it.
Jul 26 2017, 11:11 AM

Jul 6 2017

hiraditya added inline comments to D35035: [InstCombine] Prevent memcpy generation for small data size.
Jul 6 2017, 1:56 PM

Jun 30 2017

hiraditya abandoned D34768: Remove creation of vector to store loop indices.
Jun 30 2017, 6:15 AM

Jun 28 2017

hiraditya created D34768: Remove creation of vector to store loop indices.
Jun 28 2017, 11:08 AM

Jun 14 2017

hiraditya created D34224: [NFC] remove trailing WS.
Jun 14 2017, 4:26 PM
hiraditya committed rL305427: [locale] Avoid copy of __atoms when char_type is char.
[locale] Avoid copy of __atoms when char_type is char
Jun 14 2017, 4:18 PM
hiraditya closed D30268: Avoid copy of __atoms when char_type is char by committing rL305427: [locale] Avoid copy of __atoms when char_type is char.
Jun 14 2017, 4:18 PM
hiraditya updated the diff for D30268: Avoid copy of __atoms when char_type is char.

Addressed comments from Eric.

Jun 14 2017, 10:02 AM

Jun 12 2017

hiraditya added a comment to D22630: Loop rotation.

@mzolotukhin Please let me know if you have any further comments.

Jun 12 2017, 1:13 PM

Jun 9 2017

hiraditya removed a reviewer for D31349: IR: Replace the "Linker Options" module flag with "llvm.linker.options" named metadata.: hiraditya.
Jun 9 2017, 10:37 AM
hiraditya removed a reviewer for D33922: Apply summary-based dead stripping to regular LTO modules with summaries.: hiraditya.
Jun 9 2017, 10:37 AM
hiraditya removed a reviewer for D33961: encode YAML scalars using double quotes so all values can be expressed: hiraditya.
Jun 9 2017, 10:36 AM
hiraditya removed a reviewer for D33971: Object: Have the irsymtab builder take a string table builder. NFCI.: hiraditya.
Jun 9 2017, 10:36 AM
hiraditya removed a reviewer for D33972: Object: Add version and producer fields to the irsymtab header. NFCI.: hiraditya.
Jun 9 2017, 10:36 AM
hiraditya removed a reviewer for D33973: Bitcode: Write the irsymtab to disk.: hiraditya.
Jun 9 2017, 10:35 AM
hiraditya removed a reviewer for D33974: Object: Teach irsymtab::read() to try to use the irsymtab that we wrote to disk.: hiraditya.
Jun 9 2017, 10:35 AM
hiraditya removed a reviewer for D33978: MC, Object: Reserve a section type, SHT_LLVM_ODRTAB, for the ODR table.: hiraditya.
Jun 9 2017, 10:35 AM

Jun 7 2017

hiraditya added a comment to D30268: Avoid copy of __atoms when char_type is char.

Ping

Jun 7 2017, 9:00 PM

May 26 2017

hiraditya added a comment to D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.

@dberlin
When SSAPRE inserts PHI (expression PHIs), it does so at places where (potentially) multiple expressions may merge. If a PHI has a bottom (⊥) entry, that means the expression is partially available.
The concept may work for GVN-Hoist to help factor out anticipability by working on inverted graph. If we insert an outgoing PHI (if I may), to a basic block with multiple successors, as instructions are hoisted upwards to a nearest common dominator.
And we start walking the CFG to figure out if any outgoing PHI has a ⊥, that means the expression is not anticipable in the basic block having that outgoing PHI.
To minimize the number of outgoing PHIs, we will only insert them for expressions with multiple occurrences.
This will help remove the need to check for reachability.

May 26 2017, 1:01 PM
hiraditya added a comment to D24805: [GVNSink] Initial GVNSink prototype.

Thanks Danny,

I've committed the patch after changing from std::stable_sort to std::sort (I didn't need it, I was being paranoid debugging a heisenbug). This was good timing as today is my last day at ARM and in a couple of hours I will lose access to my development machine! :)

Thanks for your last reply; I now, finally, have got it! I spent yesterday prototyping and have something that conceptually works. It'll need a lot more work though. Watch this space ;)

Cheers,

James

May 26 2017, 12:42 PM
hiraditya added a comment to D22630: Loop rotation.

Ping

May 26 2017, 9:02 AM

May 23 2017

hiraditya added a comment to D30268: Avoid copy of __atoms when char_type is char.

Ping

May 23 2017, 12:56 PM

May 18 2017

hiraditya added inline comments to D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.
May 18 2017, 2:37 PM

May 11 2017

hiraditya updated the diff for D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.

Adding ':' for basic block labels in the testcase

May 11 2017, 9:01 AM

May 10 2017

hiraditya updated the diff for D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.

Addressed @chandlerc 's comments: Essentially, I've added test cases for cycles due to direct branches, indirect branches and invoke instructions.

May 10 2017, 1:44 PM

May 8 2017

hiraditya added a comment to D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.

You are continuing to argue that you do not need to add tests because they will pass. That seems to be missing the point. Tests are what verify and validate these kinds of arguments and assumptions, both now and in the future.

I'll add more tests which will reflect different aspects of cyclic control flow. I was trying to explain what program points handle specific cases pointed by you. It will be good if you can suggest any resources which can help create a variety of CFGs.

May 8 2017, 5:25 PM
hiraditya added a comment to D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.

I don't see what would have addressed my concerns.

There still is only a single test case for an infinite loop. There are *several different* CFGs that fail to terminate. You should be testing them.

Examples off the top of my head:

  • A non-loop cycle in the CFG.

The code checks for cycle, not loops so it can detect all kinds of explicit cycles as different from other three you mentioned.

May 8 2017, 4:45 PM
hiraditya updated the diff for D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.

Addressed comments from @chandlerc and @dberlin

May 8 2017, 3:05 PM
hiraditya added a comment to D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.

I'm at a loss to understand why you believe you need to compute joint post-dominance (which is what this is) to compute ANTIC.

If the set of BasicBlocks (WL) do not joint-post-dominate the hoisting point (HoistBB), then the expression to be hoisted (from WL) cannot be ANTIC in HoistBB.

Sure.
That is definitely a way of computing it.
It is a generally slow and unused way of computing it, because there are only certain points in the SSA graph where ANTIC can actually change.

It is a necessary condition what I'm checking here.

It is not necessary to perform graph reachability to do this.

https://pdfs.semanticscholar.org/6d0f/07ff330402b46e83d46142e202069d9aeceb.pdf

Stare at the down-safety step.
With a few bits, it is only actually necessary to compute and check antic at the possible phis you would insert to do your hoisting.

May 8 2017, 2:59 PM
hiraditya added a comment to D30268: Avoid copy of __atoms when char_type is char.

Ping

May 8 2017, 8:40 AM

May 5 2017

hiraditya committed rL302238: [LoopIdiom] check for safety while expanding.
[LoopIdiom] check for safety while expanding
May 5 2017, 8:10 AM
hiraditya closed D32674: [LoopIdiom] PR32811 check for safety while expanding by committing rL302238: [LoopIdiom] check for safety while expanding.
May 5 2017, 8:05 AM

May 1 2017

hiraditya updated the diff for D32674: [LoopIdiom] PR32811 check for safety while expanding.

Addressed Eli's comments.

May 1 2017, 6:25 PM
hiraditya added inline comments to D32674: [LoopIdiom] PR32811 check for safety while expanding.
May 1 2017, 5:21 PM
hiraditya added inline comments to D32674: [LoopIdiom] PR32811 check for safety while expanding.
May 1 2017, 1:30 PM
hiraditya added a comment to D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.

I'm at a loss to understand why you believe you need to compute joint post-dominance (which is what this is) to compute ANTIC.

If the set of BasicBlocks (WL) do not joint-post-dominate the hoisting point (HoistBB), then the expression to be hoisted (from WL) cannot be ANTIC in HoistBB.

Sure.
That is definitely a way of computing it.
It is a generally slow and unused way of computing it, because there are only certain points in the SSA graph where ANTIC can actually change.

It is a necessary condition what I'm checking here.

It is not necessary to perform graph reachability to do this.

https://pdfs.semanticscholar.org/6d0f/07ff330402b46e83d46142e202069d9aeceb.pdf

Stare at the down-safety step.
With a few bits, it is only actually necessary to compute and check antic at the possible phis you would insert to do your hoisting.

May 1 2017, 1:26 PM
D30268: Avoid copy of __atoms when char_type is char now requires changes to proceed.

Ping

May 1 2017, 9:12 AM

Apr 29 2017

hiraditya updated the diff for D32674: [LoopIdiom] PR32811 check for safety while expanding.
Apr 29 2017, 10:44 PM
hiraditya created D32674: [LoopIdiom] PR32811 check for safety while expanding.
Apr 29 2017, 5:39 PM

Apr 27 2017

hiraditya added a comment to D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.

I'm at a loss to understand why you believe you need to compute joint post-dominance (which is what this is) to compute ANTIC.

Apr 27 2017, 3:05 PM
hiraditya created D32614: [GVNHoist] Fix: PR32821, add check for anticipability in case of infinite loops.
Apr 27 2017, 12:25 PM
hiraditya added inline comments to D32140: Global code motion of congruent computations.
Apr 27 2017, 11:43 AM

Apr 26 2017

hiraditya updated the summary of D32140: Global code motion of congruent computations.
Apr 26 2017, 12:07 PM
hiraditya updated the diff for D32140: Global code motion of congruent computations.

Sink to immediate successors, update memory SSA when sinking.

Apr 26 2017, 11:59 AM

Apr 24 2017

D22630: Loop rotation now requires changes to proceed.

Ping

Apr 24 2017, 8:40 AM

Apr 21 2017

hiraditya added inline comments to D30268: Avoid copy of __atoms when char_type is char.
Apr 21 2017, 9:38 AM
hiraditya updated the diff for D30268: Avoid copy of __atoms when char_type is char.

Minimized the diff by putting #ifdefs inside the function.

Apr 21 2017, 9:38 AM

Apr 17 2017

hiraditya added reviewers for D32140: Global code motion of congruent computations: dberlin, sebpop.
Apr 17 2017, 2:38 PM
hiraditya created D32140: Global code motion of congruent computations.
Apr 17 2017, 2:34 PM

Apr 3 2017

hiraditya added a comment to D22630: Loop rotation.

Ping

Apr 3 2017, 9:11 AM

Mar 20 2017

hiraditya added a comment to D22630: Loop rotation.

Ping

Mar 20 2017, 9:03 AM

Mar 17 2017

hiraditya updated the diff for D31035: [GVNHoist] Call isGuaranteedToTransferExecutionToSuccessor on each instruction.

Updated comments.

Mar 17 2017, 1:52 PM
hiraditya updated the diff for D31035: [GVNHoist] Call isGuaranteedToTransferExecutionToSuccessor on each instruction.

Mark those basic blocks which does not guarantee progress as barriers and use them subsequently while checking for availability during hoisting.

Mar 17 2017, 1:46 PM
hiraditya added a comment to D30667: GVNHoist: handle basic blocks with UnreachableInst.

There is? We could propagate the unreachableness of this function to its callsites, but I don't see what that has to do with the value of the function argument.

Okay, so to close this out, what would we like to do about isGuaranteedToTransferExecutionToSuccessor?
Continue have it return false?

Past that, it's clear additional bugs should be filed against gvnhoist.

My inclination would be to have it explicitly (with a nice comment) return true. That would make bugs like the GVNHoist one we're talking about here more obviously buggy.

Mar 17 2017, 10:14 AM

Mar 16 2017

hiraditya added a comment to D30268: Avoid copy of __atoms when char_type is char.

Ping

Mar 16 2017, 11:29 AM
hiraditya retitled D31035: [GVNHoist] Call isGuaranteedToTransferExecutionToSuccessor on each instruction from Call isGuaranteedToTransferExecutionToSuccessor on each instruction to [GVNHoist] Call isGuaranteedToTransferExecutionToSuccessor on each instruction.
Mar 16 2017, 11:29 AM
hiraditya added a comment to D30667: GVNHoist: handle basic blocks with UnreachableInst.

Okay, so to close this out, what would we like to do about isGuaranteedToTransferExecutionToSuccessor?
Continue have it return false?

Past that, it's clear additional bugs should be filed against gvnhoist.

Mar 16 2017, 9:49 AM
hiraditya created D31035: [GVNHoist] Call isGuaranteedToTransferExecutionToSuccessor on each instruction.
Mar 16 2017, 9:47 AM
hiraditya committed rL297955: Fix: Refactor SimplifyCFG:canSinkInstructions [NFC].
Fix: Refactor SimplifyCFG:canSinkInstructions [NFC]
Mar 16 2017, 7:21 AM
hiraditya closed D30116: Refactor SimplifyCFG:canSinkInstructions [NFC] by committing rL297955: Fix: Refactor SimplifyCFG:canSinkInstructions [NFC].
Mar 16 2017, 7:21 AM

Mar 15 2017

hiraditya committed rL297839: Refactor SimplifyCFG:canSinkInstructions [NFC].
Refactor SimplifyCFG:canSinkInstructions [NFC]
Mar 15 2017, 7:38 AM

Mar 10 2017

hiraditya added inline comments to D22630: Loop rotation.
Mar 10 2017, 2:52 PM
hiraditya updated the diff for D22630: Loop rotation.

Removed unreachable from testcases.
Replaced fp* with i64*

Mar 10 2017, 2:52 PM

Mar 9 2017

hiraditya added a comment to D30116: Refactor SimplifyCFG:canSinkInstructions [NFC].

pimg

Mar 9 2017, 9:27 AM
hiraditya added a comment to D30268: Avoid copy of __atoms when char_type is char.

ping

Mar 9 2017, 9:27 AM

Mar 7 2017

hiraditya added a comment to D30667: GVNHoist: handle basic blocks with UnreachableInst.

Sure, and if you want to fix that bug, i think it's worth doing. But i think that's not related to fixing any gvnhoist problem :P

Mar 7 2017, 11:54 AM